Optimal all-to-all personalized exchange in d-nary banyan multistage interconnection networks

Victor W. Liu, Chiuyuan Chen () and Richard B. Chen
Additional contact information
Victor W. Liu: National Chiao Tung University
Chiuyuan Chen: National Chiao Tung University
Richard B. Chen: National Chiao Tung University

Journal of Combinatorial Optimization, 2007, vol. 14, issue 2, No 4, 142 pages

Abstract: Abstract All-to-all personalized exchange occurs in many important applications in parallel processing. In the past two decades, algorithms for all-to-all personalized exchange were mainly proposed for hypercubes, meshes, and tori. Recently, Yang and Wang (IEEE Trans Parallel Distrib Syst 11:261–274, 2000) proposed an optimal all-to-all personalized exchange algorithm for binary (each switch is of size 2×2) banyan multistage interconnection networks. It was pointed out in Massini (Discret Appl Math 128:435–446, 2003) that the algorithm in Yang, Wang (IEEE Trans Parallel Distrib Syst 11:261–274, 2000) depends on the network topologies and requires pre-computation and memory allocation for a Latin square. Thus in (Discret Appl Math 128:435–446, 2003), Massini proposed a new optimal algorithm, which is independent of the network topologies and does not require pre-computation or memory allocation for a Latin square. Unfortunately, Massini’s algorithm has a flaw and does not realize all-to-all personalized exchange. In this paper, we will correct the flaw and generalize Massini’s algorithm to be applicable to d-nary (each switch is of size d×d) banyan multistage interconnection networks.

Keywords: Multistage interconnection network; Banyan network; All-to-all communication; All-to-all personalized exchange; Latin square (search for similar items in EconPapers)
Date: 2007
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-007-9065-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:14:y:2007:i:2:d:10.1007_s10878-007-9065-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-007-9065-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().