12

我想使用 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 数组显示为输出之外，我的程序还应该显示每个步骤的操作。我也参考了这个线程计算前缀总和，但可以从中得到很多帮助。

4

3 回答 3

29

这个问题的答案在这里：Parallel Prefix Sum (Scan) with CUDA和这里：Prefix Sums and their Applications。NVidia 文章提供了使用 CUDA GPU 的最佳实现，卡内基梅隆大学的 PDF 论文解释了该算法。我还使用 MPI 实现了 O(n/p) 前缀和，您可以在此处找到：在我的 github 存储库中。

这是通用算法的伪代码（与平台无关）：

示例 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 示例中所做的那样。

于 2012-10-13T14:51:08.317 回答
2

我只实现了数组中所有元素的总和（Blelloch 的向上扫描减少部分），而不是在 java/opencl 中使用 Aparapi（ https://code.google.com/p/aparapi/ ）的完整前缀总和。它可在https://github.com/klonikar/trial-aparapi/blob/master/src/trial/aparapi/Reducer.java获得，它是针对一般块大小（在代码中称为 localBatchSize）而不是 2 编写的。我发现8 块大小最适合我的 GPU。

虽然实现有效（求和计算是正确的），但它的性能比顺序求和差得多。在我的core-i7（8 核）CPU上，8388608（8MB）个数字的顺序求和大约需要 12 毫秒，GPU（具有 384 个内核的 NVidia Quadro K2000M）上的并行执行大约需要 100 毫秒。我什至已经优化为仅在计算后传输最终总和，而不是整个数组。如果没有这种优化，它会多花 20 毫秒。该实现似乎是根据@marcel-valdez-orozco 回答中描述的算法。

于 2014-11-15T14:31:49.050 回答
-36

以下代码将完成这项工作

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 个元素。

于 2012-04-07T12:21:23.493 回答