在C中使用多线程显示素数

Question

在函数

printprime

中，我使用四个线程迭代每个元素，这几乎相当于一个单线程程序。我想将

i

增加

i=i+MAX_THREADS

。我使用四个线程，因为我的笔记本电脑有四个处理器，并且它已完全优化。有人可以告诉我如何调整

printprime

以便每个线程迭代单个数字。例如，线程 1 检查 2、6、10... 线程 2 检查 3、7、11... 等等。

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

#define N 30
#define MAX_THREADS 4

int prime_arr[N] = { 0 };

void *printprime(void *ptr) {
    int j, flag;
    int i = (int)(long long int)ptr;
    for (i = 2; i < N; i++) {
        flag = 0;
        for (j = 2; j <= i / 2; j++) {
            if (i % j == 0) {
                flag = 1;
                break;
            }
        }

        if (flag == 0) {
            prime_arr[i] = 1;
        }
    }
}

int main() {
    pthread_t tid[MAX_THREADS] = {{ 0 }};
    int count = 0;
    for (count = 0; count < MAX_THREADS; count++) {
        printf("\r\n CREATING THREADS %d", count);
        pthread_create(&tid[count], NULL, printprime, (void *)count);
    }
    printf("\n");
    for (count = 0; count < MAX_THREADS; count++) {
        pthread_join(tid[count], NULL);
    }

    int c = 0;
    for (count = 0; count < N; count++)
        if (prime_arr[count] == 1)
            printf("%d ", count);

    return 0;
}

Answer 1

为了实现理想的效果，请将函数

i

中的变量

void *printprime(void *ptr)

增加

MAX_THREADS

（在您的情况下为 4）。

注意：

printf("Thread id[%d] checking [%d]\n",pthread_self(),i);

行用于显示哪个线程正在检查哪个值。

以下代码可能会有所帮助：

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

#define N 30
#define MAX_THREADS 4

int prime_arr[N]={0};

void *printprime(void *ptr)
{
    int  j,flag;
    int i=(int)(long long int)ptr;
    while(i<N)
    {
        printf("Thread id[%d] checking [%d]\n",pthread_self(),i);
        flag=0;
        for(j=2;j<=i/2;j++)
        {
            if(i%j==0)
            {
                flag=1;
                break;
            }
        }

        if(flag==0 && (i>1))
        {
            prime_arr[i]=1;
        }
        i+=MAX_THREADS;
  }
}

int main()
{
    pthread_t tid[MAX_THREADS]={{0}};
    int count=0;
    for(count=0;count<MAX_THREADS;count++)
    {
        printf("\r\n CREATING THREADS %d",count);
        pthread_create(&tid[count],NULL,printprime,(void*)count);
    }
    printf("\n");
    for(count=0;count<MAX_THREADS;count++)
    {
        pthread_join(tid[count],NULL);
    }

    int c=0;
    for(count=0;count<N;count++)
        if(prime_arr[count]==1)
            printf("%d ",count);

    return 0;
 }

Answer 2

您的代码中存在多个问题：

• 所有线程都使用

  for (i = 2; i < N; i++)

  ，因此它们执行完全相同的扫描，测试相同的数字...使用多个线程没有任何优势。

• 对于扫描质数但不打印它们的函数来说，名称

  printprime

  非常令人困惑。

• 您在多个线程中修改同一数组而不同步：如果从不同线程访问同一元素并且元素大小小于原子大小，则这具有未定义的行为。

• 即使为每个线程修改代码来测试您在问题中记录的子集，这也会非常低效，因为所有其他线程最终只会测试偶数。

• 循环

  for (j = 2; j <= i / 2; j++)

  对于素数来说迭代时间太长。

  j * j > i

  时应停止，可测试为

  for (j = 2; i / j <= j; j++)

  。

• 即使进行了这种优化，试除法填充

  prime_arr

  数组的效率也非常低。实现埃拉托斯特尼筛法要优越得多，并且更适合多线程方法。

这是一个例子：

#include <stdio.h>
#include <stdint.h>
#include <pthread.h>

#define N 10000000
#define MAX_THREADS 4

unsigned char prime_arr[N];

void *scanprime(void *ptr) {
    int n, i, j, flag, start, stop;
    n = (int)(intptr_t)ptr;
    start = N / MAX_THREADS * n;
    stop = N / MAX_THREADS * (n + 1);
    if (start < 2)
        start = 2;
    if (n == MAX_THREADS - 1)
        stop = N;
    for (i = start; i < stop; i++) {
        flag = 1;
        for (j = 2; i / j >= j; j++) {
            if (i % j == 0) {
                flag = 0;
                break;
            }
        }
        prime_arr[i] = flag;
    }
    return NULL;
}

void *sieveprimes(void *ptr) {
    int n, i, j, start, stop;
    n = (int)(intptr_t)ptr;
    /* compute slice boundaries */
    start = N / MAX_THREADS * n;
    stop = N / MAX_THREADS * (n + 1);
    /* special case 0, 1 and 2 */
    if (n == 0) {
        prime_arr[0] = prime_arr[1] = 0;
        prime_arr[2] = 1;
        start = 3;
    }
    if (n == MAX_THREADS - 1) {
        stop = N;
    }
    /* initialize array slice: only odd numbers may be prime */
    for (i = start; i < stop; i++) {
        prime_arr[i] = i & 1;
    }
    /* set all multiples of odd numbers as composite */
    for (j = 3; j * j < N; j += 2) {
        /* start at first multiple of j inside the slice */
        i = (start + j - 1) / j * j;
        /* all multiples below j * j have been cleared already */
        if (i < j * j)
            i = j * j;
        /* only handle odd multiples */
        if ((i & 1) == 0)
            i += j;
        for (; i < stop; i += j + j) {
            prime_arr[i] = 0;
        }
    }
    return NULL;
}

int main() {
    pthread_t tid[MAX_THREADS] = { 0 };
    int i;
    for (i = 0; i < MAX_THREADS; i++) {
        printf("Creating thread %d\n", i);
        pthread_create(&tid[i], NULL, sieveprimes, (void *)(intptr_t)i);
    }
    for (i = 0; i < MAX_THREADS; i++) {
        pthread_join(tid[i], NULL);
    }

    int count = 0;
    for (i = 0; i < N; i++) {
        count += prime_arr[i];
        //if (prime_arr[i] == 1)
        //    printf("%d\n", i);
    }
    printf("%d\n", count);
    return 0;
}