標題: All-to-all personalized exchange in generalized shuffle-exchange networks
作者: Chou, Well Y.
Chen, Chiuyuan
應用數學系
Department of Applied Mathematics
關鍵字: Multistage interconnection networks;Shuffle-exchange networks;Omega network;Parallel and distributed computing;All-to-all communication;All-to-all personalized exchange
公開日期: 28-Mar-2010
摘要: 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 = 2(n), in which N is the number of processors, 2 means all the switches are of size 2 x 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. (C) 2010 Published by Elsevier B.V.
URI: http://dx.doi.org/10.1016/j.tcs.2009.10.026
http://hdl.handle.net/11536/5625
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2009.10.026
期刊: THEORETICAL COMPUTER SCIENCE
Volume: 411
Issue: 16-18
起始頁: 1669
結束頁: 1684
Appears in Collections:Articles


Files in This Item:

  1. 000276167000001.pdf