Optimal all-to-all personalized exchange in d-nary banyan multistage interconnection networks |
| |
Authors: | Victor W Liu Chiuyuan Chen Richard B Chen |
| |
Institution: | (1) Department of Applied Mathematics, National Chiao Tung University, Hsinchu, 300, Taiwan |
| |
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.
Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday.
This research was partially supported by the National Science Council of the Republic of China under the grant NSC94-2115-M-009-006. |
| |
Keywords: | Multistage interconnection network Banyan network All-to-all communication All-to-all personalized exchange Latin square |
本文献已被 SpringerLink 等数据库收录! |
|