๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

All-to-all personalized communication on multistage interconnection networks

โœ Scribed by Annalisa Massini

Book ID
104294107
Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
152 KB
Volume
128
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

โœฆ Synopsis

In parallel/distributed computing systems, the all-to-all personalized communication (or complete exchange) is required in numerous applications of parallel processing. In this paper, we consider this problem for log N stage Multistage Interconnection Networks (MINs). It is proved that the set of admissible permutations for a MIN can be partitioned in Latin Squares. Since routing permutations belonging to a Latin Square provides the all-to-all personalized communication, a method to realize the complete exchange with time complexity O(N ), that is optimal, can be derived. This method, compared with other ones in literature, does not necessitate of neither pre-computation nor memory allocation to record the Latin Square, because an explicit construction of it is not required; furthermore it is applicable to any log N stage multistage networks since it is independent of the topology.

๐Ÿ“œ SIMILAR VOLUMES

Optimal matrix transposition and bit rev
Optimal matrix transposition and bit reversal on hypercubes: All-to-all personalized communication
โœ Alan Edelman ๐Ÿ“‚ Article ๐Ÿ“… 1991 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 390 KB

In a hypercuhe multiprocessor with distributed memory, messages have a street address and an apartment number, i.e., a hypercuhe node address and a local memory address. Here we describe an optimal algorithm for performing the communication described by exchanging the bits of the node address with t

Optimal Algorithms for All-to-All Person
Optimal Algorithms for All-to-All Personalized Communication on Rings and Two Dimensional Tori
โœ Chi Chung Lam; C.-H. Huang; P. Sadayappan ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 254 KB

All-to-all personalized communication is a basic communication operation in a parallel computing environment. In this operation, each processor sends a distinct message to every other processor. It is used in several parallel algorithms, such as for the fast Fourier transform. This paper presents ne

All-to-all communication for some wavele
All-to-all communication for some wavelength-routed all-optical networks
โœ Beauquier, Bruno ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 166 KB

This paper studies the problem of all-to-all communication for optical networks. In such networks, the vast bandwidth available is utilized through wavelength division multiplexing (WDM): A single physical optical link can carry several logical signals provided that they are transmitted on different