This tutorial relies on two programs, both of which contain data races:
The first program finds prime numbers. It is written with C and is parallelized with OpenMP directives. The source file is called omp_prime.c.
The second program also finds prime number and is also written with C. However, it is parallelized with POSIX threads instead of OpenMP directives. The source file is called pthr_prime.c.
1 #include <stdio.h> 2 #include <math.h> 3 #include <omp.h> 4 5 #define THREADS 4 6 #define N 3000 7 8 int primes[N]; 9 int pflag[N]; 10 11 int is_prime(int v) 12 { 13 int i; 14 int bound = floor(sqrt ((double)v)) + 1; 15 16 for (i = 2; i < bound; i++) { 17 /* No need to check against known composites */ 18 if (!pflag[i]) 19 continue; 20 if (v % i == 0) { 21 pflag[v] = 0; 22 return 0; 23 } 24 } 25 return (v > 1); 26 } 27 28 int main(int argn, char **argv) 29 { 30 int i; 31 int total = 0; 32 33 #ifdef _OPENMP 34 omp_set_num_threads(THREADS); 35 omp_set_dynamic(0); 36 #endif 37 38 for (i = 0; i < N; i++) { 39 pflag[i] = 1; 40 } 41 42 #pragma omp parallel for 43 for (i = 2; i < N; i++) { 44 if ( is_prime(i) ) { 45 primes[total] = i; 46 total++; 47 } 48 } 49 printf("Number of prime numbers between 2 and %d: %d\n", 50 N, total); 51 for (i = 0; i < total; i++) { 52 printf("%d\n", primes[i]); 53 } 54 55 return 0; 56 }
1 #include <stdio.h> 2 #include <math.h> 3 #include <pthread.h> 4 5 #define THREADS 4 6 #define N 3000 7 8 int primes[N]; 9 int pflag[N]; 10 int total = 0; 11 12 int is_prime(int v) 13 { 14 int i; 15 int bound = floor(sqrt ((double)v)) + 1; 16 17 for (i = 2; i < bound; i++) { 18 /* No need to check against known composites */ 19 if (!pflag[i]) 20 continue; 21 if (v % i == 0) { 22 pflag[v] = 0; 23 return 0; 24 } 25 } 26 return (v > 1); 27 } 28 29 void *work(void *arg) 30 { 31 int start; 32 int end; 33 int i; 34 35 start = (N/THREADS) * (*(int *)arg) ; 36 end = start + N/THREADS; 37 for (i = start; i < end; i++) { 38 if ( is_prime(i) ) { 39 primes[total] = i; 40 total++; 41 } 42 } 43 return NULL; 44 } 45 46 int main(int argn, char **argv) 47 { 48 int i; 49 pthread_t tids[THREADS-1]; 50 51 for (i = 0; i < N; i++) { 52 pflag[i] = 1; 53 } 54 55 for (i = 0; i < THREADS-1; i++) { 56 pthread_create(&tids[i], NULL, work, (void *)&i); 57 } 58 59 i = THREADS-1; 60 work((void *)&i); 61 62 printf("Number of prime numbers between 2 and %d: %d\n", 63 N, total); 64 for (i = 0; i < total; i++) { 65 printf("%d\n", primes[i]); 66 } 67 68 return 0; 69 }
As noted in the2.1.1 Complete Listing of omp_prime.c, the order of memory accesses is non-deterministic when code contains a race condition and the computation gives different results from run to run. Each execution of omp_prime.c produces incorrect and inconsistent results because of the data races in the code. An example of the output is shown below:
% cc -xopenmp=noopt omp_prime.c -lm % a.out | sort -n 0 0 0 0 0 0 0 Number of prime numbers between 2 and 3000: 336 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 ... 2971 2999 % a.out | sort -n 0 0 0 0 0 0 0 0 0 Number of prime numbers between 2 and 3000: 325 3 5 7 13 17 19 23 29 31 41 43 47 61 67 71 73 79 83 89 101 ... 2971 2999
Similarly, as a result of data-races in pthr_prime.c, different runs of the program may produce incorrect and inconsistent results as shown below.
% cc pthr_prime.c -lm -mt % a.out | sort -n Number of prime numbers between 2 and 3000: 304 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 ... 2999 2999 % a.out | sort -n Number of prime numbers between 2 and 3000: 314 751 757 761 769 773 787 797 809 811 821 823 827 839 853 859 877 881 883 907 911 ... 2999 2999