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

Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

#### Routing with Finite Speeds of Memory and Network

##### 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. (1997). Routing with Finite Speeds of Memory and Network. In I. Prívara, & P. Ruzicka (Eds.), Proceedings of the 22nd Symposium on the Mathematical Foundations of Computer Science (MFCS-97) (pp. 488-497). Berlin: Springer.

On practical parallel computers, the time for routing a distribution of sufficiently large packets can be approximated by $\max\{T_f, T_b\}$. Here $T_f$ is proportional to the maximum number of bytes a PU sends and receives, and $T_b$ is proportional to the maximum number of bytes a connection in the network has to transfer. We show that several important routing patterns can be performed by a sequence of balanced all-to-all routings and analyze how to optimally perform these under the above cost-model. We concentrate on dimension-order routing on meshes, and assume that the routing pattern must be decomposed into a sequence of permutations. The developed strategy has been implemented on the Intel Paragon. In comparison with the trivial strategy, in which $\mi{PU}_i$ routes to $\mi{PU}_{(i + t) \bmod P}$ in permutation~$t$, $1 \leq t &lt; P$, one gains between $10$ and $20\%$.