一种基于共轭次梯度算法的非光滑布图规划方法

来源：计算机应用研究杂志2024年第9期北京时间：

作者：孙健,徐宁,吴建,朱展洋,陈彧,胡建国,

单位：1.武汉理工大学a.理学院;b.信息工程学院,武汉430070；2.中山大学深圳研究院,广东深圳528406；

摘要：针对只有硬模块的布图规划问题，通常将其构建成组合优化模型，但求解过程时间成本高。为提高求解效率，提出了一种基于非光滑解析数学规划的布图规划算法。基于布图中器件的坐标表示，构建了一个泛化的非光滑解析数学规划模型，将不同场景下的布图规划问题的不同优化阶段处理为该泛化模型的特例，并利用共轭次梯度算法（conjugate sub-gradient algorithm，CSA）对其进行求解。针对固定轮廓布图规划问题，通过统一框架下的全局布图规划、合法化、局部优化三个阶段，实现了在固定轮廓约束下的线长优化。针对无固定轮廓约束问题，提出了带黄金分割策略的共轭次梯度算法（conjugate sub-gradient algorithm with golden section strategy，CSA_GSS），利用黄金分割策略缩小固定轮廓的面积，达到面积和线长双优化的效果。实验在GSRC测试电路上与基于B*-树表示的布图规划算法进行比较，该算法对于大规模电路在线长和时间方面均占据优势。实验结果表明，该算法能以更低的时间复杂度获得更优的线长。

关键词：大规模集成电路,布图规划,非光滑优化,固定轮廓,共轭次梯度法,

基金资助：深圳科技计划资助项目(JCYJ20220818102002005)；科技部科技创新2030—“新一代人工智能”重大项目(2021ZD0114600)；；