Advanced interior point techniques for placement, routing and floorplanning problems arising in integrated circuit design

点击翻译按钮获取中文摘要

The design of many fundamental manufacturing and circuit layout problems can be modeled as linear or nonlinear combinatorial optimization problems. All of these problems are NP hard. Very tight performance specifications for these problems (minimum area, minimum power and congestion) demand near optimal designs subject to many millions to billions of constraints and variables. Over the last six years, we have developed efficient optimization techniques that can be used to solve these problems using interior point and semidefinite programming approaches that can be solved in polynomial time. We have also developed efficient interior point solvers including warmstarting that accelerate solution times for combinatorial problems. A primary "objective'' of the proposed research is aimed at "integration" of large-scale interior point methodology used in linear, quadratic, convex, second-order cone programming and semidefinite programming to form the basis of generating relative placements and routings with "little or no overlap" while reducing wirelength and area. Recent advances in a "matrix free" interior point methods will allow the scope and size of solved problems to be in the order of millions or billions of constraints and variables. Initial focus will be on the generation of VLSI circuit layout for "standard cell'' and "mixed-size cell'' technologies that still form a major part of integrated circuit design. Floorplanning and facility layout problems will also be tackled. Another equally important "objective'' is to reduce the need for search techniques (i.e., Tabu Search) to further reduce wirelength and area as well as timing, delay, power and congestion problems. In this work, we plan to minimally use search techniques to refine feasible starting solutions that are generated by the proposed powerful interior point or semidefinite programming solvers. The aim is to use the mathematical programming models of placement, floorplanning and global routing and to solve them as efficiently as possible to reduce or ideally eliminate the need for search techniques.