A High-Quality and Efficient Bus-Aware Global Router

Liu Genggeng; Wei Ling; Yu Yantao; Xu Ning

doi:10.23919/cje.2023.00.061

Article Contents

Article Navigation > Chinese Journal of Electronics > 2025 > Uncorrected proof

Genggeng Liu, Ling Wei, Yantao Yu, et al., “A High-Quality and Efficient Bus-Aware Global Router,” Chinese Journal of Electronics, vol. 34, no. 2, pp. 1–13, 2025 doi: 10.23919/cje.2023.00.061

Citation:

Genggeng Liu, Ling Wei, Yantao Yu, et al., “A High-Quality and Efficient Bus-Aware Global Router,” Chinese Journal of Electronics, vol. 34, no. 2, pp. 1–13, 2025 doi: 10.23919/cje.2023.00.061

Genggeng Liu, Ling Wei, Yantao Yu, et al., “A High-Quality and Efficient Bus-Aware Global Router,” Chinese Journal of Electronics, vol. 34, no. 2, pp. 1–13, 2025 doi: 10.23919/cje.2023.00.061

Citation:

PDF( 8239 KB)

A High-Quality and Efficient Bus-Aware Global Router

doi: 10.23919/cje.2023.00.061

Liu Genggeng^{1, 2
,},
Wei Ling^{1, 2
,},
Yu Yantao^{1, 2
,},
Xu Ning^{3
,
,}

1.
College of Computer and Data Science, Fuzhou University, Fuzhou, China
2.
Fujian Key Laboratory of Network Computing and Intelligent Information Processing, Fuzhou, China
3.
School of Information Engineering, Wuhan University of Technology, Wuhan, China

More Information

Author Bio:
Genggeng Liu was born in 1988. He received the B.S. degree in computer science and the Ph.D. degree in applied mathematics from Fuzhou University, Fuzhou, China, in 2009 and 2015, respectively. He is a Professor at the College of Computer and Data Science of Fuzhou University. His main research interests include design automation for microfluidic biochips and integrated circuits.(Email: liugenggeng@fzu.edu.cn)

Ling Wei was born in 1999. He received M.S. degree with the College of Computer and Data Science, Fuzhou University, Fuzhou, China. His main research interests include VLSI routing. (Email: 2744870231@qq.com)

Yantao Yu was born in 2000. He is currently pursuing the M.S. degree with the College of Computer and Data Science, Fuzhou University, Fuzhou, China. His main research interests include VLSI routing. (Email: 221027126@fzu.edu.cn)

Ning Xu was born in 1968. He received his Ph.D. degree in electronic science and technology from the University of Electronic Science and Technology of China in 2003. Later, he was a Postdoctoral Fellow with Tsinghua University from 2003 to 2005. Currently, he is a Professor at the Computer Science Department of Wuhan University of Technology. His research interests include computer-aided design of VLSI circuits and systems, computer architectures, data mining, and highly combinatorial optimization algorithms. (Email: Xuning@whut.edu.cn)
Corresponding author: Email: Xuning@whut.edu.cn
Received Date: 2024-03-15
Accepted Date: 2024-05-31

Available Online: 2024-07-20

Abstract

Abstract

As advanced technology nodes enter the nanometer era, the complexity of integrated circuit (IC) design is increasing, and the proportion of bus in the net is increasing. The bus routing has become a key factor affecting the performance of the chip. In addition, the existing research does not distinguish between buses and non-buses in the complete global routing process, which directly leads to the expansion of bus deviation and the degradation of chip performance. In order to solve these problems, we propose a high-quality and efficient bus-aware global router, which includes the following key strategies: 1) By introducing the routing density graph, we propose a routing model that can simultaneously consider the routability of non-buses and the deviation value of buses. 2) A dynamic routing resource adjustment algorithm is proposed to optimize the bus deviation and wirelength simultaneously, which can effectively reduce the bus deviation. 3) We propose a layer assignment algorithm consider deviation to significantly reduce the bus deviation of the 3D routing solution. 4) A DFS-based algorithm is proposed to obtain multiple routing solutions, from which the routing result with the lowest deviation is selected. Experimental results show that the proposed algorithm can effectively reduce bus deviation with the existing algorithms, so as to obtain high-quality 2D and 3D routing solutions considering bus deviation.
- Global routing,
- Layer assignment,
- Bus deviation,
- Physical design,
- Bus routing

FullText(HTML)

References(34)

References

[1]	W. Wolf, Modern VLSI Design: IP-Based Design, 4th ed., Pearson, New York, NY, USA, 2008.
[2]	D. R. Liu, B. Yu, V. Livramento, et al., “Synergistic topology generation and route synthesis for on-chip performance-critical signal groups,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 38, no. 6, pp. 1147–1160, 2019. doi: 10.1109/TCAD.2018.2834424
[3]	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
[4]	A. B. Kahng, J. Lienig, I. L. Markov, et al., VLSI Physical Design: From Graph Partitioning to Timing Closure. Springer, Dordrecht, The Netherlands, 2011.
[5]	M. Pan and C. Chu, “FastRoute: A step to integrate global routing into placement,” in Proceedings of 2006 IEEE/ACM International Conference on Computer-Aided Design, San Jose, CA, USA, pp. 464–471, 2006.
[6]	Z. Cao, T. T. Jing, J. J. Xiong, et al., “Fashion: A fast and accurate solution to global routing problem,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 4, pp. 726–737, 2008. doi: 10.1109/TCAD.2008.917590
[7]	M. Pan and C. Chu, “FastRoute 2.0: A high-quality and efficient global router,” in Proceedings of 2007 Asia and South Pacific Design Automation Conference, Yokohama, Japan, pp. 250–255, 2007.
[8]	F. Mo and R. K. Brayton, “Semi-detailed bus routing with variation reduction,” in Proceedings of 2007 International Symposium on Physical Design, Austin, TX, USA, pp. 143–150, 2007.
[9]	Z. Zhang, A. Greiner, and S. Taktak, “A reconfigurable routing algorithm for a fault-tolerant 2D-mesh network-on-chip”, in Proceedings of the 45th Annual Design Automation Conference, New York, NY, USA, pp. 441–446, 2008.
[10]	H. Y. Chen, C. H. Hsu, and Y. W. Chang, “High-performance global routing with fast overflow reduction,” in Proceedings of 2009 Asia and South Pacific Design Automation Conference, Yokohama, Japan, pp. 582–587, 2009.
[11]	J. R. Gao, P. C. Wu, and T. C. Wang, “A new global router for modern designs,” in Proceedings of 2008 Asia and South Pacific Design Automation Conference, Seoul, South Korea, pp. 232–237, 2008.
[12]	K. R. Dai, W. H. Liu, and Y. L. Li, “Efficient simulated evolution based rerouting and congestion-relaxed layer assignment on 3-D global routing,” in Proceedings of 2009 Asia and South Pacific Design Automation Conference, Yokohama, Japan, pp. 570–575, 2009.
[13]	W. H. Liu, W. C. Kao, Y. L. Li, et al., “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, vol. 32, no. 5, pp. 709–722, 2013. doi: 10.1109/TCAD.2012.2235124
[14]	Y. J. Chang, Y. T. Lee, J. R. Gao, et al., “NTHU-Route 2.0: A robust global router for modern designs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 29, no. 12, pp. 1931–1944, 2010. doi: 10.1109/TCAD.2010.2061590
[15]	T. H. Lee and T. C. Wang, “Congestion-constrained layer assignment for via minimization in global routing,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 9, pp. 1643–1656, 2008. doi: 10.1109/TCAD.2008.927733
[16]	D. R. Liu, B. Yu, S. Chowdhury, et al., “TILA-S: Timing-driven incremental layer assignment avoiding slew violations,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 37, no. 1, pp. 231–244, 2018. doi: 10.1109/TCAD.2017.2652221
[17]	S. Y. Han, W. H. Liu, R. Ewetz, et al., “Delay-driven layer assignment for advanced technology nodes,” in Proceedings of the 2017 22nd Asia and South Pacific Design Automation Conference, Chiba, Japan, pp. 456–462, 2017.
[18]	X. H. Zhang, Z. Zhuang, G. G. Liu, et al., “MiniDelay: Multi-strategy timing-aware layer assignment for advanced technology nodes,” in Proceedings of 2020 Design, Automation & Test in Europe Conference & Exhibition, Grenoble, France, pp. 586–591, 2020.
[19]	K. Pandiaraj, P. Sivakumar, and K. J. Prakash, “Machine learning based effective linear regression model for TSV layer assignment in 3D IC,” Microprocessors and Microsystems, vol. 83, article no. 103953, 2021. doi: 10.1016/j.micpro.2021.103953
[20]	O. He, S. Q. Dong, J. N. Bian, et al., “Bus via reduction based on floorplan revising,” in Proceedings of the 20th Symposium on Great Lakes Symposium on VLSI, Providence, RI, USA, pp. 9–14, 2010.
[21]	P. H. Wu and T. Y. Ho, “Bus-driven floorplanning with bus pin assignment and deviation minimization,” Integration, vol. 45, no. 4, pp. 405–426, 2012. doi: 10.1016/j.vlsi.2011.11.012
[22]	M. Mustafa Ozdal and M. D. F. Wong, “A length-matching routing algorithm for high-performance printed circuit boards,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 12, pp. 2784–2794, 2006. doi: 10.1109/TCAD.2006.882584
[23]	Y. Xu, Y. H. Zhang, and C. Chu, “FastRoute 4.0: Global router with efficient via minimization,” in Proceedings of 2009 Asia and South Pacific Design Automation Conference, Yokohama, Japan, pp. 576–581, 2009.
[24]	T. Yan and M. D. F. Wong, “BSG-Route: A length-constrained routing scheme for general planar topology,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 28, no. 11, pp. 1679–1690, 2009. doi: 10.1109/TCAD.2009.2030352
[25]	R. Zhang, T. Y. Pan, L. Zhu, et al., “A length matching routing method for disordered pins in PCB design,” in Proceedings of the 20th Asia and South Pacific Design Automation Conference, Chiba, Japan, pp. 402–407, 2015.
[26]	P. X. Liao and T. C. Wang, “A bus-aware global router,” in Proceedings of Synthesis and System Integration of Mixed Information Technologies, Kyoto, Japan, pp. 20–25, 2018.
[27]	W. D. Zhu, X. H. Zhang, G. G. Liu, et al., “MiniDeviation: An efficient multi-stage bus-aware global router,” in Proceedings of 2020 International Symposium on VLSI Design, Automation and Test, Hsinchu, China, pp. 1–4, 2020.
[28]	H. T. Zhang, M. Fujita, C. K. Cheng, et al., “SAT-based on-track bus routing,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 40, no. 4, pp. 735–747, 2021. doi: 10.1109/TCAD.2020.3007253
[29]	A. Liao, H. Chang, O. Chi, et al., “ICCAD 2018 CAD contest obstacle-aware on-track bus routing,” Available at: https://drive.google.com/file/d/16dNYQDnR9aUZ4F6cs33X-MeWjXOM8vfn/view, 2018-09-14.
[30]	C. H. Hsu, S. C. Hung, H. Chen, et al., “A DAG-based algorithm for obstacle-aware topology-matching on-track bus routing,” in Proceedings of the 56th Annual Design Automation Conference 2019, Las Vegas, NV, USA, article no. 217, 2019.
[31]	J. S. Chen, J. W. Liu, G. J. Chen, et al., “MARCH: MAze routing under a concurrent and hierarchical scheme for buses,” in Proceedings of the 56th Annual Design Automation Conference 2019, Las Vegas, NV, USA, article no. 216, 2019.
[32]	D. Kim, S. Do, S. Y. Lee, et al., “Compact topology-aware bus routing for design regularity,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 39, no. 8, pp. 1744–1749, 2020. doi: 10.1109/TCAD.2019.2926484
[33]	Y. H. Cheng, T. C. Yu, and S. Y. Fang, “Obstacle-avoiding length-matching bus routing considering nonuniform track resources,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 28, no. 8, pp. 1881–1892, 2020. doi: 10.1109/TVLSI.2020.2985312
[34]	Z. R. Zhu, Z. P. Huang, J. L. Chen, et al., “Topology-aware bus routing in complex networks of very-large-scale integration with nonuniform track configurations and obstacles,” Complexity, vol. 2021, article no. 8843271, 2021. doi: 10.1155/2021/8843271