Optimized pipelined parallel merge sort on the cell BE
2009 (English)In: Euro-Par 2008 Workshops - Parallel Processing: VHPC 2008, UNICORE 2008, HPPC 2008, SGS 2008, PROPER 2008, ROIA 2008, and DPA 2008, Las Palmas de Gran Canaria, Spain, August 25-26, 2008, Revised Selected Papers / [ed] Eduardo César, Michael Alexander, Achim Streit, Jesper Larsson Träff, Christophe Cérin, Andreas Knüpfer, Dieter Kranzlmüller and Shantenu Jha, Springer Berlin/Heidelberg, 2009, Vol. 5415 LNCS, 131-140 p.Chapter in book (Refereed)
Chip multiprocessors designed for streaming applications such as Cell BE offer impressive peak performance but suffer from limited bandwidth to off-chip main memory. As the number of cores is expected to rise further, this bottleneck will become more critical in the coming years. Hence, memory-efficient algorithms are required. As a case study, we investigate parallel sorting on Cell BE as a problem of great importance and as a challenge where the ratio between computation and memory transfer is very low. Our previous work led to a parallel mergesort that reduces memory bandwidth requirements by pipelining between SPEs, but the allocation of SPEs was rather ad-hoc. In our present work, we investigate mappings of merger nodes to SPEs. The mappings are designed to provide optimal trade-offs between load balancing, buffer memory consumption, and communication load on the on-chip bus. We solve this multi-objective optimization problem by deriving an integer linear programming formulation and compute Pareto-optimal solutions for the mapping of merge trees with up to 127 merger nodes. For mapping larger trees, we give a fast divide-and-conquer based approximation algorithm. We evaluate the sorting algorithm resulting from our mappings by a discrete event simulation.
Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2009. Vol. 5415 LNCS, 131-140 p.
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online) ; 5415
Engineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-21257DOI: 10.1007/978-3-642-00955-6_18ISBN: 3-642-00954-9ISBN: 978-3-642-00954-9ISBN: e-978-3-642-00955-6OAI: oai:DiVA.org:liu-21257DiVA: diva2:241036
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics),2009-09-302009-09-302014-10-08Bibliographically approved