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

许多基本的制造和电路布局问题的设计可以建模为线性或非线性组合优化问题。所有这些问题都是NP难的。这些问题（最小面积、最小功率和拥塞）的非常严格的性能规范要求接近最优设计，这些设计受到数百万到数十亿的约束和变量的影响。在过去的六年中，我们已经开发出有效的优化技术，可以用来解决这些问题，使用内点和半定规划方法，可以在多项式时间内解决。我们还开发了高效的内点求解器，包括warmstarting，加快组合问题的解决时间。 所提出的研究的一个主要“目标”是针对大规模内部点的“整合” 在线性、二次、凸、二阶锥规划和半定规划中使用的一种方法，用于形成生成“很少或没有重叠”的相对布局和布线的基础，同时减少线长和面积。“无矩阵”内点方法的最新进展将允许解决的问题的范围和大小在数百万或数十亿的约束和变量的顺序。最初的重点将是为“标准单元”和“混合尺寸单元”技术生成VLSI电路布局，这些技术仍然是集成电路设计的主要部分。平面规划和设施布局问题也将得到解决。 另一个同样重要的“目标”是减少对搜索技术的需求（即，禁忌搜索），以进一步减少线长和面积以及定时，延迟，功率和拥塞问题。在这项工作中，我们计划最低限度地使用搜索技术来完善可行的起始解决方案，所提出的强大的内点或半定规划求解器。其目的是使用数学规划模型的布局，布局规划和全局布线，并解决他们尽可能有效地减少或理想地消除搜索技术的需要。

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.