Tuesday, 14:15 - 14:40 h, Room: H 3012


Tim Nieberg
BonnCell: Routing of leaf cells in VLSI design

Coauthors: Stefan Hougardy, Jan Schneider


In this talk, we present and discuss the routing engine of BonnCell. Given a placed leaf cell, the task at hand is to find an
embedding of rectilinear Steiner trees which realizes a given netlist subject to various design rules.
As a leaf cell is rather small compared to other structures usually present in VLSI design, all constraints have to be considered
at the same time and as accurately as possible making leaf cell routing a very complicated problem in practice.
The underlying algorithm of our solution uses a constraint generation approach based on a MIP model for packing Steiner trees in
graphs and is extended to produce a problem specific formulation. While relaxing (some of) the constraints is not an option
for the application, there are several ways to improve on the solution times. These include further strong valid inequalities
and also some heuristic elements. Next to these, we also report on results for current real-world designs at the 22,nm chip production node.


Talk 3 of the invited session Tue.2.H 3012
"Algorithms for transistor-level layout" [...]
Cluster 2
"Combinatorial optimization" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra influence on blood clots.