Invited Session Mon.2.H 3004

Monday, 13:15 - 14:45 h, Room: H 3004

Cluster 2: Combinatorial optimization [...]

Combinatorial optimization in chip design II


Chair: Ulrich Brenner



Monday, 13:15 - 13:40 h, Room: H 3004, Talk 1

Ulrike Suhl
Lagrangian relaxation and quadratic minimum cost flows for gate sizing

Coauthor: Stephan Held


One of the key problems during the physical design of a computer chip is to choose a physical realization (gate size) for each gate/transistor on the chip from a discrete set. Available sizes for a gate differ in their power and area usage, and influence the time it takes electrical signals to traverse the chip.
We present a Gate Sizing algorithm based on Lagrangian Relaxation minimizing overall circuit power, while fulfilling constraints imposed on the speed of electrical signals.
We restrict gate sizes to the discrete sets available in practice, and solve a discretized primal problem to avoid a rounding step in the end. Instances are modified appropriately to guarantee the existence of a finite dual solution.
Lagrange Multiplier have to be projected to the flow space, which can be formulated as a Quadratic Minimum Cost Flow Problem.
Constraints on the area usage of gates in specified regions on the chip can be incorporated directly into the framework, and we show convergence for the continuous case.



Monday, 13:45 - 14:10 h, Room: H 3004, Talk 2

Christoph Bartoschek
Fast buffering of repeater trees

Coauthors: Stephan Held, Jens Vygen


The optimization of electrical interconnections is a critical task in the design of modern VLSI chips. A popular approach is to divide the problem into a Steiner tree computation and a buffering step that inserts repeaters for strengthening the electrical signals. For buffering it is common to use a dynamic program that is also the basis for a FPTAS to find low-power delay-optimal solutions. However, there are several drawbacks. Firstly, potential buffer positions have to be chosen upfront. Secondly, the underlying embedded tree topology is fixed. Finally, dynamic programming causes high running times. We present a fast algorithm for the buffering problem. It precomputes technology dependent optimal spacings, so that long distances can be buffered quickly using the precomputed data. Merging branches at steiner points is done by a short enumeration of possible solutions. We modify the original Steiner topology if this reduces the numder of inserted repeaters, which sometimes would only be required for preserving Boolean parity. We present computational results demonstrating the high and often superior quality of our buffering solutions.



Monday, 14:15 - 14:40 h, Room: H 3004, Talk 3

Stephan Held
Delay bounded Steiner trees and time-cost tradeoffs for faster chips


We will present combinatorial optimization algorithms that focus on
maximizing the clock frequency of modern microprocessors. One central
problem is the construction of Steiner trees with delay
constraints. They are used for optimizing electrical interconnections and
symmetric Boolean functions. We provide a bicriteria approximation
algorithm for tree topologies with node delays in addition to length
dependent delays. This is done by generalizing light approximate
shortest path trees.
For finding globally optimal solutions, many resource critical
problems such as threshold voltage of transistors and layer assignment
of interconnect wires can be modeled as time-cost tradeoff problems.
We will present a new method based on rounding the dual of
Minimum-Cost Flows.
Finally, we will demonstrate how the presented algorithms are employed
for increasing the clock frequency by 18,% of an upcoming


  To apply for Payday Loans In United States you don't have to seek the help of relatives or go to a bank. There are also a lot of other privileges for return customers. Men buy Viagra Gold online not to wait till the lucky event happens but to enjoy each sex act because Viagra effect lasts up to 36 hours!