générateur multithread nombre premier

Question

Je:

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

I mis en œuvre cela et il fonctionne, mais le problème est que chaque thread génère sa propre liste des nombres premiers [2, n]. Mais je veux que les deux threads travaillent sur la même tâche de générer des nombres premiers, en commutant les uns avec les autres, pas indépendamment. Comment diviser n en nombre de threads?

#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

Ce que vous voulez est loin d'être trivial. Mais voici une idée de réflexion, de recherche et de test pour deux threads.

Pour ce faire, vous devez "séparer" le travail entre les deux threads. Par exemple, faites en sorte que le premier thread recherche les nombres premiers entre [ 2, k ] et que le second thread recherche les nombres premiers entre [ k+1, x ].

C'était la partie triviale. Voici le problème - comment trouver x? (k est facile - x/2).

Vous devriez rechercher - comment trouver le nombre de nombres premiers dans un intervalle donné, par exemple. This pourrait être utile: il est dit, que vous pouvez utiliser:

N ~~ x/ln(x) 

où N est le nombre de nombres premiers, inférieur à x. Eh bien, je ne suis pas un mathématicien et je ne peux pas vous donner maintenant la solution, mais il devrait y avoir un moyen, ayant N de trouver .

Notez que cela fonctionne bien pour les grands nombres. Ainsi, une fois que vous aurez trouvé x, vous pourrez diviser le travail entre les deux threads. Comme vous le voyez, c'est vraiment loin d'être trivial et il n'y a pas de méthode exacte (précise) pour trouver x (N).

---

Bien sûr, l'autre façon triviale (et beaucoup plus facile, mais pas si bon) est de connaître la gamme de N et juste divisé en deux intervalles. Ou, trouver le premier, disons, 100 nombres premiers n'est pas un gros problème. Mais trouver le premier 1000 est quelque chose d'autre. Dans ce cas, vous pouvez simplement démarrer des threads supplémentaires pour chaque nombre premier de +500, par exemple.

---

Une autre idée est de faire une recherche pour trouver le rapprochement des N -ème nombre premier. Cela peut aider: Is there a way to find the approximate value of the nth prime?

Answer 2

Excuses si j'ai mal interprété votre message, mais je soupçonne que vous avez mal compris ce qu'est le multi threading. Votre code et la dernière question suggèrent que vous pensez que démarrer plusieurs threads identiques signifie qu'ils divisent automatiquement la tâche entre eux. C'est fondamentalement incorrect. Nous souhaitons tous que c'était, mais ce n'est pas le cas.

Il existe plusieurs approches.Il y a l'approche «manuelle» où vous exploitez les opportunités de parallélisme dans votre problème et écrivez un thread pour chaque bit (ou démarrez le même thread plusieurs fois avec des paramètres différents, de toute façon les threads + données ne sont pas identiques). Vous pouvez ensuite exécuter ces threads en parallèle. En substance, c'est l'approche proposée par Kirol Kirov.

Une alternative qui peut très bien fonctionner pour les problèmes mathématiques avec des boucles longues est d'utiliser un compilateur qui peut décomposer automatiquement la boucle en threads séparés au moment de l'exécution. Cela signifie que vous écrivez du code monothread ordinaire et dites au compilateur de générer des threads partout où il peut déterminer qu'il est sûr de le faire. Vous sauve beaucoup de travail et dans les bonnes circonstances produit des résultats efficaces. Le compilateur Sun C peut le faire sur Solaris et Intel peut le faire aussi (peut-être seulement sur Windows). Certaines recherches sur les dernières et les plus importantes peuvent être utiles. Cependant, cela ne vous apprendra rien sur la programmation multi-thread.

Une autre approche consiste à utiliser quelque chose comme openMPI qui (je pense) vous permet de mettre des instructions #pragma avant les boucles pour dire que vous voulez que la boucle des tuiles soit exécutée en parallèle. Un peu comme la version manuelle de ce que les compilateurs Intel et Sun peuvent faire.