UTS

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.