从给定范围内的数字并行程序中查找素数

Question

我尝试实施埃拉托色尼筛法来查找素数。

这是我的代码块

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<omp.h>


char isPrime[1000];     

// odd-only sieve
int eratosthenesOdd(int N, int useOpenMP)
{
        /* enable/disable OpenMP */
        omp_set_num_threads(useOpenMP ? omp_get_num_procs() : 1);

        /* instead of i*i <= N we write i <= sqr(N) to help OpenMP */
        const int NSqrt = (int)sqrt((double)N);
        int memorySize = (N-1)/2;


        int i, j;
        /* Let all numbers be prime initially */
        #pragma omp parallel for
        for (i = 0; i <= memorySize; i++){
                isPrime[i] = 1;
        }


        /* find all odd non-primes */
        #pragma omp parallel for schedule(dynamic)
        for (i = 3; i <= NSqrt; i += 2){
                if (isPrime[i/2]){
                        for (j = i*i; j <= N; j += 2*i){
                                isPrime[j/2] = 0;
                        }
                }
        }

        printf("2\n")   
        for(int k=3;k<=N;k+=2){
                if(isPrime[k/2]==1){
                        printf("%d ", k);
                }
        }

        /* sieve is complete, count primes */
        int total = N >= 2 ? 1 : 0;
        #pragma omp parallel for reduction(+:total)
        for (i = 1; i <= memorySize; i++){
                total += isPrime[i];
        }

        return total;
}

int main()
{
        double start, finish;
        start =  omp_get_wtime();
        int total = eratosthenesOdd(100, 1);
        finish = omp_get_wtime();
        printf("\n %d", total);
        printf("\n Elapsed time=%e seconds", finish-start);
        return 0;
}

我从 here 那里得到了参考。代码运行很好，我可以找到给定范围内的质数。

我对我在多次试验相同期限后得到的经过时间持怀疑态度。

假设我想查看 1 到 100 之间的质数。我还想找出各种线程的运行时间。

1st trial
N=100
Number of Thread  1, elapsed time = 5.008094e-04
Number of Thread  8, elapsed time = 4.649349e-04
Number of Thread 16, elapsed time = 4.652534e-04

2nd trial
N=100
Number of Thread  1, elapsed time = 4.668552e-04sec
Number of Thread  8, elapsed time = 5.837623e-04sec
Number of Thread 16, elapsed time = 5.835127e-04sec

 3rd trial
 N=100
Number of Thread  1, elapsed time = 4.530195e-04 sec
Number of Thread  8, elapsed time = 4.66317e-04sec
Number of Thread 16, elapsed time = 6.141420e-04 sec

请问这个程序真的实现了并行程序吗？如果是这样，我怎么能及时得到这种变化？此外，当任务在线程之间划分时，与串行时间相比，时间应该减少。但是这里并没有发生这种情况。

Answer 1

我没有安装 OMP 软件，所以我不得不删除并行化。然而，一旦 'print out the prime numbers' 循环被调整以处理这样一个事实，即算法知道 2 是唯一的偶数素数并且它将奇数 X 的素数存储在 isPrime[X / 2] 中，代码就会起作用。

这导致此代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
//#include <omp.h>

static char isPrime[1000];

// odd-only sieve
//static int eratosthenesOdd(int N, int useOpenMP)
static int eratosthenesOdd(int N)
{
    /* enable/disable OpenMP */
    //omp_set_num_threads(useOpenMP ? omp_get_num_procs() : 1);

    /* instead of i*i <= N we write i <= sqr(N) to help OpenMP */
    const int NSqrt = (int)sqrt((double)N);
    int memorySize = (N - 1) / 2;

    int i, j;
    /* Let all numbers be prime initially */
    //#pragma omp parallel for
    for (i = 0; i <= memorySize; i++)
    {
        isPrime[i] = 1;
    }


    /* find all odd non-primes */
    //#pragma omp parallel for schedule(dynamic)
    for (i = 3; i <= NSqrt; i += 2)
    {
        if (isPrime[i / 2])
        {
            for (j = i * i; j <= N; j += 2 * i)
            {
                isPrime[j / 2] = 0;
            }
        }
    }


    printf("2\n");
    for (int k = 3; k <= N; k += 2)
    {
        if (isPrime[k / 2] == 1)
        {
            printf("%d\n", k);
        }
    }

    /* sieve is complete, count primes */
    int total = N >= 2 ? 1 : 0;
    //#pragma omp parallel for reduction(+:total)
    for (i = 1; i <= memorySize; i++)
    {
        total += isPrime[i];
    }

    return total;
}

int main(void)
{
    //int total = eratosthenesOdd(100, 1);
    int total = eratosthenesOdd(100);
    printf("Number of primes: %d\n", total);
    return 0;
}

这个输出：

2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
Number of primes: 25

通过检查，这对于 100 以内的素数是正确的。

从给定范围内的数字并行程序中查找素数

Find prime numbers from a given range of numbers parallel program

c

parallel-processing

multithreading

for-loop

openmp