# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

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

##### MPS-Authors

##### External Resource

No external resources are shared

##### 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. F. (1997). Routing with Finite Speeds of Memory and Network. In I. Prívara,
& P. Ruzicka (*Proceedings of the 22nd Symposium
on the Mathematical Foundations of Computer Science (MFCS-97)* (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\%$.