Scalable Algorithms for Constructing Balanced Spanning Trees on System-ranked Process Groups

Current implementations of process groups (subcommunicators) have non-scalable (O(group size)) memory footprints and even worse time complexities for setting up communication. We propose system-ranked process groups, where member ranks are picked by the runtime system, as a cheaper and faster alternative for a subset of collective operations (barrier, broadcast, reduction, allreduce). This paper presents two distributed algorithms for spanning tree construction over system-ranked process groups obtained by splitting a parent group. Our schemes have much smaller memory footprints and also perform better, even at modest process counts. We demonstrate performance results up to 131, 072 cores of BlueGene/P.

@incollection{fixme,
   author = {Langer, Akhil and Venkataraman, Ramprasad and Kale, Laxmikant},
   affiliation = {Department of Computer Science, University of Illinois at Urbana-Champaign, USA},
   title = {Scalable Algorithms for Constructing Balanced Spanning Trees on System-Ranked Process Groups},
   booktitle = {Recent Advances in the Message Passing Interface},
   series = {Lecture Notes in Computer Science},
   editor = {Träff, Jesper and Benkner, Siegfried and Dongarra, Jack},
   publisher = {Springer Berlin / Heidelberg},
   isbn = {978-3-642-33517-4},
   keyword = {Computer Science},
   pages = {224-234},
   volume = {7490},
   year = {2012}
}