uni

University stuff
git clone git://git.margiolis.net/uni.git
Log | Files | Refs | README | LICENSE

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 }