2012-05-06 144 views
1

我使用OpenMP並且出現錯誤結果的問題。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結果呢? 我應該改變什麼?

非常感謝!

回答

7

你有一個循環的數據依賴關係:

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

這裏如果interations ii-1已分配給不同的線程,那麼就不能保證第二個已經開始,因此之前的第一個線程將完成第二個線程將讀取不正確(仍未更新)的值L[i-1][j-1]。您可以通過將ordered子句提供給omp for工作共享指令來執行排序,但會導致並行化。

由於依賴關係是對角的,因此您可以重新考慮您的算法,以某種方式對角地行走L而不是行。

+0

嗯......這是最長的常見子字符串問題,由一些英特爾的人解決,我試圖改變它,但遞歸解決方案非常慢,優化不能很好地解釋......謝謝你的幫助Hristo :) – vanste25