Fast path-disjoint routing in transputer networks

Hong Shen

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

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(k2 + km2n2) 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.

Original languageEnglish
Pages (from-to)21-31
Number of pages11
JournalMicroprocessing and Microprogramming
Volume33
Issue number1
DOIs
Publication statusPublished - Sept 1991
Externally publishedYes

Keywords

  • Path-disjoint routing
  • criterion
  • heuristic algorithm
  • route selection
  • routing order

Fingerprint

Dive into the research topics of 'Fast path-disjoint routing in transputer networks'. Together they form a unique fingerprint.

Cite this