merge/sort.c

   1 /* implementation of parallel merge sort */
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <unistd.h>
   5 #include <omp.h>
   6 #include "numlist.h"
   7
   8 #ifndef min
   9         #define min( a, b ) ( ((a) < (b)) ? (a) : (b) )
  10 #endif
  11 #ifndef max
  12         #define max( a, b ) ( ((a) > (b)) ? (a) : (b) )
  13 #endif
  14
  15 typedef int numtype;
  16
  17 void printlist(char * message, numtype * ptr, int len);
  18 int rank(int elem, numtype * list, int len);
  19 /* merge(a,n,b,m,c): merges a of size n and b of size m into c */
  20 void merge(int ti, numtype * a, int n, numtype * b, int m, numtype * c);
  21
  22 int main ( int argc, char ** argv) {
  23         int n = LISTSIZE, m = LISTSIZE;
  24         int p = 1;
  25         int opt, i;
  26         int a_len, b_len, b_len_end, b_len_begin;
  27         numtype * c;
  28         double startTime, endTime;
  29
  30         while ((opt = getopt(argc, argv, "t:")) != -1) {
  31                 switch (opt) {
  32                         case 't':
  33                                 p = atoi(optarg);
  34                                 break;
  35                         default: /* '?' */
  36                                 fprintf(stderr, "Usage: %s [-t threads]\n", argv[0]);
  37                                 exit(EXIT_FAILURE);
  38                 }
  39         }
  40
  41         //printf ("Number of processes that will be started: %i\n", p);
  42         //printf ("----------------------------------\n");
  43
  44         c = (numtype *) malloc((LISTSIZE * 2 + 1) * (sizeof (numtype)));
  45         c[LISTSIZE*2] = -1;
  46
  47         //printlist("0 Sorted List A:", a);
  48         //printlist("0 Sorted List B:", b);
  49
  50         startTime = omp_get_wtime();
  51
  52         a_len = n/p;
  53         #pragma omp parallel for shared(a,b,c,n,m,p,a_len) private(i,b_len_begin,b_len_end,b_len)
  54         for (i = 0; i < p; i++) {
  55                 b_len_begin = rank(a[i*a_len], b, m);
  56                 b_len_end = rank(a[(i+1)*a_len], b, m);
  57                 if (b_len_begin < 0) {
  58                         printf ("Insert to end of list!\n");
  59                         b_len_begin = n;
  60                 }
  61                 if (b_len_end < 0) {
  62                         //printf ("Reached end of list!\n");
  63                         b_len_end = n;
  64                 }
  65                 b_len = b_len_end - b_len_begin;
  66                 //printf ("%i a_len: %i, b_len: %i (begin:%i ([%i]) -> end:%i [%i])\n", i+1, a_len, b_len, b_len_begin, b[b_len_begin], b_len_end, b[b_len_end]);
  67                 merge(  i+1,
  68                                 &a[i*a_len],
  69                                 a_len,
  70                                 &b[b_len_begin],
  71                                 b_len,
  72                                 &c[i*a_len+b_len_begin]);
  73         }
  74
  75         endTime = omp_get_wtime();
  76         printf("took %f seconds.\n", endTime-startTime);
  77
  78         //printlist("Sorted List:", c);
  79         free(c);
  80         return 0;
  81 }
  82
  83 void printlist(char * message, numtype * ptr, int len) {
  84         printf (message);
  85         while (len > 0) {
  86                 printf (" %i", *ptr);
  87                 ptr++; len--;
  88         }
  89         printf ("\n");
  90 }
  91
  92 int rank(numtype elem, numtype * list, int len) {
  93         int pos;
  94         int i = len;
  95
  96         pos = 0;
  97         if (elem == -1) { return -1; }
  98         while (i > 0) {
  99                 /*printf ("elem_list: %i %i\n", elem, *list);*/
 100                 if (elem <= *list) {
 101                         return pos;
 102                 }
 103                 list++;
 104                 pos++;
 105                 i--;
 106         }
 107         return len;
 108 }
 109
 110 void merge(int ti, numtype * a, int n, numtype * b, int m, int * c) {
 111         int sum;
 112         int i;
 113         /*printf ("sorting a:%i (%i) and b:%i (%i)\n", *a, n, *b, m);*/
 114         if (m<0) { m=0;}
 115         if (n<0) { n=0;}
 116         sum = n + m;
 117         //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);
 118         for (i = 0; i < sum; i++) {
 119                 // n+m == 0
 120                 if (n <= 0 && m <= 0) {
 121                         printf ("%i Calculation failed somehow...\n", ti);
 122                         return;
 123                 }
 124                 if (n <= 0) {
 125                         c[i] = *b++; m--;
 126                 } else {
 127                         if (m <= 0) {
 128                                 c[i] = *a++; n--;
 129                         } else {
 130                                 if (*a < *b) {
 131                                         c[i] = *a++; n--;
 132                                 } else {
 133                                         c[i] = *b++; m--;
 134                                 }
 135                         }
 136                 }
 137         }
 138         // printf ("merge done, n=%d, m=%d\n", n, m);
 139         return;
 140 }