Fast path-disjoint routing in transputer networks

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² + km²n²) 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.