Routing with Finite Speeds of Memory and Network

Sibeyn, Jop F.

DetailsSummary

Routing with Finite Speeds of Memory and Network

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.

Item is Released

show all hide all

Basic

show hide

Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-399D-1 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-399F-E

Genre: Conference Paper

Files

show Files

Locators

show

Creators

show

hide

Creators:
Sibeyn, Jop F.¹, Author

Affiliations:
1Max Planck Society, ou_persistent13

Content

show

hide

Free keywords: -

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\%$.

Details

show

hide

Language(s): eng - English

Dates: Modified: 2010-03-02Date issued: 1997

Publication Status: Issued

Pages: -

Publishing info: -

Table of Contents: -

Rev. Type: -

Identifiers: eDoc: 517900
Other: Local-ID: C1256428004B93B8-1CB282E68672ED7FC12565CB004F7122-Sibeyn97c

Degree: -

Event

show

hide

Title: Untitled Event

Place of Event: Bratislava, Slovakia

Start-/End Date: 1997-08-22 - 1997-08-29

Legal Case

show

Project information

show

Source 1

show

hide

Title: Proceedings of the 22nd Symposium on the Mathematical Foundations of Computer Science (MFCS-97)

Source Genre: Proceedings

Creator(s):
Prívara, Igor, Editor
Ruzicka, Peter, Editor

Affiliations:
-

Publ. Info: Berlin : Springer

Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 488 - 497 Identifier: -

Source 2

show

hide

Title: Lecture Notes in Computer Science

Source Genre: Series

Creator(s):

Affiliations:

Publ. Info: -

Pages: - Volume / Issue: 1295 Sequence Number: - Start / End Page: - Identifier: -