merge/sort.c

   1 /* implementation of parallel merge sort */
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <unistd.h>
   5 #include <limits.h>
   6 #include <omp.h>
   7 #include "numlist.h"
   8
   9 #ifndef min
  10         #define min( a, b ) ( ((a) < (b)) ? (a) : (b) )
  11 #endif
  12 #ifndef max
  13         #define max( a, b ) ( ((a) > (b)) ? (a) : (b) )
  14 #endif
  15
  16 typedef int numtype;
  17
  18 void printlist(char * message, numtype * ptr, int len);
  19 int rank(int elem, numtype * list, int len);
  20 /* merge(a,n,b,m,c): merges a of size n and b of size m into c */
  21 void merge(int ti, numtype * a, int n, numtype * b, int m, numtype * c);
  22
  23 int main ( int argc, char ** argv) {
  24         int n = LISTSIZEA, m = LISTSIZEB;
  25         int p = 1;
  26         int opt, i;
  27         int block, b_len, b_len_begin, b_len_end;
  28         numtype * c;
  29         double startTime, endTime;
  30
  31         while ((opt = getopt(argc, argv, "t:")) != -1) {
  32                 switch (opt) {
  33                         case 't':
  34                                 p = atoi(optarg);
  35                                 break;
  36                         default: /* '?' */
  37                                 fprintf(stderr, "Usage: %s [-t threads]\n", argv[0]);
  38                                 exit(EXIT_FAILURE);
  39                 }
  40         }
  41
  42         if (p > LISTSIZEA) {
  43                 printf ("Zu viele Aufteilungen!\n");
  44                 exit(1);
  45         }
  46         if (((int)(LISTSIZEA/p))*p != LISTSIZEA) {
  47                 printf ("Liste ist nicht teilbar durch %i\n", p);
  48                 exit(1);
  49         }
  50
  51 #ifdef DEBUG
  52         printf ("Number of processes that will be started: %i\n", p);
  53         printf ("----------------------------------\n");
  54 #endif
  55
  56         c = (numtype *) malloc((LISTSIZEA+LISTSIZEB) * (sizeof (numtype)));
  57         for (i = 0; i < (LISTSIZEA+LISTSIZEB); i++) {
  58                 c[i] = 0;
  59         }
  60
  61 #ifdef DEBUG
  62         printlist("0 Sorted List A:", a, LISTSIZEA);
  63         printlist("0 Sorted List B:", b, LISTSIZEB);
  64 #endif
  65
  66         startTime = omp_get_wtime();
  67
  68         block = n/p;
  69         #pragma omp parallel for shared(a,b,c,n,m,p,block) private(i,b_len,b_len_begin,b_len_end)
  70         for (i = 0; i < p; i++) {
  71                 b_len_begin = rank(a[i*block],b,m);
  72                 b_len_end = rank(a[(i+1)*block],b,m);
  73                 b_len = b_len_end - b_len_begin;
  74                 if (i == p-1) { b_len = m-b_len_begin; }
  75 #ifdef DEBUG
  76                 //printf ("b_len_begin: %i, b_len_end: %i, b_len: %i\n", b_len_begin, b_len_end, b_len);
  77 #endif
  78
  79                 merge(i+1,
  80                                 &a[i*block],
  81                                 block,
  82                                 &b[b_len_begin],
  83                                 b_len,
  84                                 &c[i*block+b_len_begin]
  85                                 );
  86         }
  87
  88         endTime = omp_get_wtime();
  89         printf("took %f seconds.\n", endTime-startTime);
  90
  91 #ifdef DEBUG
  92         printlist("Sorted List:", c, LISTSIZEA+LISTSIZEB);
  93         printf ("------------\n");
  94         merge(9, a, n, b, m, c);
  95         printlist("Should Be:  ", c, LISTSIZEA+LISTSIZEB);
  96 #endif
  97         //free(c);
  98         return 0;
  99 }
 100
 101 void printlist(char * message, numtype * ptr, int len) {
 102         printf (message);
 103         while (len > 0) {
 104                 printf (" %i", *ptr);
 105                 ptr++; len--;
 106         }
 107         printf ("\n");
 108 }
 109
 110 /*
 111  * return -1 if len == 0
 112  * return pos if elem is to be placed before *list
 113  * return len if elem has to be positioned after list
 114  */
 115 int rank(numtype elem, numtype * list, int len) {
 116         int pos;
 117         int i = len;
 118         pos = 0;
 119         if (len == 0) { return -1; }
 120         while (i > 0) {
 121                 /*printf ("rank: %i %i\n", elem, *list);*/
 122                 if (elem <= *list) {
 123                         return pos;
 124                 }
 125                 list++;
 126                 pos++;
 127                 i--;
 128         }
 129         return len;
 130 }
 131
 132 void merge(int ti, numtype * a, int n, numtype * b, int m, int * c) {
 133         int sum;
 134         int i;
 135 #ifdef DEBUG
 136         //printf ("sorting a:%i (%i) and b:%i (%i)\n", *a, n, *b, m);
 137         //printlist("sortinglista", a, n);
 138         //printlist("sortinglistb", b, m);
 139 #endif
 140         if (m<0) { m=0;}
 141         if (n<0) { n=0;}
 142         sum = n + m;
 143 #ifdef DEBUG
 144         //printf ("%i modifying %i (%i+%i) (c[%i]/0x%08x -> c[%i]/0x%08x)\n", ti, sum, n, m, 0, (unsigned int) &c, sum-1, ((unsigned int) &c)+sum);
 145 #endif
 146         for (i = 0; i < sum; i++) {
 147                 // n+m == 0
 148                 if (n <= 0 && m <= 0) {
 149                         printf ("%i Calculation failed somehow...\n", ti);
 150                         return;
 151                 }
 152                 if (n <= 0) {
 153                         //printf ("changing: c[%i] from %i to %i\n", i, c[i], *b);
 154                         c[i] = *b++; m--;
 155                 } else {
 156                         if (m <= 0) {
 157                                 //printf ("changing: c[%i] from %i to %i\n", i, c[i], *a);
 158                                 c[i] = *a++; n--;
 159                         } else {
 160                                 if (*a < *b) {
 161                                         //printf ("changing: c[%i] from %i to %i\n", i, c[i], *a);
 162                                         c[i] = *a++; n--;
 163                                 } else {
 164                                         //printf ("changing: c[%i] from %i to %i\n", i, c[i], *b);
 165                                         c[i] = *b++; m--;
 166                                 }
 167                         }
 168                 }
 169         }
 170 #ifdef DEBUG
 171         //printf ("merge done, n=%d, m=%d\n", n, m);
 172 #endif
 173         return;
 174 }