//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// // // Tree -- Unbalanced Tree Search Benchmark // // Primary Algorithm: Sequential, Recursive Depth First // // Comments: // // Despite this being a tree search, there is no stored "tree", per se, // traversed by the search. Rather, the tree nodes are generated on the fly by // identifying each node with a random number in a very large sequence. Thus at // any given time, only a small number of nodes are "live" and thus retained // in memory. This allows for very large tree searches to be configured and // tested even with limit memory. // // Since there is no "tree" and no parent-child pointers, the "link" from parent // to child is obtained by creating the identifier for each chi ld based on // the identifier of the parent. The parent's identifier is the state of a // split-able random number generator. The parent's children are obtained by // reseeding the random number generator using the parent's local identifier // for each child and the parent's node idetifier. // //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// // gripe: import static doesn't work... makes using Math VERY VERY clumsy. import java.lang.Math; public class Tree { // TREE TYPE AND SHAPE CONSTANTS static final int BIN = 0; // TYPE: binomial tree static final int GEO = 1; // TYPE: geometric tree static final int HYBRID = 2; // TYPE: hybrid tree, start geometric, shift to binomial static final int LINEAR = 0; // SHAPE: linearly decreasing geometric tree static final int EXPDEC = 1; // SHAPE: exponentially decreasing geometric tree static final int CYCLIC = 2; // SHAPE: cyclic geometric tree static final int FIXED = 3; // SHAPE: fixed branching factor geometric tree static final int UNSETI =-1; // sentinel for unset integer values static final double UNSETD =-1.0; // sentinel for unset double values static final String TREES[] = {"Binomial","Geometric","Hybrid" }; static final String SHAPES[] = {"Linear decrease","Exponential decrease","Cyclic","Fixed branching factor"}; // Tree parameters and defaults private int treetype = GEO; // Tree Type: Default = GEO private double b_0 = 4.0; // branching factor for root node private int rootId = 0; // RNG seed for root node private int nonLeafBF = 4; // BINOMIAL TREE: branching factor for nonLeaf nodes private double nonLeafProb = 15.0/64.0; // BINOMIAL TREE: probability a node is a nonLeaf private int gen_mx = 6; // GEOMETRIC TREE: maximum number of generations private int shape_fn = LINEAR; // GEOMETRIC TREE: shape function: Default = LINEAR private double shiftDepth = 0.5; // HYBRID TREE: Depth fraction for shift from GEO to BIN private int computeGran = 1; // number of RNG evaluations per tree node private Node root; // output parameters private int debug = 0; // debug level private int verbose = 1; // output verbosity level private int stats = 0; // keep stats // Tree Performance Statistics private double searchTimer = 0; // search timer private int nNodes = 0; // total number of nodes discovered in tree private int nLeaves = 0; // total number of leafnodes discovered in tree private int maxTreeDepth = 0; // maximum tree depth public static void main(String args[]){ BenchmarkParameters benchmark = new BenchmarkParameters(); benchmark.parse(args); Tree tree = new Tree(benchmark); tree.showParams(); for(int i=0; i<10; i++) { tree.initRoot(); tree.startTimer(); tree.search(tree.root); tree.stopTimer(); tree.showStats(); } } void search(Node parent){ maxTreeDepth = Math.max(parent.height, maxTreeDepth); int numChildren = parent.numChildren(); if (numChildren > 0) { for(int i = 0; i < numChildren; i++) { search((new Node(parent,i))); } } else { ++nLeaves; } return; }; void initRoot(){ root = new Node(rootId); nNodes=0; nLeaves=0; maxTreeDepth=0; }; void showStats(){ // System.out.println("Tree size = " + nNodes + ", tree depth = " + maxTreeDepth + ", num leaves = " + nLeaves + " (" + fourdeci(100.*(double)nLeaves/(double)nNodes) + "%)" ); // System.out.println("Wallclock time = " + searchTimer + " sec, performance = " + (int)((double)nNodes/searchTimer) + " nodes/sec"); System.out.println("Tree size = " + nNodes + ", tree depth = " + maxTreeDepth + ", num leaves = " + nLeaves + " (" + (100.*fourdeci((double)nLeaves/(double)nNodes)) + "%) " + "Wallclock time = " + fourdeci(searchTimer) + " sec, performance = " + (int)((double)nNodes/searchTimer) + " nodes/sec"); }; double fourdeci(double val) { return Math.floor(val*10000. + 0.5)/10000.0; } void startTimer(){ searchTimer = -(double)System.nanoTime(); }; void stopTimer(){ searchTimer += (double)System.nanoTime(); searchTimer /= 1.0e+9; }; void showParams(){ System.out.println("UTS - Unbalanced Tree Search (X10 implementation)"); System.out.println("Tree Type: " + treetype + " (" + TREES[treetype] + ")"); System.out.println("Tree shape parameters:"); System.out.println(" root branching factor b_0 = " + b_0 + ", root seed = " + rootId); switch (treetype) { case BIN: System.out.println(" BIN parameters: q = " + nonLeafProb + ", m = " + nonLeafBF + ", E(n) = " + nonLeafProb*nonLeafBF + ", E(s) = " + (1.0 / (1.0 - nonLeafProb * nonLeafBF))); break; case GEO: System.out.println(" GEO parameters: gen_mx = " + gen_mx + ", shape function = " + shape_fn + "(" + SHAPES[shape_fn] + ")"); break; case HYBRID: System.out.println(" GEO parameters: gen_mx = " + gen_mx + ", shape function = " + shape_fn + " (" + SHAPES[shape_fn] + ")"); System.out.println(" BIN parameters: q = " + nonLeafProb + ", m = " + nonLeafBF + ", E(n) = " + nonLeafProb*nonLeafBF + ", E(s) = " + (1.0 / (1.0 - nonLeafProb * nonLeafBF))); System.out.println(" HYBRID: GEO from root to depth " + (int) Math.ceil(shiftDepth * gen_mx) + ", then BIN"); break; default: break; } System.out.println("Compute granularity: " + computeGran); System.out.println("Execution strategy: " + getName()); System.out.println(""); }; String getName(){ return "Sequential Recursive Search"; } String getType(){ return TREES[treetype]; }; String getShape(){ return SHAPES[shape_fn]; }; Tree(BenchmarkParameters params){ treetype = params.treetype(treetype); b_0 = params.branchingfactor(b_0); rootId = params.rootseed(rootId); nonLeafBF = params.BINnonleafnumchildren(nonLeafBF); nonLeafProb = params.BINnonleafprobability(nonLeafProb); gen_mx = params.GEOdepth(gen_mx); shape_fn = params.GEOshape(shape_fn); shiftDepth = params.HYBRIDtransitiondepth(shiftDepth); computeGran = params.computegranularity(computeGran); debug = params.debuglevel(debug); verbose = params.verbosity(verbose); stats = params.statlevel(stats); }; public class Node{ // Node State SHA1Generator state; int type; int height; int nChildren; // misc constants static final double TWO_PI = 2.0*Math.PI; static final int MAXNUMCHILDREN = 100; // max number of children for BIN tree // Tree Statistics // private static final int MAXHISTSIZE = 2000; // max tree depth in histogram // private static final int unbType = 1; // private static final int maxHeight = 0; // maximum depth of tree // private static final double maxImb = 0; // maximum imbalance // private static final double minImb = 1; // private static final double treeImb =-1; // Overall imbalance, undefined // private static final int *rootSize; // size of the root's children // private static final double *rootUnb; // imbalance of root's children // private static final int hist[MAXHISTSIZE+1][2]; // average # nodes per level // private static final double unbhist[MAXHISTSIZE+1][3]; // average imbalance per level // Tseng statistics // private static final int totalNodes = 0; // total number of nodes // private static final double imb_max = 0; // % work in largest child [100/n,100%] // private static final double imb_avg = 0; // private static final double imb_devmaxavg = 0; // private static final double imb_normdevmaxavg = 0; Node(int rootID) { // root constructor: count the nodes as they are created state = new SHA1Generator(rootID); type = treetype; height = 0; nChildren = -1; nNodes++; }; Node(Node parent, int spawn) { // child constructor: count the nodes as they are created for(int j=0; j rootBF) { System.out.println("*** Number of children of root truncated from " +nChildren+" to "+rootBF); nChildren = rootBF; } } else { if (nChildren > MAXNUMCHILDREN) { System.out.println("*** Number of children truncated from " +nChildren+" to "+MAXNUMCHILDREN); nChildren = MAXNUMCHILDREN; } } return nChildren; }; int numChildren_bin(){ // Binomial: distribution is identical below root int nc; if (height == 0) nc = (int)Math.floor(b_0); else if (rng_toProb(state.rand()) < nonLeafProb) nc = nonLeafBF; else nc = 0; return nc; }; int numChildren_geo(){ // Geometric: distribution controlled by shape and height double b_i = b_0; if (height > 0){ switch (shape_fn) { // use shape function to compute target b_i case EXPDEC: // expected size polynomial in height b_i = b_0*Math.pow((double)height,-Math.log(b_0)/Math.log((double)gen_mx)); break; case CYCLIC: // cyclic tree if (height > 5 * gen_mx) { b_i = 0.0; break; } b_i = Math.pow(b_0,Math.sin(TWO_PI*(double)height/(double)gen_mx)); break; case FIXED: // identical distribution at all nodes up to max height b_i = (height < gen_mx)? b_0 : 0; break; case LINEAR: // linear decrease in b_i default: b_i = b_0 * ( 1.0 - ((double)height/(double)gen_mx) ); break; } } double p = 1.0 / (1.0 + b_i); // probability corresponding to target b_i double u = rng_toProb(state.rand()); // get uniform random number on [0,1) // return max number of children at this cumulative probability // (inverse geometric cumulative density function) return (int)Math.floor(Math.log(1.0 - u) / Math.log(1.0 - p)); }; int childType(){ // determine what kind of children this node will have switch (type) { case BIN: return BIN; case GEO: return GEO; case HYBRID: if (height < shiftDepth * gen_mx) return GEO; else return BIN; default: error("uts_get_childtype(): Unknown tree type"); return -1; } }; double rng_toProb(int n){ // convert a random number on [0,2^31) to one on [0.1) // if (n < 0) error("*** toProb: rand n = " + n + " out of range"); return ((n<0)? 0.0 : ((double) n)/2147483648.0); }; void error(String data){ // bailout with error message System.out.println(data); System.exit(1); } }; // Node }; // Tree