如何为多线程分块素数？

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);

最后是worker函数-

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;
        }
    }
}

希望对您有所帮助。

如何为多线程分块素数？

How do I chunk prime numbers for multithreading?

c

primes

multithreading

pthreads