UTS
Line 1: | Line 1: | ||
− | The Unbalanced Tree Search benchmark is a parallel benchmarking code that reports the performance achieved when performing exhaustive | + | The Unbalanced Tree Search (UTS) benchmark is a parallel benchmarking code that reports the performance achieved when performing an exhaustive search on an unbalanced tree. The tree is generated on the fly using a splittable random number generator (RNG) |
+ | that allows the random stream to be split and processed in parallel while still producing a deterministic tree. The splittable RNG has been constructed using the SHA1 secure hash algorithm. Thus, generating a node's children requires multiple applications of the SHA1 hash algorithm to generate splittable hashes for each child. | ||
== Project Members == | == Project Members == | ||
Line 24: | Line 25: | ||
* MPI | * MPI | ||
* UPC | * UPC | ||
+ | * OpenMP | ||
* Shmem | * Shmem | ||
* GPShmem | * GPShmem |
Revision as of 20:42, 12 May 2009
The Unbalanced Tree Search (UTS) benchmark is a parallel benchmarking code that reports the performance achieved when performing an exhaustive search on an unbalanced tree. The tree is generated on the fly using a splittable random number generator (RNG) that allows the random stream to be split and processed in parallel while still producing a deterministic tree. The splittable RNG has been constructed using the SHA1 secure hash algorithm. Thus, generating a node's children requires multiple applications of the SHA1 hash algorithm to generate splittable hashes for each child.
Contents |
Project Members
The Ohio State University
- Professor P. Sadayappan
- James Dinan
- Gerald Sabin
University of Maryland
- Professor Chau-Wen Tseng
University of North Carolina
- Professor Jan Prins
- Stephen Olivier
Implementations of UTS
UTS has been implemented in the following parallel models:
- MPI
- UPC
- OpenMP
- Shmem
- GPShmem
- Pthreads
- Cray MTA/XMT
- Chapel
- Scioto
Papers
Scalable Dynamic Load Balancing Using UPC PDF Stephen Olivier, Jan Prins. Proc. of 37th International Conference on Parallel Processing (ICPP-08). Portland, OR, September 2008.
A Message Passing Benchmark for Unbalanced Applications DOI James Dinan, Stephen Olivier, Gerald Sabin, Jan Prins, P. Sadayappan, Chau-Wen Tseng Simulation Modelling Practice and Theory, In Press. June, 2008.
Dynamic Load Balancing of Unbalanced Computations Using Message Passing PDF Slides James Dinan, Stephen Olivier, Jan Prins, Gerald Sabin, P Sadayappan and Chau-Wen Tseng. Proc. of 6th Intl. Workshop on Performance Modeling, Evaluation, and Optimization of Parallel and Distributed Systems (PMEO-PDS 2007). Long Beach, CA, March 26-30, 2007.
UTS: An Unbalanced Tree Search Benchmark PDF Stephen Olivier, Jun Huan, Jinze Liu, Jan Prins, James Dinan, P Sadayappan and Chau-Wen Tseng. Proceedings of 19th Intl. Workshop on Languages and Compilers for Parallel Computing (LCPC 2006).
Download
We are cleaning up our code for a public release. If you'd like a pre-release copy of the benchmark, please contact James Dinan via email at dinan-at-cse.ohio-state.edu.