From d01d92e72f948d29243a91d6fdc51228bb74a1ca Mon Sep 17 00:00:00 2001 From: David Kaufmann Date: Mon, 30 Jan 2012 15:10:27 +0100 Subject: [PATCH] update merge --- merge/Makefile | 2 +- merge/generate_random.sh | 5 +- merge/sort.c | 98 +++++++++++++++++++++++++++------------- 3 files changed, 70 insertions(+), 35 deletions(-) diff --git a/merge/Makefile b/merge/Makefile index a442cb4..a722ecd 100644 --- a/merge/Makefile +++ b/merge/Makefile @@ -1,7 +1,7 @@ # GCC Makefile CC = gcc -CFLAGS = -pedantic -Wall -g -fopenmp -O0 --std=c99 -D_XOPEN_SOURCE +CFLAGS = -pedantic -Wall -g -fopenmp -O0 --std=c99 -D_XOPEN_SOURCE ${MYFLAGS} LDFLAGS = -fopenmp BINARIES = sort diff --git a/merge/generate_random.sh b/merge/generate_random.sh index cc88cb5..2554aa4 100755 --- a/merge/generate_random.sh +++ b/merge/generate_random.sh @@ -8,7 +8,7 @@ function pwait() { } # 10 ^ x values -X=7 +X=4 NULLEN="" PUNKTE="." for i in $(seq `expr $X - 1`); @@ -51,7 +51,8 @@ pwait rm -f unsorted1 unsorted2 rm -f numlist.h -echo "#define LISTSIZE ${VALUES}" >> numlist.h +echo "#define LISTSIZEA ${VALUES}" >> numlist.h +echo "#define LISTSIZEB ${VALUES}" >> numlist.h echo "extern int a["`expr ${VALUES} + 1`"];" >> numlist.h echo "extern int b["`expr ${VALUES} + 1`"];" >> numlist.h diff --git a/merge/sort.c b/merge/sort.c index 5e8c053..aae6c4a 100644 --- a/merge/sort.c +++ b/merge/sort.c @@ -2,6 +2,7 @@ #include #include #include +#include #include #include "numlist.h" @@ -20,10 +21,10 @@ int rank(int elem, numtype * list, int len); void merge(int ti, numtype * a, int n, numtype * b, int m, numtype * c); int main ( int argc, char ** argv) { - int n = LISTSIZE, m = LISTSIZE; + int n = LISTSIZEA, m = LISTSIZEB; int p = 1; int opt, i; - int a_len, b_len, b_len_end, b_len_begin; + int block, b_len, b_len_begin, b_len_end; numtype * c; double startTime, endTime; @@ -38,45 +39,62 @@ int main ( int argc, char ** argv) { } } - //printf ("Number of processes that will be started: %i\n", p); - //printf ("----------------------------------\n"); + if (p > LISTSIZEA) { + printf ("Zu viele Aufteilungen!\n"); + exit(1); + } + if (((int)(LISTSIZEA/p))*p != LISTSIZEA) { + printf ("Liste ist nicht teilbar durch %i\n", p); + exit(1); + } + +#ifdef DEBUG + printf ("Number of processes that will be started: %i\n", p); + printf ("----------------------------------\n"); +#endif - c = (numtype *) malloc((LISTSIZE * 2 + 1) * (sizeof (numtype))); - c[LISTSIZE*2] = -1; + c = (numtype *) malloc((LISTSIZEA+LISTSIZEB) * (sizeof (numtype))); + for (i = 0; i < (LISTSIZEA+LISTSIZEB); i++) { + c[i] = 0; + } - //printlist("0 Sorted List A:", a); - //printlist("0 Sorted List B:", b); +#ifdef DEBUG + printlist("0 Sorted List A:", a, LISTSIZEA); + printlist("0 Sorted List B:", b, LISTSIZEB); +#endif startTime = omp_get_wtime(); - a_len = n/p; - #pragma omp parallel for shared(a,b,c,n,m,p,a_len) private(i,b_len_begin,b_len_end,b_len) + block = n/p; + //#pragma omp parallel for shared(a,b,c,n,m,p,block) private(i,b_len,b_len_begin,b_len_end) for (i = 0; i < p; i++) { - b_len_begin = rank(a[i*a_len], b, m); - b_len_end = rank(a[(i+1)*a_len], b, m); - if (b_len_begin < 0) { - printf ("Insert to end of list!\n"); - b_len_begin = n; - } - if (b_len_end < 0) { - //printf ("Reached end of list!\n"); - b_len_end = n; - } + b_len_begin = rank(a[i*block],b,m); + b_len_end = rank(a[(i+1)*block],b,m); b_len = b_len_end - b_len_begin; - //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]); - merge( i+1, - &a[i*a_len], - a_len, + if (i == p-1) { b_len = m-b_len_begin; } +#ifdef DEBUG + //printf ("b_len_begin: %i, b_len_end: %i, b_len: %i\n", b_len_begin, b_len_end, b_len); +#endif + + merge(i+1, + &a[i*block], + block, &b[b_len_begin], b_len, - &c[i*a_len+b_len_begin]); + &c[i*block+b_len_begin] + ); } endTime = omp_get_wtime(); printf("took %f seconds.\n", endTime-startTime); - //printlist("Sorted List:", c); - free(c); +#ifdef DEBUG + printlist("Sorted List:", c, LISTSIZEA+LISTSIZEB); + printf ("------------\n"); + merge(9, a, n, b, m, c); + printlist("Should Be: ", c, LISTSIZEA+LISTSIZEB); +#endif + //free(c); return 0; } @@ -89,14 +107,18 @@ void printlist(char * message, numtype * ptr, int len) { printf ("\n"); } +/* + * return -1 if len == 0 + * return pos if elem is to be placed before *list + * return len if elem has to be positioned after list + */ int rank(numtype elem, numtype * list, int len) { int pos; int i = len; - pos = 0; - if (elem == -1) { return -1; } + if (len == 0) { return -1; } while (i > 0) { - /*printf ("elem_list: %i %i\n", elem, *list);*/ + /*printf ("rank: %i %i\n", elem, *list);*/ if (elem <= *list) { return pos; } @@ -110,11 +132,17 @@ int rank(numtype elem, numtype * list, int len) { void merge(int ti, numtype * a, int n, numtype * b, int m, int * c) { int sum; int i; - /*printf ("sorting a:%i (%i) and b:%i (%i)\n", *a, n, *b, m);*/ +#ifdef DEBUG + //printf ("sorting a:%i (%i) and b:%i (%i)\n", *a, n, *b, m); + //printlist("sortinglista", a, n); + //printlist("sortinglistb", b, m); +#endif if (m<0) { m=0;} if (n<0) { n=0;} sum = n + m; +#ifdef DEBUG //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); +#endif for (i = 0; i < sum; i++) { // n+m == 0 if (n <= 0 && m <= 0) { @@ -122,19 +150,25 @@ void merge(int ti, numtype * a, int n, numtype * b, int m, int * c) { return; } if (n <= 0) { + //printf ("changing: c[%i] from %i to %i\n", i, c[i], *b); c[i] = *b++; m--; } else { if (m <= 0) { + //printf ("changing: c[%i] from %i to %i\n", i, c[i], *a); c[i] = *a++; n--; } else { if (*a < *b) { + //printf ("changing: c[%i] from %i to %i\n", i, c[i], *a); c[i] = *a++; n--; } else { + //printf ("changing: c[%i] from %i to %i\n", i, c[i], *b); c[i] = *b++; m--; } } } } - // printf ("merge done, n=%d, m=%d\n", n, m); +#ifdef DEBUG + //printf ("merge done, n=%d, m=%d\n", n, m); +#endif return; } -- 2.43.0