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

作     者：Genggeng LIU Wenzhong GUO Rongrong LI Yuzhen NIU Guolong CHEN 

作者机构：College of Mathematics and Computer Science Fuzhou University Fuzhou 350116 China Fujian Provincial Key Laboratory of Network Computing and Intelligent Information Processing Fuzhou University Fuzhou 350116 China 

出 版 物：《Frontiers of Computer Science》 (中国计算机科学前沿（英文版）)

年 卷 期：2015年第9卷第4期

页      面：576-594页

核心收录：

学科分类：0810[工学-信息与通信工程] 08[工学] 081001[工学-通信与信息系统] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金 supported in part by the National Basic Research Program of China (973 Program) 福建省高等学校新世纪优秀人才支持计划 the Fujian Province High School Science Fund for Distinguished Young Scholars the Fujian Natural Science Funds for Distinguished Young Scholar 

主　　题：global routing overflow total wire length con-gestion uniformity X-architecture particle swarm optimiza-tion integer linear programming 

摘      要：This paper presents a high-quality very large scale integration （VLSI） global router in X-architecture, called XGRouter, that heavily relies on integer linear pro- gramming （ILP） techniques, partition strategy and particle swarm optimization （PSO）. A new ILP formulation, which can achieve more uniform routing solution than other formu- lations 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 re- gion is extended progressively from the most congested re- git）n. In the post-processing stage of XGRouter, maze rout- ing 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 rout- ing 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 touters, XGRouter has no overflow.