потоки в Java и вычисления

Вам нужно полностью переосмыслить логику вашего потока.

Различные потоки не могут получить доступ к одному и тому же диапазону array, например. если поток имеет min = 100 и max = 150, то могут использоваться и/или изменяться только элементы в диапазоне от 100 до 149 (включительно).

Ваш код:

for (int i = min; i < max; i++) {
    if (array[i]) {
        for (int j = min; j*i < array.length; j++) {
            array[i*j] = false;

начинается с i = 100, j = 100, что составляет i*j = 10000. Если массив действительно такой большой, это означает, что вы обращаетесь к array[10000], но это не разрешено. Конечно, массив не такой большой, поэтому код ничего не делает.

Ах, вы говорите, у первого потока есть min = 0 и max = 50, поэтому он изменит значения с индекса 0 (0*0) до 2401 (49*49), и, поскольку массив меньше этого, он обновит весь массив, но это не разрешено.

А теперь подумайте еще раз.

Если диапазон равен min = 100, max = 150, то вам нужно начать с очистки всех четных чисел в этом диапазоне, затем всех чисел, делящихся на 3, затем всех... и так далее, но только для этого диапазона.

Я оставлю вас переосмыслить логику.

ОБНОВЛЕНИЕ

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

Если диапазон min = 150, max = 200, то maxPrime = sqrt(200) = 14, поэтому нам нужны простые числа от 2 до 14 (включительно), тогда мы можем обновить диапазон 150-199.

Предполагая, что мы сначала обновляем array, чтобы найти все простые числа в диапазоне 2–14, мы можем использовать это для итерации множеств этих простых чисел в целевом диапазоне (150–199). Для этого нам нужно начать с наименьшего кратного простого числа, которое равно >= min, поэтому нам нужно округлить min до следующего кратного prime.

С помощью целочисленной математики, чтобы округлить до следующего кратного, мы вычисляем:

lower = (min + prime - 1) / prime * prime

Это дает нам основную логику:

maxPrime = (int) Math.sqrt(max);
for (int prime = 2; prime <= maxPrime; prime++) {
    if (array[prime]) {
        int lower = (min + prime - 1) / prime * prime;
        for (int i = lower; i < max; i += prime)
            array[i] = false

Мы также должны сделать каждый поток ответственным за первую установку всех логических значений в диапазоне, чтобы эта часть тоже стала многопоточной.

Основная логика теперь должна сначала найти простые числа в диапазоне 2-sqrt(N) в основном потоке, а затем затем разделить оставшийся диапазон между потоками.

Вот моя попытка:

public static long sumPrimes(int n, int threadCount) {
    // Find and sum the "seed" primes needed by the threads
    int maxSeedPrime = (int) Math.sqrt(n + 2); // extra to be sure no "float errors" occur
    boolean[] seedPrime = new boolean[maxSeedPrime + 1];
    AtomicLong totalSum = new AtomicLong(sumPrimes(seedPrime, seedPrime, 0, maxSeedPrime));

    // Split remaining into ranges and start threads to calculate sums
    Thread[] threads = new Thread[threadCount];
    for (int t = 0, rangeMin = maxSeedPrime + 1; t < threadCount; t++) {
        int min = rangeMin;
        int max = min + (n - min + 1) / (threadCount - t) - 1;
        threads[t] = new Thread(() ->
            totalSum.addAndGet(sumPrimes(seedPrime, new boolean[max - min + 1], min, max))
        );
        threads[t].start();
        rangeMin = max + 1;
    }

    // Wait for threads to end
    for (int t = 0; t < threadCount; t++) {
        try {
            threads[t].join();
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }

    // Return the calculated sum
    return totalSum.get();
}

private static long sumPrimes(boolean[] seedPrime, boolean[] rangePrime, int min, int max/*inclusive*/) {
    // Initialize range
    for (int i = Math.max(min, 2); i <= max; i++) {
        rangePrime[i - min] = true;
    }

    // Mark non-primes in range
    int maxPrime = (int) Math.sqrt(max + 1); // extra to be sure no "float errors" occur
    for (int prime = 2; prime <= maxPrime; prime++) {
        if (seedPrime[prime]) {
            int minMultiple = (min + prime - 1) / prime * prime;
            if (minMultiple <= prime)
                minMultiple = prime * 2;
            for (int multiple = minMultiple; multiple <= max ; multiple += prime) {
                rangePrime[multiple - min] = false;
            }
        }
    }

    // Sum the primes
    long sum = 0;
    for (int prime = min; prime <= max; prime++) {
        if (rangePrime[prime - min]) {
            sum += prime;
        }
    }
    return sum;
}

Проверить

public static void main(String[] args) {
    test(1000, 3);
    test(100000000, 4);
}
public static void test(int n, int threadCount) {
    long start = System.nanoTime();
    long sum = sumPrimes(n, threadCount);
    long end = System.nanoTime();
    System.out.printf("sumPrimes(%,d, %d) = %,d (%.9f seconds)%n",
                      n, threadCount, sum, (end - start) / 1e9);
}

Вывод

sumPrimes(1,000, 3) = 76,127 (0.005595600 seconds)
sumPrimes(100,000,000, 4) = 279,209,790,387,276 (0.686881000 seconds)

ОБНОВЛЕНИЕ 2

В приведенном выше коде используется лямбда-выражение:

threads[t] = new Thread(() ->
    totalSum.addAndGet(sumPrimes(seedPrime, new boolean[max - min + 1], min, max))
);

Если вы не хотите использовать лямбда-выражение, например. поэтому он будет работать на Java 7, вместо этого вы можете использовать анонимный класс:

threads[t] = new Thread() {
    @Override
    public void run() {
        totalSum.addAndGet(sumPrimes(seedPrime, new boolean[max - min + 1], min, max));
    }
};

Многопоточность обычно также означает, что вы хотите сделать что-то быстрее. Поэтому сначала, возможно, стоит повторить ваш первоначальный проект и ускорить его в однопоточном режиме. Тогда это гол, который нужно побить. Кроме того, для сравнения времени выполнения без написания уточненных тестов требуется время выполнения «видимой» длины.
На моей машине с «настройкой»

int max = 1_000_000_000;
boolean sieve[] = new boolean[max];
long sum = 0; // will be 24739512092254535 at the end

ваш исходный код,

for(int i=2;i<max;i++)
    if(!sieve[i]) {
        for(int j=i*2;j<max;j+=i)
            sieve[j]=true;
        sum+=i;
    }

работает 24-28 секунд. Как обсуждалось в комментариях под постом @Andreas и позже внутри (да, теперь я вижу, что это принято, и большая часть обсуждения ушла), внутренний цикл выполняет много дополнительных проверок (потому что он все время выполняет одно сравнение, даже если он на самом деле не запускается). Таким образом, внешний цикл можно разбить на две части: сначала просеивание и суммирование (до последнего «неизвестного» делителя max, который не больше его квадратного корня), а затем просто суммирование для остальных:

int maxunique=(int)Math.sqrt(max);
for(int i=2;i<=maxunique;i++)
    if(!sieve[i]) {
        for(int j=i*2;j<max;j+=i)
            sieve[j]=true;
        sum+=i;
    }
for(int i=maxunique+1;i<max;i++)
    if(!sieve[i])
        sum+=i;

Этот работает на моей машине 14-16 секунд. Значительный прирост и еще ни одного потока.

Затем идут потоки и проблема с if(!sieve[i]): при вычислении суммы такая проверка не должна происходить до того, как внутренний цикл (циклы) для более низких простых чисел, чем i, превзойдет i, поэтому sieve[i] действительно говорит, является ли это простым числом или нет. Потому что, например, если поток работает как for(int i=4;i<10001;i+=2)sieve[i]=true;, а другой поток одновременно проверяет sieve[10000], это все равно будет false, а 10000 будет ошибочно принято за простое число.
Первая попытка может заключаться в просеивании. один поток (в любом случае его внешний цикл "только" идет к квадратному корню из max) и суммируйте параллельно:

for(int i=2;i<=maxunique;i++)
    if(!sieve[i])
        for(int j=i*2;j<max;j+=i)
            sieve[j]=true;

int numt=4;
Thread sumt[]=new Thread[numt];
long sums[]=new long[numt];
for(int i=0;i<numt;i++) {
    long ii=i;
    Thread t=sumt[i]=new Thread(new Runnable() {
        public void run() {
            int from=(int)Math.max(ii*max/numt,2);
            int to=(int)Math.min((ii+1)*max/numt,max);
            long sum=0;
            for(int i=from;i<to;i++)
                if(!sieve[i])
                    sum+=i;
            sums[(int)ii]=sum;
        }
    });
    t.start();
}

for(int i=0;i<sumt.length;i++) {
    sumt[i].join();
    sum+=sums[i];
}

Это довольно аккуратно, все потоки (у меня 4 ядра) проверяют одинаковое количество кандидатов, и результат получается быстрее. Иногда почти на секунду, но в основном примерно на половину (~0,4...~0,8 секунды). Так что это на самом деле не стоит затраченных усилий, здесь петли для просеивания — это действительно трудоемкие части.

Можно решить разрешить избыточную работу и запустить поток для каждого простого числа, встречающегося в сите, даже если это не настоящее простое число, просто оно еще не отмечено галочкой:

List<Thread> threads=new ArrayList<>();
for(int i=2;i<=maxunique;i++)
    if(!sieve[i]) {
        int ii=i;
        Thread t=new Thread(new Runnable() {
            public void run() {
                for(int j=ii*2;j<max;j+=ii)
                    sieve[j]=true;
            }
        });
        t.start();
        threads.add(t);
    }
//System.out.println(threads.size());
for(int i=0;i<threads.size();i++)
    threads.get(i).join();

for(int i=maxunique+1;i<max;i++)
    if(!sieve[i])
        sum+=i;

Закомментированный println() сказал бы (на моей машине), что было создано 3500-3700 потоков (в то время как если кто-то поставит счетчик внутри исходных циклов, окажется, что 3401 будет минимумом, что много простых чисел встречается в однопоточном сито-петля). Пока перерегулирование не катастрофическое, количество потоков довольно велико, а прирост не слишком звездный, хотя он более заметен, чем в предыдущей попытке: время выполнения 10-11 секунд (которое, конечно, можно было бы уменьшить вдвое больше секунд, используя параллельный цикл суммирования).
Можно решить часть избыточной работы, отключив циклы, когда окажется, что они фильтруют не простое число:

for(int j=ii*2;j<max && !sieve[ii];j+=ii)

Это на самом деле имеет некоторый эффект, в результате чего время работы у меня составляет 8,6–10,1 секунды.

Поскольку создание 3401 потока не намного менее безумно, чем создание 3700 из них, может быть хорошей идеей ограничить их количество, и это тот момент, когда легче попрощаться с Threads. Хотя технически их можно подсчитать, для этого существуют различные встроенные инфраструктуры.
Executors может помочь ограничить количество потоков до фиксированного количества (newFixedThreadPool()) или, что еще лучше, до количества доступных процессоров (newWorkStealingPool()):

ExecutorService es=Executors.newWorkStealingPool();
ExecutorCompletionService<Object> ecs=new ExecutorCompletionService<Object>(es);

int count=0;

for(int i=2;i<=maxunique;i++)
    if(!sieve[i]) {
        int ii=i;
        count++;
        ecs.submit(new Callable<Object>() {
            public Object call() throws Exception {
                // if(!sieve[ii])
                for(int j=ii*2;j<max /**/ && !sieve[ii] /**/;j+=ii)
                    sieve[j]=true;
                return null;
            }
        });
    }
System.out.println(count);
while(count-->0)
    ecs.take();
es.shutdown();
long sum=0;

for(int i=2;i<max;i++)
    if(!sieve[i])
        sum+=i;

Таким образом, он дает результаты, аналогичные предыдущему (8,6–10,5 с). Но при малом количестве ЦП (4 ядра) замена условий приводит к некоторому ускорению (раскомментируйте if и прокомментируйте то же условие в цикле между /**/), потому что задачи выполняются в порядке их отправки, и, таким образом, большинство избыточных циклов могут выйти в самом начале, что делает повторные проверки пустой тратой времени. Тогда для меня это 8,5-9,3 с, что превосходит как лучшее, так и худшее время попытки прямого многопоточности. Однако, если у вас большое количество ЦП (я также запускал его на суперкомпьютерном узле с 32 ядрами, доступными в соответствии с Runtime.availableProcessors()), задачи будут больше перекрываться, и версия без обмана (то есть та, которая всегда выполняет проверку) будет быть быстрее.

И если вы хотите небольшое ускорение с довольно хорошей читабельностью, вы можете распараллелить внутренний цикл (что возможно и с Threads, просто очень утомительно), используя потоки:

long sum=0;
for(int i=2;i<=maxunique;i++)
    if(!sieve[i]) {
        sum+=i;
        int ii=i;
        IntStream.range(1, (max-1)/i).parallel().forEach(
            j -> sieve[ii+j*ii]=true);
    }

for(int i=maxunique+1;i<max;i++)
    if(!sieve[i])
        sum+=i;

Этот очень похож на оригинальную оптимизированную пару петель, и все еще имеет некоторую скорость, 9,4-10,0 секунд для меня. Так что это медленнее, чем другие (примерно на 10% или около того), но это намного проще.

1. Я исправил ряд ошибок: xy<maxuniques теперь xy<=maxuniques. Хотя это, к сожалению/к счастью, не повлияло на огромный результат, оно не помогло в таком простом случае, как max=9 (когда maxunique=3 и с циклом xy<3 9 останется простым, а сумма будет 26 вместо 17). Мех. Также исправлено несколько циклов продолжения (теперь они продолжаются с maxunique+1).

2. Создание неограниченного количества подзадач меня обеспокоило, и, к счастью, я нашел перевернутую конструкцию, в которой мы не проверяем достижение sqrt(max) (то есть maxunique), а вместо этого знаем, что если мы закончили просеивание с числами ниже определенного limit, мы можно продолжить проверку чисел до limit*limit, потому что все, что остается простым внутри диапазона (limit ... limit*limit), на самом деле является простым (и мы все еще можем помнить, что этот верхний предел ограничен maxunique). Таким образом, их можно просеивать параллельно.

Базовый алгоритм, только для проверки (однопоточный):

int limit=2;
do {
    int upper=Math.min(maxunique+1,limit*limit);
    for(int i=limit;i<upper;i++)
        if(!sieve[i]) {
            sum+=i;
            for(int j=i*2;j<max;j+=i)
                sieve[j]=true;
        }
    limit=upper;
} while(limit<=maxunique);

for(int i=limit;i<max;i++)
    if(!sieve[i])
        sum+=i;

По какой-то причине он немного медленнее, чем исходный вариант с двумя циклами (13,8-14,5 секунд против 13,7-14,0 секунд, мин/макс 20 запусков), но я все равно интересовался распараллеливанием.
Вероятно, из-за неравномерного распределения. простых чисел, использование параллельного потока не сработало (я думаю, что он просто предварительно делит работу на, казалось бы, равные части), но подход на основе Executor работает хорошо:

ExecutorService es=Executors.newWorkStealingPool();
ExecutorCompletionService<Object> ecs=new ExecutorCompletionService<>(es);

int limit=2;
int count=0;
do {
    int upper=Math.min(maxunique+1,limit*limit);
    for(int i=limit;i<upper;i++)
        if(!sieve[i]) {
            sum+=i;
            int ii=i;
            count++;
            ecs.submit(new Callable<Object>() {
                public Object call() throws Exception {
                    for(int j=ii*2;j<max;j+=ii)
                        sieve[j]=true;
                    return null;
                }
            });
        }
    while(count>0) {
        count--;
        ecs.take();
    }
    limit=upper;
} while(limit<=maxunique);

es.shutdown();

for(int i=limit;i<max;i++)
    if(!sieve[i])
        sum+=i;

Для среды с небольшим количеством ЦП это пока самая быстрая (7,4-9,0 секунд против 8,7-9,9 секунд для «бесконечного числа потоков» и 8,5-9,2 секунд для другого Executor). Однако в начале он выполняет небольшое количество параллельных задач (при limit=2 он запускает только два параллельных цикла, для 2 и 3), и, кроме того, это самые длинные выполняемые циклы (с наименьшими шагами) и из-за этого в среде с большим количеством ЦП он занимает лишь второе место после исходного процессора на основе Executor, 2,9–3,6 секунды против 2,7–3,2 секунды).
Конечно, можно реализовать отдельный разгон для начать, явно собрав необходимое количество простых чисел для насыщения доступных ядер, а позже переключиться на этот подход на основе limit, и тогда результат может превзойти другие вне зависимости от количества ядер. Однако я думаю, что пока могу сопротивляться искушению.

Я думаю, что ваша проблема в этом коде:

   public void run() {
        for (int i = min; i < max; i++) {
            if (array[i]) {
                for (int j = min; j*i < array.length; j++) {
                    array[i*j] = false;
                }
                sum += i;
            }
        }
        allFinished.release();
    }

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

Если вы приведете пример, который дает плохие результаты, мы сможем достаточно легко проверить теорию.