如何确定分叉连接任务的正确分工阈值

Question

在查看了叉子/联接教程之后，我创建了一个用于计算大型阶乘的类：

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

我的问题是如何确定细分任务的阈值？我找到了一个页面上的叉/连接并行性，上面写着：

使用叉/连接并行实现算法时要考虑的主要问题之一是选择阈值，该阈值决定任务是否将执行顺序计算，而不是分叉并行子任务。 如果阈值太大，那么程序可能无法创建足够的任务来充分利用可用的处理器/核心。 如果阈值太小，那么任务创建和管理的开销就会变得很大。 一般来说，需要进行一些实验才能找到合适的阈值。

那么，我需要做什么实验才能确定阈值呢？

Answer 1

PigeonHole估计:设置任意阈值，计算计算时间。在此基础上，增加和降低阈值，看看你的计算时间是否有所改善，直到你看到没有通过降低阈值而有所改善的时间。

Answer 2

选择阈值取决于许多因素：

实际计算应花费合理的时间。如果您正在对一个数组进行求和，并且数组很小，那么按顺序执行可能更好。如果数组长度为16M，则将其分割成较小的块并进行并行处理是值得的。试试看。

处理器的数量应该足够了。Doug曾经用数字16+处理器记录了他的框架，以使其有价值。即使将数组分割成两半并在两个线程上运行，吞吐量也将提高约1.3%。现在，您必须考虑拆分/连接开销。尝试在许多配置上运行，看看您得到了什么。

并发请求的数量应该很小。如果您有N个处理器和8(N)个并发请求，那么在吞吐量方面，每个请求使用一个线程通常更有效。这里的逻辑很简单。如果您有N个可用的处理器，并且相应地将您的工作分开，但是前面还有数百个其他任务，那么分裂又有什么意义呢？

这就是实验的意义。

不幸的是，这个框架没有提供问责的手段。无法查看每个线程上的负载。德克的高水位标志。处理的请求共计。遇到的错误等

祝好运。

Answer 3

注意，对于BigInteger，算术不是常数时间，它与输入的长度成正比。在手中，每个操作的实际复杂性并不容易，尽管Q/A部分中引用的futureboy实现会记录它(期望)在不同情况下实现什么。

在决定如何将问题划分为较小的块时，以及在确定某个特定块是否值得再次分割时，使工作估计函数正确是很重要的。

在使用实验确定阈值时，您需要注意的是，不要仅仅对问题空间的一个角落进行基准测试。