Afficher la notice abrégée

On the Size of Permutation Networks and Consequences for Efficient Simulation of Hypercube Algorithms on Bounded-Degree Networks

hal.structure.identifierDepartment of Computer Science [ETH Zürich] [D-INFK]
dc.contributor.authorHROMKOVIČ, Juraj
dc.contributor.authorKANAREK, Przemyslawa
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorKLASING, Ralf
dc.contributor.authorLORYS, Krzysztof
hal.structure.identifierLehrstuhl für Informatik I [i1]
dc.contributor.authorUNGER, Walter
dc.contributor.authorWAGENER, Hubert
dc.date.accessioned2024-04-15T09:55:23Z
dc.date.available2024-04-15T09:55:23Z
dc.date.issued2009
dc.identifier.issn0895-4801
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198750
dc.description.abstractEnThe 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.
dc.description.sponsorshipAlgorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322
dc.language.isoen
dc.publisherSociety for Industrial and Applied Mathematics
dc.subject.enNetwork design and communication
dc.subject.enCommunication networks
dc.subject.enPermutation networks
dc.subject.enSwitching networks
dc.subject.enParallel algorithms AMS subject classifications. 68M07
dc.subject.en68M10
dc.subject.en90B18
dc.subject.en94C15
dc.title.enOn the Size of Permutation Networks and Consequences for Efficient Simulation of Hypercube Algorithms on Bounded-Degree Networks
dc.typeArticle de revue
dc.identifier.doi10.1137/060669164
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
dc.subject.halInformatique [cs]/Mathématique discrète [cs.DM]
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.journalSIAM Journal on Discrete Mathematics
bordeaux.page1612--1645
bordeaux.volume23
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.issue3
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-00402764
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00402764v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=SIAM%20Journal%20on%20Discrete%20Mathematics&rft.date=2009&rft.volume=23&rft.issue=3&rft.spage=1612--1645&rft.epage=1612--1645&rft.eissn=0895-4801&rft.issn=0895-4801&rft.au=HROMKOVI%C4%8C,%20Juraj&KANAREK,%20Przemyslawa&KLASING,%20Ralf&LORYS,%20Krzysztof&UNGER,%20Walter&rft.genre=article


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée