OpenMP - パターンマッチングにおける比較の比較

Question

次のアルゴリズムがあります。これは、連続パターン検索アルゴリズムを並列にしようとして作成したものです。

比較をカウントする際に競合状態に陥っていたため、一時変数を作成して削減を試みましたが、シーケンシャルアルゴリズムと同じ量の比較はまだ得られません。

int hostMatch(long *comparisons) 
{ 
    int i = 0, j = 0, k = 0, lastI = textLength-patternLength; 
    long comparisons_tmp = 0; 
    int found = textLength + 1; 

    #pragma omp parallel for reduction(+:comparisons_tmp) \ 
         schedule(static)     \ 
         num_threads(4)      \ 
         default(none)      \ 
         shared(found, comparisons)   \ 
         private(j, k)       \ 
         firstprivate(lastI, textData, patternData, patternLength) 
    for(i = 0; i<= lastI; i++) 
    { 
     if(i < found) 
     { 
      k=i; j=0; 
      while(textData[k] == patternData[j] && j < patternLength) 
      { 
       k++; j++; comparisons_tmp++; 
      } 
      if(j == patternLength) 
      { 
       #pragma omp critical(check) 
       { 
        if(found > i) 
         found = i; 
       } 
      } 
     } 
    } 
    *comparisons = comparisons_tmp; 
// return (found < textLength + 1) ? found : -1; 
    if(found < textLength + 1) 
     return found; 
    else 
     return -1; 
} 

このコードは、順次アルゴリズムの比較のために
3996002000一方、比較TEST0ため
3994004000の量を返します。

次のように元のシーケンシャルコードはでした：

int hostMatch(long *comparisons) 
{ 
int i,j,k, lastI; 

i=0; 
j=0; 
k=0; 
lastI = textLength-patternLength; 
    *comparisons=0; 

while (i<=lastI && j<patternLength) 
{ 
      (*comparisons)++; 
    if (textData[k] == patternData[j]) 
    { 
     k++; 
     j++; 
    } 
    else 
    { 
     i++; 
     k=i; 
     j=0; 
    } 
} 
if (j == patternLength) 
    return i; 
else 
    return -1; 
} 

私は、任意のヘルプは感謝される、私は間違った場所にcomparisons_tmp変数をインクリメントしていますかどうかわかりませんよ。 Test0には1999年のAファイルのパターンファイルが含まれていて、その後にBファイルが続き、199999Aのテキストファイルに続いてBが続きます。

Answer 1

comparisons_tmpはwhile -loopの外側で増分する必要があります。最初の比較が欠落しています。たとえば、最初の文字のパターンと一致しない場合は、比較は何も増加しません。

しかし、OpenMPはではなく、はループが実行される順序を保証するため、並列位置のアルゴリズムを固定することで、より多くの比較が可能になります。つまり、最終的な値がfoundより大きいiを持つスレッドがあります。