//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// // // 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 final class Tree { // TREE TYPE AND SHAPE CONSTANTS static final String TREES[] = { "Binomial","Geometric","Hybrid" }; 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 String SHAPES[] = {"Linear decrease","Exponential decrease","Cyclic","Fixed branching factor"}; 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 // SENTINEL VALUES static final int UNSETI = -1; // sentinel for unset integer values static final double UNSETD =-1.0; // sentinel for unset double values // 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 OPTIONS 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 long nNodes = 0; // total number of nodes discovered in tree private long 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.initRoot(); tree.showParams(); tree.startTimer(); tree.nNodes=tree.search(tree.root); tree.stopTimer(); tree.showStats(); } long search(Node parent){ // how many nodes in subtree rooted at parent, inclusive? long nodeCount=1; atomic maxTreeDepth = Math.max(parent.height, maxTreeDepth); int numChildren = parent.numChildren(); if (numChildren > 0) { final int NC = numChildren; final dist D = [0:NC]->here; final future[.] nc = new future[D]; // (point[i]) { return 0; }; for(int i = 0; i < NC; i++) { final Node tmp = parent; final int spawn = i; nc[i] = future { search((new Node(tmp,spawn))) }; } for(int i=0; i 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