Advanced Large-Scale Optimization Approaches to Solve Modern Circuit Layout Problems

解决现代电路布局问题的先进大规模优化方法

• 批准号: RGPIN-2016-03833
• 负责人: Vannelli, Anthony
• 金额: $ 1.75万
• 依托单位: University of Saskatchewan
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=636889
• 关键词: Advanced; Large; Scale; Optimization; Approaches

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 (i.e., minimum wirelength, minimum area, minimum power and congestion) demand near optimal designs subject to many millions to billions of variables and constraints. 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.

许多基本制造和电路布局问题的设计可以建模为线性或非线性组合优化问题。所有这些问题都是NP-HARD。这些问题的性能规格非常紧密（即，最小线长，最小面积，最小功率和拥塞）的需求靠近最佳设计，但受到数百万至数十亿个变量和约束的影响。在过去的六年中，我们开发了有效的优化技术，可以使用内部点和半决赛编程方法来解决这些问题，这些方法可以在多项式时间内解决。