From f96792967af6ce033e35632b7dbdab065f82d4d3 Mon Sep 17 00:00:00 2001 From: limw Date: Wed, 13 Jul 2011 23:49:53 +0000 Subject: [PATCH] Ported over bamboo benchmarks for use as non-Bamboo java benchmarks. --- .../GC/NON_BAMBOO/Fibheaps/FibHeap.java | 265 ++++++++++ .../GC/NON_BAMBOO/Fibheaps/Makefile | 11 + .../GC/NON_BAMBOO/Fibheaps/TestRunner.java | 66 +++ .../GC/NON_BAMBOO/Fibheaps/Tree.java | 66 +++ .../GC/NON_BAMBOO/Fibheaps/fibheaps.hs | 308 +++++++++++ .../GC/NON_BAMBOO/GCBench/TestRunner.java | 162 ++++++ .../GC/NON_BAMBOO/JGFMonteCarlo/AppDemo.java | 240 +++++++++ .../JGFMonteCarlo/AppDemoRunner.java | 77 +++ .../JGFMonteCarlo/MonteCarloPath.java | 463 +++++++++++++++++ .../GC/NON_BAMBOO/JGFMonteCarlo/MyRandom.java | 58 +++ .../GC/NON_BAMBOO/JGFMonteCarlo/PathId.java | 179 +++++++ .../NON_BAMBOO/JGFMonteCarlo/PriceStock.java | 150 ++++++ .../GC/NON_BAMBOO/JGFMonteCarlo/RatePath.java | 483 ++++++++++++++++++ .../NON_BAMBOO/JGFMonteCarlo/ReturnPath.java | 360 +++++++++++++ .../GC/NON_BAMBOO/JGFMonteCarlo/ToResult.java | 171 +++++++ .../GC/NON_BAMBOO/MTree/TestRunner.java | 157 ++++++ .../GC/NON_BAMBOO/RayTracer/Composer.java | 35 ++ .../GC/NON_BAMBOO/RayTracer/Interval.java | 43 ++ .../GC/NON_BAMBOO/RayTracer/Isect.java | 36 ++ .../GC/NON_BAMBOO/RayTracer/Light.java | 38 ++ .../GC/NON_BAMBOO/RayTracer/Primitive.java | 43 ++ .../GC/NON_BAMBOO/RayTracer/Ray.java | 47 ++ .../GC/NON_BAMBOO/RayTracer/RayTracer.java | 407 +++++++++++++++ .../GC/NON_BAMBOO/RayTracer/Scene.java | 89 ++++ .../GC/NON_BAMBOO/RayTracer/Sphere.java | 97 ++++ .../GC/NON_BAMBOO/RayTracer/Surface.java | 52 ++ .../GC/NON_BAMBOO/RayTracer/TestRunner.java | 92 ++++ .../GC/NON_BAMBOO/RayTracer/Vec.java | 181 +++++++ .../GC/NON_BAMBOO/RayTracer/View.java | 54 ++ .../GC/NON_BAMBOO/RayTracer/makefile | 30 ++ .../Scheduling/GC/NON_BAMBOO/bh/Body.java | 242 +++++++++ .../Scheduling/GC/NON_BAMBOO/bh/Cell.java | 132 +++++ .../Scheduling/GC/NON_BAMBOO/bh/Makefile | 3 + .../GC/NON_BAMBOO/bh/MathVector.class | Bin 0 -> 2758 bytes .../GC/NON_BAMBOO/bh/MathVector.java | 241 +++++++++ .../Scheduling/GC/NON_BAMBOO/bh/Node.java | 112 ++++ .../GC/NON_BAMBOO/bh/TestRunner.java | 125 +++++ .../Scheduling/GC/NON_BAMBOO/bh/Tree.java | 298 +++++++++++ .../Scheduling/GC/NON_BAMBOO/bh/benchmark.py | 3 + .../Scheduling/GC/NON_BAMBOO/lcss/Main.hs | 60 +++ .../Scheduling/GC/NON_BAMBOO/lcss/Makefile | 8 + .../GC/NON_BAMBOO/lcss/TestRunner.java | 246 +++++++++ .../GC/NON_BAMBOO/lcss/lcss.faststdout | 1 + .../GC/NON_BAMBOO/lcss/lcss.slowstdout | 1 + .../Scheduling/GC/NON_BAMBOO/lcss/lcss.stdout | 1 + .../Scheduling/GC/NON_BAMBOO/tsp/Makefile | 4 + .../GC/NON_BAMBOO/tsp/TestRunner.java | 114 +++++ .../GC/NON_BAMBOO/tsp/Tree_tsp.java | 456 +++++++++++++++++ .../Scheduling/GC/NON_BAMBOO/tsp/benchmark.py | 3 + .../GC/NON_BAMBOO/voronoi/Edge.java | 364 +++++++++++++ .../GC/NON_BAMBOO/voronoi/EdgePair.java | 27 + .../GC/NON_BAMBOO/voronoi/MyDouble.java | 15 + .../GC/NON_BAMBOO/voronoi/TestRunner.java | 53 ++ .../GC/NON_BAMBOO/voronoi/Vec2.java | 121 +++++ .../GC/NON_BAMBOO/voronoi/Vertex.java | 262 ++++++++++ 55 files changed, 7352 insertions(+) create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/Fibheaps/FibHeap.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/Fibheaps/Makefile create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/Fibheaps/TestRunner.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/Fibheaps/Tree.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/Fibheaps/fibheaps.hs create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/GCBench/TestRunner.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/AppDemo.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/AppDemoRunner.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/MonteCarloPath.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/MyRandom.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/PathId.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/PriceStock.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/RatePath.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/ReturnPath.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/ToResult.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/MTree/TestRunner.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Composer.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Interval.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Isect.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Light.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Primitive.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Ray.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/RayTracer.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Scene.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Sphere.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Surface.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/TestRunner.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Vec.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/View.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/makefile create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/Body.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/Cell.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/Makefile create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/MathVector.class create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/MathVector.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/Node.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/TestRunner.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/Tree.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/benchmark.py create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/Main.hs create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/Makefile create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/TestRunner.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/lcss.faststdout create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/lcss.slowstdout create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/lcss.stdout create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/tsp/Makefile create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/tsp/TestRunner.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/tsp/Tree_tsp.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/tsp/benchmark.py create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/Edge.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/EdgePair.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/MyDouble.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/TestRunner.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/Vec2.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/Vertex.java diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/Fibheaps/FibHeap.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/Fibheaps/FibHeap.java new file mode 100644 index 00000000..c96413af --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/Fibheaps/FibHeap.java @@ -0,0 +1,265 @@ +public class FibHeap { + + public int degree; + public TaggedTree ttree; + public Vector forest; + + public FibHeap() { + this.degree = 0; + this.ttree = null; + this.forest = null; + } + + public FibHeap(int degree, + TaggedTree ttree, + Vector forest) { + this.degree = degree; + this.ttree = ttree; + this.forest = forest; + } + + public boolean isEmpty() { + return this.degree == 0; + } + + public int minFH() { + return this.ttree.tree.root; + } + + public FibHeap insertFH(int x) { + TaggedTree tt = new TaggedTree(0, new Tree(x, null)); + FibHeap fh = new FibHeap(1, tt, null); + + return this.meldFH(fh); + } + + public FibHeap meldFH(FibHeap fh) { + if(this.isEmpty()) { + return fh; + } else { + int root1 = fh.ttree.tree.root; + int root2 = this.ttree.tree.root; + TaggedTree root = null; + Vector forest = fh.forest; + if(forest == null) { + forest = new Vector(); + } + if(root1 <= root2) { + root = fh.ttree; + forest.insertElementAt(this.ttree, 0); + } else { + root = this.ttree; + forest.insertElementAt(fh.ttree, 0); + } + if(this.forest != null) { + for(int i = 0; i < this.forest.size(); i++) { + forest.addElement(this.forest.elementAt(i)); + } + } + return new FibHeap(fh.degree+this.degree, root, forest); + } + } + + private void insert(Vector a, + TaggedTree tt) { + int index = tt.degree; + if(a.elementAt(index) == null) { + a.setElementAt(tt.tree, index); + } else { + Tree at = (Tree)a.elementAt(index); + a.setElementAt(null, index); + // link these two tree + Tree it = tt.tree.link(at); + TaggedTree itt = new TaggedTree(index+1, it); + insert(a, itt); + } + } + + private FibHeap getMin_t(Vector a, + int mini, + Tree mint, + Vector b, + int i, + int d) { + if(i >= d) { + return new FibHeap(this.degree-1, new TaggedTree(mini, mint), b); + } else { + Tree at = (Tree)a.elementAt(i); + if(at == null) { + return getMin_t(a, mini, mint, b, i+1, d); + } else { + if(mint.root <= at.root) { + b.insertElementAt(new TaggedTree(i, at), 0); + return getMin_t(a, mini, mint, b, i+1, d); + } else { + b.insertElementAt(new TaggedTree(mini, mint), 0); + return getMin_t(a, i, at, b, i+1, d); + } + } + } + } + + private int locallog(int n) { + if(n == 1) { + return 0; + } else { + return 1 + locallog(n/2); + } + } + + public FibHeap deleteMinFH() { + if(this.isEmpty()) { + // error here + System.exit(0xa0); + } + if(this.degree == 1) { + return new FibHeap(); + } + // newArray (0,d) Zero >>= \a -> applyToAll (ins a) f + // Allocate an array indexed by degrees. + int d = locallog(this.degree - 1); + Vector a = new Vector(d+1); + for(int i = 0; i < d+1; i++) { + a.addElement(null); + } + // Insert every tree into this array. If, when inserting a tree of + // degree k, there already exists a tree of degree k, link the + // two trees and reinsert the new larger tree. + for(int i = 0; i < this.forest.size(); i++) { + TaggedTree tt = (TaggedTree)this.forest.elementAt(i); + insert(a, tt); + } + // sequence (map (ins a) (getChildren tt)) + Vector vec = this.ttree.getChildren(); + for(int i = 0; i < vec.size(); i++) { + TaggedTree tt = (TaggedTree)vec.elementAt(i); + insert(a, tt); + } + // getMin a >>= \ (tt,f) -> return (FH (n-1) tt f)) + Tree test = (Tree)a.elementAt(d); + if(test == null) { + // error here + System.exit(0xa1); + } else { + return getMin_t(a, d, test, new Vector(), 0, d); + } + } + + private Vector combine(int index, + Vector ts, + Vector next, + Vector rest) { + if(ts.size() == 0) { + return startup(index+1, next, rest); + } else if (ts.size() == 1) { + Vector vec = startup(index+1, next, rest); + vec.insertElementAt(new TaggedTree(index, (Tree)ts.elementAt(0)), 0); + return vec; + } else { + Tree t1 = (Tree)ts.elementAt(0); + Tree t2 = (Tree)ts.elementAt(1); + next.insertElementAt(t1.link(t2), 0); + Vector nts = new Vector(); + for(int i = 2; i < ts.size(); i++) { + nts.addElement(ts.elementAt(i)); + } + return combine(index, nts, next, rest); + } + } + + private Vector startup(int index, + Vector ts, + Vector rest) { + if(ts.size() == 0) { + if(rest.size() == 0) { + return new Vector(); + } else { + Vector tts = (Vector)rest.elementAt(0); + Vector nrest = new Vector(); + for(int i = 1; i < rest.size(); i++) { + nrest.addElement(rest.elementAt(i)); + } + return startup(index+1, tts, nrest); + } + } else { + if(rest.size() == 0) { + return combine(index, ts, new Vector(), new Vector()); + } else { + Vector tts = (Vector)rest.elementAt(0); + Vector nrest = new Vector(); + for(int i = 1; i < rest.size(); i++) { + nrest.addElement(rest.elementAt(i)); + } + return combine(index, ts, tts, nrest); + } + } + } + + private FibHeap chooseMin(FibHeap fh, + TaggedTree tt) { + FibHeap rfh = null; + if(fh.ttree.tree.root <= tt.tree.root) { + fh.forest.insertElementAt(tt, 0); + rfh = new FibHeap(this.degree-1, fh.ttree, fh.forest); + } else { + fh.forest.insertElementAt(fh.ttree, 0); + rfh = new FibHeap(this.degree-1, tt, fh.forest); + } + return rfh; + } + + public FibHeap deleteMinFH_t() { + if(this.isEmpty()) { + // error here + System.exit(0xa2); + } + if(this.degree == 1) { + return new FibHeap(); + } + // The second version of deleteMin uses accumArray to group trees of like + // size. It then performs the linking and all remaining steps purely + // functionally. + int d = locallog(this.degree - 1); + // arrange a 2 dimentional array to group the trees + Vector a = new Vector(d+1); + for(int i = 0; i < d+1; i++) { + a.addElement(new Vector()); + } + for(int i = 0; i < this.forest.size(); i++) { + TaggedTree tt = (TaggedTree)this.forest.elementAt(i); + int de = tt.degree; + ((Vector)a.elementAt(de)).addElement(tt.tree); + } + // sequence (map (ins a) (getChildren tt)) + Vector vec = this.ttree.getChildren(); + for(int i = 0; i < vec.size(); i++) { + TaggedTree tt = (TaggedTree)vec.elementAt(i); + int de = tt.degree; + ((Vector)a.elementAt(de)).addElement(tt.tree); + } + Vector ts = (Vector)a.elementAt(0); + Vector na = new Vector(); + for(int i = 1; i < a.size(); i++) { + na.addElement(a.elementAt(i)); + } + Vector vvec = startup(0, ts, na); + + // getMin() + TaggedTree rtt = (TaggedTree)vvec.elementAt(0); + FibHeap rfh = new FibHeap(this.degree-1, rtt, new Vector()); + Vector nvvec = new Vector(); + for(int i = 1; i < vvec.size(); i++) { + nvvec.addElement(vvec.elementAt(i)); + } + vvec = nvvec; + while(vvec.size() != 0) { + rfh = chooseMin(rfh, (TaggedTree)vvec.elementAt(0)); + Vector tvvec = new Vector(); + for(int i = 1; i < vvec.size(); i++) { + tvvec.addElement(vvec.elementAt(i)); + } + vvec = tvvec; + } + return rfh; + } +} \ No newline at end of file diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/Fibheaps/Makefile b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/Fibheaps/Makefile new file mode 100644 index 00000000..4352fb75 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/Fibheaps/Makefile @@ -0,0 +1,11 @@ +include ../../header.mk + +TEST = fibheaps +TITLE = Fibonacci heaps by Okasaki +TEST_ARGS = 200000 +HUGS_EXTRA_OPTS=-98 +GHC_EXTRA_OPTS=-funbox-strict-fields +GHC_ASM_EXTRA_OPTS=-funbox-strict-fields +GHC_OLD_EXTRA_OPTS=-funbox-strict-fields + +include ../../footer.mk diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/Fibheaps/TestRunner.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/Fibheaps/TestRunner.java new file mode 100644 index 00000000..2b5d94a5 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/Fibheaps/TestRunner.java @@ -0,0 +1,66 @@ +// the fibheap class +public class TestRunner { + + public TestRunner() {} + + public void run() { + // generate test data + int iter = 1200; //200; + int seed = 1967; + //Vector testdata = new Vector(iter); + FibHeap fh = new FibHeap(); + FibHeap fh_t = new FibHeap(); + for(int i = 0; i < iter; i++) { + int rand = (77 * seed + 1) % 1024; + //testdata.addElement(new Integer(rand)); + seed++; + fh = fh.insertFH(rand); + fh_t = fh_t.insertFH(rand); + } + // makeFH from the test data + /*FibHeap fh = new FibHeap(); + for(int i = testdata.size(); i > 0; i++) { + fh = fh.insertFH((Integer)(testdata.elementAt(i-1)).intValue()); + } + FibHeap fh_t = new FibHeap(); + for(int i = testdata.size(); i > 0; i++) { + fh_t = fh_t.insertFH((Integer)(testdata.elementAt(i-1)).intValue()); + }*/ + + int[] rfh = new int[iter]; + int[] rfh_t = new int[iter]; + + int i = 0; + while(!fh.isEmpty()) { + rfh[i] = fh.minFH(); + fh = fh.deleteMinFH(); + i++; + } + int j = 0; + while(!fh_t.isEmpty()) { + rfh_t[j] = fh_t.minFH(); + fh_t = fh_t.deleteMinFH_t(); + j++; + } + + if(i != j) { + // error! + System.exit(0xaa); + } else { + for(i = 0; i < j; i++) { + if(rfh[i] != rfh_t[i]) { + // error! + System.exit(0xbb); + } + } + } + } + + public static void main(String[] args) { + int threadnum = 62; + for(int i = 0; i < threadnum; ++i) { + TestRunner tr = new TestRunner(); + tr.run(); + } + } +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/Fibheaps/Tree.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/Fibheaps/Tree.java new file mode 100644 index 00000000..a6e495e0 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/Fibheaps/Tree.java @@ -0,0 +1,66 @@ +// the bionomial class +public class Tree { + public int root; + public Vector v_trees; + + public Tree() { + this.root = 0; + this.v_trees = null; + } + + public Tree(int root, + Vector trees) { + this.root = root; + this.v_trees = trees; + } + + public Tree link(Tree t) { + int root = 0; + Tree tmp = null; + Vector tmp_v = null; + if(this.root <= t.root) { + root = this.root; + tmp = t; + tmp_v = this.v_trees; + } else { + root = t.root; + tmp = this; + tmp_v = t.v_trees; + } + Tree nt = new Tree(root, tmp_v); + if(nt.v_trees == null) { + nt.v_trees = new Vector(); + } + nt.v_trees.insertElementAt(tmp, 0); + return nt; + } +} + +public class TaggedTree { + public int degree; + public Tree tree; + + public TaggedTree() { + this.degree = 0; + this.tree = null; + } + + public TaggedTree(int degree, + Tree tree) { + this.degree = degree; + this.tree = tree; + } + + public Vector getChildren() { + Vector rst = new Vector(); + Vector v = tree.v_trees; + int d = this.degree-1; + if(v != null) { + for(int i = 0; i < v.size(); i++) { + rst.addElement(new TaggedTree(d, (Tree)v.elementAt(i))); + d--; + } + } + return rst; + } +} \ No newline at end of file diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/Fibheaps/fibheaps.hs b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/Fibheaps/fibheaps.hs new file mode 100644 index 00000000..ebd33bf1 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/Fibheaps/fibheaps.hs @@ -0,0 +1,308 @@ +{- +Date: Tue, 04 Jul 1995 13:10:58 -0400 +From: Chris_Okasaki@LOCH.MESS.CS.CMU.EDU +To: simonpj@dcs.gla.ac.uk +Subject: Fibonacci Heaps + +As I promised at the Haskell Workshop, here is a sample program +using encapsulated state. I've translated this from SML, but +in doing so, I noticed that in fact accumArray is all the +encapsulated state you really need for this application. In SML, +we are forced to use mutable arrays because we don't have such +fancy monolithic array "primitives" as accumArray. + +I've written and tested this as a literate Gofer script because I've +never been able to get GHC to run under Mach. :-( + +Let me know if you have any problems... + +Chris + + +- ---------------------------------------------------------------------- + +FIBONACCI HEAPS + +Fibonacci heaps are a priority queue data structure supporting the +following operations: + O(1) Insert + O(1) FindMin + O(1) Meld + O(log n) DeleteMin + +(In an imperative settting, Fibonacci heaps also support + O(1) DecreaseKey (of an indicated element) + O(log n) Delete (an indicated element) +but these operations are problematic in a functional setting.) + +There is one catch: for the DeleteMin operation, the bounds are +amortized instead of worst-case. This means that the bounds are +only guaranteed if you use the data structure in a single-threaded manner. +Otherwise, you can take longer than expected by repeatedly going back +and operating on an "expensive" version of the data structure. + +(Note: I am currently working on a paper with another student describing +a functional priority queue achieving the above bounds in the worst-case +instead of amortized. This data structure may be freely used in a +non-single-threaded manner with no ill effects.) + +To understand the implementation of Fibonacci heaps, it is helpful to +first understand binomial queues. See, for example, David King's +"Functional Binomial Queues" from the last Glasgow workshop. +-} + +import Data.Array +import System.IO +import System + +import Control.Monad.ST +import Data.Array.ST + + +{- +Like binomial queues, Fibonacci heaps are based on heap-ordered +binomial trees. +-} + +data Tree a = Node !a [Tree a] + +{- +The degree of a binomial tree is equal to its number of children. +Every binomial tree of degree k has binomial trees of degrees +k-1...0 as children, in that order. It is easy to show that +a binomial tree of degree k has size 2^k. + + +The fundamental operation on binomial trees is linking, which compares +the roots of two binomial trees and makes the larger a child of the +smaller (thus bumping its degree by one). It is essential that this +only be called on binomial trees of equal degree. +-} + +link (a @ (Node x as)) (b @ (Node y bs)) = + if x <= y then Node x (b:as) else Node y (a:bs) + +-- It will also be useful to extract the minimum element from a tree. + +root (Node x _) = x + +-- We will frequently need to tag trees with their degrees. + +type TaggedTree a = (Int,Tree a) + +degree (k, t) = k +tree (k, t) = t + +-- Given a tagged tree, extract and tag its children. + +getChildren (n, Node x ts) = zipWith (,) [n-1,n-2 .. ] ts + +-- Extract the minimum element from a tagged tree. + +root' = root . tree + +{- + -------------------- + +We also need a type for bags supporting constant time union. The simple +representation given here is sufficient since we will always process bags +as a whole. Note that for this application it is not necessary to +filter out occurences of EmptyBag. Also, for this application order +is irrelevant. +-} + +data Bag a = EmptyBag | ConsBag a (Bag a) | UnionBags (Bag a) (Bag a) + +bagToList b = flatten b [] + where flatten EmptyBag xs = xs + flatten (ConsBag x b) xs = flatten b (x:xs) + flatten (UnionBags b1 b2) xs = flatten b1 (flatten b2 xs) + +applyToAll :: (a -> ST s ()) -> Bag a -> ST s () +applyToAll f EmptyBag = return () +applyToAll f (ConsBag x b) = f x >> applyToAll f b +applyToAll f (UnionBags b1 b2) = applyToAll f b1 >> applyToAll f b2 + + +-- Miscellaneous stuff. + +log2 1 = 0 +log2 n = 1 + log2 (n `div` 2) + +data MyMaybe a = Zero | One !a + +{- + -------------------- + +Since binomial trees only come in certain, fixed sizes, we need some +way to represent priority queues of other sizes. We will do this +with a forest of trees summing to the correct size. +-} + +type Forest a = Bag (TaggedTree a) + +{- +In binomial queues, this forest must be maintained in strictly increasing +order of degree. For Fibonacci heaps, we adopt a more relaxed attitude: +degrees may be repeated and order does not matter. + +To be able to find the minimum element quickly, we keep the tree with the +minimum root outside of the bag. In addition, at the top level of each heap, +we store the total size of the heap. +-} + +data FibHeap a = EmptyFH | FH !Int (TaggedTree a) (Forest a) + + +-- Now, the following operations are trivial. + +emptyFH = EmptyFH + +isEmptyFH EmptyFH = True +isEmptyFH (FH _ _ _) = False + +singleFH x = FH 1 (0, Node x []) EmptyBag + +insertFH x xs = meldFH (singleFH x) xs + +minFH EmptyFH = error "minFH EmptyFH" +minFH (FH n tt f) = root' tt + + +{- + -------------------- + +Meld achieves its efficiency by simply unioning the two forests. +-} + +meldFH EmptyFH xs = xs +meldFH xs EmptyFH = xs +meldFH (FH n1 tt1 f1) (FH n2 tt2 f2) = + if root' tt1 <= root' tt2 then + FH (n1+n2) tt1 (ConsBag tt2 (UnionBags f1 f2)) + else + FH (n1+n2) tt2 (ConsBag tt1 (UnionBags f1 f2)) + +{- +Finally, the only hard operation is deleteMin. After throwing away the +minimum element, it repeatedly links trees of equal degree until +no such pairs are left. The most efficient way to do this is with +an array. I give two implementations, one using monadic arrays, +the other using accumArray. + +In the first implementation, there are three steps. + 1. Allocate an array indexed by degrees. + 2. Insert every tree into this array. If, when inserting a tree of + degree k, there already exists a tree of degree k, link the + two trees and reinsert the new larger tree. + 3. Transfer the trees into a bag, keeping track of the minimum tree. +-} + +deleteMinFH EmptyFH = error "deleteMinFH EmptyFH" +deleteMinFH (FH 1 tt f) = EmptyFH +deleteMinFH (FH n tt f) = + let + d = log2 (n-1) -- maximum possible degree + + ins :: Ord a => STArray s Int (MyMaybe (Tree a)) -> (Int,Tree a) -> ST s () + ins a (i, t) = + readArray a i >>= \e -> + case e of + Zero -> writeArray a i (One t) + One t2 -> writeArray a i Zero >> + ins a (i+1, link t t2) + +{- +Note that after inserting all the trees, the array contains trees +in the same pattern as the bits of n-1. Since we know that the +highest order bit of n-1 is one, we know that there is a tree in +the highest slot of the array. +-} + + getMin a = + readArray a d >>= \e -> + case e of + Zero -> error "must be One" -- since array is filled as bits of n-1 + One t -> getMin' a d t EmptyBag 0 + getMin' a mini mint b i = + if i >= d then + return ((mini, mint),b) + else + readArray a i >>= \e -> + case e of + Zero -> getMin' a mini mint b (i+1) + One t -> if root mint <= root t then + getMin' a mini mint (ConsBag (i, t) b) (i+1) + else + getMin' a i t (ConsBag (mini, mint) b) (i+1) + + in + runST (newArray (0,d) Zero >>= \a -> + applyToAll (ins a) f >> + sequence (map (ins a) (getChildren tt)) >> + getMin a >>= \ (tt,f) -> + return (FH (n-1) tt f)) + +{- +The second version of deleteMin uses accumArray to group trees of like +size. It then performs the linking and all remaining steps purely +functionally. +-} + +deleteMinFH' EmptyFH = error "deleteMinFH EmptyFH" +deleteMinFH' (FH 1 tt f) = EmptyFH +deleteMinFH' (FH n tt f) = + let + d = log2 (n-1) -- maximum possible degree + + a = accumArray (flip (:)) [] (0,d) (getChildren tt ++ bagToList f) + + doLinks (ts:rest) = startup 0 ts rest + where startup i [] [] = [] + startup i [] (ts:rest) = startup (i+1) ts rest + startup i ts [] = combine i ts [] [] + startup i ts (next:rest) = combine i ts next rest + + combine i [] next rest = startup (i+1) next rest + combine i [t] next rest = (i, t) : startup (i+1) next rest + combine i (t1:t2:ts) next rest = + combine i ts (link t1 t2 : next) rest + + getMin (tt:rest) = foldl chooseMin (tt,EmptyBag) rest + where chooseMin (tt1,b) tt2 = + if root' tt1 <= root' tt2 then + (tt1,ConsBag tt2 b) + else + (tt2,ConsBag tt1 b) + + (new_tt,new_f) = getMin (doLinks (elems a)) + in + FH (n-1) new_tt new_f + + +-- Testing... + +fibToList :: (Ord a) => FibHeap a -> [a] +fibToList xs = if isEmptyFH xs then [] + else minFH xs : fibToList (deleteMinFH xs) + +fibToList' :: (Ord a) => FibHeap a -> [a] +fibToList' xs = if isEmptyFH xs then [] + else minFH xs : fibToList' (deleteMinFH' xs) + +makeFH :: (Ord a) => [a] -> FibHeap a +makeFH xs = foldr insertFH emptyFH xs + +fibSort :: (Ord a) => [a] -> [a] +fibSort = fibToList . makeFH + +fibSort' :: (Ord a) => [a] -> [a] +fibSort' = fibToList' . makeFH + +randoms :: Int -> [Int] +randoms n = take n (iterate (\seed-> (77*seed+1) `rem` 1024) 1967) + +test n = fibSort (randoms n) == fibSort' (randoms n) + +--partain +main = getArgs >>= \ [n] -> putStrLn (show (test (read n))) diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/GCBench/TestRunner.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/GCBench/TestRunner.java new file mode 100644 index 00000000..24297535 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/GCBench/TestRunner.java @@ -0,0 +1,162 @@ +//This is adapted from a benchmark written by John Ellis and Pete Kovac +//of Post Communications. +//It was modified by Hans Boehm of Silicon Graphics. + +//This is no substitute for real applications. No actual application +//is likely to behave in exactly this way. However, this benchmark was +//designed to be more representative of real applications than other +//Java GC benchmarks of which we are aware. +//It attempts to model those properties of allocation requests that +//are important to current GC techniques. +//It is designed to be used either to obtain a single overall performance +//number, or to give a more detailed estimate of how collector +//performance varies with object lifetimes. It prints the time +//required to allocate and collect balanced binary trees of various +//sizes. Smaller trees result in shorter object lifetimes. Each cycle +//allocates roughly the same amount of memory. +//Two data structures are kept around during the entire process, so +//that the measured performance is representative of applications +//that maintain some live in-memory data. One of these is a tree +//containing many pointers. The other is a large array containing +//double precision floating point numbers. Both should be of comparable +//size. + +//The results are only really meaningful together with a specification +//of how much memory was used. It is possible to trade memory for +//better time performance. This benchmark should be run in a 32 MB +//heap, though we don't currently know how to enforce that uniformly. + +//Unlike the original Ellis and Kovac benchmark, we do not attempt +//measure pause times. This facility should eventually be added back +//in. There are several reasons for omitting it for now. The original +//implementation depended on assumptions about the thread scheduler +//that don't hold uniformly. The results really measure both the +//scheduler and GC. Pause time measurements tend to not fit well with +//current benchmark suites. As far as we know, none of the current +//commercial Java implementations seriously attempt to minimize GC pause +//times. + +//Known deficiencies: +//- No way to check on memory use +//- No cyclic data structures +//- No attempt to measure variation with object size +//- Results are sensitive to locking cost, but we dont +//check for proper locking + +public class TestRunner extends Thread { + + public static final int kStretchTreeDepth = 16; // about 4Mb + public static final int kLongLivedTreeDepth = 14; // about 1Mb + public static final int kArraySize = 250000; // about 1Mb + public static final int kMinTreeDepth = 4; + public static final int kMaxTreeDepth = 14; + + // Nodes used by a tree of a given size + int TreeSize(int i) { + return ((1 << (i + 1)) - 1); + } + + // Number of iterations to use for a given tree depth + int NumIters(int i) { + return 2 * TreeSize(kStretchTreeDepth) / TreeSize(i); + } + + // Build tree top down, assigning to older objects. + void Populate(int iDepth, Node thisNode) { + if (iDepth<=0) { + return; + } else { + iDepth--; + thisNode.left = new Node(); + thisNode.right = new Node(); + Populate (iDepth, thisNode.left); + Populate (iDepth, thisNode.right); + } + } + + // Build tree bottom-up + Node MakeTree(int iDepth) { + if (iDepth<=0) { + return new Node(); + } else { + return new Node(MakeTree(iDepth-1), + MakeTree(iDepth-1)); + } + } + + void tc1(int depth) { + Node tempTree = new Node(); + Populate(depth, tempTree); + tempTree = null; + } + + void tc2(int depth) { + Node tempTree = MakeTree(depth); + tempTree = null; + } + + void TimeConstruction(int depth) { + Node root; + int iNumIters = NumIters(depth); + Node tempTree; + + for (int i = 0; i < iNumIters; ++i) { + tc1(depth); + } + for (int i = 0; i < iNumIters; ++i) { + tc2(depth); + } + } + + public void stretch() { + Node root; + Node longLivedTree; + Node tempTree; + + // Stretch the memory space quickly + tempTree = MakeTree(kStretchTreeDepth); + tempTree = null; + } + + public void run() { + Node root; + Node longLivedTree; + + // Stretch the memory space quickly + stretch(); + + // Create a long lived object + longLivedTree = new Node(); + Populate(kLongLivedTreeDepth, longLivedTree); + + // Create long-lived array, filling half of it + float array[] = new float[kArraySize]; + for (int i = 0; i < kArraySize/2; ++i) { + array[i] = 1.0f/i; + } + + for (int d = kMinTreeDepth; d <= kMaxTreeDepth; d += 2) { + TimeConstruction(d); + } + + if (longLivedTree == null || array[1000] != 1.0f/1000) { + System.out.println(0xa0); + System.out.println((int)(array[1000]*1000000)); + } + } + + class Node { + Node left, right; + int i, j; + Node(Node l, Node r) { left = l; right = r; } + Node() { } + } + + public static void main(String[] args) { + int threadnum = 62; + for(int i = 0; i < threadnum; ++i) { + TestRunner tr = new TestRunner(); + tr.run(); + } + } +} // class JavaGC diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/AppDemo.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/AppDemo.java new file mode 100644 index 00000000..001923da --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/AppDemo.java @@ -0,0 +1,240 @@ + +/************************************************************************** + * * + * Java Grande Forum Benchmark Suite - Thread Version 1.0 * + * * + * produced by * + * * + * Java Grande Benchmarking Project * + * * + * at * + * * + * Edinburgh Parallel Computing Centre * + * * + * email: epcc-javagrande@epcc.ed.ac.uk * + * * + * Original version of this code by Hon Yau (hwyau@epcc.ed.ac.uk) * + * * + * This version copyright (c) The University of Edinburgh, 2001. * + * All rights reserved. * + * * + **************************************************************************/ + + +/** + * Code, a test-harness for invoking and driving the Applications + * Demonstrator classes. + * + *

To do: + *

    + *
  1. Very long delay prior to connecting to the server.
  2. + *
  3. Some text output seem to struggle to get out, without + * the user tapping ENTER on the keyboard!
  4. + *
+ * + * @author H W Yau + * @version $Revision: 1.1 $ $Date: 2011/07/13 23:49:52 $ + */ +public class AppDemo { + + //------------------------------------------------------------------------ + // Class variables. + //------------------------------------------------------------------------ + + public float JGFavgExpectedReturnRateMC; + + //public int Serial; + //------------------------------------------------------------------------ + // Instance variables. + //------------------------------------------------------------------------ + /** + * The number of time-steps which the Monte Carlo simulation should + * run for. + */ + public int nTimeStepsMC; + /** + * The number of Monte Carlo simulations to run. + */ + public int nRunsMC; + + public int group; + /** + * The default duration between time-steps, in units of a year. + */ + public float dTime; + /** + * Flag to determine whether initialisation has already taken place. + */ + public boolean initialised; + /** + * Variable to determine which deployment scenario to run. + */ + public int runMode; + + //public Vector results; + + //public PriceStock psMC; + public float pathStartValue; + public float avgExpectedReturnRateMC; + public float avgVolatilityMC; + + public int counter; + + public RatePath avgMCrate; + + //public ToInitAllTasks initAllTasks; + public String name; + public int startDate; + public int endDate; + public int returnDefinition; + public float expectedReturnRate; + public float volatility; + + public AppDemo(int nTimeStepsMC, int nRunsMC, int group) { + this.JGFavgExpectedReturnRateMC = (float)0.0; + //this.Serial = 1; + + this.nTimeStepsMC = nTimeStepsMC; + this.nRunsMC = nRunsMC; + this.group = group; + this.initialised = false; + + this.dTime = (float)1.0/(float)365.0; + this.pathStartValue = (float)100.0; + this.avgExpectedReturnRateMC = (float)0.0; + this.avgVolatilityMC = (float)0.0; + + this.counter = 0; + + this.avgMCrate = new RatePath(this.nTimeStepsMC, + "MC", + 19990109, + 19991231, + this.dTime); + + //this.initAllTasks = null; + } + /** + * Single point of contact for running this increasingly bloated + * class. Other run modes can later be defined for whether a new rate + * should be loaded in, etc. + * Note that if the hostname is set to the string "none", + * then the demonstrator runs in purely serial mode. + */ + + /** + * Initialisation and Run methods. + */ + public void initSerial() { + // + // Measure the requested path rate. + RatePath rateP = new RatePath(); + //rateP.dbgDumpFields(); + ReturnPath returnP = rateP.getReturnCompounded(); + returnP.estimatePath(); + //returnP.dbgDumpFields(); + /*initAllTasks = new ToInitAllTasks(returnP, + nTimeStepsMC, + pathStartValue);*/ + this.name = returnP.name; + this.startDate = returnP.startDate; + this.endDate = returnP.endDate; + // + // Instance variables defined in ReturnPath object. + this.returnDefinition = returnP.returnDefinition; + this.expectedReturnRate = returnP.expectedReturnRate; + this.volatility = returnP.volatility; + + this.counter = 0; + return; + } + + //------------------------------------------------------------------------ + /** + * Method for doing something with the Monte Carlo simulations. + * It's probably not mathematically correct, but shall take an average over + * all the simulated rate paths. + * + * @exception DemoException thrown if there is a problem with reading in + * any values. + */ + boolean processResults(Vector returnMCs) { + float sumReturnRateMC = (float) 0.0; + float sumVolatilityMC = (float) 0.0; + RatePath avgmcrate = this.avgMCrate; + for(int i = 0; i < returnMCs.size(); i++) { + ToResult returnMC = (ToResult)returnMCs.elementAt(i); + avgmcrate.inc_pathValue(returnMC.pathValue); + sumReturnRateMC += returnMC.expectedReturnRate; + sumVolatilityMC += returnMC.volatility; + } + avgExpectedReturnRateMC = sumReturnRateMC; + avgVolatilityMC = sumVolatilityMC; + + this.counter++; + boolean isfinish = (this.counter == this.group); + if(isfinish) { + avgmcrate.inc_pathValue((float)1.0/((float)nRunsMC)); + avgExpectedReturnRateMC /= nRunsMC; + avgVolatilityMC /= nRunsMC; + JGFavgExpectedReturnRateMC = avgExpectedReturnRateMC; + } + + return isfinish; + } + // + //------------------------------------------------------------------------ + // Accessor methods for class AppDemo. + // Generated by 'makeJavaAccessor.pl' script. HWY. 20th January 1999. + //------------------------------------------------------------------------ + /** + * Accessor method for private instance variable nTimeStepsMC. + * + * @return Value of instance variable nTimeStepsMC. + */ + /*public int get_nTimeStepsMC() { + return(this.nTimeStepsMC); + }*/ + /** + * Set method for private instance variable nTimeStepsMC. + * + * @param nTimeStepsMC the value to set for the instance variable nTimeStepsMC. + */ + public void set_nTimeStepsMC(int nTimeStepsMC) { + this.nTimeStepsMC = nTimeStepsMC; + } + /** + * Accessor method for private instance variable nRunsMC. + * + * @return Value of instance variable nRunsMC. + */ + /*public int get_nRunsMC() { + return(this.nRunsMC); + }*/ + /** + * Set method for private instance variable nRunsMC. + * + * @param nRunsMC the value to set for the instance variable nRunsMC. + */ + public void set_nRunsMC(int nRunsMC) { + this.nRunsMC = nRunsMC; + } + /** + * Accessor method for private instance variable results. + * + * @return Value of instance variable results. + */ + /*public Vector get_results() { + return(this.results); + }*/ + /** + * Set method for private instance variable results. + * + * @param results the value to set for the instance variable results. + */ + /*public void set_results(Vector results) { + this.results = results; + }*/ + //------------------------------------------------------------------------ +} + diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/AppDemoRunner.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/AppDemoRunner.java new file mode 100644 index 00000000..e03ec1d6 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/AppDemoRunner.java @@ -0,0 +1,77 @@ +class AppDemoRunner { + + public String header; + public String name; + public int startDate; + public int endDate; + public float dTime; + public int returnDefinition; + public float expectedReturnRate; + public float volatility; + public int nTimeSteps; + public float pathStartValue; + + int id, nRunsMC, group; + //ToInitAllTasks toinitalltasks; + public Vector results; + + public AppDemoRunner(int id, + int nRunsMC, + int group, + AppDemo ad + /*ToInitAllTasks initalltask*/) { + this.id = id; + this.nRunsMC=nRunsMC; + this.group = group; + this.results = new Vector(); + + //this.header = initalltask.header; + this.name = ad.name; + this.startDate = ad.startDate; + this.endDate = ad.endDate; + this.dTime = ad.dTime; + this.returnDefinition = ad.returnDefinition; + this.expectedReturnRate = ad.expectedReturnRate; + this.volatility = ad.volatility; + this.nTimeSteps = ad.nTimeStepsMC; + this.pathStartValue = ad.pathStartValue; + } + + public void run() { + // Now do the computation. + int ilow, iupper, slice; + int gp = this.group; + int index = this.id; + int nruns = this.nRunsMC; + + slice = (nruns + gp-1)/gp; + + ilow = index*slice; + iupper = (index+1)*slice; + if (index==gp-1) { + iupper=nruns; + } + + for(int iRun=ilow; iRun < iupper; iRun++ ) { + //String header="MC run "+String.valueOf(iRun); + PriceStock ps = new PriceStock(); + ps.setInitAllTasks(this); + ps.setTask(/*header, */(long)iRun*11); + ps.run(); + results.addElement(ps.getResult()); + } + } + public static void main(String[] args) { + int datasize = 10000; //should be times of 2 + int nruns = 62 * 62; //16 * 16; + int group = 62; // 16; + + AppDemo ad = new AppDemo(datasize, nruns, group); + ad.initSerial(); + + for(int i = 0; i < group; i++) { + AppDemoRunner adr = new AppDemoRunner(i, nruns, group, ad); + adr.run(); + } + } +} \ No newline at end of file diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/MonteCarloPath.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/MonteCarloPath.java new file mode 100644 index 00000000..c3756b4b --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/MonteCarloPath.java @@ -0,0 +1,463 @@ +/** Banboo Version **/ + +/************************************************************************** + * * + * Java Grande Forum Benchmark Suite - Thread Version 1.0 * + * * + * produced by * + * * + * Java Grande Benchmarking Project * + * * + * at * + * * + * Edinburgh Parallel Computing Centre * + * * + * email: epcc-javagrande@epcc.ed.ac.uk * + * * + * Original version of this code by Hon Yau (hwyau@epcc.ed.ac.uk) * + * * + * This version copyright (c) The University of Edinburgh, 2001. * + * All rights reserved. * + * * + **************************************************************************/ + +/** + * Class representing the paths generated by the Monte Carlo engine. + * + *

To do list: + *

    + *
  1. double[] pathDate is not simulated.
  2. + *
+ * + * @author H W Yau + * @version $Revision: 1.1 $ $Date: 2011/07/13 23:49:52 $ + */ +public class MonteCarloPath extends PathId { + + //------------------------------------------------------------------------ + // Instance variables. + //------------------------------------------------------------------------ + /** + * Random fluctuations generated as a series of random numbers with + * given distribution. + */ + public float[] fluctuations; + /** + * The path values from which the random fluctuations are used to update. + */ + public float[] pathValue; + /** + * Integer flag for determining how the return was calculated, when + * used to calculate the mean drift and volatility parameters. + */ + public int returnDefinition; + /** + * Value for the mean drift, for use in the generation of the random path. + */ + public float expectedReturnRate; + /** + * Value for the volatility, for use in the generation of the random path. + */ + public float volatility; + /** + * Number of time steps for which the simulation should act over. + */ + public int nTimeSteps; + /** + * The starting value for of the security. + */ + public float pathStartValue; + //------------------------------------------------------------------------ + // Constructors. + //------------------------------------------------------------------------ + /** + * Default constructor. Needed by the HPT library to start create + * new instances of this class. The instance variables for this should + * then be initialised with the setInitAllTasks() method. + */ + public MonteCarloPath() { + super(); + this.expectedReturnRate = (float)0.0; + this.volatility = (float)0.0; + this.pathStartValue = (float)0.0; + this.returnDefinition=1; + this.nTimeSteps=0; + } + + /** + * Constructor, using the ReturnPath object to initialise + * the necessary instance variables. + * + * @param returnPath Object used to define the instance variables in + * this object. + * @param nTimeSteps The number of time steps for which to generate the + * random path. + * @exception DemoException Thrown if there is a problem initialising the + * object's instance variables. + */ + public MonteCarloPath(ReturnPath returnPath, + int nTimeSteps) { + /** + * These instance variables are members of PathId class. + */ + this.expectedReturnRate = (float)0.0; + this.volatility = (float)0.0; + this.pathStartValue = (float)0.0; + this.returnDefinition=1; + + copyInstanceVariables(returnPath); + this.nTimeSteps = nTimeSteps; + this.pathValue = new float[nTimeSteps]; + this.fluctuations = new float[nTimeSteps]; + } + /** + * Constructor, where the PathId objects is used to ease + * the number of instance variables to pass in. + * + * @param pathId Object used to define the identity of this Path. + * @param returnDefinition How the statistic variables were defined, + * according to the definitions in + * ReturnPath's two class variables + * COMPOUNDED and + * NONCOMPOUNDED. + * @param expectedReturnRate The measured expected return rate for which to generate. + * @param volatility The measured volatility for which to generate. + * @param nTimeSteps The number of time steps for which to generate. + * @exception DemoException Thrown if there is a problem initialising the + * object's instance variables. + */ + public MonteCarloPath(PathId pathId, + int returnDefinition, + float expectedReturnRate, + float volatility, + int nTimeSteps) { + /** + * These instance variables are members of PathId class. + * Invoking with this particular signature should point to the + * definition in the PathId class. + */ + this.pathStartValue = (float)0.0; + + copyInstanceVariables(pathId); + this.returnDefinition = returnDefinition; + this.expectedReturnRate = expectedReturnRate; + this.volatility = volatility; + this.nTimeSteps = nTimeSteps; + this.pathValue = new float[nTimeSteps]; + this.fluctuations = new float[nTimeSteps]; + } + /** + * Constructor, for when the user wishes to define each of the instance + * variables individually. + * + * @param name The name of the security which this Monte Carlo path + * should represent. + * @param startDate The date when the path starts, in 'YYYYMMDD' format. + * @param endDate The date when the path ends, in 'YYYYMMDD' format. + * @param dTime The interval in the data between successive data points + * in the generated path. + * @param returnDefinition How the statistic variables were defined, + * according to the definitions in + * ReturnPath's two class variables + * COMPOUNDED and + * NONCOMPOUNDED. + * @param expectedReturnRate The measured mean drift for which to generate. + * @param volatility The measured volatility for which to generate. + * @param nTimeSteps The number of time steps for which to generate. + */ + public MonteCarloPath(String name, + int startDate, + int endDate, + float dTime, + int returnDefinition, + float expectedReturnRate, + float volatility, + int nTimeSteps) { + /** + * These instance variables are members of PathId class. + */ + this.name = name; + this.startDate = startDate; + this.endDate = endDate; + this.dTime = dTime; + this.returnDefinition = returnDefinition; + this.expectedReturnRate = expectedReturnRate; + this.volatility = volatility; + this.nTimeSteps = nTimeSteps; + this.pathValue = new float[nTimeSteps]; + this.fluctuations = new float[nTimeSteps]; + } + + //------------------------------------------------------------------------ + // Methods. + //------------------------------------------------------------------------ + //------------------------------------------------------------------------ + // Accessor methods for class MonteCarloPath. + // Generated by 'makeJavaAccessor.pl' script. HWY. 20th January 1999. + //------------------------------------------------------------------------ + /** + * Accessor method for private instance variable fluctuations. + * + * @return Value of instance variable fluctuations. + * @exception DemoException thrown if instance variable fluctuations + * is undefined. + */ + /*public float[] get_fluctuations() { + return(this.fluctuations); + }*/ + /** + * Set method for private instance variable fluctuations. + * + * @param fluctuations the value to set for the instance variable + * fluctuations. + */ + public void set_fluctuations(float[] fluctuations) { + this.fluctuations = fluctuations; + } + /** + * Accessor method for private instance variable pathValue. + * + * @return Value of instance variable pathValue. + * @exception DemoException thrown if instance variable pathValue + * is undefined. + */ + /*public float[] get_pathValue() { + return(this.pathValue); + }*/ + /** + * Set method for private instance variable pathValue. + * + * @param pathValue the value to set for the instance variable pathValue. + */ + public void set_pathValue(float[] pathValue) { + this.pathValue = pathValue; + } + /** + * Accessor method for private instance variable returnDefinition. + * + * @return Value of instance variable returnDefinition. + * @exception DemoException thrown if instance variable returnDefinition + * is undefined. + */ + /*public int get_returnDefinition() { + return(this.returnDefinition); + }*/ + /** + * Set method for private instance variable returnDefinition. + * + * @param returnDefinition the value to set for the instance variable + * returnDefinition. + */ + public void set_returnDefinition(int returnDefinition) { + this.returnDefinition = returnDefinition; + } + /** + * Accessor method for private instance variable expectedReturnRate. + * + * @return Value of instance variable expectedReturnRate. + * @exception DemoException thrown if instance variable expectedReturnRate + * is undefined. + */ + /*public float get_expectedReturnRate() { + return(this.expectedReturnRate); + }*/ + /** + * Set method for private instance variable expectedReturnRate. + * + * @param expectedReturnRate the value to set for the instance variable + * expectedReturnRate. + */ + public void set_expectedReturnRate(float expectedReturnRate) { + this.expectedReturnRate = expectedReturnRate; + } + /** + * Accessor method for private instance variable volatility. + * + * @return Value of instance variable volatility. + * @exception DemoException thrown if instance variable volatility + * is undefined. + */ + /*public float get_volatility() { + return(this.volatility); + }*/ + /** + * Set method for private instance variable volatility. + * + * @param volatility the value to set for the instance variable + * volatility. + */ + public void set_volatility(float volatility) { + this.volatility = volatility; + } + /** + * Accessor method for private instance variable nTimeSteps. + * + * @return Value of instance variable nTimeSteps. + * @exception DemoException thrown if instance variable nTimeSteps + * is undefined. + */ + /*public int get_nTimeSteps() { + return(this.nTimeSteps); + }*/ + /** + * Set method for private instance variable nTimeSteps. + * + * @param nTimeSteps the value to set for the instance variable + * nTimeSteps. + */ + public void set_nTimeSteps(int nTimeSteps) { + this.nTimeSteps = nTimeSteps; + } + /** + * Accessor method for private instance variable pathStartValue. + * + * @return Value of instance variable pathStartValue. + * @exception DemoException thrown if instance variable pathStartValue + * is undefined. + */ + /*public float get_pathStartValue() { + return(this.pathStartValue); + }*/ + /** + * Set method for private instance variable pathStartValue. + * + * @param pathStartValue the value to set for the instance variable + * pathStartValue. + */ + public void set_pathStartValue(float pathStartValue) { + this.pathStartValue = pathStartValue; + } + //------------------------------------------------------------------------ + /** + * Method for copying the suitable instance variable from a + * ReturnPath object. + * + * @param obj Object used to define the instance variables which + * should be carried over to this object. + * @exception DemoException thrown if there is a problem accessing the + * instance variables from the target objetct. + */ + private void copyInstanceVariables(ReturnPath obj) { + // + // Instance variables defined in the PathId object. + this.name = obj.name; + this.startDate = obj.startDate; + this.endDate = obj.endDate; + this.dTime = obj.dTime; + // + // Instance variables defined in this object. + this.returnDefinition = obj.returnDefinition; + this.expectedReturnRate = obj.expectedReturnRate; + this.volatility = obj.volatility; + } + + /** + * Method for returning a RatePath object from the Monte Carlo data + * generated. + * + * @return a RatePath object representing the generated + * data. + * @exception DemoException thrown if there was a problem creating + * the RatePath object. + */ + public RatePath getRatePath() { + return(new RatePath(this)); + } + /** + * Method for calculating the sequence of fluctuations, based around + * a Gaussian distribution of given mean and variance, as defined + * in this class' instance variables. Mapping from Gaussian + * distribution of (0,1) to (mean-drift,volatility) is done via + * Ito's lemma on the log of the stock price. + * + * @param randomSeed The psuedo-random number seed value, to start off a + * given sequence of Gaussian fluctuations. + * @exception DemoException thrown if there are any problems with + * the computation. + */ + public boolean computeFluctuationsGaussian(long randomSeed) { + int ntimesteps = this.nTimeSteps; + int length = this.fluctuations.length; + if( ntimesteps > length ) { + return false; + } + float[] flucts = this.fluctuations; + float expectedreturnrate = this.expectedReturnRate; + float vol = this.volatility; + float dtime = this.dTime; + + // + // First, make use of the passed in seed value. + MyRandom rnd; + float v1,v2, r; + v1 = (float)0.0; + v2 = (float)0.0; + if( randomSeed == -1 ) { + rnd = new MyRandom(0, v1, v2); + } else { + rnd = new MyRandom((int)randomSeed, v1, v2); + } + + // + // Determine the mean and standard-deviation, from the mean-drift and volatility. + float mean = (expectedreturnrate-(float)0.5*vol*vol)*dtime; + float sd = vol*Math.sqrtf(dtime); + float gauss, meanGauss=(float)0.0, variance=(float)0.0; + for( int i=0; i < ntimesteps; i += 2 ) { + r = rnd.seed(); + gauss = r*rnd.v1; + meanGauss+= gauss; + variance+= gauss*gauss; + // + // Now map this onto a general Gaussian of given mean and variance. + flucts[i] = mean + sd*gauss; + // dbgPrintln("gauss="+gauss+" fluctuations="+fluctuations[i]); + + gauss = r*rnd.v2; + meanGauss+= gauss; + variance+= gauss*gauss; + // + // Now map this onto a general Gaussian of given mean and variance. + flucts[i+1] = mean + sd*gauss; + } + meanGauss/=(float)ntimesteps; + variance /=(float)ntimesteps; + // dbgPrintln("meanGauss="+meanGauss+" variance="+variance); + } + /** + * Method for calculating the sequence of fluctuations, based around + * a Gaussian distribution of given mean and variance, as defined + * in this class' instance variables. Mapping from Gaussian + * distribution of (0,1) to (mean-drift,volatility) is done via + * Ito's lemma on the log of the stock price. This overloaded method + * is for when the random seed should be decided by the system. + * + * @exception DemoException thrown if there are any problems with + * the computation. + */ + public void computeFluctuationsGaussian() { + computeFluctuationsGaussian((long)-1); + } + /** + * Method for calculating the corresponding rate path, given the + * fluctuations and starting rate value. + * + * @param startValue the starting value of the rate path, to be + * updated with the precomputed fluctuations. + * @exception DemoException thrown if there are any problems with + * the computation. + */ + public void computePathValue(float startValue) { + float[] pathvalue = this.pathValue; + float[] flucts = this.fluctuations; + int length = this.nTimeSteps; + pathvalue[0] = startValue; + if( returnDefinition == 1 | + returnDefinition == 2) { + for(int i=1; i < length; i++ ) { + //System.printI((int)(flucts[i] * 10000)); + pathvalue[i] = pathvalue[i-1] * Math.expf(flucts[i]); + } + } + } +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/MyRandom.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/MyRandom.java new file mode 100644 index 00000000..2a8f985d --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/MyRandom.java @@ -0,0 +1,58 @@ +public class MyRandom { + + public int iseed; + public float v1,v2; + + public MyRandom(int iseed, float v1, float v2) { + this.iseed = iseed; + this.v1 = v1; + this.v2 = v2; + } + + public float update() { + float rand; + float scale= (float)4.656612875e-10; + + int is1,is2,iss2; + int imult= 16807; + int imod = 2147483647; + int seed = this.iseed; + + if (seed<=0) { + iseed = seed = 1; + } + + is2 = seed % 32768; + is1 = seed / 32768; + iss2 = is2 * imult; + is2 = iss2 % 32768; + is1 = (is1 * imult + iss2 / 32768) % (65536); + + iseed = seed = (is1 * 32768 + is2) % imod; + + rand = scale * seed; + + return rand; + + } + + public float seed() { + + float s,u1,u2,r; + s = (float)1.0; + //do { + u1 = update(); + u2 = update(); + + v1 = (float)2.0 * u1 - (float)1.0; + v2 = (float)2.0 * u2 - (float)1.0; + s = v1*v1 + v2*v2; + //} while (s >= (float)1.0); + s = s - (int)s; + //System.printI(0xb4); + r = Math.sqrtf((float)(-2.0*Math.logf(s))/(float)s); + //System.printI(0xb5); + return r; + + } +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/PathId.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/PathId.java new file mode 100644 index 00000000..2320a693 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/PathId.java @@ -0,0 +1,179 @@ +/** Banboo Version **/ + +/************************************************************************** +* * +* Java Grande Forum Benchmark Suite - Thread Version 1.0 * +* * +* produced by * +* * +* Java Grande Benchmarking Project * +* * +* at * +* * +* Edinburgh Parallel Computing Centre * +* * +* email: epcc-javagrande@epcc.ed.ac.uk * +* * +* Original version of this code by Hon Yau (hwyau@epcc.ed.ac.uk) * +* * +* This version copyright (c) The University of Edinburgh, 2001. * +* All rights reserved. * +* * +**************************************************************************/ + +/** + * Base class for all the security objects, namely in terms of + * providing a consistent means of identifying each such object. + * Also provides some methods for writing out debug messages. + * + * @author H W Yau + * @version $Revision: 1.1 $ $Date: 2011/07/13 23:49:52 $ + */ +public class PathId { + + //------------------------------------------------------------------------ + // Instance variables. + //------------------------------------------------------------------------ + /** + * Simple string name. + */ + public String name; + + /** + * The start date for the path, in YYYYMMDD format. + */ + public int startDate; + /** + * The end date for the path, in YYYYMMDD format. + */ + public int endDate; + /** + * The change in time between two successive data values. + */ + public float dTime; + + //------------------------------------------------------------------------ + // Constructors. + //------------------------------------------------------------------------ + /** + * Default constructor. + */ + public PathId() { + this.startDate=0; + this.endDate=0; + this.dTime=(float)0.0; + } + + /** + * Another constructor. + * + * @param name The name for the security to record. + */ + public PathId(String name) { + this.name = name; + this.startDate=0; + this.endDate=0; + this.dTime=(float)0.0; + } + + //------------------------------------------------------------------------ + // Methods. + //------------------------------------------------------------------------ + //------------------------------------------------------------------------ + // Accessor methods for class PathId. + // Generated by 'makeJavaAccessor.pl' script. HWY. 20th January 1999. + //------------------------------------------------------------------------ + /** + * Accessor method for private instance variable name. + * + * @return Value of instance variable name. + * @exception DemoException thrown if instance variable name is undefined. + */ + /*public String get_name() { + return(this.name); + }*/ + /** + * Set method for private instance variable name. + * + * @param name the value to set for the instance variable name. + */ + public void set_name(String name) { + this.name = name; + } + /** + * Accessor method for private instance variable startDate. + * + * @return Value of instance variable startDate. + * @exception DemoException thrown if instance variable startDate is undefined. + */ + /*public int get_startDate() { + return(this.startDate); + }*/ + /** + * Set method for private instance variable startDate. + * + * @param startDate the value to set for the instance variable startDate. + */ + public void set_startDate(int startDate) { + this.startDate = startDate; + } + /** + * Accessor method for private instance variable endDate. + * + * @return Value of instance variable endDate. + * @exception DemoException thrown if instance variable endDate is undefined. + */ + /*public int get_endDate() { + return(this.endDate); + }*/ + /** + * Set method for private instance variable endDate. + * + * @param endDate the value to set for the instance variable endDate. + */ + public void set_endDate(int endDate) { + this.endDate = endDate; + } + /** + * Accessor method for private instance variable dTime. + * + * @return Value of instance variable dTime. + * @exception DemoException thrown if instance variable dTime is undefined. + */ + /*public float get_dTime() { + return(this.dTime); + }*/ + /** + * Set method for private instance variable dTime. + * + * @param dTime the value to set for the instance variable dTime. + */ + public void set_dTime(float dTime) { + this.dTime = dTime; + } + //------------------------------------------------------------------------ + /** + * Clone the instance variables in this class, from another instance + * of this class. + * + * @param obj the PathId object from which to copy. + * @exception DemoException thrown if the values to be copied contain + * any undefined objects. + */ + public void copyInstanceVariables(PathId obj) { + this.name = obj.name; + this.startDate = obj.startDate; + this.endDate = obj.endDate; + this.dTime = obj.dTime; + } + /** + * Dumps the contents of the fields, to standard-out, for debugging. + */ + public void dbgDumpFields() { +// dbgPrintln("name=" +this.name); +// dbgPrintln("startDate="+this.startDate); +// dbgPrintln("endDate=" +this.endDate); +// dbgPrintln("dTime=" +this.dTime); + } +} + diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/PriceStock.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/PriceStock.java new file mode 100644 index 00000000..7daed65c --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/PriceStock.java @@ -0,0 +1,150 @@ +/** Banboo Version **/ + +/************************************************************************** + * * + * Java Grande Forum Benchmark Suite - Thread Version 1.0 * + * * + * produced by * + * * + * Java Grande Benchmarking Project * + * * + * at * + * * + * Edinburgh Parallel Computing Centre * + * * + * email: epcc-javagrande@epcc.ed.ac.uk * + * * + * Original version of this code by Hon Yau (hwyau@epcc.ed.ac.uk) * + * * + * This version copyright (c) The University of Edinburgh, 2001. * + * All rights reserved. * + * * + **************************************************************************/ + +/** + * Class to do the work in the Application demonstrator, in particular + * the pricing of the stock path generated by Monte Carlo. The run + * method will generate a single sequence with the required statistics, + * estimate its volatility, expected return rate and final stock price + * value. + * + * @author H W Yau + * @version $Revision: 1.1 $ $Date: 2011/07/13 23:49:52 $ + */ +public class PriceStock{ + + //------------------------------------------------------------------------ + // Instance variables. + //------------------------------------------------------------------------ + /** + * The Monte Carlo path to be generated. + */ + public MonteCarloPath mcPath; + /** + * String identifier for a given task. + */ + //private String taskHeader; + /** + * Random seed from which the Monte Carlo sequence is started. + */ + public long randomSeed; + /** + * Initial stock price value. + */ + public float pathStartValue; + /** + * Object which represents the results from a given computation task. + */ + public ToResult result; + public float expectedReturnRate; + public float volatility; + public float volatility2; + public float finalStockPrice; + public float[] pathValue; + + //------------------------------------------------------------------------ + // Constructors. + //------------------------------------------------------------------------ + /** + * Default constructor. + */ + public PriceStock() { + //this.taskHeader = ""; + this.randomSeed=-1; + this.pathStartValue=(float)0.0; + this.expectedReturnRate=(float)0.0; + this.volatility=(float)0.0; + this.volatility2=(float)0.0; + this.finalStockPrice=(float)0.0; + + mcPath = new MonteCarloPath(); + } + //------------------------------------------------------------------------ + // Methods. + //------------------------------------------------------------------------ + //------------------------------------------------------------------------ + // Methods which implement the Slaveable interface. + //------------------------------------------------------------------------ + /** + * Method which is passed in the initialisation data common to all tasks, + * and then unpacks them for use by this object. + * + * @param obj Object representing data which are common to all tasks. + */ + public void setInitAllTasks(AppDemoRunner obj) { + mcPath.name = obj.name; + mcPath.startDate = obj.startDate; + mcPath.endDate = obj.endDate; + mcPath.dTime = obj.dTime; + mcPath.returnDefinition = obj.returnDefinition; + mcPath.expectedReturnRate = obj.expectedReturnRate; + mcPath.volatility = obj.volatility; + int nTimeSteps = obj.nTimeSteps; + mcPath.nTimeSteps = nTimeSteps; + this.pathStartValue = obj.pathStartValue; + mcPath.pathStartValue = pathStartValue; + mcPath.pathValue = new float[nTimeSteps]; + mcPath.fluctuations = new float[nTimeSteps]; + } + /** + * Method which is passed in the data representing each task, which then + * unpacks it for use by this object. + * + * @param obj Object representing the data which defines a given task. + */ + public void setTask(/*String header, */long randomSeed) { + //this.taskHeader = header; + this.randomSeed = randomSeed; + } + /** + * The business end. Invokes the necessary computation routine, for a + * a given task. + */ + public void run() { + mcPath.computeFluctuationsGaussian(randomSeed); + mcPath.computePathValue(pathStartValue); + RatePath rateP = new RatePath(mcPath); + ReturnPath returnP = rateP.getReturnCompounded(); + returnP.estimatePath(); + expectedReturnRate = returnP.expectedReturnRate; + volatility = returnP.volatility; + volatility2 = returnP.volatility2; + finalStockPrice = rateP.getEndPathValue();//pathValue[rateP.pathValue.length-1]; + pathValue = mcPath.pathValue; + } + /* + * Method which returns the results of a computation back to the caller. + * + * @return An object representing the computed results. + */ + public ToResult getResult() { + //String resultHeader = "Result of task with Header="+taskHeader+": randomSeed="+randomSeed+": pathStartValue="+(int)pathStartValue; + ToResult res = new ToResult(/*resultHeader,*/ + expectedReturnRate, + volatility, + volatility2, + finalStockPrice, + pathValue); + return res; + } +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/RatePath.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/RatePath.java new file mode 100644 index 00000000..f7576982 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/RatePath.java @@ -0,0 +1,483 @@ +/** Banboo Version **/ + +/************************************************************************** + * * + * Java Grande Forum Benchmark Suite - Thread Version 1.0 * + * * + * produced by * + * * + * Java Grande Benchmarking Project * + * * + * at * + * * + * Edinburgh Parallel Computing Centre * + * * + * email: epcc-javagrande@epcc.ed.ac.uk * + * * + * Original version of this code by Hon Yau (hwyau@epcc.ed.ac.uk) * + * * + * This version copyright (c) The University of Edinburgh, 2001. * + * All rights reserved. * + * * + **************************************************************************/ + +/** + * Class for recording the values in the time-dependent path of a security. + * + *

To Do list: + *

    + *
  1. None! + *
+ * + * @author H W Yau + * @version $Revision: 1.1 $ $Date: 2011/07/13 23:49:52 $ + */ +public class RatePath extends PathId { + + //------------------------------------------------------------------------ + // Class variables. + //------------------------------------------------------------------------ + /** + * Class variable to represent the minimal date, whence the stock prices + * appear. Used to trap any potential problems with the data. + */ + public int MINIMUMDATE; + /** + * Class variable for defining what is meant by a small number, small enough + * to cause an arithmetic overflow when dividing. According to the + * Java Nutshell book, the actual range is +/-4.9406564841246544E-324 + */ + public float EPSILON; + + //------------------------------------------------------------------------ + // Instance variables. + //------------------------------------------------------------------------ + /** + * An instance variable, for storing the rate's path values itself. + */ + public float[] pathValue; + /** + * An instance variable, for storing the corresponding date of the datum, + * in 'YYYYMMDD' format. + */ + public int[] pathDate; + /** + * The number of accepted values in the rate path. + */ + public int nAcceptedPathValue; + + //------------------------------------------------------------------------ + // Constructors. + //------------------------------------------------------------------------ + /** + * Constructor, where the user specifies the directory and filename in + * from which the data should be read. + * + * @param String dirName + * @param String filename + * @exception DemoException thrown if there is a problem reading in + * the data file. + */ + public RatePath() { + this.MINIMUMDATE = 19000101; + this.EPSILON= (float)10.0 * (float)(4.9E-324); + this.nAcceptedPathValue = 0; + readRatesFile(); + } + /** + * Constructor, for when the user specifies simply an array of values + * for the path. User must also include information for specifying + * the other characteristics of the path. + * + * @param pathValue the array containing the values for the path. + * @param name the name to attach to the path. + * @param startDate date from which the path is supposed to start, in + * 'YYYYMMDD' format. + * @param startDate date from which the path is supposed to end, in + * 'YYYYMMDD' format. + * @param dTime the time interval between successive path values, in + * fractions of a year. + */ + public RatePath(float[] pathValue, + String name, + int startDate, + int endDate, + float dTime) { + this.MINIMUMDATE = 19000101; + this.EPSILON= (float)10.0 * (float)(4.9E-324); + + this.name = name; + this.startDate = startDate; + this.endDate = endDate; + this.dTime = dTime; + this.pathValue = pathValue; + this.nAcceptedPathValue = pathValue.length; + } + /** + * Constructor, for use by the Monte Carlo generator, when it wishes + * to represent its findings as a RatePath object. + * + * @param mc the Monte Carlo generator object, whose data are to + * be copied over. + * @exception DemoException thrown if there is an attempt to access + * an undefined variable. + */ + public RatePath(MonteCarloPath mc) { + this.MINIMUMDATE = 19000101; + this.EPSILON= (float)10.0 * (float)(4.9E-324); + + // + // Fields pertaining to the parent PathId object: + this.name = mc.name; + this.startDate = mc.startDate; + this.endDate = mc.endDate; + this.dTime = mc.dTime; + // + // Fields pertaining to RatePath object itself. + pathValue=mc.pathValue; + nAcceptedPathValue=mc.nTimeSteps; + // + // Note that currently the pathDate is neither declared, defined, + // nor used in the MonteCarloPath object. + pathDate=new int[nAcceptedPathValue]; + } + /** + * Constructor, for when there is no actual pathValue with which to + * initialise. + * + * @param pathValueLegth the length of the array containing the values + * for the path. + * @param name the name to attach to the path. + * @param startDate date from which the path is supposed to start, in + * 'YYYYMMDD' format. + * @param startDate date from which the path is supposed to end, in + * 'YYYYMMDD' format. + * @param dTime the time interval between successive path values, in + * fractions of a year. + */ + public RatePath(int pathValueLength, + String name, + int startDate, + int endDate, + float dTime) { + this.MINIMUMDATE = 19000101; + this.EPSILON= (float)10.0 * (float)(4.9E-324); + + this.name = name; + this.startDate = startDate; + this.endDate = endDate; + this.dTime = dTime; + this.pathValue = new float[pathValueLength]; + this.nAcceptedPathValue = pathValue.length; + } + //------------------------------------------------------------------------ + // Methods. + //------------------------------------------------------------------------ + /** + * Routine to update this rate path with the values from another rate + * path, via its pathValue array. + * + * @param operandPath the path value array to use for the update. + * @exception DemoException thrown if there is a mismatch between the + * lengths of the operand and target arrays. + */ + public boolean inc_pathValue(float[] operandPath) { + int length = this.pathValue.length; + if( length != operandPath.length ) { + return false; + } + float[] pathvalue = this.pathValue; + for(int i=0; ipathValue. + * + * @return Value of instance variable pathValue. + * @exception DemoException thrown if instance variable pathValue is undefined. + */ + /*public float[] get_pathValue() { + return(this.pathValue); + }*/ + /** + * Set method for private instance variable pathValue. + * + * @param pathValue the value to set for the instance variable pathValue. + */ + public void set_pathValue(float[] pathValue) { + this.pathValue = pathValue; + } + /** + * Accessor method for private instance variable pathDate. + * + * @return Value of instance variable pathDate. + * @exception DemoException thrown if instance variable pathDate is undefined. + */ + /*public int[] get_pathDate() { + return(this.pathDate); + }*/ + /** + * Set method for private instance variable pathDate. + * + * @param pathDate the value to set for the instance variable pathDate. + */ + public void set_pathDate(int[] pathDate) { + this.pathDate = pathDate; + } + //------------------------------------------------------------------------ + /** + * Method to return the terminal value for a given rate path, as used + * in derivative calculations. + * + * @return The last value in the rate path. + */ + public float getEndPathValue() { + return( getPathValue(pathValue.length-1) ); + } + /** + * Method to return the value for a given rate path, at a given index. + * One may want to index this in a more user friendly manner! + * + * @param index the index on which to return the path value. + * @return The value of the path at the designated index. + */ + public float getPathValue(int index) { + return(pathValue[index]); + } + /** + * Method for calculating the returns on a given rate path, via the + * definition for the instantaneous compounded return. + * u_i = \ln{\frac{S_i}{S_{i-1}}} + * + * @return the return, as defined. + * @exception DemoException thrown if there is a problem with the + * calculation. + */ + public ReturnPath getReturnCompounded() { + int length = this.nAcceptedPathValue; + float[] pathvalue = this.pathValue; + if( pathvalue == null || length == 0 ) { + return null; + } + float[] returnPathValue = new float[length]; + returnPathValue[0] = (float)0.0; + for(int i=1; i< length; i++ ) { + returnPathValue[i] = Math.logf(pathvalue[i] / pathvalue[i-1]); + } + + ReturnPath rPath = new ReturnPath(returnPathValue, length, 1); + // + // Copy the PathId information to the ReturnPath object. + rPath.copyInstanceVariables(this); + rPath.estimatePath(); + return(rPath); + } + /** + * Method for calculating the returns on a given rate path, via the + * definition for the instantaneous non-compounded return. + * u_i = \frac{S_i - S_{i-1}}{S_i} + * + * @return the return, as defined. + * @exception DemoException thrown if there is a problem with the + * calculation. + */ + public ReturnPath getReturnNonCompounded() { + int length = this.nAcceptedPathValue; + float[] pathvalue = this.pathValue; + if( pathvalue == null || length == 0 ) { + return null; + } + float[] returnPathValue = new float[length]; + returnPathValue[0] = (float)0.0; + for(int i=1; i< length; i++ ) { + returnPathValue[i] = (pathvalue[i] - pathvalue[i-1])/pathvalue[i]; + } + + ReturnPath rPath = new ReturnPath(returnPathValue, length, 2); + // + // Copy the PathId information to the ReturnPath object. + rPath.copyInstanceVariables(this); + rPath.estimatePath(); + return(rPath); + } + //------------------------------------------------------------------------ + // Private methods. + //------------------------------------------------------------------------ + /** + * Method for reading in data file, in a given format. + * Namely: +
+      881003,0.0000,14.1944,13.9444,14.0832,2200050,0
+      881004,0.0000,14.1668,14.0556,14.1668,1490850,0
+      ...
+      990108,35.8125,36.7500,35.5625,35.8125,4381200,0
+      990111,35.8125,35.8750,34.8750,35.1250,3920800,0
+      990112,34.8750,34.8750,34.0000,34.0625,3577500,0
+      
+ *

Where the fields represent, one believes, the following: + *

    + *
  1. The date in 'YYMMDD' format
  2. + *
  3. Open
  4. + *
  5. High
  6. + *
  7. Low
  8. + *
  9. Last
  10. + *
  11. Volume
  12. + *
  13. Open Interest
  14. + *
+ * One will probably make use of the closing price, but this can be + * redefined via the class variable DATUMFIELD. Note that + * since the read in data are then used to compute the return, this would + * be a good place to trap for zero values in the data, which will cause + * all sorts of problems. + * + * @param dirName the directory in which to search for the data file. + * @param filename the data filename itself. + * @exception DemoException thrown if there was a problem with the data + * file. + */ + private void readRatesFile(){ + // + // Now create an array to store the rates data. + int minimumdate = MINIMUMDATE; + float epsilon = EPSILON; + int nLines = 1000; //200; + int year = 88; + int month = 10; + int day = 3; + this.pathValue = new float[nLines]; + this.pathDate = new int[nLines]; + float[] pathvalue = this.pathValue; + int[] pathdate = this.pathDate; + nAcceptedPathValue=0; + int iLine=0; + /*char[] date = new char[9]; + date[0] = '1'; + date[1] = '9'; + date[2] = (char)(year/10 + '0'); + date[3] = (char)(year%10 + '0'); + date[4] = (char)(month/10 + '0'); + date[5] = (char)(month%10 + '0'); + date[6] = (char)(day/10 + '0'); + date[7] = (char)(day%10 + '0'); + date[8] = '\0';*/ + int aDate = 19881003; + /*for(int di = 0; di < 9; di++) { + aDate = aDate * 10 + (int)date[di]; + }*/ + for(int k = 0; k < 20; /*40;*/ k++ ) { + for(int j = 0; j < 50; /*5;*/ j++) { + /*String date = "19"+String.valueOf(year); + if(month < 10) { + date += "0"; + } + date += String.valueOf(month); + if(day < 10) { + date += "0"; + } + date += String.valueOf(day);*/ + //int aDate = Integer.parseInt(date); + day++; + aDate++; + /*if(date[7] == '9') { + date[7] = '0'; + date[6] = (char)(date[6] + 1); + } else { + date[7] = (char)(date[7] + 1); + }*/ + if(month == 2) { + if(day == 29) { + day = 1; + month++; + /*date[6] = '0'; + date[7] = '1'; + date[5] = '3';*/ + aDate += 72;// - day(29) + 101; + } + } else { + if(day == 31) { + day = 1; + month++; + aDate += 70; + /*date[6] = '0'; + date[7] = '1';*/ + if(month == 13) { + month = 1; + year++; + aDate += 8800; + /*date[4] = '0'; + date[5] = '1'; + if(date[3] == '9') { + if(date[2] == '9') { + if(date[1] == '9') { + date[1] = '0'; + date[0] = (char)(date[0] + 1); + } else { + date[1] = (char)(date[1] + 1); + } + date[2] = '0'; + } else { + date[2] = (char)(date[2] + 1); + } + date[3] = '0'; + } else { + date[3] = (char)(date[3] + 1); + }*/ + } /*else { + if(date[5] == '9') { + date[4] = '1'; + date[5] = '0'; + } else { + date[5] = (char)(date[5] + 1); + } + }*/ + } + } + // + // static float float.parsefloat() method is a feature of JDK1.2! + int tmp = k + j; + float aPathValue = (float)(121.7500 - tmp); + if( (aDate <= minimumdate) /*| (Math.abs(aPathValue) < epsilon)*/ ) { + //System.printString("Skipped erroneous data indexed by date="+date+"."); + } else { + pathdate[iLine] = aDate; + pathvalue[iLine] = aPathValue; + iLine++; + } + } + } + // + // Record the actual number of accepted data points. + nAcceptedPathValue = iLine; + // + // Now to fill in the structures from the 'PathId' class. + this.name = "rate"; + this.startDate = pathdate[0]; + this.endDate = pathdate[iLine-1]; + this.dTime = (float)(1.0/365.0); + } +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/ReturnPath.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/ReturnPath.java new file mode 100644 index 00000000..1f1eaee9 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/ReturnPath.java @@ -0,0 +1,360 @@ +/** Banboo Version **/ + +/************************************************************************** +* * +* Java Grande Forum Benchmark Suite - Thread Version 1.0 * +* * +* produced by * +* * +* Java Grande Benchmarking Project * +* * +* at * +* * +* Edinburgh Parallel Computing Centre * +* * +* email: epcc-javagrande@epcc.ed.ac.uk * +* * +* Original version of this code by Hon Yau (hwyau@epcc.ed.ac.uk) * +* * +* This version copyright (c) The University of Edinburgh, 2001. * +* All rights reserved. * +* * +**************************************************************************/ + + +/** + * Class for representing the returns of a given security. + * + *

To do list: + *

    + *
  1. Define a window over which the mean drift and volatility + * are calculated.
  2. + *
  3. Hash table to reference {DATE}->{pathValue-index}.
  4. + *
+ * + * @author H W Yau + * @version $Revision: 1.1 $ $Date: 2011/07/13 23:49:52 $ + */ +public class ReturnPath extends PathId { + /** + * Flag for indicating one of the return definitions, via: + * u_i = \ln{\frac{S_i}{S_{i-1}}} + * corresponding to the instantaneous compounded return. + */ + public int COMPOUNDED; + + /** + * Flag for indicating one of the return definitions, via: + * u_i = \frac{S_i - S_{i-1}}{S_i} + * corresponding to the instantaneous non-compounded return. + */ + public int NONCOMPOUNDED; + + //------------------------------------------------------------------------ + // Instance variables. + //------------------------------------------------------------------------ + /** + * An instance variable, for storing the return values. + */ + public float[] pathValue; + /** + * The number of accepted values in the rate path. + */ + public int nPathValue; + /** + * Integer flag for indicating how the return was calculated. + */ + public int returnDefinition; + /** + * Value for the expected return rate. + */ + public float expectedReturnRate; + /** + * Value for the volatility, calculated from the return data. + */ + public float volatility; + /** + * Value for the volatility-squared, a more natural quantity + * to use for many of the calculations. + */ + public float volatility2; + /** + * Value for the mean of this return. + */ + public float mean; + /** + * Value for the variance of this return. + */ + public float variance; + + //------------------------------------------------------------------------ + // Constructors. + //------------------------------------------------------------------------ + /** + * Default constructor. + */ + public ReturnPath() { + super(); + + this.COMPOUNDED = 1; + this.NONCOMPOUNDED = 2; + this.nPathValue=-1; + this.returnDefinition = -1; + this.expectedReturnRate = (float)0.0; + this.volatility = (float)0.0; + this.volatility2 = (float)0.0; + this.mean = (float)0.0; + this.variance = (float)0.0; + } + + /** + * Another constructor. + * + * @param pathValue for creating a return path with a precomputed path + * value. Indexed from 1 to nPathArray-1. + * @param nPathValue the number of accepted data points in the array. + * @param returnDefinition to tell this class how the return path values + * were computed. + */ + public ReturnPath(float[] pathValue, + int nPathValue, + int returnDefinition) { + this.pathValue = pathValue; + this.nPathValue = nPathValue; + this.returnDefinition = returnDefinition; + + this.COMPOUNDED = 1; + this.NONCOMPOUNDED = 2; + this.expectedReturnRate = (float)0.0; + this.volatility = (float)0.0; + this.volatility2 = (float)0.0; + this.mean = (float)0.0; + this.variance = (float)0.0; + } + + //------------------------------------------------------------------------ + // Methods. + //------------------------------------------------------------------------ + //------------------------------------------------------------------------ + // Accessor methods for class ReturnPath. + // Generated by 'makeJavaAccessor.pl' script. HWY. 20th January 1999. + //------------------------------------------------------------------------ + /** + * Accessor method for private instance variable pathValue. + * + * @return Value of instance variable pathValue. + * @exception DemoException thrown if instance variable pathValue is undefined. + */ + /*public float[] get_pathValue(){ + return(this.pathValue); + }*/ + /** + * Set method for private instance variable pathValue. + * + * @param pathValue the value to set for the instance variable pathValue. + */ + public void set_pathValue(float[] pathValue) { + this.pathValue = pathValue; + } + /** + * Accessor method for private instance variable nPathValue. + * + * @return Value of instance variable nPathValue. + * @exception DemoException thrown if instance variable nPathValue is undefined. + */ + /*public int get_nPathValue() { + return(this.nPathValue); + }*/ + /** + * Set method for private instance variable nPathValue. + * + * @param nPathValue the value to set for the instance variable nPathValue. + */ + public void set_nPathValue(int nPathValue) { + this.nPathValue = nPathValue; + } + /** + * Accessor method for private instance variable returnDefinition. + * + * @return Value of instance variable returnDefinition. + * @exception DemoException thrown if instance variable returnDefinition is undefined. + */ + /*public int get_returnDefinition() { + return(this.returnDefinition); + }*/ + /** + * Set method for private instance variable returnDefinition. + * + * @param returnDefinition the value to set for the instance variable returnDefinition. + */ + public void set_returnDefinition(int returnDefinition) { + this.returnDefinition = returnDefinition; + } + /** + * Accessor method for private instance variable expectedReturnRate. + * + * @return Value of instance variable expectedReturnRate. + * @exception DemoException thrown if instance variable expectedReturnRate is undefined. + */ + /*public float get_expectedReturnRate() { + return(this.expectedReturnRate); + }*/ + /** + * Set method for private instance variable expectedReturnRate. + * + * @param expectedReturnRate the value to set for the instance variable expectedReturnRate. + */ + public void set_expectedReturnRate(float expectedReturnRate) { + this.expectedReturnRate = expectedReturnRate; + } + /** + * Accessor method for private instance variable volatility. + * + * @return Value of instance variable volatility. + * @exception DemoException thrown if instance variable volatility is undefined. + */ + /*public float get_volatility() { + return(this.volatility); + }*/ + /** + * Set method for private instance variable volatility. + * + * @param volatility the value to set for the instance variable volatility. + */ + public void set_volatility(float volatility) { + this.volatility = volatility; + } + /** + * Accessor method for private instance variable volatility2. + * + * @return Value of instance variable volatility2. + * @exception DemoException thrown if instance variable volatility2 is undefined. + */ + /*public float get_volatility2() { + return(this.volatility2); + }*/ + /** + * Set method for private instance variable volatility2. + * + * @param volatility2 the value to set for the instance variable volatility2. + */ + public void set_volatility2(float volatility2) { + this.volatility2 = volatility2; + } + /** + * Accessor method for private instance variable mean. + * + * @return Value of instance variable mean. + * @exception DemoException thrown if instance variable mean is undefined. + */ + /*public float get_mean() { + return(this.mean); + }*/ + /** + * Set method for private instance variable mean. + * + * @param mean the value to set for the instance variable mean. + */ + public void set_mean(float mean) { + this.mean = mean; + } + /** + * Accessor method for private instance variable variance. + * + * @return Value of instance variable variance. + * @exception DemoException thrown if instance variable variance is undefined. + */ + /*public float get_variance() { + return(this.variance); + }*/ + /** + * Set method for private instance variable variance. + * + * @param variance the value to set for the instance variable variance. + */ + public void set_variance(float variance) { + this.variance = variance; + } + //------------------------------------------------------------------------ + /** + * Method to calculate the expected return rate from the return data, + * using the relationship: + * \mu = \frac{\bar{u}}{\Delta t} + \frac{\sigma^2}{2} + * + * @exception DemoException thrown one tries to obtain an undefined variable. + */ + public void computeExpectedReturnRate() { + this.expectedReturnRate = mean/(float)this.dTime + (float)0.5*volatility2; + } + /** + * Method to calculate volatility and volatility2 + * from the return path data, using the relationship, based on the + * precomputed variance. + * \sigma^2 = s^2\Delta t + * + * @exception DemoException thrown if one of the quantites in the + * computation are undefined. + */ + public void computeVolatility() { + this.volatility2 = this.variance / (float)this.dTime; + this.volatility = Math.sqrtf(volatility2); + } + /** + * Method to calculate the mean of the return, for use by other + * calculations. + * + * @exception DemoException thrown if nPathValue is + * undefined. + */ + public void computeMean() { + float sum = (float) 0.0; + float[] tmpvalue = this.pathValue; + int length = this.nPathValue; + for( int i=1; i < length; i++ ) { + sum += tmpvalue[i]; + } + this.mean = sum / ((float)(length - (float)1.0)); + } + /** + * Method to calculate the variance of the retrun, for use by other + * calculations. + * + * @exception DemoException thrown if the mean or + * nPathValue values are undefined. + */ + public void computeVariance() { + float sum = (float) 0.0; + int length = this.nPathValue; + float[] tmpvalue = this.pathValue; + float tmpmean = this.mean; + for( int i=1; i < length; i++ ) { + sum += (tmpvalue[i] - tmpmean)*(tmpvalue[i] - tmpmean); + } + this.variance = sum / ((float)(length - (float)1.0)); + } + /** + * A single method for invoking all the necessary methods which + * estimate the parameters. + * + * @exception DemoException thrown if there is a problem reading any + * variables. + */ + public void estimatePath() { + computeMean(); + computeVariance(); + computeExpectedReturnRate(); + computeVolatility(); + } + /** + * Dumps the contents of the fields, to standard-out, for debugging. + */ + public void dbgDumpFields() { + super.dbgDumpFields(); +// dbgPrintln("nPathValue=" +this.nPathValue); +// dbgPrintln("expectedReturnRate="+this.expectedReturnRate); +// dbgPrintln("volatility=" +this.volatility); +// dbgPrintln("volatility2=" +this.volatility2); +// dbgPrintln("mean=" +this.mean); +// dbgPrintln("variance=" +this.variance); + } +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/ToResult.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/ToResult.java new file mode 100644 index 00000000..b1cf010f --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/JGFMonteCarlo/ToResult.java @@ -0,0 +1,171 @@ +/** Banboo Version **/ + +/************************************************************************** +* * +* Java Grande Forum Benchmark Suite - Thread Version 1.0 * +* * +* produced by * +* * +* Java Grande Benchmarking Project * +* * +* at * +* * +* Edinburgh Parallel Computing Centre * +* * +* email: epcc-javagrande@epcc.ed.ac.uk * +* * +* Original version of this code by Hon Yau (hwyau@epcc.ed.ac.uk) * +* * +* This version copyright (c) The University of Edinburgh, 2001. * +* All rights reserved. * +* * +**************************************************************************/ + +/** + * Class for defining the results of a task. Currently, this is simply + * the Monte Carlo generate rate path. + * + * @author H W Yau + * @version $Revision: 1.1 $ $Date: 2011/07/13 23:49:52 $ + */ +public class ToResult { + //private String header; + public float expectedReturnRate; + public float volatility; + public float volatility2; + public float finalStockPrice; + public float[] pathValue; + + /** + * Constructor, for the results from a computation. + * + * @param header Simple header string. + * @param pathValue Data computed by the Monte Carlo generator. + */ + public ToResult(/*String header, */ + float expectedReturnRate, + float volatility, + float volatility2, + float finalStockPrice, + float[] pathValue) { + //this.header=header; + this.expectedReturnRate = expectedReturnRate; + this.volatility = volatility; + this.volatility2 = volatility2; + this.finalStockPrice = finalStockPrice; + this.pathValue = pathValue; + } + /** + * Gives a simple string representation of this object. + * + * @return String representation of this object. + */ + /*public String toString(){ + return(header); + }*/ + //------------------------------------------------------------------------ + // Accessor methods for class ToResult. + // Generated by 'makeJavaAccessor.pl' script. HWY. 20th January 1999. + //------------------------------------------------------------------------ + /** + * Accessor method for private instance variable header. + * + * @return Value of instance variable header. + */ + /*public String get_header() { + return(this.header); + }*/ + /** + * Set method for private instance variable header. + * + * @param header the value to set for the instance variable header. + */ + /*public void set_header(String header) { + this.header = header; + }*/ + /** + * Accessor method for private instance variable expectedReturnRate. + * + * @return Value of instance variable expectedReturnRate. + */ + /*public float get_expectedReturnRate() { + return(this.expectedReturnRate); + }*/ + /** + * Set method for private instance variable expectedReturnRate. + * + * @param expectedReturnRate the value to set for the instance variable + * expectedReturnRate. + */ + public void set_expectedReturnRate(float expectedReturnRate) { + this.expectedReturnRate = expectedReturnRate; + } + /** + * Accessor method for private instance variable volatility. + * + * @return Value of instance variable volatility. + */ + /*public float get_volatility() { + return(this.volatility); + }*/ + /** + * Set method for private instance variable volatility. + * + * @param volatility the value to set for the instance variable volatility. + */ + public void set_volatility(float volatility) { + this.volatility = volatility; + } + /** + * Accessor method for private instance variable volatility2. + * + * @return Value of instance variable volatility2. + */ + /*public float get_volatility2() { + return(this.volatility2); + }*/ + /** + * Set method for private instance variable volatility2. + * + * @param volatility2 the value to set for the instance variable volatility2. + */ + public void set_volatility2(float volatility2) { + this.volatility2 = volatility2; + } + /** + * Accessor method for private instance variable finalStockPrice. + * + * @return Value of instance variable finalStockPrice. + */ + /*public float get_finalStockPrice() { + return(this.finalStockPrice); + }*/ + /** + * Set method for private instance variable finalStockPrice. + * + * @param finalStockPrice the value to set for the instance variable + * finalStockPrice. + */ + public void set_finalStockPrice(float finalStockPrice) { + this.finalStockPrice = finalStockPrice; + } + /** + * Accessor method for private instance variable pathValue. + * + * @return Value of instance variable pathValue. + */ + /*public float[] get_pathValue() { + return(this.pathValue); + }*/ + /** + * Set method for private instance variable pathValue. + * + * @param pathValue the value to set for the instance variable pathValue. + */ + public void set_pathValue(float[] pathValue) { + this.pathValue = pathValue; + } + //------------------------------------------------------------------------ +} + + diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/MTree/TestRunner.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/MTree/TestRunner.java new file mode 100644 index 00000000..746ea133 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/MTree/TestRunner.java @@ -0,0 +1,157 @@ +public class TestRunner extends Thread { + + int m_index; + int m_size; + int m_nodenum; + Node m_tree; // The root of a BST + + public TestRunner(int index, + int size, + int nodenum) { + this.m_index = index; + this.m_size = size; + this.m_nodenum = nodenum; + this.m_tree = new Node(); + } + + public void run() { + // Randomly generate new (key, value) pair and insert into the tree + // If have collision, simply throw away the old node + // The tree can hold m_size nodes at most, if it has reached the + // limitation of m_size, then replace the node whose key is the + // closest to the new key. + Random rand = new Random(m_index); + while(this.m_nodenum-- > 0) { + // Generate a new (key, value) pair + int key = Math.abs(rand.nextInt()); + int value = Math.abs(rand.nextInt()); + if(this.m_tree.insert(key, value, !(this.m_size > 0))) { + // insert a new node + this.m_size--; + } + } + } + + class Node { + int m_key; + int m_value; + Node m_left; + Node m_right; + Node m_parent; + + public Node() { + // an empty node + this.m_key = -1; + this.m_value = -1; + this.m_left = null; + this.m_right = null; + this.m_parent = null; + } + + public Node(int key, + int value) { + this.m_key = key; + this.m_value = value; + this.m_left = null; + this.m_right = null; + this.m_parent = null; + } + + public int getKey() { + return this.m_key; + } + + public void setParent(Node p) { + this.m_parent = p; + } + + public void setLeftChild(int key, + int value) { + Node n = new Node(key, value); + this.m_left = n; + n.setParent(this); + } + + public void setRightChild(int key, + int value) { + Node n = new Node(key, value); + this.m_right = n; + n.setParent(this); + } + + public boolean insert(int key, + int value, + boolean candelete) { + if(this.m_key == -1) { + // empty tree + this.m_key = key; + this.m_value = value; + } else { + if(this.m_key == key) { + // collision + replace(key, value); + return false; + } else if(this.m_key > key) { + if(this.m_left == null) { + // no left subtree + if(candelete) { + // replace this node with the new node + replace(key, value); + return false; + } else { + setLeftChild(key, value); + } + } else { + // insert into the left subtree + return this.m_left.insert(key, value, candelete); + } + } else if(this.m_key < key) { + if(this.m_right == null) { + // no right subtree + if(candelete) { + replace(key, value); + return false; + } else { + setRightChild(key, value); + } + } else { + // insert into the right subtree + return this.m_right.insert(key, value, candelete); + } + } + } + return true; + } + + public void replace(int key, + int value) { + Node n = new Node(key, value); + n.m_left = this.m_left; + n.m_right = this.m_right; + n.m_parent = this.m_parent; + if(this.m_parent != null) { + if(this.m_parent.getKey() > key) { + this.m_parent.m_left = n; + } else { + this.m_parent.m_right = n; + } + } + if(this.m_left != null) { + this.m_left.m_parent = n; + } + if(this.m_right != null) { + this.m_right.m_parent = n; + } + } + } + + public static void main(String[] args) { + int threadnum = 62; // 56; + int size = 40000; + int nodenum = size*10; + for(int i = 0; i < threadnum; ++i) { + TestRunner tr = new TestRunner(i, size, nodenum); + tr.run(); + } + } +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Composer.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Composer.java new file mode 100644 index 00000000..08f0322c --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Composer.java @@ -0,0 +1,35 @@ +public class Composer { + + int numCore; + int num_composed; + //int image[][]; + int heightPerCore; + public long result; + public long result1; + + public Composer(int numCore, + int size) { + this.numCore = numCore; + this.num_composed = 0; + heightPerCore = size/this.numCore; + + // set image size + //this.image=new int[size][]; + this.result = 0; + this.result1 = 0; + } + + public boolean compose(TestRunner tr) { + this.num_composed++; + int startidx=0; //heightPerCore * tr.id; + int endidx=this.heightPerCore; //startidx + heightPerCore; + for(int i = startidx; i < endidx; i++) { + //this.image[i] = tr.image[i]; + for(int j = 0; j < this.heightPerCore*this.numCore; j++) { + this.result += tr.image[i][j]; + } + } + this.result1 += tr.checksum; + return this.num_composed == this.numCore; + } +} \ No newline at end of file diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Interval.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Interval.java new file mode 100644 index 00000000..653dd8b8 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Interval.java @@ -0,0 +1,43 @@ +/************************************************************************** + * * + * Java Grande Forum Benchmark Suite - Version 2.0 * + * * + * produced by * + * * + * Java Grande Benchmarking Project * + * * + * at * + * * + * Edinburgh Parallel Computing Centre * + * * + * email: epcc-javagrande@epcc.ed.ac.uk * + * * + * Original version of this code by * + * Florian Doyon (Florian.Doyon@sophia.inria.fr) * + * and Wilfried Klauser (wklauser@acm.org) * + * * + * This version copyright (c) The University of Edinburgh, 1999. * + * All rights reserved. * + * * + **************************************************************************/ + + +public class Interval { + + public final int number; + public final int width; + public final int height; + public final int yfrom; + public final int yto; + public final int total; + + public Interval(int number, int width, int height, int yfrom, int yto, int total) + { + this.number = number; + this.width = width; + this.height = height; + this.yfrom = yfrom; + this.yto = yto; + this.total = total; + } +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Isect.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Isect.java new file mode 100644 index 00000000..5f7aca3f --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Isect.java @@ -0,0 +1,36 @@ +/************************************************************************** + * * + * Java Grande Forum Benchmark Suite - Version 2.0 * + * * + * produced by * + * * + * Java Grande Benchmarking Project * + * * + * at * + * * + * Edinburgh Parallel Computing Centre * + * * + * email: epcc-javagrande@epcc.ed.ac.uk * + * * + * Original version of this code by * + * Florian Doyon (Florian.Doyon@sophia.inria.fr) * + * and Wilfried Klauser (wklauser@acm.org) * + * * + * This version copyright (c) The University of Edinburgh, 1999. * + * All rights reserved. * + * * + **************************************************************************/ + + +public class Isect { + public float t; + public int enter; + public Sphere prim; + public Surface surf; + + public Isect(){ + t=0; + enter=0; + } + +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Light.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Light.java new file mode 100644 index 00000000..05750ede --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Light.java @@ -0,0 +1,38 @@ +/************************************************************************** + * * + * Java Grande Forum Benchmark Suite - Version 2.0 * + * * + * produced by * + * * + * Java Grande Benchmarking Project * + * * + * at * + * * + * Edinburgh Parallel Computing Centre * + * * + * email: epcc-javagrande@epcc.ed.ac.uk * + * * + * Original version of this code by * + * Florian Doyon (Florian.Doyon@sophia.inria.fr) * + * and Wilfried Klauser (wklauser@acm.org) * + * * + * This version copyright (c) The University of Edinburgh, 1999. * + * All rights reserved. * + * * + **************************************************************************/ + + +public class Light +//implements java.io.Serializable +{ + public Vec pos; + public float brightness; + + public Light() { + } + + public Light(float x, float y, float z, float brightness) { + this.pos = new Vec(x, y, z); + this.brightness = brightness; + } +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Primitive.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Primitive.java new file mode 100644 index 00000000..ce0cf56d --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Primitive.java @@ -0,0 +1,43 @@ +/************************************************************************** + * * + * Java Grande Forum Benchmark Suite - Version 2.0 * + * * + * produced by * + * * + * Java Grande Benchmarking Project * + * * + * at * + * * + * Edinburgh Parallel Computing Centre * + * * + * email: epcc-javagrande@epcc.ed.ac.uk * + * * + * Original version of this code by * + * Florian Doyon (Florian.Doyon@sophia.inria.fr) * + * and Wilfried Klauser (wklauser@acm.org) * + * * + * This version copyright (c) The University of Edinburgh, 1999. * + * All rights reserved. * + * * + **************************************************************************/ + + +public class Primitive +{ + public Surface surf; + + public Primitive(){ + surf=new Surface(); + } + + public void setColor(float r, float g, float b) { + surf.color = new Vec(r, g, b); + } + + public /*abstract*/ Vec normal(Vec pnt); + public /*abstract*/ Isect intersect(Ray ry); + public /*abstract*/ String toString(); + public /*abstract*/ Vec getCenter(); + public /*abstract*/ void setCenter(Vec c); + +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Ray.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Ray.java new file mode 100644 index 00000000..7d86ecad --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Ray.java @@ -0,0 +1,47 @@ +/************************************************************************** + * * + * Java Grande Forum Benchmark Suite - Version 2.0 * + * * + * produced by * + * * + * Java Grande Benchmarking Project * + * * + * at * + * * + * Edinburgh Parallel Computing Centre * + * * + * email: epcc-javagrande@epcc.ed.ac.uk * + * * + * Original version of this code by * + * Florian Doyon (Florian.Doyon@sophia.inria.fr) * + * and Wilfried Klauser (wklauser@acm.org) * + * * + * This version copyright (c) The University of Edinburgh, 1999. * + * All rights reserved. * + * * + **************************************************************************/ + + + +final public class Ray { + public Vec P, D; + + public Ray(Vec pnt, Vec dir) { + P = new Vec(pnt.x, pnt.y, pnt.z); + D = new Vec(dir.x, dir.y, dir.z); + D.normalize(); + } + + public Ray() { + P = new Vec(); + D = new Vec(); + } + + public Vec point(float t) { + return new Vec(P.x + D.x * t, P.y + D.y * t, P.z + D.z * t); + } + + public String toString() { + return "{" + P.toString() + " -> " + D.toString() + "}"; + } +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/RayTracer.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/RayTracer.java new file mode 100644 index 00000000..35b114ca --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/RayTracer.java @@ -0,0 +1,407 @@ + +/************************************************************************** + * * Java Grande Forum Benchmark Suite - Version 2.0 * * produced by * * Java + * Grande Benchmarking Project * * at * * Edinburgh Parallel Computing Centre * + * * email: epcc-javagrande@epcc.ed.ac.uk * * Original version of this code by * + * Florian Doyon (Florian.Doyon@sophia.inria.fr) * and Wilfried Klauser + * (wklauser@acm.org) * * This version copyright (c) The University of + * Edinburgh, 1999. * All rights reserved. * * + **************************************************************************/ + +public class RayTracer extends Thread { + + public int image[][]; + + Scene scene; + /** + * Lights for the rendering scene + */ + Light lights[]; + + /** + * Objects (spheres) for the rendering scene + */ + Primitive prim[]; + + /** + * The view for the rendering scene + */ + View view; + + /** + * Temporary ray + */ + // Ray tRay= new Ray(); + // Ray tRay; + + /** + * Alpha channel + */ + // static final int alpha = 255 << 24; + static final int alpha; + + /** + * Null vector (for speedup, instead of new Vec(0,0,0) + */ + // static final Vec voidVec = new Vec(); + // static final Vec voidVec; + + /** + * Temporary vect + */ + // Vec L = new Vec(); + // Vec L; + + /** + * Current intersection instance (only one is needed!) + */ + // Isect inter = new Isect(); + // Isect inter; + + /** + * Height of the Image to be rendered + */ + int height; + + /** + * Width of the Image to be rendered + */ + int width; + + // int datasizes[] = { 150, 500 }; + int datasizes[]; + + public long checksum; + + int size; + + int numobjects; + + public RayTracer() { + // tRay = new Ray(); + alpha = 255 << 24; + // voidVec = new Vec(); + // L = new Vec(); + // inter = new Isect(); + checksum = 0; + datasizes = new int[2]; + datasizes[0] = 150; + datasizes[1] = 500; + numobjects = 0; + width = 0; + height = 0; + size = 0; + } + + /** + * Create and initialize the scene for the rendering picture. + * + * @return The scene just created + */ + + public Scene createScene() { + int x = 0; + int y = 0; + + Scene scene = new Scene(); + + /* create spheres */ + + Primitive p; + int nx = 4; // 6 + int ny = 4; // 6 + int nz = 4; // 6 + for (int i = 0; i < nx; i++) { + for (int j = 0; j < ny; j++) { + for (int k = 0; k < nz; k++) { + float xx = (float) (20.0f / (nx - 1) * i - 10.0); + float yy = (float) (20.0f / (ny - 1) * j - 10.0); + float zz = (float) (20.0f / (nz - 1) * k - 10.0); + + p = new Sphere(new Vec(xx, yy, zz), 3); + // p.setColor(i/(float) (nx-1), j/(float)(ny-1), + // k/(float) (nz-1)); + p.setColor(0, 0, (i + j) / (float) (nx + ny - 2)); + p.surf.shine = (float) 15.0; + p.surf.ks = (float) (1.5 - 1.0); + p.surf.kt = (float) (1.5 - 1.0); + scene.addObject(p); + } + } + } + + /* Creates five lights for the scene */ + scene.addLight(new Light((float) 100, (float) 100, (float) -50, (float) 1.0)); + scene.addLight(new Light((float) -100, (float) 100, (float) -50, (float) 1.0)); + scene.addLight(new Light((float) 100, (float) -100, (float) -50, (float) 1.0)); + scene.addLight(new Light((float) -100, (float) -100, (float) -50, (float) 1.0)); + scene.addLight(new Light((float) 200, (float) 200, (float) 0, (float) 1.0)); + + /* Creates a View (viewing point) for the rendering scene */ + View v = new View(new Vec(x, 20, -30), new Vec(x, y, 0), new Vec(0, 1, + 0),(float) 1.0, (float)(35.0 * 3.14159265 / 180.0), (float)1.0); + /* + * v.from = new Vec(x, y, -30); v.at = new Vec(x, y, -15); v.up = new + * Vec(0, 1, 0); v.angle = 35.0 * 3.14159265 / 180.0; v.aspect = 1.0; + * v.dist = 1.0; + */ + scene.setView(v); + + return scene; + } + + public void setScene(Scene scene) { + // Get the objects count + int nLights = scene.getLights(); + int nObjects = scene.getObjects(); + + lights = new Light[nLights]; + prim = new Primitive[nObjects]; + + // Get the lights + for (int l = 0; l < nLights; l++) { + lights[l] = scene.getLight(l); + } + + // Get the primitives + for (int o = 0; o < nObjects; o++) { + prim[o] = scene.getObject(o); + } + + // Set the view + view = scene.getView(); + } + + public void render(Interval interval) { + + // Screen variables + int pixCounter = 0; // iterator + + Vec viewVec; + viewVec = Vec.sub(view.at, view.from); + viewVec.normalize(); + Vec tmpVec = new Vec(viewVec); + tmpVec.scale(Vec.dot(view.up, viewVec)); + Vec upVec = Vec.sub(view.up, tmpVec); + upVec.normalize(); + Vec leftVec = Vec.cross(view.up, viewVec); + leftVec.normalize(); + float frustrumwidth = (float) (view.dist * Math.tan(view.angle)); + upVec.scale(-frustrumwidth); + leftVec.scale((float) (view.aspect * frustrumwidth)); + + // For each line + for (int y = interval.yfrom; y < interval.yto; y++) { + + float ylen = (float) (2.0 * y) / (float) interval.width -(float) 1.0; + + // For each pixel of the line + int row[]=new int[interval.width]; + int line_checksum=0; + Ray tRay = new Ray(); + Ray r = new Ray(view.from, new Vec(0,0,0)); + + for (int x = 0; x < interval.width; x++) { + Vec col = new Vec(); + + float xlen = (float) (2.0 * x) / (float) interval.width - (float) 1.0; + + r.D = Vec.comb(xlen, leftVec, ylen, upVec); + r.D.add(viewVec); + r.D.normalize(); + + col = trace( 0, (float) 1.0, r,new Isect(),new Ray(),new Vec()); + + // computes the color of the ray + + int red = (int) (col.x * 255.0); + if (red > 255) + red = 255; + int green = (int) (col.y * 255.0); + if (green > 255) + green = 255; + int blue = (int) (col.z * 255.0); + if (blue > 255) + blue = 255; + + checksum += red; + checksum += green; + checksum += blue; + + // Sets the pixels + row[x]= alpha | (red << 16) | (green << 8) | (blue); + } // end for (x) + + image[y-interval.yfrom]=row; + } // end for (y) + + + } + + boolean intersect(Ray r, float maxt, Isect inter) { + Isect tp; + int i, nhits; + + nhits = 0; + inter.t = (float) 1e9; + for (i = 0; i < prim.length; i++) { + // uses global temporary Prim (tp) as temp.object for speedup + tp = prim[i].intersect(r); + if (tp != null && tp.t < inter.t) { + inter.t = tp.t; + inter.prim = tp.prim; + inter.surf = tp.surf; + inter.enter = tp.enter; + nhits++; + } + } + return nhits > 0 ? true : false; + } + + /** + * Checks if there is a shadow + * + * @param r + * The ray + * @return Returns 1 if there is a shadow, 0 if there isn't + */ + int Shadow(Ray r, float tmax, Isect inter) { + if (intersect(r, tmax, inter)) + return 0; + return 1; + } + + /** + * Return the Vector's reflection direction + * + * @return The specular direction + */ + Vec SpecularDirection(Vec I, Vec N) { + Vec r; + r = Vec.comb((float) (1.0 / Math.abs(Vec.dot(I, N))), I, (float) 2.0, N); + r.normalize(); + return r; + } + + /** + * Return the Vector's transmission direction + */ + Vec TransDir(Surface m1, Surface m2, Vec I, Vec N) { + float n1, n2, eta, c1, cs2; + Vec r; + n1 = m1 == null ? (float) 1.0 : m1.ior; + n2 = m2 == null ? (float) 1.0 : m2.ior; + eta = n1 / n2; + c1 = -Vec.dot(I, N); + cs2 =(float) ( 1.0 - eta * eta * (1.0 - c1 * c1)); + if (cs2 < 0.0) + return null; + r = Vec.comb((float) eta, I,(float) ( eta * c1 - Math.sqrt(cs2)), N); + r.normalize(); + return r; + } + + /** + * Returns the shaded color + * + * @return The color in Vec form (rgb) + */ + Vec shade(int level, float weight, Vec P, Vec N, Vec I, Isect hit, + Ray tRay, Vec L) { + float n1, n2, eta, c1, cs2; + Vec r; + Vec tcol; + Vec R; + float t, diff, spec; + Surface surf; + Vec col; + int l; + + col = new Vec(); + surf = hit.surf; + R = new Vec(); + if (surf.shine > 1e-6) { + R = SpecularDirection(I, N); + } + + // Computes the effectof each light + for (l = 0; l < lights.length; l++) { + // L.sub2(lights[l].pos, P); + + L.x = lights[l].pos.x - P.x; + L.y = lights[l].pos.y - P.y; + L.z = lights[l].pos.z - P.z; + + if (Vec.dot(N, L) >= 0.0) { + t = L.normalize(); + + tRay.P = P; + tRay.D = L; + + // Checks if there is a shadow + if (Shadow(tRay, t, hit) > 0) { + diff = Vec.dot(N, L) * surf.kd * lights[l].brightness; + + col.adds(diff, surf.color); + if (surf.shine > 1e-6) { + spec = Vec.dot(R, L); + if (spec > 1e-6) { + spec = (float) (Math.pow(spec, surf.shine)); + col.x += spec; + col.y += spec; + col.z += spec; + } + } + } + } // if + } // for + + tRay.P = P; + if (surf.ks * weight > 1e-3) { + tRay.D = SpecularDirection(I, N); + tcol = trace(level + 1, surf.ks * weight, tRay, hit, tRay, L); + col.adds(surf.ks, tcol); + } + if (surf.kt * weight > 1e-3) { + if (hit.enter > 0) + tRay.D = TransDir(null, surf, I, N); + else + tRay.D = TransDir(surf, null, I, N); + tcol = trace(level + 1, surf.kt * weight, tRay, hit, tRay, L); + col.adds(surf.kt, tcol); + } + + // garbaging... + tcol = null; + surf = null; + + return col; + } + + /** + * Launches a ray + */ + Vec trace(int level, float weight, Ray r, Isect inter, Ray tRay, Vec L) { + + Vec P, N; + boolean hit; + + // Checks the recursion level + if (level > 6) { + return new Vec(); + } + hit = intersect(r, (float) 1e6, inter); + if (hit) { + P = r.point(inter.t); + N = inter.prim.normal(P); + if (Vec.dot(r.D, N) >= 0.0) { + N.negate(); + } + return shade(level, weight, P, N, r.D, inter, tRay, L); + } + + // no intersection --> col = 0,0,0 + return new Vec(0, 0, 0); + } + +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Scene.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Scene.java new file mode 100644 index 00000000..38b3e409 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Scene.java @@ -0,0 +1,89 @@ +/************************************************************************** + * * + * Java Grande Forum Benchmark Suite - Version 2.0 * + * * + * produced by * + * * + * Java Grande Benchmarking Project * + * * + * at * + * * + * Edinburgh Parallel Computing Centre * + * * + * email: epcc-javagrande@epcc.ed.ac.uk * + * * + * Original version of this code by * + * Florian Doyon (Florian.Doyon@sophia.inria.fr) * + * and Wilfried Klauser (wklauser@acm.org) * + * * + * This version copyright (c) The University of Edinburgh, 1999. * + * All rights reserved. * + * * + **************************************************************************/ + + + +//import java.util.Vector; + +public class Scene +//implements java.io.Serializable +{ + public final Vector lights; + public final Vector objects; + private View view; + + public Scene () + { + this.lights = new Vector (); + this.objects = new Vector (); + } + + public void addLight(Light l) + { + this.lights.addElement(l); + } + + public void addObject(Primitive object) + { + this.objects.addElement(object); + } + + public void setView(View view) + { + this.view = view; + } + + public View getView() + { + return this.view; + } + + public Light getLight(int number) + { + return (Light) this.lights.elementAt(number); + } + + public Primitive getObject(int number) + { + return (Primitive) objects.elementAt(number); + } + + public int getLights() + { + return this.lights.size(); + } + + public int getObjects() + { + return this.objects.size(); + } + + public void setObject(Primitive object, int pos) + { + this.objects.setElementAt(object, pos); + } +} + + + + diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Sphere.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Sphere.java new file mode 100644 index 00000000..24957b77 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Sphere.java @@ -0,0 +1,97 @@ +/************************************************************************** + * * + * Java Grande Forum Benchmark Suite - Version 2.0 * + * * + * produced by * + * * + * Java Grande Benchmarking Project * + * * + * at * + * * + * Edinburgh Parallel Computing Centre * + * * + * email: epcc-javagrande@epcc.ed.ac.uk * + * * + * Original version of this code by * + * Florian Doyon (Florian.Doyon@sophia.inria.fr) * + * and Wilfried Klauser (wklauser@acm.org) * + * * + * This version copyright (c) The University of Edinburgh, 1999. * + * All rights reserved. * + * * + **************************************************************************/ + + + +public class Sphere extends Primitive +//implements java.io.Serializable +{ + Vec c; + float r, r2; +//Vec v,b; // temporary vecs used to minimize the memory load + + + public Sphere(Vec center, float radius) { + super(); + c = center; + r = radius; + r2 = r*r; +// v=new Vec(); +// b=new Vec(); + } + + public float dot(float x1, float y1, float z1, float x2, float y2, float z2){ + + return x1*x2 + y1*y2 + z1*z2; + + } + + public Isect intersect(Ray ry) { + + + float b, disc, t; + Isect ip; + + float x=c.x-ry.P.x; + float y=c.y-ry.P.y; + float z=c.z-ry.P.z; + + b=dot( x, y, z, ry.D.x, ry.D.y, ry.D.z); + disc = (float) (b*b -dot(x,y,z,x,y,z) + r2); + if (disc < 0.0) { + return null; + } + disc = (float) Math.sqrtf((float)disc); + t = (b - disc < 1e-6) ? b + disc : b - disc; + if (t < 1e-6) { + return null; + } + ip = new Isect(); + ip.t = t; + ip.enter = dot(x,y,z,x,y,z) > r2 + 1e-6 ? 1 : 0; +// ip.enter = Vec.dot(v, v) > r2 + 1e-6 ? 1 : 0; + ip.prim = this; + ip.surf = surf; + return ip; + + } + + public Vec normal(Vec p) { + Vec r; + r = Vec.sub(p, c); + r.normalize(); + return r; + } + + public String toString() { + return "Sphere {" + c.toString() + "," + r + "}"; + } + + public Vec getCenter() { + return c; + } + public void setCenter(Vec c) { + this.c = c; + } +} + diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Surface.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Surface.java new file mode 100644 index 00000000..2bdc20ee --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Surface.java @@ -0,0 +1,52 @@ +/************************************************************************** + * * + * Java Grande Forum Benchmark Suite - Version 2.0 * + * * + * produced by * + * * + * Java Grande Benchmarking Project * + * * + * at * + * * + * Edinburgh Parallel Computing Centre * + * * + * email: epcc-javagrande@epcc.ed.ac.uk * + * * + * Original version of this code by * + * Florian Doyon (Florian.Doyon@sophia.inria.fr) * + * and Wilfried Klauser (wklauser@acm.org) * + * * + * This version copyright (c) The University of Edinburgh, 1999. * + * All rights reserved. * + * * + **************************************************************************/ + + + +public class Surface +//implements java.io.Serializable +{ + public Vec color; + public float kd; + public float ks; + public float shine; + public float kt; + public float ior; + public boolean isnull; + + public Surface() { + color = new Vec(1, 0, 0); + kd =(float) 1.0; + ks = (float) 0.0; + shine = (float) 0.0; + kt = (float) 0.0; + ior = (float) 1.0; + isnull=false; + } + + public String toString() { + return "Surface { color=" + color + "}"; + } +} + + diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/TestRunner.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/TestRunner.java new file mode 100644 index 00000000..46ff50c2 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/TestRunner.java @@ -0,0 +1,92 @@ +/************************************************************************** + * * Java Grande Forum Benchmark Suite - Version 2.0 * * produced by * * Java + * Grande Benchmarking Project * * at * * Edinburgh Parallel Computing Centre * + * * email: epcc-javagrande@epcc.ed.ac.uk * * * This version copyright (c) The + * University of Edinburgh, 1999. * All rights reserved. * * + **************************************************************************/ + +public class TestRunner extends RayTracer { + + int numCore; + public int id; + + public TestRunner(int id, + int numCore, + int size, + Scene scene) { + super(); + this.id = id; + this.numCore = numCore; + this.size = size; + + // create the objects to be rendered + this.scene = scene; //createScene(); + + // set image size + width=size; + height=size; + // get lights, objects etc. from scene. + setScene(this.scene); + + numobjects = this.scene.getObjects(); + /*this.image=new int[size][]; + + // get lights, objects etc. from scene. + setScene(scene); + + numobjects = scene.getObjects();*/ + } + + public void init() { + this.image=new int[this.size/this.numCore][]; + } + + public void JGFvalidate() { + // long refval[] = {2676692,29827635}; + // long refval[] = new long[2]; + // refval[0] = 2676692; + // refval[1] = 29827635; + // long dev = checksum - refval[size]; + // if (dev != 0) { + // System.out.println("Validation failed"); + // System.out.println("Pixel checksum = " + checksum); + // System.out.println("Reference value = " + refval[size]); + // } + } + + public void JGFtidyup() { + // scene = null; + // lights = null; + // prim = null; + // tRay = null; + // inter = null; + // System.gc(); + } + + public void run() { + this.init(); + + int heightPerCore=height/numCore; + int startidx=heightPerCore * this.id; + int endidx=startidx + heightPerCore; + Interval interval = new Interval(0, width, height, startidx, endidx, 1); + render(interval); + + //System.out.println("CHECKSUM="+checksum); + + } + public static void main(String[] args) { + int threadnum = 62; // 56; + int size = threadnum * 25; + Composer comp = new Composer(threadnum, size); + RayTracer rt = new RayTracer(); + Scene scene = rt.createScene(); + for(int i = 0; i < threadnum; ++i) { + TestRunner tr = new TestRunner(i, threadnum, size, scene); + tr.run(); + if(comp.compose(tr)) { + long r = comp.result; + } + } + } +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Vec.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Vec.java new file mode 100644 index 00000000..1daa0f06 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/Vec.java @@ -0,0 +1,181 @@ +/************************************************************************** + * * + * Java Grande Forum Benchmark Suite - Version 2.0 * + * * + * produced by * + * * + * Java Grande Benchmarking Project * + * * + * at * + * * + * Edinburgh Parallel Computing Centre * + * * + * email: epcc-javagrande@epcc.ed.ac.uk * + * * + * Original version of this code by * + * Florian Doyon (Florian.Doyon@sophia.inria.fr) * + * and Wilfried Klauser (wklauser@acm.org) * + * * + * This version copyright (c) The University of Edinburgh, 1999. * + * All rights reserved. * + * * + **************************************************************************/ + + + + +/** + * This class reflects the 3d vectors used in 3d computations + */ +public class Vec +//implements java.io.Serializable +{ + + /** + * The x coordinate + */ + public float x; + + /** + * The y coordinate + */ + public float y; + + /** + * The z coordinate + */ + public float z; + + /** + * Constructor + * @param a the x coordinate + * @param b the y coordinate + * @param c the z coordinate + */ + public Vec(float a, float b, float c) { + x = a; + y = b; + z = c; + } + + /** + * Copy constructor + */ + public Vec(Vec a) { + x = a.x; + y = a.y; + z = a.z; + } + /** + * Default (0,0,0) constructor + */ + public Vec() { + x = (float) 0.0; + y = (float) 0.0; + z = (float) 0.0; + } + + /** + * Add a vector to the current vector + * @param: a The vector to be added + */ + public final void add(Vec a) { + x+=a.x; + y+=a.y; + z+=a.z; + } + + /** + * adds: Returns a new vector such as + * new = sA + B + */ + public static Vec adds(float s, Vec a, Vec b) { + return new Vec(s * a.x + b.x, s * a.y + b.y, s * a.z + b.z); + } + + /** + * Adds vector such as: + * this+=sB + * @param: s The multiplier + * @param: b The vector to be added + */ + public final void adds(float s,Vec b){ + x+=s*b.x; + y+=s*b.y; + z+=s*b.z; + } + + /** + * Substracs two vectors + */ + public static Vec sub(Vec a, Vec b) { + return new Vec(a.x - b.x, a.y - b.y, a.z - b.z); + } + + /** + * Substracts two vects and places the results in the current vector + * Used for speedup with local variables -there were too much Vec to be gc'ed + * Consumes about 10 units, whether sub consumes nearly 999 units!! + * cf thinking in java p. 831,832 + */ + public final void sub2(Vec a,Vec b) { + this.x=a.x-b.x; + this.y=a.y-b.y; + this.z=a.z-b.z; + } + + public static Vec mult(Vec a, Vec b) { + return new Vec(a.x * b.x, a.y * b.y, a.z * b.z); + } + + public static Vec cross(Vec a, Vec b) { + return + new Vec(a.y*b.z - a.z*b.y, + a.z*b.x - a.x*b.z, + a.x*b.y - a.y*b.x); + } + + public static float dot(Vec a, Vec b) { + return a.x*b.x + a.y*b.y + a.z*b.z; + } + + public static Vec comb(float a, Vec A, float b, Vec B) { + return + new Vec(a * A.x + b * B.x, + a * A.y + b * B.y, + a * A.z + b * B.z); + } + + public final void comb2(float a,Vec A,float b,Vec B) { + x=a * A.x + b * B.x; + y=a * A.y + b * B.y; + z=a * A.z + b * B.z; + } + + public final void scale(float t) { + x *= t; + y *= t; + z *= t; + } + + public final void negate() { + x = -x; + y = -y; + z = -z; + } + + public final float normalize() { + float len; + len =(float) Math.sqrt(x*x + y*y + z*z); + if (len > 0.0) { + x /= len; + y /= len; + z /= len; + } + return len; + } + + public final String toString() { + return "<" + x + "," + y + "," + z + ">"; + } +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/View.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/View.java new file mode 100644 index 00000000..f22e4ce9 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/View.java @@ -0,0 +1,54 @@ +/************************************************************************** + * * + * Java Grande Forum Benchmark Suite - Version 2.0 * + * * + * produced by * + * * + * Java Grande Benchmarking Project * + * * + * at * + * * + * Edinburgh Parallel Computing Centre * + * * + * email: epcc-javagrande@epcc.ed.ac.uk * + * * + * Original version of this code by * + * Florian Doyon (Florian.Doyon@sophia.inria.fr) * + * and Wilfried Klauser (wklauser@acm.org) * + * * + * This version copyright (c) The University of Edinburgh, 1999. * + * All rights reserved. * + * * + **************************************************************************/ + + + +public class View +//implements java.io.Serializable +{ + /* public Vec from; + public Vec at; + public Vec up; + public float dist; + public float angle; + public float aspect;*/ + public final Vec from; + public final Vec at; + public final Vec up; + public final float dist; + public final float angle; + public final float aspect; + + public View (Vec from, Vec at, Vec up, float dist, float angle, float aspect) + { + this.from = from; + this.at = at; + this.up = up; + this.dist = dist; + this.angle = angle; + this.aspect = aspect; + } +} + + + diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/makefile b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/makefile new file mode 100644 index 00000000..879d1004 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/RayTracer/makefile @@ -0,0 +1,30 @@ +#raytracer +PROGRAM=test + +SOURCE_FILES=test.java + +BUILDSCRIPT=~/eclipse/workspaces/irvine_sep09/Robust/src/buildscript + +USEMLP= -mlp 8 2 # -mlpdebug # use to turn mlp on and off and make sure rest of build not broken +BSFLAGS= -32bit -nooptimize -mainclass test -debug -garbagestats +OWNERSHIP= -ownership -ownallocdepth 1 -enable-assertions -methodeffects -flatirusermethods -ownwritedots final -ownaliasfile aliases.txt + +default: + ../../../buildscript -nojava $(USEMLP) $(BSFLAGS) $(OWNERSHIP) -o $(PROGRAM) $(SOURCE_FILES) + +single: + ../../../buildscript $(BSFLAGS) -o $(PROGRAM) $(SOURCE_FILES) + +java: + ../../../buildscript $(USEMLP) $(BSFLAGS) $(OWNERSHIP) -o $(PROGRAM) $(SOURCE_FILES) + +clean: + rm -f $(PROGRAM).bin + rm -fr tmpbuilddirectory + rm -f *~ + rm -f *.dot + rm -f *.png + rm -f *.txt + rm -f aliases.txt + rm -f mlpReport*txt + rm -f results*txt diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/Body.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/Body.java new file mode 100644 index 00000000..bc341f49 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/Body.java @@ -0,0 +1,242 @@ + +/** + * A class used to representing particles in the N-body simulation. + **/ +final class Body extends Node +{ + public MathVector vel; + public MathVector acc; + public MathVector newAcc; + public double phi; + + public Body next; + public Body procNext; + + /** + * Create an empty body. + **/ + public Body() + { + super(); + vel = new MathVector(); + acc = new MathVector(); + newAcc = new MathVector(); + phi = 0.0; + next = null; + procNext = null; + } + + /** + * Set the next body in the list. + * @param n the body + **/ + public void setNext(Body n) + { + next = n; + } + + /** + * Get the next body in the list. + * @return the next body + **/ + public Body getNext() + { + return next; + } + + /** + * Set the next body in the list. + * @param n the body + **/ + public void setProcNext(Body n) + { + procNext = n; + } + + /** + * Get the next body in the list. + * @return the next body + **/ + public Body getProcNext() + { + return procNext; + } + + /** + * Enlarge cubical "box", salvaging existing tree structure. + * @param tree the root of the tree. + * @param nsteps the current time step + **/ + public void expandBox(Tree tree, int nsteps) + { + MathVector rmid = new MathVector(); + + boolean inbox = icTest(tree); + while (!inbox) { + double rsize = tree.rsize; + rmid.addScalar(tree.rmin, 0.5 * rsize); + + for (int k = 0; k < rmid.NDIM; k++) { + if (pos.value(k) < rmid.value(k)) { + double rmin = tree.rmin.value(k); + tree.rmin.value(k, rmin - rsize); + } + } + tree.rsize = 2.0 * rsize; + if (tree.root != null) { + MathVector ic = tree.intcoord(rmid); + if (ic == null) { + //throw new Error("Value is out of bounds"); + System.exit(-2); + } + int k = oldSubindex(ic, IMAX >> 1); + Cell newt = new Cell(); + newt.subp[k] = tree.root; + tree.root = newt; + inbox = icTest(tree); + } + } + } + + /** + * Check the bounds of the body and return true if it isn't in the + * correct bounds. + **/ + public boolean icTest(Tree tree) + { + double pos0 = pos.value(0); + double pos1 = pos.value(1); + double pos2 = pos.value(2); + + // by default, it is in bounds + boolean result = true; + + double xsc = (pos0 - tree.rmin.value(0)) / tree.rsize; + if (!(0.0 < xsc && xsc < 1.0)) { + result = false; + } + + xsc = (pos1 - tree.rmin.value(1)) / tree.rsize; + if (!(0.0 < xsc && xsc < 1.0)) { + result = false; + } + + xsc = (pos2 - tree.rmin.value(2)) / tree.rsize; + if (!(0.0 < xsc && xsc < 1.0)) { + result = false; + } + + return result; + } + + /** + * Descend Tree and insert particle. We're at a body so we need to + * create a cell and attach this body to the cell. + * @param p the body to insert + * @param xpic + * @param l + * @param tree the root of the data structure + * @return the subtree with the new body inserted + **/ + public Node loadTree(Body p, MathVector xpic, int l, Tree tree) + { + // create a Cell + Cell retval = new Cell(); + int si = subindex(tree, l); + // attach this Body node to the cell + retval.subp[si] = this; + + // move down one level + si = oldSubindex(xpic, l); + Node rt = retval.subp[si]; + if (rt != null) { + if(rt instanceof Body) { + Body rtb = (Body) rt; + retval.subp[si] = rtb.loadTree(p, xpic, l >> 1, tree); + } else if(rt instanceof Cell){ + Cell rtc = (Cell) rt; + retval.subp[si] = rtc.loadTree(p, xpic, l >> 1, tree); + } + } else { + retval.subp[si] = p; + } + return retval; + } + + /** + * Descend tree finding center of mass coordinates + * @return the mass of this node + **/ + public double hackcofm() + { + return mass; + } + + /** + * Determine which subcell to select. + * Combination of intcoord and oldSubindex. + * @param t the root of the tree + **/ + public int subindex(Tree tree, int l) + { + MathVector xp = new MathVector(); + + double xsc = (pos.value(0) - tree.rmin.value(0)) / tree.rsize; + xp.value(0, Math.floor(1073741824/*IMAX*/ * xsc)); + + xsc = (pos.value(1) - tree.rmin.value(1)) / tree.rsize; + xp.value(1, Math.floor(1073741824/*IMAX*/ * xsc)); + + xsc = (pos.value(2) - tree.rmin.value(2)) / tree.rsize; + xp.value(2, Math.floor(1073741824/*IMAX*/ * xsc)); + + int i = 0; + for (int k = 0; k < xp.NDIM; k++) { + if (((int)xp.value(k) & l) != 0) { + i += 8/*Cell.NSUB*/ >> (k + 1); + } + } + return i; + } + + /** + * Evaluate gravitational field on the body. + * The original olden version calls a routine named "walkscan", + * but we use the same name that is in the Barnes code. + **/ + public void hackGravity(double rsize, Node root) + { + MathVector pos0 = (MathVector)pos.clone(); + + HG hg = new HG(this, pos); + if(root instanceof Body) { + Body rootb = (Body)root; + hg = rootb.walkSubTree(rsize * rsize, hg); + } else if(root instanceof Cell) { + Cell rootc = (Cell)root; + hg = rootc.walkSubTree(rsize * rsize, hg); + } + this.phi = hg.phi0; + this.newAcc = hg.acc0; + } + + /** + * Recursively walk the tree to do hackwalk calculation + **/ + public HG walkSubTree(double dsq, HG hg) + { + if (this != hg.pskip) + hg = gravSub(hg); + return hg; + } + + /** + * Return a string represenation of a body. + * @return a string represenation of a body. + **/ + /*public String toString() + { + return "Body " + super.toString(); + }*/ + +} \ No newline at end of file diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/Cell.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/Cell.java new file mode 100644 index 00000000..4e83ee96 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/Cell.java @@ -0,0 +1,132 @@ + +/** + * A class used to represent internal nodes in the tree + **/ +final class Cell extends Node +{ + // subcells per cell + public final int NSUB; // 1 << NDIM + + /** + * The children of this cell node. Each entry may contain either + * another cell or a body. + **/ + public Node[] subp; + public Cell next; + + public Cell() + { + super(); + NSUB = 8; + subp = new Node[NSUB]; + next = null; + } + + /** + * Descend Tree and insert particle. We're at a cell so + * we need to move down the tree. + * @param p the body to insert into the tree + * @param xpic + * @param l + * @param tree the root of the tree + * @return the subtree with the new body inserted + **/ + public Node loadTree(Body p, MathVector xpic, int l, Tree tree) + { + // move down one level + int si = oldSubindex(xpic, l); + Node rt = subp[si]; + if (rt != null) { + if(rt instanceof Body) { + Body rtb = (Body)rt; + subp[si] = rtb.loadTree(p, xpic, l >> 1, tree); + } else if(rt instanceof Cell) { + Cell rtc = (Cell)rt; + subp[si] = rtc.loadTree(p, xpic, l >> 1, tree); + } + } else { + subp[si] = p; + } + return this; + } + + /** + * Descend tree finding center of mass coordinates + * @return the mass of this node + **/ + public double hackcofm() + { + double mq = 0.0; + MathVector tmpPos = new MathVector(); + MathVector tmpv = new MathVector(); + for (int i=0; i < NSUB; i++) { + Node r = subp[i]; + if (r != null) { + double mr = 0.0; + if(r instanceof Body) { + Body rb = (Body)r; + mr = rb.hackcofm(); + } else if(r instanceof Cell) { + Cell rc = (Cell)r; + mr = rc.hackcofm(); + } + mq = mr + mq; + tmpv.multScalar(r.pos, mr); + tmpPos.addition(tmpv); + } + } + mass = mq; + pos = tmpPos; + pos.divScalar(mass); + + return mq; + } + + /** + * Recursively walk the tree to do hackwalk calculation + **/ + public HG walkSubTree(double dsq, HG hg) + { + if (subdivp(dsq, hg)) { + for (int k = 0; k < this.NSUB; k++) { + Node r = subp[k]; + if (r != null) { + if(r instanceof Body) { + Body rb = (Body)r; + hg = rb.walkSubTree(dsq / 4.0, hg); + } else if(r instanceof Cell) { + Cell rc = (Cell)r; + hg = rc.walkSubTree(dsq / 4.0, hg); + } + } + } + } else { + hg = gravSub(hg); + } + return hg; + } + + /** + * Decide if the cell is too close to accept as a single term. + * @return true if the cell is too close. + **/ + public boolean subdivp(double dsq, HG hg) + { + MathVector dr = new MathVector(); + dr.subtraction(pos, hg.pos0); + double drsq = dr.dotProduct(); + + // in the original olden version drsp is multiplied by 1.0 + return (drsq < dsq); + } + + /** + * Return a string represenation of a cell. + * @return a string represenation of a cell. + **/ + /*public String toString() + { + return "Cell " + super.toString(); + }*/ + +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/Makefile b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/Makefile new file mode 100644 index 00000000..2efba011 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/Makefile @@ -0,0 +1,3 @@ +BMARK = BH +PARMS = -b 4096 -m +include ../Makefile.common \ No newline at end of file diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/MathVector.class b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/MathVector.class new file mode 100644 index 0000000000000000000000000000000000000000..a13c3079aa4ed8123d89d380d5a3cd986facf0d9 GIT binary patch literal 2758 zcmb7E-EUKM7=F)3*R6CPY%A=mY-7`%wPRaBr#K{08bXt9n9Xd8OU&sxb(D5J(4OuB z;~hc0#CR!&n8?D7ppgvF%y@w@24f<|Yy7~(nD_@QB0lf$v^`z7CiUk0KF<4lpXYtv zkMI7yvq3}$={X;HX|jn_ity*4mk#-`PWtF6dfH1<5~;J%*o;I{3|mvTb&2HHq7pS6 zNo7;^QHd07bOFDPS!PnA)_5wLoGq**lDU`lLG*fw7&l=cnX9-ikk+bso^81!l*2pDSl382N zykMFVRbI>&5)uU}EM_YBc2?X+U3N`SsmyfVD&&mh@f7E$)s<_Uv*0H`HT$WNn*8Kr zeVeyP>ZND=^ei2gsI59@An9JQSBRHCmlMf~jz(z!b>&6T$+Vl@iyaWK1_%OBGrlc2 zor9f>H5^(eDb#S2+&s7cRO0 z(M=uHLqY1LVXPtS+F;X0@?&7iUfL}YZBnOzZ!f|h0yx9By6_T^83JnI+YaYM{rC<5 zVi277<4=ch!~C=OqhOun$rBH|^q=o@=m)}}&wHgWGIv2n41b1i;EgO0dZ+>W z5L5~SZH)Tp0BKmqX+i|xC;1U|GW|`2h+3dMMe_Yc@?IfN))pi&B?Tg1@UdxgBMYosC}9Lz&EA&y#c)Y1%6 z5QkQ#H&Mmsk*Bw|`sRx1N2xo$7vS520EUz)HJ~~nh&l+U978~jXuwdx|MzN)i|F&W zA@xP{%)2gzf-JB+`|IIv)!=^#{NDrrOW^;$>zgyo{D&|D9R5qC1hkwetJ6Iq*A+dCUt=%XCYuA~9i&Lqbl9sadW%rj3|L)sNZ^1U>lko1 zXcFrbedZGIaI}+v)yN$9Uxp!FVyPgd+_}|df^^=;fJlhxfjOj@m;IW?!)&_@O>Y?f8Or< g!2g*O5P!!x@c>o-3lx5Us{hT!D9wp+(UlYb0p6+CMF0Q* literal 0 HcmV?d00001 diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/MathVector.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/MathVector.java new file mode 100644 index 00000000..e81e8266 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/MathVector.java @@ -0,0 +1,241 @@ + +/** + * A class representing a three dimensional vector that implements + * several math operations. To improve speed we implement the + * vector as an array of doubles rather than use the exising + * code in the java.util.Vector class. + **/ +class MathVector +{ + /** + * The number of dimensions in the vector + **/ + public final int NDIM; + /** + * An array containing the values in the vector. + **/ + private double data[]; + + /** + * Construct an empty 3 dimensional vector for use in Barnes-Hut algorithm. + **/ + public MathVector() + { + NDIM = 3; + data = new double[NDIM]; + for (int i=0; i < NDIM; i++) { + data[i] = 0.0; + } + } + + public MathVector(boolean x) { + NDIM = 3; + data = null; + } + + /** + * Create a copy of the vector. + * @return a clone of the math vector + **/ + public Object clone() + { + MathVector v = new MathVector(); + v.data = new double[NDIM]; + for (int i = 0; i < NDIM; i++) { + v.data[i] = data[i]; + } + return v; + } + + /** + * Return the value at the i'th index of the vector. + * @param i the vector index + * @return the value at the i'th index of the vector. + **/ + public double value(int i) + { + return data[i]; + } + + /** + * Set the value of the i'th index of the vector. + * @param i the vector index + * @param v the value to store + **/ + public void value(int i, double v) + { + data[i] = v; + } + + /** + * Set one of the dimensions of the vector to 1.0 + * param j the dimension to set. + **/ + public void unit(int j) + { + for (int i=0; i < NDIM; i++) { + data[i] = (i == j ? 1.0 : 0.0); + } + } + + /** + * Add two vectors and the result is placed in this vector. + * @param u the other operand of the addition + **/ + public void addition(MathVector u) + { + for (int i=0; i < NDIM; i++) { + data[i] += u.data[i]; + } + } + + /** + * Subtract two vectors and the result is placed in this vector. + * This vector contain the first operand. + * @param u the other operand of the subtraction. + **/ + public void subtraction(MathVector u) + { + for (int i=0; i < NDIM; i++) { + data[i] -= u.data[i]; + } + } + + /** + * Subtract two vectors and the result is placed in this vector. + * @param u the first operand of the subtraction. + * @param v the second opernd of the subtraction + **/ + public void subtraction(MathVector u, MathVector v) + { + for (int i=0; i < NDIM; i++) { + data[i] = u.data[i] - v.data[i]; + } + } + + /** + * Multiply the vector times a scalar. + * @param s the scalar value + **/ + public void multScalar(double s) + { + for (int i=0; i < NDIM; i++) { + data[i] *= s; + } + } + + /** + * Multiply the vector times a scalar and place the result in this vector. + * @param u the vector + * @param s the scalar value + **/ + public void multScalar(MathVector u, double s) + { + for (int i=0; i < NDIM; i++) { + data[i] = u.data[i] * s; + } + } + + /** + * Divide each element of the vector by a scalar value. + * @param s the scalar value. + **/ + public void divScalar(double s) + { + for (int i=0; i < NDIM; i++) { + data[i] /= s; + } + } + + /** + * Return the dot product of a vector. + * @return the dot product of a vector. + **/ + public double dotProduct() + { + double s = 0.0; + for (int i=0; i < NDIM; i++) { + s += data[i] * data[i]; + } + return s; + } + + public double absolute() + { + double tmp = 0.0; + for (int i = 0; i < NDIM; i++) { + tmp += data[i] * data[i]; + } + return Math.sqrt(tmp); + } + + public double distance(MathVector v) + { + double tmp = 0.0; + for (int i = 0; i < NDIM; i++) { + tmp += (data[i] - v.data[i]) * (data[i] - v.data[i]); + } + return Math.sqrt(tmp); + } + + public void crossProduct(MathVector u, MathVector w) + { + data[0] = u.data[1] * w.data[2] - u.data[2]*w.data[1]; + data[1] = u.data[2] * w.data[0] - u.data[0]*w.data[2]; + data[2] = u.data[0] * w.data[1] - u.data[1]*w.data[0]; + } + + public void incrementalAdd(MathVector u) + { + for (int i = 0; i < NDIM; i++) { + data[i] += u.data[i]; + } + } + + public void incrementalSub(MathVector u) + { + for (int i = 0; i < NDIM; i++) { + data[i] -= u.data[i]; + } + } + + public void incrementalMultScalar(double s) + { + for (int i=0; i < NDIM; i++) { + data[i] *= s; + } + } + + public void incrementalDivScalar(double s) + { + for (int i=0; i < NDIM; i++) { + data[i] /= s; + } + } + + /** + * Add a scalar to each element in the vector and put the + * result in this vector. + * @param u a vector + * @param s the scalar + **/ + public void addScalar(MathVector u, double s) + { + for (int i = 0; i < NDIM; i++) { + data[i] = u.data[i] + s; + } + } + + + /** + * Return the string representation of the vector + **/ + /*public String toString() + { + StringBuffer s = new StringBuffer(); + for (int i = 0; i < NDIM; i++) { + s.append(data[i] + " "); + } + return s.toString(); + }*/ +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/Node.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/Node.java new file mode 100644 index 00000000..2d2cbaaa --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/Node.java @@ -0,0 +1,112 @@ + +/** + * A class that represents the common fields of a cell or body + * data structure. + **/ +class Node +{ + /** + * Mass of the node. + **/ + public double mass; + /** + * Position of the node + **/ + public MathVector pos; + + // highest bit of int coord + public final int IMAX; + + // potential softening parameter + public final double EPS; + + /** + * Construct an empty node + **/ + public Node() + { + IMAX = 1073741824; + EPS = 0.05; + mass = 0.0; + pos = new MathVector(); + } + + /*abstract Node loadTree(Body p, MathVector xpic, int l, Tree root); + abstract double hackcofm(); + abstract HG walkSubTree(double dsq, HG hg);*/ + + public final int oldSubindex(MathVector ic, int l) + { + int i = 0; + for (int k = 0; k < 3/*MathVector.NDIM*/; k++) { + if (((int)ic.value(k) & l) != 0) + i += 8/*Cell.NSUB*/ >> (k + 1); + } + return i; + } + + /** + * Return a string representation of a node. + * @return a string representation of a node. + **/ + /*public String toString() + { + return mass + " : " + pos; + }*/ + + /** + * Compute a single body-body or body-cell interaction + **/ + public final HG gravSub(HG hg) + { + MathVector dr = new MathVector(); + dr.subtraction(pos, hg.pos0); + + double drsq = dr.dotProduct() + EPS * EPS; + double drabs = Math.sqrt(drsq); + + double phii = mass / drabs; + hg.phi0 -= phii; + double mor3 = phii / drsq; + dr.multScalar(mor3); + hg.acc0.addition(dr); + return hg; + } +} + +/** + * A class which is used to compute and save information during the + * gravity computation phse. + **/ +public class HG +{ + /** + * Body to skip in force evaluation + **/ + public Body pskip; + /** + * Point at which to evaluate field + **/ + public MathVector pos0; + /** + * Computed potential at pos0 + **/ + public double phi0; + /** + * computed acceleration at pos0 + **/ + public MathVector acc0; + + /** + * Create a HG object. + * @param b the body object + * @param p a vector that represents the body + **/ + public HG(Body b, MathVector p) + { + pskip = b; + pos0 = (MathVector)p.clone(); + phi0 = 0.0; + acc0 = new MathVector(); + } +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/TestRunner.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/TestRunner.java new file mode 100644 index 00000000..213a7084 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/TestRunner.java @@ -0,0 +1,125 @@ + +/*import java.util.Enumeration; +import java.lang.Math;*/ + +/** + * A Java implementation of the bh Olden benchmark. + * The Olden benchmark implements the Barnes-Hut benchmark + * that is decribed in : + *

+ * J. Barnes and P. Hut, "A hierarchical o(NlogN) force-calculation algorithm", + * Nature, 324:446-449, Dec. 1986 + * + *

+ * The original code in the Olden benchmark suite is derived from the + * + * source distributed by Barnes. + **/ +public class TestRunner extends Thread +{ + + /** + * The user specified number of bodies to create. + **/ + public int nbody; // = 0; + + /** + * The maximum number of time steps to take in the simulation + **/ + public int nsteps; // = 10; + + /** + * Should we print information messsages + **/ + //private static boolean printMsgs = false; + /** + * Should we print detailed results + **/ + //private static boolean printResults = false; + + public double DTIME; // = 0.0125; + public double TSTOP; // = 2.0; + + public TestRunner(int nbody) { + this.nbody = nbody; + this.nsteps = 10; + this.DTIME = 0.0125; + this.TSTOP = 2.0; + } + + public void run() + { + //parseCmdLine(args); + + /*if (printMsgs) + System.out.println("nbody = " + nbody);*/ + + //long start0 = System.currentTimeMillis(); + Tree root = new Tree(this.DTIME); + root.createTestData(nbody); + /*long end0 = System.currentTimeMillis(); + if (printMsgs) + System.out.println("Bodies created"); + + long start1 = System.currentTimeMillis();*/ + double tnow = 0.0; + int i = 0; + while ((tnow < (TSTOP + 0.1f*DTIME)) && (i < nsteps)) { + root.stepSystem(i++); + tnow += DTIME; + } + /*long end1 = System.currentTimeMillis(); + + if (printResults) { + int j = 0; + for (Enumeration e = root.bodies(); e.hasMoreElements(); ) { + Body b = (Body)e.nextElement(); + System.out.println("body " + j++ + " -- " + b.pos); + } + } + + if (printMsgs) { + System.out.println("Build Time " + (end0 - start0)/1000.0); + System.out.println("Compute Time " + (end1 - start1)/1000.0); + System.out.println("Total Time " + (end1 - start0)/1000.0); + } + System.out.println("Done!");*/ + } + + /** + * Random number generator used by the orignal BH benchmark. + * @param seed the seed to the generator + * @return a random number + **/ + public double myRand(double seed) + { + double t = 16807.0*seed + 1; + + seed = t - 2147483647.0 * Math.floor(t / 2147483647.0f); + return seed; + } + + /** + * Generate a doubleing point random number. Used by + * the original BH benchmark. + * + * @param xl lower bound + * @param xh upper bound + * @param r seed + * @return a doubleing point randon number + **/ + public double xRand(double xl, double xh, double r) + { + double res = xl + (xh-xl)*r/2147483647.0; + return res; + } + + public static void main(String[] args) { + int threadnum = 62; + int nbody = 700; + for(int i = 0; i < threadnum; ++i) { + TestRunner tr = new TestRunner(nbody); + tr.run(); + } + } +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/Tree.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/Tree.java new file mode 100644 index 00000000..6dea99a8 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/Tree.java @@ -0,0 +1,298 @@ + +//import java.util.Enumeration; + +/** + * A class that represents the root of the data structure used + * to represent the N-bodies in the Barnes-Hut algorithm. + **/ +class Tree +{ + public double DTIME; + + MathVector rmin; + public double rsize; + /** + * A reference to the root node. + **/ + public Node root; + /** + * The complete list of bodies that have been created. + **/ + public Body bodyTab; + /** + * The complete list of bodies that have been created - in reverse. + **/ + public Body bodyTabRev; + + /** + * Construct the root of the data structure that represents the N-bodies. + **/ + public Tree(double DTIME) + { + rmin = new MathVector(); + rsize = -2.0 * -2.0; + root = null; + bodyTab = null; + bodyTabRev = null; + + rmin.value(0, -2.0); + rmin.value(1, -2.0); + rmin.value(2, -2.0); + + this.DTIME = DTIME; + } + + /** + * Return an enumeration of the bodies. + * @return an enumeration of the bodies. + **/ + /*final Enumeration bodies() + { + return bodyTab.elements(); + }*/ + + /** + * Return an enumeration of the bodies - in reverse. + * @return an enumeration of the bodies - in reverse. + **/ + /*final Enumeration bodiesRev() + { + return bodyTabRev.elementsRev(); + }*/ + + /** + * Random number generator used by the orignal BH benchmark. + * @param seed the seed to the generator + * @return a random number + **/ + public double myRand(double seed) + { + double t = 16807.0*seed + 1; + + double iseed = t - (2147483647.0 * Math.floor(t / 2147483647.0f)); + return iseed; + } + + /** + * Generate a doubleing point random number. Used by + * the original BH benchmark. + * + * @param xl lower bound + * @param xh upper bound + * @param r seed + * @return a doubleing point randon number + **/ + public double xRand(double xl, double xh, double r) + { + double res = xl + (xh-xl)*r/2147483647.0; + return res; + } + + /** + * Create the testdata used in the benchmark. + * @param nbody the number of bodies to create + **/ + public void createTestData(int nbody) + { + MathVector cmr = new MathVector(); + MathVector cmv = new MathVector(); + + Body head = new Body(); + Body prev = head; + + double rsc = 3.0 * Math.PI() / 16.0; + double vsc = Math.sqrt(1.0 / rsc); + double seed = 123.0; + //Random rand = new Random((long)seed); + //int max_int = ~(int)0x1+1; + + for (int i = 0; i < nbody; i++) { + Body p = new Body(); + + prev.setNext(p); + prev = p; + p.mass = 1.0/nbody; + + seed = myRand(seed); + //seed = Math.abs((double)rand.nextInt()/max_int); + double t1 = xRand(0.0, 0.999, seed); + t1 = Math.pow(t1, (-2.0/3.0)) - 1.0; + double r = 1.0 / Math.sqrt(t1); + + double coeff = 4.0; + for (int k = 0; k < cmr.NDIM; k++) { + seed = myRand(seed); + //seed = Math.abs((double)rand.nextInt()/max_int); + r = xRand(0.0, 0.999, seed); + p.pos.value(k, coeff*r); + } + + cmr.addition(p.pos); + + double x, y; + do { + seed = myRand(seed); + //seed = Math.abs((double)rand.nextInt()/max_int); + x = xRand(0.0, 1.0, seed); + seed = myRand(seed); + //seed = Math.abs((double)rand.nextInt()/max_int); + y = xRand(0.0, 0.1, seed); + } while (y > (x*x * Math.pow((1.0f - x*x), 3.5))); + + double v = Math.sqrt(2.0) * x / Math.pow(1 + r*r, 0.25); + + double rad = vsc * v; + double rsq; + do { + for (int k = 0; k < cmr.NDIM; k++) { + seed = myRand(seed); + //seed = Math.abs((double)rand.nextInt()/max_int); + p.vel.value(k, xRand(-1.0, 1.0, seed)); + } + rsq = p.vel.dotProduct(); + } while (rsq > 1.0); + double rsc1 = rad / Math.sqrt(rsq); + p.vel.multScalar(rsc1); + cmv.addition(p.vel); + } + + // mark end of list + prev.setNext(null); + // toss the dummy node at the beginning and set a reference to the first element + bodyTab = head.getNext(); + + cmr.divScalar(nbody); + cmv.divScalar(nbody); + + prev = null; + Body b = this.bodyTab; + do { + b.pos.subtraction(cmr); + b.vel.subtraction(cmv); + b.setProcNext(prev); + prev = b; + b = b.getNext(); + } while(b != null); + // set the reference to the last element + bodyTabRev = prev; + } + + + /** + * Advance the N-body system one time-step. + * @param nstep the current time step + **/ + public void stepSystem(int nstep) + { + // free the tree + this.root = null; + + makeTree(nstep); + + Body next = null; + Body b = this.bodyTabRev; + do { + b.hackGravity(this.rsize, this.root); + b = b.getProcNext(); + } while(b != null); + + vp(this.bodyTabRev, nstep); + + } + + /** + * Initialize the tree structure for hack force calculation. + * @param nsteps the current time step + **/ + public void makeTree(int nstep) + { + Body q = this.bodyTabRev; + do { + if (q.mass != 0.0) { + q.expandBox(this, nstep); + MathVector xqic = intcoord(q.pos); + if (this.root == null) { + this.root = q; + } else { + if(root instanceof Body) { + Body rootb = (Body) root; + this.root = rootb.loadTree(q, xqic, 1073741824/*Node.IMAX*/ >> 1, this); + } else if(root instanceof Cell) { + Cell rootc = (Cell)root; + this.root = rootc.loadTree(q, xqic, 1073741824/*Node.IMAX*/ >> 1, this); + } + } + } + q = q.getProcNext(); + } while(q != null); + if(root instanceof Body) { + Body rootb = (Body)root; + rootb.hackcofm(); + } else if(root instanceof Cell) { + Cell rootc = (Cell)root; + rootc.hackcofm(); + } + } + + /** + * Compute integerized coordinates. + * @return the coordinates or null if rp is out of bounds + **/ + public MathVector intcoord(MathVector vp) + { + MathVector xp = new MathVector(); + + double xsc = (vp.value(0) - rmin.value(0)) / rsize; + if (0.0 <= xsc && xsc < 1.0) { + xp.value(0, Math.floor(1073741824/*Node.IMAX*/ * xsc)); + } else { + return null; + } + + xsc = (vp.value(1) - rmin.value(1)) / rsize; + if (0.0 <= xsc && xsc < 1.0) { + xp.value(1, Math.floor(1073741824/*Node.IMAX*/ * xsc)); + } else { + return null; + } + + xsc = (vp.value(2) - rmin.value(2)) / rsize; + if (0.0 <= xsc && xsc < 1.0) { + xp.value(2, Math.floor(1073741824/*Node.IMAX*/ * xsc)); + } else { + return null; + } + return xp; + } + + public void vp(Body p, int nstep) + { + MathVector dacc = new MathVector(); + MathVector dvel = new MathVector(); + double dthf = 0.5 * this.DTIME; + + Body b = p; + do { + MathVector acc1 = (MathVector)b.newAcc.clone(); + if (nstep > 0) { + dacc.subtraction(acc1, b.acc); + dvel.multScalar(dacc, dthf); + dvel.addition(b.vel); + b.vel = (MathVector)dvel.clone(); + } + b.acc = (MathVector)acc1.clone(); + dvel.multScalar(b.acc, dthf); + + MathVector vel1 = (MathVector)b.vel.clone(); + vel1.addition(dvel); + MathVector dpos = (MathVector)vel1.clone(); + dpos.multScalar(this.DTIME); + dpos.addition(b.pos); + b.pos = (MathVector)dpos.clone(); + vel1.addition(dvel); + b.vel = (MathVector)vel1.clone(); + + b = b.getProcNext(); + } while(b != null); + } +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/benchmark.py b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/benchmark.py new file mode 100644 index 00000000..64db9dab --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/bh/benchmark.py @@ -0,0 +1,3 @@ +from ashes2.lang.java.JOldenBenchmark import JOldenBenchmark + +benchmark = JOldenBenchmark("bh", "BH", params = ("-b", "4096", "-m")) diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/Main.hs b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/Main.hs new file mode 100644 index 00000000..5037cfa9 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/Main.hs @@ -0,0 +1,60 @@ +{- +From: Andrew J Bromage +Date: Fri, 22 Nov 2002 13:49:13 +1100 +To: haskell@haskell.org +Subject: Re: diff in Haskell: clarification + +Just for jollies, here's a Haskell version of Hirschberg's LCSS +algorithm. It's O(N^2) time but O(N) space at any given point in +time, assuming eager evaluation. You should be able to make diff out +of this. You should also be able to find many opportunities for +optimisation here. +-} + +module Main (main) where + +import System + +algb :: (Eq a) => [a] -> [a] -> [Int] +algb xs ys + = 0 : algb1 xs [ (y,0) | y <- ys ] + where + algb1 [] ys' = map snd ys' + algb1 (x:xs) ys' + = algb1 xs (algb2 0 0 ys') + where + algb2 _ _ [] = [] + algb2 k0j1 k1j1 ((y,k0j):ys) + = let kjcurr = if x == y then k0j1+1 else max k1j1 k0j + in (y,kjcurr) : algb2 k0j kjcurr ys + +algc :: (Eq a) => Int -> Int -> [a] -> [a] -> [a] -> [a] +algc m n xs [] = id +algc m n [x] ys = if x `elem` ys then (x:) else id +algc m n xs ys + = algc m2 k xs1 (take k ys) . algc (m-m2) (n-k) xs2 (drop k ys) + where + m2 = m `div` 2 + + xs1 = take m2 xs + xs2 = drop m2 xs + + l1 = algb xs1 ys + l2 = reverse (algb (reverse xs2) (reverse ys)) + + k = findk 0 0 (-1) (zip l1 l2) + + findk k km m [] = km + findk k km m ((x,y):xys) + | x+y >= m = findk (k+1) k (x+y) xys + | otherwise = findk (k+1) km m xys + +lcss :: (Eq a) => [a] -> [a] -> [a] +lcss xs ys = algc (length xs) (length ys) xs ys [] + +main = do + [a,b,c,d,e,f] <- getArgs + let a', b', c', d', e', f' :: Int + a' = read a; b' = read b; c' = read c; + d' = read d; e' = read e; f' = read f + print (lcss [a',b'..c'] [d',e'..f']) diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/Makefile b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/Makefile new file mode 100644 index 00000000..88fbcfd5 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/Makefile @@ -0,0 +1,8 @@ +TOP=../.. +include $(TOP)/mk/boilerplate.mk + +FAST_OPTS = 1 2 500 250 251 750 +NORM_OPTS = 1 2 1000 500 501 1500 +SLOW_OPTS = 1 2 2000 1000 1001 3000 + +include $(TOP)/mk/target.mk diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/TestRunner.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/TestRunner.java new file mode 100644 index 00000000..b22808d9 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/TestRunner.java @@ -0,0 +1,246 @@ +public class TestRunner { + + int[] testargs; + + public TestRunner(int[] args) { + this.testargs = args; + } + + private Vector algb2(int x, + int p, + int q, + Vector ys, + Vector yst, + Vector yst1) { + Vector result = null; + if(ys.size() == 0) { + // algb2 _ _ [] = [] + result = new Vector(); + } else { + // algb2 k0j1 k1j1 ((y,k0j):ys) + int y = ((Integer)ys.elementAt(0)).intValue(); + int yt = ((Integer)yst.elementAt(0)).intValue(); + Vector ys2 = new Vector(); + for(int i = 1; i < ys.size(); i++) { + ys2.addElement(ys.elementAt(i)); + } + Vector yst2 = new Vector(); + for(int i = 1; i < yst.size(); i++) { + yst2.addElement(yst.elementAt(i)); + } + + // = let kjcurr = if x == y then k0j1+1 else max k1j1 k0j + // in (y,kjcurr) : algb2 k0j kjcurr ys + int k = 0; + if(x == y) { + k = p + 1; + } else { + k = (q > yt) ? q : yt; + } + result = this.algb2(x, yt, k, ys2, yst2, yst1); + result.insertElementAt(new Integer(y), 0); + yst1.insertElementAt(new Integer(k), 0); + } + return result; + } + + private Vector algb1(Vector xs, + Vector ys, + Vector yst) { + Vector result = null; + if(xs.size() == 0) { + // algb1 [] ys' = map snd ys' + result = yst; + } else { + // algb1 (x:xs) ys' + // = algb1 xs (algb2 0 0 ys') + int x = ((Integer)xs.elementAt(0)).intValue(); + Vector xs1 = new Vector(); + for(int i = 1; i < xs.size(); i++) { + xs1.addElement(xs.elementAt(i)); + } + + Vector yst1 = new Vector(); + Vector ys1 = this.algb2(x, 0, 0, ys, yst, yst1); + + result = this.algb1(xs1, ys1, yst1); + } + return result; + } + + private Vector algb(Vector xs, + Vector ys) { + // algb xs ys + // = 0 : algb1 xs [ (y,0) | y <- ys ] + Vector yst = new Vector(); + for(int i = 0; i < ys.size(); i++) { + yst.addElement(new Integer(0)); + } + Vector result = this.algb1(xs, ys, yst); + result.insertElementAt(new Integer(0), 0); + return result; + } + + private int findk(int k, + int km, + int m, + Vector v, + Vector vt) { + int result = 0; + if(v.size() == 0) { + // findk k km m [] = km + result = km; + } else { + // findk k km m ((x,y):xys) + int x = ((Integer)v.elementAt(0)).intValue(); + int y = ((Integer)vt.elementAt(0)).intValue(); + Vector v1 = new Vector(); + for(int i = 1; i < v.size(); i++) { + v1.addElement(v.elementAt(i)); + } + Vector vt1 = new Vector(); + for(int i = 1; i < vt.size(); i++) { + vt1.addElement(vt.elementAt(i)); + } + + if(x + y >= m) { + // | x+y >= m = findk (k+1) k (x+y) xys + result = this.findk(k+1, k, x+y, v1, vt1); + } else { + // | otherwise = findk (k+1) km m xys + result = this.findk(k+1, km, m, v1, vt1); + } + } + return result; + } + + private Vector algc(int m, + int n, + Vector xs, + Vector ys, + Vector r) { + Vector result = null; + if(ys.size() == 0) { + // algc m n xs [] = id + result = r; + } else if(xs.size() == 1) { + // algc m n [x] ys = if x `elem` ys then (x:) else id + result = r; + + int x = ((Integer)xs.elementAt(0)).intValue(); + // if x `elem` ys + boolean iscontains = false; + for(int i = 0; i < ys.size(); i++) { + if(((Integer)ys.elementAt(i)).intValue() == x) { + iscontains = true; + i = ys.size(); // break; + } + } + if(iscontains) { + // then (x:) + r.insertElementAt(new Integer(x), 0); + } + } else { + // algc m n xs ys + // = algc m2 k xs1 (take k ys) . algc (m-m2) (n-k) xs2 (drop k ys) + // where + // m2 = m `div` 2 + int m2 = m/2; + + // xs1 = take m2 xs + Vector xs1 = new Vector(); + int i = 0; + for(i = 0; i < m2; i++) { + xs1.addElement(xs.elementAt(i)); + } + + // xs2 = drop m2 xs + Vector xs2 = new Vector(); + for(; i < xs.size(); i++) { + xs2.addElement(xs.elementAt(i)); + } + + // l1 = algb xs1 ys + Vector l1 = this.algb(xs1, ys); + + // l2 = reverse (algb (reverse xs2) (reverse ys)) + Vector rxs2 = new Vector(); + for(i = xs2.size(); i > 0; i--) { + rxs2.addElement(xs2.elementAt(i - 1)); + } + Vector rys = new Vector(); + for(i = ys.size(); i > 0; i--) { + rys.addElement(ys.elementAt(i - 1)); + } + Vector rl2 = algb(rxs2, rys); + Vector l2 = new Vector(); + for(i = rl2.size(); i > 0; i--) { + l2.addElement(rl2.elementAt(i - 1)); + } + + // k = findk 0 0 (-1) (zip l1 l2) + int k = this.findk(0, 0, (-1), l1, l2); + + // algc m n xs ys + // = algc m2 k xs1 (take k ys) . algc (m-m2) (n-k) xs2 (drop k ys) + Vector ysk = new Vector(); + // (take k ys) + for(i = 0; i < k; i++) { + ysk.addElement(ys.elementAt(i)); + } + Vector ysd = new Vector(); + // (drop k ys) + for(; i < ys.size(); i++) { + ysd.addElement(ys.elementAt(i)); + } + Vector interresult = this.algc(m-m2, n-k, xs2, ysd, r); + result = this.algc(m2, k, xs1, ysk, interresult); + } + return result; + } + + public void run() { + Vector xs = new Vector(); + Vector ys = new Vector(); + + int x1 = this.testargs[0]; + int x2 = this.testargs[1]; + int xfinal = this.testargs[2]; + int xdelta = x2-x1; + int y1 = this.testargs[3]; + int y2 = this.testargs[4]; + int yfinal = this.testargs[5]; + int ydelta = y2-y1; + xs.addElement(new Integer(x1)); + for(int i = x2; i <= xfinal; ) { + xs.addElement(new Integer(i)); + i += xdelta; + } + ys.addElement(new Integer(y1)); + for(int i = y2; i <= yfinal; ) { + ys.addElement(new Integer(i)); + i += ydelta; + } + + Vector r = new Vector(); + + Vector result = this.algc(xs.size(), ys.size(), xs, ys, r); + for(int i = 0; i < result.size(); i++) { + int tmp = ((Integer)result.elementAt(i)).intValue(); + } + } + public static void main(String argv[]){ + int threadnum = 62; + int[] args = new int[6]; + args[0] = 1; + args[1] = 2; + args[2] = 160; + args[3] = 80; + args[4] = 81; + args[5] = 240; + for(int i = 0; i < threadnum; ++i) { + TestRunner tr = new TestRunner(args); + tr.run(); + } + } +} \ No newline at end of file diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/lcss.faststdout b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/lcss.faststdout new file mode 100644 index 00000000..9f0cd5fe --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/lcss.faststdout @@ -0,0 +1 @@ +[250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277,278,279,280,281,282,283,284,285,286,287,288,289,290,291,292,293,294,295,296,297,298,299,300,301,302,303,304,305,306,307,308,309,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,329,330,331,332,333,334,335,336,337,338,339,340,341,342,343,344,345,346,347,348,349,350,351,352,353,354,355,356,357,358,359,360,361,362,363,364,365,366,367,368,369,370,371,372,373,374,375,376,377,378,379,380,381,382,383,384,385,386,387,388,389,390,391,392,393,394,395,396,397,398,399,400,401,402,403,404,405,406,407,408,409,410,411,412,413,414,415,416,417,418,419,420,421,422,423,424,425,426,427,428,429,430,431,432,433,434,435,436,437,438,439,440,441,442,443,444,445,446,447,448,449,450,451,452,453,454,455,456,457,458,459,460,461,462,463,464,465,466,467,468,469,470,471,472,473,474,475,476,477,478,479,480,481,482,483,484,485,486,487,488,489,490,491,492,493,494,495,496,497,498,499,500] diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/lcss.slowstdout b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/lcss.slowstdout new file mode 100644 index 00000000..ef178105 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/lcss.slowstdout @@ -0,0 +1 @@ +[1000,1001,1002,1003,1004,1005,1006,1007,1008,1009,1010,1011,1012,1013,1014,1015,1016,1017,1018,1019,1020,1021,1022,1023,1024,1025,1026,1027,1028,1029,1030,1031,1032,1033,1034,1035,1036,1037,1038,1039,1040,1041,1042,1043,1044,1045,1046,1047,1048,1049,1050,1051,1052,1053,1054,1055,1056,1057,1058,1059,1060,1061,1062,1063,1064,1065,1066,1067,1068,1069,1070,1071,1072,1073,1074,1075,1076,1077,1078,1079,1080,1081,1082,1083,1084,1085,1086,1087,1088,1089,1090,1091,1092,1093,1094,1095,1096,1097,1098,1099,1100,1101,1102,1103,1104,1105,1106,1107,1108,1109,1110,1111,1112,1113,1114,1115,1116,1117,1118,1119,1120,1121,1122,1123,1124,1125,1126,1127,1128,1129,1130,1131,1132,1133,1134,1135,1136,1137,1138,1139,1140,1141,1142,1143,1144,1145,1146,1147,1148,1149,1150,1151,1152,1153,1154,1155,1156,1157,1158,1159,1160,1161,1162,1163,1164,1165,1166,1167,1168,1169,1170,1171,1172,1173,1174,1175,1176,1177,1178,1179,1180,1181,1182,1183,1184,1185,1186,1187,1188,1189,1190,1191,1192,1193,1194,1195,1196,1197,1198,1199,1200,1201,1202,1203,1204,1205,1206,1207,1208,1209,1210,1211,1212,1213,1214,1215,1216,1217,1218,1219,1220,1221,1222,1223,1224,1225,1226,1227,1228,1229,1230,1231,1232,1233,1234,1235,1236,1237,1238,1239,1240,1241,1242,1243,1244,1245,1246,1247,1248,1249,1250,1251,1252,1253,1254,1255,1256,1257,1258,1259,1260,1261,1262,1263,1264,1265,1266,1267,1268,1269,1270,1271,1272,1273,1274,1275,1276,1277,1278,1279,1280,1281,1282,1283,1284,1285,1286,1287,1288,1289,1290,1291,1292,1293,1294,1295,1296,1297,1298,1299,1300,1301,1302,1303,1304,1305,1306,1307,1308,1309,1310,1311,1312,1313,1314,1315,1316,1317,1318,1319,1320,1321,1322,1323,1324,1325,1326,1327,1328,1329,1330,1331,1332,1333,1334,1335,1336,1337,1338,1339,1340,1341,1342,1343,1344,1345,1346,1347,1348,1349,1350,1351,1352,1353,1354,1355,1356,1357,1358,1359,1360,1361,1362,1363,1364,1365,1366,1367,1368,1369,1370,1371,1372,1373,1374,1375,1376,1377,1378,1379,1380,1381,1382,1383,1384,1385,1386,1387,1388,1389,1390,1391,1392,1393,1394,1395,1396,1397,1398,1399,1400,1401,1402,1403,1404,1405,1406,1407,1408,1409,1410,1411,1412,1413,1414,1415,1416,1417,1418,1419,1420,1421,1422,1423,1424,1425,1426,1427,1428,1429,1430,1431,1432,1433,1434,1435,1436,1437,1438,1439,1440,1441,1442,1443,1444,1445,1446,1447,1448,1449,1450,1451,1452,1453,1454,1455,1456,1457,1458,1459,1460,1461,1462,1463,1464,1465,1466,1467,1468,1469,1470,1471,1472,1473,1474,1475,1476,1477,1478,1479,1480,1481,1482,1483,1484,1485,1486,1487,1488,1489,1490,1491,1492,1493,1494,1495,1496,1497,1498,1499,1500,1501,1502,1503,1504,1505,1506,1507,1508,1509,1510,1511,1512,1513,1514,1515,1516,1517,1518,1519,1520,1521,1522,1523,1524,1525,1526,1527,1528,1529,1530,1531,1532,1533,1534,1535,1536,1537,1538,1539,1540,1541,1542,1543,1544,1545,1546,1547,1548,1549,1550,1551,1552,1553,1554,1555,1556,1557,1558,1559,1560,1561,1562,1563,1564,1565,1566,1567,1568,1569,1570,1571,1572,1573,1574,1575,1576,1577,1578,1579,1580,1581,1582,1583,1584,1585,1586,1587,1588,1589,1590,1591,1592,1593,1594,1595,1596,1597,1598,1599,1600,1601,1602,1603,1604,1605,1606,1607,1608,1609,1610,1611,1612,1613,1614,1615,1616,1617,1618,1619,1620,1621,1622,1623,1624,1625,1626,1627,1628,1629,1630,1631,1632,1633,1634,1635,1636,1637,1638,1639,1640,1641,1642,1643,1644,1645,1646,1647,1648,1649,1650,1651,1652,1653,1654,1655,1656,1657,1658,1659,1660,1661,1662,1663,1664,1665,1666,1667,1668,1669,1670,1671,1672,1673,1674,1675,1676,1677,1678,1679,1680,1681,1682,1683,1684,1685,1686,1687,1688,1689,1690,1691,1692,1693,1694,1695,1696,1697,1698,1699,1700,1701,1702,1703,1704,1705,1706,1707,1708,1709,1710,1711,1712,1713,1714,1715,1716,1717,1718,1719,1720,1721,1722,1723,1724,1725,1726,1727,1728,1729,1730,1731,1732,1733,1734,1735,1736,1737,1738,1739,1740,1741,1742,1743,1744,1745,1746,1747,1748,1749,1750,1751,1752,1753,1754,1755,1756,1757,1758,1759,1760,1761,1762,1763,1764,1765,1766,1767,1768,1769,1770,1771,1772,1773,1774,1775,1776,1777,1778,1779,1780,1781,1782,1783,1784,1785,1786,1787,1788,1789,1790,1791,1792,1793,1794,1795,1796,1797,1798,1799,1800,1801,1802,1803,1804,1805,1806,1807,1808,1809,1810,1811,1812,1813,1814,1815,1816,1817,1818,1819,1820,1821,1822,1823,1824,1825,1826,1827,1828,1829,1830,1831,1832,1833,1834,1835,1836,1837,1838,1839,1840,1841,1842,1843,1844,1845,1846,1847,1848,1849,1850,1851,1852,1853,1854,1855,1856,1857,1858,1859,1860,1861,1862,1863,1864,1865,1866,1867,1868,1869,1870,1871,1872,1873,1874,1875,1876,1877,1878,1879,1880,1881,1882,1883,1884,1885,1886,1887,1888,1889,1890,1891,1892,1893,1894,1895,1896,1897,1898,1899,1900,1901,1902,1903,1904,1905,1906,1907,1908,1909,1910,1911,1912,1913,1914,1915,1916,1917,1918,1919,1920,1921,1922,1923,1924,1925,1926,1927,1928,1929,1930,1931,1932,1933,1934,1935,1936,1937,1938,1939,1940,1941,1942,1943,1944,1945,1946,1947,1948,1949,1950,1951,1952,1953,1954,1955,1956,1957,1958,1959,1960,1961,1962,1963,1964,1965,1966,1967,1968,1969,1970,1971,1972,1973,1974,1975,1976,1977,1978,1979,1980,1981,1982,1983,1984,1985,1986,1987,1988,1989,1990,1991,1992,1993,1994,1995,1996,1997,1998,1999,2000] diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/lcss.stdout b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/lcss.stdout new file mode 100644 index 00000000..b7d919fd --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/lcss/lcss.stdout @@ -0,0 +1 @@ +[500,501,502,503,504,505,506,507,508,509,510,511,512,513,514,515,516,517,518,519,520,521,522,523,524,525,526,527,528,529,530,531,532,533,534,535,536,537,538,539,540,541,542,543,544,545,546,547,548,549,550,551,552,553,554,555,556,557,558,559,560,561,562,563,564,565,566,567,568,569,570,571,572,573,574,575,576,577,578,579,580,581,582,583,584,585,586,587,588,589,590,591,592,593,594,595,596,597,598,599,600,601,602,603,604,605,606,607,608,609,610,611,612,613,614,615,616,617,618,619,620,621,622,623,624,625,626,627,628,629,630,631,632,633,634,635,636,637,638,639,640,641,642,643,644,645,646,647,648,649,650,651,652,653,654,655,656,657,658,659,660,661,662,663,664,665,666,667,668,669,670,671,672,673,674,675,676,677,678,679,680,681,682,683,684,685,686,687,688,689,690,691,692,693,694,695,696,697,698,699,700,701,702,703,704,705,706,707,708,709,710,711,712,713,714,715,716,717,718,719,720,721,722,723,724,725,726,727,728,729,730,731,732,733,734,735,736,737,738,739,740,741,742,743,744,745,746,747,748,749,750,751,752,753,754,755,756,757,758,759,760,761,762,763,764,765,766,767,768,769,770,771,772,773,774,775,776,777,778,779,780,781,782,783,784,785,786,787,788,789,790,791,792,793,794,795,796,797,798,799,800,801,802,803,804,805,806,807,808,809,810,811,812,813,814,815,816,817,818,819,820,821,822,823,824,825,826,827,828,829,830,831,832,833,834,835,836,837,838,839,840,841,842,843,844,845,846,847,848,849,850,851,852,853,854,855,856,857,858,859,860,861,862,863,864,865,866,867,868,869,870,871,872,873,874,875,876,877,878,879,880,881,882,883,884,885,886,887,888,889,890,891,892,893,894,895,896,897,898,899,900,901,902,903,904,905,906,907,908,909,910,911,912,913,914,915,916,917,918,919,920,921,922,923,924,925,926,927,928,929,930,931,932,933,934,935,936,937,938,939,940,941,942,943,944,945,946,947,948,949,950,951,952,953,954,955,956,957,958,959,960,961,962,963,964,965,966,967,968,969,970,971,972,973,974,975,976,977,978,979,980,981,982,983,984,985,986,987,988,989,990,991,992,993,994,995,996,997,998,999,1000] diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/tsp/Makefile b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/tsp/Makefile new file mode 100644 index 00000000..f84382b0 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/tsp/Makefile @@ -0,0 +1,4 @@ +BMARK = TSP +PARMS = -c 10000 -m +include ../Makefile.common + diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/tsp/TestRunner.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/tsp/TestRunner.java new file mode 100644 index 00000000..28f5ae2d --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/tsp/TestRunner.java @@ -0,0 +1,114 @@ + +//import java.io.*; + +/** + * A Java implementation of the tsp Olden benchmark, the traveling + * salesman problem. + *

+ * + * R. Karp, "Probabilistic analysis of partitioning algorithms for the + * traveling-salesman problem in the plane." Mathematics of Operations Research + * 2(3):209-224, August 1977 + * + **/ +public class TestRunner extends Thread +{ + + /** + * Number of cities in the problem. + **/ + public int cities; + /** + * Set to true if the result should be printed + **/ + //private static boolean printResult = false; + /** + * Set to true to print informative messages + **/ + //private static boolean printMsgs = false; + + public TestRunner(int cities) { + this.cities = cities; + } + + /** + * The main routine which creates a tree and traverses it. + * @param args the arguments to the program + **/ + public void run() + { + /*parseCmdLine(args); + + if (printMsgs) + System.out.println("Building tree of size " + cities); + + long start0 = System.currentTimeMillis();*/ + Tree_tsp t = Tree_tsp.buildTree(this.cities, false, 0.0f, 1.0f, 0.0f, 1.0f); + /*long end0 = System.currentTimeMillis(); + + long start1 = System.currentTimeMillis();*/ + t.tsp(150); + /*long end1 = System.currentTimeMillis(); + + if (printResult) { + // if the user specifies, print the final result + t.printVisitOrder(); + } + + if (printMsgs) { + System.out.println("Tsp build time " + (end0 - start0)/1000.0); + System.out.println("Tsp time " + (end1 - start1)/1000.0); + System.out.println("Tsp total time " + (end1 - start0)/1000.0); + } + System.out.println("Done!");*/ + } + + /** + * Parse the command line options. + * @param args the command line options. + **/ + /*private static final void parseCmdLine(String args[]) + { + int i = 0; + String arg; + + while (i < args.length && args[i].startsWith("-")) { + arg = args[i++]; + + if (arg.equals("-c")) { + if (i < args.length) + cities = new Integer(args[i++]).intValue(); + else throw new Error("-c requires the size of tree"); + } else if (arg.equals("-p")) { + printResult = true; + } else if (arg.equals("-m")) { + printMsgs = true; + } else if (arg.equals("-h")) { + usage(); + } + } + if (cities == 0) usage(); + }*/ + + /** + * The usage routine which describes the program options. + **/ + /*private static final void usage() + { + System.err.println("usage: java TSP -c [-p] [-m] [-h]"); + System.err.println(" -c number of cities (rounds up to the next power of 2 minus 1)"); + System.err.println(" -p (print the final result)"); + System.err.println(" -m (print informative messages)"); + System.err.println(" -h (print this message)"); + System.exit(0); + }*/ + public static void main(String[] args) { + int threadnum = 62; + int ncities = 4080*2; + for(int i = 0; i < threadnum; ++i) { + TestRunner tr = new TestRunner(ncities); + tr.run(); + } + } +} + diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/tsp/Tree_tsp.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/tsp/Tree_tsp.java new file mode 100644 index 00000000..706ba059 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/tsp/Tree_tsp.java @@ -0,0 +1,456 @@ + +//import java.util.Random; + +/** + * A class that represents a node in a binary tree. Each node represents + * a city in the TSP benchmark. + **/ +final class Tree_tsp +{ + /** + * The number of nodes (cities) in this subtree + **/ + private int sz; + /** + * The coordinates that this node represents + **/ + private float x,y; + /** + * Left child of the tree + **/ + private Tree_tsp left; + /** + * Right child of tree + **/ + private Tree_tsp right; + /** + * The next pointer in a linked list of nodes in the subtree. The list + * contains the order of the cities to visit. + **/ + private Tree_tsp next; + /** + * The previous pointer in a linked list of nodes in the subtree. The list + * contains the order of the cities to visit. + **/ + private Tree_tsp prev; + + // used by the random number generator + //private static final float M_E2; // = 7.3890560989306502274; + //private static final float M_E3; // = 20.08553692318766774179; + //private static final float M_E6; // = 403.42879349273512264299; + //private static final float M_E12; // = 162754.79141900392083592475; + + /** + * Construct a Tree node (a city) with the specified size + * @param size the number of nodes in the (sub)tree + * @param x the x coordinate of the city + * @param y the y coordinate of the city + * @param left the left subtree + * @param right the right subtree + **/ + Tree_tsp(int size, float x, float y, Tree_tsp l, Tree_tsp r) + { + /*M_E2 = 7.3890560989306502274f; + M_E3 = 20.08553692318766774179f; + M_E6 = 403.42879349273512264299f; + M_E12 = 162754.79141900392083592475f;*/ + + sz = size; + this.x = x; + this.y = y; + left = l; + right = r; + next = null; + prev = null; + } + + /** + * Find Euclidean distance between this node and the specified node. + * @param b the specified node + * @return the Euclidean distance between two tree nodes. + **/ + float distance(Tree_tsp b) + { + return (Math.sqrtf((float)((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y)))); + } + + /** + * Create a list of tree nodes. Requires root to be the tail of the list. + * Only fills in next field, not prev. + * @return the linked list of nodes + **/ + Tree_tsp makeList() + { + Tree_tsp myleft, myright; + Tree_tsp tleft,tright; + Tree_tsp retval = this; + + // head of left list + if (left != null) + myleft = left.makeList(); + else + myleft = null; + + // head of right list + if (right != null) + myright = right.makeList(); + else + myright = null; + + if (myright != null) { + retval = myright; + right.next = this; + } + + if (myleft != null) { + retval = myleft; + if (myright != null) + left.next = myright; + else + left.next = this; + } + next = null; + + return retval; + } + + /** + * Reverse the linked list. Assumes that there is a dummy "prev" + * node at the beginning. + **/ + void reverse() + { + Tree_tsp prev = this.prev; + prev.next = null; + this.prev = null; + Tree_tsp back = this; + Tree_tsp tmp = this; + // reverse the list for the other nodes + Tree_tsp next; + for (Tree_tsp t = this.next; t != null; back = t, t = next) { + next = t.next; + t.next = back; + back.prev = t; + } + // reverse the list for this node + tmp.next = prev; + prev.prev = tmp; + } + + /** + * Use closest-point heuristic from Cormen, Leiserson, and Rivest. + * @return a + **/ + Tree_tsp conquer() + { + // create the list of nodes + Tree_tsp t = makeList(); + + // Create initial cycle + Tree_tsp cycle = t; + t = t.next; + cycle.next = cycle; + cycle.prev = cycle; + + // Loop over remaining points + Tree_tsp donext; + for (; t != null; t = donext) { + donext = t.next; /* value won't be around later */ + Tree_tsp min = cycle; + float mindist = t.distance(cycle); + for (Tree_tsp tmp = cycle.next; tmp != cycle; tmp=tmp.next) { + float test = tmp.distance(t); + if (test < mindist) { + mindist = test; + min = tmp; + } /* if */ + } /* for tmp... */ + + Tree_tsp next = min.next; + Tree_tsp prev = min.prev; + + float mintonext = min.distance(next); + float mintoprev = min.distance(prev); + float ttonext = t.distance(next); + float ttoprev = t.distance(prev); + + if ((float)(ttoprev - mintoprev) < (float)(ttonext - mintonext)) { + /* insert between min and prev */ + prev.next = t; + t.next = min; + t.prev = prev; + min.prev = t; + } else { + next.prev = t; + t.next = next; + min.next = t; + t.prev = min; + } + } /* for t... */ + + return cycle; + } + + /** + * Merge two cycles as per Karp. + * @param a a subtree with one cycle + * @param b a subtree with the other cycle + **/ + Tree_tsp merge(Tree_tsp a, Tree_tsp b) + { + // Compute location for first cycle + Tree_tsp min = a; + float mindist = distance(a); + Tree_tsp tmp = a; + for (a = a.next; a != tmp; a = a.next) { + float test = distance(a); + if (test < mindist) { + mindist = test; + min = a; + } + } + + Tree_tsp next = min.next; + Tree_tsp prev = min.prev; + float mintonext = min.distance(next); + float mintoprev = min.distance(prev); + float ttonext = distance(next); + float ttoprev = distance(prev); + + Tree_tsp p1, n1; + float tton1, ttop1; + if ((ttoprev - mintoprev) < (ttonext - mintonext)) { + // would insert between min and prev + p1 = prev; + n1 = min; + tton1 = mindist; + ttop1 = ttoprev; + } else { + // would insert between min and next + p1 = min; + n1 = next; + ttop1 = mindist; + tton1 = ttonext; + } + + // Compute location for second cycle + min = b; + mindist = distance(b); + tmp = b; + for (b = b.next; b != tmp; b = b.next) { + float test = distance(b); + if (test < mindist) { + mindist = test; + min = b; + } + } + + next = min.next; + prev = min.prev; + mintonext = min.distance(next); + mintoprev = min.distance(prev); + ttonext = this.distance(next); + ttoprev = this.distance(prev); + + Tree_tsp p2, n2; + float tton2, ttop2; + if ((ttoprev - mintoprev) < (ttonext - mintonext)) { + // would insert between min and prev + p2 = prev; + n2 = min; + tton2 = mindist; + ttop2 = ttoprev; + } else { + // would insert between min andn ext + p2 = min; + n2 = next; + ttop2 = mindist; + tton2 = ttonext; + } + + // Now we have 4 choices to complete: + // 1:t,p1 t,p2 n1,n2 + // 2:t,p1 t,n2 n1,p2 + // 3:t,n1 t,p2 p1,n2 + // 4:t,n1 t,n2 p1,p2 + float n1ton2 = n1.distance(n2); + float n1top2 = n1.distance(p2); + float p1ton2 = p1.distance(n2); + float p1top2 = p1.distance(p2); + + mindist = (float)(ttop1 + ttop2 + n1ton2); + int choice = 1; + + float test = (float)(ttop1 + tton2 + n1top2); + if (test < mindist) { + choice = 2; + mindist = test; + } + + test = tton1 + ttop2 + p1ton2; + if (test < mindist) { + choice = 3; + mindist = test; + } + + test = tton1 + tton2 + p1top2; + if (test < mindist) + choice = 4; + + if (choice == 1) { + //case 1: + // 1:p1,this this,p2 n2,n1 -- reverse 2! + n2.reverse(); + p1.next = this; + this.prev = p1; + this.next = p2; + p2.prev = this; + n2.next = n1; + n1.prev = n2; + //break; + } else if(choice == 2) { + //case 2: + // 2:p1,this this,n2 p2,n1 -- OK + p1.next = this; + this.prev = p1; + this.next = n2; + n2.prev = this; + p2.next = n1; + n1.prev = p2; + //break; + } else if(choice == 3) { + //case 3: + // 3:p2,this this,n1 p1,n2 -- OK + p2.next = this; + this.prev = p2; + this.next = n1; + n1.prev = this; + p1.next = n2; + n2.prev = p1; + //break; + } else if(choice == 4) { + //case 4: + // 4:n1,this this,n2 p2,p1 -- reverse 1! + n1.reverse(); + n1.next = this; + this.prev = n1; + this.next = n2; + n2.prev = this; + p2.next = p1; + p1.prev = p2; + //break; + } + return this; + } + + /** + * Compute TSP for the tree t. Use conquer for problems <= sz + * @param sz the cutoff point for using conquer vs. merge + **/ + Tree_tsp tsp(int sz) + { + if (this.sz <= sz) return conquer(); + + Tree_tsp leftval = left.tsp(sz); + Tree_tsp rightval = right.tsp(sz); + + return merge(leftval, rightval); + } + + /** + * Print the list of cities to visit from the current node. The + * list is the result of computing the TSP problem. + * The list for the root node (city) should contain every other node + * (city). + **/ + /*void printVisitOrder() + { + System.out.println("x = " + x + " y = " + y); + for (Tree_tsp tmp = next; tmp != this; tmp = tmp.next) { + System.out.println("x = " + tmp.x + " y = " + tmp.y); + } + }*/ + + // + // static methods + // + + /** + * Return an estimate of median of n values distributed in [min,max) + * @param min the minimum value + * @param max the maximum value + * @param n + * @return an estimate of median of n values distributed in [min,max) + **/ + private static float median(float min, float max, int n) + { + float M_E2 = 7.3890560989306502274f; + float M_E3 = 20.08553692318766774179f; + float M_E6 = 403.42879349273512264299f; + float M_E12 = 162754.79141900392083592475f; + + // get random value in [0.0, 1.0) + float t = (new Random()).nextFloat(); + + float retval; + if (t > 0.5) { + retval = /*java.lang.*/(float)(Math.log(1.0-(2.0*(M_E12-1)*(t-0.5)/M_E12))/12.0f); + } else { + retval = (float)(-/*java.lang.*/Math.log(1.0-(2.0*(M_E12-1)*t/M_E12))/12.0f); + } + // We now have something distributed on (-1.0,1.0) + retval = (float)((retval+1.0f) * (max-min)/2.0f); + retval = retval + min; + return retval; + } + + /** + * Get float uniformly distributed over [min,max) + * @return float uniformily distributed over [min,max) + **/ + private static float uniform(float min, float max) + { + // get random value between [0.0,1.0) + float retval = (new Random()).nextFloat(); + retval = retval * (max-min); + return retval + min; + } + + /** + * Builds a 2D tree of n nodes in specified range with dir as primary + * axis (false for x, true for y) + * + * @param n the size of the subtree to create + * @param dir the primary axis + * @param min_x the minimum x coordinate + * @param max_x the maximum x coordinate + * @param min_y the minimum y coordinate + * @param max_y the maximum y coordinate + * @return a reference to the root of the subtree + **/ + public static Tree_tsp buildTree(int n, boolean dir, float min_x, + float max_x, float min_y, float max_y) + { + if (n==0) return null; + + Tree_tsp left, right; + float x, y; + if (dir) { + dir = !dir; + float med = median(min_x,max_x,n); + left = buildTree(n/2, dir, min_x, med, min_y, max_y); + right = buildTree(n/2, dir, med, max_x, min_y, max_y); + x = med; + y = uniform(min_y, max_y); + } else { + dir = !dir; + float med = median(min_y,max_y,n); + left = buildTree(n/2, dir, min_x, max_x, min_y, med); + right = buildTree(n/2, dir, min_x, max_x, med, max_y); + y = med; + x = uniform(min_x, max_x); + } + return new Tree_tsp(n, x, y, left, right); + } + +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/tsp/benchmark.py b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/tsp/benchmark.py new file mode 100644 index 00000000..1acab5da --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/tsp/benchmark.py @@ -0,0 +1,3 @@ +from ashes2.lang.java.JOldenBenchmark import JOldenBenchmark + +benchmark = JOldenBenchmark("tsp", "TSP", params = ("-c", "1000", "-m")) diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/Edge.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/Edge.java new file mode 100644 index 00000000..b2819dea --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/Edge.java @@ -0,0 +1,364 @@ + +/** + * A class that represents the quad edge data structure which implements + * the edge algebra as described in the algorithm. + *

+ * Each edge contains 4 parts, or other edges. Any edge in the group may + * be accessed using a series of rotate and flip operations. The 0th + * edge is the canonical representative of the group. + *

+ * The quad edge class does not contain separate information for vertice + * or faces; a vertex is implicitly defined as a ring of edges (the ring + * is created using the next field). + **/ +class Edge +{ + /** + * Group of edges that describe the quad edge + **/ + Edge quadList[]; + /** + * The position of this edge within the quad list + **/ + int listPos; + /** + * The vertex that this edge represents + **/ + Vertex vertex; + /** + * Contains a reference to a connected quad edge + **/ + Edge next; + + public Edge(){ + } + + /** + * Create a new edge which. + **/ + public Edge(Vertex v, Edge ql[], int pos) + { + vertex = v; + quadList = ql; + listPos = pos; + } + + /** + * Create a new edge which. + **/ + public Edge(Edge ql[], int pos) + { + this(null, ql, pos); + } + + /** + * Create a string representation of the edge + **/ + /*public String toString() + { + if (vertex != null) + return vertex.toString(); + else + return "None"; + }*/ + + public Edge makeEdge(Vertex o, Vertex d) + { + Edge ql[] = new Edge[4]; + ql[0] = new Edge(ql, 0); + ql[1] = new Edge(ql, 1); + ql[2] = new Edge(ql, 2); + ql[3] = new Edge(ql, 3); + + ql[0].next = ql[0]; + ql[1].next = ql[3]; + ql[2].next = ql[2]; + ql[3].next = ql[1]; + + Edge base = ql[0]; + base.setOrig(o); + base.setDest(d); + return base; + } + + public void setNext(Edge n) + { + next = n; + } + + /** + * Initialize the data (vertex) for the edge's origin + **/ + public void setOrig(Vertex o) + { + vertex = o; + } + + /** + * Initialize the data (vertex) for the edge's destination + **/ + public void setDest(Vertex d) + { + symmetric().setOrig(d); + } + + Edge oNext() + { + return next; + } + + Edge oPrev() + { + return this.rotate().oNext().rotate(); + } + + Edge lNext() + { + return this.rotateInv().oNext().rotate(); + } + + Edge lPrev() + { + return this.oNext().symmetric(); + } + + Edge rNext() + { + return this.rotate().oNext().rotateInv(); + } + + Edge rPrev() + { + return this.symmetric().oNext(); + } + + Edge dNext() + { + return this.symmetric().oNext().symmetric(); + } + + Edge dPrev() + { + return this.rotateInv().oNext().rotateInv(); + } + + Vertex orig() + { + return vertex; + } + + Vertex dest() + { + return symmetric().orig(); + } + + /** + * Return the symmetric of the edge. The symmetric is the same edge + * with the opposite direction. + * @return the symmetric of the edge + **/ + Edge symmetric() + { + return quadList[(listPos+2)%4]; + } + + /** + * Return the rotated version of the edge. The rotated version is a + * 90 degree counterclockwise turn. + * @return the rotated version of the edge + **/ + Edge rotate() + { + return quadList[(listPos+1)%4]; + } + + /** + * Return the inverse rotated version of the edge. The inverse + * is a 90 degree clockwise turn. + * @return the inverse rotated edge. + **/ + Edge rotateInv() + { + return quadList[(listPos+3)%4]; + } + + Edge nextQuadEdge() + { + return quadList[(listPos+1)%4]; + } + + Edge connectLeft(Edge b) + { + Vertex t1,t2; + Edge ans, lnexta; + + t1 = dest(); + lnexta = lNext(); + t2 = b.orig(); + Edge e = new Edge(); + ans = e.makeEdge(t1, t2); + ans.splice(lnexta); + ans.symmetric().splice(b); + return ans; + } + + Edge connectRight(Edge b) + { + Vertex t1,t2; + Edge ans, oprevb,q1; + + t1 = dest(); + t2 = b.orig(); + oprevb = b.oPrev(); + + Edge e = new Edge(); + ans = e.makeEdge(t1, t2); + ans.splice(symmetric()); + ans.symmetric().splice(oprevb); + return ans; + } + + /****************************************************************/ + /* Quad-edge manipulation primitives + ****************************************************************/ + void swapedge() + { + Edge a = oPrev(); + Edge syme = symmetric(); + Edge b = syme.oPrev(); + splice(a); + syme.splice(b); + Edge lnexttmp = a.lNext(); + splice(lnexttmp); + lnexttmp = b.lNext(); + syme.splice(lnexttmp); + Vertex a1 = a.dest(); + Vertex b1 = b.dest(); + setOrig(a1); + setDest(b1); + } + + void splice(Edge b) + { + Edge alpha = oNext().rotate(); + Edge beta = b.oNext().rotate(); + Edge t1 = beta.oNext(); + Edge temp = alpha.oNext(); + alpha.setNext(t1); + beta.setNext(temp); + temp = oNext(); + t1 = b.oNext(); + b.setNext(temp); + setNext(t1); + } + + boolean valid(Edge basel) + { + Vertex t1 = basel.orig(); + Vertex t3 = basel.dest(); + Vertex t2 = dest(); + return t1.ccw(t2, t3); + } + + void deleteEdge() + { + Edge f = oPrev(); + splice(f); + f = symmetric().oPrev(); + symmetric().splice(f); + } + + EdgePair doMerge(Edge ldo, Edge ldi, Edge rdi, Edge rdo) + { + boolean torun = true; + while (torun) { + Vertex t3 = rdi.orig(); + Vertex t1 = ldi.orig(); + Vertex t2 = ldi.dest(); + + while (t1.ccw(t2, t3)) { + ldi = ldi.lNext(); + + t1=ldi.orig(); + t2=ldi.dest(); + } + + t2=rdi.dest(); + + if (t2.ccw(t3, t1)) { + rdi = rdi.rPrev(); + } else { + torun = false; + // break; + } + } + + Edge basel = rdi.symmetric().connectLeft(ldi); + + Edge lcand = basel.rPrev(); + Edge rcand = basel.oPrev(); + Vertex t1 = basel.orig(); + Vertex t2 = basel.dest(); + + if (t1 == rdo.orig()) + rdo = basel; + if (t2 == ldo.orig()) + ldo = basel.symmetric(); + + while (true) { + Edge t = lcand.oNext(); + if (t.valid(basel)) { + Vertex v4 = basel.orig(); + + Vertex v1 = lcand.dest(); + Vertex v3 = lcand.orig(); + Vertex v2 = t.dest(); + while (v1.incircle(v2,v3,v4)){ + lcand.deleteEdge(); + lcand = t; + + t = lcand.oNext(); + v1 = lcand.dest(); + v3 = lcand.orig(); + v2 = t.dest(); + } + } + + t = rcand.oPrev(); + if (t.valid(basel)) { + Vertex v4 = basel.dest(); + Vertex v1 = t.dest(); + Vertex v2 = rcand.dest(); + Vertex v3 = rcand.orig(); + while (v1.incircle(v2,v3,v4)) { + rcand.deleteEdge(); + rcand = t; + t = rcand.oPrev(); + v2 = rcand.dest(); + v3 = rcand.orig(); + v1 = t.dest(); + } + } + + boolean lvalid = lcand.valid(basel); + + boolean rvalid = rcand.valid(basel); + if ((!lvalid) && (!rvalid)) { + return new EdgePair(ldo, rdo); + } + + Vertex v1 = lcand.dest(); + Vertex v2 = lcand.orig(); + Vertex v3 = rcand.orig(); + Vertex v4 = rcand.dest(); + if (!lvalid || (rvalid && v1.incircle(v2,v3,v4))) { + basel = rcand.connectLeft(basel.symmetric()); + rcand = basel.symmetric().lNext(); + } else { + basel = lcand.connectRight(basel).symmetric(); + lcand = basel.rPrev(); + } + } + } +} + diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/EdgePair.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/EdgePair.java new file mode 100644 index 00000000..0778de01 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/EdgePair.java @@ -0,0 +1,27 @@ + + +/** + * A class that represents an edge pair + **/ +public class EdgePair +{ + Edge left; + Edge right; + + public EdgePair(Edge l, Edge r) + { + left = l; + right = r; + } + + public Edge getLeft() + { + return left; + } + + public Edge getRight() + { + return right; + } + +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/MyDouble.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/MyDouble.java new file mode 100644 index 00000000..c995c9cc --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/MyDouble.java @@ -0,0 +1,15 @@ + + +/** + * A class that represents a wrapper around a double value so + * that we can use it as an 'out' parameter. The java.lang.Double + * class is immutable. + **/ +public class MyDouble +{ + public float value; + MyDouble(float d) + { + value = d; + } +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/TestRunner.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/TestRunner.java new file mode 100644 index 00000000..aa2f0f58 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/TestRunner.java @@ -0,0 +1,53 @@ + + +/** + * A Java implementation of the voronoi Olden benchmark. Voronoi + * generates a random set of points and computes a Voronoi diagram for + * the points. + *

+ * + * L. Guibas and J. Stolfi. "General Subdivisions and Voronoi Diagrams" + * ACM Trans. on Graphics 4(2):74-123, 1985. + * + *

+ * The Java version of voronoi (slightly) differs from the C version + * in several ways. The C version allocates an array of 4 edges and + * uses pointer addition to implement quick rotate operations. The + * Java version does not use pointer addition to implement these + * operations. + **/ +public class TestRunner extends Thread +{ + + /** + * The number of points in the diagram + **/ + private int points; + + public TestRunner(int npoints) { + this.points = npoints; + } + + /** + * The main routine which creates the points and then performs + * the delaunay triagulation. + * @param args the command line parameters + **/ + public void run() + { + Vertex v = new Vertex(); + v.seed = 1023; + Vertex extra = v.createPoints(1, new MyDouble(1.0f), points); + Vertex point = v.createPoints(points-1, new MyDouble(extra.X()), points-1); + Edge edge = point.buildDelaunayTriangulation(extra); + } + + public static void main(String[] args) { + int threadnum = 62; + int npoints = 32000; + for(int i = 0; i < threadnum; ++i) { + TestRunner tr = new TestRunner(npoints); + tr.run(); + } + } +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/Vec2.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/Vec2.java new file mode 100644 index 00000000..10d1da9e --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/Vec2.java @@ -0,0 +1,121 @@ + + +/** + * Vector Routines from CMU vision library. + * They are used only for the Voronoi Diagram, not the Delaunay Triagulation. + * They are slow because of large call-by-value parameters. + **/ +class Vec2 +{ + float x,y; + float norm; + + public Vec2() {} + + public Vec2(float xx, float yy) + { + x = xx; + y = yy; + norm = (float)(x*x + y*y); + } + + public float X() + { + return x; + } + + public float Y() + { + return y; + } + + public float Norm() + { + return norm; + } + + public void setNorm(float d) + { + norm = d; + } + + /*public String toString() + { + return x + " " + y; + }*/ + + Vec2 circle_center(Vec2 b, Vec2 c) + { + Vec2 vv1 = b.sub(c); + float d1 = vv1.magn(); + vv1 = sum(b); + Vec2 vv2 = vv1.times(0.5f); + if (d1 < 0.0) /*there is no intersection point, the bisectors coincide. */ + return(vv2); + else { + Vec2 vv3 = b.sub(this); + Vec2 vv4 = c.sub(this); + float d3 = vv3.cprod(vv4) ; + float d2 = (float)(-2.0f * d3) ; + Vec2 vv5 = c.sub(b); + float d4 = vv5.dot(vv4); + Vec2 vv6 = vv3.cross(); + Vec2 vv7 = vv6.times((float)(d4/d2)); + return vv2.sum(vv7); + } + } + + + + /** + * cprod: forms triple scalar product of [u,v,k], where k = u cross v + * (returns the magnitude of u cross v in space) + **/ + float cprod(Vec2 v) + { + return((float)(x * v.y - y * v.x)); + } + + /* V2_dot: vector dot product */ + + float dot(Vec2 v) + { + return((float)(x * v.x + y * v.y)); + } + + /* V2_times: multiply a vector by a scalar */ + + Vec2 times(float c) + { + return (new Vec2((float)(c*x), (float)(c*y))); + } + + /* V2_sum, V2_sub: Vector addition and subtraction */ + + Vec2 sum(Vec2 v) + { + return (new Vec2((float)(x + v.x), (float)(y + v.y))); + } + + Vec2 sub(Vec2 v) + { + return(new Vec2((float)(x - v.x), (float)(y - v.y))); + } + +/* V2_magn: magnitude of vector */ + + float magn() + { + return (float) (Math.sqrt((float)(x*x+y*y))); + } + + /* returns k X v (cross product). this is a vector perpendicular to v */ + + Vec2 cross() + { + return(new Vec2((float)y,(float)(-x))); + } +} + + + diff --git a/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/Vertex.java b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/Vertex.java new file mode 100644 index 00000000..6ab45d72 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/NON_BAMBOO/voronoi/Vertex.java @@ -0,0 +1,262 @@ + + +/** + * A class that represents a voronoi diagram. The diagram is represnted + * as a binary tree of points. + **/ +class Vertex extends Vec2 +{ + /** + * The left child of the tree that represents the voronoi diagram. + **/ + Vertex left; + /** + * The right child of the tree that represents the voronoi diagram. + **/ + Vertex right; + + /** + * Seed value used during tree creation. + **/ + int seed; + + public Vertex() { } + + public Vertex(float x, float y) + { + super(x, y); + left = null; + right = null; + } + + public void setLeft(Vertex l) + { + left = l; + } + + public void setRight(Vertex r) + { + right = r; + } + + public Vertex getLeft() + { + return left; + } + + public Vertex getRight() + { + return right; + } + + /** + * Generate a voronoi diagram + **/ + Vertex createPoints(int n, MyDouble curmax, int i) + { + if (n < 1 ) { + return null; + } + + Vertex cur = new Vertex(); + + Vertex right = cur.createPoints(n/2, curmax, i); + i -= n/2; + cur.x = (float)(curmax.value * Math.exp(Math.log((float)this.drand())/i)); + cur.y = (float)this.drand(); + cur.norm = (float)(cur.x * cur.x + cur.y*cur.y); + cur.right = right; + curmax.value = (float)cur.X(); + Vertex left = cur.createPoints(n/2, curmax, i-1); + + cur.left = left; + return cur; + } + + + /** + * Builds delaunay triangulation. + **/ + Edge buildDelaunayTriangulation(Vertex extra) + { + EdgePair retVal = buildDelaunay(extra); + return retVal.getLeft(); + } + + /** + * Recursive delaunay triangulation procedure + * Contains modifications for axis-switching division. + **/ + EdgePair buildDelaunay(Vertex extra) + { + EdgePair retval = null; + if (getRight() != null && getLeft() != null) { + // more than three elements; do recursion + Vertex minx = getLow(); + Vertex maxx = extra; + + EdgePair delright = getRight().buildDelaunay(extra); + EdgePair delleft = getLeft().buildDelaunay(this); + + Edge e = new Edge(); + retval = e.doMerge(delleft.getLeft(), delleft.getRight(), + delright.getLeft(), delright.getRight()); + + Edge ldo = retval.getLeft(); + while (ldo.orig() != minx) { + ldo = ldo.rPrev(); + } + Edge rdo = retval.getRight(); + while (rdo.orig() != maxx) { + rdo = rdo.lPrev(); + } + + retval = new EdgePair(ldo, rdo); + + } else if (getLeft() == null) { + // two points + Edge e = new Edge(); + Edge a = e.makeEdge(this, extra); + retval = new EdgePair(a, a.symmetric()); + } else { + // left, !right three points + // 3 cases: triangles of 2 orientations, and 3 points on a line. */ + Vertex s1 = getLeft(); + Vertex s2 = this; + Vertex s3 = extra; + Edge e = new Edge(); + Edge a = e.makeEdge(s1, s2); + Edge b = e.makeEdge(s2, s3); + a.symmetric().splice(b); + Edge c = b.connectLeft(a); + if (s1.ccw(s3, s2)) { + retval = new EdgePair(c.symmetric(), c); + } else { + retval = new EdgePair(a, b.symmetric()); + if (s1.ccw(s2, s3)) + c.deleteEdge(); + } + } + return retval; + } + + /** + * Print the tree + **/ + /*void print() + { + Vertex tleft, tright; + + System.out.println("X=" + X() + " Y=" + Y()); + if (left == null) + System.out.println("NULL"); + else + left.print(); + if (right == null) + System.out.println("NULL"); + else + right.print(); + }*/ + + /** + * Traverse down the left child to the end + **/ + Vertex getLow() + { + Vertex temp; + Vertex tree = this; + + while ((temp=tree.getLeft()) != null) + tree = temp; + return tree; + } + + /****************************************************************/ + /* Geometric primitives + ****************************************************************/ + boolean incircle(Vertex b, Vertex c, Vertex d) + /* incircle, as in the Guibas-Stolfi paper. */ + { + float adx, ady, bdx, bdy, cdx, cdy, dx, dy, anorm, bnorm, cnorm, dnorm; + float dret ; + Vertex loc_a,loc_b,loc_c,loc_d; + + int donedx,donedy,donednorm; + loc_d = d; + dx = loc_d.X(); dy = loc_d.Y(); dnorm = loc_d.Norm(); + loc_a = this; + adx = loc_a.X() - dx; ady = loc_a.Y() - dy; anorm = loc_a.Norm(); + loc_b = b; + bdx = loc_b.X() - dx; bdy = loc_b.Y() - dy; bnorm = loc_b.Norm(); + loc_c = c; + cdx = loc_c.X() - dx; cdy = loc_c.Y() - dy; cnorm = loc_c.Norm(); + dret = (float)((anorm - dnorm) * (bdx * cdy - bdy * cdx)); + dret += (float)((bnorm - dnorm) * (cdx * ady - cdy * adx)); + dret += (float)((cnorm - dnorm) * (adx * bdy - ady * bdx)); + return( (0.0f < dret) ? true : false ); + } + + boolean ccw(Vertex b, Vertex c) + /* TRUE iff this, B, C form a counterclockwise oriented triangle */ + { + float dret ; + float xa,ya,xb,yb,xc,yc; + Vertex loc_a,loc_b,loc_c; + + int donexa,doneya,donexb,doneyb,donexc,doneyc; + + loc_a = this; + xa = loc_a.X(); + ya = loc_a.Y(); + loc_b = b; + xb = loc_b.X(); + yb = loc_b.Y(); + loc_c = c; + xc = loc_c.X(); + yc = loc_c.Y(); + dret = (float)((float)(xa-xc)*(float)(yb-yc) - (float)(xb-xc)*(float)(ya-yc)); + return( (dret > 0.0f)? true : false); + } + + /** + * A routine used by the random number generator + **/ + int mult(int p,int q) + { + int p1, p0, q1, q0; + int CONST_m1 = 10000; + + p1=p/CONST_m1; p0=p%CONST_m1; + q1=q/CONST_m1; q0=q%CONST_m1; + return (((p0*q1+p1*q0) % CONST_m1)*CONST_m1+p0*q0); + } + + /** + * Generate the nth random number + **/ + int skiprand(int seed, int n) + { + for (; n != 0; n--) + seed=random(seed); + return seed; + } + + int random(int seed) + { + int CONST_b = 31415821; + + seed = mult(seed, CONST_b) + 1; + return seed; + } + + float drand() + { + this.seed = this.random(this.seed); + float retval = ((float)this.seed) / + (float) 2147483647; + return retval; + } + +} + + -- 2.34.1