0

問題が同期メソッド（ Math.random() など）の使用である、またはオーバーヘッドを正当化するには作業が少なすぎるという同様の質問を読みましたが、ここではそうではないと思います。

私のプロセッサには 4 つの物理コアと 8 つの論理コアがあります。1 回のウォームアップの後、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);
    }

}
4

1 に答える 1

4

このような分割統治アルゴリズムを処理する一般的な方法は、十分な数の独立したタスクが存在するまで単一のスレッドで特定のレベルまで下降し、それらのすべてのタスクを ExecutorService でスケジュールして、再帰のさらなるレベルを同じタスク内で実行できるようにすることです。 . たとえば、1 つ下のレベルでは、行列式を計算する 121 のサブマトリックスがあるため、121 のタスクを ExecutorService に送信します。または、もう 1 レベル進んで 12,100 のサブ問題を取得し、それらすべてを提出します。

アクティブなタスク数についてExecutorServiceをポーリングすることは、おそらく最善の方法ではありません。newFixedThreadPool(4)テストするスレッドを 1 つまたは任意の数作成し、 ExecutorServiceにタスクの実行を管理させます。達成しようとしているのがワーク スティーリングである場合は、ワーク スティーリングを自動的に管理する Fork/Join フレームワークに慣れるために時間を費やすことを強くお勧めします。まさにあなたの種類のタスクを処理するように設計されています。

質問に直接関係しないもう1つのこと：すべての計算に使用される2D配列が1つだけになるように、コードを確実に再設計する必要があります。1D 配列はさらに優れています。

于 2013-05-27T14:16:16.650 に答える