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

详细信息    查看全文

• 作者：Genggeng Liu ; Wenzhong Guo ; Rongrong Li ; Yuzhen Niu…
• 关键词：global routing ; overflow ; total wire length ; congestion uniformity ; X ; architecture ; particle swarm optimization ; integer linear programming
• 刊名：Frontiers of Computer Science in China
• 出版年：2015
• 出版时间：August 2015
• 年：2015
• 卷：9
• 期：4
• 页码：576-594
• 全文大小：995 KB
• 参考文献：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鈥?944View Article
  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鈥?077View Article
  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鈥?49View Article
  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鈥?72View Article
  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鈥?026View Article
  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鈥?07View Article
  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鈥?40View Article
  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鈥?22View Article
  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鈥?143View Article
  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鈥?32View Article
  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鈥?0View Article
  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): 32View Article
  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鈥?
  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鈥?36
  15.Behjat L, Vannelli A, Rosehart W. Integer linear programming models for global routing. INFORMS Journal on Computing, 2006, 18(2): 137鈥?50MathSciNet View Article
  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鈥?4View Article
  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鈥?67View Article
  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鈥?87
  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鈥?
  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鈥?76
  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鈥?161
  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鈥?0View Article
  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鈥?169View Article
  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鈥?18View Article
  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鈥?53View Article
  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鈥?23View Article
  27.Ho T Y. A performance-driven X-architecture router based on a novel multilevel framework. Integration, the VLSI Journal, 2009, 42: 400鈥?08View Article
  28.Teig S L. The X architecture: not your father鈥檚 diagonal wiring. In: Proceedings of ACM International Workshop on System-Level Interconnect Prediction. 2002, 33鈥?7
  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鈥?3View Article
  30.Neumann F, Witt C. Bioinspired computation in combinatorial optimization: algorithms and their computational complexity. Springer, 2010View Article
  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鈥?40MathSciNet View Article
  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鈥?44View Article
  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鈥?2View Article
  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鈥?337View Article
  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鈥?16MathSciNet View Article
  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鈥?2
  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鈥?108
  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鈥?46
  39.Parsopoulos K E, Halgamuge M N. Recent approaches to global optimization problems through particle swarm optimization. Natural Computing, 2002, 1(2-3): 235鈥?06MathSciNet View Article
  40.Salman A, Ahmad I, Al-Madani S. Particle swarm optimization for task assignment problem. Microprocessors and Microsystems, 2002, 26(8): 363鈥?71View Article
  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鈥?39.View Article
  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鈥?1.
  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鈥?23View Article
  44.Qian C, Yu Y, Zhou Z. An analysis on recombination in multi-objective evolutionary optimization, Artificial Intelligence, 2013, 204: 99鈥?19MathSciNet View Article
  45.Alpert C, Tellez G. The importance of routing congestion analysis. In: Proceedings of the IEEE Design Automation Conference. 2010, 1鈥?4
  46.Shi Y H, Eberhart R C. A modified particle swarm optimizer. In: Proceedings of the IEEE International Conference on Evolutionary Computation. 1998, 69鈥?3
  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鈥?55View Article
  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鈥?62
  49.Rudolph G. Convergence analysis of canonical genetic algorithms. IEEE Transactions on Neural Networks, 1994, 5(1): 96鈥?01View Article
  
• 作者单位：Genggeng Liu (1)
  Wenzhong Guo (1) (2)
  Rongrong Li (1)
  Yuzhen Niu (1)
  Guolong Chen (1) (2)
  
  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
  
• 刊物类别：Computer Science
• 刊物主题：Computer Science, general
  Chinese Library of Science
  
• 出版者：Higher Education Press, co-published with Springer-Verlag GmbH
• ISSN：1673-7466

文摘

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.