我想用C++实现并行前缀和算法。我的程序应该采用输入数组 x[1....N]
,并且它应该在数组 y[N]
中显示输出。 (注意N的最大值为1000。)
到目前为止,我浏览了许多研究论文,甚至浏览了维基百科中的算法。 但是我的程序还应该显示输出、步骤以及每个步骤的操作/说明。
我想要最快的实现,就像我想要最小化操作数量和步骤一样。
例如::
x = {1, 2, 3, 4, 5, 6, 7, 8 } - Input
y = ( 1, 3, 6, 10, 15, 21, 28, 36) - Output
但除了显示 y 数组作为输出外,我的程序还应该显示每个步骤的操作。我也引用这个线程 calculate prefix sum , 但可以从中得到很多帮助。
最佳答案
这个问题的答案在这里:Parallel Prefix Sum (Scan) with CUDA在这里:Prefix Sums and Their Applications . NVidia 文章提供了使用 CUDA GPU 的最佳实现,卡内基梅隆大学 PDF 论文解释了该算法。我还使用 MPI 实现了一个 O(n/p) 前缀和,您可以在这里找到它:In my github repo .
这是通用算法的伪代码(独立于平台):
示例 3. 工作高效的求和扫描算法的上扫(归约)阶段(Blelloch 1990 之后)
for d = 0 to log2(n) – 1 do
for all k = 0 to n – 1 by 2^(d+1) in parallel do
x[k + 2^(d+1) – 1] = x[k + 2^d – 1] + x[k + 2^(d+1) – 1]
示例 4. 工作高效的并行求和扫描算法的向下扫描阶段(Blelloch 1990 之后)
x[n – 1] = 0
for d = log2(n) – 1 down to 0 do
for all k = 0 to n – 1 by 2^(d+1) in parallel do
t = x[k + 2^d – 1]
x[k + 2^d – 1] = x[k + 2^(d+1) – 1]
x[k + 2^(d+1) – 1] = t + x[k + 2^(d+1) – 1]
其中x是输入数据,n是输入的大小,d是并行度(CPU数) .这是一个共享内存计算模型,如果它使用分布式内存,您需要向该代码添加通信步骤,就像我在提供的 Github 示例中所做的那样。
关于c++ - 并行前缀和 - 最快的实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10053629/