超大规模集成电路布局的ell-1模优化模型及其算法研究

布局是超大规模集成电路物理设计自动化的主要环节之一。由于集成电路的规模越来越大，对布局问题的优化目标和优化方法提出了更高的要求。当前基于分析方法的各种布局算法都是对半周长线长作光滑化近似，不能很好地反应实际布局的需求。本项目主要针对该问题开展研究，取得了以下主要成果：.. 我们研究了超大规模集成电路混合单元布局问题，提出了l1模线长目标函数和非光滑密度约束的布局非线性规划模型，提出了基于非光滑优化的布局算法，由此形成的布局工具解的质量比当前最好的布局工具ePlace及工业上所采用的布局工具CAPO10.5、SimPL等有较大幅度的提高，可满足工业界对布局问题的需求。该研究成果获得国际学术界和业界的好评，被认为是指出布局研究的新方向，Fuzhou Placer等；我们研究了基于增广拉格朗日函数法的VLSI全局布局算法，并用来解决超大规模集成电路物理设计中的全局布局问题，改进了以往的基于非线性规划的布局算法都是采用惩罚函数法求解的缺点；研究了超大规模集成电路两阶段布局算法的第一阶段中的凸优化问题，基于Nesterov光滑化技术和Excessive gap technique，构造了一个原始-对偶一阶优化算法，证明了算法的收敛速度是最优的；针对超大规模集成电路的modern mixed-size布局问题，设计并实现了一个新的布局流程。与当前最好的混合单元布局器相比，本算法可有效处理包含可移动宏单元的超大规模集成电路布局问题；研究了从超大规模集成电路全局布局中提取的非凸非线性规划问题，构造了基于临近点的交替方向法，在适当条件下证明了算法收敛于问题的KKT点；研究了超大规模集成电路标准单元布局的聚类方法，提出了考虑位置信息的聚类方法，实验表明该策略对集成电路布局问题是有益的。同时，我们还研究了超大规模集成电路标准单元阵列布局问题的快速遗传算法，二维strip packing问题，超大规模集成电路划分问题，图的最大二等分问题，图的max-k-cut问题等。.. 在本项目的资助下，课题组共发表学术刊物论文35篇，其中SCI收录刊物论文20篇，其中CCF A类刊物论文3篇，CCF B类刊物论文3篇， CCF C类刊物论文2篇；申请发明专利4项。