提高并行计算欧拉数的性能

Question

我正在尝试计算 e=∑(3−4k^2/(2k+1)!); k=0..10000 但是我卡住了，无法使用多线程获得所需的性能提升。

给定线程数，我尝试将总和分成 k / numberOfThreads 块，并为每个部分总和提交期货。我认为不好的部分可能是阶乘计算或粒度。我尝试了一个较小的步骤，但没有得到很大的改进。也许需要一种不同的方法。

ExecutorService executor = Executors.newFixedThreadPool(numberOfThreads);
List<Future<BigDecimal>> futures = new ArrayList<>(numberOfThreads);
int step = k / numberOfThreads ;
BigDecimal result = BigDecimal.ZERO;
for (int j = 0; j <= k; j += step) {
    Future<BigDecimal> future = executor.submit(new EulerCalculator(j, j + step));
    futures.add(future);
}
for (Future<BigDecimal> future : futures) {
    result = result.add(future.get());
}

public class EulerCalculator implements Callable<BigDecimal> {
    private int start;
    private int end;

    public BigDecimal call() {
        long numerator = 3 - 4 * start * start;
        BigDecimal denominator = factorial(2 * start + 1);
        BigDecimal partialSum = BigDecimal.valueOf(numerator)
                                .divide(denominator, 1000, RoundingMode.HALF_EVEN);
        for (int i = start + 1 ; i < end; i++) {
            numerator = 3 - 4 * i * i;
            denominator = denominator.multiply(BigDecimal.valueOf(2 * i * (2*i + 1)));
            partialSum = partialSum.add(BigDecimal.valueOf(numerator)
                                        .divide(fact, 1000, RoundingMode.HALF_EVEN));
        }

        return partialSum;
    }

    private BigDecimal factorial(int cur) {
        BigDecimal fact = BigDecimal.ONE;
        for (int i = 2; i <= cur; i++) {
            fact = fact.multiply(BigDecimal.valueOf(i));
        }

        return fact;
    }
}

在四核上运行几次的最佳结果：

k = 10000

线程数 = 1：345 毫秒

线程数 = 2：216 毫秒

线程数 = 4：184 毫秒

线程数 = 8：225 毫秒

Answer 1

你的阶乘部分不是常数时间运算，而是 O(n)。这意味着您的第一个线程比最后一个线程的工作要少得多。因此你没有平均分配工作。

通常有三种方法可以解决这个问题。

你可以做不均匀的步长，即k越小步长越大。但是，这是非常低效的，因为您要进行数千次相同的乘法运算。

您可以尝试切换到近似算法来计算阶乘，使其达到常数时间。对于小 k，您可以使用迭代来防止精度损失，因为惩罚会很低，而且小 k 也不多。

另一种方法是构建一个大数组，其中包含所有可能用于计算的阶乘，在提交任何任务之前必须运行。这种缓存方法损失的精度较低。请参阅下面关于如何并行化此过程的评论。

Answer 2

由于您需要所有 denominator，并且每个都依赖于之前的 ALL，因此我将有一个专用线程来计算所有这些；并且对于每个 denominator 计算提交一个不同的任务到你的线程池来并行计算特定的部分和。最后使用 parallel stream 聚合所有结果。以下代码显示了这些详细信息：

    public static BigDecimal calculate(int k, int numberOfThreads) {
        ExecutorService executor = Executors.newFixedThreadPool(numberOfThreads);
        List<Future<BigDecimal>> futures = new ArrayList<>(numberOfThreads);

        BigDecimal denominator = BigDecimal.ONE;
        for (int j = 1; j <= k; j++) {
            denominator = denominator.multiply(BigDecimal.valueOf(4 * j * j + 2 * j));
            Future<BigDecimal> future = executor.submit(computePartialSum(j, denominator));
            futures.add(future);
        }

        return futures.stream().parallel()
            .map(future.get())
            .reduce(BigDecimal.ZERO, BigDecimal::add).add(BigDecimal.valueOf(3));
    }

    public static Callable<BigDecimal> computePartialSum(int curr, BigDecimal denominator) {
        return () -> {
            long numerator = 3 - 4 * curr * curr;
            return BigDecimal.valueOf(numerator).divide(denominator, 1000, RoundingMode.HALF_EVEN);
        };
    }

不过，您的瓶颈将是阶乘的计算；您可以将其划分为更小的阶乘段并缓存它们以聚合成它们的真实值，我的两分钱。

Complete code on GitHub

Answer 3

感谢您的回答！我用一个简单的 for 循环缓存了阶乘，我得到了另一个计算的好结果：

1 thread = 17ms
2 threads  = 10ms
4 threads = 7ms

但是我需要画一个类似于下图的图表，只有我利用线程计算阶乘才有可能。

我测试了这个n!算法：

public BigDecimal calculate(int number) {
        if (number == 0 || number == 1) {
            return BigDecimal.ONE;
        }
        List<Callable<BigDecimal>> callables = new ArrayList<>();
        int step = number / processors;
        for (int i = 2; i <= number; i += step + 1) {
            callables.add(new FactorialPartCalculator(i, i + step >= number ? number : i + step));
        }
        List<Future<BigDecimal>> futures = executor.invokeAll(callables);
        BigDecimal result = BigDecimal.ONE;
        for (Future<BigDecimal> future : futures) {
            result = result.multiply(future.get());
        }
        return result;
    }
public class FactorialPartCalculator implements Callable<BigDecimal> {
    @Override
    public BigDecimal call() throws Exception {
        BigDecimal factorialPart = BigDecimal.ONE;
        for (int i = start; i <= end; i++) {
            factorialPart = factorialPart.multiply(BigDecimal.valueOf(i));
        }

        return factorialPart;
    }

我在 20000! 的 6 个线程中获得了 6.4 倍的加速。所以我需要缓存阶乘并将缓存过程包括在整体时间中。该程序将在 32 个处理器上进行测试，我应该获得尽可能多的加速

所以我的问题是如何更改上述算法以将所有阶乘存储在一个数组中？如果有帮助，我只需要奇数阶乘。

提高并行计算欧拉数的性能

Improve performance of parallel calculation of euler number

java

math

parallel-processing

multithreading

eulers-number