XGRouter: high-quality global router in X-architecture with particle swarm optimization

doi:10.1007/s11704-015-4017-1

Front. Comput. Sci.

2015, Vol. 9

Issue (4) : 576-594 https://doi.org/10.1007/s11704-015-4017-1

RESEARCH ARTICLE

XGRouter: high-quality global router in X-architecture with particle swarm optimization

Genggeng LIU¹,Wenzhong GUO^1,^2,^*(

),Rongrong LI¹,Yuzhen NIU¹,Guolong CHEN^1,²

1. College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China
2. Fujian Provincial Key Laboratory of Network Computing and Intelligent Information Processing, Fuzhou University, Fuzhou 350116, China

Download: PDF(816 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

This paper presents a high-quality very large scale integration (VLSI) global router in X-architecture, called XGRouter, that heavily relies on integer linear programming (ILP) techniques, partition strategy and particle swarm optimization (PSO). A new ILP formulation, which can achieve more uniform routing solution than other formulations and can be effectively solved by the proposed PSO is proposed. To effectively use the new ILP formulation, a partition strategy that decomposes a large-sized problem into some small-sized sub-problems is adopted and the routing region is extended progressively from the most congested region. In the post-processing stage of XGRouter, maze routing based on new routing edge cost is designed to further optimize the total wire length and mantain the congestion uniformity. To our best knowledge, XGRouter is the first work to use a concurrent algorithm to solve the global routing problem in X-architecture. Experimental results show that XGRouter can produce solutions of higher quality than other global routers. And, like several state-of-the-art global routers, XGRouter has no overflow.

Keywords global routing overflow total wire length congestion uniformity X-architecture particle swarm optimization integer linear programming

Corresponding Author(s): Wenzhong GUO

Issue Date: 07 September 2015

Cite this article:

Genggeng LIU,Wenzhong GUO,Rongrong LI, et al. XGRouter: high-quality global router in X-architecture with particle swarm optimization[J]. Front. Comput. Sci., 2015, 9(4): 576-594.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-015-4017-1
https://academic.hep.com.cn/fcs/EN/Y2015/V9/I4/576

1	Chang Y J, Lee Y T, Gao J R, Wu P C, Wang T C. NTHU-route 2.0: a robust global router for modern designs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2010, 29(12): 1931&horbar;1944 https://doi.org/10.1109/TCAD.2010.2061590
2	Roy J A, Markov I L. High-performance routing at the nanometer scale. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(6): 1066&horbar;1077 https://doi.org/10.1109/TCAD.2008.923255
3	Zhang Y, Xu Y, Chu C. FastRoute3.0: a fast and high quality global router based on virtual capacity. In: Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design. 2008, 344&horbar;349 https://doi.org/10.1109/ICCAD.2008.4681596
4	Dai K R, Liu W H, Li Y L. NCTU-GR: efficient simulated evolutionbased rerouting and congestion-relaxed layer assignment on 3-D global routing. IEEE Transactions on Very Large Scale Integration Systems, 2012, 20(3): 459&horbar;472 https://doi.org/10.1109/TVLSI.2010.2102780
5	Moffitt M D. Maizerouter: engineering an effective global router. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(11): 2017&horbar;2026 https://doi.org/10.1109/TCAD.2008.2006082
6	Ao J, Dong S, Chen S, Goto S. Delay-driven layer assignment in global routing under multi-tier interconnect structure. In: Proceedings of the 2013 ACM International Symposium on International Symposium on Physical Design. 2013, 101&horbar;107 https://doi.org/10.1145/2451916.2451942
7	Ozdal M M, Wong M D F. Archer: a history-based global routing algorithm. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2009, 28(4): 528&horbar;540 https://doi.org/10.1109/TCAD.2009.2013991
8	Liu W H, Kao W C, Li Y L, Chao K Y. 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, 2013, 32(5):709&horbar;722 https://doi.org/10.1109/TCAD.2012.2235124
9	Cho M, Pan D Z. BoxRouter: a new global router based on box expansion and progressive ILP. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2007, 26(12): 2130&horbar;2143 https://doi.org/10.1109/TCAD.2007.907003
10	Albrecht C. Global routing by new approximation algorithms for multicommodity flow. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2001, 20(5): 622&horbar;632 https://doi.org/10.1109/43.920691
11	Hu J, Roy J A, Markov I L. Sidewinder: a scalable ILP-based router. In: Proceedings of ACM International Workshop on System Level Interconnect Prediction. 2008, 73&horbar;80 https://doi.org/10.1145/1353610.1353625
12	Cho M, Lu K, Yuan K, Pan D Z. BoxRouter 2.0: a hybrid and robust global router with layer assignment for routability. ACM Transactions on Design Automation of Electronic Systems, 2009, 14(2): 32 https://doi.org/10.1145/1497561.1497575
13	Vannelli A. An interior point method for solving the global routing problem. In: Proceedings of the IEEE 1989 Custom Integrated Circuits Conference. 1989, 1&horbar;4 https://doi.org/10.1109/CICC.1989.56681
14	Behjat L, Chiang A, Rakai L, Li J H. An effective congestion-based integer programming model for VLSI global routing. In: Proceedings of Canadian Conference on Electrical and Computer Engineering. 2008, 931&horbar;936 https://doi.org/10.1109/ccece.2008.4564673
15	Behjat L, Vannelli A, Rosehart W. Integer linear programming models for global routing. INFORMS Journal on Computing, 2006, 18(2): 137&horbar;150 https://doi.org/10.1287/ijoc.1040.0127
16	Wu T H, Davoodi A, Linderoth J T. GRIP: global routing via integer programming. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2011, 30(1): 72&horbar;84 https://doi.org/10.1109/TCAD.2010.2066030
17	Han Y, Ancajas D M, Chakraborty K, Roy S. Exploring highthroughput computing paradigm for global routing. IEEE Transactions on Very Large Scale Integration Systems, 2014, 22(1): 155&horbar;167 https://doi.org/10.1109/TVLSI.2012.2234489
18	Liu G G, Chen G L, Guo W Z. DPSO based octagonal steiner tree algorithm for VLSI routing. In: Proceedings of the 15th IEEE International Conference on Advanced Computational Intellligence. 2012, 383&horbar;387 https://doi.org/10.1109/icaci.2012.6463191
19	Dong J, Zhu H L, Xie M, Zeng X. Graph Steiner tree construction and its routing applications. In: Proceedings of the 10th IEEE International Conference on ASIC. 2013, 1&horbar;4
20	Hung J H, Yeh Y K, Lin Y C, Huang H H, Hsieh T M. ECO-aware obstacle-avoiding routing tree algorithm. WSEAS Transactions on Circuits and Systems, 2010, 9(9): 567&horbar;576
21	Tsai C C, Kuo C C, Lee T Y. High performance buffered X-architecture zero-skew clock tree construction with via delay consideration. International Journal of Innovative Computing, Information and Control, 2011, 7(9): 5145&horbar;5161
22	Tsai C C, Kuo C C, Hsu F T, Lee T Y. Discharge-path-based antenn aeffect detection and fixing for X-architecture clock tree. Integration, the VLSI Journal, 2012, 45(1): 76&horbar;90
23	Liu G G, Guo W Z, Niu Y Z, Chen G L, Huang X. A PSO-basedtiming- driven octilinear Steiner tree algorithm for VLSI routing considering bend reduction. Soft Computing, 2014, 19(5): 1153&horbar;1169 https://doi.org/10.1007/s00500-014-1329-2
24	Ho T Y. A performance-driven multilevel framework for the X-based full-chip router. Integrated circuit and system design. Power and timing modeling, optimization and simulation. Springer Berlin Heidelberg, 2009: 209&horbar;218 https://doi.org/10.1007/978-3-540-95948-9_21
25	Hu Y, Jing T, Hong X, Hu X, Yan G. A routing paradigm with novel resources estimation and routability models for X-architecture based physical design. Embedded computer systems: architectures, modeling, and simulation. Springer Berlin Heidelberg, 2005: 344&horbar;353
26	Cao Z, Jing T, Hu Y, Shi Y, Hong X, Hu X, Yan G. DraXRouter: global routing in X-architecture with dynamic resource assignment. In: Proceedings of the 2006 Asia and South Pacific Design Automation Conference. 2006, 618&horbar;623 https://doi.org/10.1145/1118299.1118445
27	Ho T Y. A performance-driven X-architecture router based on a novel multilevel framework. Integration, the VLSI Journal, 2009, 42: 400&horbar;408
28	Teig S L. The X architecture: not your father’s diagonal wiring. In: Proceedings of ACM International Workshop on System-Level Interconnect Prediction. 2002, 33&horbar;37 https://doi.org/10.1145/505348.505355
29	Eberhar R C, Kennedy J. A new optimizer using particles swarm theory. In: Proceedings of the 6th International Symposium on Micro Machine and Human Science. 1995, 39&horbar;43 https://doi.org/10.1109/MHS.1995.494215
30	Neumann F, Witt C. Bioinspired computation in combinatorial optimization: algorithms and their computational complexity. Springer, 2010 https://doi.org/10.1007/978-3-642-16544-3
31	Zhang Y, Gong D W. Generating test data for both paths coverage and faults detection using genetic algorithms: multi-path case. Frontiers of Computer Science, 2014, 8(5): 726&horbar;740 https://doi.org/10.1007/s11704-014-3372-7
32	Rabanal P, Rodríguez I, Rubio F. An ACO-RFD hybrid method to solve NP-complete problems. Frontiers of Computer Science, 2013, 7(5): 729&horbar;744 https://doi.org/10.1007/s11704-013-2302-4
33	Wang Y, Cai Z X. A hybrid multi-swarm particle swarm optimization to solve constrained optimization problems. Frontiers of Computer Science, 2009, 3(1): 38&horbar;52 https://doi.org/10.1007/s11704-009-0010-x
34	Chen G L, Guo W Z, Chen Y Z. A PSO-based intelligent decision algorithm for VLSI floorplanning. Soft Computing, 2010, 14(12): 1329&horbar;1337 https://doi.org/10.1007/s00500-009-0501-6
35	Guo W Z, Liu G G, Chen G L, Peng S J. A hybrid multi-objective PSO algorithm with local search strategy for VLSI partitioning. Frontiers of Computer Science, 2014, 8(2): 203&horbar;216 https://doi.org/10.1007/s11704-014-3008-y
36	Koh C K, Madden P H. Manhattan or non-manhattan? A study of alternative VLSI routing architectures. In: Proceedings of the 10th Great Lakes symposium on VLSI. 2000, 47&horbar;52
37	Kennedy J, Eberhart R C. A discrete binary version of the particle swarm algorithm. In: Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics. 1997, 4104&horbar;4108 https://doi.org/10.1109/icsmc.1997.637339
38	Hu X, Eberhart R C, Shi Y. Swarm intelligence for permutation optimization: a case study of n-queens problem. In: Proceedings of Swarm Intelligence Symposium. 2003, 243&horbar;246
39	Parsopoulos K E, Halgamuge M N. Recent approaches to global optimization problems through particle swarm optimization. Natural Computing, 2002, 1(2-3): 235&horbar;306 https://doi.org/10.1023/A:1016568309421
40	Salman A, Ahmad I, Al-Madani S. Particle swarm optimization for task assignment problem. Microprocessors and Microsystems, 2002, 26(8): 363&horbar;371 https://doi.org/10.1016/S0141-9331(02)00053-4
41	Clerc M. Discrete particle swarm optimizationillustrated by the traveling salesman problem. In: Onwubolu GC, Babu BV: eds. New optimization techniques in engineering. Berlin: Springer-Verlag, 2004: 219&horbar;239 https://doi.org/10.1007/978-3-540-39930-8_8
42	Pan Q K, Tasgetiren M F, Liang Y C. A discrete particle swarm optimization algorithm for the permutation flowshop sequecing problem with makespan criteria. In: Proceedings of Research and Development in Intelligent Systems XXIII. 2006, 19&horbar;31.
43	Dietzfelbinger M, Naudts B, van Hoyweghen C, Wegener I. The analysis of a recombinative hill-climber on H-IFF. IEEE Transactions on Evolutionary Computation, 2003, 7(5): 417&horbar;423 https://doi.org/10.1109/TEVC.2003.818192
44	Qian C, Yu Y, Zhou Z. An analysis on recombination in multi-objec<?Pub Caret?>tive evolutionary optimization, Artificial Intelligence, 2013, 204: 99&horbar;119 https://doi.org/10.1016/j.artint.2013.09.002
45	Alpert C, Tellez G. The importance of routing congestion analysis. In: Proceedings of the IEEE Design Automation Conference. 2010, 1&horbar;14
46	Shi Y H, Eberhart R C. A modified particle swarm optimizer. In: Proceedings of the IEEE International Conference on Evolutionary Computation. 1998, 69&horbar;73 https://doi.org/10.1109/icec.1998.699146
47	Ratnaweera A, Halgamuge S K, Watson H C. Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients. IEEE Transactions on Evolutionary Computation, 2004, 8(3): 240&horbar;255 https://doi.org/10.1109/TEVC.2004.826071
48	Lv H, Zheng J, Zhou C, Li K. The convergence analysis of genetic algorithm based on space mating. In: Proceeding of the 5th International Conference on Natural Computation. 2009, 557&horbar;562 https://doi.org/10.1109/icnc.2009.39
49	Rudolph G. Convergence analysis of canonical genetic algorithms. IEEE Transactions on Neural Networks, 1994, 5(1): 96&horbar;101 https://doi.org/10.1109/72.265964

[1]

Supplementary Material-Highlights in 3-page ppt

Download

[1]	Yihui LIANG, Han HUANG, Zhaoquan CAI. PSO-ACSC: a large-scale evolutionary algorithm for image matting[J]. Front. Comput. Sci., 2020, 14(6): 146321-.
[2]	Wei-Neng CHEN, Da-Zhao TAN. Set-based discrete particle swarm optimization and its applications: a survey[J]. Front. Comput. Sci., 2018, 12(2): 203-216.
[3]	Cui HUANG, Dakun ZHANG, Guozhi SONG. A novel mapping algorithm for three-dimensional network on chip based on quantum-behaved particle swarm optimization[J]. Front. Comput. Sci., 2017, 11(4): 622-631.
[4]	Priyanka CHAWLA,Inderveer CHANA,Ajay RANA. A novel strategy for automatic test data generation using soft computing technique[J]. Front. Comput. Sci., 2015, 9(3): 346-363.
[5]	Wenzhong GUO,Genggeng LIU,Guolong CHEN,Shaojun PENG. A hybrid multi-objective PSO algorithm with local search strategy for VLSI partitioning[J]. Front. Comput. Sci., 2014, 8(2): 203-216.
[6]	Wei ZHAO, Ye SAN. RBF neural network based on q-Gaussian function in function approximation[J]. Front Comput Sci Chin, 2011, 5(4): 381-386.
[7]	Yong WANG, Zixing CAI. A hybrid multi-swarm particle swarm optimization to solve constrained optimization problems[J]. Front Comput Sci Chin, 2009, 3(1): 38-52.
[8]	Yuhui SHI, Russ EBERHART. Monitoring of particle swarm optimization[J]. Front Comput Sci Chin, 2009, 3(1): 31-37.

Viewed

Full text

Abstract

Cited

Shared

Discussed