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

许多基本制造和电路布局问题的设计都可以建模为线性或非线性组合优化问题。所有这些问题都是NP困难的。对于这些问题（最小面积，最小功率和拥塞），非常严格的性能规格要求接近最佳设计，受到数百万到数十亿的约束和变量的影响。在过去的六年里，我们已经开发了有效的优化技术，可以用来解决这些问题，使用内点和半定规划方法，可以在多项式时间内解决。我们还开发了高效的内部点求解器，包括加速组合问题的求解时间的热启动。

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.