2026-09-20T08:11:35Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/29839 2023-07-10 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

Gropp, William D. Kale, Laxmikant V. Padua, David A. Snir, Marc Sack, Paul 2012-02-06T20:21:05Z 2012-02-06T20:21:05Z 2011-12 2012-02-06T20:21:05Z 2011-12 Governments, universities, and companies expend vast resources building the top supercomputers. The processors and interconnect networks become faster, while the number of nodes grows exponentially. Problems of scale emerge, not least of which is collective performance. This thesis identifies and proposes solutions for two major scalability problems. Our first contribution is a novel algorithm for process-partitioning and remapping for exascale systems that has far better time and space scaling than known algorithms. Our evaluations predict an improvement of up to 60x for large exascale systems and arbitrary reduction in the large temporary buffer space required for generating new communicators. Our second contribution consists of several novel collective algorithms for Clos and torus networks. Known allgather, reduce-scatter, and composite algorithms for Clos networks suffer the worst congestion when the largest messages are exchanged, damaging performance. Known algorithms for torus networks use only one network port, regardless of how many are available. Unlike known algorithms, our algorithms have a small amount of redundant communication. Unlike known algorithms, our algorithms can be reordered so that congestion hinders small messages rather than large, and all ports can be fully used on multi-port torus networks. The redundant communication gives us this flexibility. On a 32k-node system, we deliver improvements of up to 11x for the reduce-scatter operation, when the native reduce-satter algorithm does not use special hardware, and 5.5x for the allgather operation. We show large improvements over native algorithms with as few as 16 processors. Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2011-11-28T15:24:31Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 sack_paul.pdf: 973280 bytes, checksum: a342093bbaca4bf38b1a52e6b795ee63 (MD5) Made available in DSpace on 2012-02-06T20:21:05Z (GMT). No. of bitstreams: 2 sack_paul.pdf: 973280 bytes, checksum: a342093bbaca4bf38b1a52e6b795ee63 (MD5) license.txt: 4059 bytes, checksum: d8173d05241d8f1a29991460f8613d10 (MD5) http://hdl.handle.net/2142/29839 en Copyright 2011 Paul Sack Supercomputing Message-passing collective algorithms Scalable collective message-passing algorithms Dissertation / Thesis text Computer Science 1434 Computer Science 0112 University of Illinois at Urbana-Champaign Dissertation Ph.D. PHD:Computer Science -UIUC 10KS0112PHD