1 /* implementation of parallel merge sort */
10 #define min( a, b ) ( ((a) < (b)) ? (a) : (b) )
13 #define max( a, b ) ( ((a) > (b)) ? (a) : (b) )
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);
23 int main ( int argc, char ** argv) {
24 int n = LISTSIZEA, m = LISTSIZEB;
27 int block, b_len, b_len_begin, b_len_end;
29 double startTime, endTime;
31 while ((opt = getopt(argc, argv, "t:")) != -1) {
37 fprintf(stderr, "Usage: %s [-t threads]\n", argv[0]);
43 printf ("Zu viele Aufteilungen!\n");
46 if (((int)(LISTSIZEA/p))*p != LISTSIZEA) {
47 printf ("Liste ist nicht teilbar durch %i\n", p);
52 printf ("Number of processes that will be started: %i\n", p);
53 printf ("----------------------------------\n");
56 c = (numtype *) malloc((LISTSIZEA+LISTSIZEB) * (sizeof (numtype)));
57 for (i = 0; i < (LISTSIZEA+LISTSIZEB); i++) {
62 printlist("0 Sorted List A:", a, LISTSIZEA);
63 printlist("0 Sorted List B:", b, LISTSIZEB);
66 startTime = omp_get_wtime();
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; }
76 //printf ("b_len_begin: %i, b_len_end: %i, b_len: %i\n", b_len_begin, b_len_end, b_len);
84 &c[i*block+b_len_begin]
88 endTime = omp_get_wtime();
89 printf("took %f seconds.\n", endTime-startTime);
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);
101 void printlist(char * message, numtype * ptr, int len) {
104 printf (" %i", *ptr);
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
115 int rank(numtype elem, numtype * list, int len) {
119 if (len == 0) { return -1; }
121 /*printf ("rank: %i %i\n", elem, *list);*/
132 void merge(int ti, numtype * a, int n, numtype * b, int m, int * c) {
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);
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);
146 for (i = 0; i < sum; i++) {
148 if (n <= 0 && m <= 0) {
149 printf ("%i Calculation failed somehow...\n", ti);
153 //printf ("changing: c[%i] from %i to %i\n", i, c[i], *b);
157 //printf ("changing: c[%i] from %i to %i\n", i, c[i], *a);
161 //printf ("changing: c[%i] from %i to %i\n", i, c[i], *a);
164 //printf ("changing: c[%i] from %i to %i\n", i, c[i], *b);
171 //printf ("merge done, n=%d, m=%d\n", n, m);