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" [...]


  To apply for USA Payday Loans you don't have to seek the help of relatives or go to a bank. Thanks to that, they have a great variety of drugs that can help in these cases. Female Viagra is not an exception.