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

先进的内点技术，解决集成电路设计中出现的布局、布线和布局规划问题

• 批准号: 44456-2011
• 负责人: Vannelli, Anthony
• 金额: $ 1.97万
• 依托单位: University of Guelph
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=568926
• 关键词: Advanced; interior; point; techniques; placement

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.

许多基本制造和电路布局问题的设计可以建模为线性或非线性组合优化问题。所有这些问题都很难。这些问题（最小面积，最小功率和拥塞）的最佳性能规格非常紧密，需要数百万美元的最佳设计，并受到数百万个约束和变量的需求。在过去的六年中，我们开发了有效的优化技术，可以使用内部点和半决赛编程方法来解决这些问题，这些方法可以在多项式时间内解决。我们还开发了有效的内点求解器，包括加速解决方案时间的求解时间。 拟议研究的主要“客观”旨在“整合”大规模内部点 在线性，二次，凸，二阶锥度编程和半决赛编程中使用的方法，以形成与“很少或没有重叠”的相对位置和路由的基础，同时降低电线长度和区域。 “免费矩阵”内部方法的最新进展将使解决问题的范围和大小按数百万或数十亿个约束和变量的顺序。最初的焦点将集中在“标准单元格”和“混合尺寸单元格”技术的VLSI电路布局上，这些技术仍然构成了集成电路设计的主要部分。也将解决平面图和设施布局问题。 另一个同样重要的“客观”是减少对搜索技术的需求（即禁忌搜索），以进一步降低电线长度，区域以及时间安排，延迟，功率和拥塞问题。在这项工作中，我们计划使用最小的搜索技术来完善可容纳的启动解决方案，这些解决方案是由提议的强大的室内或半度性的编程，以实现的范围为目标，以实现目标，以实现目标和半度性的编程。全球路线并尽可能有效地解决它们，以减少或理想地消除对搜索技术的需求。