本教程依赖两个包含数据争用的程序:
第一个程序查找素数。它是用 C 编写的,是使用 OpenMP 指令并行化的。源文件名为 omp_prime.c。
第二个程序也查找素数,并且也是用 C 编写的。但是, 它是使用 POSIX 线程而不是 OpenMP 指令并行化的。源文件名为 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 }
如 2.1.1 omp_prime.c 的完整列表所述,当代码包含争用情况且不同的运行提供不同的计算结果时,内存访问顺序是不确定的。由于代码中存在数据争用,所以每次执行 omp_prime.c 都会生成不正确且不一致的结果。下面显示了一个输出示例:
% 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
同样,由于 pthr_prime.c 中存在数据争用,所以程序的不同运行可能生成不正确且不一致的结果,如下所示。
% 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