2

私は OpenMP の初心者です。私はそのような問題に出くわします。

M長さのマスク配列がありN、その要素はeither 0 or 1です。i条件を満たすすべてのインデックスを抽出M[i]=1し、それらを新しい配列に格納したいと考えていTます。

この問題は OpenMP によって高速化できますか?

次のコードを試しました。しかし、それはパフォーマンス効率的ではありません。

int count = 0;
#pragma omp parallel for
for(int i = 0; i < N; ++i) {
    if(M[i] == hashtag) {
        int pos = 0;
        #pragma omp critical (c1)
        pos = count++;
        T[pos] = i;
}
4

3 に答える 3

2

Floris の高速関数に基づいて、OpenMP を使用してより高速なソリューションを見つける方法を見つけられるかどうかを確認しようとしました。foo_v2私は 2 つの関数を思いつきましたfoo_v3。どちらが大きい配列の方foo_v2が高速で、密度に関係なくfoo_v3高速で、疎な配列の方が高速です。この関数foo_v2は基本的に、幅のある 2D 配列と、各スレッドのカウントを含むN*nthreads配列を作成します。countsaこれは、コードでよりよく説明されています。次のコードは、T に書き出されたすべての要素をループします。

for(int ithread=0; ithread<nthreads; ithread++) {
    for(int i=0; i<counta[ithread]; i++) {
        T[ithread*N/nthread + i]
    } 
}

この関数foo_v3は、要求に応じて 1D 配列を作成します。いずれの場合もN、OpenMP のオーバーヘッドを克服するにはかなり大きくする必要があります。M以下のコードは、約 10%の密度で 256MB にデフォルト設定されています。私の 4 コア Sandy Bridge システムでは、OpenMP 関数は両方とも 2 倍以上高速です。密度を 50%foo_v2にすると、さらに約 2 倍foo_v3速くなりますが、もはや速くはなりません。 

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>

int foo_v1(int *M, int *T, const int N) {   
    int count = 0;
    for(int i = 0; i<N; i++) {
        T[count] = i;
        count += M[i];
    }
    return count;
}

int foo_v2(int *M, int *T, int *&counta, const int N) {
    int nthreads;
    #pragma omp parallel
    {
        nthreads = omp_get_num_threads();
        const int ithread = omp_get_thread_num();   
        #pragma omp single
        counta = new int[nthreads];
        int count_private = 0;      
        #pragma omp for
        for(int i = 0; i<N; i++) {
            T[ithread*N/nthreads + count_private] = i;
            count_private += M[i];
        }
        counta[ithread] = count_private;
    }
    return nthreads;
}

int foo_v3(int *M, int *T, const int N) {
    int count = 0;

    int *counta = 0;    
    #pragma omp parallel reduction(+:count)
    {
        const int nthreads = omp_get_num_threads();
        const int ithread = omp_get_thread_num();   
        #pragma omp single
        {
            counta = new int[nthreads+1];
            counta[0] = 0;
        }
        int *Tprivate = new int[N/nthreads];

        int count_private = 0;      
        #pragma omp for nowait
        for(int i = 0; i<N; i++) {
            Tprivate[count_private] = i;
            count_private += M[i];
        }
        counta[ithread+1] = count_private;
        count += count_private;

        #pragma omp barrier
        int offset = 0;
        for(int i=0; i<(ithread+1); i++) {
            offset += counta[i];
        }

        for(int i=0; i<count_private; i++) {
            T[offset + i] = Tprivate[i];
        }

        delete[] Tprivate;
    }
    delete[] counta;
    return count;
}

void compare(const int *T1, const int *T2, const int N, const int count, const int *counta, const int nthreads) {
    int diff = 0;
    int n = 0;
    for(int ithread=0; ithread<nthreads; ithread++) {
        for(int i=0; i<counta[ithread]; i++) {
            int i2 = N*ithread/nthreads+i;
            //printf("%d %d\n", T1[n], T2[i2]);
            int tmp = T1[n++] - T2[i2];
            if(tmp<0) tmp*=-1;
            diff += tmp;
        }
    }
    printf("diff %d\n", diff);
}

void compare_v2(const int *T1, const int *T2, const int count) {
    int diff = 0;
    int n = 0;
    for(int i=0; i<count; i++) {
        int tmp = T1[i] - T2[i];
        //if(tmp!=0) printf("%i %d %d\n", i, T1[i], T2[i]);
        if(tmp<0) tmp*=-1;
        diff += tmp;
    }
    printf("diff %d\n", diff);
}

int main() {
    const int N = 1 << 26;

    printf("%f MB\n", 4.0*N/1024/1024);
    int *M = new int[N];
    int *T1 = new int[N];
    int *T2 = new int[N];
    int *T3 = new int[N];

    int *counta;
    double dtime;
    for(int i=0; i<N; i++) {
        M[i] = ((rand()%10)==0);
    }

    //int repeat = 10000;
    int repeat = 1;
    int count1, count2;
    int nthreads;
    dtime = omp_get_wtime();
    for(int i=0; i<repeat; i++) count1 = foo_v1(M, T1, N);
    dtime = omp_get_wtime() - dtime;
    printf("time v1 %f\n", dtime);

    dtime = omp_get_wtime();
    for(int i=0; i<repeat; i++) nthreads = foo_v2(M, T2, counta, N);
    dtime = omp_get_wtime() - dtime;
    printf("time v2 %f\n", dtime);
    compare(T1, T2, N, count1, counta, nthreads);

    dtime = omp_get_wtime();
    for(int i=0; i<repeat; i++) count2 = foo_v3(M, T3, N);
    dtime = omp_get_wtime() - dtime;
    printf("time v2 %f\n", dtime);
    printf("count1 %d, count2 %d\n", count1, count2);
    compare_v2(T1, T3, count1); 

}
于 2013-08-16T10:00:32.997 に答える
1

重要な操作は;のatomic代わりにする必要があります。critical実際にあなたの場合、atomic capture句を使用する必要があります：

int pos, count = 0;                     // pos declared outside the loop
#pragma omp parallel for private(pos)   // and privatized, count is implicitly
for(int i = 0; i < N; ++i) {            // shared by all the threads
    if(M[i]) {
        #pragma omp atomic capture
            pos = count++;
        T[pos] = i;
    }
}

この回答を見て、 atomicOpenMPで可能なすべての操作の概要を把握してください。

于 2013-08-08T14:13:34.180 に答える