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

布局是超大规模集成电路（VLSI）物理设计的关键环节之一，是典型的大规模NP困难问题。随着电路芯片的集成度不断提高，VLSI布局对优化目标的准确性和优化方法的效率提出了更高要求。VLSI布局的目标是最小化半周长之和的总线长。由于半周长线长是一个非光滑凸函数，当前基于分析方法的各种布局算法都是采用不同的线长模型对其进行近似，存在较大误差，不能很好反映布局的实际线长。针对该问题，本项目研究直接优化半周长线长的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.