C语言 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 threadsn",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行走。