Dynamic Local Usage in BonnRouteGlobal

Abstract

In this dissertation we consider the global routing problem which is a central task in chip design. Up to millions of sets of pins on a chip, so called nets, have to be connected through wires without intersecting each other and meeting many design rules. Global routing operates on a coarse grid graph modeling a condensed version of the chip, allowing the optimization of global objectives. The result is used as guidance by a detailed routing algorithm to compute the exact wiring. BonnRouteGlobal, the global router that is developed at the Research Institute for Discrete Mathematics, employs the resource sharing algorithm to share available routing space among the nets and to optimize signal delay through the wires. Traditionally, the impact on space of shorter wires that connect to pins is pre-estimated before long connections on the coarse global routing graph are computed. In this thesis we establish a new optimization model, called the dynamic local usage, in which all wiring can be optimized simultaneously. <br /> We discuss the impact of the dynamic local usage on BonnRouteGlobal and develop algorithms to approximately optimally embed local wires into the chip image and into the layers. The algorithms implemented consider the current prices of the resource sharing algorithm and thus fit into the resource sharing framework. We evaluate the resulting global routing quality in terms of routability during detailed routing and demonstrate the capability of the dynamic local usage to persistently improve results in the routing flow of IBM with better signal delay, shorter wire length, and less design rule violations. <br /> In the second part, we consider a variant of the rectilinear Steiner tree problem in which we are given a set of rectangles: Some may not be crossed at all, some only in horizontal direction, and some only in vertical direction. Moreover the length of any tree component on such a rectangle is bounded. This models the situation during buffering, which is also an important step in chip design. To speed up signal propagation, nets are subdivided by buffers, which must not be placed on top of obstacles, motivating bounding the length of unbuffered wiring on top of them. Special obstacle structures can make it impossible to place horizontal or vertical wires. <br /> We present a fast 2-approximation algorithm for this problem. We provide a more thorough case distinction in the proof of the main theorem than Held and Spirkl (2014) and Bihler (2015) which this part is based on, closing gaps in the previous proofs. Moreover, we slightly improve the extraction of the Steiner tree and extend the post-optimization. As a side result, we improve on the pre-processing time of the algorithm by Kahng, Mandoiu and Zelikovsky (2003) for the online maximum cost edge on tree path problem. <br /> At the end, we present an application of our Steiner tree algorithm for the computation of lower bounds on wire length and via numbers with the dynamic local usage. The results point out the potential of our algorithm to generate strong lower bounds significantly faster than the currently used approach in BonnRouteGlobal.