Multilayer chip-level global routing using an efficient graph-based Steiner tree heuristic

We present a chip-level global router based on a new, more accurate global routing model for the multilayer macro-cell (building block) technology. Th e routing model uses a three-dimensional mixed directed/undirected routing graph, which provides not only the topological information but also the lay er information; The irregular routing graph closely models the multilayer r outing problem, so the global router can give an accurate estimate of the r outing resources needed. Route-searching is formulated as the Steiner probl em in networks (graph Steiner tree problem). Although the Steiner problem i n 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. me developed an improved Steiner tree heuristic algorithm which can take advantage of the features of routin g graphs. Tested on industrial circuits, our algorithm yields comparable re sults while having dramatically lower time and space complexities than the leading heuristics [2], [18]. The efficiency and effectiveness of our algor ithm make our global router applicable to large industrial circuits, easily handling multilayer problems consisting of 200 macro cells and 10 000 nets . While minimizing the mire length, our global router can also minimize the number of vias or solve the routing resource congestion problems.