We present a multilayer pin (crossing point) assignment algorithm for macro cell circuits. The pin-assignment algorithm takes advantage of a multilayer chip-level global router that we recently developed. Previously reported methods also sought to combine global routing and pin assignment, but their models forced them to use inferior global routing methods. No previous pin-assignment program can handle multilayer layout in which multiple crossing points should be assigned to cell boundaries to fully minimize total routing length and area. In fact, we will show that multiple crossing-point layouts had 27% less total wire length and 9% less area, on average, than single-pin-assignment solutions.

We present a chip-level global router based on a new, more accurate global routing model for the multilayer macro-cell (building block) technology. The routing model uses a three-dimensional mixed directed/undirected routing graph, which provides not only the topological information but also the layer information. The irregular routing graph closely models the multilayer routing problem, so the global router can give an accurate estimate of the routing resources needed. Route-searching is formulated as the Steiner problem in networks (graph Steiner tree problem). Although the Steiner problem in networks is an NP-hard problem, it can generate better routes than other approaches. Previously published Steiner tree heuristics can not handle the complexity of the modern routing graphs. We developed an improved Steiner tree heuristic algorithm which can take advantage of the features of routing graphs. Tested on industrial circuits, our algorithm yields comparable results while having dramatically lower time and space complexities than the leading heuristics. The efficiency and effectiveness of our algorithm make our global router applicable to large industrial circuits, easily handling multilayer problems consisting of 200 macro cells and 10000 nets. While minimizing the wire length, our global router can also minimize the number of vias or solve the routing resource congestion problems.

We present a chip-level area router for modern VLSI technologies. The gridless area router can handle any number of layers, as well as rectilinear blockage areas on any layer. A two-stage divide-and-conquer strategy is applied so that the area router can handle very large chips. The first stage includes an area-minimization loop by using an efficient and accurate multi-layer global router. The global router minimizes the chip area while performing the global routing. According to the global routing results, switchboxes are generated for the whole chip area. Then the switchboxes are sent to the second stage for detailed routing, in which a tile-expansion based switchbox router is used. With multi-level rip-up and re-route techniques, the detailed router is shown to be able to complete many difficult switchboxes. The router was tested on the MCNC building block circuits. Our results show better chip areas than the best previously published results.