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

Non-smooth floorplanning method based on conjugate sub-gradient algorithm

作　　者：孙健 徐宁[2] 吴建 朱展洋 陈彧[1] 胡建国 Sun Jian;Xu Ning;Wu Jian;Zhu Zhanyang;Chen Yu;Hu Jianguo(School of Science,Wuhan University of Technology,Wuhan 430070,China;School of Information Engineering,Wuhan University of Technology,Wuhan 430070,China;Shenzhen Research Institute,Sun Yat-Sen University,Shenzhen Guangdong 528406,China)

机构地区：[1]武汉理工大学理学院,武汉430070 [2]武汉理工大学信息工程学院,武汉430070 [3]中山大学深圳研究院,广东深圳528406

出　　处：《计算机应用研究》2024年第9期2751-2757,共7页Application Research of Computers

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

摘　　要：针对只有硬模块的布图规划问题,通常将其构建成组合优化模型,但求解过程时间成本高。为提高求解效率,提出了一种基于非光滑解析数学规划的布图规划算法。基于布图中器件的坐标表示,构建了一个泛化的非光滑解析数学规划模型,将不同场景下的布图规划问题的不同优化阶段处理为该泛化模型的特例,并利用共轭次梯度算法(conjugate sub-gradient algorithm,CSA)对其进行求解。针对固定轮廓布图规划问题,通过统一框架下的全局布图规划、合法化、局部优化三个阶段,实现了在固定轮廓约束下的线长优化。针对无固定轮廓约束问题,提出了带黄金分割策略的共轭次梯度算法(conjugate sub-gradient algorithm with golden section strategy,CSA_GSS),利用黄金分割策略缩小固定轮廓的面积,达到面积和线长双优化的效果。实验在GSRC测试电路上与基于B*-树表示的布图规划算法进行比较,该算法对于大规模电路在线长和时间方面均占据优势。实验结果表明,该算法能以更低的时间复杂度获得更优的线长。Aiming at the floorplanning problem with only hard modules,it is usually constructed as a combinatorial optimization model,but the time cost of solving process is high.In order to improve the solving efficiency,this paper proposed a floorplanning algorithm based on non-smooth analytic mathematical programming.Based on the coordinate representation of mo-dules,this paper established a non-smooth mathematical programming model,which was a generalization of the optimization models corresponding to various optimization stages of different cases that were solved by the conjugate sub-gradient algorithm(CSA).Aiming at the fixed-outline floorplanning problem,this paper achieved wirelength optimization under fixed-outline constraint through the general framework consisted of three stages:global floorplanning,legalization and local optimization.To address the case without fixed-outline constraint,this paper proposed a conjugate sub-gradient algorithm with golden section stra-tegy(CSA_GSS).The algorithm adopted golden section strategy to reduce the area of the fixed-outline and to achieve the dual effect of both area and wirelength optimization.Compared with floorplanning algorithm based on B*-tree on GSRC test circuit,the proposed algorithm had advantages in terms of wirelength and time for large-scale circuits.Experimental results show that the algorithm can obtain better wirelength with lower time complexity.

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]