我在尝试并行化算法时遇到了一些问题。目的是对 100x100 矩阵进行一些修改。当我在没有 openMP 的情况下运行算法时,一切都在大约 34-35 秒内顺利运行,当我在 2 个线程上并行化时(我只需要它只有 2 个线程),它会下降到 22 秒,但输出是错误的,我认为这是一个我无法解决的同步问题。
这是代码:
for (p = 0; p < sapt; p++){
memset(count,0,Nc*sizeof(int));
for (i = 0; i < N; i ++){
for (j = 0; j < N; j++){
for( m = 0; m < Nc; m++)
dist[m] = N+1;
omp_set_num_threads(2);
#pragma omp parallel for shared(configurationMatrix, dist) private(k,m) schedule(static,chunk)
for (k = 0; k < N; k++){
for (m = 0; m < N; m++){
if (i == k && j == m)
continue;
if (MAX(abs(i-k),abs(j-m)) < dist[configurationMatrix[k][m]])
dist[configurationMatrix[k][m]] = MAX(abs(i-k),abs(j-m));
}
}
int max = -1;
for(m = 0; m < Nc; m++){
if (dist[m] == N+1)
continue;
if (dist[m] > max){
max = dist[m];
configurationMatrix2[i][j] = m;
}
}
}
}
memcpy(configurationMatrix, configurationMatrix2, N*N*sizeof(int));
#pragma omp parallel for shared(count, configurationMatrix) private(i,j)
for (i = 0; i < N; i ++)
for (j = 0; j < N; j++)
count[configurationMatrix[i][j]] ++;
for (i = 0; i < Nc; i ++)
fprintf(out,"%i ", count[i]);
fprintf(out, "n");
}
其中:sapt = 100;count ->它是一个向量,它保存了我在每一步中矩阵的每个元素的数量;
(例如:count[1] = 60
-->我的矩阵中有元素"1"60 次,依此类推)
dist --> vector
,这使我从元素 i,j 的最大距离,假设值 K 到元素 k,m 具有相同值 K。
(例如:dist[1] = 10
-->从值 1 的元素到值 1 的最远元素的距离)
然后我把东西写在输出文件中,但同样,错误的输出。
正确理解你的代码,这一行
count[configurationMatrix[i][j]] ++;
在索引为 configurationMatrix[i][j]
的元素处count
递增。 我没有看到您的代码采取任何步骤来确保线程不会同时尝试增加相同的count
元素。 configurationMatrix
的两个不同元素在count
中提供相同的索引,并且这两个元素由不同的线程处理是完全可行的。 由于++
不是原子操作,因此您的代码具有数据竞赛;多个线程可以争用对同一变量的更新访问权限,并且您将失去对结果的正确性或确定性的任何保证。
我认为您可能在代码的其他部分中也有相同问题的其他示例。 与串行程序的结果相比,您对并行程序结果中观察到的错误保持沉默,但这些错误在诊断问题时通常非常有用。 例如,如果每次运行并行程序时的结果都不相同,则非常暗示代码中某处存在数据竞赛。
如何解决这个问题? 由于您只有 2 个线程,最简单的解决方法是不并行化程序的这一部分。 您可以将数据竞争包装在 OpenMP critical
部分中,但这实际上只是序列化代码的另一种方式。 最后,您可以修改算法和数据结构以完全避免此问题。