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
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=667610
• 关键词: 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.***There are two main objectives in developing this research program and direction. First, a major objective of the proposed research program is aimed at "integration" of large-scale interior point methodologies used in linear, quadratic, convex, second-order cone programming to form the basis of generating relative placements and routings with "little or no overlap" while reducing wirelength and area. A second major objective is to develop promising approaches to "allow optimizers to scale"; that is, predictable fast running times will be achieved as problem size increases beyond a million constraints and variables for these present day layout problems. ***To achieve these objectives during the next five years, two novel approaches to solve large optimization problems containing more than a million variables and constraints will be developed. First, recent advances in "matrix free" interior-point approaches will allow the scope and size of solved problems to be in the order of millions or billions of variables and constraints. Second, we plan to accelerate interior-point algorithms using new warmstarting techniques to speed up the running time of for these very large problems. ***Initial focus will be on the generation of Very Large Scale Integrated (VLSI) circuit layout for "standard cell" and "mixed cell" technologies that still form a major part of integrated circuit design. Second, the exploration of analytic-based models and large-scale nonlinear interior-point solvers will be developed to solve emerging large placement problems arising in Field Programmable Gate Array (FPGAs) layout. ***Another equally important "objective" of this research is to reduce the need for search techniques such as simulated annealing, genetic algorithms and Tabu search to further reduce wirelength and area as well as timing, delay, power and congestion problems. In this overall research program, we plan to minimally use search techniques to refine feasible starting solutions that are generated by the powerful interior point or semidefinite programming solvers. The aim is to use 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. **

许多基本的制造和电路布局问题的设计可以建模为线性或非线性组合优化问题。所有这些问题都是NP难的。对于这些问题(即最小有线长度、最小面积、最小功率和拥塞)非常严格的性能规格要求近乎最优的设计，受制于数百万到数十亿的变量和约束。在过去的六年里，我们开发了有效的优化技术，可以使用内点和半定规划方法来解决这些问题，这些方法可以在多项式时间内求解。*发展这一研究计划和方向有两个主要目标。首先，拟议研究计划的一个主要目标是将线性、二次、凸、二阶锥体规划中使用的大规模内点方法进行“集成”，以形成在减少线长和面积的同时生成“很少或没有重叠”的相对放置和布线的基础。第二个主要目标是开发有前景的方法来“允许优化器进行扩展”；也就是说，当问题的大小增加到超过当前布局问题的一百万个约束和变量时，将实现可预测的快速运行时间。*为了在未来五年内实现这些目标，将开发两种新的方法来解决包含100多万个变量和约束的大型优化问题。首先，“无矩阵”内点方法的最新进展将允许解决的问题的范围和大小在数百万或数十亿个变量和约束的数量级。其次，我们计划使用新的热启动技术来加速内点算法，以加快对这些非常大的问题的运行时间。*最初的重点将是为“标准单元”和“混合单元”技术生成超大规模集成电路(VLSI)电路布局，这两种技术仍是集成电路设计的主要部分。其次，将开发基于解析模型和大规模非线性内点求解器的探索，以解决现场可编程门阵列(现场可编程门阵列)布局中出现的新的大型布局问题。*这项研究的另一个同样重要的“目标”是减少对诸如模拟退火法、遗传算法和禁忌搜索等搜索技术的需求，以进一步减少无线长度和面积以及定时、延迟、功率和拥塞问题。在这个整体的研究计划中，我们计划最小限度地使用搜索技术来精炼由强大的内点或半定规划求解器生成的可行起始解。其目的是使用布局、布局规划和全局布线的数学规划模型，并尽可能有效地求解它们，以减少或理想地消除对搜索技术的需求。**