English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Routing with Finite Speeds of Memory and Network

MPS-Authors
/persons/resource/persons45478

Sibeyn,  Jop
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

https://rdcu.be/dwpTz
(Publisher version)

Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Sibeyn, J. (1997). Routing with Finite Speeds of Memory and Network. In I. Prívara, & P. Ruzicka (Eds.), Mathematical Foundations of Computer Science 1997 (pp. 488-497). Berlin: Springer.


Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-399D-1
Abstract
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\%$.