2.1 Tutorial Source Files

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.

2.1.1 Complete Listing of omp_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  } 

2.1.2 Complete Listing of pthr_prime.c

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  } 

2.1.2.1 Data Races in omp_prime.c and pthr_prime.c

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