-
摘要: 布线是芯片设计自动化流程中至关重要且特别耗时的一环, 直接影响最终产品的面积、成本、功耗、速度和可靠性, 研究智能布线算法对提高芯片布线效率和优化芯片布线效果具有重要意义. 芯片布线问题是一个多目标、多约束的NP困难问题. 即使已有几十年的研究历史, 目前仍存在大量未突破的问题和空间. 随着制造工艺的不断发展, 布线规则、约束和目标也持续调整和增加, 使得布线选择极其困难. 因此, 对芯片设计自动化中自动布线的前沿研究进行了全面归纳与分析, 以帮助科研人员全面了解该领域的研究进展和方向, 助力智能布线算法的研究和发展. 具体而言, 首先阐述芯片布线的问题背景, 然后分别介绍全局布线(Global routing, GR) 和详细布线(Detailed routing, DR)的任务定义和目标、过程特点、难点和挑战、评估方法; 接着详述和分析各布线方法, 重点论述基于规划搜索的布线方法和基于机器学习的布线方法的最新研究成果、优缺点及其应用环节; 然后介绍公开数据集和开源布线工具; 最后总结现有方法在实际应用中存在的局限性, 并对自动布线未来的发展趋势和潜在研究方向进行展望.Abstract: 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.
-
Key words:
- Machine learning /
- AI planning /
- reinforcement learning /
- chip /
- routing /
- global routing (GR) /
- detailed routing (DR)
1)1 1 LEF/DEF Language Reference Version 5.7,https://www.ispd.cc/contests/18/lefdefref.pdf 2)2 1 Guelph FPGA CAD Group,http://fpga.socs.uoguelph.ca/ 3)3 1 TritonRoute, UCSD Detailed Router,https://github.com/The-OpenROAD-Project/TritonRoute 2 CUGR, VLSI Global Routing Tool Developed by CUHK,https://github.com/cuhk-eda/cu-gr 3 Dr.CU, VLSI Detailed Routing Tool Developed by CUHK,https://github.com/cuhk-eda/dr-cu 4 EDA-AI,https://github.com/Thinklab-SJTU/EDA-AI 5 Verilog to Routing, Open Source CAD Flow for FPGA Research,https://github.com/verilog-to-routing/vtr-verilog-to-routing -
图 9 三维转二维全局布线流程: 投影−布线−层分配
Fig. 9 3D to 2D global routing process: Projection−routing−layer assignment
图 14 基于布局信息的设计规划违例预测框架
Fig. 14 Design rule violation prediction framework based on placement information
图 15 基于深度强化学习的线长和短路违例预测与布局规划模型
Fig. 15 Wirelength and short violation prediction and floor planning model based on deep reinforcement learning
图 16 A* 搜索指导的强化学习全局布线流程
Fig. 16 Global routing based on A* search-guided reinforcement learning
图 17 线网排序强化学习框架中的策略网络模型和价值网络模型
Fig. 17 Policy network and value network in the reinforcement learning framework for net ordering
图 18 基于多智能体强化学习的详细布线框架
Fig. 18 Detailed routing framework based on multi-agent reinforcement learning
表 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] 郭文忠等[82] (2019) 基于离散粒子群优化、遗传操作和基于协商的精炼策略的轨道分配算法 DAC12[80] 基于网格的并行布线 Jia等[83] (2014)
Jia等[84] (2018)基于多商品流方法的并行布线算法 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) 分层并行迷宫布线方法实现总线布线 ICCAD 2018** 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 cell placement optimization
任务类型 算法框架 文献(年份) 芯片类型 数据集 可布线性预测 SVN Chan等[124] (2017) VLSI Foundry NN Tabrizi等[125−126] (2019, 2018) VLSI ISPD15[127] CNN Yu等[128] (2019) VLSI Generated CNN Liang等[129] (2020) VLSI Foundry CNN Xie等[130] (2018)、Huang等[131] (2019) VLSI ISPD15[127] CNN Chen等[132] (2022) VLSI Foundry & DAC12[80] CNN Alhyari等[133−134] (2021, 2019) FPGA ISPD16[113] & Xilinx cGAN Alawieh等[135] (2020)、Yu等[136] (2019) FPGA ISPD16[113] LHNN Wang等[137] (2022) VLSI ISPD11[138] & DAC12[80] 布局规划优化 RL + GCN Mirhoseini等[139] (2021) VLSI Foundry & Ariane[140] 布局布线融合 RL + GNN + CNN Cheng等[141−142] (2021, 2022) VLSI ISPD05[77]
下载: 导出CSV
表 5 基于详细布线优化的布线方法
Table 5 Routing approaches for detailed routing optimization
任务类型 算法框架 文献(年份) 芯片类型 数据集 违例预测与修复 RL Gandhi等[14] (2019) VLSI Generated RL Ren等[149] (2021) VLSI Foundry Random-Forest Siddiqi等[150] (2022) FPGA VPR 7[151] 线网排序 RL Lin等[152] (2022), Qu等[153] (2021) VLSI ISPD18[19] & ISPD19[20] 走线选择 MCTS + RL He等[15] (2022) VLSI Generated RL Liao等[154] (2020) VLSI Foundry RL Chen等[155] (2023) VLSI Foundry 异步并行布线 MARL Ju等[156] (2021) VLSI Generated
下载: 导出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 the Symposium on the Complexity of Computer Computations. New York, USA: Springer, 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. Burlington: Morgan Kaufmann, 2009. 687−749 [4] Sherwani N A. Algorithms for VLSI Physical Design Automation (3rd edition). New York: Springer, 1999. [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, 2021, 26(5): Article No. 40 [6] Lopera 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 3rd Workshop on Machine Learning for CAD (MLCAD). Raleigh, USA: IEEE, 2021. 1−6 [7] Gubbi K I, Beheshti-Shirazi S A, Sheaves T, Salehi S, Manoj P D S, Rafatirad S, et al. Survey of machine learning for electronic design automation. In: Proceedings of the Great Lakes Symposium on VLSI. Irvine, USA: ACM, 2022. 513−518 [8] 田春生, 陈雷, 王源, 王硕, 周婧, 张瑶伟, 等. 面向FPGA的布局与布线技术研究综述. 电子学报, 2022, 50(5): 1243−1254 doi: 10.12263/DZXB.20210637Tian 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 doi: 10.12263/DZXB.20210637 [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 doi: 10.3969/j.issn.1000-7180.2021.11.wdzxyjsj202111001Qu Tong, Gai Tian-Yang, Wang Shu-Han, Su Xiao-Jing, Su Ya-Juan, Wei Ya-Yi. Research progress of VLSI detailed routing algorithm. Microelectronics and Computer, 2021, 38(11): 1−6 doi: 10.3969/j.issn.1000-7180.2021.11.wdzxyjsj202111001 [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 International Symposium on Physical Design. Virtual Event: ACM, 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 1st Workshop on Machine Learning for CAD (MLCAD). Canmore, 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 International Symposium on VLSI Design, Automation and Test (VLSI-DAT). Hsinchu, China: IEEE, 2022. 1−5 [16] 陈春章, 艾霞, 王国雄. 数字集成电路物理设计. 北京: 科学出版社, 2008.Chen Chun-Zhang, Ai Xia, Wang Guo-Xiong. Physical Design of Digital Integrated Circuits. Beijing: Science Press, 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 International Symposium on Physical Design. Austin, USA: ACM, 2007. Article No. 167 [18] Nam G J, Sze C, Yildiz M. The ISPD global routing benchmark suite. In: Proceedings of the International Symposium on Physical Design. Portland, USA: ACM, 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 International Symposium on Physical Design. Monterey, USA: ACM, 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 International Symposium on Physical Design. San Francisco, USA: ACM, 2019. 147−151 [21] Lee C Y. An algorithm for path connections and its applications. IRE Transactions on Electronic Computers, 1961, EC-10(3): 346−365 doi: 10.1109/TEC.1961.5219222 [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. Las Vegas, USA: IEEE, 1978. 100−102 [24] Mikami K, Tabuchi K. A computer program for optimal routing of printed circuit conductors. In: Proceedings of the International Federation for Information Processing (IFIP). Edinburgh, UK: North-Holland, 1968. 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. San Francisco, USA: ACM, 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. New York: ACM, 2022. 287−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. Albuquerque, USA: IEEE, 1984. 45−51 [30] McMurchie L, Ebeling C. PathFinder: A negotiation-based performance-driven router for FPGAs. In: Proceedings of the 3rd International Symposium on Field-Programmable Gate Arrays. Napa Valley, USA: IEEE, 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 58th ACM/IEEE Design Automation Conference (DAC). San Francisco, 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, 2008, 27(1): 70−83 doi: 10.1109/TCAD.2007.907068 [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 F, Zhou H, Young F Y, Yang H H, Sherwani N. Integrated floorplanning and interconnect planning. Layout Optimization in VLSI Design. New York: Springer, 2001. 1−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. San Francisco, USA: ACM, 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 IEEE/ACM International Conference on Computer-Aided Design. San Jose, USA: ACM, 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. San Francisco, USA: IEEE, 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, 2011, 30(1): 72−84 doi: 10.1109/TCAD.2010.2066030 [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. Santa Clara, USA: IEEE, 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, 2009, 14(2): Article No. 32 [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 Asia and South Pacific Design Automation Conference. Yokohama, Japan: IEEE, 2009. 582−587 [51] Xu Y, Zhang Y H, Chu C. FastRoute 4.0: Global router with efficient via minimization. In: Proceedings of the Asia and South Pacific Design Automation Conference. Yokohama, Japan: 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 [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 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). Westminster, 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, 2023, 42(2): 569−582 doi: 10.1109/TCAD.2022.3178353 [56] 刘耿耿, 李泽鹏, 郭文忠, 陈国龙, 徐宁. 面向超大规模集成电路物理设计的通孔感知的并行层分配算法. 电子学报, 2022, 50(11): 2575−2583 doi: 10.12263/DZXB.20211065Liu 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 doi: 10.12263/DZXB.20211065 [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 F. 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 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). San Jose, USA: 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 57th ACM/IEEE Design Automation Conference (DAC). San Francisco, 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 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). Westminster, 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, 2023, 42(7): 2317−2330 doi: 10.1109/TCAD.2022.3217668 [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 IEEE Computer Society Annual Symposium on VLSI (ISVLSI). Tampa, 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, 2024, 43(1): 352−365 doi: 10.1109/TCAD.2023.3305579 [65] Zou P, Cai Z J, Lin Z F, Ma C Y, Yu J, Chen J L. Incremental 3-D global routing considering cell movement and complex routing constraints. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2023, 42(6): 2016−2029 doi: 10.1109/TCAD.2022.3210493 [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. San Diego, USA: ACM, 2022. Article No. 129 [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. San Diego, USA: ACM, 2020. Article No. 69 [68] Hu K S, Yu T C, Yang M J, Shen C F C. 2021 ICCAD CAD contest problem B: Routing with cell movement advanced: Invited paper. In: Proceedings of the IEEE/ACM International Conference on Computer Aided Design (ICCAD). Munich, Germany: IEEE, 2021. 1−5 [69] Nieberg T. Gridless pin access in detailed routing. In: Proceedings of the 48th ACM/EDAC/IEEE Design Automation Conference (DAC). San Diego, USA: IEEE, 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, 2016, 21(3): Article No. 42 [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. Austin, USA: ACM, 2017. Article No. 20 [72] Kahng A B, Wang L T, Xu B Q. The Tao of PAO: Anatomy of a pin access oracle for detailed routing. In: Proceedings of the 57th ACM/IEEE Design Automation Conference (DAC). San Francisco, 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, 2022, 41(3): 784−788 doi: 10.1109/TCAD.2021.3066528 [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 IEEE/ACM International Conference on Computer-Aided Design. San Jose, USA: ACM, 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, 2013, 21(9): 1655−1668 doi: 10.1109/TVLSI.2012.2214491 [76] Alpert C J. The ISPD98 circuit benchmark suite. In: Proceedings of the International Symposium on Physical Design. Monterey, USA: ACM, 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 International Symposium on Physical Design. San Francisco, USA: ACM, 2005. 216−220 [78] Nam G J. ISPD 2006 placement contest: Benchmark suite and results. In: Proceedings of the International Symposium on Physical Design. San Jose, USA: ACM, 2006. Article No. 167 [79] Wong M P, Liu W H, Wang T C. Negotiation-based track assignment considering local nets. In: Proceedings of the 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 Design Automation Conference (DAC). San Francisco, USA: IEEE, 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 Great Lakes Symposium on VLSI. Tysons Corner, USA: ACM, 2019. 315−318 [82] 郭文忠, 陈晓华, 刘耿耿, 陈国龙. 基于混合离散粒子群优化的轨道分配算法. 模式识别与人工智能, 2019, 32(8): 758−770Guo 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 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). San Jose, 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, 2018, 37(1): 217−230 doi: 10.1109/TCAD.2017.2693270 [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 International Symposium on Physical Design. Petaluma, USA: ACM, 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 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). San Diego, USA: IEEE, 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 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). San Diego, 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, 2021, 40(3): 547−559 doi: 10.1109/TCAD.2020.3003234 [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, 2022, 41(4): 1076−1089 doi: 10.1109/TCAD.2021.3079268 [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. Las Vegas, USA: ACM, 2019. Article No. 216 [91] Chen G J, Pui C W, Li H C, 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, 2020, 39(9): 1902−1915 doi: 10.1109/TCAD.2019.2927542 [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 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). Westminster, 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 Design, Automation and Test in Europe Conference and 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, USA: ACM, 2013. Article No. 93 [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, USA: ACM, 2015. Article No. 69 [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 ACM on International Symposium on Physical Design. Portland, USA: ACM, 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. San Francisco, USA: ACM, 2018. Article No. 49 [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, USA: ACM, 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, 2013, 18(2): Article No. 32 [102] Ajayi T, Blaauw D, Chan T B, Cheng C K, Chhabria V A, Choo D K, et al. OpenROAD: Toward a self-driving, open-source digital layout implementation tool chain. In: Proceedings of the Government Microcircuit Applications and Critical Technology Conference. Albuquerque, USA: Defense Technical Information Center, 2019. 1105−1110 [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): Article No. 79 [104] Betz V, Rose J. VPR: A new packing, placement and routing tool for FPGA research. In: Proceedings of the 7th International Conference on Field-Programmable Logic and Applications (FPL). London, UK: Springer, 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, 2020, 13(2): Article No. 9 [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 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM). San Diego, 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, 2012, 31(1): 61−74 doi: 10.1109/TCAD.2011.2165715 [108] Wang D K, 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, 2018, 37(8): 1706−1710 doi: 10.1109/TCAD.2017.2768416 [109] Vercruyce D, Vansteenkiste E, Stroobandt D. CRoute: A fast high-quality timing-driven connection-based FPGA router. In: Proceedings of the 27th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM). San Diego, 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 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 (ASP-DAC). Tokyo, Japan: IEEE, 2023. 529−534 [113] Yang S, Gayasen A, Mulpuri C, Reddy S, Aggarwal R. Routability-driven FPGA placement contest. In: Proceedings of the International Symposium on Physical Design. Santa Rosa, USA: ACM, 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, 2021, 32(4): 884−899 doi: 10.1109/TPDS.2020.3035787 [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, 2020, 39(4): 830−842 doi: 10.1109/TCAD.2019.2901243 [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, 2021, 40(9): 1850−1863 doi: 10.1109/TCAD.2020.3031259 [117] Shen M H, Xiao N. Load balance-centric distributed parallel routing for large-scale FPGAs. In: Proceedings of the 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, 2020, 39(2): 411−423 doi: 10.1109/TCAD.2018.2887050 [119] Shen M H, Xiao N. Towards serial-equivalent multi-core parallel routing for FPGAs. In: Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE). Grenoble, France: IEEE, 2020. 1139−1144 [120] Gort M, Anderson J H. Deterministic multi-core parallel routing for FPGAs. In: Proceedings of the International Conference on Field-Programmable Technology. Beijing, China: IEEE, 2010. 78−86 [121] Shen M H, Xiao N. Fine-grained parallel routing for FPGAs with selective expansion. In: Proceedings of the 36th International Conference on Computer Design (ICCD). Orlando, USA: IEEE, 2018. 577−586 [122] Zha Y, Li J. Revisiting pathfinder routing algorithm. In: Proceedings of the ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. New York, USA: ACM, 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, USA: ACM, 2013. Article No. 152 [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 ACM on International Symposium on Physical Design. Portland, USA: ACM, 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, 2020, 39(6): 1177−1190 doi: 10.1109/TCAD.2019.2917130 [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, USA: ACM, 2018. Article No. 48 [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 Symposium on International Symposium on Physical Design. Monterey, USA: ACM, 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. Las Vegas, USA: ACM, 2019. Article No. 220 [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 International Symposium on Physical Design. Taipei, China: ACM, 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 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). San Diego, USA: 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 Design, Automation and Test in Europe Conference and 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, 2023, 42(1): 164−177 doi: 10.1109/TCAD.2022.3168259 [133] Alhyari A, Szentimrey H, Shamli A, Martin T, Gréwal G, Areibi S. A deep learning framework to predict routability for FPGA circuit placement. ACM Transactions on Reconfigurable Technology and Systems, 2021, 14(3): Article No. 16 [134] Alhyari 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: IEEE, 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 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. Las Vegas, USA: ACM, 2019. Article No. 219 [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. San Francisco, USA: ACM, 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 International Symposium on Physical Design. Santa Barbara, USA: ACM, 2011. 141−146 [139] Mirhoseini A, Goldie A, Yazgan M, Jiang J W, 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. In: Proceedings of the 35th International Conference on Neural Information Processing Systems. Virtual Event: Curran Associates Inc., 2021. Article No. 1262 [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. In: Proceedings of the 36th International Conference on Neural Information Processing Systems. New Orleans, USA: Curran Associates Inc., 2022. Article No. 1911 [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 International Symposium on Physical Design. Taipei, China: ACM, 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 27th Asia and South Pacific Design Automation Conference (ASP-DAC). Taipei, China: 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): Article No. 51 [146] Utyamishev D, Partin-Vaisband I. Late breaking results: A neural network that routes ICs. In: Proceedings of the 57th ACM/IEEE Design Automation Conference (DAC). San Francisco, USA: IEEE, 2020. 1−2 [147] Gandhi U, Aghaeekiasaraee E, Bustany I S K, Mousavi P, Taylor M E, 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. Knoxville, USA: ACM, 2023. 197−201 [148] Liao H G, Zhang W T, Dong X L, Poczos B, Shimada K, Kara L B. A deep reinforcement learning approach for global routing. Journal of Mechanical Design, 2020, 142(6): Article No. 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 (ASP-DAC). Tokyo, Japan: IEEE, 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 ACM/IEEE Workshop on Machine Learning for CAD. Utah, USA: ACM, 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, 2014, 7(2): Article No. 6 [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, 2022, 41(9): 3132−3142 doi: 10.1109/TCAD.2021.3117505 [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 Design, Automation and Test in Europe Conference and 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 2nd ACM/IEEE Workshop on Machine Learning for CAD (MLCAD). Reykjavik, Iceland: IEEE, 2020. 105−110 [155] Chen H, Hsu K C, Turner W J, Wei P H, Zhu K R, Pan D Z, et al. Reinforcement learning guided detailed routing for custom circuits. In: Proceedings of the International Symposium on Physical Design. Virtual Event: ACM, 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 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 Y, 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, 2015, 8(2): Article No. 10 [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 29th AAAI Conference on Artificial Intelligence. Austin, USA: AAAI, 2015. 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 21st International Conference on International Conference on Automated Planning and Scheduling. Freiburg, Germany: AAAI, 2011. 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: Article No. 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, 2020, 11(2): Article No. 18 [166] Zhuo H H. Recognizing multi-agent plans when action models and team plans are both incomplete. ACM Transactions on Intelligent Systems and Technology, 2019, 10(3): Article No. 30 [167] Zhuo H H. Human-aware plan recognition. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence. San Francisco, USA: AAAI, 2017. 3686−3693 -
图(18) / 表(7)
计量
- 文章访问数: 915
- HTML全文浏览量: 401
- PDF下载量: 189
- 被引次数: 0
