de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-399D-1
Zusammenfassung
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 < P$, one gains between $10$ and $20\%$.