引用本文

周展文, 卓汉逵. 芯片智能布线方法研究综述. 自动化学报, 2024, 50(9): 1671−1703 doi: 10.16383/j.aas.c230368

Zhou Zhan-Wen, Zhuo Han-Kui. Survey on intelligent routing approaches for chips. Acta Automatica Sinica, 2024, 50(9): 1671−1703 doi: 10.16383/j.aas.c230368

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c230368

关键词

机器学习，智能规划，强化学习，芯片，布线，全局布线，详细布线 

摘要

布线是芯片设计自动化流程中至关重要且特别耗时的一环, 直接影响最终产品的面积、成本、功耗、速度和可靠性, 研究智能布线算法对提高芯片布线效率和优化芯片布线效果具有重要意义. 芯片布线问题是一个多目标、多约束的NP困难问题. 即使已有几十年的研究历史, 目前仍存在大量未突破的问题和空间. 随着制造工艺的不断发展, 布线规则、约束和目标也持续调整和增加, 使得布线选择极其困难. 因此, 对芯片设计自动化中自动布线的前沿研究进行了全面归纳与分析, 以帮助科研人员全面了解该领域的研究进展和方向, 助力智能布线算法的研究和发展. 具体而言, 首先阐述芯片布线的问题背景, 然后分别介绍全局布线(Global routing, GR) 和详细布线(Detailed routing, DR)的任务定义和目标、过程特点、难点和挑战、评估方法; 接着详述和分析各布线方法, 重点论述基于规划搜索的布线方法和基于机器学习的布线方法的最新研究成果、优缺点及其应用环节; 然后介绍公开数据集和开源布线工具; 最后总结现有方法在实际应用中存在的局限性, 并对自动布线未来的发展趋势和潜在研究方向进行展望.

文章导读

芯片, 是信息产业的核心部件. 一颗芯片从无到有、从市场需求到最终应用, 大致可以分为设计、制造、封装、测试四个主要环节. 其中, 芯片设计是将系统、逻辑和性能的设计要求转化为具体物理版图的过程. 芯片设计周期长、过程复杂, 对设计人员专业程度要求高, 往往需要借助电子设计自动化(Electronic design automation, EDA)工具完成. 在芯片设计流程里, 通常只有在最后的物理验证、签核和测试阶段, 才能准确衡量设计在功率、性能和面积(Power, performance and area, PPA)方面的质量. 因此, 在设计的早期阶段对PPA的准确估算可以减少设计迭代次数, 增加设计的可靠性, 提高最终芯片的质量. 其中, 布线是芯片设计自动化流程中至关重要也是特别耗时的一环, 能否按照设计需求将所有线网布通是决定芯片能否流片的首要前提, 布线结果的好坏直接影响最终产品的面积、成本、功耗、速度和可靠性. 

芯片布线问题是一个多约束、多目标和多任务的NP困难问题, 即使对于相对简单的布线问题. 如斯坦纳最小树问题(Steiner minimum tree problem, SMTP), 即在没有障碍物和设计规则约束的情况下为一层中一个包含多个终端(Terminal)的线网(Net)寻找连接所有端点的最短路线, 不同于最小生成树(Minimum spanning tree, MST)问题可以有O(nlogn)时间复杂度算法, SMTP问题如果允许通过任意角度连线, 则为NP-hard[1]; 如果仅允许水平和垂直连线, 则为NP-complete[2]. 除此之外, 布线过程还需要解决拥塞避让、线网排序、引脚连接点分析、轨道分配、设计规则检查(Design rule checking, DRC)等各种困难问题. 

因布线问题复杂、规模庞大, 布线过程一般分为全局布线(Global routing, GR)和详细布线(Detailed routing, DR)[3-4]. 全局布线做全局规划生成布线指导, 在保证关键路径时延前提下, 分散走线, 避免局部拥塞, 从而提高详细布线的成功率; 详细布线在布线指导指引下完成具体走线, 满足设计规则检查, 并使总线长尽可能短, 通孔尽可能少. 虽然布线研究已有几十年历史, 产生了迷宫布线(Maze routing)、通道布线(Channel routing)、四边通道布线(Switchbox routing)、拥塞协商布线(Negotiated-congestion routing)、并行布线(Parallel routing)、基于学习的布线(Learning-based routing)等大量非常智能且有效的布线算法, 推动着EDA自动布线技术的发展. 但现有算法中仍然存在大量可研究问题和未突破空间, 如庞大布线搜索空间下布线时长与布线质量的优化与平衡、线网选取与实际走线之间的微妙关系、布线经验沉淀与数据利用等, 都具有相当大的难度和非常高的研究价值. 随着信息技术和制造工艺的不断发展, 芯片晶体管密度不断提高, 各类应用对芯片的要求也越来越高, 使得布线规则、约束和目标不断调整和增加: 压缩体积、降低功耗、消除拥塞、优化时序、减少耦合效应、消除串扰、保证信号完整性等, 这一长串经常相互冲突的目标使布线选择极其困难. 因此, 研究智能布线算法对提高芯片布线效率和优化芯片布线效果具有重要意义, 部分研究问题的解决方案甚至能够推广到其他组合优化问题上. 在技术应用上, 研究智能布线算法可沉淀布线知识和经验, 提高布线质量和产品可靠性, 加快芯片和电子产品的上市速度. 特别是在硅材料芯片因工艺制程极限约束逐步往多层架构方向发展, 以及如何将人工智能(Artificial intelligence, AI)应用于AI芯片设计并加快产品产量上, 智能布线都具有非常高的研究意义和应用价值. 从国家战略上, EDA工具是芯片设计、制造、封装、测试等阶段的必备工具, 在当前复杂多变的国际国内形势下, 必须拥有一批自主可控的EDA工具与企业, 以避免在芯片设计环节被“卡脖子”, 已经成为国家和行业共识. 研究智能布线算法和技术可弥补我国在EDA工具研发上的部分空白, 且从布线这一芯片后端设计的核心环节上进行突破能加速竞争力的形成. 

目前国内外的有关综述[5-7]大多探讨机器学习(Machine learning, ML)方法在EDA流程各环节中的应用. 部分综述[8-9]同时探讨超大规模集成电路(Very large scale integration, VLSI)的布局和布线方法, 尚无针对芯片布线全面而细致的综述文献. 文献[10]只综述了VLSI全局布线和斯坦纳树构建的主要挑战和相关基于规划搜索的布线算法. 文献[11]将布线问题抽象为图搜索问题或多商品流问题, 分别介绍了基于迷宫或A* 搜索、整数线性规划以及并行加速技术的VLSI详细布线算法的最新研究进展, 但缺少对全局布线的探讨, 对机器学习类布线算法的研究和分析亦不够深入. 文献[12]仅从布线违例预测、布线优化、智能布线三个维度综述了机器学习类算法在VLSI布线中的应用案例, 缺少从全局布线和详细布线的特点和环节出发归纳机器学习算法的应用框架, 缺乏对传统布线工具和机器学习算法的差异对比和融合方式的思考. 文献[13]则专注于近期VLSI布线中的挑战和布线方法, 包括GPU (Graphics processing unit)加速布线、信号速度优化、印制电路板(Printed circuit board, PCB)布线和AI驱动的模拟电路布线. 本文对芯片设计自动化中布线方法进行全面综述, 旨在帮助研究人员对该领域的任务设置、主流方法、评价体系、开源工具等方面有系统性的了解, 便于快速进入该领域. 本文关注各布线方法间的共性与不同, 按照问题导向逐步介绍其发展脉络, 着重介绍规划搜索类算法在VLSI和现场可编程门阵列(Field programmable gate array, FPGA)布线的最新研究成果, 剖析机器学习类算法在元件布局优化、全局布线和详细布线各环节的框架设计、应用效果、与传统算法的融合思路, 以及现有开源环境的支撑, 并结合领域研究现状对未来发展趋势进行展望, 希望帮助研究者们开拓思路, 助力智能布线算法的研究和发展. 

本文主要内容的框架如图1所示. 

图 1  本文主要内容框架

本文后续内容组织如下: 第1节首先介绍全局布线和详细布线的问题背景和定义, 分析研究难点与挑战, 然后介绍芯片智能布线方法的发展历程; 第2节首先简述基础的单线网和多线网布线方法, 接着面向VLSI布线和FPGA布线分别介绍基于规划搜索的智能布线方法的最新研究成果; 然后在第3节着重讲述近年主流的基于机器学习的智能布线方法, 按照方法的应用环节和设计原理进行归纳与分析; 第4节介绍常用的公开数据集与开源布线工具; 第5节分析了智能布线研究的现状与局限性, 并对未来发展趋势与潜在研究方向进行展望; 第6节是文章的总结与展望. 

图 2  3D网格空间与线网布线

图 3  全局布线的三个步骤

布线是芯片设计自动化流程中至关重要也是特别耗时的一环, 直接影响最终产品的面积、成本、功耗、速度和可靠性. 芯片自动布线问题是一个多约束、多目标和多任务的NP困难问题. 布线问题规模庞大、任务复杂, 布线环境千差万别, 设计规则约束随着技术发展不断提升, 因此芯片布线一直是EDA领域炙手可热的研究问题之一. 本文对该领域的任务定义、研究难点、布线方法、常用公开数据集、评价指标等进行了综合梳理, 重点综述了规划搜索类算法在VLSI和FPGA布线的最新研究成果, 剖析了机器学习类算法在元件布局优化、全局布线和详细布线各环节的框架设计、应用效果, 以及与传统算法的融合思路. 

在未来相当长的一段时间内, 基于规划搜索的智能布线方法仍将是重要的研究方向, 特别是多核并行布线技术. 虽然现有的学习类布线器仍无法超越或是接近传统布线器, 但学习类布线算法的研究时间远比传统算法短, 仍可期待后续的突破. 随着技术的进步, 集成机器学习来解决布线问题是一个明显的趋势. 在此发展过程中, 将不再为了应用机器学习而将先进的技术引入到布线问题中, 而是期待开发适合布线问题特点的机器学习方法. 

机器学习方法在半导体行业中正实践着一个正反馈的循环, 它的出现加速了芯片的迭代过程; 反之, 芯片的迭代也促进了机器学习方法的性能提升, 正逐步实现“用摩尔定律来加速摩尔定律”的这个愿景, 更好地支撑万物互联、万物智能时代的应用需求. 

作者简介

周展文

中山大学计算机学院博士研究生. 主要研究方向为芯片布线, 智能规划, 机器学习和强化学习. E-mail: zhouzhw26@mail2.sysu.edu.cn

卓汉逵

中山大学计算机学院副教授. 主要研究方向为智能规划, 机器学习, 人工智能. 本文通信作者. E-mail: zhuohank@mail.sysu.edu.cn