From 3215bdf7deb41b7ee41ace8637989315cf61b041 Mon Sep 17 00:00:00 2001 From: yeom Date: Mon, 26 Jul 2010 05:43:36 +0000 Subject: [PATCH] add mergesort benchmark ported from dpj --- .../oooJava/mergesort/MergeSort.java | 236 ++++++++++++++++++ .../oooJava/mergesort/MergeSort4.java | 181 ++++++++++++++ .../src/Benchmarks/oooJava/mergesort/makefile | 32 +++ 3 files changed, 449 insertions(+) create mode 100644 Robust/src/Benchmarks/oooJava/mergesort/MergeSort.java create mode 100644 Robust/src/Benchmarks/oooJava/mergesort/MergeSort4.java create mode 100644 Robust/src/Benchmarks/oooJava/mergesort/makefile diff --git a/Robust/src/Benchmarks/oooJava/mergesort/MergeSort.java b/Robust/src/Benchmarks/oooJava/mergesort/MergeSort.java new file mode 100644 index 00000000..5e8f9a59 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/mergesort/MergeSort.java @@ -0,0 +1,236 @@ +/** + * Sample sort program adapted from a demo in Cilk and Hood. + * + * There are two versions of MergeSort here: One that splits the array into four + * pieces at each recursive step, and one that splits the array into eight + * pieces. This abstract class represents the common elements of both versions. + * + **/ + +public class MergeSort { + + /* Threshold values */ + + // Cutoff for when to do sequential versus parallel merges + public static int MERGE_SIZE; + + // Cutoff for when to do sequential quicksort versus parallel mergesort + public static int QUICK_SIZE; + + // Cutoff for when to use insertion-sort instead of quicksort + public static int INSERTION_SIZE; + + public static int SERIALIZED_CUT_OFF; + + + protected int[] input; + protected int[] result; + protected int size; + + public void run(int size) { + this.size=size; + long startT=System.currentTimeMillis(); + initialize(); + System.out.println("init time="+(System.currentTimeMillis()-startT)); + runWorkAndTest(); + } + + public MergeSort() { + MERGE_SIZE = 2048; + QUICK_SIZE = 2048; + INSERTION_SIZE = 2000; + } + + public void initialize() { + + SERIALIZED_CUT_OFF=size/16; + + input = new int[size]; + result = new int[size]; + + Random random = new Random(100100); + for (int i = 0; i < size; ++i) { + int k = random.nextInt(); + if (k < 0) { + k *= -1; + } + k = k % 10000; + input[i] = k; + } + } + + public void runWorkAndTest() { + sese run{ + sort(input, result); + } +// sese test{ +// checkSorted(input); +// } + } + + public void sort(int A[], int B[]){ + } + + protected void checkSorted(int[] array) { + System.out.println("Verifying results- size of " + array.length); + for (int i = 1; i < array.length; i++) { + if (array[i - 1] > array[i]) { + System.out.println("Validation Failed."); + return; + } + } + System.out.println("Validation Success."); + } + + protected void merge(int A[], int B[], int out[]) { + + if (A.length <= MERGE_SIZE) { + sequentialMerge(A, B, out); + } else { + int aHalf = A.length >>> 1; /* l33t shifting h4x!!! */ + int bSplit = findSplit(A[aHalf], B); + + int[] A_split0 = new int[aHalf]; + int[] A_split1 = new int[A.length - aHalf]; + for (int i = 0; i < aHalf; i++) { + A_split0[i] = A[i]; + } + for (int i = aHalf; i < A.length; i++) { + A_split1[i - aHalf] = A[i]; + } + + int[] B_split0 = new int[bSplit]; + int[] B_split1 = new int[B.length - bSplit]; + for (int i = 0; i < bSplit; i++) { + B_split0[i] = B[i]; + } + for (int i = bSplit; i < B.length; i++) { + B_split1[i - bSplit] = B[i]; + } + + int outSplit = aHalf + bSplit; + int[] out_split0 = new int[outSplit]; + int[] out_split1 = new int[out.length - outSplit]; + + merge(A_split0, B_split0, out_split0); + merge(A_split1, B_split1, out_split1); + + for (int i = 0; i < outSplit; i++) { + out[i]=out_split0[i]; + } + for (int i = outSplit; i < out.length; i++) { + out[i]=out_split1[i - outSplit]; + } + + } + + } + + /** A standard sequential merge **/ + protected void sequentialMerge(int A[], int B[], int out[]) { + int a = 0; + int aFence = A.length; + int b = 0; + int bFence = B.length; + int k = 0; + + while (a < aFence && b < bFence) { + if (A[a] < B[b]) + out[k++] = A[a++]; + else + out[k++] = B[b++]; + } + + while (a < aFence) + out[k++] = A[a++]; + while (b < bFence) + out[k++] = B[b++]; + } + + protected int findSplit(int value, int B[]) { + int low = 0; + int high = B.length; + while (low < high) { + int middle = low + ((high - low) >>> 1); + if (value <= B[middle]) + high = middle; + else + low = middle + 1; + } + return high; + } + + /** A standard sequential quicksort **/ + protected void quickSort(int array[], int lo, int hi) { +// int lo = 0; +// int hi = array.length - 1; + // If under threshold, use insertion sort + int[] arr = array; + if (hi - lo + 1l <= INSERTION_SIZE) { + for (int i = lo + 1; i <= hi; i++) { + int t = arr[i]; + int j = i - 1; + while (j >= lo && arr[j] > t) { + arr[j + 1] = arr[j]; + --j; + } + arr[j + 1] = t; + } + return; + } + + // Use median-of-three(lo, mid, hi) to pick a partition. + // Also swap them into relative order while we are at it. + + int mid = (lo + hi) >>> 1; + + if (arr[lo] > arr[mid]) { + int t = arr[lo]; + arr[lo] = arr[mid]; + arr[lo] = arr[mid]; + arr[mid] = t; + } + if (arr[mid] > arr[hi]) { + int t = arr[mid]; + arr[mid] = arr[hi]; + arr[hi] = t; + + if (arr[lo] > arr[mid]) { + t = arr[lo]; + arr[lo] = arr[mid]; + arr[mid] = t; + } + + } + + int left = lo + 1; // start one past lo since already handled lo + int right = hi - 1; // similarly + + int partition = arr[mid]; + + while(true){ + + while (arr[right] > partition) + --right; + + while (left < right && arr[left] <= partition) + ++left; + + if (left < right) { + int t = arr[left]; + arr[left] = arr[right]; + arr[right] = t; + --right; + } else + break; + + } + + quickSort(arr,lo,left+1); + quickSort(arr,left+1,hi); + + } + +} diff --git a/Robust/src/Benchmarks/oooJava/mergesort/MergeSort4.java b/Robust/src/Benchmarks/oooJava/mergesort/MergeSort4.java new file mode 100644 index 00000000..e35cbfae --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/mergesort/MergeSort4.java @@ -0,0 +1,181 @@ +/** + * 4-way split version of merge sort + */ + +public class MergeSort4 extends MergeSort { + + public static void main(String[] args) { + int problemSize= 1048576; + if(args.length>0){ + problemSize=Integer.parseInt(args[0]); + } + MergeSort4 sort = new MergeSort4(); + sort.run(problemSize); + } + + public MergeSort4(){ + super(); + } + + public void serializedSort(int A[], int B[]){ + + if (A.length <= QUICK_SIZE) { + quickSort(A,0,A.length-1); + } else { + + int q = A.length / 4; + + int[] idxs = new int[3]; + idxs[0] = q; + idxs[1] = 2 * q; + idxs[2] = 3 * q; + + int size0 = idxs[0]; + int size1 = idxs[1] - idxs[0]; + int size2 = idxs[2] - idxs[1]; + int size3 = A.length - idxs[2]; + + int[] A_quarters0 = new int[size0]; + int[] A_quarters1 = new int[size1]; + int[] A_quarters2 = new int[size2]; + int[] A_quarters3 = new int[size3]; + + for (int i = 0; i < idxs[0]; i++) { + A_quarters0[i] = A[i]; + } + for (int i = idxs[0]; i < idxs[1]; i++) { + A_quarters1[i - idxs[0]] = A[i]; + } + for (int i = idxs[1]; i < idxs[2]; i++) { + A_quarters2[i - idxs[1]] = A[i]; + } + for (int i = idxs[2]; i < A.length; i++) { + A_quarters3[i - idxs[2]] = A[i]; + } + + int[] B_quarters0 = new int[size0]; + int[] B_quarters1 = new int[size1]; + int[] B_quarters2 = new int[size2]; + int[] B_quarters3 = new int[size3]; + + for (int i = 0; i < idxs[0]; i++) { + B_quarters0[i] = B[i]; + } + for (int i = idxs[0]; i < idxs[1]; i++) { + B_quarters1[i - idxs[0]] = B[i]; + } + for (int i = idxs[1]; i < idxs[2]; i++) { + B_quarters2[i - idxs[1]] = B[i]; + } + for (int i = idxs[2]; i < B.length; i++) { + B_quarters3[i - idxs[2]] = B[i]; + } + + int halfSize = B.length - (2 * q); + int[] B_halves0 = new int[halfSize]; + int[] B_halves1 = new int[halfSize]; + + sort(A_quarters0, B_quarters0); + sort(A_quarters1, B_quarters1); + sort(A_quarters2, B_quarters2); + sort(A_quarters3, B_quarters3); + + merge(A_quarters0, A_quarters1, B_halves0); + merge(A_quarters2, A_quarters3, B_halves1); + merge(B_halves0, B_halves1, A); + + } + + } + + public void sort(int A[], int B[]) { + + if(A.length<=SERIALIZED_CUT_OFF){ + serializedSort(A, B); + }else{ + if (A.length <= QUICK_SIZE) { + quickSort(A,0,A.length-1); + } else { + + int q = A.length / 4; + + int[] idxs = new int[3]; + idxs[0] = q; + idxs[1] = 2 * q; + idxs[2] = 3 * q; + + int size0 = idxs[0]; + int size1 = idxs[1] - idxs[0]; + int size2 = idxs[2] - idxs[1]; + int size3 = A.length - idxs[2]; + + int[] A_quarters0 = new int[size0]; + int[] A_quarters1 = new int[size1]; + int[] A_quarters2 = new int[size2]; + int[] A_quarters3 = new int[size3]; + + for (int i = 0; i < idxs[0]; i++) { + A_quarters0[i] = A[i]; + } + for (int i = idxs[0]; i < idxs[1]; i++) { + A_quarters1[i - idxs[0]] = A[i]; + } + for (int i = idxs[1]; i < idxs[2]; i++) { + A_quarters2[i - idxs[1]] = A[i]; + } + for (int i = idxs[2]; i < A.length; i++) { + A_quarters3[i - idxs[2]] = A[i]; + } + + int[] B_quarters0 = new int[size0]; + int[] B_quarters1 = new int[size1]; + int[] B_quarters2 = new int[size2]; + int[] B_quarters3 = new int[size3]; + + for (int i = 0; i < idxs[0]; i++) { + B_quarters0[i] = B[i]; + } + for (int i = idxs[0]; i < idxs[1]; i++) { + B_quarters1[i - idxs[0]] = B[i]; + } + for (int i = idxs[1]; i < idxs[2]; i++) { + B_quarters2[i - idxs[1]] = B[i]; + } + for (int i = idxs[2]; i < B.length; i++) { + B_quarters3[i - idxs[2]] = B[i]; + } + + int halfSize = B.length - (2 * q); + int[] B_halves0 = new int[halfSize]; + int[] B_halves1 = new int[halfSize]; + + sese p1{ + sort(A_quarters0, B_quarters0); + } + sese p2{ + sort(A_quarters1, B_quarters1); + } + sese p3{ + sort(A_quarters2, B_quarters2); + } + sese p4{ + sort(A_quarters3, B_quarters3); + } + + sese m1{ + merge(A_quarters0, A_quarters1, B_halves0); + } + + sese m2{ + merge(A_quarters2, A_quarters3, B_halves1); + } + + sese m3{ + merge(B_halves0, B_halves1, A); + } + + } + } + } + +} diff --git a/Robust/src/Benchmarks/oooJava/mergesort/makefile b/Robust/src/Benchmarks/oooJava/mergesort/makefile new file mode 100644 index 00000000..c97479b5 --- /dev/null +++ b/Robust/src/Benchmarks/oooJava/mergesort/makefile @@ -0,0 +1,32 @@ +#raytracer +PROGRAM=MergeSort4 + +SOURCE_FILES=MergeSort4.java + +BUILDSCRIPT=../../../buildscript + +USEOOO= -ooojava 31 2 -ooodebug +BSFLAGS= -64bit -mainclass $(PROGRAM) -garbagestats -joptimize #-debug +#USEOOO= -ooojava 8 2 -ooodebug +#BSFLAGS= -64bit -nooptimize -mainclass $(PROGRAM) -debug -garbagestats -joptimize +DISJOINT= -disjoint -disjoint-k 1 -enable-assertions + +default: + $(BUILDSCRIPT) -nojava $(USEOOO) $(BSFLAGS) $(DISJOINT) -o $(PROGRAM)p $(SOURCE_FILES) -builddir par + +single: + $(BUILDSCRIPT) $(BSFLAGS) -o $(PROGRAM)s -builddir sing $(SOURCE_FILES) + +ooo: + $(BUILDSCRIPT) $(USEOOO) $(BSFLAGS) $(DISJOINT) -o $(PROGRAM)p -builddir par $(SOURCE_FILES) + +clean: + rm -f $(PROGRAM)p.bin $(PROGRAM)s.bin + rm -fr par sing + rm -f *~ + rm -f *.dot + rm -f *.png + rm -f *.txt + rm -f aliases.txt + rm -f mlpReport*txt + rm -f results*txt -- 2.34.1