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

Question

我有一个用 C++ 编写的高性能动态程序，它的结果放在一个 M × N 表中，大约是 2000 行 × 30000 列。
每个条目（r，c）取决于表中其他几列中的几行。

跨P个处理器并行计算行r的最明显方法是静态分区数据：即，让处理器p计算所有有效k的条目 (r, p + k P ) 。

但是，不同列的条目计算时间略有不同（例如，一个可能需要五倍于另一个），所以我想动态分区数据以获得更好的性能，通过避免停滞提前完成的 CPU 反而让它们从仍在追赶的 CPU 中窃取工作。

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

所以，我的问题是：
有没有办法以更可扩展的方式执行这种动态分区（即在计算每个条目后不必访问单个全局计数器）？

score 0 · Accepted Answer

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

要使用 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 的结构是相似的。

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

巴里

1 回答 1