A fast physical constraint generator for timing driven layout
W.K. Luk
DAC 1991
We present a global wiring algorithm used in a top-down physical design environment,i.e., macros are laid out after global wiring is done, and wires are allowed to pass through macros (the wiring-through model). The floorplan of the chip is in the form of a slicing structure. The algorithm is based on a hierarchical scheme. The final result is obtained through a series of refinement as the problem is recursively decomposed into a set of small-sized problems and then solved efficiently. The worst-case run-time for an arbitrary slicing tree (totally skewed) is O(M2N). When the floorplan is represented by a balanced slicing tree, the run-time of the overall algorithm is O(MN), where M is the number of macros and N the number of nets. The algorithm has been implemented in the C language and is used for chip designs. Experiments on both real and randomly generated designs show that the hierarchical router performs equally well as a flat global router in terms of wire length and wireability handling, but much faster in run-time (at least 10 times for an example with 100 macros and 1000 nets, and the gap being even larger for bigger-size problems). Copyright © 1987 by The Institute of Electrical and Electronics Engineers, Inc.
W.K. Luk
DAC 1991
W.K. Luk, Alvar A. Dean, et al.
ICCAD 1989
W.K. Luk, Alvar A. Dean
DAC 1989
W.K. Luk, Y. Katayama, et al.
ICCD 1997