README.md

The Unbalanced Tree Search benchmark (UTS)

Formulation

The problem consists in counting the number of nodes in an implicitly constructed tree that is parameterized in shape, depth, size and imbalance [1]. UTS trees are generated using a process, in which the number of children of a node is a random variable with a given distribution. Our implementation supports binomial trees, i.e. each node has $m$ children with probability $q$ and has no children with probability $1-q$, where $q\in [0,1]$. When $mq < 1$, this process generates a finite tree, and the variation of subtree sizes increases dramatically as $mq$ approaches $1$. The root-specific branching factor $b$ can be set sufficiently high to generate an interesting variety of subtree sizes below the root. Another root-specific parameter is $r$. Multiple instances of a tree type can be generated by varying this parameter, hence providing a check on the validity of an implementation. Finally, to vary the granularity, we introduced the $g$ parameter which controls the number of random number generation(s) per decomposed node.

Configuration options

./main_uts.out {...}

where the available options are:

• --t: tree type

  • 0: binary (default)
  • 1: geometric
  • 2: hybrid
  • 3: balanced

• --m: number of children per node in binary trees

  • any positive integer (2 by default)

• --q: probability of having child nodes in binary trees

  • any real number between 0.0 and 1.0 (0.499995 by default)

• --b: root branching factor

  • any positive integer (2000 by default)

• --r: seed for RNG state at root

  • any positive integer (0 by default)

• --g: instance granularity

  • any positive integer (1 by default)

sample_trees_UTS.sh contains sample workloads for UTS, along with the tree statistics.

References

1. S. Olivier, J. Huan, J. Liu, et al. (2007) UTS: An Unbalanced Tree Search Benchmark. 19th International Workshop on Languages and Compilers for Parallel Computing. DOI: 10.1007/978-3-540-72521-3_18.