openMP を使用して、 Longest Common Subsequenceアルゴリズムの並列バージョンを作成しています。
順次バージョンは次のとおりです (正しく動作します)。
// 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]);
}
}
}
重要な部分はスコア マトリックスを埋めることであり、これは私が主に並列化しようとしている部分です。
それを行う 1 つの方法 (私が選んだ方法) は、逆対角線で行列を埋めて、左、上、左上の依存関係が常に満たされるようにすることです。簡単に言うと、対角線 (3 番目のループ、以下の変数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--;
}
}
}
}
最初の 2 つのループ (最初の行と列) は正しく機能し、スレッドはバランスの取れた方法でセルを埋めます。
マトリックスを（斜めに）埋めようとすると、何もうまくいきません。デバッグしてみたのですが、どうやらスレッドが勝手に動いて書き込んでいるようです。
最初の 2 つのループではまったく問題がなかったので、何が問題なのかわかりません。
何か案が？
PSマトリックスに斜めにアクセスすることは非常にキャッシュにやさしくなく、スレッドのバランスが崩れる可能性があることは知っていますが、今ではそれが機能するだけで済みます。
PS #2 役に立つかどうかはわかりませんが、私の CPU には最大 8 つのスレッドがあります。