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

研究成果: Article同行評審

2 引文 斯高帕斯(Scopus)


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

頁(從 - 到)93-100
期刊Microprocessing and Microprogramming
出版狀態Published - 8月 1990


深入研究「Occam implementation of path-disjoint routing on the Hathi-2 transputer system」主題。共同形成了獨特的指紋。