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

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