Governments, universities, and companies expend vast resourcesbuilding the top supercomputers. The processors and interconnectnetworks become faster, while the number of nodes grows exponentially. Problems of scale emerge, not least of which iscollective performance. This thesis identifies and proposes solutions for two major scalability problems.Our first contribution is a novel algorithm for process-partitioningand remapping for exascale systems that has far better time and spacescaling than known algorithms. Our evaluations predict an improvementof up to 60x for large exascale systems and arbitrary reduction in the large temporary buffer space required for generating newcommunicators. Our second contribution consists of several novel collectivealgorithms 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, damagingperformance. Known algorithms for torus networks use only one networkport, regardless of how many are available. Unlike known algorithms,our algorithms have a small amount of redundant communication. Unlikeknown algorithms, our algorithms can be reordered so that congestionhinders small messages rather than large, and all ports can be fullyused on multi-port torus networks. The redundant communication givesus this flexibility. On a 32k-node system, we deliver improvements ofup to 11x for the reduce-scatter operation, when the nativereduce-satter algorithm does not use special hardware, and 5.5x forthe allgather operation. We show large improvements over nativealgorithms with as few as 16 processors.
PDF
download
878987797
028-85220240
