Invited Session Tue.1.H 3021

Tuesday, 10:30 - 12:00 h, Room: H 3021

Cluster 2: Combinatorial optimization [...]

Data structures and algorithms for VLSI routing


Chair: Tim Nieberg



Tuesday, 10:30 - 10:55 h, Room: H 3021, Talk 1

Dirk Müller
Multi-flows and generalizations in VLSI routing


In the (global) routing of VLSI chips, limited space must be shared by different
connections, so-called nets.
In this context, multi-commodity flow problems arise naturally, and
approximation schemes have been applied to them and their generalizations to
fractional Steiner tree packing successfully for more than 15 years,
the traditional objective being wire length minimization.
Technology scaling causes a growing need to extend global routing to directly consider
other objectives and additional constraints, such as signal delays, power consumption
and manufacturing yield. All these depend non-linearly on the spacing between wires.
Because these dependencies are given by convex functions, we can show that a fractional
relaxation of the extended global routing problem can be formulated as a block-angular
min-max resource sharing problem. We present a simple approximation scheme for this problem
which generalizes and improves various previous results, and can be parallelized very efficiently.
Furter, we show experimental results on recent industrial chips with millions of nets and



Tuesday, 11:00 - 11:25 h, Room: H 3021, Talk 2

Christian Schulte
Efficient algorithms and data structures in VLSI detailed routing

Coauthors: Michael Gester, Dirk Müller, Tim Nieberg, Christian Panten, Jens Vygen


We present the core elements of detailed routing in BonnRoute.
Long-distance connections are computed by a fast, interval based path
search algorithm using efficient data structures for routing space
representation. With advanced pin access strategies we avoid local
conflicts in dense pin configurations.
BonnRoute is able to handle complex design rules in modern technologies,
and is used in practice on current, real world designs.
Compared to an industrial routing tool it is much faster
and gives better results in terms of total connection length
and number of detours.



Tuesday, 11:30 - 11:55 h, Room: H 3021, Talk 3

Michael Gester
New challenges in chip design driven by technology scaling

Coauthors: Dirk Müller, Tim Nieberg, Christian Panten, Christian Schulte, Jens Vygen


While structures on modern computer chips are getting smaller and smaller, e.g., by the use of more sophisticated lithography techniques, the design rules which chip design software has to respect are increasing in number and are getting more and more complex. This leads to various new algorithmical challenges in
chip design. We discuss some of the most important challenges from a practical and from a theoretical perspective.
Special emphasis is put on double patterning lithography. Here all structures on a single chip layer are assigned to two
different production steps in manufacturing. This assignment can be considered as a coloring problem on a conflict graph which arises in different areas of chip design and has fundamental consequences for the whole design flow of modern computer chips.


  The best way to go for you to know the credible Michigan Loans Online providers. Thanks to that, they have a great variety of drugs that can help in these cases. Female Viagra is not an exception.