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

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; 
     } 
    } 
} 

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

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

Answer 1

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

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

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

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

Вот мой пойти на это (псевдо-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

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

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

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

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