A Bus Planning Algorithm for FPC Design in Complex Scenarios

WU Haoying; ZOU Sizhan; XU Ning; XIANG Shixu; LIU Mingyu

doi:10.23919/cje.2022.00.399

Volume 33 Issue 2

Mar. 2024

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2024 > 33(2): 346-352

Haoying WU, Sizhan ZOU, Ning XU, et al., “A Bus Planning Algorithm for FPC Design in Complex Scenarios,” Chinese Journal of Electronics, vol. 33, no. 2, pp. 346–352, 2024 doi: 10.23919/cje.2022.00.399

Citation:

Haoying WU, Sizhan ZOU, Ning XU, et al., “A Bus Planning Algorithm for FPC Design in Complex Scenarios,” Chinese Journal of Electronics, vol. 33, no. 2, pp. 346–352, 2024 doi: 10.23919/cje.2022.00.399

Citation:

PDF( 9771 KB)

A Bus Planning Algorithm for FPC Design in Complex Scenarios

doi: 10.23919/cje.2022.00.399

WU Haoying^1
,,
ZOU Sizhan^1
,,
XU Ning^{1
,
,},
XIANG Shixu^1
,,
LIU Mingyu^2
,

1.
School of Information Engineering, Wuhan University of Technology, Wuhan 430070, China
2.
Huawei Device Co., Ltd., Wuhan 430206, China

More Information

Author Bio:
Haoying WU received the B.S. and M.S. degrees in information engineering and the Ph.D. degree in the Key Laboratory of Fiber Optic Sensing Technology and Information Processing from the Wuhan University of Technology, China, in 1996, 2002, and 2009, respectively. She was with the Centre for Autonomous Systems, University of Technology Sydney, Sydney, Australia, from 2012 to 2013, as a Visiting Scholar. She is currently an Associate Professor at Wuhan University of Technology. Her current research interests include fiber optic sensing technology, physical human-robot interaction and control and electronic design automation. (Email: why_dd@whut.edu.cn)

Sizhan ZOU received the B.S. degree in information engineering from Wuhan University of Technology, China, in 2020. He is currently pursuing the M.S. degree in Wuhan University of Technology, China. His research interests include the electronic design automation. (Email: 142857@whut.edu.cn)

Ning XU received the Ph.D. degree in electronic science and technology from the University of Electronic Science and Technology of China, Chengdu, in 2003. Later, he was a Postdoctoral Fellow with Tsinghua University, Beijing, from 2003 to 2005. Currently, he is a Professor at the School of Information Engineering of Wuhan University of Technology, Wuhan. His research interests include computer aided design of VLSI circuits and systems, image processing, big data analysis, and artificial intelligence. (Email: xuning@whut.edu.cn)

Shixu XIANG received the B.E. degree from Wuhan University of Technology, Wuhan, China, in 2020. He is currently pursuing the M.E. degree in Wuhan University of Technology, Wuhan, China. His research interests include the fanout and routing of PCB. (Email: xiangshixu@whut.edu.cn)

Mingyu LIU received the B.E. degree from Huazhong University of Science and Technology, Wuhan, China, in 2001. He has more than 20 years of experience in product development and tool design. He is currently the Chief Architect of Huawei Terminal Tools Department, Director of R&D Tools and Automation Technical Management Group, he is now Level 6 Technical Expert. His current research interests include electronic design automation and automated test tools. (Email: liumingyu@huawei.com)
Corresponding author: Email: xuning@whut.edu.cn
Received Date: 2022-11-23
Accepted Date: 2023-02-06

Available Online: 2023-02-16

Publish Date: 2024-03-05

Abstract

Abstract

Flexible printed circuit (FPC) design in complex scenarios has a list of pin concentration areas, which lead to extremely congested intersection regions while connecting the pins. Currently, it is challenging to explore the routability and to find topologically non-crossing and routable paths manually for the nets timely. The existing bus planning methods cannot offer optimal solutions concerning the special resource distribution of the FPC design. To investigate an effective way to shorten the routing time of FPC and achieve enhanced performance, a bus planning algorithm is proposed to tackle complex area connection problems. On the basis of the pin location information, the routing space is partitioned and generally represented as an undirected graph, and the topological non-crossing relationship between different regions is obtained using the dynamic pin sequence. Considering the routability and electrical constraints, a heuristic algorithm is proposed to search the optimal location of the crossing point on the region boundary. Experimental results on industrial cases show that the proposed algorithm realize better performance in terms of count and routability in comparison with numerous selected state-of-the-art router and methods.
- Flexible printed circuit,
- Routability,
- Non-crossing topology,
- Heuristic algorithm

FullText(HTML)

References(13)

References

[1]	M. Y. Liu, H. Y. Wu, N, Xu, et al., “Thoughts on the development of PCB design automation industry in China under the new situation,” Communication of Chinese Computer Society, vol. 17, no. 4, pp. 52–58, 2021. (in Chinese)
[2]	J. T. Yan, “Bus assignment considering flexible escape routing for layer minimization in PCB designs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 41, no. 8, pp. 2699–2713, 2022. doi: 10.1109/TCAD.2021.3112882
[3]	Q. Ma, E. F. Y. Young, and M. D. F. Wong, “An optimal algorithm for layer assignment of bus escape routing on PCBs,” in Proceedings of the 2011 48th ACM/EDAC/IEEE Design Automation Conference (DAC), San Diego, CA, USA, pp.176–181, 2011.
[4]	J. T. Yan, “Efficient layer assignment of bus-oriented nets in high-speed PCB designs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 35, no. 8, pp. 1332–1344, 2016. doi: 10.1109/TCAD.2015.2504898
[5]	J. T. Yan, “Direction-constrained rectangle escape routing,” ACM Transactions on Design Automation of Electronic Systems, vol. 23, no. 3, article no. 34, 2018. doi: 10.1145/3178047
[6]	H. Kong, T. Yan, and M. D. F. Wong, “Automatic bus planner for dense PCBs,” in Proceedings of the 2009 46th ACM/IEEE Design Automation Conference (DAC), San Francisco, CA, USA, pp.326–331, 2009.
[7]	M. M. Ozdal and M. D. F. Wong, “Algorithms for simultaneous escape routing and layer assignment of dense PCBs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 8, pp. 1510–1522, 2006. doi: 10.1109/TCAD.2005.857376
[8]	B. Wang, H. Y. Wu, and M. Y. Liu, “Resource allocation applied to flexible printed circuit routing based on constrained Delaunay triangulation,” Integration, vol. 87, pp. 16–23, 2022. doi: 10.1016/j.vlsi.2022.05.008
[9]	B. Y. Ma, N. Xu, H. Y. Wu, et al., “Routing algorithm for flexible printed circuit channel area,” Journal of Computer-Aided Design & Computer Graphics, vol. 34, no. 8, pp. 1179–1185, 2022. (in Chinese) doi: 10.3724/SP.J.1089.2022.19465
[10]	C. Y. Chin, C. Y. Kuan, T. Y. Tsai, et al., “Escaped boundary pins routing for high-speed boards,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 32, no. 3, pp. 381–391, 2013. doi: 10.1109/TCAD.2012.2221714
[11]	FreeRouting. Available at: https://freerouting.org/.
[12]	T. C. Lin, D. Merrill, Y. Y. Wu, et al., “A unified printed circuit board routing algorithm with complicated constraints and differential pairs,” in Proceedings of the 2021 26th Asia and South Pacific Design Automation Conference (ASP-DAC), Tokyo, Japan, pp.170–175, 2021.
[13]	L. McMurchie and C. Ebeling, “PathFinder: A negotiation-based performance-driven router for FPGAs,” in Proceedings of the 1995 Third International ACM Symposium on Field-Programmable Gate Arrays, Napa Valley, CA, USA, pp.111–117, 1995.