All-to-all personalized exchange in generalized shuffle-exchange networks

Well Y. Chou, Chiuyuan Chen*

*Corresponding author for this work

Research output: Contribution to journalArticle

14 Scopus citations

Abstract

An all-to-all communication algorithm is said to be optimal if it has the smallest communication delay. Previous all-to-all personalized exchange algorithms are mainly for hypercube, mesh, and torus. In Yang and Wang (2000) [13], Yang and Wang proved that a multistage interconnection network (MIN) is a better choice for implementing all-to-all personalized exchange and they proposed optimal all-to-all personalized exchange algorithms for MINs. In Massini (2003) [9], Massini proposed a new optimal algorithm for MINs, which is independent of the network topology. Do notice that the algorithms in [9] and [13] work only for MINs with the unique path property (meaning that there is a unique path between each pair of source and destination) and satisfying N = 2n, in which N is the number of processors, 2 means all the switches are of size 2×2, and n is the number of stages. In Padmanabhan (1991) [10], Padmanabhan proposed the generalized shuffle-exchange network (GSEN), which is a generalization of the shuffle-exchange network. Since a GSEN does not have the unique path property, the algorithms in [9] and [13] cannot be used. The purpose of this paper is to consider the all-to-all personalized exchange problem in GSENs. An optimal algorithm and several bounds will be proposed.

Original languageEnglish
Pages (from-to)1669-1684
Number of pages16
JournalTheoretical Computer Science
Volume411
Issue number16-18
DOIs
StatePublished - 28 Mar 2010

Keywords

  • All-to-all communication
  • All-to-all personalized exchange
  • Multistage interconnection networks
  • Omega network
  • Parallel and distributed computing
  • Shuffle-exchange networks

Fingerprint Dive into the research topics of 'All-to-all personalized exchange in generalized shuffle-exchange networks'. Together they form a unique fingerprint.

  • Cite this