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

この質問への答えはここにあります： CUDAを使用した並列プレフィックス合計（スキャン）およびここ：プレフィックス合計とそのアプリケーション。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

java / openclでAparapi（ https://code.google.com/p/aparapi/ ）を使用して完全なプレフィックスの合計ではなく、配列内のすべての要素の合計（Blellochのアップスイープリデュース部分）のみを実装しました。https://github.com/klonikar/trial-aparapi/blob/master/src/trial/aparapi/Reducer.javaで入手でき、2ではなく一般的なブロックサイズ（コードではlocalBatchSizeと呼ばれます）で記述されています。そのブロックサイズ8は、私のGPUに最適です。

実装は機能しますが（合計の計算は正しいです）、順次合計よりもパフォーマンスが大幅に低下します。私のコア-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 に答える