Invited Session Tue.2.H 3012

Tuesday, 13:15 - 14:45 h, Room: H 3012

Cluster 2: Combinatorial optimization [...]

Algorithms for transistor-level layout


Chair: Stefan Hougardy



Tuesday, 13:15 - 13:40 h, Room: H 3012, Talk 1

Stefan Hougardy
Transistor level layout: Algorithms and complexity


In hierarchical VLSI design a leaf cell is a functional unit at the lowest level of the hierarchy. A leaf cell implements a specific function. It is built from a small number of transistors that are connected by wires.
The problem of automatically generating transistor level layouts of leaf cells has been studied for several decades. It requires the solution of hard problems as for example Steiner tree packing problems or linear arrangement problems. We give an overview of some of the algorithmic problems appearing in the transistor level layout of leaf cells and discuss why current VLSI technology requires new algorithms.



Tuesday, 13:45 - 14:10 h, Room: H 3012, Talk 2

Jan Schneider
BonnCell: Placement of leaf cells in VLSI design

Coauthors: Stefan Hougardy, Tim Nieberg


The automatic layout of leaf cells in VLSI design requires significantly different algorithms than classical tools for the physical design of VLSI instances. While the number of placement objects in leaf cells is very small, at most a few dozen, the placement constraints are not covered by usual approaches. We present the placement engine of our tool BonnCell, which computes optimal placements for most real-world instances within seconds. Optimality is measured with respect to a target function that models the cell routability and proved to be very accurate in practice.



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

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.


  Do you need Missouri Loans Online as soon as possible? Therefore, we can say that the active substances in its composition are more perfectly mixed. Vardenafil is not only present in the original Order Levitra, but also as part of its analogs.