OpenMP嵌套循环并行

Question

我使用OpenMP,我遇到了错误结果的问题.

这是代码:

    #pragma omp parallel shared(L,nthreads,chunk) private(tid,i,j){
        tid = omp_get_thread_num();
        if (tid == 0)
        {
            nthreads = omp_get_num_threads();
            printf("Starting matrix multiple example with %d threads\n",nthreads);
            printf("Initializing matrices...\n");
        }

        #pragma omp for schedule (static, chunk) 
        for( i=0; i<SIZE_A;i++){
            for( j=0; j<SIZE_B;j++){
                if(A[i]==B[j]){
                    if(i==0 || j==0)
                        L[i][j]=1;
                    else
                        L[i][j] = L[i-1][j-1] + 1;
                }
                // or reset the matching score to 0
                else
                    L[i][j]=0;
            }
        }
    }

你怎么想,为什么我得到了结果？我应该改变什么？

非常感谢!

Answer 1

你有一个循环数据依赖:

L[i][j] = L[i-1][j-1] + 1;

这里如果交互i并i-1已分配给不同的线程,则无法保证第一个线程在第二个线程开始之前就已完成,因此第二个线程将读取不正确(仍未更新)的值L[i-1][j-1].您可以通过将ordered子句赋予omp for工作共享指令来执行命令,但这会导致并行化.

由于依赖是对角线的,你可以重新考虑你的算法,以某种方式L对角走,而不是行.