Load balancing of irregular parallel divide-and-conquer algorithms in group-SPMD programming environments
2006 (English)In: 8th Workshop on Parallel Systems and Algorithms PASA 2006 / [ed] Wolfgang Karl, Jürgen Becker, Karl-Erwin Großpietsch, Christian Hochberger and Erik Maehle, Frankfurt/Main, Germany, 2006, 313-322 p.Conference paper (Refereed)
We study strategies for local load balancing of irregular parallel divide-andconquer algorithms such as Quicksort and Quickhull in SPMD-parallel environments such as MPI and Fork that allow to exploit nested parallelism by dynamic group splitting. We propose two new local strategies, repivoting and serialisation, and develop a hybrid local load balancing strategy, which is calibrated by parameters that are derived off-line from a dynamic programming optimisation. While the approach is generic, we have implemented and evaluated our method for two very different parallel platforms. We found that our local strategy is superior to global dynamic load balancing on a Linux cluster, while the latter performs better on a tightly synchronised sharedmemory platform with nonblocking, cheap task queue access.
Place, publisher, year, edition, pages
Frankfurt/Main, Germany, 2006. 313-322 p.
, GI Lecture Notes in Informatics (LNI), vol. P-81
National CategoryComputer Science
IdentifiersURN: urn:nbn:se:liu:diva-35761Local ID: 28492ISBN: 3-88579-175-7OAI: oai:DiVA.org:liu-35761DiVA: diva2:256609
8th Workshop on Parallel Systems and Algorithms (PASA 2006), March 16, 2006, Frankfurt/Main, Germany - in connection with the 19th International Conference on Architecture of Computing Systems (ARCS 2006), March 13-16, 2006, Frankfurt/Main, Germany