openmp/merge/sort.c

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