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 parallelism 的页面，其中指出：

使用 fork/join 并行实现算法时要考虑的主要事项之一是选择阈值，该阈值确定任务是否将执行顺序计算而不是分叉并行子任务。

如果阈值太大，则程序可能无法创建足够的任务来充分利用可用的处理器/内核。

如果阈值太小，则任务创建和管理的开销可能会变得很大。

通常，需要进行一些实验来找到合适的阈值。

那么我需要做哪些实验来确定阈值呢？

4

4 回答 4

4

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

实际计算应该花费合理的时间。如果您要对数组求和并且数组很小，那么按顺序进行可能会更好。如果数组长度为 16M，那么将其拆分为更小的部分并进行并行处理应该是值得的。试试看。

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

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

这就是实验的意思。

不幸的是，这个框架没有提供问责手段。无法查看每个线程上的负载。双端队列中的高水位线。处理的请求总数。遇到的错误等等。

祝你好运。

于 2013-11-24T18:54:34.850 回答
4

PigeonHole 估计：设置任意阈值，计算计算时间。并在此基础上增加和减少阈值以查看您的计算时间是否有所改善，直到您通过降低阈值看不到任何改善为止。

于 2013-11-24T17:19:20.117 回答
2

请注意，BigInteger 的算术不是恒定时间，它与输入的长度成正比。每个操作的实际复杂性并不容易掌握，尽管 Q/A 部分中引用的 futureboy 实现确实记录了它（期望）在不同情况下实现的目标。

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

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

于 2013-11-24T17:52:29.127 回答
1

据我了解，这个实验是一个优化，所以它应该只在需要时应用。

您可以尝试不同的拆分策略 - 即一个可以拆分为两个相等的部分或通过估计的乘法成本，这取决于整数十进制长度。

对于每个策略，您可以测试尽可能多的阈值，以全面了解您的策略。如果您的 CPU 资源有限，则可以每 5 次或 10 次测试一次。因此，根据我的经验，这里的第一件事是全面了解您的算法的执行情况。

于 2013-11-24T17:51:47.203 回答