Invited Session Mon.1.H 3004

Monday, 10:30 - 12:00 h, Room: H 3004

Cluster 2: Combinatorial optimization [...]

Combinatorial optimization in chip design I


Chair: Stephan Held



Monday, 10:30 - 10:55 h, Room: H 3004, Talk 1

Igor L. Markov
A primal-dual Lagrange optimization for VLSI global placement

Coauthor: Myung-Chul Kim


We propose a projected subgradient primal-dual Lagrange
optimization for global placement, that can be instantiated
with a variety of interconnect models. It decomposes the
original non-convex problem into "more convex'' sub-problems. It
generalizes the recent SimPL, SimPLR and Ripple algorithms and extends them. Empirical results on the ISPD 2005 and 2006 benchmark suites confirm the superiority of this technique compared to prior art.



Monday, 11:00 - 11:25 h, Room: H 3004, Talk 2

Markus Struzyna
Quadratic and constrained placement in chip design: Global flows and local realizations


The classical large scale placement problem is a key step in chip design. Given a finite set of modules connected by nets, the task is to find overlap-free positions to the modules in such a way that the overall net length is minimized.
This talk presents a quadratic, partitioning-based placement algorithm which is able to handle non-convex and overlapping position constraints to subsets of modules, the movebounds.
The key routine of our algorithm is the flow-based partitioning which combines a global MinCostFlow model for computing directions with extremely fast and highly parallelizable local realization steps. Despite its global view, the size of the MinCostFlow instance is only linear in the number of partitioning regions and does not depend on the number of cells. We prove that our partitioning scheme finds a (fractional) solution for any given placement or decides in polynomial time that none exists.



Monday, 11:30 - 11:55 h, Room: H 3004, Talk 3

Ulrich Brenner
Fractional versus integral flows: A new approach to VLSI legalization


In VLSI placement legalization, a large set of rectangular
cells with the same height is given. The cells are spread
over a rectangular area but may still overlap, and
the task is to arrange them overlap-free into rows
such that the cells' movement
is minimized.
If we relax the problem by allowing to move fractions of cells, this
leads to a minimum-cost flow formulation.
Several legalization algorithms are based on that idea.
However, in the end we have to get rid of the relaxation since
cells cannot be split.
Most approaches just round the flow solution and then iterate
the whole process.
Our algorithm
is based on the Successive-Shortest Path Algorithm which iteratively
augments flow along paths, but we ensure
that only augmentations are considered that can
be realized exactly by cell movements.
Hence, the method avoids realization problems
which are inherent to previous flow-based legalization
We compare our approach to legalization tools from industry
and academia
by experiments on recent real-world designs and public benchmarks.
The results show that we are faster and produce significantly
smaller movements than any other tool.


  Do you need Missouri Payday Loans as soon as possible? 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 No RX influence on blood clots.