我正在实现http://www.cs.cmu.edu/~guyb/papers/Ble93.pdf中讨论的前缀和算法。我面临的问题是输入大小不是2的幂我正在使用这个前缀和实现在并行快速排序分区。具体来说,我面临的问题是在下面的下扫相位算法。

 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]

问题1:在上述算法中,假设n=10,对于d=2和k=8,索引k+2^d–1>n。这也是k+2^(d+1)–1>n的情况。这将导致应用程序核心转储。我们应该如何处理n不是2的幂的情况?
问题2:对于输入序列1,1,1,0,0,0,0,0,0,0,1,正确的前缀和是1,2,3,3,3,3,3,3,3,3,4假设我忽略了索引大于n的操作。如果我手动计算,我得到的前缀和是基于上述文件的,3,4,5,6,6,6,6,0,0。
让我知道如何处理这些问题。

最佳答案

如果您不受某些特定语言的限制,请考虑使用c++tbb来利用existing parallel prefix algorithm implementation这是医生的摘录。
说明
并行扫描(range,body)计算并行前缀,也称为并行扫描。这种计算是并行计算中的一个高级概念,在似乎具有内在串行依赖关系的场景中有时很有用。
并行前缀的数学定义如下。设x为左恒等元id为x的关联运算序列z0,z1,…zn-1上的x的平行前缀是序列y0,y1,y2,…yn-1,其中:

y0 = id× × z0
yi = yi-1 × zi

例如,如果x是加法,则parallel前缀对应于一个运行和。并行前缀的串行实现是:
T temp = id×;
for( int i=1; i<=n; ++i ) {
    temp = temp × z[i];
    y[i] = temp;
}

parallel prefix通过重新关联x的应用程序并使用两个过程来并行执行此操作。它可以调用×最多是串行前缀算法的两倍。给定正确的粒度和足够的硬件线程,它可以执行串行前缀,因为即使它做更多的工作,它也可以跨多个硬件线程分配工作。

07-24 09:46
查看更多