A VLSI Routing Algorithm Based on Improved DPSO

摘要：

The minimum rectilinear Steiner tree (MRST) problem is an NP-hard problem, which is one of the fundamental issues in electronic design automation (EDA). Particle swarm optimization (PSO) has been proved to be an efficient intelligent algorithm for optimization designs. This paper presents an application of discrete particle swarm optimization (DPSO) for resolving MRST in VLSI routing and proposes a routing algorithm based on improved DPSO (DPSO-RA in short). A novel encoding and several updating operations for DPSO are adopted respectively, according to the characteristics of discrete PSO. The parameters are adjusted to find out an MRST and, consequently, achieve interconnect of all destination nodes in VLSI. The experiments have been carried out to demonstrate the feasibility of DPSO-RA implement to VLSI routing. Moreover, the algorithm also shows good result in routing optimization.

关键词： DPSO-RA VLSI Routing MRST

作者: Chen Dong Gaofeng Wang Zhenyi Chen Shilei Sun Dingwen Wang

作者单位: Computer School,Wuhan University,Hubei,China;College of Mathematics and Computer Science,Fuzhou Univ Institute of Microelectronics and Information Technology,Wuhan University,Hubei,China Computer School,Wuhan University,Hubei,China;Fuzhou Electric Power Bureau,Fujian,China

会议类型: 国际会议

会议名称: 2009 IEEE International Conference on Intelligent Computing and Intelligent Systems(2009 IEEE 智能计算与智能系统国际会议)

会议地点: 上海

会议语种:英文

页码: 802-805

在线出版日期: 2009-11-20（万方平台首次上网日期，不代表论文的发表时间）