Optimal multiphase complete exchange on circuit-switched hypercube architectures

David M. Nicol, Shahid H. Bokhari

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 Exchange 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.

Original languageEnglish (US)
Title of host publicationPerformance Evaluation Review
PublisherPubl by ACM
Number of pages9
ISBN (Print)089791659X, 9780897916592
StatePublished - 1994
Externally publishedYes
EventProceedings of the 1994 ACM Sigmetrics on Measurement and Modeling of Computer Systems - Nashville, TN, USA
Duration: May 16 1994May 20 1994

Publication series

NamePerformance Evaluation Review
ISSN (Print)0163-5999


OtherProceedings of the 1994 ACM Sigmetrics on Measurement and Modeling of Computer Systems
CityNashville, TN, USA

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Optimal multiphase complete exchange on circuit-switched hypercube architectures'. Together they form a unique fingerprint.

Cite this