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
Received August 1, 1989; revised March 13, 1990.
Communicated by Lin-Shan Lee.
*This work is supported by the National Science Council, Taipei, Taiwan, Republic of China under Grant NSC 78-0404-E002-46, and Grant NSC 79-0404-E002-33.