VLSI详细布线算法研究进展  

Research progress of VLSI detailed routing algorithm

作　　者：屈通 盖天洋 王书涵 苏晓菁 粟雅娟[1,2,3] 韦亚一 QU Tong;GAI Tianyang;WANG Shuhan;SU Xiaojing;SU Yajuan;WEI Yayi(Institute of Microelectronics of the Chinese Academy of Sciences,Beijing 100029,China;University of Chinese Academy of Sciences,Beijing 100049,China;Guangdong Greater Bay Area Applied Research Institute of Integrated Circuit and Systems,Guangzhou 510535,China)

机构地区：[1]中国科学院微电子研究所,北京100029 [2]中国科学院大学,北京100049 [3]广东省大湾区集成电路与系统应用研究院,广东广州510535

出　　处：《微电子学与计算机》2021年第11期1-6,共6页Microelectronics & Computer

基　　金：国家自然科学基金(61874002);北京市自然科学基金(4182021);国家重点研发计划(2019YFB2205005)。

摘　　要：超大规模集成电路(VLSI)中的详细布线是物理设计中一个重要且具有挑战性的环节.在这一阶段,所有导线的路径都会被确定下来,布线的优劣直接关系到芯片的面积和性能,路径搜索是布线中最为耗时的步骤之一.本文介绍了基于网格的布线模型,将布线问题抽象为一个图搜索问题或者多商品流问题;总结了迷宫搜索算法、A*算法、整数线性规划(ILP)算法和并行加速算法在路径搜索中的应用和针对设计约束作出的优化,结合在布线器中应用情况分析其优劣;总结回顾了基于机器学习求解算法的研究进展,分析了存在的问题,并对详细布线算法的发展趋势做了展望.分析表明,A*算法在布线质量、稳定性和速度等方面的综合性能较其他算法更为优异,其难点在于设计合理的布线排序策略和图模型.强化学习具有巨大的研究潜力,目前的研究仅在规模较小的设计中测试,仍需要进一步改进和探索.Detailed routing in very-large-scale integration(VLSI)is one of the most important and challenging stages in physical design.The path of all wires will be determined at this stage,the quality of routing is directly related to the area and performance of the chip.The path search is one of the most time-consuming steps in routing.First,the grid-based routing model is described in this paper,which models the routing problem into a graph search problem or a multi-commodity flow problem.Then it summarizes the application of maze search algorithm,A*algorithm,integer linear programming(ILP)algorithm,and parallel acceleration algorithm in path search and optimization for design constraints,and analyzes its pros and cons in the application of routers.Finally,it summarized and reviewed the research progress of algorithms based on machine learning,analyzed the existing problems,and looked forward to the development trend of detailed routing algorithms.Analysis shows that the comprehensive performance of the A*algorithm in terms of routing quality,stability,and speed is over performed than other algorithms.The difficulty lies in designing a reasonable routing strategy and graph model.Reinforcement learning has great research potential,the current research is only tested in a small-scale design,and further improvement and exploration are still needed.

关 键 词：详细布线 机器学习 强化学习 迷宫搜索 整数线性规划 

分 类 号：TN47[电子电信—微电子学与固体电子学]