3

Fork/Join Tutorialを見た後、大きな階乗を計算するためのクラスを作成しました。

public class ForkFactorial extends RecursiveTask<BigInteger> {

    final int end;
    final int start;
    private static final int THRESHOLD = 10;

    public ForkFactorial(int n) {
        this(1, n + 1);
    }

    private ForkFactorial(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    protected BigInteger compute() {
        if (end - start < THRESHOLD) {
            return computeDirectly();
        } else {
            int mid = (start + end) / 2;
            ForkFactorial lower = new ForkFactorial(start, mid);
            lower.fork();
            ForkFactorial upper = new ForkFactorial(mid, end);
            BigInteger upperVal = upper.compute();
            return lower.join().multiply(upperVal);
        }
    }

    private BigInteger computeDirectly() {
        BigInteger val = BigInteger.ONE;
        BigInteger mult = BigInteger.valueOf(start);
        for (int iter = start; iter < end; iter++, mult = mult.add(BigInteger.ONE)) {
            val = val.multiply(mult);
        }
        return val;
    }
}

私が持っている質問は、タスクを細分化するしきい値をどのように決定するかです。フォーク/ジョインの並列処理に関するページを見つけました。

fork/join 並列処理を使用するアルゴリズムを実装する際に考慮すべき主な事項の 1 つは、並列サブタスクを fork するのではなく、タスクが順次計算を実行するかどうかを決定するしきい値を選択することです。

しきい値が大きすぎると、プログラムは使用可能なプロセッサ/コアを十分に活用するのに十分なタスクを作成しない可能性があります。

しきい値が小さすぎると、タスクの作成と管理のオーバーヘッドが大きくなる可能性があります。

一般に、適切なしきい値を見つけるには、いくつかの実験が必要です。

では、しきい値を決定するには、どのような実験を行う必要があるでしょうか?

4

4 に答える 4

4

PigeonHole 推定: 任意のしきい値を設定し、計算時間を計算します。それに基づいて、しきい値を増減して、しきい値を下げても改善が見られなくなるまで、計算時間が改善されるかどうかを確認します。

于 2013-11-24T17:19:20.117 に答える
4

しきい値の選択は、多くの要因によって異なります。

実際の計算にはかなりの時間がかかります。配列を合計していて、配列が小さい場合は、おそらく順次実行する方がよいでしょう。配列の長さが 16M の場合は、配列を小さな断片に分割して並列処理する価値があります。試してみてください。

プロセッサの数は十分である必要があります。Doug Lea はかつて、価値のあるものにするために、16 個以上のプロセッサを使用してフレームワークを文書化しました。配列を半分に分割して 2 つのスレッドで実行しても、スループットが約 1.3% 向上します。ここで、分割/結合のオーバーヘッドを考慮する必要があります。多くの構成で実行してみて、何が得られるかを確認してください。

同時リクエストの数は少なくする必要があります。N 個のプロセッサと 8(N) 個の同時リクエストがある場合、多くの場合、リクエストごとに 1 つのスレッドを使用すると、スループットがより効率的になります。ここでのロジックは単純です。N 個のプロセッサが利用可能で、それに応じて作業を分割しても、他に何百ものタスクが待ち受けているとしたら、分割する意味は何でしょう?

これが実験の意味です。

残念ながら、このフレームワークには説明責任の手段がありません。各スレッドの負荷を確認する方法はありません。deques の最高水準点。処理されたリクエストの合計。発生したエラーなど

幸運を。

于 2013-11-24T18:54:34.850 に答える
2

演算は BigInteger では一定時間ではなく、入力の長さに比例することに注意してください。各操作の実際の複雑さはすぐにはわかりませんが、その Q/A セクションで参照されているfutureboyの実装は、さまざまな状況で達成する (期待される) ことを文書化しています。

問題をより小さなチャンクに分割する方法を決定する場合と、特定のチャンクを再度分割する価値があるかどうかを決定する場合の両方で、作業推定関数を正しく取得することが重要です。

実験を使用してしきい値を決定する場合、問題領域の 1 つのコーナーだけをベンチマークしないように注意する必要があります。

于 2013-11-24T17:52:29.127 に答える
1

私が理解しているように、この実験は最適化であるため、必要がある場合にのみ適用する必要があります。

さまざまな分割戦略を試すことができます。つまり、2 つの等しい部分で分割したり、整数の 10 進数の長さに依存する推定乗算コストで分割したりできます。

各戦略について、戦略の全体像を把握するために、できるだけ多くのしきい値をテストできます。CPU リソースが限られている場合は、5 番目または 10 番目ごとにテストできます。したがって、私の経験から、ここで最初に重要なことは、アルゴリズムがどのように機能するかの全体像を把握することです。

于 2013-11-24T17:51:47.203 に答える