Logo image
Back
DEADLOCK-FREE ROUTING IN IRREGULAR NETWORKS USING PREFIX ROUTING
Journal article   Open access   Peer reviewed

DEADLOCK-FREE ROUTING IN IRREGULAR NETWORKS USING PREFIX ROUTING

JIE WU and L I Sheng
Parallel processing letters, v 13(4), pp 705-720
Dec 2003
DOI: https://doi.org/10.1142/S0129626403001616
url
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.5065View
SubmittedOpen Access (License Unspecified),  Open

Abstract

We propose a deadlock-free routing scheme in irregular networks using prefix routing. Prefix routing is a special type of routing with a compact routing table associated with each node (processor). Basically, each outgoing channel of a node is assigned a special label and an outgoing channel is selected if its label is a prefix of the label of the destination node. Node and channel labeling in an irregular network is done through constructing a spanning tree. The routing process follows a two-phase process of going up and then down along the spanning tree, with a possible cross channel (shortcut) between two branches of the tree between two phases. We show that the proposed routing scheme is deadlock- and livelock-free. We also compare prefix routing with the existing up*/down* routing which has been widely used in irregular networks. Possible extensions are also discussed.

Metrics

12 Record Views
1 citations in Scopus

Details

Logo image