java - ExecutorService没有性能增益递归行列式Java

Question

我读过类似的问题，其中问题是同步方法的使用(如 Math.random() )或工作量太少，无法证明开销的合理性，但我不认为这里是这种情况。

我的处理器有 4 个物理核心/8 个逻辑核心。一次热身后，我在 11x11 矩阵上使用 n=1;2;3;4;8 测试以下代码；

ExecutorService pool = Executors.newFixedThreadPool(n);
long startTime = System.currentTimeMillis();
double result = pool.submit(new Solver(pool, matrix)).get();
System.out.println(result);
long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.println(elapsedTime);

执行分别需要:

1 ~ 15500 2～13500～14000 3～14300～15500 4 ~ 14500 - 19000 8 ~ 19000 - 23000

所以我得到了 2 的提升很小， 3 几乎没有提升， 有时几乎没有提升，但有时会极度减速 4 8 时完全减速；

这是代码:

import java.util.ArrayList;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Future;
import java.util.concurrent.ThreadPoolExecutor;

public class Solver implements Callable<Double> {

    private ExecutorService pool;
    private double[][] matrix;


    public Solver(ExecutorService pool, double[][] matrix){
        this.pool = pool;
        this.matrix = matrix;
    }

    public double determinant(double[][] matrix) {
        if (matrix.length == 1)
            return (matrix[0][0]);

        double coefficient;
        double sum = 0;
        int threadsCount = ((ThreadPoolExecutor) pool).getMaximumPoolSize();
        ArrayList<Double> coefficients = new ArrayList<Double>();
        ArrayList<Future<Double>> delayedDeterminants = new ArrayList<Future<Double>>();

        for (int k = 0; k < matrix.length; k++) {
            double[][] smaller = new double[matrix.length - 1][matrix.length - 1];
            for (int i = 1; i < matrix.length; i++) {
                for (int j = 0; j < matrix.length; j++) {
                    if (j < k)
                        smaller[i - 1][j] = matrix[i][j];
                    else if (j > k)
                        smaller[i - 1][j - 1] = matrix[i][j];
                }
            }
            coefficient = ((k % 2 == 0) ? 1 : -1) * matrix[0][k];
            if (((ThreadPoolExecutor) pool).getActiveCount() < threadsCount
                    && matrix.length > 5) {
                coefficients.add(coefficient);
                delayedDeterminants.add(pool.submit(new Solver(pool, smaller)));
            } else
                sum += coefficient * (determinant(smaller));
        }

        try {
            for (int i = 0; i < coefficients.size(); i++)
                sum += coefficients.get(i) * delayedDeterminants.get(i).get();
        } catch (InterruptedException | ExecutionException e) {
            e.printStackTrace();
        }

        return (sum);
    }

    @Override
    public Double call() throws Exception {
        return determinant(matrix);
    }

}

Answer 1

处理这种分治算法的一般方法是在单个线程中下降到某个级别，直到有足够的独立任务，然后将所有这些任务调度到 ExecutorService 上，让更多级别的递归在其中执行同一个任务。例如，往下一层有 121 个子矩阵来计算行列式，因此向 ExecutorService 提交 121 个任务。或者再升一级以获取 12,100 个子问题并提交所有这些问题。

轮询 ExecutorService 来获取 Activity 任务计数可能不是最好的主意。创建一个 newFixedThreadPool(4) 或您想要测试的任意数量的线程，并让 ExecutorService 管理任务执行。如果您想要完成的是工作窃取，那么我强烈建议您花一些时间熟悉 Fork/Join 框架，该框架可以自动管理工作窃取。它旨在完全处理您的任务类型。

另一件事，与问题没有直接关系:您绝对应该重新设计代码，以便只有一个二维数组用于所有计算。一维数组会更好。