hierarchial global wiring for custom chip design
We present a global wiring algorithm used in a top-down physical design environment, i.e. macros are laid out only after global wiring is done, and wires are allowed to pass through macros (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. Given a balanced slicing tree representation of the floorplan, the worst-case running 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 has been used for actual chip design. Experiments showed that the hierarchical router performs better than a flat maze type router in wireability handling, equally well in wire length, and 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 sized problems).
hierarchic global custom design algorithm physical design environments macros model floorplanning slice structure scheme refine tree representation timing language experience router examples case