我正在使用 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--;
}
}
}
}
前两个循环（第一行和第一列）正常工作，线程以平衡的方式填充单元格。
当谈到填充矩阵（对角线）时，没有什么效果很好。我试图调试它，但似乎线程随机地行动和写东西。
我不知道出了什么问题，因为在前两个循环中根本没有问题。
任何想法？
PS我知道以对角线方式访问矩阵对缓存非常不友好，线程可能不平衡，但我现在只需要它工作。
PS #2 我不知道它是否有用，但我的 CPU 最多有 8 个线程。