PhDdefense3.pptVIP

Approximation Algorithms for VLSI Routing Ion I. Mandoiu Ph.D. Defense of Research August 11, 2000 VLSI Routing Overview of Results A New RSMT Heuristic The RSMT problem Why RSMT? Key Results on RSMT Problem The IRV Algorithm: High-Level Idea Iterative method: in each step add/remove one Steiner point to/from tree The Bidirected Cut Formulation The Bidirected Cut Formulation The Bidirected Cut Formulation The Bidirected Cut Formulation The Bidirected Cut Formulation (cont.) The Bidirected Cut Formulation (cont.) The Bidirected Cut Formulation (cont.) The Bidirected Cut Formulation (cont.) The RV Algorithm Adaptation to General Graphs Implementation Issues Size of graphs resulting from reduction to grid is a potential bottleneck Use efficiently computable reductions: Vertex reduction based on the empty rectangle test Edge reductions based on bound on max. degree of geometric MSTs (RS 95) Experimental Setup Test bed for experiments: Random instances ranging in size between 10 and 250 terminals, 1000 instances/size Instances extracted from industrial designs Measure of quality: percent improvement over MST Average Improvement over MST Average CPU Time Results on Industrial Instances Improved ZST and BST Approximation Algorithms Zero-Skew Trees The Zero-Skew Tree Problem Overview ZST Lower-Bound ZST Lower-Bound ZST Lower-Bound ZST Lower-Bound ZST Lower-Bound Constructive Lower-Bound Constructive Lower-Bound Stretching Rooted Spanning Trees Stretching Rooted Spanning Trees Stretching Rooted Spanning Trees Zero-Skew Spanning Tree Problem How good are the MST and Min-Star? The Rooted-Kruskal Algorithm The Rooted-Kruskal Algorithm How good is Rooted-Kruskal? How good is Rooted-Kruskal? Factor 4 Approximation Stretching Using Steiner Points Factor 3 Approximation Practical Considerations Running Time Extension to Other Metric Spaces Bounded-Skew Trees BST construction idea + lower bound Constructing the tree cover BST Approximation BST Approximation Summary of Resu