2.765

2022影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

周展文 卓汉逵

周展文, 卓汉逵. 芯片智能布线方法研究综述. 自动化学报, xxxx, xx(x): x−xx doi: 10.16383/j.aas.c230368
引用本文: 周展文, 卓汉逵. 芯片智能布线方法研究综述. 自动化学报, xxxx, xx(x): x−xx doi: 10.16383/j.aas.c230368
Zhou Zhan-Wen, Zhuo Han-Kui. Survey on intelligent routing approaches for chips. Acta Automatica Sinica, xxxx, xx(x): x−xx doi: 10.16383/j.aas.c230368
Citation: Zhou Zhan-Wen, Zhuo Han-Kui. Survey on intelligent routing approaches for chips. Acta Automatica Sinica, xxxx, xx(x): x−xx doi: 10.16383/j.aas.c230368

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

doi: 10.16383/j.aas.c230368
基金项目: 国家基金面上项目(62076263), 广东省杰出青年项目(2017A030306028), 广东省“特支计划”青年拔尖人才计划(2017TQ04X866)资助
详细信息
    作者简介:

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

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

Survey on Intelligent Routing Approaches for Chips

Funds: Supported by National Natural Science Foundation of China (62076263), Guangdong Natural Science Funds for Distinguished Young Scholar (2017A030306028), and Guangdong special branch plans young talent with scientific and technological innovation (2017TQ04X866)
More Information
    Author Bio:

    ZHOU Zhan-Wen Ph.D. candidate at the School of Computer Science and Engineering, Sun Yat-sen University. His research interest covers chip routing, automated planning, machine learning and reinforcement learning

    ZHUO Han-Kui Associate professor at the School of Computer Science and Engineering, Sun Yat-sen University. His research interest covers automated planning, machine learning and artificial intelligence. Corresponding author of this paper

  • 摘要: 布线是芯片设计自动化流程中至关重要也是特别耗时的一环, 直接影响最终产品的面积、成本、功耗、速度和可靠性, 研究智能布线算法对提高芯片布线效率和优化芯片布线效果具有重要意义. 芯片布线问题是一个多目标、多约束的NP困难问题. 即使已有几十年的研究历史, 目前仍存在大量未突破的问题和空间. 随着制造工艺的不断发展, 布线规则、约束和目标也持续调整和增加, 使得布线选择极其困难. 本文旨在对芯片设计自动化中自动布线的前沿研究进行全面归纳与分析, 以帮助科研人员全面了解该领域的研究进展和方向, 助力智能布线算法的研究和发展. 具体而言, 本文首先阐述芯片布线的问题背景, 然后分别介绍全局布线和详细布线的任务定义和目标、过程特点、难点和挑战、评估方法; 接着详述和分析各布线方法, 重点论述基于规划搜索的布线方法和基于机器学习的布线方法的最新研究成果、优缺点及其应用环节; 然后介绍公开数据集和开源布线工具; 最后总结现有方法在实际应用中存在的局限性, 并对自动布线未来的发展趋势和潜在研究方向进行展望.
    1)  11 LEF/DEF Language Reference version 5.7, https://www.ispd.cc/contests/18/lefdefref.pdf
    2)  22 Guelph FPGA CAD Group, http://fpga.socs.uoguelph.ca/
    3)  33 TritonRoute, UCSD Detailed Router, https://github.com/The-OpenROAD-Project/TritonRoute4 CUGR, VLSI Global Routing Tool Developed by CUHK, https://github.com/cuhk-eda/cu-gr5 Dr.CU, VLSI Detailed Routing Tool Developed by CUHK, https://github.com/cuhk-eda/dr-cu6 EDA-AI, https://github.com/Thinklab-SJTU/EDA-AI7 Verilog to Routing, Open Source CAD Flow for FPGA Research, https://github.com/verilog-to-routing/vtr-verilog-to-routing
  • 图  1  本文的主要内容框架

    Fig.  1  The main content framework of this paper

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

    Fig.  2  3D grid graph for net routing

    图  3  全局布线的三个步骤

    Fig.  3  Three steps of global routing

    图  4  详细布线的四个步骤

    Fig.  4  Four steps of detailed routing

    图  5  常见的设计间距约束

    Fig.  5  Representative design spacing constrains

    图  6  芯片智能布线方法的发展历程

    Fig.  6  Evolution of intelligent chip routing approaches

    图  7  粗化-反粗化多级布线方法框架

    Fig.  7  Coarsening-uncoarsening multilevel routing framework

    图  8  布线流程图

    Fig.  8  Routing procedures

    图  9  三维转二维全局布线流程: 投影-布线-层分配

    Fig.  9  3D to 2D global routing process: projection - routing - layer assignment

    图  10  基于队列的拆线重布操作过程[89]

    Fig.  10  Queue-based ripup and reroute process[89]

    图  11  全局详细布线器框架

    Fig.  11  Global-detailed routing framework

    图  12  多核分布式内存并行布线框架

    Fig.  12  Multi-core distributed memory parallel routing framework

    图  13  基于机器学习的布线过程

    Fig.  13  Machine learning-based routing process

    图  14  基于布局信息的布线违例预测框架[126]

    Fig.  14  Design rule violation prediction framework based on placement information[126]

    图  15  基于深度强化学习的线长和短路违例预测与布局规划模型[139]

    Fig.  15  Wirelength and short circuit violation prediction and floor planning model based on deep reinforcement learning[139]

    图  16  A*搜索指导的强化学习全局布线流程[148]

    Fig.  16  Global routing based on A* search-guided reinforcement learning[148]

    图  17  线网排序强化学习框架中的策略网络模型和价值网络模型[152]

    Fig.  17  Policy network and value network in reinforcement learning framework of net ordering[152]

    图  18  基于多智能体强化学习的详细布线框架[156]

    Fig.  18  Detailed routing framework based on multi-agent reinforcement learning[156]

    表  1  智能布线方法的特点和应用阶段

    Table  1  Characteristics and application phases of intelligent routing approaches

    类型 布线方法 方法过程和特点 布线阶段
    规划搜索类 迷宫布线 从一个引脚点出发, 采用广度优先搜索技术, 找出存在障碍的网格中另一引脚点的曼哈顿最短路径, 然后以已经连接好的路径为起点, 用同样的方法寻找下一个引脚点, 直到连接完线网的所有引脚. GR/DR
    线搜索布线 首先将源和目标设置为基点, 向四个方向(两个水平和两个垂直)执行深度优先搜索, 一直延伸到芯片边界或障碍物, 生成0级线段. 然后, 将这些第$ i $级线段的每个网格点设置为新的基点, 生成第$ i+1 $级的垂直线段. 这个过程不断重复, 直到从源生成的线段与从目标生成的线段相交, 通过交叉点跟踪到源和目标来找到它们的连接路径. GR/DR
    通道布线 在一个包含水平和垂直多条布线轨道的横向布线区域, 线网引脚分布在顶端和底部, 布线时构建水平约束图和垂直有向约束图, 利用贪婪算法和遗传算法等方法将不同线网的横边分配到合适的轨道上, 以减少轨道占用, 压缩通道宽度. DR
    A*搜索布线算法 一般以连线长度、通孔成本和违例成本为权重的曼哈顿距离作为启发式函数, 利用A*算法连接存在障碍的网格中的两个引脚点. 然后以已经连接好的路径为起点, 选择离已连线引脚的中心最近的引脚作为下一个目标点, 直到连接完线网的所有引脚. GR/DR
    模式布线 对每一个双引脚线网, 只考虑L, Z, U, T, E等几种形状的连接方式, 能快速找到最短连接方案, 可用于全局布线或者详细布线的首次迭代. GR/DR
    整数线性规划布线 网表中每个线网通过L型或Z型找出多个可选路径方案, 并按照成本给每个方案一个权重, 在满足每个线网只选择一个方案, 且所有线网的路径方案所使用的边不超过其容量前提下, 最小化所有方案的成本和. GR
    拥塞协商 多线网布线时以协商的方式确定各线网间互联资源的分配, 迭代地进行拆线重布, 初始时所有线网都用最小代价完成布线, 逐渐加大对多个线网重复使用的互连资源或者设计规则违例区域的惩罚力度, 经过多次迭代后, 基于拥塞协商的布线能快速地分散拥塞, 避免冲突和溢出. GR/DR
    多级布线 用动态规划的思想将芯片逐级划分到更小区域, 直到能够被算法处理为止, 部分线网因而被切割成多段, 待下级区域内布线完成后再向上串连各段线网, 最终输出完整的布线方案. GR/DR
    查表布线 对于少于一定数量(如10个)引脚的线网, 先预先构建并存储好直线斯坦纳最小树的所有可能连接方案, 在实际布线时通过查表的方式快速确认方案的可行性; 对于大线网则通过线网拆分技术将其拆成多个小线网, 单独查表布线后再汇总连接. GR
    并行布线 将布线区域进行切割或者将非重叠线网划分到不同的分组, 通过布线任务调度和多线程并行布线实现加速, 提高布线效率. GR/DR
    机器学习类 拥塞与违例预测 利用卷积神经网络等深度学习框架, 基于芯片布局和引脚密度等信息生成拥塞热图, 或者基于全局布线产生的拥塞报告, 预测给定设计的详细布线所产生的设计规则违例位置, 指导布线路径优化. GR/DR
    布线路径生成 利用收集的布线方案进行对抗学习, 通过生成模型生成线网的全局布线方案, 并根据预估线长和拥塞结果指导宏布局和线网排序. GR
    强化学习布线 基于强化学习算法框架, 训练布线智能体完成线网排序、路径选择、违例修复等任务. GR/DR
    多智能体布线 将芯片布线转化为多智能体路径规划任务, 基于多智能体深度强化学习框架训练多智能体并行布线, 利用智能体之间的异步通信来避免布线冲突. GR/DR
    下载: 导出CSV

    表  2  VLSI详细布线方法

    Table  2  Detailed routing approaches for VLSI

    布线任务 文献(年份) 方法特点 数据集
    引脚连接点分析 Nieberg [69] (2011) 选择从引脚到网格点不违反设计规则的最短路径. Foundry
    Xu等[70] (2016) 基于引脚访问点数量来动态评估引脚可达性. OpenSparc T1 *
    Kahng等[72] (2020) 设计规则感知的基于动态规划的引脚连接点分析框架. ISPD18[19]
    轨道分配 Zhang等[75] (2012) 基于最大加权独立集问题启发式求解的轨道分配算法. ISPD98[76]&ISPD05[77]&ISPD06[78]
    Wong等[79] (2016) 基于协商的轨道分配算法. DAC12[80]
    Liu等[81] (2019) 可布线性驱动的轨道分配算法. DAC12[80]
    Guo等[82] (2019) 基于离散粒子群优化、遗传操作和基于协商的精炼策略的轨道分配算法. DAC12[80]
    基于网格的并行布线 Jia等[83] (2017) 基于多商品流方法的并行布线算法. Foundry&ISPD05[77]&ISPD14[85]
    Kahng等[86] (2018) 通过混合整数线性规划逐层进行并行布线. ISPD18[19]
    基于网格的顺序布线 Sun等[87] (2018) 考虑全局指导的基于协商的并行布线方法. ISPD18[19]
    Kahng等[89] (2021) 基于队列的拆线重布算法以减少违例, 用全新的设计规则分析引擎准确计算路径成本. ISPD18[19]&ISPD19[20]
    Chen等[90] (2019) 分层并行迷宫布线方法实现总线布线. ICCAD18 **
    Li等[92] (2019) 边构造边修正的路径优化并行搜索方法降低设计规则违例的数量. ISPD18[19]&ISPD19[20]
    Zhuang等[93] (2022) 设计规则驱动的轨道分配和违例优化方法. ISPD19[20]
    无网格布线 Cong等[94] (2005) 基于多级布线框架的无网格布线器. Foundry
    Li等[95] (2007) 结合瓦片展开和隐式连接图的多层无网格布线器. Foundry
    光刻工艺友好的布线 Du等[96] (2013) 基于符合SID (Spacer-Is-Dielectric)型自对准双重成像设计约束的图模型的拥塞协商详细布线. Foundry
    Ding等[97] (2015) 基于符合SIM (Spacer-Is-Metal)型自对准双重成像和自对准四重成像设计约束的图模型的拥塞协商详细布线. Generated
    Ou等[98] (2017) 基于DSA (Directed Self Assembly)光刻工艺友好的图模型的详细布线. OpenSparc T1 *
    Yu等[99] (2018) 考虑DSA光刻工艺的基于冲突和兼容性图模型的详细布线. Foundry
    * OpenSPARC T1, http://www.oracle.com/technetwork/systems/opensparc/index.html
    ** ICCAD 2018 Contest Problem B: Obstacle-Aware On-Track Bus Routing, http://iccad-contest.org/2018/problems.html
    下载: 导出CSV

    表  3  基于元件布局优化的布线方法

    Table  3  Routing approaches for placement optimization

    任务类型 算法框架 文献(年份) 芯片类型 数据集
    可布线性预测SVNChan等[124] (2017)VLSIFoundry
    NNTabrizi等[125126] (2019, 2018)VLSIISPD15[127]
    CNNYu等[128] (2019)VLSIGenerated
    CNNLiang等[129] (2020)VLSIFoundry
    CNNXie等[130]、Huang等[131] (2019)VLSIISPD15[127]
    CNNChen等[132] (2022)VLSIFoundry&DAC12[80]
    CNNAlhyari等[133134] (2021, 2019)FPGAISPD16[113]&Xilinx
    cGANAlawieh等[135] (2020)、Yu等[136] (2019)FPGAISPD16[113]
    LHNNWang等[137] (2022)VLSIISPD11[138]&DAC12[80]
    布局规划优化RL+GCNMirhoseini等[139] (2021)VLSIFoundry&Ariane[140]
    布局布线融合RL+GNN+CNNCheng等[141142] (2021, 2022)VLSIISPD05[77]
    下载: 导出CSV

    表  4  基于全局布线优化的布线方法

    Table  4  Routing approaches for global routing optimization

    任务类型 算法框架 文献(年份) 芯片类型 数据集
    拥塞预测CNNHung等[143] (2020)VLSIFoundry
    CNNSu等[144] (2022)VLSIICCAD19[61]
    斯坦纳树构建VAEUtyamishev等[145146] (2022, 2020)VLSIISPD98[76]
    RLLiu等[33] (2021)VLSIICCAD19[61]
    走线选择RLGandhi等[147] (2020)VLSIISPD18[19]
    RLLiao等[148] (2020)VLSIGenerated
    下载: 导出CSV

    表  5  基于详细布线优化的布线方法

    Table  5  Routing approaches for detailed routing optimization

    任务类型 算法框架 文献(年份) 芯片类型 数据集
    违例预测与修复RLGandhi等[14] (2019)VLSIGenerated
    RLRen等[149] (2021)VLSIFoundry
    Random-ForestSiddiqi等[150] (2022)FPGAVTR7[151]
    线网排序RLLin等[152] (2022), Qu等[153] (2021)VLSIISPD18[19]&ISPD19[20]
    走线选择MCTS+RLHe等[15] (2022)VLSIGenerated
    RLLiao等[154] (2020)VLSIFoundry
    RLChen等[155] (2023)VLSIFoundry
    异步并行布线MARLJu等[156] (2021)VLSIGenerated
    下载: 导出CSV

    表  6  芯片布线常用公开数据集

    Table  6  Public datasets commonly used for chip routing

    类型 数据集 测试用例 方法过程和特点 方法特点
    全局布线 ISPD-2007[17] 16个 8个单层和8个6~8层测试用例, 多层用例线网数量从176 715个到548 073个不等. 溢出数、总线长
    ISPD-2008[18] 16个 在ISPD-2007多层用例基础上再增加8个6~8层测试用例, 线网数量从176 715个到1 647 410个不等. 溢出数、总线长、运行时长
    ICCAD-2019[61] 12个 从ISPD-2018和ISPD-2019数据集中选取了6个32 nm的测试用例, 通过限制用例层数为5层, 形成额外的6个用例. 将全局布线输出的布线指导导入Dr.CU[91]并评估详细布线后的设计规则违例数、通孔数、总线长、运行时长
    ICCAD-2020[67] 12个 3~16层, GCell数量最大为277×277, 线网数量从6个到332 080个不等. 零溢出、零开路、最大单元移动限制、1小时运行时长限制
    ICCAD-2021[68] 10个 3~16层, GCell数量最大为277×277, 线网数量从6个到332 063个不等. 零溢出、零开路、电压区域限制、最大单元移动限制、1小时运行时长限制
    详细布线 ISPD-2018[19] 10个 45 nm到32 nm, 9层, 线网数量从3 153个到182 000个. 设计规则违例数、通孔数、总线长、运行时长
    ISPD-2019[20] 10个 65 nm到32 nm, 5~9层, 线网数量从3 153个到895 253个. 设计规则违例数、通孔数、总线长、运行时长
    FPGA布线 VPR[151] 19个 来源于多款应用芯片, 六输入查找表数量从174到107 784. 总线长、关键路径延时
    Titan[157] 23个 来源于多款应用芯片, 六输入查找表数量从24 759到805 063, 原语数量从90 778到1 859 485. 总线长、关键路径延时
    下载: 导出CSV

    表  7  芯片智能布线方法的对比分析

    Table  7  Comparison and analysis of intelligent routing approaches

    线网数量 方法类型 布线方法 布线阶段 布线效率 布线质量 CPU/GPU要求 内存要求 布线规模 数据要求
    单线网 规划搜索类 迷宫布线 GR/DR
    线搜索布线 GR/DR
    A*搜索布线算法 GR/DR
    模式布线 GR/DR
    查表布线 GR
    机器学习类 布线路径生成 GR
    强化学习布线 GR/DR
    多线网 规划搜索类 贪心通道布线 DR
    整数线性规划布线 GR
    拥塞协商 GR/DR
    多级布线 GR/DR
    并行布线 GR/DR
    机器学习类 拥塞与违例预测 GR/DR
    多智能体布线 GR/DR
    下载: 导出CSV
  • [1] Karp R M. Reducibility among combinatorial problems. In: Proceedings of a Symposium on the Complexity of Computer Computations. IBM Thomas J. Watson Center, Yorktown Heights, New York, USA: 1972. 85−103
    [2] Garey M R, Johnson D S. The rectilinear steiner tree problem is np-complete. SIAM Journal on Applied Mathematics, 1977, 32(4): 826−834 doi: 10.1137/0132071
    [3] Chen H Y, Chang Y W. Global and detailed routing. Electronic Design Automation, Elsevier, 2009. 687−749
    [4] Sherwani N A. Algorithms for VLSI physical design automation. Springer Science & Business Media, 2012
    [5] Huang G Y, Hu J B, He Y F, Liu J L, Ma M Y, Shen Z Y, et al. Machine learning for electronic design automation: A survey. ACM Transactions on Design Automation of Electronic Systems (TODAES), 2021, 26(5): 1−46
    [6] Loper D S, Servadei L, Kiprit G N, Hazra S, Wille R, Ecker W. A survey of graph neural networks for electronic design automation. In: Proceedings of the 2021 ACM/IEEE 3rd Workshop on Machine Learning for CAD (MLCAD). Raleigh, NC, USA: IEEE, 2021. 1−6
    [7] Gubbi K I, Beheshti-Shirazi S A, Sheaves T, Salehi S, PD S M, Rafatirad S, et al. Survey of machine learning for electronic design automation. In: Proceedings of the Great Lakes Symposium on VLSI 2022. New York, USA: 2022. 513−518
    [8] 田春生, 陈雷, 王源, 王硕, 周婧, 张瑶伟, 等. 面向fpga的布局与布线技术研究综述. 电子学报, 2022, 50(5): 1243−1254

    Tian Chun-Sheng, Chen Lei, Wang Yuan, Wang Shuo, Zhou Jing, Zhang Yao-Wei, et al. Review on technology of placement and routing for the fpga. Acta Electronica Sinica, 2022, 50(5): 1243−1254
    [9] Yan J C, Lyu X L, Cheng R Y, Lin Y B. Towards machine learning for placement and routing in chip design: a methodological overview. arXiv preprint arXiv: 2202.13564, 2022
    [10] Tang H, Liu G G, Chen X H, Xiong N X. A survey on steiner tree construction and global routing for vlsi design. IEEE Access, 2020, 8: 68593−68622 doi: 10.1109/ACCESS.2020.2986138
    [11] 屈通, 盖天洋, 王书涵, 苏晓菁, 粟雅娟, 韦亚一. Vlsi详细布线算法研究进展. 微电子学与计算机, 2021, 38(11): 1−6

    Qu Tong, Gai Tian-Yang, Wang Shu-Han, Su Xiao-Jing, Su Ya-Juan, Wei Ya-Yi. Research progress of vlsi detailed routing algorithm. Microelectronics & Computer, 2021, 38(11): 1−6
    [12] Li L, Cai Y C, Zhou Q. A survey on machine learning-based routing for vlsi physical design. Integration, 2022, 86: 51−56 doi: 10.1016/j.vlsi.2022.05.003
    [13] Posser G, Young E F Y, Held S, Li Y L, Pan D Z. Challenges and Approaches in VLSI Routing. In: Proceedings of the 2022 International Symposium on Physical Design. 2022. 185−192
    [14] Gandhi U, Bustany I, Swartz W, Behjat L. A reinforcement learning-based framework for solving physical design routing problem in the absence of large test sets. In: Proceedings of the 2019 ACM/IEEE 1st Workshop on Machine Learning for CAD (MLCAD). Canmore, AB, Canada: IEEE, 2019. 1−6
    [15] He Y B, Li H B, Jin T, Bao F S. Circuit routing using monte carlo tree search and deep reinforcement learning. In: Proceedings of the 2022 International Symposium on VLSI Design, Automation and Test (VLSI-DAT). Hsinchu, Taiwan: IEEE, 2022. 1−5
    [16] 陈春章, 艾霞, 王国雄. 数字集成电路物理设计, 2008

    Chen Chun-Zhang, Ai Xia, Wang Guo-Xiong. Physical design of digital integrated circuits, 2008
    [17] Nam G J, Yildiz M, Pan D Z, Madden P H. Ispd placement contest updates and ispd 2007 global routing contest. In: Proceedings of the 2007 international symposium on Physical design. 2007. 167−167
    [18] Nam G J, Sze C, Yildiz M. The ispd global routing benchmark suite. In: Proceedings of the 2008 international symposium on Physical design. 2008. 156−159
    [19] Mantik S, Posser G, Chow W K, Ding Y X, Liu W H. Ispd 2018 initial detailed routing contest and benchmarks. In: Proceedings of the 2018 International Symposium on Physical Design. 2018. 140−143
    [20] Liu W H, Mantik S, Chow W K, Ding Y X, Farshidi A, Posser G. Ispd 2019 initial detailed routing contest and benchmark with advanced routing rules. In: Proceedings of the 2019 International Symposium on Physical Design. 2019. 147−151
    [21] Lee C Y. An algorithm for path connections and its applications. IRE transactions on electronic computers, 1961(3): 346−365
    [22] Hadlock F O. A shortest path algorithm for grid graphs. Networks, 1977, 7(4): 323−334 doi: 10.1002/net.3230070404
    [23] Soukup J. Fast maze router. In: Proceedings of the 15th Design Automation Conference. IEEE Computer Society, 100−101
    [24] Mikami K. A computer program for optimal routing of printed circuit connections. In: Proceedings of the International Federation for Information Processing (IFIP). 1968. 47 : 1475−1478
    [25] Hightower D W. A solution to line-routing problems on the continuous plane. In: Proceedings of the 6th annual Design Automation Conference. 1969. 1−24
    [26] Hetzel A. A sequential detailed router for huge grid graphs. In: Proceedings of the Design, Automation and Test in Europe. Paris, France: IEEE, 1998. 332−338
    [27] Dijkstra E W. A note on two problems in connexion with graphs. Edsger Wybe Dijkstra: His Life, Work, and Legacy, 2022287−290
    [28] Hart P E, Nilsson N J, Raphael B. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 1968, 4(2): 100−107 doi: 10.1109/TSSC.1968.300136
    [29] Clow G W. A global routing algorithm for general cells. In: Proceedings of the 21st Design Automation Conference. IEEE, 1984. 45−51
    [30] Mcmurchie L, Ebeling C. PathFinder: A negotiation-based performance-driven router for fpgas. In: Proceedings of the 1995 ACM 3rd International Symposium on Field-Programmable Gate Arrays. 1995. 111−117
    [31] Yang Y, Wing O. Suboptimal algorithm for a wire routing problem. IEEE Transactions on Circuit Theory, 1972, 19(5): 508−510 doi: 10.1109/TCT.1972.1083538
    [32] Lee J, Bose N, Hwang F. Use of steiner’s problem in suboptimal routing in rectilinear metric. IEEE Transactions on Circuits and Systems, 1976, 23(7): 470−476 doi: 10.1109/TCS.1976.1084243
    [33] Liu J W, Chen G J, Young E F Y. Rest: Constructing rectilinear steiner minimum tree via reinforcement learning. In: Proceedings of the 2021 58th ACM/IEEE Design Automation Conference (DAC). San Francisco, CA, USA: IEEE, 2021. 1135−1140
    [34] Chu C, Wong Y C. Flute: Fast lookup table based rectilinear steiner minimal tree algorithm for vlsi design. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2007, 27(1): 70−83
    [35] Ho J M, Vijayan G, Wong C K. New algorithms for the rectilinear steiner tree problem. IEEE transactions on computer-aided design of integrated circuits and systems, 1990, 9(2): 185−193 doi: 10.1109/43.46785
    [36] Chen H M, Wong M D, Zhou H, Young E F Y, Yang H H, Sherwani N. Integrated floorplanning and interconnect planning. Layout optimization in VLSI design, 20011−18
    [37] Kastner R, Bozorgzadeh E, Sarrafzadeh M. Pattern routing: Use and theory for increasing predictability and avoiding coupling. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2002, 21(7): 777−790 doi: 10.1109/TCAD.2002.1013891
    [38] Deutsch D N. A ``Dogleg'' channel router. In: Proceedings of the 13th Design Automation Conference. 1976. 425−433
    [39] Burstein M, Pelavin R. Hierarchical wire routing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1983, 2(4): 223−234 doi: 10.1109/TCAD.1983.1270040
    [40] Li J T, Marek-Sadowska M. Global routing for gate array. IEEE transactions on computer-aided design of integrated circuits and systems, 1984, 3(4): 298−307 doi: 10.1109/TCAD.1984.1270088
    [41] Lin S P, Chang Y W. A novel framework for multilevel routing considering routability and performance. In: Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design. San Jose, CA, USA: 2002. 44−50
    [42] Chang Y W, Lin S P. Mr: A new framework for multilevel full-chip routing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2004, 23(5): 793−800 doi: 10.1109/TCAD.2004.826547
    [43] Vannelli A. An adaptation of the interior point method for solving the global routing problem. IEEE transactions on computer-aided design of integrated circuits and systems, 1991, 10(2): 193−203 doi: 10.1109/43.68406
    [44] Cho M, Pan D Z. Boxrouter: A new global router based on box expansion and progressive ilp. In: Proceedings of the 43rd annual Design Automation Conference. 2006. 373−378
    [45] Wu T H, Davoodi A, Linderoth J T. Grip: Global routing via integer programming. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2010, 30(1): 72−84
    [46] Vecchi M P, Kirkpatrick S. Global wiring by simulated annealing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1983, 2(4): 215−222 doi: 10.1109/TCAD.1983.1270039
    [47] Shin H, Sangiovanni-Vincentell A. Mighty: a rip-up and reroute detailed router. In: Proceedings of the International Conference on Computer Aided Design. 1986. 2−5
    [48] Cho M, Lu K, Yuan K, Pan D Z. Boxrouter 2.0: A hybrid and robust global router with layer assignment for routability. ACM Transactions on Design Automation of Electronic Systems (TODAES), 2009, 14(2): 1−21
    [49] Moffitt M D. Maizerouter: Engineering an effective global router. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(11): 2017−2026 doi: 10.1109/TCAD.2008.2006082
    [50] Chen H Y, Hsu C H, Chang Y W. High-performance global routing with fast overflow reduction. In: Proceedings of the 2009 Asia and South Pacific Design Automation Conference. IEEE, 2009. 582−587
    [51] Xu Y, Zhang Y, Chu C. Fastroute 4.0: Global router with efficient via minimization. In: Proceedings of the 2009 Asia and South Pacific Design Automation Conference. IEEE, 2009. 576−581
    [52] Chang Y J, Lee Y T, Gao J R, Wu P C, Wang T C. Nthu-route 2.0: a robust global router for modern designs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2010, 29(12): 1931−1944 doi: 10.1109/TCAD.2010.2061590
    [53] Liu W H, Kao W C, Li Y L, Chao K Y. Nctu-gr 2.0: Multithreaded collision-aware global routing with bounded-length maze routing. IEEE Transactions on computer-aided design of integrated circuits and systems, 2013, 32(5): 709−722 doi: 10.1109/TCAD.2012.2235124
    [54] He J Y, Burtscher M, Manohar R, Pingali K. Sproute: A scalable parallel negotiation-based global router. In: Proceedings of the 2019 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). Westminster, CO, USA: IEEE, 2019. 1−8
    [55] Jiang Y J, Fang S Y. COALA: Concurrently Assigning Wire Segments to Layers for 2-D Global Routing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 42(2): 569−582
    [56] 刘耿耿, 李泽鹏, 郭文忠, 陈国龙, 徐宁. 面向超大规模集成电路物理设计的通孔感知的并行层分配算法. 电子学报, 2022, 50(11): 2575−2583

    Liu Geng-Geng, Li Ze-Peng, Guo Wen-Zhong, Chen Guo-Long, Xu Ning. Via-Aware Parallel Layer Assignment Algorithm for VLSI Physical Design. ACTA ELECTONICA SINICA, 2022, 50(11): 2575−2583
    [57] Roy J A, Markov I L. High-performance routing at the nanometer scale. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(6): 1066−1077 doi: 10.1109/TCAD.2008.923255
    [58] Ozdal M M, Wong M D. Archer: A history-based global routing algorithm. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2009, 28(4): 528−540 doi: 10.1109/TCAD.2009.2013991
    [59] Xu Y, Chu C. Mgr: Multi-level global router. In: Proceedings of the 2011 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). IEEE, 2011. 250−255
    [60] Liu J W, Pui C W, Wang F Z, Young E F Y. Cugr: Detailed-routability-driven 3d global routing with probabilistic resource model. In: Proceedings of the 2020 57th ACM/IEEE Design Automation Conference (DAC), San Francisco, CA, USA: IEEE, 2020. 1−6
    [61] Dolgov S, Volkov A, Wang L T, Xu B Q. 2019 cad contest: Lef/def based global routing. In: Proceedings of the 2019 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). Westminster, CO, USA: IEEE, 2019. 1−4
    [62] Liu S T, Pu Y, Liao P Y, Wu H Z, Zhang R, Chen Z T, et al. Fastgr: Global routing on cpu-gpu with heterogeneous task graph scheduler. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 42(7): 2317−2330
    [63] Fontana T A, Aghaeekiasaraee E, Netto R, Almeida S F, Gandh U, Tabrizi A F, et al. Ilp-based global routing optimization with cell movements. In: Proceedings of the 2021 IEEE Computer Society Annual Symposium on VLSI (ISVLSI). Tampa, FL, USA: IEEE, 2021. 25−30
    [64] Fontana T A, Aghaeekiasaraee E, Netto R, Almeida S F, Gandh U, Behjat L, et al. ILPGRC: ILP-Based Global Routing Optimization With Cell Movements. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2023
    [65] Zou P, Cai Z J, Lin Z F, Ma C Y, Yu J, Chen J L. Incremental 3D Global Routing Considering Cell Movement and Complex Routing Constraints. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 2016−2029
    [66] Zhu Z R, Shen F H, Mei Y J, Huang Z P, Chen J L, Yang J. A robust global routing engine with high-accuracy cell movement under advanced constraints. In: Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design. 2022. 1−9
    [67] Hu K S, Yang M J, Yu T C, Chen G C. Iccad-2020 cad contest in routing with cell movement. In: Proceedings of the 39th International Conference on Computer-Aided Design. 2020. 1−4
    [68] Hu K S, Yu T C, Yang M J, Shen C F. 2021 iccad cad contest problem b: Routing with cell movement advanced. In: Proceedings of the 2021 IEEE/ACM International Conference On Computer Aided Design (ICCAD). IEEE, 2021. 1−5
    [69] Nieberg T. Gridless pin access in detailed routing. In: Proceedings of the 48th Design Automation Conference. San Diego, CA, USA: 2011. 170−175
    [70] Xu X Q, Yu B, Gao J R, Hsu C L, Pan D Z. Parr: Pin-access planning and regular routing for self-aligned double patterning. ACM Transactions on Design Automation of Electronic Systems (TODAES), 2016, 21(3): 1−21
    [71] Xu X Q, Lin Y B, Livramento V, Pan D Z. Concurrent pin access optimization for unidirectional routing. In: Proceedings of the 54th Annual Design Automation Conference 2017. Austin, TX, USA: 2017. 1−6
    [72] Kahng A B, Wang L, Xu B Q. The tao of pao: Anatomy of a pin access oracle for detailed routing. In: Proceedings of the 2020 57th ACM/IEEE Design Automation Conference (DAC). San Francisco, CA, USA: IEEE, 2020. 1−6
    [73] Kahng A B, Kuang J, Liu W H, Xu B Q. In-route pin access-driven placement refinement for improved detailed routing convergence. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2021, 41(3): 784−788
    [74] Batterywala S, Shenoy N, Nicholls W, Zhou H. Track assignment: A desirable intermediate step between global routing and detailed routing. In: Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design. 2002. 59−66
    [75] Zhang Y H, Chu C. Regularroute: An efficient detailed router applying regular routing patterns. IEEE transactions on very large scale integration (VLSI) systems, 2012, 21(9): 1655−1668
    [76] Alpert C J. The ispd98 circuit benchmark suite. In: Proceedings of the 1998 international symposium on Physical design. New York, NY, USA: 1998. 80−85
    [77] Nam G J, Alpert C J, Villarrubia P, Winter B, Yildiz M. The ispd2005 placement contest and benchmark suite. In: Proceedings of the 2005 international symposium on Physical design. 2005. 216−220
    [78] Nam G J, Aplert C J, Villarrubia P G. The ISPD 2006 placement contest and benchmark suite. In: Proceedings of the 2006 international symposium on Physical design. San Jose, California, USA: 2006
    [79] Wong M P, Liu W H, Wang T C. Negotiation-based track assignment considering local nets. In: Proceedings of the 2016 21st Asia and South Pacific Design Automation Conference (ASP-DAC). Macao, China: IEEE, 2016. 378−383
    [80] Viswanathan N, Alpert C, Sze C, Li Z, Wei Y G. The dac 2012 routability-driven placement contest and benchmark suite. In: Proceedings of the 49th Annual Design Automation Conference. San Francisco, CA, USA: 2012. 774−782
    [81] Liu G G, Zhuang Z, Guo W Z, Wang T C. Rdta: An efficient routability-driven track assignment algorithm. In: Proceedings of the 2019 on Great Lakes Symposium on VLSI. New York, NY, USA: 2019. 315−318
    [82] 郭文忠, 陈晓华, 刘耿耿, 陈国龙. 基于混合离散粒子群优化的轨道分配算法. 模式识别与人工智能, 2019, 32(8): 758−770

    Guo Wen-Zhong, Chen Xiao-Hua, Liu Geng-Geng, Chen Guo-Long. Track assignment algorithm based on hybrid discrete particle swarm optimization. Pattern Recognition and Artificial Intelligence, 2019, 32(8): 758−770
    [83] Jia X T, Cai Y C, Zhou Q, Chen G, Li Z Y, Li Z W. Mcfroute: A detailed router based on multi-commodity flow method. In: Proceedings of the 2014 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). San Jose, CA, USA: IEEE, 2014. 397−404
    [84] Jia X T, Cai Y C, Zhou Q, Yu B. A multicommodity flow-based detailed router with efficient acceleration techniques. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2017, 37(1): 217−230
    [85] Yutsis V, Bustany I S, Chinnery D, Shinnerl J R, Liu W H. ISPD 2014 benchmarks with sub-45nm technology rules for detailed-routing-driven placement. In: Proceedings of the 2014 on International symposium on physical design. 2014. 161−168
    [86] Kahng A B, Wang L T, Xu B Q. Tritonroute: An initial detailed router for advanced vlsi technologies. In: Proceedings of the 2018 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). ACM, 2018. 1−8
    [87] Sun F K, Chen H, Chen C Y, Hsu C H, Chang Y W. A multithreaded initial detailed routing algorithm considering global routing guides. In: Proceedings of the 2018 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). San Diego, CA, USA: IEEE, 2018. 1−7
    [88] Kahng A B, Wang L T, Xu B Q. Tritonroute: The open-source detailed router. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 40(3): 547−559
    [89] Kahng A B, Wang L T, Xu B Q. Tritonroute-wxl: The open-source router with integrated drc engine. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2021, 41(4): 1076−1089
    [90] Chen J S, Liu J W, Chen G J, Zheng D, Young E F Y. March: Maze routing under a concurrent and hierarchical scheme for buses. In: Proceedings of the 56th Annual Design Automation Conference 2019. Las Vegas, NV, USA: 2019. 1−6
    [91] Chen G J, Pui C W, Li H C, Chen J S, Jiang B T, Young E F Y. Dr. cu: Detailed routing by sparse grid graph and minimum-area-captured path search. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019, 39(9): 1902−1915
    [92] Li H C, Chen G J, Jiang B T, Chen J S, Young E F Y. Dr. cu 2.0: A scalable detailed routing framework with correct-by-construction design rule satisfaction. In: Proceedings of the 2019 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). Westminster, CO, USA: IEEE, 2019. 1−7
    [93] Zhuang Z, Liu G G, Ho T Y, Yu B, Guo W Z. Trader: a practical track-assignment-based detailed router. In: Proceedings of the 2022 Design, Automation & Test in Europe Conference & Exhibition (DATE). Antwerp, Belgium: IEEE, 2022. 766−771
    [94] Cong J, Fang J, Xie M, Zhang Y. Mars-a multilevel full-chip gridless routing system. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2005, 24(3): 382−394 doi: 10.1109/TCAD.2004.842803
    [95] Li Y L, Chen H Y, Lin C T. Nemo: A new implicit-connection-graph-based gridless router with multilayer planes and pseudo tile propagation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2007, 26(4): 705−718 doi: 10.1109/TCAD.2007.891381
    [96] Du Y L, Ma Q, Song H, Shiely J, Luk-Pat G, Miloslavsky A, et al. Spacer-is-dielectric-compliant detailed routing for self-aligned double patterning lithography. In: Proceedings of the 50th Annual Design Automation Conference. Austin, TX, USA: 2013. 1−6
    [97] Ding Y X, Chu C, Mak W K, Detailed routing for spacer-is-metal type self-aligned double/quadruple patterning lithography. In: Proceedings of the 52nd Annual Design Automation Conference. San Francisco, CA, USA: 2015. 1−6
    [98] Ou J J, Yu B, Xu X Q, Mitra J, Lin Y B, Pan D Z. Dsar: Dsa aware routing with simultaneous dsa guiding pattern and double patterning assignment. In: Proceedings of the 2017 ACM on International Symposium on Physical Design. New York, NY, USA: 2017. 91−98
    [99] Yu H J, Chang Y W. Dsa-friendly detailed routing considering double patterning and dsa template assignments. In: Proceedings of the 55th Annual Design Automation Conference. New York, NY, USA: 2018. 1−6
    [100] Zhang Y H, Chu C. Gdrouter: Interleaved global routing and detailed routing for ultimate routability. In: Proceedings of the 49th Annual Design Automation Conference. San Francisco, CA, USA: 2012. 597−602
    [101] Gester M, Müller D, Nieberg T, Panten C, Schulte C, Vygen J. Bonnroute: Algorithms and data structures for fast and good vlsi routing. ACM Transactions on Design Automation of Electronic Systems (TODAES), 2013, 18(2): 1−24
    [102] Ajayi T, Blaauw D. Openroad: Toward a self-driving, open-source digital layout implementation tool chain. In: Proceedings of Government Microcircuit Applications and Critical Technology Conference. 2019
    [103] Aghaeekiasaraee E, Tabrizi A F, Fontana T A, Netto R, Almeida S F, Gandhi U, et al. CRP2. 0: A Fast and Robust Cooperation between Routing and Placement in Advanced Technology Nodes. ACM Transactions on Design Automation of Electronic Systems, 2023, 28(5): 1−42
    [104] Betz V, Rose J. Vpr: A new packing, placement and routing tool for fpga research. In: Proceedings of the International Conference on Field-Programmable Logic and Applications (FPL). Springer-Verlag, Berlin, Germany: 1997, 213−222
    [105] Murray K E, Petelin O, Zhong S, Wang J M, Eldafrawy M, Legault J P, et al. Vtr 8: High-performance cad and customizable fpga architecture modelling. ACM Transactions on Reconfigurable Technology and Systems (TRETS), 2020, 13(2): 1−55
    [106] Shah D, Hung E, Wolf C, Bazanski S, Gisselquist D, Milanovic M. Yosys+ nextpnr: an open source framework from verilog to bitstream for commercial fpgas. In: Proceedings of the 2019 IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM). San Diego, CA, USA: IEEE, 2019. 1−4
    [107] Gort M, Anderson J H. Accelerating fpga routing through parallelization and engineering enhancements special section on par-cad 2010. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2011, 31(1): 61−74
    [108] Wang D, Duan Z H, Tian C, Huang B H, Zhang N. A runtime optimization approach for fpga routing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2017, 37(8): 1706−1710
    [109] Vercruyce D, Vansteenkiste E, Stroobandt D. Croute: a fast high-quality timing-driven connection-based fpga router. In: Proceedings of the 2019 IEEE 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM). San Diego, CA, USA: IEEE, 2019. 53−60
    [110] Murray K E, Zhong S, Betz V. Air: A fast but lazy timing-driven fpga router. In: Proceedings of the 2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC). Beijing, China: IEEE, 2020. 338−344
    [111] Wang D K, Feng J, Zhou W, Hao X X, Zhang X D. Fcroute: A fast fpga connection router using soft routing-space pruning algorithm. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2023, 42(3): 887−899 doi: 10.1109/TCAD.2022.3188964
    [112] Wang J R, Mai J, Di Z X, Lin Y B. A Robust FPGA Router with Concurrent Intra-CLB Rerouting. In: Proceedings of the 28th Asia and South Pacific Design Automation Conference. 2023. 529−534
    [113] Yang S, Gayasen A, Mulpuri C, Reddy S, Aggarwal R. Routability-driven fpga placement contest. In: Proceedings of the 2016 on International Symposium on Physical Design. 2016. 139−143
    [114] Shen M H, Luo G J, Xiao N. Coarse-grained parallel routing with recursive partitioning for fpgas. IEEE Transactions on Parallel and Distributed Systems, 2020, 32(4): 884−899
    [115] Wang D K, Duan Z H, Tian C, Huang B H, Zhang N. Parra: A shared memory parallel fpga router using hybrid partitioning approach. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019, 39(4): 830−842
    [116] Shen M H, Luo G J, Xiao N. Combining static and dynamic load balance in parallel routing for fpgas. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 40(9): 1850−1863
    [117] Shen M H, Xiao N. Load balance-centric distributed parallel routing for large-scale fpgas. In: Proceedings of the 2021 31st International Conference on Field-Programmable Logic and Applications (FPL). Dresden, Germany: IEEE, 2021. 242−248
    [118] Shen M H, Zhang W T, Luo G J, Xiao N. Serial-equivalent static and dynamic parallel routing for fpgas. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 39(2): 411−423
    [119] Shen M H, Xiao N. Towards serial-equivalent multi-core parallel routing for fpgas. In: Proceedings of the 2020 Design, Automation & Test in Europe Conference & Exhibition (DATE). Grenoble, France: IEEE, 2020. 1139−1144
    [120] Gort M, Anderson J H. Deterministic multi-core parallel routing for FPGAs. In: 2010 International Conference on Field-Programmable Technology. IEEE, 2010. 78−86
    [121] Shen M H, Xiao N. Fine-grained parallel routing for fpgas with selective expansion. In: Proceedings of the 2018 IEEE 36th International Conference on Computer Design (ICCD). Orlando, FL, USA: IEEE, 2018. 577−586
    [122] Zha Y, Li J. Revisiting pathfinder routing algorithm. In: Proceedings of the 2022 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. New York, NY, USA: 2022. 24−34
    [123] He X, Huang T, Chow W K, Kuang J, Lam K C, Cai W Z, et al. Ripple 2.0: High quality routability-driven placement via global router integration. In: Proceedings of the 50th Annual Design Automation Conference. Austin, TX, USA: 2013. 1−6
    [124] Chan W T J, Ho P H, Kahng A B, Saxena P. Routability optimization for industrial designs at sub-14nm process nodes using machine learning. In: Proceedings of the 2017 ACM on International Symposium on Physical Design. New York, NY, USA: 2017. 15−21
    [125] Tabrizi A F, Darav N K, Rakai L, Bustany I, Kennings A, Behjat L. Eh? predictor: A deep learning framework to identify detailed routing short violations from a placed netlist. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019, 39(6): 1177−1190
    [126] Tabrizi A F, Darav N K, Xu S C, Rakai L, Bustany I, Kennings A, et al. A machine learning framework to identify detailed routing short violations from a placed netlist. In: Proceedings of the 55th Annual Design Automation Conference. San Francisco, CA, USA: 2018. 1−6
    [127] Bustany I S, Chinnery D, Shinnerl J R, Yutsis V. Ispd 2015 benchmarks with fence regions and routing blockages for detailed-routing-driven placement. In: Proceedings of the 2015 Symposium on International Symposium on Physical Design. 2015. 157−164
    [128] Yu T C, Fang S Y, Chiu H S, Hu K S, Tai P H Y, Shen C C F, et al. Pin accessibility prediction and optimization with deep learning-based pin pattern recognition. In: Proceedings of the 56th Annual Design Automation Conference 2019. New York, NY, USA: 2019. 1−6
    [129] Liang R J, Xiang H, Pandey D, Reddy L, Ramji S, Nam G J, et al. Drc hotspot prediction at sub-10nm process nodes using customized convolutional network. In: Proceedings of the 2020 International Symposium on Physical Design. New York, NY, USA: 2020. 135−142
    [130] Xie Z Y, Huang Y H, Fang G Q, Ren H X, Fang S Y, Chen Y R, et al. Routenet: Routability prediction for mixed-size designs using convolutional neural network. In: Proceedings of the 2018 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). IEEE, 2018. 1−8
    [131] Huang Y H, Xie Z Y, Fang G Q, Yu T C, Ren H X, Fang S Y, et al. Routability-driven macro placement with embedded cnn-based prediction model. In: Proceedings of the 2019 Design, Automation & Test in Europe Conference & Exhibition (DATE). Florence, Italy: IEEE, 2019. 180−185
    [132] Chen J S, Kuang J, Zhao G W, Huang D J H, Young E F Y. Pros 2.0: A plug-in for routability optimization and routed wirelength estimation using deep learning. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 42(1): 164−177
    [133] Al-Hyari A, Szentimrey H, Shamli A, Martin T, Grewal G, Areibi S. A deep learning framework to predict routability for fpga circuit placement. ACM Transactions on Reconfigurable Technology and Systems (TRETS), 2021, 14(3): 1−28
    [134] Al-Hyari A, Shamli A, Abuwaimer Z, Areibi S, Grewal G. A deep learning framework to predict routability for fpga circuit placement. In: Proceedings of the 29th International Conference on Field Programmable Logic and Applications (FPL), Barcelona, Spain: 2019. 334−341
    [135] Alawieh M B, Li W X, Lin Y B, Singhal L, Iyer M A, Pan D Z. High-definition routing congestion prediction for large-scale fpgas. In: Proceedings of the 2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC). Beijing, China: IEEE, 2020. 26−31
    [136] Yu C X, Zhang Z R. Painting on placement: Forecasting routing congestion using conditional generative adversarial nets. In: Proceedings of the 56th Annual Design Automation Conference 2019. Las Vegas, NV, USA: 2019. 1−6
    [137] Wang B W, Shen G B, Li D, Hao J Y, Liu W L, Huang Y, et al. LHNN: Lattice hypergraph neural network for VLSI congestion prediction. In: Proceedings of the 59th ACM/IEEE Design Automation Conference. 2022. 1297−1302
    [138] Viswanathan N, Alpert C J, Sze C, Li Z, Nam G J, Roy J A. The ISPD-2011 routability-driven placement contest and benchmark suite. In: Proceedings of the 2011 international symposium on Physical design. 2011. 141−146
    [139] Mirhoseini A, Goldie A, Yazgan M, Jiang J W J, Songhori E, Wang S, et al. A graph placement methodology for fast chip design. Nature, 2021, 594(7862): 207−212 doi: 10.1038/s41586-021-03544-w
    [140] Zaruba F, Benini L. The cost of application-class processing: Energy and performance analysis of a linux-ready 1.7-ghz 64-bit risc-v core in 22-nm fdsoi technology. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2019, 27(11): 2629−2640 doi: 10.1109/TVLSI.2019.2926114
    [141] Cheng R Y, Yan J C. On joint learning for solving placement and routing in chip design. Advances in Neural Information Processing Systems, 2021, 34: 16508−16519
    [142] Cheng R Y, Lyu X L, Li Y, Ye J J, Hao J Y, Yan J C. The policy-gradient placement and generative routing neural networks for chip design. Advances in Neural Information Processing Systems, 2022, 35: 26350−26362
    [143] Hung W T, Huang J Y, Chou Y C, Tsai C H, Chao M. Transforming global routing report into drc violation map with convolutional neural network. In: Proceedings of the 2020 International Symposium on Physical Design. New York, NY, USA: 2020. 57−64
    [144] Su M D, Ding H Z, Weng S H, Zou C Z, Zhou Z H, Chen Y L, et al. High-correlation 3d routability estimation for congestion-guided global routing. In: Proceedings of the 2022 27th Asia and South Pacific Design Automation Conference (ASP-DAC). Taipei, Taiwan: IEEE, 2022. 580−585
    [145] Utyamishev D, Partin-Vaisband I. Multiterminal pathfinding in practical vlsi systems with deep neural networks. ACM Transactions on Design Automation of Electronic Systems, 2023, 28(4): 1−19
    [146] Utyamishev D, Partin-Vaisband I. Late breaking results: A neural network that routes ics. In: Proceedings of the 2020 57th ACM/IEEE Design Automation Conference (DAC). San Francisco, CA, USA: IEEE, 2020. 1−2
    [147] Gandhi U, Aghaeekiasaraee E, Bustany I S K, Mousavi P, E.Taylor M, Behjat L. RL-Ripper: A Framework for Global Routing Using Reinforcement Learning and Smart Net Ripping Techniques. In: Proceedings of the Great Lakes Symposium on VLSI 2023. 2023. 197−201
    [148] Liao H G, Zhang W T, Dong X L, Poczos B, Shimada K, Burak Kara L. A deep reinforcement learning approach for global routing. Journal of Mechanical Design, 2020, 142(6): 061701 doi: 10.1115/1.4045044
    [149] Ren H X, Fojtik M. Standard cell routing with reinforcement learning and genetic algorithm in advanced technology nodes. In: Proceedings of the 26th Asia and South Pacific Design Automation Conference. 2021. 684−689
    [150] Siddiqi U, Martin T, Van Den Eijnden S, Shamli A, Grewal G, Sait S, et al. Faster fpga routing by forecasting and pre-loading congestion information. In: Proceedings of the 2022 ACM/IEEE Workshop on Machine Learning for CAD. New York, NY, USA: 2022. 15−20
    [151] Luu J, Goeders J, Wainberg M, Somerville A, Yu T, Nasartschuk K, et al. Vtr 7.0: Next generation architecture and cad system for fpgas. ACM Transactions on Reconfigurable Technology and Systems (TRETS), 2014, 7(2): 1−30
    [152] Lin Y B, Qu T, Lu Z Q, Su Y J, Wei Y Y. Asynchronous reinforcement learning framework and knowledge transfer for net-order exploration in detailed routing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2021, 41(9): 3132−3142
    [153] Qu T, Lin Y B, Lu Z Q, Su Y J, Wei Y Y. Asynchronous reinforcement learning framework for net order exploration in detailed routing. In: Proceedings of the 2021 Design, Automation & Test in Europe Conference & Exhibition (DATE). Grenoble, France: IEEE, 2021. 1815−1820
    [154] Liao H G, Dong Q Y, Qi W Y, Fallon E, Kara L B. Track-assignment detailed routing using attention-based policy model with supervision. In: Proceedings of the 2020 ACM/IEEE Workshop on Machine Learning for CAD. 2020. 105−110
    [155] Chen H, Hsu K C, Turner W J, Wei P H, Zhu K, Pan D Z, et al. Reinforcement Learning Guided Detailed Routing for Custom Circuits. In: Proceedings of the 2023 International Symposium on Physical Design. 2023. 26−34
    [156] Ju X H, Zhu K L, Lin Y B, Zhang L. Asynchronous multi-nets detailed routing in vlsi using multi-agent reinforcement learning. In: Proceedings of the 2021 7th IEEE International Conference on Network Intelligence and Digital Content (IC-NIDC). Beijing, China: IEEE, 2021. 250−254
    [157] Murray K E, Whitty S, Liu S, Luu J, Betz V. Timing-driven titan: Enabling large benchmarks and exploring the gap between academic and commercial cad. ACM Transactions on Reconfigurable Technology and Systems (TRETS), 2015, 8(2): 1−18
    [158] Zhuo H H, Kambhampati S. Model-lite planning: Case-based vs. model-based approaches. Artificial Intelligence, 2017, 246: 1−21 doi: 10.1016/j.artint.2017.01.004
    [159] Zhuo H H, Muñoz-Avila H, Yang Q. Learning hierarchical task network domains from partially observed plan traces. Artificial Intelligence, 2014, 212: 134−157 doi: 10.1016/j.artint.2014.04.003
    [160] Zhuo H H, Yang Q, Hu D H, Li L. Learning complex action models with quantifiers and logical implications. Artificial Intelligence, 2010, 174(18): 1540−1569 doi: 10.1016/j.artint.2010.09.007
    [161] Zhuo H H. Crowdsourced action-model acquisition for planning. In: Proceedings of the AAAI Conference on Artificial Intelligence. 2015, 29 (1): 3439−3446.
    [162] Zhuo H H, Yang Q. Action-model acquisition for planning via transfer learning. Artificial Intelligence, 2014, 212: 80−103 doi: 10.1016/j.artint.2014.03.004
    [163] Zhuo H H, Yang Q, Pan R, Li L. Cross-domain action-model acquisition for planning via web search. In: Proceedings of the International Conference on Automated Planning and Scheduling. 2011, 21 : 298−305
    [164] Jin K B, Zhuo H H, Xiao Z H, Wan H, Kambhampati S. Gradient-based mixed planning with symbolic and numeric action parameters. Artificial Intelligence, 2022, 313: 103789 doi: 10.1016/j.artint.2022.103789
    [165] Zhuo H H, Zha Y T, Kambhampati S, Tian X. Discovering underlying plans based on shallow models. ACM Transactions on Intelligent Systems and Technology (TIST), 2020, 11(2): 1−30
    [166] Zhuo H H. Recognizing multi-agent plans when action models and team plans are both incomplete. ACM Transactions on Intelligent Systems and Technology (TIST), 2019, 10(3): 1−24
    [167] Zhuo H H. Human-aware plan recognition. In: Proceedings of the AAAI Conference on Artificial Intelligence. 2017, 31 (1): 3686−3693.
  • 加载中
计量
  • 文章访问数:  292
  • HTML全文浏览量:  126
  • 被引次数: 0
出版历程
  • 收稿日期:  2023-06-15
  • 录用日期:  2023-11-09
  • 网络出版日期:  2024-04-29

目录

    /

    返回文章
    返回