Occam implementation of path-disjoint routing on the Hathi-2 transputer system

This paper describes how to develop an Occam program to heuristically solve the path-disjoint routing problem in transputer networks. In this paper, we first introduce the heuristic criteria for path-disjoint routing and a fast routing algorithm based on the criteria, then describe the design of the Occam program for path-disjoint routing based on the algorithm, and finally show some implementation results of the Occam program on the Hathi-2 transputer system. With the main feature of no batched data-swapping during program execution, our program can be efficiently implemented. For the problem of finding k edge-disjoint paths in a m × n mesh, multigrid or torus, the program runs in time O(k² + km²n²) on one transputer. All paths in a successful solution produced by the program have a minimum total length and fewest total bends, which provides an optimally embedded layout.