多線程素數生成器

Question

我：

input1: n to generate primes up to 
input2: no of threads to generate primes 

我實現了這一點，它的工作原理，但問題是，每一個線程生成自己的素數[2, n]的名單。

但我希望這兩個線程都能處理產生素數的相同任務，而不是彼此獨立切換。如何將n分成多個線程？

#include <pthread.h> 
#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 

void *BusyWork(void *threadid) 
{ 
long tid; 
tid = (long)threadid; 
printf("Hello World! It's me, thread # %ld\n", tid); 

double s,d; 
int n,i,c,k,p,cs,nsqrt;  
printf("Input an integer n > 1 to generate primes upto this n: "); // prompt 
scanf("%d",&n); 
printf("Entered integer: %d\n",n); 
int array[n]; 
for(i=0;i<n;i++) 
    array[i]=0; 
s=sqrt(n); 
d=floor(s); 
nsqrt = (int) d; 

for (c= 2; c <= nsqrt; c++)// note here < is not working <= is working here. 
    { 
     if(array[c]==0) 
      { 
       cs = c*c; 
       k=0; 
       for(p=cs; p<n; p=(cs+k*c)) 
        { 
         k++; 
         array[p] = 1; 
       }//for 
      }//if 
    }//for 

    for (i = 2; i < n; i++) 
    { 
     if (array[i]==0) 
     { 
      printf("%5d",i); 
     }//if 
    }// for 
    printf("\n"); 


    printf("Above prime numbers are generated from me i.e. thread # %ld GOOD BYE!!! \n ", tid); 


    pthread_exit((void*) threadid); 
    } 

    int main (int argc, char *argv[]) 
    { 

    //////// time cal /////////////////// 

    struct timespec start, finish; 
    double elapsed; 

     clock_gettime(CLOCK_MONOTONIC, &start); 
    ///////////////////////////////////// 

    int NUM_THREADS; 
    printf("Please Input Total Number of Threads you want to make:- "); 
    scanf("%d",&NUM_THREADS); 


    pthread_t thread[NUM_THREADS]; 
    pthread_attr_t attr; 
     int rc; 
    long t; 
    void *status; 

     /* Initialize and set thread detached attribute */ 
    pthread_attr_init(&attr); 
     pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE); 

     for(t=0; t<NUM_THREADS; t++) { 
     printf("Main: creating thread %ld\n", t); 
     rc = pthread_create(&thread[t], &attr, BusyWork, (void *)t); 
     if (rc) { 
      printf("ERROR; return code from pthread_create() is %d\n", rc); 
      exit(-1); 
      } 
     } 

     /* Free attribute and wait for the other threads */ 
     pthread_attr_destroy(&attr); 
     for(t=0; t<NUM_THREADS; t++) { 
     rc = pthread_join(thread[t], &status); 
     if (rc) { 
     printf("ERROR; return code from pthread_join() is %d\n", rc); 
     exit(-1); 
     } 
     printf("Main: completed join with thread %ld having a status of %ld\n",t, (long)status); 
     } 

    printf("Main: program completed. Exiting.\n"); 
    ////////////// time end //////////////////////// 
    clock_gettime(CLOCK_MONOTONIC, &finish); 

    elapsed = (finish.tv_sec - start.tv_sec); 
     elapsed += (finish.tv_nsec - start.tv_nsec)/1000000000.0; 
    printf("Total time spent by the main: %e \n", elapsed); 
    ////////////////////////////////////////////////////////// 
    pthread_exit(NULL); 
    } 

Answer 1

你想要什麼遠不是微不足道的。但是這裏有兩個線程的思考，研究和測試的想法。

爲此，您需要在兩個線程之間「拆分」作業。例如，使第一個線程查找[ 2, k ]之間的素數，並使第二個線程查找[ k+1, x ]之間的素數。

這是微不足道的部分。問題來了 - 如何找到x？ （k很容易 - x/2）。

您應該研究 - 例如，如何查找給定間隔中的素數數目。 This可能是有益的：它說，你可以使用：

N ~~ x/ln(x) 

其中N是素數的數量，小於x。

那麼，我不是一個數學家，我現在不能給你解決方案，但應該有一種方法，讓N找到x。

請注意，這對大量工作正常。

所以，有了這個，一旦你找到了x，你將能夠在兩個線程之間分配工作。

正如你所看到的，這實際上並不是微不足道的，並且沒有確切的（精確的）找到x（N）的方法。

---

當然，其他瑣碎的方式（和輕鬆了許多，但不是好）是知道的N範圍，只是把它分成兩個區間。或者，找到第一個例如10​​0個素數並不是什麼大問題。但找到第一個1000是另一回事。在這種情況下，例如，您可以爲每個+500的素數啓動額外的線程。

---

另一個想法是做一個研究尋找近似的N素數。這可能有所幫助：Is there a way to find the approximate value of the nth prime?

Answer 2

道歉，如果我錯誤地解釋了你的帖子，但我懷疑你誤解了多線程的內容。你的代碼和最後一個問題表明，你認爲啓動多個相同的線程意味着它們自動地將任務自動分開。這從根本上說是不正確的。我們都希望這是，但事實並非如此。

有幾種方法。有一種'手動'的方法，你可以在你的問題中利用並行機會，併爲每一位寫一個線程（或者用不同的參數多次啓動同一個線程，無論哪種方式線程和數據都不相同）。然後您可以並行運行這些線程。實質上，這是基羅基洛夫建議的方法。

對於長循環的數學問題可以很好地工作的替代方法是使用編譯器，該編譯器可以在運行時自動將循環分解爲單獨的線程。這意味着你編寫普通的單線程代碼，並告訴編譯器生成線程，只要它能確定它是安全的。爲您節省大量的工作，並在適當的環境下產生有效的結果。 Sun C編譯器可以在Solaris上執行此操作，英特爾也可以執行此操作（可能僅在Windows上）。對最新和最好的一些研究可能是值得的。但是，這不會教給你任何有關多線程編程的知識。

另一種方法是使用類似openMPI的（我認爲）允許您在for循環之前放置#pragma語句，以表示您希望並行執行tile循環。有點像英特爾和Sun編譯器可以執行的手動版本。