ex2a.c (2698B)
1 #include <err.h> 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <time.h> 5 6 #include <omp.h> 7 8 static void pretty_print(int *, int, const char *); 9 static int cmpfunc(const void *, const void *); 10 static void merge(int *, int *, int *, int *, int *); 11 static void multisort(int *, int *, int); 12 13 /* 14 * Print the contents of a 2D array like: 15 * 16 * array = [x, y, z] 17 */ 18 static void 19 pretty_print(int *arr, int n, const char *name) 20 { 21 int i; 22 23 printf("\n%s = [", name); 24 for (i = 0; i < n; i++) 25 printf("%d%s", arr[i], (i == n - 1) ? "" : ", "); 26 printf("]\n"); 27 } 28 29 /* 30 * Passed to qsort(3). 31 */ 32 static int 33 cmpfunc(const void *a, const void *b) 34 { 35 return (*(int *)a - *(int *)b); 36 } 37 38 static void 39 merge(int *a, int *enda, int *b, int *endb, int *res) 40 { 41 while (a <= enda && b <= endb) { 42 if (*a < *b) 43 *res++ = *a++; 44 else 45 *res++ = *b++; 46 } 47 while (a <= enda) 48 *res++ = *a++; 49 while (b <= endb) 50 *res++ = *b++; 51 } 52 53 static void 54 multisort(int *arr, int *space, int n) 55 { 56 int quarter, *sta, *spa, *stb, *spb, *stc, *spc, *std, *spd; 57 58 if ((quarter = n / 4) < 4) 59 qsort(arr, n, sizeof(int), cmpfunc); 60 else { 61 /* Split the array into 4 quarters. */ 62 sta = arr; 63 spa = space; 64 stb = sta + quarter; 65 spb = spa + quarter; 66 stc = stb + quarter; 67 spc = spb + quarter; 68 std = stc + quarter; 69 spd = spc + quarter; 70 #pragma omp task 71 multisort(sta, spa, quarter); 72 #pragma omp task 73 multisort(stb, spb, quarter); 74 #pragma omp task 75 multisort(stc, spc, quarter); 76 #pragma omp task 77 multisort(std, spd, n - 3 * quarter); 78 /* Wait for the tasks above to finish. */ 79 #pragma omp taskwait 80 #pragma omp task 81 /* Merge A and B into SpaceA */ 82 merge(sta, sta + quarter - 1, stb, stb + quarter - 1, spa); 83 #pragma omp task 84 /* Merge C and D into SpaceC */ 85 merge(stc, stc + quarter - 1, std, arr + n - 1, spc); 86 #pragma omp taskwait 87 /* Merge the two resulting couples (SpaceA and SpaceC). */ 88 merge(spa, spc - 1, spc, space + n - 1, arr); 89 } 90 } 91 92 int 93 main(int argc, char *argv[]) 94 { 95 int *a, *space, i, n, ntd; 96 double start, end; 97 98 99 if (argc < 3) { 100 fprintf(stderr, "usage: %s nthreads n\n", getprogname()); 101 return (1); 102 } 103 if ((ntd = atoi(argv[1])) < 1) 104 err(1, "can't use nthreads n < 1"); 105 if ((n = atoi(argv[2])) < 1) 106 err(1, "can't use n < 1"); 107 108 srand(time(NULL)); 109 omp_set_num_threads(ntd); 110 111 if ((a = malloc(n * sizeof(int))) == NULL) 112 err(1, "malloc"); 113 if ((space = malloc(n * sizeof(int))) == NULL) 114 err(1, "malloc"); 115 for (i = 0; i < n; i++) 116 a[i] = rand() % 100; 117 118 start = omp_get_wtime(); 119 120 pretty_print(a, n, "A_unsorted"); 121 multisort(a, space, n); 122 pretty_print(a, n, "A_multisort"); 123 124 end = omp_get_wtime(); 125 printf("Total time: %f seconds\n", end - start); 126 127 free(a); 128 129 return (0); 130 }