如何爲多線程分塊質數？

Question

我對C比較陌生，到目前爲止幾乎沒有多線程的經驗。我寫了一個小程序來計算一個數組是否是素數或複合數。這工作正常，但是當處理更大的數字時，我想分割線程間的工作負載。

我有種想法，這將如何工作，我只是無法看到如何在C中實現這一點。作爲一個簡單的例子，如果我們採用素數199，我會將這個數除以核心數（如4）得到49.75。然後我們將這個數字四捨五入到50.每個線程都會被賦予一個範圍來計算。

第一個線程將計算從i 2到50，第二個從i 51到102，依此類推。

我希望這樣做有道理，我敢肯定解決方案比我想象的要容易，這只是我不能爲我的生活做出來的。

我的代碼：

#include <pthread.h> 
#include <inttypes.h> 
#include <stdio.h> 
#include <unistd.h> 

#ifdef _SC_NPROCESSORS_ONLN 
#define NUM_THREADS sysconf(_SC_NPROCESSORS_ONLN) 
#else 
#define NUM_THREADS 1 
#endif 

uint64_t numbers[] = {7,3,19,17,199,333}; // Numbers to check 

void *work(void *n_void_ptr); 
int isPrime(uint64_t n); 

int main() 
{ 
    int rc; 
    pthread_t thread[NUM_THREADS]; 

    for (int i = 0; i < sizeof(numbers)/sizeof(uint64_t); i++) { 
     rc = pthread_create(&thread[i], NULL, work, &numbers[i]); 
    } 

    pthread_exit(NULL); 

    return 0; 
} 

void *work(void *n_void_ptr) 
{ 
    uint64_t *n_ptr = (uint64_t *)n_void_ptr; 

    if (!isPrime(*n_ptr)) { 
     printf("%llu is a prime!\n", *n_ptr); 
    } 

    pthread_exit(NULL); 
} 

int isPrime(uint64_t n) 
{ 
    int count = 0; 
    uint64_t i; // Any number > n/2 cannot be a factor 

    for (i = 2; i < n/2 - 0.5; i++) { 
     if (n % i == 0) { 
      count++; 
     } 

     if (count == 1) { 
      printf("%llu is composite!\n", n); 

      return -1; // n is not prime 
     } 
    } 

    return 0; // n is prime 
} 

Answer 1

所以，你想要做的是有不同的線程來檢查不同的非重疊的範圍。

我們首先需要一個結構來將範圍傳遞給工作者。所以我們開始 -

typedef struct { 
    int lower; 
    int upper; 
    int number; 
    int result; 
} worker_range; 

現在在主要我假設你需要檢查199和每個線程需要檢查50個值。

我們這樣開始

worker_threads **ranges = malloc(sizeof(worker_threads*) * (199/50 + 1)); 

現在，我們需要生成線程

int i; 
for (i = 0; i < 199/50 + 1; i++){ //Fix this so that extra threads are not spawned. 
    ranges[i] = malloc(sizeof(worker_range)); 
    ranges[i]->number = 199; 
    ranges[i]->lower = 2 + i * 50; 
    ranges[i]->upper = range->lower + 50; //We are probably okay with a bit of overflow 
    range[i]->result = 0; 
    pthread_create(&thread[i], NULL, work, ranges[i]); 
} 

現在所有線程都已經開始了，我們等待他們完成。

int flag = 0; 
for (i = 0 ;i < 199/50 + 1; i++) { 
    pthread_join(thread[i]); 
    if(ranges[i]->result == 1) 
     flag = 1; 
    free(ranges[i]); 
} 
if (flag==1){ 
    printf("%d is composite\n",199); 
}else{ 
    printf("%d is prime\n",199); 
} 
free(ranges); 

最後工人功能 -

void* work(void * param) { 
    work_range *range = param; 
    int i; 
    for(i = range->lower, i < range->upper; i++){ 
     if (range->number % i == 0){ 
      (range->result) = 1; 
      break; 
     } 
    } 
} 

我希望這有助於。