A Weighted Directed Graph-Based Algorithm for Group Routing in Printed Circuit Boards

Deng Xinguo; Zhang Xinhong; Chen Jiarui; Liu Qinghai; Chen Chuandong

doi:10.7544/issn1000-1239.202440069

Journal of Computer Research and Development > 2025 > Accepted Manuscript > DOI: 10.7544/issn1000-1239.202440069 CSTR: 32373.14.issn1000-1239.202440069

Deng Xinguo, Zhang Xinhong, Chen Jiarui, Liu Qinghai, Chen Chuandong. A Weighted Directed Graph-Based Algorithm for Group Routing in Printed Circuit Boards[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202440069

Citation:

PDF (1756 KB)

A Weighted Directed Graph-Based Algorithm for Group Routing in Printed Circuit Boards

1.
College of Computer and Data Science, Fuzhou University, Fuzhou 350108
2.
Center for Discrete Mathematics, Fuzhou University, Fuzhou 350108
3.
Fujian Science & Technology Innovation Laboratory for Optoelectronic Information of China, Fuzhou 350024
4.
College of Physics and Information Engineering, Fuzhou University, Fuzhou 350108

Funds: This work was supported by the National Natural Science Foundation of China (61977017) and the National Key Research and Development Program of Fujian Laboratory for Optoelectronic Information Science and Technology Innovation (MINDU Innovation Laboratory)(2021ZR142).

More Information

Author Bio:
Deng Xinguo: born in 1975. PhD, associate professor. His main research interest includes electronic design automation

Zhang Xinhong: born in 1998. Master. His main research interest includes electronic design automation

Chen Jiarui: born in 1981. PhD, associate professor. His main research interest includes electronic design automation

Liu Qinghai: born in 1982. PhD, professor. Member of CCF. His main research interest includes Web mining, information retrieval, and machine learning

Chen Chuandong: born in 1982. PhD, associate professor. His main research interest includes electronic design automation
Received Date: February 03, 2024
Revised Date: March 31, 2024
Accepted Date: March 02, 2025
Available Online: March 02, 2025

Graphical Abstract

Abstract

Abstract

Routing is considered an essential component in the design of printed circuit board (PCB). Current existing PCB designs mostly rely on the process results from electronic design automation tools, and traditional automatic routing research often focuses on only general bus routing without considering bus groups to be determined during the routing process. Due to the absence of general bus grouping, there may be situations where there are more nets in one group than in other groups, resulting in larger line width and line clearance occupied by this group when compared to other bus groups in the original bus routing, thereby posing new challenges to effective and efficient routing. To overcome this drawback, this paper focuses on studying PCB group routing. In this study, a group routing algorithm based on a weighted directed graph is proposed. A Hanan grid graph is constructed, containing only merged edges and their adjacent relationships. Following this, a weighted directed graph is developed using the merged edge information to represent the routing resources on the circuit board. For routing planning, a heuristic search algorithm equipped with multi-wire avoidance features is utilized. The routing situations are then classified into several potential scenarios, with each considered separately, to accomplish detailed routing and obtain a final result of group routing. Results from experiments demonstrate that a 100% routability is consistently achieved by using the algorithm on complex industrial examples that have been previously tested, and that the design rule constraints of all benchmark industrial PCB cases are not violated.
- electronic design automation,
- printed circuit board,
- group routing,
- weighted directed graph,
- path planning

FullText(HTML)

References (31)

References

[1]	Hsu J, Hung G, Tseng J, et al. High-speed data center PCB design challenges and findings by Intel® automatic in-board characterization[C/OL]// Proc of the 17th Int Microsystems, Packaging, Assembly and Circuits Technology Conf. Piscataway, NJ: IEEE, 2022[2024-04-08]. https://ieeexplore.ieee.org/document/9966724
[2]	Tan Yan. Algorithmic studies on PCB routing[D]. Urbana-Champaign: University of Illinois at Urbana-Champaign, 2010: 15−27
[3]	Lin S T, Wang H H, Kuo C Y, et al. A complete PCB routing methodology with concurrent hierarchical routing[C]//Proc of the 58th ACM/IEEE Design Automation Conf. Piscataway, NJ: IEEE, 2021: 1141−1146
[4]	Lin T C, Merrill D, Wu Y Y, et al. A unified printed circuit board routing algorithm with complicated constraints and differential pairs[C]//Proc of the 26th Asia and South Pacific Design Automation Conf. New York: ACM, 2021: 170−175
[5]	邓新国,叶似锦,陈家瑞,等. 结合改进A算法与拆线重布的有序逃逸布线[J]. 电子与信息学报,2021,43(6):1609−1616 doi: 10.11999/JEIT201033 Deng Xinguo, Ye Sijin, Chen Jiarui, et al. Ordered escape routing combining improved A algorithm with rip-up and reroute[J]. Journal of Electronics & Information Technology, 2021, 43(6): 1609−1616 (in Chinese) doi: 10.11999/JEIT201033
[6]	Save Y D, Rakhi R, Shambhulingayya N D, et al. Oscad: An open source EDA tool for circuit design, simulation, analysis and PCB design[C]//Proc of the 20th Int Conf on Electronics, Circuits, and Systems. Piscataway, NJ: IEEE, 2013: 851−854
[7]	Goyal P, Agrawal H, Paradiso J A, et al. BoardLab: PCB as an interface to EDA software[C]//Proc of the 26th Annual ACM Symp on the Djunct Publication of the User Interface Software and Technology. New York: ACM, 2013: 19−20
[8]	CAMA). Piscataway,NJ:IEEE,2018[2024-04-08]. https://ieeexplore.ieee.org/document/8530652 (没有届 Wane S, Patton R, Gross N. Unification of instrumentation and EDA tooling platforms for enabling smart chip-package-PCB-probe arrays co-design solutions using advanced RFIC technologies[C/OL]//Proc of the 2018 IEEE Conf on Antenna Measurements & Applications
[9]	Sherwani N A. Algorithms for VLSI Physical Design Automation[M]. 3rd ed. Berlin: Springer, 2012
[10]	Fang S C, Chang K E, Feng W S, et al. Constrained via minimization with practical considerations for multi-layer VLSI/PCB routing problems[C]//Proc of the 28th ACM/IEEE Design Automation Conf. Piscataway, NJ: IEEE, 1991: 60−65
[11]	Zhang Cong, Jin Huilin, Chen Jienan, et al. A hierarchy MCTS algorithm for the automated PCB routing[C]//Proc of the 16th Int Conf on Control & Automation. Piscataway, NJ: IEEE, 2020: 1366−1371
[12]	Kahng A B,Lienig J. 超大规模集成电路物理设计:从图分割到时序收敛[M]. 于永斌,冯策,徐宁,等,译. 2版. 北京:机械工业出版社,2024 Kahng A B, Lienig J. Software Engineering: A Practitioner's Approach[M]. Translated by Yu Yongbin, Feng Ce, Xu Ning, et al. 2nd ed. Beijing: China Machine Press, 2024 (in Chinese)
[13]	Kong Hui, Ma Qiang, Yan Tan, et al. An optimal algorithm for finding disjoint rectangles and its application to PCB routing[C]//Proc of the 47th Design Automation Conf. Piscataway, NJ: IEEE, 2010: 212−217
[14]	Zhang Jixin, Xu Ning, Liu Mingyu. FanoutNet: A neuralized PCB fanout automation method using deep reinforcement learning[C]// Proc of the 37th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2023: 8554−8561
[15]	He Youbiao, Li Hebi, Jin Tian, et al. Circuit routing using monte carlo tree search and deep reinforcement learning[C/OL]//Proc of the 2022 Int Symp on VLSI Design, Automation and Test. Piscataway, NJ: IEEE, 2022[2024-04-08]. https://ieeexplore.ieee.org/document/9768074
[16]	刘郭庆,钱宇华,张亚宇,等. 给定预算下基于相对熵置信区间的蒙特卡洛树搜索最优动作识别算法[J]. 计算机研究与发展,2023,60(8):1780−1794 doi: 10.7544/issn1000-1239.202330257 Liu Guoqing, Qian Yuhua, Zhang Yayu, et al. Best action identification algorithm in Monte Carlo tree search based on relative entropy confidence interval with given budget[J]. Journal of Computer Research and Development, 2023, 60(8): 1780−1794 (in Chinese) doi: 10.7544/issn1000-1239.202330257
[17]	Goh Y, Jung D, Hwang G, et al. Consumer electronics product manufacturing time reduction and optimization using AI-based PCB and VLSI circuit designing[J]. IEEE Transactions on Consumer Electronics, 2023, 69(3): 240−249
[18]	Hung S C, Chen Hao, Sun Fankeng, et al. A DAG-based algorithm for obstacle-aware topology-matching on-track bus routing[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 40(3): 533−546
[19]	Chen Jingsong, Kuang Jian, Zhao Guowei, 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, 2022, 42(1): 164−177
[20]	Zhang H T, Fujita M, Cheng C K, et al. SAT-based on-track bus routing[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 40(4): 735−747
[21]	Chen Jingsong, Liu Jinwei, Chen Gengjie, et al. MARCH: Maze routing under a concurrent and hierarchical scheme for buses[C/OL]// Proc of the 56th Annual Design Automation Conf 2019. Piscataway, NJ: IEEE, 2019[2024-04-08]. https://ieeexplore.ieee.org/document/8807035
[22]	Kim D, Do S, Lee S Y, et al. Compact topology-aware bus routing for design regularity[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019, 39(8): 1744−1749
[23]	Cheng Yihao, Yu Taochun, Fang Shaoyun. Obstacle-avoiding length-matching bus routing considering nonuniform track resources[J]. IEEE Transactions on Very Large Scale Integration Systems, 2020, 28(8): 1881−1892
[24]	Yan Jintai,Chen Zhiwei. Obstacle-aware length-matching bus routing[C]//Proc of the 2011 Int Symp on Physical Design. New York:ACM,2011:61−68(没有届
[25]	Yan Jintai. Single-layer obstacle-aware multiple-bus routing considering simultaneous escape length[J]. IEEE Transactions on Components, Packaging and Manufacturing Technology, 2022, 12(6): 902−915
[26]	Kong Hui, Yan Tan, Wong M D F. Automatic bus planner for dense PCBs[C]//Proc of the 46th ACM/IEEE Design Automation Conf. Piscataway, NJ: IEEE, 2009: 326−331
[27]	Wu Peici, Ma Qiang, Wong M D F. An ILP-based automatic bus planner for dense PCBs[C]//Proc of the 18th Asia and South Pacific Design Automation Conf. Piscataway, NJ: IEEE, 2013: 181−186
[28]	Tang Hao,Liu Genggeng,Chen Xiaohua,et al. A survey on steiner tree construction and global routing for VLSI design[J]. IEEE Access,2020,8:68593-68622(只有卷
[29]	Zachariasen M. A catalog of Hanan grid problems[J]. Networks: An International Journal, 2001, 38(2): 76−83
[30]	赵奇,赵阿群. 一种基于A算法的多径寻由算法[J]. 电子与信息学报,2013,35(4):952−957 Zhao Qi, Zhao Aqun. A multi-path routing algorithm base on A algorithm[J]. Journal of Electronics & Information Technology, 2013, 35(4): 952−957 (in Chinese)
[31]	马博宇,徐宁,吴皓莹,等. 面向柔性电路通道区的自动布线算法[J]. 计算机辅助设计与图形学学报,2022,34(8):1179−1185 Ma Boyu, Xu Ning, Wu Haoying, et al. Routing Algorithm for flexible printed circuit channel area[J]. Journal of Computer-Aided Design & Computer Graphics, 2022, 34(8): 1179−1185 (in Chinese)

[1]	Jin Dongming, Jin Zhi, Chen Xiaohong, Wang Chunhui. ChatModeler: A Human-Machine Collaborative and Iterative Requirements Elicitation and Modeling Approach via Large Language Models[J]. Journal of Computer Research and Development, 2024, 61(2): 338-350. DOI: 10.7544/issn1000-1239.202330746
[2]	Wang Juanjuan, Wang Hongan. Multi-Agent Multi-Criticality Scheduling Based Self-Healing System of Power Grid[J]. Journal of Computer Research and Development, 2017, 54(4): 720-730. DOI: 10.7544/issn1000-1239.2017.20161026
[3]	He Wenbin, Liu Qunfeng, Xiong Jinzhi. The Error Theory of Polynomial Smoothing Functions for Support Vector Machines[J]. Journal of Computer Research and Development, 2016, 53(7): 1576-1585. DOI: 10.7544/issn1000-1239.2016.20148462
[4]	He Wangquan, Wei Di, Quan Jianxiao, Wu Wei, Qi Fengbin. Dynamic Task Scheduling Model and Fault-Tolerant via Queuing Theory[J]. Journal of Computer Research and Development, 2016, 53(6): 1271-1280. DOI: 10.7544/issn1000-1239.2016.20148445
[5]	Zhao Yu, Wang Yadi, Han Jihong, Fan Yudan, and Zhang Chao. A Formal Model for Cryptographic Protocols Based on Planning Theory[J]. Journal of Computer Research and Development, 2008, 45(9).
[6]	Shi Jin, Lu Yin, and Xie Li. Dynamic Intrusion Response Based on Game Theory[J]. Journal of Computer Research and Development, 2008, 45(5): 747-757.
[7]	Li Ye, Cai Yunze, Yin Rupo, Xu Xiaoming. Support Vector Machine Ensemble Based on Evidence Theory for Multi-Class Classification[J]. Journal of Computer Research and Development, 2008, 45(4): 571-578.
[8]	Lin Jianning, Wu Huizhong. Research on a Trust Model Based on the Subjective Logic Theory[J]. Journal of Computer Research and Development, 2007, 44(8): 1365-1370.
[9]	He Lijian and Zhang Wei. An Agent Organization Structure for Solving DCOP Based on the Partitions of Constraint Graph[J]. Journal of Computer Research and Development, 2007, 44(3).
[10]	Mu Kedian and Lin Zuoquan. Symbolic Dempster-Shafer Theory[J]. Journal of Computer Research and Development, 2005, 42(11): 1833-1842.