algorithm - 前缀和如何成为批量同步算法原语？

Question

关于 NVIDIA GPU，作者在 High Performance and Scalable GPU Graph Traversal论文说:

1-A sequence of kernel invocations is bulk- synchronous: each kernel is initially presented with a consistent view of the results from the previous.

2-Prefix-sum is a bulk-synchronous algorithmic primitive

我无法理解这两点(虽然我知道基于 GPU 的前缀和)，有人可以帮助我这个概念吗？

Answer 1

1-A sequence of kernel invocations is bulk- synchronous: each kernel is initially presented with a consistent view of the results from the previous.

它是关于并行计算模型的:每个处理器都有自己的快速内存(就像 CPU 中的缓存)，并且使用存储在那里的值执行计算而无需任何同步。然后发生非阻塞同步 - 处理器放置它到目前为止计算的数据并从它的邻居那里获取数据。然后是另一个同步 - 屏障，这使得它们都互相等待。

2-Prefix-sum is a bulk-synchronous algorithmic primitive

我相信这就是 BSP 模型的第二步 - 同步。这就是处理器为下一步存储和获取数据的方式。

模型的名称暗示它是高度并发的(许多进程相对于彼此同步工作)。这就是我们到达第二点的方式。

就我们想要名副其实(高度并发)而言，我们希望在可能的情况下摆脱顺序部分。我们可以使用前缀和来实现。

考虑前缀和结合运算符 +。然后扫描集合 [5 2 0 3 1] 返回集合 [0 5 7 7 10 11]。所以，现在我们可以替换这样的顺序伪代码:

foreach i = 1...n
    foo[i] = foo[i-1] + bar(i);

使用这个伪代码，现在可以并行(!):

foreach(i)
    baz[i] = bar(i);
scan(foo, baz);

这是非常幼稚的版本，但解释起来没问题。