ex2.c (9997B)
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <mpi.h> 4 5 /* Flags */ 6 #define FIND_XMIN 1 << 0 7 #define FIND_XMAX 1 << 1 8 #define COUNT_BELOW_AVG 1 << 2 9 #define COUNT_ABOVE_AVG 1 << 3 10 11 typedef struct { 12 float val; /* Max value in array */ 13 int i; /* Index of max */ 14 } Pair; 15 16 /* Function declarations */ 17 static float input(const char *, int); 18 static float find(int); 19 static float findavg(float *, int); 20 static float calcavg(void); 21 static int count(float, int); 22 static float calcvar(float); 23 static float *calcd(float, float); 24 static Pair findmax(float *); 25 static float *calcpfxsums(void); 26 static void printv(const char *, const float *); 27 static void *emalloc(size_t); 28 29 /* Global variables */ 30 static int rank, nproc, root = 0; 31 static int *scounts, *displs; 32 static float *vec, *localvec; 33 static int n, localn; 34 35 /* Function implementations */ 36 /* Formatted input */ 37 static float 38 input(const char *fmt, int i) 39 { 40 char buf[48]; 41 float n; 42 43 sprintf(buf, fmt, i); 44 printf("%s", buf); 45 scanf("%f", &n); 46 getchar(); 47 48 return n; 49 } 50 51 /* Find `xmin` and `xmax` depending on the `flag` argument. */ 52 static float 53 find(int flag) 54 { 55 float localres = *localvec; 56 float finalres = localres; 57 float *res; 58 int i; 59 60 res = emalloc(nproc * sizeof(float)); 61 /* 62 * Loop through each local vector and assign the local 63 * result depending on which of the two flags is set 64 */ 65 for (i = 0; i < localn; i++) 66 if ((flag & FIND_XMIN && localvec[i] < localres) 67 || (flag & FIND_XMAX && localvec[i] > localres)) 68 localres = localvec[i]; 69 /* Send local results to `root` */ 70 MPI_Gather(&localres, 1, MPI_FLOAT, res, 1, MPI_FLOAT, root, MPI_COMM_WORLD); 71 72 if (rank == root) 73 /* Same process as above */ 74 for (i = 0; i < nproc; i++) 75 if ((flag & FIND_XMIN && res[i] < finalres) 76 || (flag & FIND_XMAX && res[i] > finalres)) 77 finalres = res[i]; 78 79 /* Everyone has to know the final result */ 80 MPI_Bcast(&finalres, 1, MPI_FLOAT, root, MPI_COMM_WORLD); 81 free(res); 82 83 return finalres; 84 } 85 86 /* 87 * Small utility function for `calcavg` to avoid code duplication. 88 * Calcuates the average for a given vector 89 */ 90 static float 91 findavg(float *v, int len) 92 { 93 float sum = 0.0f; 94 int i = 0; 95 96 for (; i < len; i++) 97 sum += v[i]; 98 return (sum / (float)len); 99 } 100 101 /* Calculate the global average */ 102 static float 103 calcavg(void) 104 { 105 float *avgs, localavg, finalavg; 106 107 avgs = emalloc(nproc * sizeof(float)); 108 localavg = findavg(localvec, localn); 109 MPI_Gather(&localavg, 1, MPI_FLOAT, avgs, 1, MPI_FLOAT, root, MPI_COMM_WORLD); 110 111 if (rank == root) 112 finalavg = findavg(avgs, nproc); 113 MPI_Bcast(&finalavg, 1, MPI_FLOAT, root, MPI_COMM_WORLD); 114 free(avgs); 115 116 return finalavg; 117 } 118 119 /* 120 * Count how many elements are below or above average based on the 121 * `flag` argument. Similar logic as with `find` above. 122 */ 123 static int 124 count(float avg, int flag) 125 { 126 int *res, localres = 0, finalres = 0, i; 127 128 res = emalloc(nproc * sizeof(int)); 129 for (i = 0; i < localn; i++) 130 if ((flag & COUNT_BELOW_AVG && localvec[i] < avg) 131 || (flag & COUNT_ABOVE_AVG && localvec[i] > avg)) 132 localres++; 133 MPI_Gather(&localres, 1, MPI_INT, res, 1, MPI_INT, root, MPI_COMM_WORLD); 134 135 if (rank == root) 136 for (i = 0; i < nproc; i++) 137 finalres += res[i]; 138 MPI_Bcast(&finalres, 1, MPI_INT, root, MPI_COMM_WORLD); 139 free(res); 140 141 return finalres; 142 } 143 144 /* Calculate the global variance */ 145 static float 146 calcvar(float avg) 147 { 148 float *vars, localvar = 0.0f, finalvar = 0.0f; 149 int i; 150 151 for (i = 0; i < localn; i++) 152 localvar += (localvec[i] - avg) * (localvec[i] - avg); 153 154 vars = emalloc(nproc * sizeof(float)); 155 MPI_Gather(&localvar, 1, MPI_FLOAT, vars, 1, MPI_FLOAT, root, MPI_COMM_WORLD); 156 157 if (rank == root) { 158 for (i = 0; i < nproc; i++) 159 finalvar += vars[i]; 160 finalvar /= (float)n - 1; 161 } 162 MPI_Bcast(&finalvar, 1, MPI_FLOAT, root, MPI_COMM_WORLD); 163 free(vars); 164 165 return finalvar; 166 } 167 168 /* Generate D. A vector where each element is 169 * ((xi - xmin) / (xmax - xmin)) * 100. 170 */ 171 static float * 172 calcd(float xmin, float xmax) 173 { 174 float *locald, *finald; 175 int i; 176 177 locald = emalloc(localn * sizeof(float)); 178 finald = emalloc(n * sizeof(float)); 179 180 for (i = 0; i < localn; i++) 181 locald[i] = ((localvec[i] - xmin) / (xmax - xmin)) * 100; 182 183 MPI_Gatherv(locald, localn, MPI_FLOAT, finald, scounts, displs, 184 MPI_FLOAT, root, MPI_COMM_WORLD); 185 186 free(locald); 187 188 return finald; 189 } 190 191 /* Find global max and MAXLOC */ 192 static Pair 193 findmax(float *d) 194 { 195 Pair in, out; 196 int i = 1; 197 198 in.val = *d; 199 in.i = 0; 200 for (; i < n; i++) { 201 if (in.val < d[i]) { 202 in.val = d[i]; 203 in.i = i; 204 } 205 } 206 in.i += rank * localn; 207 MPI_Reduce(&in, &out, 1, MPI_FLOAT_INT, MPI_MAXLOC, root, MPI_COMM_WORLD); 208 209 return out; 210 } 211 212 /* Calucate the prefix sums of `vec`. Only world when 213 * n == nproc 214 */ 215 static float * 216 calcpfxsums(void) 217 { 218 float *pfxsums; 219 float sum = 0.0f; 220 221 pfxsums = emalloc(n * sizeof(float)); 222 223 /* Scan each local vector and assign the result to `sum`. */ 224 MPI_Scan(localvec, &sum, 1, MPI_FLOAT, MPI_SUM, MPI_COMM_WORLD); 225 /* Be in sync. */ 226 MPI_Barrier(MPI_COMM_WORLD); 227 /* Get results in `pfxsums` */ 228 MPI_Gather(&sum, 1, MPI_FLOAT, pfxsums, 1, MPI_FLOAT, root, MPI_COMM_WORLD); 229 230 return pfxsums; 231 } 232 233 /* Utility function to print a vector in a prettier way. */ 234 static void 235 printv(const char *str, const float *v) 236 { 237 int i = 0; 238 239 printf("%s [", str); 240 for (; i < n; i++) 241 printf("%.4f%s", v[i], i != n-1 ? ", " : ""); 242 printf("]\n"); 243 } 244 245 /* Error checking `malloc(3)`. */ 246 static void * 247 emalloc(size_t nb) 248 { 249 void *p; 250 251 if ((p = malloc(nb)) == NULL) { 252 fputs("cannot allocate memory", stderr); 253 exit(EXIT_FAILURE); 254 } 255 return p; 256 } 257 258 int 259 main(int argc, char *argv[]) 260 { 261 Pair dmax; 262 float avg, var, xmin, xmax; 263 float *d, *pfxsums; 264 int belowavg, aboveavg; 265 int i, rc; 266 267 if ((rc = MPI_Init(&argc, &argv)) != 0) { 268 fprintf(stderr, "%s: cannot initialize MPI.\n", argv[0]); 269 MPI_Abort(MPI_COMM_WORLD, rc); 270 } 271 MPI_Comm_size(MPI_COMM_WORLD, &nproc); 272 MPI_Comm_rank(MPI_COMM_WORLD, &rank); 273 274 /* Read global vector. */ 275 if (rank == root) { 276 n = input("N: ", 0); 277 vec = emalloc(n * sizeof(float)); 278 for (i = 0; i < n; i++) 279 vec[i] = input("vec[%d]: ", i); 280 } 281 282 /* Send `n` to everyone. */ 283 MPI_Bcast(&n, 1, MPI_INT, root, MPI_COMM_WORLD); 284 285 /* Will be used for `MPI_Scatterv(3)` and `MPI_Gatherv(3)` later on. */ 286 scounts = emalloc(nproc * sizeof(int)); 287 displs = emalloc(nproc * sizeof(int)); 288 for (i = 0; i < nproc; i++) { 289 /* make it work even if `n` is not a multiple of `nproc`. */ 290 scounts[i] = (i != nproc - 1) ? n / nproc : n / nproc + n % nproc; 291 /* take the last `scounts` so that we don't offset +1 each time. */ 292 displs[i] = i * scounts[i != 0 ? i-1 : i]; 293 } 294 295 /* 296 * Each local `n` is the same as the `scounts` of each process, so we 297 * assign it to `localn` for readablity. 298 */ 299 localn = scounts[rank]; 300 localvec = emalloc(localn * sizeof(float)); 301 302 /* Scatter the array to each process. */ 303 MPI_Scatterv(vec, scounts, displs, MPI_FLOAT, localvec, localn, 304 MPI_FLOAT, root, MPI_COMM_WORLD); 305 306 /* Part 0.1 - Calculate global minimum and maximum. */ 307 xmin = find(FIND_XMIN); 308 xmax = find(FIND_XMAX); 309 310 /* Part 0.2 - Calculate average. */ 311 avg = calcavg(); 312 313 /* Part 1 - Find how many elements are above or below average. */ 314 belowavg = count(avg, COUNT_BELOW_AVG); 315 aboveavg = count(avg, COUNT_ABOVE_AVG); 316 317 /* Part 2 - Calculate variance. */ 318 var = calcvar(avg); 319 320 /* Part 3 - Generate D. */ 321 d = calcd(xmin, xmax); 322 323 /* Part 4 - Find dmax and dmaxloc. */ 324 dmax = findmax(d); 325 326 /* Part 5 - Prefix sums of `vec`. */ 327 pfxsums = calcpfxsums(); 328 329 /* Print all results */ 330 if (rank == root) { 331 printf("\n"); 332 printv("X: ", vec); 333 printf("Average: %.4f\n", avg); 334 printf("Xmin: %.4f\n", xmin); 335 printf("Xmax: %.4f\n", xmax); 336 printf("Below Average: %d\n", belowavg); 337 printf("Above Average: %d\n", aboveavg); 338 printf("Variance: %.4f\n", var); 339 printv("D: ", d); 340 printf("Dmax: %.4f\n", dmax.val); 341 printf("Dmaxloc: %d\n", dmax.i); 342 printv("Prefix Sums: ", pfxsums); 343 } 344 345 free(scounts); 346 free(displs); 347 free(vec); 348 free(localvec); 349 free(d); 350 free(pfxsums); 351 352 MPI_Finalize(); 353 354 return 0; 355 }