David M. Nicol
Shahid H. Bokhari
ABSTRACT
The complete-exchange communication primitive on a distributed memory multiprocessor calls for every processor to send a message to every other processor, each such message being unique. For circuit-switched hypercube networks there are two well-known schemes for implementing this primitive. Direct exchange minimizes communication volume but maximizes startup costs, while Standard Exchange minimizes startup costs at the price of higher communication volume. This paper analyzes a hybrid, which can be thought of as a sequence of Direct Echange phases, applied to variable-sized subcubes. This paper examines the problem of determining the optimal subcube dimension sizes di for every phase. We show that optimal performance is achieved using some equi-partition, where |di-dj|≤1 for all phases i and j. We study the behavior of the optimal partition as a function of machine communication parameters, hypercube dimension, and message size, and show that the optimal partition can be determined with no more than 2(d+1) comparisons. Finally we validate the model empirically, and for certain problem instances observe as much as a factor of two improvement over the other methods.
- 1.S. H. Bokhari. Multiphase complete exchange on a circuit switched hypercube. In Proceedings of the 1991 Int'l Conference on Parallel Processing, pages 525-529, August 1991.Google Scholar
- 2.S. H. Bokhari. Multiphase complete exchange: A theoreticM analysis. ICASE Technical Report 93- 64, August 1993.Google Scholar
- 3.L. Bomans and D. Roose. Benchmarking the iPSC/2 hypercube multiprocessor. Concurrency: Practzce and Experience, 1(1):3-18, September 1989.Google ScholarCross Ref
- 4.J. Douglas and J. E. Gunn. A general formulation of alternating direction methods. Nurner. Math., 6(5), 1964.Google Scholar
- 5.S. Lennart Johnsson and Ching-Tien Ho. Matrix transposition on boolean n-cube configured ensemble architectures. SIAM J. Matr, x Anal. Appl., 9(3):419-454, July 1988. Google ScholarDigital Library
- 6.Richard B. Pelz. The parallel Fourier pseudospectral method. J. Comp. Phys, 92(2):296-312, February 1991. Google ScholarDigital Library
- 7.Thomas Schmiermund and Steve R. Seidel. A communication model for the intel iPSC/2. Technical Report CS-TR 9002, Dept. of Computer Science, Michigan Tech. Univ., April 1990.Google Scholar
- 8.Steve Seidel, Ming-Horng Lee, and Shivi Fotedar. Concurrent bidirectional communication on the Intel iPSC/860 and iPSC/2. Technical Report CS-TR 9006, Dept. of Computer Science, Michigan Tech. Univ., November 1990.Google Scholar
- 9.Steve R. Seidel. Circuit switched vs. storeand-forward solutions to symmetric communication problems. In Proc. ~th. Conf. Hypercube Concurrent Computers and Apphcations, pages 253-255, 1989.Google Scholar
Index Terms
- Optimal multiphase complete exchange on circuit-switched hypercube architectures
Recommendations
Optimal multiphase complete exchange on circuit-switched hypercube architectures
The complete-exchange communication primitive on a distributed memory multiprocessor calls for every processor to send a message to every other processor, each such message being unique. For circuit-switched hypercube networks there are two well-known ...
Multiphase Complete Exchange: A Theoretical Analysis
Abstract-Complete Exchange requires each of N processors to send a unique message to each of the remaining N 1 processors. For a circuit switched hypercube with N = 2d processors, the Direct and Standard algorithms for Complete Exchange are time optimal ...
Toward Optimal Complete Exchange on Wormhole-Routed Tori
In this paper, we propose new routing schemes to perform all-to-all personalized communication (or known as complete exchange) in wormhole-routed, one-port tori. On tori of equal size along each dimension, our algorithms use both asymptotically optimal ...
Comments