JISE


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


Journal of Information Science and Engineering, Vol. 6 No. 3, pp. 173-189


An H-V Tile-Expansion Router


Chia-Chun Tsai, Sao-Jie Chen+ and Wu-Shiung Feng+
Department of Electronic Engineering 
National Taipei Institute of Technology 
Taipei, Taiwan 10643, Republic of China 
+Department of Electrical Engineering 
National Taiwan University 
Taipei, Taiwan 10764, Republic of China


    An H-V tile-expansion router based on the H-V model of cornerstitching data structure is presented in this paper. The H-V tile-expansion consists of a sequence of alternatingH(V) and V(H) space tiles, the expansion searching of which is guided by a heuristic cost function using the A*technique and the damping concept, and the tile growing of which is governed by the constrained expansion area, the limited expansion depth, and the oriented expansion direction. The net-forest structure combines several H-V tile-expansions; it obtains near-optimal connection paths with a minimum number of bends, and guarantees that a feasible solution can be found if one exists. The router is well suited for wiring hierarchical modules by M3 technology and as part of the IDAF-a database management system for VLSI design system. In addition, we also present the results of running this router on several layout examples. Experimentally, our router is always faster than the H-tile-expansion method.


Keywords: H-V tile-expansion, net-forest structure, router

  Retrieve PDF document (JISE_199003_02.pdf)