博士论文ppt(45).ppt

Ion I. Mandoiu
. Defense of Research
August 11, 2000
Approximation Algorithms for VLSI Routing
VLSI Routing
VLSI Physical Design
Electrical description  Geometrical layout
VLSI Global Routing
Given: locations terminals
Find: tree interconnection for
Minimizing:
total length (RSMT problem)
skew (ZST problem)
number of buffers (MSPT problem)
…
Overview of Results
routing:
New RSMT heuristic
runs 10 times faster, and gives higher-quality solutions than previous best RSMT heuristic
Improved ZST approximation algorithms
very fast: O(n log n) running time
Tight analysis of the MST heuristic for MSPT
routing:
MCF-based approximation algorithms for global buffering via buffer blocks
A New RSMT Heuristic
The RSMT problem
RSMT
Steiner point
MST
MST gives 3/2 approximation [H76]
Why RSMT?
Minimum wire length gives
Minimum area
Minimum resistance/capacitance
RSMT used for:
Non-s
Physically small instances
Key Results on RSMT Problem
Reduction to discrete grid [H66]
NP-hard [GJ77]
Iterated 1-Steiner heuristic [KR90]
Greedily adds Steiner points to the tree
Almost 11% improvement over MST on average
Fast batched implementation (BI1S)
Exact algorithm: GeoSteiner [WWZ98]
Branch-and-cut
% improvement over MST on average
Average parable to BI1S!!!
The IRV Algorithm: High-Level Idea
Iterative method: in each step add/remove one Steiner point to/from tree
Unlike Iterated 1-Steiner heuristic, do not insist on choosing best Steiner point in each step
Steiner point to be added is chosen using a powerful LP formulation of the Steiner tree problem in graphs, called the bidirected cut formulation
The Bidirected Cut Formulation