并行前缀和 - 最快的实现

Question

我想用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数组显示为输出外,我的程序还应显示每个步骤的操作.我也引用这个线程计算前缀总和,但可以得到很多帮助.

Answer 1

这个问题的答案在这里:http://http.developer.nvidia.com/GPUGems3/gpugems3_ch39.html ,这里是http://www.cs.cmu.edu/~guyb/papers/Ble93.pdf.NVidia文章使用CUDA GPU提供了最佳实现,卡内基梅隆大学PDF论文解释了该算法.我还使用MPI实现了一个O(n/p)前缀和,你可以在这里找到:在我的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示例中所做的那样.

Answer 2

下面的代码将完成这项工作

void prfxSum()
{
    int *x=0;
    int *y=0;
    int sum=0;
    int num=0;
    int i=0;

    cout << "Enter the no. of elements in input array : ";
    cin >> num;

    x = new int[num];
    y = new int[num];

    while(i < num)
    {
        cout << "Enter element " << i+1 << " : ";
        cin >> x[i++];
    }

    cout << "Output array :- " << endl;
    i = 0;
    while(i < num)
    {
        sum += x[i];
        y[i] = sum;
        cout << y[i++] << ", ";
    }

    delete [] x;
    delete [] y;
}

以下是执行时的输出

Enter the no. of elements in input array : 8
Enter element 1 : 1
Enter element 2 : 2
Enter element 3 : 3
Enter element 4 : 4
Enter element 5 : 5
Enter element 6 : 6
Enter element 7 : 7
Enter element 8 : 8
Output array :- 
1, 3, 6, 10, 15, 21, 28, 36

您可以通过从文件等提供数组 x[] 的 1000 个元素来避免用户输入。