parallelizing c code using openmp

Question

I am trying to make the following program parallel using OpenMP :

#include <time.h> // Program computes the total number of primes larger than 100000001 and smaller than 16000001. main() { int number = 100000001; int primes[20]; int i, j, is_prime, index = 0, nprimes = 0; time_t start_time, end_time; start_time = time(NULL); for (i = 0; i < 3000000; i++) { // get the next number to check if it is a prime number += 2; is_prime = 1; for (j = 2; j < 10001; j++) { if ((number % j) == 0) { is_prime = 0; break; } } // f0und a prime number. Count it and save the first 20 primes if (is_prime) nprimes++; if (is_prime && (index < 20)) { primes[index] = number; index++; } } for (i = 0; i < 20; i++) printf("%d is prime\n", primes[i]); end_time = time(NULL); printf("number of primes = %d, elapsed time is %d seconds\n", nprimes, end_time - start_time); }

What I have done is this:

#include <stdio.h> #include <time.h> #include <omp.h> #define CHUNKSIZE 750000 //#define CHUNKSIZE2 2500 // Program computes the total number of primes larger than 100000001 and smaller than 16000001. int main() { int number = 100000001; int primes[20]; int i, j, is_prime, index = 0, nprimes = 0; time_t start_time, end_time; start_time = time(NULL); int chunk = CHUNKSIZE; //int chunk2 = CHUNKSIZE2; #pragma omp parallel shared(number, index, nprimes, chunk) private(i, j, is_prime) { #pragma omp parallel for schedule (dynamic, chunk) for (i = 0; i < 3000000; i++) { // get the next number to check if it is a prime number += 2; is_prime = 1; //#pragma omp parallel for schedule (dynamic, chunk2) for (j = 2; j < 10001; j++) { if ((number % j) == 0) { is_prime = 0; break; } } // f0und a prime number. Count it and save the first 20 primes if (is_prime) nprimes++; if (is_prime && (index < 20)) { primes[index] = number; index++; } } for (i = 0; i < 20; i++) printf("%d is prime\n", primes[i]); end_time = time(NULL); printf("number of primes = %d, elapsed time is %d seconds\n", nprimes, end_time - start_time); //return 0; }

I have tried many things but most of them gave me longer or same time !!!

damienfrancois · Accepted Answer · 2013-10-17 19:54:34Z

The number variable is incremented globally and hence creates a barrier; no computation can be done in parallel, each thread must wait for the previous one to end so that the number+=2 part is consistent.

You can circumvent this by creating another, thread-specific variable (here n) whose value is based on the loop index (i)

One pragma omp parallel for is sufficient:

#include <stdio.h> #include <time.h> #include <omp.h> #define CHUNKSIZE 750000 //#define CHUNKSIZE2 2500 // Program computes the total number of primes larger than 100000001 and smaller than 16000001. int main() { int number = 100000001; int n; int primes[20]; int i, j, is_prime, index = 0, nprimes = 0; time_t start_time, end_time; start_time = time(NULL); int chunk = CHUNKSIZE; //int chunk2 = CHUNKSIZE2; #pragma omp parallel for private(n, is_prime, j) for (i = 0; i < 300000; i++) { // get the next number to check if it is a prime //number += 2; n = number + i*2; is_prime = 1; //#pragma omp parallel for schedule (dynamic, chunk2) for (j = 2; j < 10001; j++) { if ((n % j) == 0) { is_prime = 0; break; } } // f0und a prime number. Count it and save the first 20 primes if (is_prime) nprimes++; if (is_prime && (index < 20)) { primes[index] = n; index++; } } for (i = 0; i < 20; i++) printf("%d is prime\n", primes[i]); end_time = time(NULL); printf("number of primes = %d, elapsed time is %d seconds\n", nprimes, end_time - start_time); //return 0; }

Result with gcc and a trimmed-down computations to avoid waiting too much:

$ gcc -fopenmp -o tt tt.c $ time OMP_NUM_THREADS=1 ./tt 100000007 is prime [...] 100000393 is prime number of primes = 326390, elapsed time is 21 seconds real 0m20.507s user 0m20.492s sys 0m0.001s $ time OMP_NUM_THREADS=8 ./tt 101500027 is prime [...] 105250049 is prime number of primes = 325580, elapsed time is 3 seconds real 0m3.041s user 0m24.284s sys 0m0.002s

Collectives™ on Stack Overflow

parallelizing c code using openmp

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related