c++ - 并行化大型动态程序

我有一个高性能的C++动态程序，它的结果放在一个M×N的表中，大概是2000行×30000列的数量级。
每个条目(r、c)都取决于表中其他几列中的几行。

在 P 个处理器上并行计算行 r 的最明显方法是对数据进行静态分区:即，让处理器 < em>p 为所有有效的 k 计算条目 (r, p + k P) .

但是，不同列的条目计算时间略有不同(例如，一个可能需要另一个的五倍)，所以我想对数据进行动态分区为了获得更好的性能，可以避免提前完成的 CPU 停顿，而是让它们从仍在追赶的 CPU 那里窃取工作。

解决此问题的一种方法是保留一个原子全局计数器，该计数器指定已计算的列数，并在每次 CPU 需要更多工作时增加它。
但是，这会强制所有 CPU 在计算表中的每个条目后访问相同全局计数器——也就是说，它在某种程度上序列化了程序。由于计算每个条目或多或少是一个快速的过程，这在某种程度上是不可取的。

所以，我的问题是:
有没有办法以更具可扩展性的方式执行此动态分区(即无需在计算每个条目后访问单个全局计数器)？

最佳答案

我假设您正在为新值使用第二个数组。如果是这样，听起来 TBB 或 Cilk Plus 的循环结构都可以。两者都使用工作窃取在可用处理器之间分配工作，当一个处理器用完工作时，它将从有可用工作的处理器中窃取工作。这平衡了数据的“ block 度”。

要使用 Cilk，您需要一个支持 Cilk Plus 的编译器。 GCC 4.9 和 Intel 编译器都支持它。通常你会写这样的东西:

cilk_for (int x = 0; x < XMAX; x++) {
    for (int y = 0; y < YMAX; y++) {
        perform-the-calculation;
    }
}

TBB 的结构相似。

另一种方法是以缓存不经意的方式“平铺”计算。也就是说，您实现自己的分而治之算法，该算法将计算分解为高速缓存高效的 block 。参见 http://www.1024cores.net/home/parallel-computing/cache-oblivious-algorithms/implementation有关缓存不经意算法的更多信息。

巴里

关于c++ - 并行化大型动态程序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29047591/