Affordable Access

Publisher Website

Fast path-disjoint routing in transputer networks

Authors
Journal
Microprocessing and Microprogramming
0165-6074
Publisher
Elsevier
Publication Date
Volume
33
Issue
1
Identifiers
DOI: 10.1016/0165-6074(91)90012-i
Keywords
  • Path-Disjoint Routing
  • Heuristic Algorithm
  • Routing Order
  • Route Selection
  • Criterion
Disciplines
  • Computer Science

Abstract

Abstract This paper addresses the problem of path-disjoint routing in transputer networks. We first study the criteria for path-disjoint routing, then give heuristic approaches to the criteria, and finally present a fast heuristic algorithm to solve this problem in transputer networks. For routing k edge-disjoint paths in a m × n messh, multigrid or torus, our algorithm works in O( k 2 + km 2 n 2) time on one processor. This algorithm has been implemented in Occam on the Hathi-2 transputer network. The implementation result shows a layout that all produced paths have aminimum total length and fewest total bends.

There are no comments yet on this publication. Be the first to share your thoughts.