超大规模集成电路全局布局布线算法研究综述

doi:10.11871/jfdc.issn.2096-742X.2026.03.011

数据与计算发展前沿 ›› 2026, Vol. 8 ›› Issue (3): 122-136.

doi: 10.11871/jfdc.issn.2096-742X.2026.03.011

超大规模集成电路全局布局布线算法研究综述

李旭^1,²(),李晨¹,姜金荣^1,²,陆忠华^1,²,迟学斌^1,^2,^*()

¹ 中国科学院计算机网络信息中心，北京 100083
² 中国科学院大学，北京 100190

收稿日期:2025-09-07 出版日期:2026-06-20 发布日期:2026-06-18
通讯作者: 迟学斌
作者简介:李旭，中国科学院计算机网络信息中心，博士研究生，主要研究方向为高性能计算和VLSI全局布局。
本文负责文献调研，整理分析。
LI Xu is a Ph.D student at the Computer Network Information Center, Chinese Academy of Sciences. His research interests include high-performance computing and VLSI global placement.
In this paper, he is responsible for literature review, organization, and analysis.
E-mail: lixu@cnic.cn|迟学斌，中国科学院计算机网络信息中心，研究员，博士生导师。主要研究方向为高性能计算网格技术。
本文负责把握文章总体方向与框架。
CHI Xuebin is currently a professor at the Computer Network Information Center, Chinese Academy of Sciences, China. His current research interests include high-performance computing Grid Technology.
In this paper, he is responsible for guiding the overall direction and designing the framework of the manuscript.
E-mail: chi@sccas.cn
基金资助:
光合基金A类(202407012934)

A Survey of Research on Global Placement and Route Algorithm of Very Large Scale Integration

LI Xu^1,²(),LI Chen¹,JIANG Jinrong^1,²,LU Zhonghua^1,²,CHI Xuebin^1,^2,^*()

¹ Computer Network Information Center, Chinese Academy of Sciences, Beijing 100083, China
² University of Chinese Academy of Sciences, Beijing 100190, China

Received:2025-09-07 Online:2026-06-20 Published:2026-06-18
Contact: CHI Xuebin

摘要/Abstract

摘要：

【背景】超大规模集成电路物理设计是电子设计自动化中的核心问题，布局布线是物理设计中的关键步骤，直接影响芯片的性能、功耗和面积。随着芯片规模不断扩大，物理设计的布局布线问题愈发复杂，对应的算法也在发展。 【方法】本文从研究对象和算法思想两个维度，对超大规模集成电路全局布局与全局布线的研究进行了系统分类与总结。同时，本文分析了近年来机器学习在布局与布线中的应用趋势。 【结论】目前全局布局的解析算法和全局布线的顺序布线算法与机器学习方法的结合正成为布局布线的重要发展趋势，未来需进一步提升算法的并行化能力。

关键词: 超大规模集成电路, 电子设计自动化, 物理设计, 全局布局, 全局布线

Abstract:

[Background] Very Large Scale Integration (VLSI) physical design is a core problem in Electronic Design Automation (EDA). With the continuous growth of chip scale, placement and routing algorithms have also evolved accordingly. [Methods] This paper systematically classifies and summarizes research on global placement and global routing in VLSI from two perspectives: the design objects and the underlying algorithmic strategies. In addition, recent trends in applying machine learning to placement and routing are analyzed. [Conclusions] The combination of analytical algorithms and machine learning methods has become an important development trend in placement and routing. Future work should focus on further enhancing the parallelism of algorithms.

Key words: VLSI, EDA, physical design, global placement, global routing

李旭,李晨,姜金荣,陆忠华,迟学斌. 超大规模集成电路全局布局布线算法研究综述[J]. 数据与计算发展前沿, 2026, 8(3): 122-136.

LI Xu,LI Chen,JIANG Jinrong,LU Zhonghua,CHI Xuebin. A Survey of Research on Global Placement and Route Algorithm of Very Large Scale Integration[J]. Frontiers of Data and Computing, 2026, 8(3): 122-136.

图/表 8

图1

图2

图3

表1

图4

图5

图6

图7

参考文献 77

[1]	谢非, 罗安. 非对称性贸易依赖关系对中国芯片进口的影响探究[J]. 改革, 2022(6): 116-130.
[2]	SHERWANI N A. Algorithms for VLSI physical design automation[M]. Springer Science & Business Media, 2012.
[3]	LU J, CHEN P, CHANG C, et al. FFTPL: An analytic placement algorithm using fast fourier transform for density equalization[C]. 2013 IEEE 10th International Conference on ASIC, Shenzhen, 2013:1-4.
[4]	朱自然, 张勋, 陆亦辰, 等. 超大规模集成电路宏模块布局研究进展[J]. 中国基础科学, 2023, 25(4): 40-48.
[5]	焦虹, 洪先龙. 宏单元阵列布局的两步模拟退火算法[J]. 计算机工程与设计, 1997(3): 49-51.
[6]	王克胜, 唐璞山. 一种采用规划方法的宏模块布局算法[J]. 计算机辅助设计与图形学学报, 2002(5): 413-416.
[7]	朱彦臻, 严浩鹏, 蔡述庭, 等. 基于张力微调和线长驱动的宏单元布局器[J]. 电子与信息学报, 2025, 47(7): 2396-2404.
[8]	符强, 梁家瑞, 肖有军, 等. 基于机器学习的宏单元摆放方法与约束方案[J]. 微电子学, 2025(8): 1-7.
[9]	SHI Y, XUE K, SONG L, et al. Macro placement by wire-mask-guided black-box optimization[C]. In Proceedings of the 37th International Conference on Neural Information Processing Systems (NIPS '23). Curran Associates Inc., Red Hook, NY, USA, 2023:6825-6843.
[10]	GENG Z, WANG J, LIU Z, et al. Reinforcement learning within tree search for fast macro placement[C]. In Proceedings of the 41st International Conference on Machine Learning(ICML'24), 2024, 235:15402-15417.
[11]	GU H, GU J, PENG K, et al. LAMPlace: Legalization-Aided Reinforcement Learning-Based Macro Placement for Mixed-Size Designs With Preplaced Blocks[J]. IEEE Transactions on Circuits and Systems II: Express Briefs, 2024: 3770-3774.
[12]	CHEN Y, MAI J, GAO X, et al. MacroRank: Ranking Macro Placement Solutions Leveraging Translation Equivariancy[C]. 2023 28th Asia and South Pacific Design Automation Conference (ASP-DAC), Tokyo, 2023: 258-263.
[13]	DENG J, LI Z, ZHANG J, et al. EGPlace: An efficient macro placement method via evolutionary search with greedy repositioning guided mutation[C]. Proceedings of the Forty-second International Conference on Machine Learning, 2025.
[14]	JARROD A, ROY D, PAPA S, et al. Capo: robust and scalable open-source min-cut floorplacer[C]. In Proceedings of the 2005 international symposium on Physical design (ISPD'05). Association for Computing Machinery, New York, NY, USA, 2005: 224-226.
[15]	CARL S. Chip-planning,placement, and global routing of macro/custom cell integrated circuits using simulated annealing[C]. 25th ACM/IEEE, Design Automation Conference.Proceedings 1988, Anaheim, CA, USA, 1988: 73-80.
[16]	CARL S, ALBERTO S. TimberWolf3.2: A New Standard Cell Placement and Global Routing Package[C]. 23rd ACM/IEEE Design Automation Conference, Las Vegas, NV, USA, 1986: 432-439.
[17]	LU J, CHEN P, CHANG C, et al. EPlace: Electrostatics-Based Placement Using Fast Fourier Transform and Nesterov's Method[J]. ACM Transactions on Design Automation of Electronic Systems, 2015: 20:34.
[18]	HO C, REN H. Large Language Model (LLM) for Standard Cell Layout Design Optimization[C]. IEEE LLM Aided Design Workshop (LAD), San Jose, CA, USA, 2024: 1-6.
[19]	ROY J, PAPA D, MARKOV I. Capo: Congestion-Driven Placement for Standard-cell and RTL Netlists with Incremental Capability[M]. Springer, Boston, 2007.
[20]	RAY B, BALACHANDRAN S. An efficient wirelength model for analytical placement[C]. 2013 Design, Automation & Test in Europe Conference & Exhibition(DATE). IEEE, 2013: 1711-1714.
[21]	YAO B, CHEN H, CHENG C, et al. Unified quadratic programming approach for mixed mode placement[C]. In Proceedings of the 2005 international symposium on Physical design (ISPD'05). Association for Computing Machinery, New York, 2005: 193-199.
[22]	CHEN T, JIANG Z, HSU T, et al. NTUplace3: An Analytical Placer for Large-Scale Mixed-Size Designs With Preplaced Blocks and Density Constraints[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(7): 1228-1240.
[23]	LU J, CHEN P, CHANG C, et al. ePlace: Electrostatics based placement using Nesterov’s method[C]. ACM/EDAC/IEEE Design Automation Conference (DAC), San Francisco, CA, USA, 2014: 1-6.
[24]	LIN Y, SHOUNAK D, WU L, et al. DREAMPIace: Deep Learning Toolkit-Enabled GPU Acceleration for Modern VLSI Placement[C]. 2019 56th ACM/IEEE Design Automation Conference (DAC), Las Vegas, NV, USA, 2019: 1-6.
[25]	LIN Y, JIANG Z, GU J, et al. DREAMPlace: Deep Learning Toolkit-Enabled GPU Acceleration for Modern VLSI Placement[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2021, 40: 748-761. doi: 10.1109/TCAD.2020.3003843
[26]	LIN Y, DAVID Z, REN H, et al. DREAMPlace 2.0: Open-Source GPU-Accelerated Global and Detailed Placement for Large-Scale VLSI Designs[C]. China Semiconductor Technology International Conference (CSTIC), Shanghai, 2020: 1-4.
[27]	GU J, JIANG Z, LIN Y, et al. DREAMPlace 3.0: Multi-Electrostatics Based Robust VLSI Placement with Region Constraints[C]. 2020 IEEE/ACM International Conference On Computer Aided Design (ICCAD), San Diego, CA, USA, 2020: 1-9.
[28]	LIAO P, LIU S, CHEN Z, et al. DREAMPlace 4.0: Timing-driven Global Placement with Momentum-based Net Weighting[C]. 2022 Design, Automation & Test in Europe Conference & Exhibition (DATE), Antwerp, Belgium, 2022: 939-944.
[29]	MIRHOSEINI A, GOLDIE A, YAZGAN M, et al. A graph placement methodology for fast chip design[J]. Nature, 2021, 594(7862): 207-212. doi: 10.1038/s41586-021-03544-w
[30]	LIU S, SUN Q, LIUAO P, et al. Global placement with deep learning-enabled explicit routability optimization[C]. 2021 Design, Automation & Test in Europe Conference & Exhibition(DATE). IEEE, 2021: 1821-1824.
[31]	LU Y, REN H, HSIAO H, et al. DREAM-GAN: Advancing DREAMPlace towards Commercial-Quality using Generative Adversarial Learning[C]. Proceedings of the 2023 International Symposium on Physical Design, 2023: 141-148.
[32]	LAI Y, MU Y, LUO P. Maskplace: Fast chip placement via reinforced visual representation learning[J]. Advances in Neural Information Processing Systems, 2022, 35: 24019-24030.
[33]	LIAO P, LIU H, LIN Y, et al. On a Moreau Envelope Wirelength Model for Analytical Global Placement[C]. 2023 60th ACM/IEEE Design Automation Conference (DAC). IEEE, 2023: 1-6.
[34]	LIU L, FU B, MARTIN D, et al. Xplace: an extremely fast and extensible global placement framework[C]. In Proceedings of the 59th ACM/IEEE Design Automation Conference (DAC'22). Association for Computing Machinery, New York, 2022.
[35]	解飞. 一种集成电路全局布局混合整数规划模型[J]. 运筹与模糊学, 2023, 13(4): 2878-2884.
[36]	YAO X, JIANG J, ZHAO Y, et al. Evolution of Optimization Algorithms for Global Placement via Large Language Models[J]. arXiv preprint arXiv:2504.17801, 2025.
[37]	CHENG C, KAHNG A, KANG I, et al. RePlAce: Advancing Solution Quality and Routability Validation in Global Placement[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019, 38(9): 1717-1730.
[38]	WANG B, SHEN G, LI D, et al. LHNN: Lattice hypergraph neural network for VLSI congestion prediction[C]. Proceedings of the 59th ACM/IEEE Design Automation Conference. 2022: 1297-1302.
[39]	BAEK K, PARK H, KIM S, et al. Pin accessibility and routing congestion aware drc hotspot prediction using graph neural network and u-net[C]. Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design. 2022: 1-9.
[40]	LIANG R, XIANG H, JUNG J, et al. A Stochastic Approach to Handle Non-Determinism in Deep Learning-Based Design Rule Violation Predictions[C]. Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design. 2022: 1-8.
[41]	CAI Z, ZOU P, WU Z, et al. PUFFER: A Routability-Driven Placement Framework via Cell Padding with Multiple Features and Strategy Exploration[C]. 2023 60th ACM/IEEE Design Automation Conference (DAC), San Francisco, CA, USA, 2023.
[42]	SHI Y, XU S, KAI S, et al. Timing-Driven Global Placement by Efficient Critical Path Extraction[C]. 2025 Design, Automation & Test in Europe Conference (DATE), Lyon, France, 2025.
[43]	于泓, 洪先龙, 蔡懿慈, 等. 一种新型宏模块和标准单元的混合模式布局算法[J]. 电子学报, 2000(5): 1-4.
[44]	张杰. 基于混合摆放技术的布局规划[J]. 中国集成电路, 2020, 29(Z3): 63-66.
[45]	CHENG R, YAN J. On joint learning for solving placement and routing in chip design[J]. Advances in Neural Information Processing Systems, 2021, 34: 16508-16519.
[46]	AGNESINA A, RAJVANSHI P, YANG T, et al. AutoDMP: Automated dreamplace-based macro placement[C]. Proceedings of the 2023 International Symposium on Physical Design, 2023: 149-157.
[47]	LU J, ZHUANG H, CHEN P, et al. ePlace-MS: Electrostatics-Based Placement for Mixed-Size Circuits[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2015, 34(5): 685-698. doi: 10.1109/TCAD.2015.2391263
[48]	CHEN Y, WEN Z, LIANG Y, et al. Stronger Mixed-Size Placement Backbone Considering Second-Order Information[C]. 2023 IEEE/ACM International Conference on Computer Aided Design (ICCAD), San Francisco, CA, USA, 2023.
[49]	PENG K, ZHU W. Pplace-MS: Methodologically Faster Poisson’s Equation-Based Mixed-Size Global Placement[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2024, 43(2): 613-626. doi: 10.1109/TCAD.2023.3320628
[50]	IM J, KANG S. SkyPlace: A New Mixed-size Placement Framework using Modularity-based Clustering and SDP Relaxation[C]. In Proceedings of the 61st ACM/IEEE Design Automation Conference (DAC'24). Association for Computing Machinery, New York, NY, USA, Article, 2024.
[51]	TEIG S. 2002. The X architecture: not your father’s diagonal wiring[C]. In Proceedings of the 2002 international workshop on System-level interconnect prediction (SLIP'02). Association for Computing Machinery, New York, NY, USA, 2002.
[52]	NIE S, CHEN Y, CHANG Y. 2022. Y-architecture-based flip-chip routing with dynamic programming-based bend minimization[C]. In Proceedings of the 59th ACM/IEEE Design Automation Conference (DAC'22). Association for Computing Machinery, New York, NY, USA, 2022.
[53]	ZHOU Z, ZHU Z, CHEN J, et al. Congestion-aware Global Routing using Deep Convolutional Generative Adversarial Networks[C]. 2019 ACM/IEEE 1st Workshop on Machine Learning for CAD (MLCAD), Canmore, AB, Canada, 2019.
[54]	LIAO H, ZHANG W, DONG X, et al. A Deep Reinforcement Learning Approach for Global Routing[J]. Journal of Mechanical Design, 2020, 142(6): 1-17
[55]	CHOI H, LEE M, LEE C, et al. Machine learning optimal ordering in global routing problems in semiconductors[J]. Scientific Reports, 2024, 14: 31077.
[56]	屈通, 盖天洋, 王书涵, 等. VLSI详细布线算法研究进展[J]. 微电子学与计算机, 2021, 38(11): 1-6.
[57]	CHO M, LU K, YUAN K, et al. BoxRouter 2.0: A Hybrid and Robust Global Router with Layer Assignment for Routability[J]. ACM Transactions on Design Automation of Electronic Systems, 2009, 14(2):1-21.
[58]	刘耿耿, 裴镇宇, 徐宁. 基于多阶段优化的高质量总体布线算法[J]. 计算机辅助设计与图形学学报, 2024, 36(4): 608-614.
[59]	LIU W, KAO W, LI Y, et al. NCTU-GR 2.0: Multithreaded Collision-Aware Global Routing With Bounded-Length Maze Routing[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2013, 32(5): 709-722. doi: 10.1109/TCAD.2012.2235124
[60]	LIU J, YOUNG E. EDGE: Efficient DAG-Based Global Routing Engine[C]. In Proceedings of the 60th Annual ACM/IEEE Design Automation Conference (DAC'23). IEEE Press, 2023.
[61]	LIU S, LIAO P, ZHANG R, et al. FastGR: Global Routing on CPU-GPU With Heterogeneous Task Graph Scheduler[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2023, 42(7): 2317-2330.
[62]	XU Y, ZHANG Y, CHU C. FastRoute 4.0: global router with efficient via minimization[C]. In Proceedings of the 2009 Asia and South Pacific Design Automation Conference. IEEE Press, 2009: 576-581.
[63]	CAO Z, JING T, XIONG J, et al. DpRouter: A fast and accurate dynamic-pattern-based global routing algorithm[C]. In 2007 Asia and South Pacific Design Automation Conference. IEEE, 2007.
[64]	CHU C, WONG Y. FLUTE: Fast Lookup Table Based Rectilinear Steiner Minimal Tree Algorithm for VLSI Design[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(1): 70-83. doi: 10.1109/TCAD.2007.907068
[65]	BLANKENBURG D, RABENSTEIN S, SACCARDI P. Continuous Global Routing[C]. International Conference on Operations Research. Springer, Cham, 2025.
[66]	SU M, DING H, WENG S, et al. High-Correlation 3D Routability Estimation for Congestion-guided Global Routing[C]. 2022 27th Asia and South Pacific Design Automation Conference (ASP-DAC), Taipei, Taiwan, 2022: 580-585.
[67]	QU T, LIN Y, LU Z, et al. Asynchronous reinforcement learning framework for net order exploration in detailed routing[C]. 2021 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE, 2021: 1815-1820.
[68]	CHENG R, LYU X, LI Y, et al. The policy-gradient placement and generative routing neural networks for chip design[J]. Advances in Neural Information Processing Systems, 2022, 35: 26350-26362.
[69]	朱自然, 陈建利, 朱文兴. 基于多阶段拆线重布的总体布线算法[J]. 计算机辅助设计与图形学学报, 2016, 28(11): 2000-2008.
[70]	YANG Z, VANNELLI A, AREIBO S. An ILP based hierarchical global routing approach for VLSI ASIC design[J]. Optimization Letters 2007, 1(3): 281-297. doi: 10.1007/s11590-006-0027-0
[71]	CHANG Y, LEE Y, GAO J, et al. NTHU-Route 2.0: A Robust Global Router for Modern Desig ns[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2010, 29(12): 1931-1944.
[72]	YEH Y, CHEN S, CHEN H, et al. 2023. DPRoute: Deep Learning Framework for Package Routing[C]. In Proceedings of the 28th Asia and South Pacific Design Automation Conference (ASPDAC'23). Association for Computing Machinery, New York, 2023: 277-282.
[73]	UTYAMISHEV D, PARTIN I. Late breaking results: A neural network that routes ICs[C]. 2020 57th ACM/IEEE Design Automation Conference(DAC). IEEE,2020: 1-2.
[74]	CHAN W, HO P, KAHNG A, et al. Routability optimization for industrial designs at sub-14nm process nodes using machine learning[C]. Proceedings of the 2017 ACM on International Symposium on Physical Design. 2017: 15-21.
[75]	YU C, ZHANG Z. Painting on placement: Forecasting routing congestion using conditional generative adversarial nets[C]. Proceedings of the 56th Annual Design Automation Conference 2019. 2019: 1-6.
[76]	CHEN J, KUANG J, ZHAO G, et al. PROS 2.0: A Plug-In for Routability Optimization and Routed Wirelength Estimation Using Deep Learning[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2023, 42(1): 164-177. doi: 10.1109/TCAD.2022.3168259
[77]	ISLAM R, CHALLAGUNDLA D. Pre-Global Routing DRC Violation Prediction Using Unsupervised Learning[C]. 2025 23rd IEEE Interregional NEWCAS Conference (NEWCAS), Paris, France, 2025:450-454.

参考文献	布局方法	GPU加速	布线驱动	时序驱动	布局器
[14]	划分式	否	否	否	Copa
[15][16]	启发式	否	否	否	TimerWolf
[22]	解析式	否	否	否	NTUPlace
[23]	解析式	否	否	否	ePlace
[24-28]	解析式	是	是	是	DREAMPlace
[31]	解析式	是	是	是	DREAM-GAN
[34]	解析式	是	否	否	Xplace
[37]	解析式	否	否	否	RePlAce
[41]	解析式	否	是	否	PUFFER
[46]	解析式	是	是	是	Autoplace
[47]	解析式	否	否	否	ePlace-MS
[49]	解析式	否	否	否	Pplace
[50]	解析式	是	否	否	SkyPlace

超大规模集成电路全局布局布线算法研究综述

A Survey of Research on Global Placement and Route Algorithm of Very Large Scale Integration

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 77

相关文章 0

编辑推荐

Metrics

本文评价