我坚持并行化以下代码:
double[][] a, b, c;
double d;
double[] e;
for (int i = 1; i < x; i++) {
double f = 0.0;
for (int j = 0; j < y; j++) {
double a1 = a[i-1][j];
double a2 = a[i][j];
double a3 = a1 * a2;
d -= a3;
c[i][j] = c[i - 1][j] + a3;
f += c[i][j] * a3;
}
e[i] = d + f;
for (int j = 0; j < y; j++) {
a[i][j] = e[i] * b[i][j]
}
}
第二个内部循环依赖于第一个(因为e[i]
(,所以它们必须按顺序执行,但是在每个内部,计算可以在y
上并行化。
问题是它们都在外部变量上读取和写入。写入可以并行化(概念上(,因为每个内部循环将其部分结果聚合到全局变量。
x
在 10000 和 250y
量级。在此示例中,内部循环处理得到了简化,但实际上计算强度更高。
这里的问题是如何并行化读取和写入外部变量的循环?
由于d
和f
,以下尝试无法编译:
double[][] a, b, c;
double d;
double[] e;
for (int i = 1; i < x; i++) {
double f = 0.0;
IntStream.range(0, y).parallel().forEach(j -> {
double a1 = a[i-1][j];
double a2 = a[i][j];
double a3 = a1 * a2;
d -= a3;
c[i][j] = c[i - 1][j] + a3;
f += c[i][j] * a3;
});
e[i] = d + f;
IntStream.range(0, y).parallel().forEach(j -> {
a[i][j] = e[i] * b[i][j];
});
}
要并行化子循环,您必须首先了解每个子循环的结果。
第一个循环的结果是:
- 递增到可变
d
f
的价值- 新的
c[i]
子阵列
若要计算它们,可以创建自定义类型来保存 3 个值,然后执行可变缩减以计算所有 3 个值。由于没有更好的名称,我将自定义类型称为ResultContainer
。
同样,第二个循环的结果是数组a[i]
。这更简单,因为很容易从Stream
构建数组。
因此,这将提供:
for (int i0 = 1; i0 < x; i0++) {
final int i = i0; // tmp store as final for use in lambda
ResultContainer result = IntStream.range(0, y).parallel()
.collect(() -> new ResultContainer(y), (resultContainer, j) -> {
double a1 = a[i - 1][j];
double a2 = a[i][j];
double a3 = a1 * a2;
double cij = c[i - 1][j] + a3;
resultContainer.add(-a3, cij * a3, j, cij);
}, ResultContainer::add);
d += result.d;
e[i] = d + result.f;
c[i] = result.ci;
a[i] = IntStream.range(0, y).parallel().mapToDouble(j -> e[i] * b[i][j]).toArray();
}
使用我们的自定义类型:
class ResultContainer {
double d;
double f;
double[] ci;
public ResultContainer(int y) {
this.d = 0;
this.f = 0;
ci = new double[y];
}
public void add(double d, double f, int j, double cij) {
this.d += d;
this.f += f;
ci[j] = cij;
}
public void add(ResultContainer resultContainer2) {
d += resultContainer2.d;
f += resultContainer2.f;
for (int j = 0; j < ci.length; j++) {
// note that one of the two is always 0 here
ci[j] += resultContainer2.ci[j];
}
}
}