|標題:||Optimal all-to-all personalized exchange in d-nary banyan multistage interconnection networks|
|作者:||Liu, Victor W.|
Chen, Richard B.
Department of Applied Mathematics
|關鍵字:||multistage interconnection network;banyan network;all-to-all communication;all-to-all personalized exchange;latin square|
|摘要:||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 2x2) 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 dxd) banyan multistage interconnection networks.|
|期刊:||JOURNAL OF COMBINATORIAL OPTIMIZATION|
|Appears in Collections:||Conferences Paper|
Files in This Item:
If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.