gpt4 book ai didi

java - 为什么这种并行矩阵加法效率如此低下?

转载 作者:行者123 更新时间:2023-11-30 07:44:59 27 4
gpt4 key购买 nike

我对多线程非常陌生,并且没有太多使用内部类的经验。

任务是以并行方式添加两个包含 double 值的矩阵。

我的想法是递归地执行此操作,将大矩阵拆分为较小的矩阵,并在矩阵达到一定大小限制时执行加法,然后融合它们。

并行化代码的运行速度比序列化代码慢 40-80 倍。

我怀疑我在这里做错了什么。也许是因为我创建了很多新矩阵,或者因为我遍历了它们很多次。

这是代码:

package concurrency;

import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

public class ParallelMatrixAddition {
public static void main(String[] args) {

Random rand = new Random();

final int SIZE = 1000;
double[][] one = new double[SIZE][SIZE];
double[][] two = new double[SIZE][SIZE];
double[][] serialSums = new double[SIZE][SIZE];
double[][] parallelSums = new double[SIZE][SIZE];

for (int i = 0; i < one.length; i++) {
for (int j = 0; j < one.length; j++) {
one[i][j] = rand.nextDouble();
two[i][j] = rand.nextDouble();
}
}

long serialStartTime = System.currentTimeMillis();

for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
serialSums[i][j] = one[i][j] + two[i][j];
}
}

long serialEndTime = System.currentTimeMillis();

System.out.println("Serial runtime is: " + (serialEndTime - serialStartTime) + " milliseconds");

long startTime = System.currentTimeMillis();

parallelSums = parallelAddMatrix(one, two);

long endTime = System.currentTimeMillis();

System.out.println("Parallel execution took " + (endTime - startTime) + " milliseconds.");

}

public static double[][] parallelAddMatrix(double[][] a, double[][] b) {
RecursiveTask<double[][]> task = new SumMatricesTask(a, b);
ForkJoinPool pool = new ForkJoinPool();
double[][] result = new double[a.length][a.length];
result = pool.invoke(task);
return result;
}

@SuppressWarnings("serial")
private static class SumMatricesTask extends RecursiveTask<double[][]> {
private final static int THRESHOLD = 200;

private double[][] sumz;
private double[][] one;
private double[][] two;

public SumMatricesTask(double[][] one, double[][] two) {
this.one = one;
this.two = two;
this.sumz = new double[one.length][one.length];
}

@Override
public double[][] compute() {
if (this.one.length < THRESHOLD) {
// Compute a sum here.
// Add the sums of the matrices and store the result in the
// matrix we will return later.

double[][] aStuff = new double[this.one.length][this.one.length];

for (int i = 0; i < one.length; i++) {
for (int j = 0; j < one.length; j++) {
aStuff[i][j] = this.one[i][j] + this.two[i][j];
}
}

return aStuff;

} else {

// Split a matrix into four smaller submatrices.
// Create four forks, then four joins.

int currentSize = this.one.length;

int newSize = currentSize / 2;

double[][] topLeftA = new double[newSize][newSize];
double[][] topLeftB = new double[newSize][newSize];
double[][] topLeftSums = new double[newSize][newSize];

double[][] topRightA = new double[newSize][newSize];
double[][] topRightB = new double[newSize][newSize];
double[][] topRightSums = new double[newSize][newSize];

double[][] bottomLeftA = new double[newSize][newSize];
double[][] bottomLeftB = new double[newSize][newSize];
double[][] bottomLeftSums = new double[newSize][newSize];

double[][] bottomRightA = new double[newSize][newSize];
double[][] bottomRightB = new double[newSize][newSize];
double[][] bottomRightSums = new double[newSize][newSize];

// Populate topLeftA and topLeftB
for (int i = 0; i < newSize; i++) {
for (int j = 0; j < newSize; j++) {
topLeftA[i][j] = this.one[i][j];
topLeftB[i][j] = this.two[i][j];
}
}

// Populate bottomLeftA and bottomLeftB

for (int i = 0; i < newSize; i++) {
for (int j = 0; j < newSize; j++) {
bottomLeftA[i][j] = this.one[i + newSize][j];
bottomLeftB[i][j] = this.two[i + newSize][j];
}
}

// Populate topRightA and topRightB

for (int i = 0; i < newSize; i++) {
for (int j = 0; j < newSize; j++) {
topRightA[i][j] = this.one[i][j + newSize];
topRightB[i][j] = this.two[i][j + newSize];
}
}

// Populate bottomRightA and bottomRightB

for (int i = 0; i < newSize; i++) {
for (int j = 0; j < newSize; j++) {
bottomRightA[i][j] = this.one[i + newSize][j + newSize];
bottomRightB[i][j] = this.two[i + newSize][j + newSize];
}
}

SumMatricesTask topLeft = new SumMatricesTask(topLeftA, topLeftB);
SumMatricesTask topRight = new SumMatricesTask(topRightA, topRightB);
SumMatricesTask bottomLeft = new SumMatricesTask(bottomLeftA, bottomLeftB);
SumMatricesTask bottomRight = new SumMatricesTask(bottomRightA, bottomRightB);

topLeft.fork();
topRight.fork();
bottomLeft.fork();
bottomRight.fork();

topLeftSums = topLeft.join();
topRightSums = topRight.join();
bottomLeftSums = bottomLeft.join();
bottomRightSums = bottomRight.join();

// Fuse the four matrices into one and return it.

for (int i = 0; i < newSize; i++) {
for (int j = 0; j < newSize; j++) {
this.sumz[i][j] = topLeftSums[i][j];
}
}

for (int i = newSize; i < newSize * 2; i++) {
for (int j = 0; j < newSize; j++) {
this.sumz[i][j] = bottomLeftSums[i - newSize][j];
}
}

for (int i = 0; i < newSize; i++) {
for (int j = newSize; j < newSize * 2; j++) {
this.sumz[i][j] = topRightSums[i][j - newSize];
}
}

for (int i = newSize; i < newSize * 2; i++) {
for (int j = newSize; j < newSize * 2; j++) {
this.sumz[i][j] = bottomRightSums[i - newSize][j - newSize];
}
}

return this.sumz;
}
}
}

}

感谢您的帮助。

最佳答案

即使对于 double,创建对象也比执行 + 慢很多倍。

这意味着创建一个对象对于添加来说并不是一个好的权衡。更糟糕的是,使用更多内存意味着您的 CPU 缓存无法高效工作,在最坏的情况下,在 L1/L2 cpu 缓存中工作的内容现在位于 L3 缓存中,该缓存是共享的且不可扩展,甚至更糟您最终会使用主内存。

我建议你重写这个,以便

  • 您没有创建任何对象。
  • 您认为跨缓存行工作比分解它更有效。即按行而不是按列分解工作。
  • 在 Java 中处理一维数组可能会更高效,因此请考虑如何使用仅显示为 2D martix 的一维数组来实现此目的。

关于java - 为什么这种并行矩阵加法效率如此低下?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34066423/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com