On the Size of Permutation Networks and Consequences for Efficient Simulation of Hypercube Algorithms on Bounded-Degree Networks
| hal.structure.identifier | Department of Computer Science [ETH Zürich] [D-INFK] | |
| dc.contributor.author | HROMKOVIČ, Juraj | |
| dc.contributor.author | KANAREK, Przemyslawa | |
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| dc.contributor.author | KLASING, Ralf | |
| dc.contributor.author | LORYS, Krzysztof | |
| hal.structure.identifier | Lehrstuhl für Informatik I [i1] | |
| dc.contributor.author | UNGER, Walter | |
| dc.contributor.author | WAGENER, Hubert | |
| dc.date.accessioned | 2024-04-15T09:55:23Z | |
| dc.date.available | 2024-04-15T09:55:23Z | |
| dc.date.issued | 2009 | |
| dc.identifier.issn | 0895-4801 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/198750 | |
| dc.description.abstractEn | 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. | |
| dc.description.sponsorship | Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322 | |
| dc.language.iso | en | |
| dc.publisher | Society for Industrial and Applied Mathematics | |
| dc.subject.en | Network design and communication | |
| dc.subject.en | Communication networks | |
| dc.subject.en | Permutation networks | |
| dc.subject.en | Switching networks | |
| dc.subject.en | Parallel algorithms AMS subject classifications. 68M07 | |
| dc.subject.en | 68M10 | |
| dc.subject.en | 90B18 | |
| dc.subject.en | 94C15 | |
| dc.title.en | On the Size of Permutation Networks and Consequences for Efficient Simulation of Hypercube Algorithms on Bounded-Degree Networks | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1137/060669164 | |
| dc.subject.hal | Informatique [cs]/Algorithme et structure de données [cs.DS] | |
| dc.subject.hal | Informatique [cs]/Mathématique discrète [cs.DM] | |
| dc.subject.hal | Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC] | |
| bordeaux.journal | SIAM Journal on Discrete Mathematics | |
| bordeaux.page | 1612--1645 | |
| bordeaux.volume | 23 | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.issue | 3 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00402764 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00402764v1 | |
| bordeaux.COinS | ctx_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 |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||