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

Title:
Optimal all-to-all personalized exchange in d-nary banyan multistage interconnection networks
Authors:
LIU, Victor W, CHIUYUAN CHEN, CHEN, Richard B
Source:
Selected papers from the CTS Conference on Combinatorics and its Applications in Honor of Franck K. Hwang's 65th birthdayJournal of combinatorial optimization. 14(2-3):131-142
Publisher Information:
Norwell, MA: Springer, 2007.
Publication Year:
2007
Physical Description:
print, 1/2 p
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Recherche operationnelle. Gestion, Operational research. Management science, Recherche opérationnelle et modèles formalisés de gestion, Operational research and scientific management, Flots dans les réseaux. Problèmes combinatoires, Flows in networks. Combinatorial problems, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Logiciel, Software, Systèmes informatiques et systèmes répartis. Interface utilisateur, Computer systems and distributed systems. User interface, Algorithme optimal, Optimal algorithm, Algoritmo óptimo, Carré latin, Latin square, Cuadrado latino, Echange total, Gossiping(all to all), Todos a todos, Gestion mémoire, Storage management, Gestión memoria, Hypercube, Hipercubo, Multiétage, Multistage, Poliescalonado, Optimisation combinatoire, Combinatorial optimization, Optimización combinatoria, Parallélisme, Parallelism, Paralelismo, Réseau banian, Banyan network, Red Banyan, Réseau interconnexion, Interconnection network, Red interconexión, Réseau télécommunication, Telecommunication network, Red telecomunicación, Système réparti, Distributed system, Sistema repartido, Topologie circuit, Network topology, Traitement parallèle, Parallel processing, Tratamiento paralelo, Multistage interconnection network Banyan network All-to-all communication All-to-all personalized exchange * Latin square
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Department of Applied Mathematics, National Chiao Tung University, Hsinchu 300, Tawain, Province of China
ISSN:
1382-6905
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=19068012
Rights:
Copyright 2008 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Operational research. Management
Accession Number:
edscal.19068012
Database:
PASCAL Archive

Further Information

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 x 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 x d) banyan multistage interconnection networks.