超大规模集成电路布局的优化模型与算法

布局确定集成电路单元在芯片中的具体位置，在单元互不重叠的基础上优化一些性能指标。该问题是NP困难的组合优化问题，是超大规模集成电路物理设计的核心问题之一，对集成电路的性能指标，如线网可布通性、时延、功耗、电路可靠性等有重大影响。在现代的集成电路设计中，布局问题通常包含数百万个集成电路单元，以及大小相异的异质性模块，和各种复杂的布局约束。目前的超大规模集成电路布局算法通常分解为总体布局、布局合法化和详细布局三个步骤。根据近年来集成电路布局算法的研究进展，综述并分析集成电路的总体布局、布局合法化和详细布局的相关优化模型和算法，并展望进一步的研究方向。

Optimization models and algorithms for placement of very large scale integrated circuits

Placement is one of the critical stages in the physical design of very large scale integrated circuits (VLSI), which has significant impact on the performance of integrated circuits, such as routability, delay, power consumption, circuit reliability, etc. Placement determines the specific positions of cells of a chip, by optimizing some performance metrics under the constraint of cells non-overlapping, which is an NP-hard combinatorial optimization problem. Modern placement algorithms need to deal with large-scale designs with millions of cells, heterogeneous modules with different sizes, and various complex placement constraints. Modern placement algorithms usually consist of three steps:global placement, legalization, and detailed placement. Based on the recent research progress of VLSI placement algorithms, this paper surveys related optimization models and algorithms for VLSI global placement, legalization and detailed placement, and discusses possible research directions.