有没有办法并行化下三角矩阵求解器?
Is there a way to parallelize a lower triangle matrix solver?
目标是将 OpenMP 并行化添加到 for (i = 0; i < n; i++)
以用于形式 Ax=b
的下三角求解器。预期结果与没有向 for (i = 0; i < n; i++)
添加并行化时的结果完全相同。
vector<vector<double>>
表示二维矩阵。 makeMatrix(int m, int n)
初始化大小为 mxn
.
的所有零的 vector<vector<double>>
评论中留下了两个最突出的尝试。
vector<vector<double>> lowerTriangleSolver(vector<vector<double>> A, vector<vector<double>> b)
{
vector<vector<double>> x = makeMatrix(A.size(), 1);
int i, j;
int n = A.size();
double s;
//#pragma omp parallel for reduction(+: s)
//#pragma omp parallel for shared(s)
for (i = 0; i < n; i++)
{
s = 0.0;
#pragma omp parallel for
for (j = 0; j < i; j++)
{
s = s + A[i][j] * x[j][0];
}
x[i][0] = (b[i][0] - s) / A[i][i];
}
return x;
}
您可以尝试在线程之间分配外循环迭代,而不是内循环。通过这种方式,您可以增加并行任务的粒度并避免减少 's' 变量。
#pragma omp parallel for
for (int i = 0; i < n; i++){
double s = 0.0;
for (int j = 0; j < i; j++){
s = s + A[i][j] * x[j][0];
}
x[i][0] = (b[i][0] - s) / A[i][i];
}
不幸的是,这是不可能的,因为 s = s + A[i][j] * x[j][0];
和 x[i][0] = (b[i][0] - s) / A[i][i];
之间存在依赖关系,更准确地说,x[j][0]
取决于 x[i][0]
。
所以你可以尝试两种方法:
for (int i = 0; i < n; i++){
double s = 0.0;
#pragma omp parallel for reduction(+:s)
for (int j = 0; j < i; j++){
s = s + A[i][j] * x[j][0];
}
x[i][0] = (b[i][0] - s) / A[i][i];
}
或使用 SIMD :
for (int i = 0; i < n; i++){
double s = 0.0;
#pragma omp simd reduction(+:s)
for (int j = 0; j < i; j++){
s = s + A[i][j] * x[j][0];
}
x[i][0] = (b[i][0] - s) / A[i][i];
}
目标是将 OpenMP 并行化添加到 for (i = 0; i < n; i++)
以用于形式 Ax=b
的下三角求解器。预期结果与没有向 for (i = 0; i < n; i++)
添加并行化时的结果完全相同。
vector<vector<double>>
表示二维矩阵。 makeMatrix(int m, int n)
初始化大小为 mxn
.
vector<vector<double>>
评论中留下了两个最突出的尝试。
vector<vector<double>> lowerTriangleSolver(vector<vector<double>> A, vector<vector<double>> b)
{
vector<vector<double>> x = makeMatrix(A.size(), 1);
int i, j;
int n = A.size();
double s;
//#pragma omp parallel for reduction(+: s)
//#pragma omp parallel for shared(s)
for (i = 0; i < n; i++)
{
s = 0.0;
#pragma omp parallel for
for (j = 0; j < i; j++)
{
s = s + A[i][j] * x[j][0];
}
x[i][0] = (b[i][0] - s) / A[i][i];
}
return x;
}
您可以尝试在线程之间分配外循环迭代,而不是内循环。通过这种方式,您可以增加并行任务的粒度并避免减少 's' 变量。
#pragma omp parallel for
for (int i = 0; i < n; i++){
double s = 0.0;
for (int j = 0; j < i; j++){
s = s + A[i][j] * x[j][0];
}
x[i][0] = (b[i][0] - s) / A[i][i];
}
不幸的是,这是不可能的,因为 s = s + A[i][j] * x[j][0];
和 x[i][0] = (b[i][0] - s) / A[i][i];
之间存在依赖关系,更准确地说,x[j][0]
取决于 x[i][0]
。
所以你可以尝试两种方法:
for (int i = 0; i < n; i++){
double s = 0.0;
#pragma omp parallel for reduction(+:s)
for (int j = 0; j < i; j++){
s = s + A[i][j] * x[j][0];
}
x[i][0] = (b[i][0] - s) / A[i][i];
}
或使用 SIMD :
for (int i = 0; i < n; i++){
double s = 0.0;
#pragma omp simd reduction(+:s)
for (int j = 0; j < i; j++){
s = s + A[i][j] * x[j][0];
}
x[i][0] = (b[i][0] - s) / A[i][i];
}