From 2f4c7c226368ecb12efaa58ea60dd452c0f0f2bf Mon Sep 17 00:00:00 2001 From: jzhou Date: Wed, 28 Jul 2010 03:50:30 +0000 Subject: [PATCH] Add the BH benchmark from JOlden for the multicore gc --- .../Scheduling/GC/Fibheaps/FibHeapsBench.java | 2 +- .../GC/RayTracer/RayTracerBench.java | 2 +- .../Benchmarks/Scheduling/GC/bh/BHBench.java | 23 ++ .../src/Benchmarks/Scheduling/GC/bh/Body.java | 242 ++++++++++++++ .../src/Benchmarks/Scheduling/GC/bh/Cell.java | 132 ++++++++ .../src/Benchmarks/Scheduling/GC/bh/Makefile | 3 + .../Scheduling/GC/bh/MathVector.java | 241 ++++++++++++++ .../src/Benchmarks/Scheduling/GC/bh/Node.java | 112 +++++++ .../Scheduling/GC/bh/TestRunner.java | 168 ++++++++++ .../src/Benchmarks/Scheduling/GC/bh/Tree.java | 298 ++++++++++++++++++ .../Benchmarks/Scheduling/GC/bh/benchmark.py | 3 + .../Scheduling/GC/lcss/LcssBench.java | 4 +- .../Scheduling/GC/voronoi/VoronoiBench.java | 2 +- Robust/src/Runtime/multicoreruntime.h | 5 + Robust/src/buildscript | 22 +- 15 files changed, 1252 insertions(+), 7 deletions(-) create mode 100644 Robust/src/Benchmarks/Scheduling/GC/bh/BHBench.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/bh/Body.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/bh/Cell.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/bh/Makefile create mode 100644 Robust/src/Benchmarks/Scheduling/GC/bh/MathVector.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/bh/Node.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/bh/TestRunner.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/bh/Tree.java create mode 100644 Robust/src/Benchmarks/Scheduling/GC/bh/benchmark.py diff --git a/Robust/src/Benchmarks/Scheduling/GC/Fibheaps/FibHeapsBench.java b/Robust/src/Benchmarks/Scheduling/GC/Fibheaps/FibHeapsBench.java index 4ffc2453..46e295f1 100644 --- a/Robust/src/Benchmarks/Scheduling/GC/Fibheaps/FibHeapsBench.java +++ b/Robust/src/Benchmarks/Scheduling/GC/Fibheaps/FibHeapsBench.java @@ -19,4 +19,4 @@ task t2(TestRunner tr{run}) { //System.printString("task t2\n"); tr.run(); taskexit(tr{!run}); -} \ No newline at end of file +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/RayTracer/RayTracerBench.java b/Robust/src/Benchmarks/Scheduling/GC/RayTracer/RayTracerBench.java index 5a288fda..3e562ea3 100644 --- a/Robust/src/Benchmarks/Scheduling/GC/RayTracer/RayTracerBench.java +++ b/Robust/src/Benchmarks/Scheduling/GC/RayTracer/RayTracerBench.java @@ -1,7 +1,7 @@ task t1(StartupObject s{initialstate}) { //System.printString("task t1\n"); - int threadnum = 62; // 56; + int threadnum = 56; // 62; // 56; int size = threadnum * 25; Composer comp = new Composer(threadnum, size){compose}; RayTracer rt = new RayTracer(); diff --git a/Robust/src/Benchmarks/Scheduling/GC/bh/BHBench.java b/Robust/src/Benchmarks/Scheduling/GC/bh/BHBench.java new file mode 100644 index 00000000..2c7e839d --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/bh/BHBench.java @@ -0,0 +1,23 @@ +/** Bamboo Version + * Ported by: Jin Zhou 07/26/10 + * + * This is ported from the NoFib, originally written in Haskell + * **/ + +task t1(StartupObject s{initialstate}) { + //System.printString("task t1\n"); + + int threadnum = 62; // 56; + int nbody = 700; //4096; //30000; + for(int i = 0; i < threadnum; ++i) { + TestRunner tr = new TestRunner(nbody){run}; + } + + taskexit(s{!initialstate}); +} + +task t2(TestRunner tr{run}) { + //System.printString("task t2\n"); + tr.run(); + taskexit(tr{!run}); +} \ No newline at end of file diff --git a/Robust/src/Benchmarks/Scheduling/GC/bh/Body.java b/Robust/src/Benchmarks/Scheduling/GC/bh/Body.java new file mode 100644 index 00000000..bc341f49 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/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/bh/Cell.java b/Robust/src/Benchmarks/Scheduling/GC/bh/Cell.java new file mode 100644 index 00000000..4e83ee96 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/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/bh/Makefile b/Robust/src/Benchmarks/Scheduling/GC/bh/Makefile new file mode 100644 index 00000000..2efba011 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/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/bh/MathVector.java b/Robust/src/Benchmarks/Scheduling/GC/bh/MathVector.java new file mode 100644 index 00000000..e81e8266 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/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/bh/Node.java b/Robust/src/Benchmarks/Scheduling/GC/bh/Node.java new file mode 100644 index 00000000..2d2cbaaa --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/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/bh/TestRunner.java b/Robust/src/Benchmarks/Scheduling/GC/bh/TestRunner.java new file mode 100644 index 00000000..6181b2f2 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/bh/TestRunner.java @@ -0,0 +1,168 @@ + +/*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 +{ + flag run; + + /** + * 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; + } + + /** + * 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++]; + + // check for options that require arguments + if (arg.equals("-b")) { + if (i < args.length) { + nbody = new Integer(args[i++]).intValue(); + } else { + throw new Error("-l requires the number of levels"); + } + } else if (arg.equals("-s")) { + if (i < args.length) { + nsteps = new Integer(args[i++]).intValue(); + } else { + throw new Error("-l requires the number of levels"); + } + } else if (arg.equals("-m")) { + printMsgs = true; + } else if (arg.equals("-p")) { + printResults = true; + } else if (arg.equals("-h")) { + usage(); + } + } + if (nbody == 0) usage(); + }*/ + + /** + * The usage routine which describes the program options. + **/ + /*private static final void usage() + { + System.err.println("usage: java BH -b [-s ] [-p] [-m] [-h]"); + System.err.println(" -b the number of bodies"); + System.err.println(" -s the max. number of time steps (default=10)"); + System.err.println(" -p (print detailed results)"); + System.err.println(" -m (print information messages"); + System.err.println(" -h (this message)"); + System.exit(0); + }*/ + +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/bh/Tree.java b/Robust/src/Benchmarks/Scheduling/GC/bh/Tree.java new file mode 100644 index 00000000..6dea99a8 --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/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/bh/benchmark.py b/Robust/src/Benchmarks/Scheduling/GC/bh/benchmark.py new file mode 100644 index 00000000..64db9dab --- /dev/null +++ b/Robust/src/Benchmarks/Scheduling/GC/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/lcss/LcssBench.java b/Robust/src/Benchmarks/Scheduling/GC/lcss/LcssBench.java index 044c2924..1bdeefe4 100644 --- a/Robust/src/Benchmarks/Scheduling/GC/lcss/LcssBench.java +++ b/Robust/src/Benchmarks/Scheduling/GC/lcss/LcssBench.java @@ -1,5 +1,5 @@ /** Bamboo Version - * Ported by: Jin Zhou 07/15/10 + * Ported by: Jin Zhou 07/23/10 * * This is ported from the NoFib, originally written in Haskell * **/ @@ -26,4 +26,4 @@ task t2(TestRunner tr{run}) { //System.printString("task t2\n"); tr.run(); taskexit(tr{!run}); -} \ No newline at end of file +} diff --git a/Robust/src/Benchmarks/Scheduling/GC/voronoi/VoronoiBench.java b/Robust/src/Benchmarks/Scheduling/GC/voronoi/VoronoiBench.java index 22a88fd8..f1c44a96 100644 --- a/Robust/src/Benchmarks/Scheduling/GC/voronoi/VoronoiBench.java +++ b/Robust/src/Benchmarks/Scheduling/GC/voronoi/VoronoiBench.java @@ -20,4 +20,4 @@ task t2(TestRunner tr{run}) { //System.printString("task t2\n"); tr.run(); taskexit(tr{!run}); -} \ No newline at end of file +} diff --git a/Robust/src/Runtime/multicoreruntime.h b/Robust/src/Runtime/multicoreruntime.h index 80e77da3..df49ed10 100644 --- a/Robust/src/Runtime/multicoreruntime.h +++ b/Robust/src/Runtime/multicoreruntime.h @@ -294,6 +294,8 @@ struct Queue * totransobjqueue; // queue to hold objs to be transferred #else #ifdef GC_LARGESHAREDHEAP #define BAMBOO_NUM_PAGES ((GC_BAMBOO_NUMCORES)*(2+2)) +#elif defined GC_LARGESHAREDHEAP2 +#define BAMBOO_NUM_PAGES ((GC_BAMBOO_NUMCORES)*(2+2)) #else #define BAMBOO_NUM_PAGES ((GC_BAMBOO_NUMCORES)*(2+3)) //(15 * 1024) //(64 * 4 * 0.75) //(1024 * 1024 * 3.5) 3G #endif @@ -303,6 +305,9 @@ struct Queue * totransobjqueue; // queue to hold objs to be transferred #elif defined GC_SMALLPAGESIZE #define BAMBOO_PAGE_SIZE (256 * 1024) // (4096) #define BAMBOO_SMEM_SIZE (256 * 1024) +#elif defined GC_SMALLPAGESIZE2 +#define BAMBOO_PAGE_SIZE (256 * 1024) // (4096) +#define BAMBOO_SMEM_SIZE (256 * 1024) #else #define BAMBOO_PAGE_SIZE (1024 * 1024) // (4096) #define BAMBOO_SMEM_SIZE (1024 * 1024) diff --git a/Robust/src/buildscript b/Robust/src/buildscript index 3545225f..d5968554 100755 --- a/Robust/src/buildscript +++ b/Robust/src/buildscript @@ -48,9 +48,9 @@ echo "-gccache_local set the gc shared memory cache strategy as local (should be echo "-gccache_ran set the gc shared memory cache strategy as random (should be used together with -multicoregc)" echo "-gccontroller_near set the gc shared memory to use the nearest controller for each core (should be used together with -multicoregc)" echo "-gccontroller_remote set the gc shared memory to use a remote controller for each core (should be used together with -multicoregc)" -echo "-gcsmallpagesize set the gc shared memory to use small page size (should be used together with -multicoregc)" +echo "-gcsmallpagesize(2) set the gc shared memory to use small page size (should be used together with -multicoregc)" echo "-gclargepagesize set the gc shared memory to use large page size (should be used together with -multicoregc)" -echo "-gclargesharedheap set the gc shared memory as large (should be used together with -multicoregc)" +echo "-gclargesharedheap(2) set the gc shared memory as large (should be used together with -multicoregc)" echo -gcprofile build with gcprofile options echo "-tilera_memprof build the memprof version (should be used together with -tilera_xx) " echo -accurateprofile build with accurate profile information including pre/post task processing info @@ -153,6 +153,8 @@ GCCONTROLLERREMOTEFLAG=false; GCSMALLPAGESIZEFLAG=false; GCLARGEPAGESIZEFLAG=false; GCLARGESHAREDHEAPFLAG=false; +GCSMALLPAGESIZEFLAG2=false; +GCLARGESHAREDHEAPFLAG2=false; USEDMALLOC=false THREADFLAG=false FASTCHECK=false @@ -419,12 +421,18 @@ GCCONTROLLERREMOTEFLAG=true elif [[ $1 = '-gcsmallpagesize' ]] then GCSMALLPAGESIZEFLAG=true +elif [[ $1 = '-gcsmallpagesize2' ]] +then +GCSMALLPAGESIZEFLAG2=true elif [[ $1 = '-gclargepagesize' ]] then GCLARGEPAGESIZEFLAG=true elif [[ $1 = '-gclargesharedheap' ]] then GCLARGESHAREDHEAPFLAG=true +elif [[ $1 = '-gclargesharedheap2' ]] +then +GCLARGESHAREDHEAPFLAG2=true elif [[ $1 = '-dmalloc' ]] then USEDMALLOC=true @@ -877,6 +885,16 @@ then # GC_LARGESHAREDHEAP version TILERACFLAGS="${TILERACFLAGS} -DGC_LARGESHAREDHEAP" fi +if $GCSMALLPAGESIZEFLAG2 +then # GC_SMALLPAGESIZE2 version +TILERACFLAGS="${TILERACFLAGS} -DGC_SMALLPAGESIZE2" +fi + +if $GCLARGESHAREDHEAPFLAG2 +then # GC_LARGESHAREDHEAP2 version +TILERACFLAGS="${TILERACFLAGS} -DGC_LARGESHAREDHEAP2" +fi + cp $ROBUSTROOT/Tilera/Runtime/$TILERA_INDIR/$MAKEFILE ./Makefile if $TILERABMEFLAG -- 2.34.1