基于半周长线长的VLSI布局模型及其算法研究

Placement is a crucial step in very large scale integration (VLSI) physical design automation. In modern VLSI placement, the size of chip becomes larger and the required technology keeps increasing raise the bar even higher on optimization objective and optimization methods. The objective of VLSI placement is to minimize its total wirelength which is calculated by total half-perimeter wirelength (HPWL). Since the HPWL is not differentiable (although convex), various wirelength functions have been proposed to approximate it in analytical methods. In this proposal, we study the method to optimize the total HPWL. Firstly, we construct the placement model. Then, we present the methods to handle the objective function, the ways to deal with placement constraints, and the optimization algorithm. In addition, we analyze the convexity, monotonicity of gradient and separability of the placement model. Using the properties above, we also analyze the convergence of the optimization algorithm. With the multilevel technique, a VLSI placer is generated finally. Based on the efforts above, we hope that the VLSI placer is effective and efficient, and can be applied to industry.

布局是超大规模集成电路（VLSI）物理设计自动化的关键环节之一。随着集成电路规模的不断增大及工艺上的要求越来越高，对VLSI布局优化目标及优化方法提出了更高的要求。VLSI布局问题的目标是最小化半周长线长计算的总线长。半周长线长是一个不连续可微的凸函数。当前基于分析方法的各种布局算法都是对半周长线长作光滑化近似，不能很好地反应实际布局的目标。针对该问题，本项目对基于半周长线长计算的VLSI布局问题展开研究。通过建立问题模型，给出目标函数的处理方法、约束条件的处理技术及所采用的优化算法，并分析所建立的问题模型的凸性、可分离性、梯度单调性及采用的优化算法的收敛性等。在此基础上，结合VLSI分层技术，获得高质量、高效率的基于解析方法的布局算法，最终生成工业上可用的布局软件。

针对当前基于分析方法的各种超大规模集成电路（VLSI）布局算法都是对半周长线长(不连续可微的凸函数)作光滑化近似，不能很好地反应实际布局的目标，本项目对基于半周长线长计算的VLSI布局问题展开研究。通过建立不同的线长模型及约束模型，给出线长函数的处理方法、约束条件的处理技术及所采用的优化算法，并分析所建立的问题模型的凸性、可分离性、梯度单调性及采用的优化算法的收敛性等。在此项目资助下，已发表论文两篇，投稿论文两篇，申请国家发明专利一项，软件著作权二项。.本项目中，最主要的工作为提出一种非光滑但可精确计算半周长线长的l1-norm线长模型。在l1-norm线长模型和精确计算单元与BIN的密度的基础上，将线长目标及密度约束转化为无约束的非线性规划问题。采用一种非光滑的优化技术对此非线性规划问题进行求解，并及分析所采用的算法的局部收敛性。采用IBM及相关ISPD竞赛的测试例子集对我们所提出的算法进行测试，实验结果表明，由此形成的布局工具，解的质量比当前最好的布局工具EPLACE提高1.1%。