Производительность параллельного сита из эратосфена

Question

Я пытаюсь изменить последовательный алгоритм "Сито Эратосфена", чтобы использовать преимущества нескольких ядер.Моя цель состояла в том, чтобы повысить производительность по сравнению с алгоритмом ванили, но все мои попытки были тщетны ...

Вот что я имею до сих пор:

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, потому что я могу ограничить количество используемых потоков и легко отправлять ему пользовательские рекурсивные задачи, которые прерывают работу по маркировке кратных чисел.Тем не менее, мое решение слишком медленное!Есть предложения?

Answer 1

Со всеми предполагаемыми многопоточными решениями вы должны сбалансировать преимущество, которое вы получите, умножив объем доступной обработки на издержки, связанные с администрированием многопоточного решения.

В частности:

• Есть некоторые издержки для запуска потоков.
• Если вы синхронизируете или используете потокобезопасный класс (со встроенной синхронизацией), это приводит к накладным расходам синхронизации, плюс тот факт, что при использовании синхронизированных методов вы, возможно, направляете решение обратно в один поток.

Глядя на ваше решение, реальная логика (метод вычисления) имеет очень мало с точки зрения вычислений, но получает доступ к потокобезопасному битовому набору и запускает новый поток. Таким образом, накладные расходы будут намного превышать реальную логику.

Чтобы эффективно использовать многопоточность, вам необходимо выяснить, как разделить вашу задачу так, чтобы каждый поток выполнял значительный объем работы и использование синхронизированных структур данных было ограничено. Вы не можете вызывать новый поток для каждого целого числа, с которым вы сталкиваетесь.

В Интернете много говорится о том, как распараллелить сито Эратосфена, поэтому я предлагаю посмотреть, как другие решили эту проблему.

Общая парадигма сегодня - «сокращение карты». Разбейте проблемный набор на куски. Обработайте каждый кусок отдельно. Снова сопоставьте результаты. Повторить и / или повторить.