UTS: An unbalanced tree search benchmark

Stephen Olivier, Jun Huan, Jinze Liu, Jan Prins, James Dinan, P. Sadayappan, Chau Wen Tseng

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

124 Scopus citations


This paper presents an unbalanced tree search (UTS) benchmark designed to evaluate the performance and ease of programming for parallel applications requiring dynamic load balancing. We describe algorithms for building a variety of unbalanced search trees to simulate different forms of load imbalance. We created versions of UTS in two parallel languages, OpenMP and Unified Parallel C (UPC), using work stealing as the mechanism for reducing load imbalance. We benchmarked the performance of UTS on various parallel architectures, including shared-memory systems and PC clusters. We found it simple to implement UTS in both UPC and OpenMP, due to UPCs shared-memory abstractions. Results show that both UPC and OpenMP can support efficient dynamic load balancing on shared-memory architectures. However, UPC cannot alleviate the underlying communication costs of distributed-memory systems. Since dynamic load balancing requires intensive communication, performance portability remains difficult for applications such as UTS and performance degrades on PC clusters. By varying key work stealing parameters, we expose important tradeoffs between the granularity of load balance, the degree of parallelism, and communication costs.

Original languageEnglish
Title of host publicationLanguages and Compilers for Parallel Computing - 19th International Workshop, LCPC 2006, Revised Papers
Number of pages16
StatePublished - 2007
Event19th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2006 - New Orleans, LA, United States
Duration: Nov 2 2006Nov 4 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4382 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference19th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2006
Country/TerritoryUnited States
CityNew Orleans, LA

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)


Dive into the research topics of 'UTS: An unbalanced tree search benchmark'. Together they form a unique fingerprint.

Cite this