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

布局是超大规模集成电路物理设计自动化的主要环节之一。由于集成电路的规模越来越大，对布局问题的优化目标和优化方法提出了更高的要求。超大规模集成电路布局问题的原始的目标函数是用ell-1模计算的，当前基于分析方法的各种布局算法都是对其作光滑化近似，不能很好地反应实际布局的需求。针对该问题，本项目研究该目标函数下的标准单元和混合单元布局问题的优化算法。对非光滑密度约束的全局布局问题，本项目将构造基于Lagrange函数的临近点交替方向法；对光滑化后的密度约束的全局布局问题，利用序列二次规划算法的思想，构造临近点交替方向法求解该问题，并分析算法的收敛性。同时，利用超大规模集成电路的稀疏结构，改进所构造的算法以求解更大规模的全局布局问题，减少布局算法分层次数。为使得到的解更优，本项目将研究好的初始解的生成方法。最后结合分层等技术实现整个布局算法，并研究其性能，最终形成工业上可用的布局软件核心技术。

布局是超大规模集成电路物理设计自动化的主要环节之一。由于集成电路的规模越来越大，对布局问题的优化目标和优化方法提出了更高的要求。当前基于分析方法的各种布局算法都是对半周长线长作光滑化近似，不能很好地反应实际布局的需求。本项目主要针对该问题开展研究，取得了以下主要成果：.. 我们研究了超大规模集成电路混合单元布局问题，提出了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项。