JISE


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


Journal of Information Science and Engineering, Vol. 10 No. 1, pp. 111-127


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

  Retrieve PDF document (JISE_199401_07.pdf)