multi-layer 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 multi-layer macro-cell technology. The routing model uses a 3-dimensional mixed directed/undirected routing graph, which accurately models the multi-layer routing problem. However the complexity of the routing graph challenges previous route-generating algorithms. Generating the routes is to search for the Steiner minimum trees for the nets, which is an NP-hard problem. We developed an improved Steiner tree heuristic algorithm suitable for large routing graphs and able to generate high quality Steiner tree routing. Tested on industrial circuits, our algorithm yields comparable results while having dramatically lower time and space complexities than the leading heuristics. While minimizing the wire length, our global router can also minimize the number of vias or solve the routing resource congestion problems.
chip-level global routing global routing global routing efficiency graph graph-based steiner tree heuristic tree tree heuristics router global routing model model technologies direct complexity challenge algorithm search steiner minimum trees np-hard problem steiner tree heuristic algorithm heuristic algorithm large routing graphs quality industrial circuits timing space complexity space routing resource congestion problems resource congestion trees time complexity macros network routing multilayer macro-cell technology layer multilayer routing problem wire length minimisation vias minimisation