An H-V Alternating Router

An H-V alternating router based on the concurrent H (horizontal) and V (vertical) tile expansions is presented. The router is modeled by a sequence of alternating H and V corner-stitching space tiles, where the expansion direction is controlled by a heuristic evaluation function using the A* technique and the damping concept. In addition, tile growing is governed by the following three factors: Constrained expansion area, limited expansion depth, and oriented expansion direction. All the H-V tile-expansion operations can be easily performed on a specially designed net-forest structure. It is shown that this approach generates nearly optimal connection paths with a minimum number of bends and always guarantees a feasible solution if such a path exists. The performance of this router is better than that of H only tile-expansion routers. Furthermore, this router is well suited for wiring hierarchical modules with the M³ technology and can be extended to multilayer layouts. Currently, it has been successfully integrated into the IDAF system—a database management environment for VLSI design.