]> git.somenet.org - pub/astra/parallel.git/blob - merge/sort.c
fix runall that it works with hillis_sum
[pub/astra/parallel.git] / 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 }