add openmp from isi

diff --git a/openmp/merge/Makefile b/openmp/merge/Makefile
new file mode 100644 (file)
index 0000000..f8efee4
--- /dev/null
+++ b/openmp/merge/Makefile
@@ -0,0 +1,20 @@
+# GCC Makefile
+
+CC      = gcc
+CFLAGS  = -pedantic -Wall -g -fopenmp
+LDFLAGS = -fopenmp
+
+BINARIES = sort
+OBJECTS  = $(BINARIES).o
+
+all: sort
+
+sort: sort.o
+       $(CC) -o $@ $< $(LDFLAGS)
+
+%.o: %.c
+       $(CC) $(CFLAGS) -c $<
+
+.PHONY: clean
+clean:
+       rm -rf $(OBJECTS) $(BINARIES)

diff --git a/openmp/merge/sort.c b/openmp/merge/sort.c
new file mode 100644 (file)
index 0000000..13957f3
--- /dev/null
+++ b/openmp/merge/sort.c
@@ -0,0 +1,119 @@
+/* implementation of parallel merge sort */
+#include <stdio.h>
+#include <omp.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+#define LISTSIZE 10
+#define THREADS 2
+
+void printlist(char * message, int * ptr) {
+       printf (message);
+       while (*ptr != -1) {
+               printf (" %i", *ptr);
+               ptr++;
+       }
+       printf ("\n");
+}
+
+int rank(int elem, int * list) {
+       int pos;
+       
+       pos = 0;
+       if (elem == -1) { return -1; }
+       while (*list >= 0) {
+               /*printf ("elem_list: %i %i\n", elem, *list);*/
+               if (elem <= *list) {
+                       return pos;
+               }
+               list++;
+               pos++;
+       }
+       return -1;
+}
+
+/* merge(a,n,b,m,c): merges a of size n and b of size m into c */
+void merge(int ti, int * a, int n, int * b, int m, int * c) {
+       int sum;
+       int i;
+       sleep (1);
+       /*printf ("sorting a:%i (%i) and b:%i (%i)\n", *a, n, *b, m);*/
+       if (m<0) { m=0;}
+       if (n<0) { n=0;}
+       sum = n + m;
+       //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);
+       i = 0;
+       while (i < sum) {
+               if (*a < 0 && *b < 0) {
+                       printf ("%i Calculation failed somehow...\n", ti);
+                       return;
+               }
+               if (*a < 0) {
+                       c[i] = *b; m--;
+                       b++;
+               } else {
+                       if (*b < 0) {
+                               c[i] = *a; n--;
+                               a++;
+                       } else {
+                               if (*a < *b) {
+                                       c[i] = *a; n--;
+                                       a++;
+                               } else {
+                                       c[i] = *b; m--;
+                                       b++;
+                               }
+                       }
+               }
+               i++;
+       }
+       return;
+}
+
+int main ( int argc, char ** argv) {
+       int n = LISTSIZE;
+       int p = THREADS;
+       int i;
+       int a_len, b_len, b_len_end, b_len_begin;
+       int a[] = {0,3,4,14,61,62,70,72,74,99,-1};
+       int b[] = {1,2,7,34,35,68,77,78,79,84,-1};
+       int * c;
+
+       printf ("----------------------------------\n");
+
+       c = (int *) malloc((LISTSIZE * 2 + 1) * (sizeof (int)));
+       c[LISTSIZE*2] = -1;
+
+       printlist("0 Sorted List A:", a);
+       printlist("0 Sorted List B:", b);
+
+       a_len = n/p;
+#pragma omp parallel for shared(a,b,c,n,p,a_len) private(i,b_len_begin,b_len_end,b_len)
+       for (i = 0; i < p; i++) {
+               b_len_begin = rank(a[i*a_len], b);
+               b_len_end = rank(a[(i+1)*a_len], b);
+               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 = 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]);
+               if (b_len == 0) {
+                       continue;
+               }
+               merge(  i+1,
+                               &a[i*a_len],
+                               a_len,
+                               &b[b_len_begin],
+                               b_len,
+                               &c[i*a_len+b_len_begin]);
+       }
+
+       printlist("Sorted List:", c);
+       free(c);
+       return 0;
+}