2

我正在修改我很久以前写的一些代码，并决定重写它以更好地利用线程（以及更好地利用一般编程......）。

它位于此处：https ://github.com/buddhabrot/buddhabrot/blob/master/basic.c ：

这是一个呈现佛像分形的应用程序。由于超出这个问题范围的原因，很难使用记忆化来优化它，基本上如果你对此进行分析，超过 99% 的时间都花在最里面的循环中，最终会：

buddhabrot[col][row]++;

多个线程将执行此代码。由于递增不是线程安全的，因此我在这部分内存周围使用了特定的互斥锁。因此，buddhabrot 内存中的每个可寻址位置都有一个单独的互斥体。

现在，这当然比使用一个锁更有效（这肯定会使所有线程相互等待），但它的内存效率较低；看来互斥锁也需要一些数据。我还想知道在具有数百万互斥锁的 pthreads 实现中的其他影响？

我现在还有另外两个策略要考虑：

  • 为地图中的每个“区域”使用一组密度较低的互斥锁。因此，例如，对 [col/16][row/16] 的锁定只会在线程访问与另一个线程相同的 16 像素区域时锁定线程。锁的密度可以动态调整。但是当我对此建模时，我想知道我是否没有解决甚至可能由内核实现的现有问题，而且我也无法真正找到一种方法来解决这个问题而不会减慢速度。我也考虑过“互斥树”，但所有这些在这个循环中都太慢了（给出一个指示，在优化编译器背后的一些数学运算的顺序后，我可以多挤出大约 30% 的处理器时间） . 有没有一个主题，我如何寻找更多关于“互斥密度规划”的信息..？

  • 复制每个线程的内存，这样我什至不必围绕它进行互斥。但这更加内存效率低下。它将解决在不知道其影响的情况下拥有数百万个互斥锁的问题。

那么，还有什么，我能做的更好吗？

4

3 回答 3

4

您可以在 Windows 平台上使用 intrin.h 中的 InterlockedIncrement 等原子增量函数。

#include <intrin.h>

#pragma intrinsic(_InterlockedExchangeAdd, _InterlockedIncrement, _InterlockedDecrement, _InterlockedCompareExchange, _InterlockedExchange)
#define InterlockedExchangeAdd _InterlockedExchangeAdd
#define InterlockedIncrement _InterlockedIncrement
#define InterlockedDecrement _InterlockedDecrement
#define InterlockedCompareExchange _InterlockedCompareExchange
#define InterlockedExchange _InterlockedExchange

#pragma intrinsic(abs, fabs, labs, memcmp, memcpy, memset, strcat, strcmp, strcpy, strlen)
#pragma intrinsic(acos, cosh, pow, tanh, asin, fmod, sinh)
#pragma intrinsic(atan, exp, log10, sqrt, atan2, log, sin, tan, cos)

这种增量是原子的，不需要在矩阵上拥有数百万个互斥锁或全局锁。

于 2011-12-05T13:03:59.360 回答
0

我认为您应该能够对矩阵进行分区，以便每个线程只会更新 1 列。这样他们就不会互相干扰，你也不必锁定。

做一个所有列的中央同步队列，让每个线程去那里获取一个列号，然后它只会更新该列中的值，然后进入下一列的队列，直到全部完成。

那么争用只会出现在中央队列上，与其他队列相比应该是微不足道的。

另外我猜每列中会有足够的行，所以你不会得到错误的共享，这会减慢你的速度。

问候 GJ

于 2011-12-05T13:14:32.553 回答
0

由于您给出的原因，您的第二个设计是更好的选择。为了渲染一个Buddhabrot，你想要建立一个大的矩阵。如果您让每个处理器计算它自己的数组，然后每分钟左右将其结果添加到主数组，则可以避免内存争用。这是唯一需要内存锁的部分，甚至可以通过让每个线程写入自己的文件来避免这种情况。你确实有多个处理器，对吧？如果没有，那么添加线程将不会带来任何好处。

于 2012-11-08T08:59:58.360 回答