English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  Better Deterministic Routing on Meshes

Sibeyn, J. F. (1999). Better Deterministic Routing on Meshes. In Proceedings of the 13th International Parallel Processing Symposium, and 10th Symposium on Parallel and Distributed Processing (IPPS/SPDP-99) (pp. 420-425). Los Alamitos, USA: IEEE.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-35AF-4 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-35B0-F
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Sibeyn, Jop F.1, Author
Affiliations:
1Max Planck Society, ou_persistent13              

Content

show
hide
Free keywords: -
 Abstract: Optimal randomized and deterministic algorithms have been given for $k$-$k$ routing on two-dimensional $n \times n$ meshes. The deterministic algorithm is based on ``column-sort'' and exploits only part of the features of the mesh. For small $n$ and moderate $k$, the lower-order terms of this algorithm make it considerably more expensive than the randomized algorithm. In this paper, we present a novel deterministic algorithm, which, by exploiting the topology of the mesh, has lower-order terms that are almost negligible, even smaller than those of the randomized algorithm. An additional advantage of the new algorithm is that it routes average-case packet distributions twice as fast as worst-case distributions. In earlier algorithms this required additional steps for globally probing the distribution.

Details

show
hide
Language(s): eng - English
 Dates: 2010-03-021999
 Publication Status: Issued
 Pages: -
 Publishing info: Los Alamitos, USA : IEEE
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 518038
Other: Local-ID: C1256428004B93B8-A1D623860EF477C4C125688A00509C5F-F.Sibeyn-IPPS-1999
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: St Juan, Puerto Rico
Start-/End Date: 1999-04-12 - 1999-04-16

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the 13th International Parallel Processing Symposium, and 10th Symposium on Parallel and Distributed Processing (IPPS/SPDP-99)
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Los Alamitos, USA : IEEE
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 420 - 425 Identifier: ISBN: 0-7695-0143-5