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]	Gong Xiaohang, Jiang Binze, Chen Xianglan, Gao Yinkang, Li Xi. Survey of Real-Time Computer System Architecture[J]. Journal of Computer Research and Development, 2023, 60(5): 1021-1036. DOI: 10.7544/issn1000-1239.202220731
[2]	Zhu Yi’an, Shi Xianchen, Yao Ye, Li Lian, Ren Pengyuan, Dong Weizhen, Li Jiayu. A WCET Analysis Method for Multi-Core Processors with Multi-Tier Coherence Protocol[J]. Journal of Computer Research and Development, 2023, 60(1): 30-42. DOI: 10.7544/issn1000-1239.202111244
[3]	Wang Chao, Chen Xianglan, Zhang Bo, Li Xi, Wang Chao, Zhou Xuehai. A Real-Time Processor Model with Timing Semantics[J]. Journal of Computer Research and Development, 2021, 58(6): 1176-1191. DOI: 10.7544/issn1000-1239.2021.20210157
[4]	Zhu Yi, Xiao Fangxiong, Zhou Hang, Zhang Guangquan. Method for Modeling and Analyzing Software Energy Consumption of Embedded Real-Time System[J]. Journal of Computer Research and Development, 2014, 51(4): 848-855.
[5]	Zhou Hang, Huang Zhiqiu, Zhu Yi, Xia Liang, Liu Linyuan. Real-Time Systems Contact Checking and Resolution Based on Time Petri Net[J]. Journal of Computer Research and Development, 2012, 49(2): 413-420.
[6]	Zhou Hang, Huang Zhiqiu, Hu Jun, Zhu Yi. Real-Time System Resource Conflict Checking Based on Time Petri Nets[J]. Journal of Computer Research and Development, 2009, 46(9): 1578-1585.
[7]	Guo Meng, Jian Fangjun, Zhang Qin, Xu Bin, Wang Zhensong, Han Chengde. FPGA-Based Real-Time Imaging System for Spaceborne SAR[J]. Journal of Computer Research and Development, 2007, 44(3).
[8]	Hu Xiao, Li Xi, and Gong Yuchang. High-Level Low-Power Synthesis of Real-Time Systems Using Time Petri Nets[J]. Journal of Computer Research and Development, 2006, 43(1): 176-184.
[9]	Li Guohui, Wang Hongya, Liu Yunsheng. Updates Dissemination in Mobile Real-Time Database Systems[J]. Journal of Computer Research and Development, 2005, 42(11): 2004-2009.
[10]	Zhu Xiangbin and Tu Shiliang. Analysis and Research of a Window-Constrained Real-Time System with Constraints[J]. Journal of Computer Research and Development, 2005, 42(8): 1445-1451.