ex2a.c (2851B)
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 an 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 /* 39 * Merge sort 40 */ 41 static void 42 merge(int *a, int *enda, int *b, int *endb, int *res) 43 { 44 while (a <= enda && b <= endb) { 45 if (*a < *b) 46 *res++ = *a++; 47 else 48 *res++ = *b++; 49 } 50 while (a <= enda) 51 *res++ = *a++; 52 while (b <= endb) 53 *res++ = *b++; 54 } 55 56 static void 57 multisort(int *arr, int *space, int n) 58 { 59 int quarter, *sta, *spa, *stb, *spb, *stc, *spc, *std, *spd; 60 61 /* 62 * Sort with qsort(3) directly if we can't split the array into 4 63 * quarters. 64 */ 65 if ((quarter = n / 4) < 4) 66 qsort(arr, n, sizeof(int), cmpfunc); 67 else { 68 /* Split the array into 4 quarters. */ 69 sta = arr; 70 spa = space; 71 stb = sta + quarter; 72 spb = spa + quarter; 73 stc = stb + quarter; 74 spc = spb + quarter; 75 std = stc + quarter; 76 spd = spc + quarter; 77 /* Sort each quarter */ 78 #pragma omp task 79 multisort(sta, spa, quarter); 80 #pragma omp task 81 multisort(stb, spb, quarter); 82 #pragma omp task 83 multisort(stc, spc, quarter); 84 #pragma omp task 85 multisort(std, spd, n - 3 * quarter); 86 /* Wait for the tasks above to finish. */ 87 #pragma omp taskwait 88 #pragma omp task 89 /* Merge A and B into SpaceA */ 90 merge(sta, sta + quarter - 1, stb, stb + quarter - 1, spa); 91 #pragma omp task 92 /* Merge C and D into SpaceC */ 93 merge(stc, stc + quarter - 1, std, arr + n - 1, spc); 94 #pragma omp taskwait 95 /* Merge the two resulting couples (SpaceA and SpaceC). */ 96 merge(spa, spc - 1, spc, space + n - 1, arr); 97 } 98 } 99 100 int 101 main(int argc, char *argv[]) 102 { 103 int *a, *space, i, n, ntd; 104 double start, end; 105 106 107 if (argc < 3) { 108 fprintf(stderr, "usage: %s nthreads n\n", *argv); 109 return (1); 110 } 111 if ((ntd = atoi(argv[1])) < 1) 112 err(1, "can't use nthreads n < 1"); 113 if ((n = atoi(argv[2])) < 1) 114 err(1, "can't use n < 1"); 115 116 srand(time(NULL)); 117 omp_set_num_threads(ntd); 118 119 if ((a = malloc(n * sizeof(int))) == NULL) 120 err(1, "malloc"); 121 if ((space = malloc(n * sizeof(int))) == NULL) 122 err(1, "malloc"); 123 for (i = 0; i < n; i++) 124 a[i] = rand() % 100; 125 126 /* Calculate speed up */ 127 start = omp_get_wtime(); 128 129 pretty_print(a, n, "A_unsorted"); 130 multisort(a, space, n); 131 pretty_print(a, n, "A_multisort"); 132 133 end = omp_get_wtime(); 134 printf("Total time: %f seconds\n", end - start); 135 136 free(a); 137 138 return (0); 139 }