XGRouter: high-quality global router in X-architecture with particle swarm optimization |
| |
| Authors: | Genggeng Liu Wenzhong Guo Rongrong Li Yuzhen Niu Guolong Chen |
| |
| Affiliation: | 1. College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350116, China2. Fujian Provincial Key Laboratory of Network Computing and Intelligent Information Processing, Fuzhou University, Fuzhou 350116, China |
| |
| 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 |
| 本文献已被 SpringerLink 等数据库收录！ |
| 点击此处可从《Frontiers of Computer Science》浏览原始摘要信息 |
|
点击此处可从《Frontiers of Computer Science》下载全文 |
