Как я могу заставить этот главный искатель работать параллельно

Question

Я знаю, что первопричина хорошо изучена, и существует множество различных реализаций.Мой вопрос, используя предоставленный метод (пример кода), как я могу разбить работу?Машина, на которой она будет работать, имеет 4 четырехъядерных гиперпоточных процессора и 16 ГБ ОЗУ.Я понимаю, что есть некоторые улучшения, которые могут быть сделаны, особенно в методе IsPrime.Я также знаю, что проблемы возникнут, когда в списке будет более int.MaxValue элементов.Меня не волнует ни одно из этих улучшений.Единственное, что меня волнует, это как разбить работу.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Prime
{
    class Program
    {
        static List<ulong> primes = new List<ulong>() { 2 };

        static void Main(string[] args)
        {
            ulong reportValue = 10;
            for (ulong possible = 3; possible <= ulong.MaxValue; possible += 2)
            {
                if (possible > reportValue)
                {
                    Console.WriteLine(String.Format("\nThere are {0} primes less than {1}.", primes.Count, reportValue));

                    try
                    {
                        checked
                        {
                            reportValue *= 10;
                        }
                    }
                    catch (OverflowException)
                    {
                        reportValue = ulong.MaxValue;
                    }
                }

                if (IsPrime(possible))
                {
                    primes.Add(possible);
                    Console.Write("\r" + possible);
                }
            }

            Console.WriteLine(primes[primes.Count - 1]);
            Console.ReadLine();
        }

        static bool IsPrime(ulong value)
        {
            foreach (ulong prime in primes)
            {
                if (value % prime == 0) return false;
                if (prime * prime > value) break;
            }

            return true;
        }
    }
}

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

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

Answer 1

При желании вы можете распараллелить обе операции: проверку простого числа и проверку нескольких простых чисел одновременно.Хотя я не уверен, что это поможет.Если честно, я бы подумал об удалении потоков в main ().

Я пытался оставаться верным вашему алгоритму, но для его ускорения я использовал x * x вместо reportvalue;это то, что вы можете легко вернуть, если хотите.

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

Также моя концепция пула потоков может не существовать так, как я хочу ее использовать

Вот мой путь (псевдо-ish-код):

List<int> primes = {2};  
List<int> nextPrimes = {};
int cores = 4;
main()
{   
  for (int x = 3; x < MAX; x=x*x){  
    int localmax = x*x;
    for(int y = x; y < localmax; y+=2){  
      thread{primecheck(y);}
    }
  "wait for all threads to be executed"
  primes.add(nextPrimes);
  nextPrimes = {};
  }
}

void primecheck(int y)
{  
  bool primality;  
  threadpool? pool;
  for(int x = 0; x < cores; x++){
    pool.add(thread{
      if (!smallcheck(x*primes.length/cores,(x+1)*primes.length/cores ,y)){
        primality = false;
        pool.kill();
      }
    });
  }  
  "wait for all threads to be executed or killed"
  if (primality)
    nextPrimes.add(y);  
}

bool smallcheck(int a, int b, int y){  
  foreach (int div in primes[a to b])  
    if (y%div == 0)  
      return false;  
  return true;
}

E: Я добавил то, что, по моему мнению, должно выглядеть как пул, посмотрите ревизию, если хотите увидеть ее без.

Answer 2

Вместо этого используйте сито Эратосфена.Параллелизовать не стоит, если вы сначала не используете хороший алгоритм.

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

Используйте битовый массив для представления простых чисел, он занимает меньше места, чем их явное представление.

См. Также этот ответ для хорошей реализации сита (в Java нет разделения на регионы).