Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.10 No.1, pp.111-127 (March 1994)
A Linear Time Algorithm for Planar Moat Routing*

Chia-Chun Tsai and Sao-Jie Chen#
Department of Electronic Engineering
National Taipei Institute of Technology
Taipei, Taiwan, R.O.C.
#Department of Electronic Engineering
National Taipei University
Taipei, Taiwan, R.O.C.

In this paper, the problem of planar moat routing, a special case of moat routing, is investigated. Given a central module with a number of boundary terminals and the same number of i/o pads around the chip, the problem is to complete the interconnectoions between the terminals and i/o pads. Based on the sloped interconnection technique, a linear time routing algorithm is presented. The algorithm always finds a minimum area layout with the shortest wire length and has a running time of O(N), where N is the total number of boundaty terminals. Some examples have been expermetally tested to show the effectiveness of out approach.

Keywords: sloped interconnection, planar moat routing (PMR), river router

Received October 30, 1992; revised October 14, 1993.
Communicated by Jhing-Fa Wang.
*This work was supported by the National Science Council, Taipei, Taiwan under Grants NSC 82-0404-E027-020 and NSC 82-0404-E002-166.