On the Size of Permutation Networks and Consequences for Efficient Simulation of Hypercube Algorithms on Bounded-Degree Networks
KLASING, Ralf
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
See more >
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
KLASING, Ralf
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
< Reduce
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Language
en
Article de revue
This item was published in
SIAM Journal on Discrete Mathematics. 2009, vol. 23, n° 3, p. 1612--1645
Society for Industrial and Applied Mathematics
English Abstract
The sizes of permutation networks and planar permutation networks for special sets of permutations are investigated. Several asymptotically optimal estimations for distinct subsets of the set of all permutations are ...Read more >
The sizes of permutation networks and planar permutation networks for special sets of permutations are investigated. Several asymptotically optimal estimations for distinct subsets of the set of all permutations are established here. The two main results are: (i) an asymptotically optimal switching network of size O(N log log N) for shifts of power 2. (ii) an asymptotically optimal planar permutation network of size Θ(N 2 • (log log N/ log N) 2) for shifts of power 2. A consequence of our results is the construction of a 4-degree network which can simulate each communication step of any hypercube algorithm using edges from at most a constant number of different dimensions in one communication step in O(log log N) communication steps. An essential improvement of gossiping in vertex-disjoint path mode in bounded-degree networks follows.Read less <
English Keywords
Network design and communication
Communication networks
Permutation networks
Switching networks
Parallel algorithms AMS subject classifications. 68M07
68M10
90B18
94C15
ANR Project
Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322
Origin
Hal imported