Inhalt des Dokuments
Congestion-aware Steiner Trees with Small Elmore Delay
Klaus Heeger (Uni Bonn)
Modern computer chips consist of billions of transistors. This huge size makes it impossible to design computer chips by hand, so they have to be designed (mainly) by algorithms.
Due to its enormous complexity, any chip design flow is split into several steps. Most of these steps can be formulated as mathematical optimization problems, and most of them are NP-hard.
We will focus on a design step called global routing. All circuits (which are small building blocks of transistors) have already been assigned a position on the chip area, and it is known which circuits have to be connected by wires before the global routing.
Global routing now determines the rough position of these wires, minimizing some global objectives such as congestion, timing, manufacturing yield or power consumption, but ignoring design rules such as a minimum distance between wires.
We will only consider the congestion and timing objective. More specifically, we consider the Congestion- and Delay-aware Net Routing Problem. This problem asks, given a source and a set of sinks, to connect all sinks to the source minimizing the weighted sum of delay at the sinks and congestion costs. The delay of a wire is modelled by the Elmore delay model. This makes the problem harder than the classical Steiner tree problem, as the cost of an edge does not only depend on the edge itself, but also on the rest of the solution. In contrast to the Steiner tree problem, it remains NP-hard even with only one sink, and cannot be approximated by a constant factor (unless P=NP).
We will therefore present an exponential-time exact algorithm for this problem. This algorithm is a generalization of a well-known algorithm for the Steiner tree problem, namely the Dijkstra-Steiner algorithm. Furthermore, we will describe a faster heuristic dervied from this exact algorithm. We implemented the both the exact algorithm and the heuristic as part of BonnRoute, the routing tool of the BonnTools, which is the chip design software developed at the Research Institute for Discrete Mathematics at the University of Bonn, and also present the experimental results.
Back to the research colloquium site.