我該如何使這個主要發現者並行工作

我知道主要發現已經很好研究，並且有很多不同的實現。我的問題是，使用提供的方法（代碼示例），我該如何去分解工作？它將運行的機器有4個四核心超線程處理器和16GB內存。我意識到可以進行一些改進，特別是在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）使用每個線程測試一個可能的素數，當下一個要測試的數大於發現的最高素數的平方時，這可能導致發現不連續的素數串並且遇到未使用的資源問題。

對我來說，感覺這兩種情況只是在構建素數列表的早期階段才具有挑戰性，但我並不完全確定。這是通過個人練習打破這種工作而完成的。

來源

2010-08-13 Nick Larsen

如果你願意，你可以並行兩種操作：檢查素數和一次檢查多個素數。雖然我不確定這會有所幫助。說實話，我會考慮刪除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：我加了什麼，我認爲池應該是什麼樣子，在修訂看，如果你想看到它沒有。

來源

2010-08-16 20:59:13

改爲使用Eratosthenes篩。除非您首先使用了一個好的算法，否則不值得並行化。

將空間分隔成大片地區，並用自己的螺紋篩分。或者更好地在大區域使用一些workqueue概念。

使用位數組來表示質數，它比顯式表示它們需要更少的空間。

另請參閱this answer以獲得篩選的良好實現（使用Java，不分區域）。

來源

2010-08-13 21:42:42 starblue

「這不值得並行化，除非你首先使用了一個好的算法。」該問題明確要求您將此實現並行化，而不是另一個主要發現算法。這種算法是否滿足一些隨意的價值衡量與如何並行化無關。 – 2010-08-14 09:11:23

我該如何使這個主要發現者並行工作

回答

相關問題