多线程素数生成器

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编译器可以执行的手动版本。