Abstract
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 UPC’s 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.
This work was supported by the U.S. Department of Defense.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Harris, T.: The Theory of Branching Processes. Springer, Heidelberg (1963)
Eastlake, D., Jones, P.: US secure hash algorithm 1 (SHA-1). Internet Engineering Task Force, RFC 3174 (Sept. 2001), Available at http://www.rfc-editor.org/rfc/rfc3174.txt
Leskovec, J., Kleinberg, J., Faloutsos, C.: Graphs over time: densification laws, shrinking diameters and possible explanations. In: Proc. 11th ACM SIGKDD Int’l Conf. Know. Disc. Data Mining (KDD ’05), pp. 177–187. ACM Press, New York (2005)
Blumofe, R., Leiserson, C.: Scheduling multithreaded computations by work stealing. In: Proc. 35th Ann. Symp. Found. Comp. Sci., Nov., pp. 356–368 (1994)
Kumar, V., Grama, A.Y., Vempaty, N.R.: Scalable load balancing techniques for parallel computers. J. Par. Dist. Comp. 22(1), 60–79 (1994)
Kumar, V., Rao, V.N.: Parallel depth first search. part II. analysis. Int’l J. Par. Prog. 16(6), 501–519 (1987)
UPC Consortium. UPC language specifications, v1.2. Lawrence Berkeley National Lab, Tech. Rep. LBNL-59208 (2005)
Frigo, M., Leiserson, C.E., Randall, K.H.: The implementation of the Cilk-5 multithreaded language. In: Proc. 1998 SIGPLAN Conf. Prog. Lang. Design Impl (PLDI ’98), pp. 212–223 (1998)
Marowka, A.: Analytic comparison of two advanced c language-based parallel programming models. In: Proc. Third Int’l Symp. Par. and Dist. Comp./Int’l Workshop Algorithms, Models and Tools for Par. Comp. Hetero. Nets (ISPDC/HeteroPar’04), pp. 284–291 (2004)
Marathe, J., Mueller, F.: Hardware profile-guided automatic page placement for ccnuma systems. In: Proc. 11th ACM SIGPLAN Symp. Princ. Pract. Par. Prog (PPoPP ’06), pp. 90–99. ACM Press, New York (2006)
Berlin, K., et al.: Evaluating the impact of programming language features on the performance of parallel applications on cluster architectures. In: Rauchwerger, L. (ed.) LCPC 2003. LNCS, vol. 2958, pp. 194–208. Springer, Heidelberg (2004)
European Center for Parallelism. PARAVER (2006), Available at http://www.cepba.upc.edu/paraver/
Chen, W., Iancu, C., Yelick, K.A.: Communication optimizations for fine-grained UPC applications. In: Proc. Int’l Conf. Par. Arch. Compilation Tech. (PACT 2005) pp. 267–278 (2005)
Prins, J., et al.: UPC implementation of an unbalanced tree search benchmark. Univ. North Carolina at Chapel Hill, Tech. Rep. TR03-034 (Oct. 2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Olivier, S. et al. (2007). UTS: An Unbalanced Tree Search Benchmark. In: Almási, G., Caşcaval, C., Wu, P. (eds) Languages and Compilers for Parallel Computing. LCPC 2006. Lecture Notes in Computer Science, vol 4382. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72521-3_18
Download citation
DOI: https://doi.org/10.1007/978-3-540-72521-3_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72520-6
Online ISBN: 978-3-540-72521-3
eBook Packages: Computer ScienceComputer Science (R0)