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 的前缀和)，smeone 可以帮助我这个概念吗？

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);

这是非常幼稚的版本，但可以用来解释。