Efficient Algorithms for Routing a Net Subject to VLSI Design Rules

Abstract

In this thesis we consider detailed routing, an important step in the design of integrated circuits. On large instances detailed routing requires packing millions of node-disjoint Steiner trees into a graph with hundreds of billions of nodes, while respecting hundreds of complicated design rules. The Steiner trees are usually composed of paths. <br /> One of our main contributions is an efficient and flexible path search algorithm. <br /> We show how to make the path search efficient while retaining flexibility. Our path search is the new algorithmic core of BonnRouteDetailed, a state-of-the-art detailed router developed at the University of Bonn in joint work with IBM. We compare our path search to the previous implementation in BonnRouteDetailed: Ours supports more general cost functions, leads to vastly superior detailed routings, and is less complicated and much easier to extend. <br /> Moreover, we consider the problem of respecting design rules in the path search. Obeying even simple rules is NP-hard. This follows from one of our main theoretical results that given a two-dimensional grid graph and nodes <em>s</em>, <em>t</em> it is NP-complete to decide whether there is an <em>s</em>-<em>t</em>-path in which each maximal straight subpath has length at least two. Nevertheless, our path search is very good at respecting design rules in practice. Our framework, consisting of same-net checking, post-processing, multi-labeling, and protections, reduces the number of violations by a factor of approximately 443 in our experiments. Its most important component is the multi-labeling that allows us to respect design rules in a correct-by-construction manner. Our multi-labeling is more general and more efficient than previous ones, which allows us to respect more rules while being less restrictive. <br /> Composing Steiner trees of paths can lead to non-optimal solutions. Hence, we extend our path search to compute optimal Steiner trees respecting restrictions on the topology and on the location of Steiner points derived from the global routing. To achieve this we introduce the Restricted Dijkstra-Steiner algorithm, which generalizes the Dijkstra-Steiner algorithm. In our application the Restricted Dijkstra-Steiner algorithm achieves near-linear runtime under mild assumptions. This is possible because the restrictions actually make the problem easier. <br /> Due to the better algorithmic core that we describe in this thesis, our new BonnRoute computes excellent routing solutions fast and is being used by IBM for the design of all its processor chips. Moreover, we lay the foundation for future enhancements.