From 78db55fc965bbb9b1911904075c4da58adb23d6e Mon Sep 17 00:00:00 2001
From: someone <someone@somenet.org>
Date: Mon, 16 Jan 2012 18:53:03 +0100
Subject: [PATCH] rewrote prefix sums (seqential, recursive and dataparallel) -
 now more modular and out-of-source building.

---
 .gitignore                                 |  1 +
 openmp/prefix/Makefile                     | 25 ++++++----
 openmp/prefix/algorithm_2.c                |  7 ---
 openmp/prefix/algorithm_2.h                |  7 ---
 openmp/prefix/algorithm_3.c                |  7 ---
 openmp/prefix/datapar.c                    | 27 +++++++++++
 openmp/prefix/datapar.h                    |  6 +++
 openmp/prefix/hillis.c                     |  9 ++++
 openmp/prefix/{algorithm_3.h => hillis.h}  |  1 -
 openmp/prefix/prefix.c                     | 56 +++++++++++-----------
 openmp/prefix/prefix.h                     | 13 +++--
 openmp/prefix/{algorithm_1.c => recurse.c} |  7 ++-
 openmp/prefix/{algorithm_1.h => recurse.h} |  1 -
 openmp/prefix/runAll.sh                    | 17 +++++++
 openmp/prefix/seq.c                        | 18 +++++++
 openmp/prefix/seq.h                        |  6 +++
 16 files changed, 141 insertions(+), 67 deletions(-)
 delete mode 100644 openmp/prefix/algorithm_2.c
 delete mode 100644 openmp/prefix/algorithm_2.h
 delete mode 100644 openmp/prefix/algorithm_3.c
 create mode 100644 openmp/prefix/datapar.c
 create mode 100644 openmp/prefix/datapar.h
 create mode 100644 openmp/prefix/hillis.c
 rename openmp/prefix/{algorithm_3.h => hillis.h} (57%)
 rename openmp/prefix/{algorithm_1.c => recurse.c} (73%)
 rename openmp/prefix/{algorithm_1.h => recurse.h} (59%)
 create mode 100755 openmp/prefix/runAll.sh
 create mode 100644 openmp/prefix/seq.c
 create mode 100644 openmp/prefix/seq.h

diff --git a/.gitignore b/.gitignore
index aacd912..01d7f18 100644
--- a/.gitignore
+++ b/.gitignore
@@ -3,6 +3,7 @@
 *.class
 .*.swp
 *.pyc
+build
 openmp/merge/sort
 openmp/merge/merge.dat
 openmp/merge/merge.png
diff --git a/openmp/prefix/Makefile b/openmp/prefix/Makefile
index f29e2ef..ba9a3a6 100644
--- a/openmp/prefix/Makefile
+++ b/openmp/prefix/Makefile
@@ -1,20 +1,29 @@
 # GCC Makefile
 
 CC      = gcc
-CFLAGS  = -pedantic -Wall -ggdb -fopenmp --std=c99
+CFLAGS  = -pedantic -Wall -ggdb -fopenmp --std=c99 -O3
 LDFLAGS = -fopenmp
 
-BINARIES = prefix
-OBJECTS  = $(BINARIES).o algorithm_1.o algorithm_2.o algorithm_3.o
+all: build/seq build/recurse build/datapar build/hillis
 
-all: prefix
+build/seq: build/prefix.o build/seq.o
+	$(CC) -o $@ $? $(LDFLAGS)
+
+build/recurse: build/prefix.o build/recurse.o
+	$(CC) -o $@ $? $(LDFLAGS)
 
-prefix: prefix.o algorithm_1.o algorithm_2.o algorithm_3.o
+build/datapar: build/prefix.o build/datapar.o
 	$(CC) -o $@ $? $(LDFLAGS)
 
-%.o: %.c
-	$(CC) $(CFLAGS) -c $<
+build/hillis: build/prefix.o build/hillis.o
+	$(CC) -o $@ $? $(LDFLAGS)
+
+build/%.o: %.c mkdir
+	$(CC) $(CFLAGS) -c $< -o $@
+
+mkdir:
+	mkdir -p build
 
 .PHONY: clean
 clean:
-	rm -rf $(OBJECTS) $(BINARIES)
+	rm -rf build
diff --git a/openmp/prefix/algorithm_2.c b/openmp/prefix/algorithm_2.c
deleted file mode 100644
index 0dafd6b..0000000
--- a/openmp/prefix/algorithm_2.c
+++ /dev/null
@@ -1,7 +0,0 @@
-/*
- * In-place iterative algorithm
- */
-#include "algorithm_2.h"
-
-void algorithm_2 (numtype y[], unsigned int n, unsigned int ops[]) {
-}
diff --git a/openmp/prefix/algorithm_2.h b/openmp/prefix/algorithm_2.h
deleted file mode 100644
index c9e3939..0000000
--- a/openmp/prefix/algorithm_2.h
+++ /dev/null
@@ -1,7 +0,0 @@
-/*
- * In-place iterative algorithm
- */
-#include <stdio.h>
-#include "prefix.h"
-
-void algorithm_2 (numtype y[], unsigned int n, unsigned int ops[]);
diff --git a/openmp/prefix/algorithm_3.c b/openmp/prefix/algorithm_3.c
deleted file mode 100644
index 312dea8..0000000
--- a/openmp/prefix/algorithm_3.c
+++ /dev/null
@@ -1,7 +0,0 @@
-/*
- * O(nlog n) work algorithm (Hillis-Steele)
- */
-#include "algorithm_3.h"
-
-void algorithm_3 (numtype y[], unsigned int n, unsigned int ops[]) {
-}
diff --git a/openmp/prefix/datapar.c b/openmp/prefix/datapar.c
new file mode 100644
index 0000000..38c1487
--- /dev/null
+++ b/openmp/prefix/datapar.c
@@ -0,0 +1,27 @@
+#include "datapar.h"
+/*
+ * Non-recursive, data parallel implementation
+ */
+
+void algorithm (numtype x[], unsigned long size, unsigned int ops[]) {
+	printf ("par2");
+	unsigned long k;
+	unsigned long kk;
+	unsigned long i;
+
+	for(k=1; k < size; k = kk){
+		kk = k<<1;
+		for(i = kk-1; i < size; i+= kk){
+			x[i] = x[i-k] + x[i];
+		}
+		//barrier;
+	}
+
+	for(k=kk>>1; k > 1; k = kk){
+		kk = k>>1;
+		for(i = k-1; i < size-kk; i+= k){
+			x[i+kk] = x[i] + x[i+kk];
+		}
+		//barrier;
+	}
+}
diff --git a/openmp/prefix/datapar.h b/openmp/prefix/datapar.h
new file mode 100644
index 0000000..45778eb
--- /dev/null
+++ b/openmp/prefix/datapar.h
@@ -0,0 +1,6 @@
+/*
+ * Non-recursive, data parallel implementation
+ */
+#include <stdio.h>
+#include "prefix.h"
+
diff --git a/openmp/prefix/hillis.c b/openmp/prefix/hillis.c
new file mode 100644
index 0000000..0ddeda3
--- /dev/null
+++ b/openmp/prefix/hillis.c
@@ -0,0 +1,9 @@
+/*
+ * O(nlog n) work algorithm (Hillis-Steele)
+ */
+#include "hillis.h"
+
+void algorithm (numtype in[], unsigned long size, unsigned int ops[]) {
+	printf ("hillis. TODO\n");
+
+}
diff --git a/openmp/prefix/algorithm_3.h b/openmp/prefix/hillis.h
similarity index 57%
rename from openmp/prefix/algorithm_3.h
rename to openmp/prefix/hillis.h
index 97e94ce..aa2257c 100644
--- a/openmp/prefix/algorithm_3.h
+++ b/openmp/prefix/hillis.h
@@ -4,4 +4,3 @@
 #include <stdio.h>
 #include "prefix.h"
 
-void algorithm_3 (numtype y[], unsigned int n, unsigned int ops[]);
diff --git a/openmp/prefix/prefix.c b/openmp/prefix/prefix.c
index b5e9b44..4318d2b 100644
--- a/openmp/prefix/prefix.c
+++ b/openmp/prefix/prefix.c
@@ -1,43 +1,41 @@
 #include <stdio.h>
 #include <omp.h>
 #include "prefix.h"
-#include "algorithm_1.h"
-#include "algorithm_2.h"
-#include "algorithm_3.h"
 
-#define NUMBERS 104857500
+/* TODO: Replace with file read. */
+#define NUMBERS 5
 
 int main (int argc, char* argv[]) {
 	numtype numarray[NUMBERS];
+	unsigned long size;
 	//unsigned int countarray[NUMBERS];
-	int i;
-	double startTime, endTime;
+	double startTime;
 
-	for (i = 0; i < NUMBERS; i++) {
-		numarray[i] = 10;
-		//countarray[i] = 0;
+//TODO: read num file here.
+//first value in file = numcount
+	for (size = 0; size < NUMBERS; size++) {
+		numarray[size] = 10;
 	}
 
+	/* might want to comment this out, if numarray is big */
+	printf ("array details\n[%li", numarray[0]);
+	for (unsigned long i = 1; i < size; i++) {
+		printf (", %li", numarray[i]);
+	}
+	printf ("]\n");
+
+	printf("init done starting algorithm. size: %li\n", size);
 	startTime = omp_get_wtime();
-	printf ("calling algorithm 1:");
-	algorithm_1(numarray, NUMBERS, NULL);
-	printf ("sum: %i\n", numarray[NUMBERS-1]);
-	endTime = omp_get_wtime();
-	printf("took %f seconds.\n", endTime-startTime);
-	
-	startTime = omp_get_wtime();
-	printf ("calling algorithm 2:");
-	algorithm_2(numarray, NUMBERS, NULL);
-	printf ("sum: %i\n", numarray[NUMBERS-1]);
-	endTime = omp_get_wtime();
-	printf("took %f seconds.\n", endTime-startTime);
-	
-	startTime = omp_get_wtime();
-	printf ("calling algorithm 3:");
-	algorithm_3(numarray, NUMBERS, NULL);
-	printf ("sum: %i\n", numarray[NUMBERS-1]);
-	endTime = omp_get_wtime();
-	printf("took %f seconds.\n", endTime-startTime);
-	
+	algorithm(numarray, size, NULL);
+	printf("DONE. took %f seconds.\n", omp_get_wtime()-startTime);
+	printf ("result: %li\n", numarray[(size-1)]);
+
+	/* might want to comment this out, if numarray is big */
+	printf ("array details\n[%li", numarray[0]);
+	for (unsigned long i = 1; i < size; i++) {
+		printf (", %li", numarray[i]);
+	}
+	printf ("]\n");
+
 	return 0;
 }
diff --git a/openmp/prefix/prefix.h b/openmp/prefix/prefix.h
index b724faf..27cb99d 100644
--- a/openmp/prefix/prefix.h
+++ b/openmp/prefix/prefix.h
@@ -1,4 +1,11 @@
-#ifndef NUMTYPE
-#define NUMTYPE
-typedef unsigned int numtype;
+/*
+* Loader that inits the startarray + size, runs the linked algorithm and later prints the array output.
+*/
+
+#ifndef _prefix_h_
+#define _prefix_h_
+
+typedef unsigned long numtype;
+void algorithm (numtype in[], unsigned long size, unsigned int ops[]);
+
 #endif
diff --git a/openmp/prefix/algorithm_1.c b/openmp/prefix/recurse.c
similarity index 73%
rename from openmp/prefix/algorithm_1.c
rename to openmp/prefix/recurse.c
index 7b549de..4958b23 100644
--- a/openmp/prefix/algorithm_1.c
+++ b/openmp/prefix/recurse.c
@@ -1,9 +1,9 @@
 /*
  * Recursive parallel prefix with auxiliary array y
  */
-#include "algorithm_1.h"
+#include "recurse.h"
 
-void algorithm_1 (numtype x[], unsigned int n, unsigned int ops[]) {
+void algorithm (numtype x[], unsigned long n, unsigned int ops[]) {
 	unsigned int i;
 	numtype y[n/2];
 	if (n == 1) {
@@ -14,10 +14,9 @@ void algorithm_1 (numtype x[], unsigned int n, unsigned int ops[]) {
 		y[i] = x[2*i] + x[2*i+1];
 	}
 
-	algorithm_1(y, n/2, ops);
+	algorithm(y, n/2, ops);
 
 	x[1] = y[0];
-
 	for (i = 1; i < (n/2); i++){
 		x[2*i] = y[i-1] + x[2*i];
 		x[2*i+1] = y[i];
diff --git a/openmp/prefix/algorithm_1.h b/openmp/prefix/recurse.h
similarity index 59%
rename from openmp/prefix/algorithm_1.h
rename to openmp/prefix/recurse.h
index f171fcb..34c6870 100644
--- a/openmp/prefix/algorithm_1.h
+++ b/openmp/prefix/recurse.h
@@ -4,4 +4,3 @@
 #include <stdio.h>
 #include "prefix.h"
 
-void algorithm_1 (numtype y[], unsigned int n, unsigned int ops[]);
diff --git a/openmp/prefix/runAll.sh b/openmp/prefix/runAll.sh
new file mode 100755
index 0000000..d08363c
--- /dev/null
+++ b/openmp/prefix/runAll.sh
@@ -0,0 +1,17 @@
+#!/bin/bash
+
+echo "seq"
+build/seq
+
+echo "recurse"
+ulimit -s unlimited
+build/recurse
+
+echo "datapar"
+build/datapar
+
+echo "hillis"
+build/hillis
+
+echo "done - hit ENTER to exit"
+read
diff --git a/openmp/prefix/seq.c b/openmp/prefix/seq.c
new file mode 100644
index 0000000..59418a3
--- /dev/null
+++ b/openmp/prefix/seq.c
@@ -0,0 +1,18 @@
+
+#include "seq.h"
+/**
+ * Sequential algorithm to compute correct values.
+ */
+void algorithm (numtype in[], unsigned long size, unsigned int ops[]) {
+	numtype out[size];
+	out[1] = in[0];
+	for (unsigned long i = 1; i < size; i++){
+		out[i+1] = out[i] + in[i];
+	}
+	out[size] = out[size-1] + in[size-1];
+
+	/* Copy out array to in */
+	for (unsigned long i = 0; i < size; i++){
+		in[i] = out[i+1];
+	}
+}
diff --git a/openmp/prefix/seq.h b/openmp/prefix/seq.h
new file mode 100644
index 0000000..aa2257c
--- /dev/null
+++ b/openmp/prefix/seq.h
@@ -0,0 +1,6 @@
+/*
+ * O(nlog n) work algorithm (Hillis-Steele)
+ */
+#include <stdio.h>
+#include "prefix.h"
+
-- 
2.43.0