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; 
      } 
     } 
    } 

あなたはなぜ私はwrond結果を得ています、どう思いますか？ 変更する必要はありますか？

ありがとうございます！

Answer 1

あなたはループのデータ依存性を持っている：

ここ

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

interations iとi-1が異なるスレッドに割り当てられている場合は、2番目は、このように開始している前に、最初のスレッドが終了しているだろうという保証はありません2番目のスレッドは正しくない（まだ更新されていない）値L[i-1][j-1]を読み込みます。 omp for worksharingディレクティブにordered句を指定することで実行を順序付けることができますが、並列処理が終了します。

依存性が対角線であるので、あなたは何とかL斜めの代わりに、行方向に歩いて、あなたのアルゴリズムを再考することができます。