An Efficient Method for Custom Integrated Circuit Global Routing.

This paper presents an efficient global routing technique for a custom integrated circuit (IC) containing tens of modules, where a module may be, e.g., a RAM, ROM, PLA, or block of polycells. The router uses a "slicing tree" floorplan representation and wiring is assumed to lie in channels between the modules. The router chooses, for each net, the set of channels containing the wiring for that net (but not the detailed positions in the channels). The routings should also yield minimal IC area (for high manufacturing yield) and minimal total wirelength (for best performance). The global router will be part of a new custom IC floorplanner (under development in Department 52171) which determines the relative positions and dimensions of the modules. Given a candidate floorplan, running the router determines the area and wirelength for the candidate. Then the candidate can be revised, and the router re-run, continuing in this manner until the best floorplan is found. Four special feature of the router are (i) each terminal pin of a net can be specified to be on one of the four boundaries or at the center of a module (if a boundary location is unknown) (ii) a mapping of terminal pins to module corners to reduce the graph complexity, (iii) an on/off toggle for each module to allow over-the-module routing, (iv) the use of four "imaginary modules" bounding the IC to facilitate computations using the arcs on the boundary of the IC, and (v) options to re-route each net a specified number of times and update routing costs after any specified number of nets have been routed. We provide a comparative study of CPU time/area/wirelength for various re- routing and cost updating strategies, in particular comparing sequential "one-pass" routing vs. iterative re-routing. The graph algorithms employed to realize maximum efficiency are discussed in detail.