下面显示的代码用于通过Gauss Jordan方法计算矩阵的逆矩阵，将内存访问减半。这缩短了单线程执行时间。我遇到的问题是创建了新的数据依赖关系，使我无法并行化。例如，对于循环K或循环i（具有条件if i！=k....的循环）。
for (k = 0; k < size; k += 2)
{
pivot = original[k][k];
for (j = 0; j < size; j++)
{
original[k][j] /= pivot;
inverse[k][j] /= pivot;
}
pivot = original[k + 1][k];
for (i = 0; i < size; i++)
{
original[k + 1][i] -= original[k][i] * pivot;
inverse[k + 1][i] -= inverse[k][i] * pivot;
}
pivot = original[k+1][k+1];
for (j = 0; j < size; j++)
{
original[k+1][j] /= pivot;
inverse[k+1][j] /= pivot;
}
for (i = 0; i < size; i++)
{
if (i != k && i != k + 1)
{
pivot = original[i][k];
for (j = 0; j < size; j++)
{
original[i][j] -= original[k][j] * pivot;
inverse[i][j] -= inverse[k][j] * pivot;
}
}
if (i != k + 1)
{
pivot = original[i][k+1];
for (j = 0; j < size; j++)
{
original[i][j] -= original[k + 1][j] * pivot;
inverse[i][j] -= inverse[k + 1][j] * pivot;
}
}
}
}我想我们必须对代码进行转换以消除数据依赖性，并且代码肯定是可并行的
1条答案
按热度按时间gc0ot86w1#
你需要分析什么是基本依赖，什么是并行的。和所有线性代数因式分解算法一样，有一个顺序循环来计算主元。这就是你的
k循环，它不能被并行化。（也许需要一些特殊的聪明才智，但这可能需要大量的重写。）接下来是双
i,j循环，每次写访问都到[i][j]位置，这意味着它是完全并行的，而且这个循环也比之前的单循环大得多，这取决于它们！因此，从并行化双
i,j循环开始，看看你得到了什么样的加速，然后你可以尝试并行化单循环，或者让它们保持单线程，它们可能太小，不能给你带来任何好处。但不需要转换代码：在双循环上插入一个
omp parallel for collapse(2)，您可能已经完成了任务。