многопоточного генератора простое число

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 это число простых чисел, меньше, чем х.

Ну, я не математик, и я не могу дать вам прямо сейчас решение, но должен быть способ, имея N, чтобы найти x.

Обратите внимание, что это отлично работает для больших чисел.

Итак, имея это, как только вы найдете x, вы сможете разделить работу между двумя потоками.

Как вы видите, это действительно далеко не тривиально и нет точного (точного) метода для нахождения x (N).

---

Конечно, другой тривиальный путь (и намного проще, но не так хорошо), чтобы знать диапазон N и просто разделить его на два интервала. Или, найдя первое, скажем, 100 простых чисел, не имеет большого значения. Но найти первые 1000 - это что-то еще. В этом случае вы можете просто запустить дополнительные потоки для каждого +500 простых чисел, например.

---

Другая идея состоит в том, чтобы сделать исследование для нахождения аппроксимации N го простого числа. Это может помочь: Is there a way to find the approximate value of the nth prime?

Answer 2

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

Существует несколько подходов.Существует «ручной» подход, в котором вы используете возможности параллелизма в своей проблеме и записываете поток для каждого бита (или запускаете один и тот же поток несколько раз с разными параметрами. В любом случае потоки + данные не идентичны). Затем вы можете запускать эти потоки параллельно. По сути, это подход, предложенный Киролом Кировым.

Альтернативой, которая может хорошо работать для математических задач с длинными циклами, является использование компилятора, который может автоматически разложить цикл на отдельные потоки во время выполнения. Это означает, что вы пишете обычный однопоточный код и сообщаете компилятору генерировать потоки везде, где он может определить, что это безопасно. Экономит вашу работу и при правильных обстоятельствах дает эффективные результаты. Компилятор Sun C может сделать это на Solaris, а Intel тоже может это сделать (возможно, только в Windows). Некоторые исследования последних и самых больших, возможно, стоит. Однако это не научит вас чему-либо о многопоточном программировании.

Другой подход - использовать что-то вроде openMPI, которое (я думаю) позволяет вам вводить инструкции #pragma в before для циклов, чтобы сказать, что вы хотите, чтобы цикл цикла выполнялся параллельно. Как и ручная версия того, что могут сделать компиляторы Intel и Sun.