直接优化半周长线长的VLSI两阶段迭代布局算法研究

Placement is a crucial step in very large scale integration (VLSI) physical design. It is a typical NP-hard problem. With the development of chip integration, VLSI placement comes higher standard over the accuracy of optimization object and the efficiently of optimization methods. The objective of VLSI placement problem is to minimize its total wire length which is calculated by the half-perimeter wire length (HPWL) method. Since HPWL is not differentiable (although convex), various wire length models have been proposed to approximate it in the analytical methods. However, there is a gap between their solutions and the actual total wire length. In this proposal, we investigate the method to optimize the total HPWL directly. Based on the framework of the two-phase iterative placement algorithm, this proposal aims to design a two-phase iterative placement algorithm for direct optimization of total HPWL. The algorithm contains four major parts: 1) an optimization method to handle HPWL and analyze the convergence of the method in the first phase; 2) an enhanced cell distribution technique to reduce the cell overlaps in the second phase; 3) an interactive method to control the number of iterations of the first and second phases; 4) and an appropriate stopping criteria for the iterative method. In addition, the multilevel framework will be used to make the algorithm much more scalable. As predicted in the proposal, the algorithm could solve the VLSI placement problem effectively and efficiently.

布局是超大规模集成电路（VLSI）物理设计的关键环节之一，是典型的大规模NP困难问题。随着电路芯片的集成度不断提高，VLSI布局对优化目标的准确性和优化方法的效率提出了更高要求。VLSI布局的目标是最小化半周长之和的总线长。由于半周长线长是一个非光滑凸函数，当前基于分析方法的各种布局算法都是采用不同的线长模型对其进行近似，存在较大误差，不能很好反映布局的实际线长。针对该问题，本项目研究直接优化半周长线长的VLSI布局算法。在具有较大优势的基于分析方法的两阶段迭代布局框架下，设计求解半周长线长函数的第一阶段问题的算法并分析算法的收敛性，改进第二阶段的单元散开方式，研究第一阶段与第二阶段的交互技术，分析与选择迭代终止准则，从而得到直接优化半周长线长的两阶段迭代布局算法。在此基础上，利用多极框架进一步提高该算法求解更大规模布局问题的能力，最终获得高效率、高质量的基于两阶段迭代的布局工具。

布局是超大规模集成电路（VLSI）物理设计的关键环节之一，是典型的大规模NP困难问题。随着电路芯片的集成度不断提高，VLSI布局对优化目标的准确性和优化方法的效率提出了更高要求。VLSI布局的目标是最小化半周长之和的总线长。由于半周长线长是一个非光滑凸函数，当前基于分析方法的各种布局算法都是采用不同的线长模型对其进行近似，存在较大误差，不能很好反映布局的实际线长。针对该问题，本项目研究直接优化半周长线长的VLSI布局算法,并考虑不同约束的布局问题。. 我们提出一种基于分离变量法和精确的密度函数的解析方法求解泊松方程，可实现当前全局布局工具中最好的线长；在利用近端群域多乘子交替方向法同时考虑在全局布局中雾化效应和邻近效应约束，可显著提高布局质量。对多倍高的布局合法化问题，我们在尽量保持全局布局单元位置不变的基础上，提出了一个快速且接近最优的算法（MMSIM）来解决混合高度单元的合法化问题。在单元合法化过程中，我们额外考虑了最小植入区域约束，技术约束和区域约束，相比当前最先进的合法化布局工具，我们的合法化算法均可实现更好的布局质量。对包含不同约束的超大规模集成电路设计问题，我们通过离散松弛优化算法和整数规划算法来处理DSA的通孔层掩模板和模板分配问题，并提出了一种自适应混合模型算法来处理多目标热感知非切片布局规划优化问题，同时优化芯片的面积、总线长、最高温度和平均温度。. 在本项目支持下，项目组成员取得的主要成就如下：获第54届设计自动化会DAC 2017最佳论文奖；获第36届国际集成电路计算机辅助设计会议（ICCAD 2017）所举行的CAD学术竞赛全球第一名；蝉联第37届国际集成电路计算机辅助设计会议（ICCAD 2018）所举行的CAD学术竞赛全球第一名；在第37届国际集成电路计算机辅助设计会议（ICCAD 会议）发表论文4篇，并且其中一篇论文获得ICCAD 2018最佳论文提名奖；获首届中国计算机学会（CCF）集成电路Early Career Award。