java - 埃拉托色尼平行筛的性能

问题描述

我正在尝试修改顺序的“埃拉托色尼筛”算法，以利用多个内核。我的目标是提高相对于香草算法的性能，但我所有的尝试都是徒劳的......

到目前为止，这是我所拥有的：

public class ParallelSieve implements SieveCalculator
{
    private int nThreads;

    public ParallelSieve(int nThreads) {
        this.nThreads = nThreads;
    }

    @Override
    public SieveResult calculate(int ceiling) {
        if (ceiling < Primes.MIN) {
            return SieveResult.emptyResult();
        }

        ThreadSafeBitSet isComposite = new ThreadSafeBitSet(ceiling + 1);

        ForkJoinPool threadPool = new ForkJoinPool(nThreads);

        for (int n = Primes.MIN; n * n <= ceiling; ++n) {
            if (isComposite.get(n)) {
                continue;
            }
            int from = n * n;
            int to = (ceiling / n) * n;
            threadPool.invoke(new RecursivelyMarkSieve(isComposite, from, to, n));
        }

        threadPool.shutdown();

        return new SieveResult(isComposite);
    }

    private class RecursivelyMarkSieve extends RecursiveAction
    {
        private static final int THRESHOLD = 1000;
        private final ThreadSafeBitSet isComposite;
        private final int from, to, step;

        RecursivelyMarkSieve(ThreadSafeBitSet isComposite, int from, int to, int step) {
            this.isComposite = isComposite;
            this.from = from;
            this.to = to;
            this.step = step;
        }

        @Override
        protected void compute() {
            int workload = (to - from) / step + 1;
            if (workload <= THRESHOLD) {
                for (int index = from; index <= to; index += step) {
                    isComposite.set(index);
                }
                return;
            }

            int middle = (to - from) / (2 * step);
            int leftSplit = from + middle * step;
            int rightSplit = from + (middle + 1) * step;
            ForkJoinTask.invokeAll(
                    new RecursivelyMarkSieve(isComposite, from, leftSplit, step),
                    new RecursivelyMarkSieve(isComposite, rightSplit, to, step)
            );
        }
    }
}

我的想法是，一旦找到一个素数，我们就可以通过线程池分解标记其倍数的工作。我被 ForkJoinPool 所吸引是因为我可以限制正在使用的线程数量，并且可以轻松地提交自定义的递归任务，从而打破标记倍数的工作。不过，我的解决方案太慢了！有什么建议么？

标签： javaconcurrencyparallel-processing

对于所有预期的多线程解决方案，您必须平衡通过将可用处理量与管理多线程解决方案的开销相乘所获得的优势。

尤其是：

启动线程有一些开销。
如果您同步或使用线程安全类（内置同步），则会产生同步开销，而且在使用同步方法时，您可能会将解决方案汇集到单个线程。

查看您的解决方案，实际逻辑（计算方法）在计算方面几乎没有，但访问线程安全位集并启动一个新线程。因此，开销将远远超过实际逻辑。

要有效地使用多线程，您需要弄清楚如何拆分任务，以便每个线程都有大量工作要做，并且同步数据结构的使用受到限制。您不能为遇到的每个整数调用一个新线程。

网上有很多关于如何并行化 Eratosthenes 的筛子，所以我建议看看其他人是如何解决这个问题的。

今天的一般范式是“map-reduce”。将问题集分成块。分别处理每个块。再次将结果整理在一起。重复和/或递归。

java - 埃拉托色尼平行筛的性能

问题描述

解决方案

推荐阅读