1 /* implementation of parallel merge sort */
10 void printlist(char * message, numtype * ptr, int len);
11 int rank(int elem, numtype * list, int len);
12 /* merge(a,n,b,m,c): merges a of size n and b of size m into c */
13 void merge(int ti, numtype * a, int n, numtype * b, int m, numtype * c);
15 int main ( int argc, char ** argv) {
16 int n = LISTSIZE, m = LISTSIZE;
19 int a_len, b_len, b_len_end, b_len_begin;
21 double startTime, endTime;
23 while ((opt = getopt(argc, argv, "t:")) != -1) {
29 fprintf(stderr, "Usage: %s [-t threads]\n", argv[0]);
34 //printf ("Maximal number of threads: %i\n", omp_get_max_threads());
35 //printf ("----------------------------------\n");
37 c = (numtype *) malloc((LISTSIZE * 2 + 1) * (sizeof (numtype)));
40 //printlist("0 Sorted List A:", a);
41 //printlist("0 Sorted List B:", b);
43 startTime = omp_get_wtime();
46 #pragma omp parallel for shared(a,b,c,n,m,p,a_len) private(i,b_len_begin,b_len_end,b_len)
47 for (i = 0; i < p; i++) {
48 b_len_begin = rank(a[i*a_len], b, m);
49 b_len_end = rank(a[(i+1)*a_len], b, m);
50 if (b_len_begin < 0) {
51 printf ("Insert to end of list!\n");
55 //printf ("Reached end of list!\n");
58 b_len = b_len_end - b_len_begin;
59 //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]);
65 &c[i*a_len+b_len_begin]);
68 endTime = omp_get_wtime();
69 printf("took %f seconds.\n", endTime-startTime);
71 //printlist("Sorted List:", c);
76 void printlist(char * message, numtype * ptr, int len) {
85 int rank(numtype elem, numtype * list, int len) {
90 if (elem == -1) { return -1; }
92 /*printf ("elem_list: %i %i\n", elem, *list);*/
103 void merge(int ti, numtype * a, int n, numtype * b, int m, int * c) {
106 /*printf ("sorting a:%i (%i) and b:%i (%i)\n", *a, n, *b, m);*/
110 //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);
111 for (i = 0; i < sum; i++) {
113 if (n <= 0 && m <= 0) {
114 printf ("%i Calculation failed somehow...\n", ti);
131 // printf ("merge done, n=%d, m=%d\n", n, m);