HROMKOVIČ, Juraj; KANAREK, Przemyslawa; KLASING, Ralf; LORYS, Krzysztof; UNGER, Walter; WAGENER, Hubert

doi:10.1137/060669164

Metadatos

Mostrar el registro completo del ítem

Licencia de uso del documento

HROMKOVIČ, Juraj
Department of Computer Science [ETH Zürich] [D-INFK]

KANAREK, Przemyslawa

KLASING, Ralf
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]

Idioma

Article de revue

Este ítem está publicado en

SIAM Journal on Discrete Mathematics. 2009, vol. 23, n° 3, p. 1612--1645

Society for Industrial and Applied Mathematics

Resumen en inglés

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.< Leer menos

Palabras clave en inglés

Network design and communication

Communication networks

Permutation networks

Switching networks

Parallel algorithms AMS subject classifications. 68M07

68M10

90B18

94C15

URI

https://oskar-bordeaux.fr/handle/20.500.12278/198750

DOI

http://dx.doi.org/10.1137/060669164

Proyecto ANR

Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322

Orígen

Importado de Hal

Centros de investigación

Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800