openMP最長的常見子序列

我正在使用openMP編寫Longest Common Subsequence算法的並行版本。openMP最長的常見子序列

順序版本如下（和它工作正常）：

// Preparing first row and first column with zeros 
for(j=0; j < (len2+1); j++) 
    score[0][j] = 0; 

for(i=0; i < (len1+1); i++) 
    score[i][0] = 0; 

// Calculating scores 
for(i=1; i < (len1+1); i++) { 
    for(j=1; j < (len2+1) ;j++) { 
     if (seq1[i-1] == seq2[j-1]) { 
       score[i][j] = score[i-1][j-1] + 1; 
     } 
     else { 
      score[i][j] = max(score[i-1][j], score[i][j-1]); 
     } 
    } 
}

關鍵部分是填補了得分矩陣，這是我想主要是並行的部分。

做到這一點（我選擇）的一種方法是：用反對角線填充矩陣，所以總是滿足左，上和左上的依賴關係。簡而言之，我會跟蹤對角線（第三個循環，下面的變量i），並且線程並行填充對角線。爲此，我寫這個代碼：

void parallelCalculateLCS(int len1, int len2, char *seq1, char *seq2) { 

int score[len1 + 1][len2 + 1]; 
int i, j, k, iam; 
char *lcs = NULL; 

for(i=0;i<len1+1;i++) 
    for(j=0;j<len2+1;j++) 
     score[i][j] = -1; 

#pragma omp parallel default(shared) private(iam) 
{ 
    iam = omp_get_thread_num(); 
// Preparing first row and first column with zeros 
    #pragma omp for 
    for(j=0; j < (len2+1); j++) 
     score[0][j] = iam; 

    #pragma omp for 
    for(i=0; i < (len1+1); i++) 
     score[i][0] = iam; 

// Calculating scores 
    for(i=1; i < (len1+1); i++) { 
     k=i; 
     #pragma omp for 
     for(j=1; j <= i; j++) { 
      if (seq1[k-1] == seq2[j-1]) { 
       // score[k][j] = score[k-1][j-1] + 1; 
       score[k][j] = iam; 
      } 
      else { 
      // score[k][j] = max(score[k-1][j], score[k][j-1]); 
       score[k][j] = iam; 
      } 
      #pragma omp atomic 
      k--; 
     } 
    } 

} 
}

前兩個迴路（第一行和列）正常工作和線程填補細胞在平衡的方式。

當談到填補矩陣（對角），沒有什麼效果。我試圖調試它，但似乎線程會隨機地執行和寫入東西。

我找不出什麼問題，因爲在前兩個循環中根本沒有問題。

任何想法？

附：我知道以對角方式訪問矩陣非常緩存不友好，線程可能不平衡，但我現在只需要它就可以工作。

P.S. ＃2我不知道它是否有用，但我的CPU有多達8個線程。

來源

2014-01-10 boh

#pragma omp atomic表示處理器將一次執行一個操作。您正在尋找#pragma omp for private(k)：處理器將不再共享相同的值。再見，弗朗西斯

來源

2014-01-10 20:03:16 francis

謝謝。但是如果我將k設置爲私人，他們都有k = i作爲它們的初始值，對吧？我怎樣才能讓線程修改矩陣實際對角線的單元格？因爲如果我不修改k，線程將在第K行中出現故障。我希望問題清楚。 – boh

你說得對。 'k'的正確值必須是'k = i-j + 1'。嘗試像這樣：'for（j = 1; j <= i; j ++）{k = i-j + 1; ...}'我可能是一個索引太短或太長... – francis

並注意for循環的邊界，因爲len1 + 1對角線的數目超過了！ – francis

以下嵌套for循環

#pragma omp for 
for(j=1; j <= i; j++)

將並行執行，每個線程與j中沒有特定的順序不同的值。由於沒有在omp for部分中指定，因此所有線程之間默認共享k。因此，根據線程的順序，k將在未知的時間遞減（即使使用omp atomic）。因此，對於固定的j，k的值可能會在執行for循環體的過程中（在if子句之間...）之間發生更改。

來源

2014-01-10 20:00:33

謝謝。但是如果我將k設置爲私人，他們都有k = i作爲它們的初始值，對吧？我怎樣才能讓線程修改矩陣的_actual_對角線的單元格？因爲如果我不修改k，線程將在第K行中出現故障。我希望問題清楚。 – boh

openMP最長的常見子序列

回答

相關問題