芯片智能布线方法研究综述  

Survey on Intelligent Routing Approaches for Chips

作　　者：周展文[1] 卓汉逵[1] ZHOU Zhan-Wen;ZHUO Han-Kui(School of Computer Science and Engineering,Sun Yat-sen University,Guangzhou 510006)

机构地区：[1]中山大学计算机学院,广州510006

出　　处：《自动化学报》2024年第9期1671-1703,共33页Acta Automatica Sinica

摘　　要：布线是芯片设计自动化流程中至关重要且特别耗时的一环,直接影响最终产品的面积、成本、功耗、速度和可靠性,研究智能布线算法对提高芯片布线效率和优化芯片布线效果具有重要意义.芯片布线问题是一个多目标、多约束的NP困难问题.即使已有几十年的研究历史,目前仍存在大量未突破的问题和空间.随着制造工艺的不断发展,布线规则、约束和目标也持续调整和增加,使得布线选择极其困难.因此,对芯片设计自动化中自动布线的前沿研究进行了全面归纳与分析,以帮助科研人员全面了解该领域的研究进展和方向,助力智能布线算法的研究和发展.具体而言,首先阐述芯片布线的问题背景,然后分别介绍全局布线(Global routing,GR)和详细布线(Detailed routing,DR)的任务定义和目标、过程特点、难点和挑战、评估方法;接着详述和分析各布线方法,重点论述基于规划搜索的布线方法和基于机器学习的布线方法的最新研究成果、优缺点及其应用环节;然后介绍公开数据集和开源布线工具;最后总结现有方法在实际应用中存在的局限性,并对自动布线未来的发展趋势和潜在研究方向进行展望.Routing is a crucial and particularly time-consuming part of the chip design automation process,directly affecting the area,cost,power consumption,speed and reliability of the final product.It is of great significance to study intelligent routing algorithms to improve the efficiency and effectiveness of optimizing chip routing.The chip routing problem is a NP-hard problem with multiple objectives and constraints.Even with decades of research history,there are still a large number of problems and spaces for breakthrough.As manufacturing techniques evolve,design rules,constraints and objectives are continuously adjusted and added,which make wiring selection extremely difficult.This survey aims to provide a comprehensive overview and analysis of the cutting-edge research on automated routing in the chip design automation,in order to help researchers fully understand the research progresses and directions in this field,and to accelerate the research and development of intelligent routing algorithms.Specifically,this paper first describes the background of chip routing,then introduces the definitions and objectives,process characteristics,difficulties and challenges,and evaluation methods of global and detailed routing respectively,followed by a detailed description and analysis of various routing methods,focusing on the latest research results,advantages and disadvantages of planning and search-based routing methods and machine learning-based routing approaches and their application aspects,then introduces public data sets and open-source routing tools,and finally summarizes the limitations of existing methods in practical applications and provides an outlook on future trends and potential research directions for automated routing.

关 键 词：机器学习 智能规划 强化学习 芯片 布线 全局布线 详细布线 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TN40[自动化与计算机技术—控制科学与工程]