java - 如何确定fork-join任务的合适分工阈值

Question

看了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;
    }
}

我的问题是如何确定我分割任务的阈值？我找到了一个 page on fork/join parallelism其中指出:

One of the main things to consider when implementing an algorithm using fork/join parallelism is chosing the threshold which determines whether a task will execute a sequential computation rather than forking parallel sub-tasks.

If the threshold is too large, then the program might not create enough tasks to fully take advantage of the available processors/cores.

If the threshold is too small, then the overhead of task creation and management could become significant.

In general, some experimentation will be necessary to find an appropriate threshold value.

那么我需要做哪些实验才能确定阈值？

Answer 1

PigeonHole估计:设置一个任意的Threshold，计算计算时间。并根据它增加和减少阈值以查看您的计算时间是否有所改善，直到您通过降低阈值看不到任何改善。