ex1.c (3537B)
1 #include <err.h> 2 #include <stdarg.h> 3 #include <stdio.h> 4 #include <stdlib.h> 5 6 #include <omp.h> 7 8 #define abs(x) ((x) < 0 ? -(x) : (x)) 9 10 static void *emalloc(size_t); 11 static int safe_input(const char *, ...); 12 static void pretty_print(int **, int, const char *); 13 static int strictly_diagonal_dominant(int **, int); 14 static int diagonal_max(int **, int); 15 static int **new_array(int **, int, int); 16 static int calc_min(int **, int); 17 18 /* 19 * Fail-safe malloc(3). 20 */ 21 static void * 22 emalloc(size_t nb) 23 { 24 void *p; 25 26 if ((p = malloc(nb)) == NULL) 27 err(1, "malloc"); 28 29 return (p); 30 } 31 32 static int 33 safe_input(const char *fmt, ...) 34 { 35 va_list args; 36 char buf[48]; 37 int n, rc; 38 39 /* Collect the arguments into a buffer. */ 40 va_start(args, fmt); 41 vsnprintf(buf, sizeof(buf), fmt, args); 42 va_end(args); 43 44 /* 45 * The following loop keeps asking for input as long as the current 46 * input wasn't correct. In this case "incorrect" input means anything 47 * other than digits. 48 */ 49 do { 50 printf("\r%s", buf); 51 rc = scanf("%d", &n); 52 (void)getchar(); 53 } while (rc != 1); 54 55 return (n); 56 } 57 58 /* 59 * Print the contents of a 2D array like: 60 * 61 * array = [ 62 * [x, y, z] 63 * [x, y, z] 64 * ] 65 */ 66 static void 67 pretty_print(int **arr, int n, const char *name) 68 { 69 int i, j; 70 71 printf("\n%s = [\n", name); 72 for (i = 0; i < n; i++) { 73 printf("\t["); 74 for (j = 0; j < n; j++) { 75 printf("%d%s", arr[i][j], 76 (j == n - 1) ? "]\n" : ", "); 77 } 78 } 79 printf("]\n"); 80 } 81 82 static int 83 strictly_diagonal_dominant(int **a, int n) 84 { 85 int i, j, sum, flag = 1; 86 87 #pragma omp parallel for 88 for (i = 0; i < n; i++) { 89 for (j = 0; j < n; j++) { 90 if (i == j) 91 continue; 92 sum += abs(a[i][j]); 93 } 94 if (abs(a[i][i]) <= sum) 95 flag = 0; 96 } 97 98 return (flag); 99 } 100 101 static int 102 diagonal_max(int **a, int n) 103 { 104 int i, max; 105 106 max = a[0][0]; 107 #pragma omp parallel for reduction(max : max) 108 for (i = 0; i < n; i++) { 109 if (abs(a[i][i]) > max) 110 max = a[i][i]; 111 } 112 113 return (max); 114 } 115 116 static int ** 117 new_array(int **a, int m, int n) 118 { 119 int **b, i, j; 120 121 b = emalloc(n * sizeof(int *)); 122 #pragma omp parallel for 123 for (i = 0; i < n; i++) { 124 b[i] = emalloc(n * sizeof(int)); 125 for (j = 0; j < n; j++) 126 b[i][j] = m - a[i][j]; 127 } 128 129 return (b); 130 } 131 132 static int 133 calc_min(int **b, int n) 134 { 135 int i, j, min; 136 137 /* with reduction */ 138 min = b[0][0]; 139 #pragma omp parallel for reduction(min : min) 140 for (i = 0; i < n; i++) { 141 for (j = 0; j < n; j++) { 142 if (b[i][j] < min) 143 min = b[i][j]; 144 } 145 } 146 147 /* without reduction, with critical region protection */ 148 min = b[0][0]; 149 #pragma omp parallel for private(i, j) shared(min) 150 for (i = 0; i < n; i++) { 151 for (j = 0; j < n; j++) { 152 #pragma omp critical 153 { 154 if (b[i][j] < min) 155 min = b[i][j]; 156 } 157 } 158 } 159 160 /* XXX: didn't implement binary tree method */ 161 162 return (min); 163 } 164 165 int 166 main(int argc, char *argv[]) 167 { 168 int **a, **b; 169 int i, j, m, min, n, ntd; 170 double start, end; 171 172 ntd = safe_input("threads: ", 0); 173 omp_set_num_threads(ntd); 174 175 n = safe_input("n: ", 0); 176 a = emalloc(n * sizeof(int *)); 177 for (i = 0; i < n; i++) { 178 a[i] = emalloc(n * sizeof(int)); 179 for (j = 0; j < n; j++) 180 a[i][j] = safe_input("a[%d][%d]: ", i, j); 181 } 182 183 start = omp_get_wtime(); 184 185 if (strictly_diagonal_dominant(a, n)) { 186 m = diagonal_max(a, n); 187 b = new_array(a, m, n); 188 min = calc_min(b, n); 189 190 pretty_print(a, n, "A"); 191 pretty_print(b, n, "B"); 192 printf("Diagonal max: %d\n", m); 193 printf("Min: %d\n", min); 194 195 free(b); 196 } else 197 printf("not strictly diagonal dominant\n"); 198 199 end = omp_get_wtime(); 200 printf("Total time: %f seconds\n", end - start); 201 202 free(a); 203 204 return (0); 205 }