0

いくつかの配列のプレフィックス（例out_arr[0]= in_arr[0]、out_arr[1]= in_arr[0]+in_arr[1].. など）の合計を並行して計算するコードがあります。私のコードにはNスレッドがNあり、多数のin_arr要素があり、各スレッドは配列の 1 つの要素のみを処理します。これは良い解決策ではないので、各スレッドで処理したいのですがN/num_of_threads、失敗しました。

値を持つ共有変数を作成し、最初のディレクティブの後ろにあるこの変数を使用してサイクルをN/num_of_threads編成しようとしましたが、stdout でそれらのマジック ナンバーをデバッグできませんでした。for#pragma

これは、«bad» ソリューションの動作バージョンです。

void CalcSum2(int a[], int s[], int n) { 
    int* old = new int [n], *cnt = new int [n]; 
    #pragma omp parallel num_threads(N) {
    int i = omp_get_thread_num(), d = 1; 
    s[i] = a[i]; 
    cnt[i] = 1; 
     #pragma omp barrier 
    while (d < n) { 
        old[i] = s[i]; 
     #pragma omp barrier 
         if (i >= d) { 
             s[i] += old[i-d]; 
         cnt[i]++; 
         } 
         d += d; 
     #pragma omp barrier 
    }
    }
    delete[] old; delete[] cnt; 
    return; 
}
4

2 に答える 2

1

スキャンを並列化する方法では、パフォーマンスを損なう可能性のあるバリアが多すぎます。

マルチコア CPU での並列スキャンは、合計演算の数が からn-1に増加するため、あまり効率的ではありません2n。したがって、時間コストは です2n/m。ここmで、 は CPU コアの数です。

バリアの数を減らすには、まずデータの各セグメントに対して順次スキャンを実行し、次に各セグメントの結果に適切なオフセットを追加します。次のコードは、アイデアのデモです。1Gだと8コアCPUで2.4倍速になりました。len2 番目の部分を改善して、より高いパフォーマンスを得ることができます。

inline void scan(int a[], int s[], int len)
{
    int sum=0.0;
    for(int i=0;i<len;i++) {
        sum+=a[i];
        s[i]=sum;
    }
}

void ParallelScan(int a[], int s[], int len)
{
    int nt;
    int seglen, subseglen;
    int* segsum;
    #pragma omp parallel
    {
        #pragma omp single
        {
            nt = omp_get_num_threads();
            seglen = (len+nt-1)/nt;
            subseglen = (seglen+nt-1)/nt;
            segsum = new int[nt];
        }
        int tid = omp_get_thread_num();
        int start = seglen*tid;
        int end = seglen*(tid+1);
        end = end > len ? len : end;

        scan(&a[start],&s[start],end-start);
        segsum[tid]=s[end-1];
        #pragma omp barrier

        #pragma omp single
        for(int i=1; i<nt; i++) {
            segsum[i]+=segsum[i-1];
        }

        for(int segid=1; segid<nt; segid++) {
            int segstart=seglen*segid;
            int start = segstart + subseglen*tid;
            int end = start + subseglen;
            end = end > len ? len : end;
            end = end > segstart+seglen ? segstart+seglen : end;

            int offset = segsum[segid-1];
            for(int i=start; i<end; i++) {
                s[i]+=offset;
            }
        }
    }


    delete[] segsum;
}
于 2013-10-17T20:40:26.660 に答える