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 language | English |
---|---|
Pages (from-to) | 21-31 |
Number of pages | 11 |
Journal | Microprocessing and Microprogramming |
Volume | 33 |
Issue number | 1 |
DOIs | |
Publication status | Published - Sept 1991 |
Externally published | Yes |
Keywords
- Path-disjoint routing
- criterion
- heuristic algorithm
- route selection
- routing order