de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

#### Better Deterministic Routing on Meshes

##### MPG-Autoren

Sibeyn,  Jop F.
Max Planck Society;

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

Sibeyn, J. F. (1999). Better Deterministic Routing on Meshes. In Proceedings of the 13th International Parallel Processing Symposium, and 10th Symposium on Parallel and Distributed Processing (IPPS/SPDP-99) (pp. 420-425). Los Alamitos, USA: IEEE.

Optimal randomized and deterministic algorithms have been given for $k$-$k$ routing on two-dimensional $n \times n$ meshes. The deterministic algorithm is based on column-sort'' and exploits only part of the features of the mesh. For small $n$ and moderate $k$, the lower-order terms of this algorithm make it considerably more expensive than the randomized algorithm. In this paper, we present a novel deterministic algorithm, which, by exploiting the topology of the mesh, has lower-order terms that are almost negligible, even smaller than those of the randomized algorithm. An additional advantage of the new algorithm is that it routes average-case packet distributions twice as fast as worst-case distributions. In earlier algorithms this required additional steps for globally probing the distribution.