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

Question

关于 NVIDIA GPU，High Performance and Scalable GPU Graph Traversal论文中的作者说：

1-一系列内核调用是批量同步的：每个内核最初都呈现与前一个结果的一致视图。

2-Prefix-sum 是一种批量同步算法原语

我无法理解这两点（虽然我知道基于 GPU 的前缀和），可以帮助我这个概念。

Answer 1

1-一系列内核调用是批量同步的：每个内核最初都呈现与前一个结果的一致视图。

它是关于并行计算模型的：每个处理器都有自己的内存，速度很快（就像 CPU 中的缓存），并且使用存储在那里的值执行计算而没有任何同步。然后进行非阻塞同步 - 处理器放置它迄今为止计算的数据并从其邻居获取数据。然后是另一个同步 - 屏障，这使得它们都互相等待。

2-Prefix-sum 是一种批量同步算法原语

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

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

就我们希望名副其实（高度并发）而言，我们希望在可能的情况下摆脱顺序部分。我们可以通过前缀和来实现。

考虑前缀和关联运算符+。然后 scan on set[5 2 0 3 1]返回 set [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);

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