Nonsmooth Optimization Method for VLSI Global Placement
Nonsmooth Optimization Method for VLSI Global Placement
复制标题
DOI：
10.1109/tcad.2015.2394484
复制
发表时间：
2015-01
影响因子：
2.9
通讯作者：
Wen-xing Zhu;Jianli Chen;Zheng Peng;Genghua Fan
中科院分区：
文献类型：
--
作者：
Wen-xing Zhu;Jianli Chen;Zheng Peng;Genghua Fan
超大规模集成(VLSI)布局问题的共同目标是最小化总布线长度，该总布线长度由总半周布线长度(HPWL)计算。由于HPWL是不可微的，因此在解析布局方法中提出了各种可微的线长近似函数。在本文中，我们将HPWL重新表示为线长函数的L1范数模型，该模型是精确的但不光滑的。基于L1范数线长模型和单元与箱体重叠面积的精确计算，提出了VLSI全局布局问题的非光滑优化模型，并提出了求解非光滑优化问题的次梯度方法。此外，在适当的条件下，证明了次梯度法的局部收敛。此外，在非光滑优化方法中还采用了自适应参数控制步长和谨慎增加惩罚参数两种改进技术。为了使布局方法具有可扩展性，采用了多层次的布局框架。在聚类阶段，根据L1范数线长模型改进最优选择聚类算法对小区进行聚类，在去聚阶段递归使用非光滑优化方法。对2005年国际物理设计研讨会(ISPD)和2006年国际物理设计会议(ISPD)基准的实验结果的比较表明，全局布局方法是很有前途的。
The common objective of very large-scale integration (VLSI) placement problem is to minimize the total wirelength, which is calculated by the total half-perimeter wirelength (HPWL). Since the HPWL is not differentiable, various differentiable wirelength approximation functions have been proposed in analytical placement methods. In this paper, we reformulate the HPWL as an l1-norm model of the wirelength function, which is exact but nonsmooth. Based on the l1-norm wirelength model and exact calculation of overlapping areas between cells and bins, a nonsmooth optimization model is proposed for the VLSI global placement problem, and a subgradient method is proposed for solving the nonsmooth optimization problem. Moreover, local convergence of the subgradient method is proved under some suitable conditions. In addition, two enhanced techniques, i.e., an adaptive parameter to control the step size and a cautious strategy for increasing the penalty parameter, are also used in the nonsmooth optimization method. In order to make the placement method scalable, a multilevel framework is adopted. In the clustering stage, the best choice clustering algorithm is modified according to the l1-norm wirelength model to cluster the cells, and the nonsmooth optimization method is recursively used in the declustering stage. Comparisons of experimental results on the International Symposium on Physical Design (ISPD) 2005 and 2006 benchmarks show that the global placement method is promising.