| Practical Approximation Algorithms for Separable Packing Linear Programs (2008) | |||||||||||||||
Abstract | |||||||||||||||
| We describefVkw polynomial time approximation schemes fm generalized multicommodity flow problems arising in VLSI applications such as Global Routing via Bu#er Blocks (GRBB). We extend Fleischer's improvement [7]of Garg and Konemann [8]f]AR polynomial time approximation schemefm edge capacitated multicommodity flows to multiterminal multicommodity flows in graphs with capacities on vertices and subsetsof vertices. In addition, our problemfob ulations observe upper bounds and parity constraints on the numberof vertices on any source-to-sink path. Unlike previous works on the GRBB problem [5,17], our algorithms can take into account (i) multiterminal nets, (ii) simultaneous bu#ered routing and compaction, and (iii) bu#er libraries. Our method outperfAVR existing algorithmsfl the problem and has been validated on top-level layouts extractedftr a recent high-end microprocessor design. 1 Intro ductio In this paper, we address the problem of how to performbu#erin of global nob given an existingbist bi ck plan. We give in teger linrb program (ILP) formulation of the basic Global Routin via Bu#er Blocks (GRBB) probleman its exten26b' to (i) multitermin7 nlti (ii) simultan678 bu#ered routinan compaction an (iii) bu#er libraries. Thefraction' relaxation of these ILP's are separab packing LP's (SP LP) which are multitermin] multicommodity flowsin graphs with capacitieson verticesan subsets of vertices. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||