VLSI Global Routing Strategies Based On Particle Swarm Optimization

Integrated circuit (IC) industry is booming, which is pushed by Moore’s Law. The trend of the IC’s development is smaller chip features and higher integrity for reducing the chip cost. This trend results in more compaction between blocks, more complexity and congestion of interconnect’s distribution, longer length and more area occupation. With the rapid development of IC’s technics, switches’calculating velocity and clock frequency, the interconnect delay exceeds the switches delay far and away. Accordingly, almost 60% of the path delay is brought by interconnect. Interconnect effect becomes the bottleneck of IC’s performance. Effective and fast routing tool is the key of improving IC’s performance.There are two phases involved in routing stage, global rouing and detailed routing. Global routing is the basic of detailed routing, which ensure the feasibility, reasonability, connectivity and superiority of routing result. The performance of global routing approaches affects the routing stage and IC performance totally and greatly. Consequently, the global routing plays the vital role in physical design.The traditional global routing methods are not fit for the very large scale integration rouing problem, which are infeasibility for the booming calculation. The global routers based on heuristic intelligent optimization algorithms have the capability of searching global optimization results or approximate global optimization results with time-limit, which are the effective approaches for VLSI routing.Particle swarm optimization (PSO) algorithm is a kind of heuristic and random optimization algorithm, it bases on swarm intelligence theory. In virtue of the simplification and robustness, PSO algorithm is researched widely. PSO algorithm was proved to be an efficient intelligent algorithm for optimization problems. With the feature of global exploration and fast convergence, PSO algorithm has been applied into many engineering fields.The aim of this paper is presenting of an effective global router based on heuristic optimization algorithm. In this papar, the present gobal routing approaches and theirs deficiency are discussed in great detail. With abundant investigation and analysis of the PSO evolution stage and its improved strategies, the improved PSO algorithms and the global routing approaches are proposed. These new methods are employed to deal with the multi-terminal net routing and the VLSI global rouing problem.Following are the primary study and idea of this papar:(1) A novel inertia weight self-adaptive PSO algorithm is presented (SAW-PSO in short), with detailed investigation and analysis of the PSO parameters, especially inertia weight. In this novel self-adaptive PSO, a special function, which is defined in terms of the particle fitness value, swarm size and the dimension size of solution space, is introduced to adjust the inertia weight adaptively. The SAW-PSO can greatly accelerate the convergence rate and improve the capability to find the global minimum for large-scale problems.(2) An improved PSO algorithm based on acceleration coefficients self-adaptive is design (SAC-PSO in short). In this new self-adaptive PSO, special functions, which are defined in terms of the particle fitness, are introduced to adjust the acceleration coefficients adaptively. This novel self-adaptive PSO can greatly accelerate the convergence rate and improve the capability to reach the global minimum for optimization problems.(3) This paper presents the first application of discrete particle swarm optimization (DPSO) with mutation to resolving MRST in VLSI routing and proposes a routing algorithm based on improved DPSO (MDPSO-RA in short). A special 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 terminals in VLSI. The experiments have been carried out to demonstrate the feasibility of MDPSO-RA implement to VLSI routing. Moreover, the algorithm also shows good result in routing optimization.(4) The discrete particle swarm optimization (DPSO) with mutation is the first applied to tackling global routing, which leads to a new global routing approach for achieving optimized wire length and via numbers (MDPSO-GR in short). Based on the characteristics of discrete PSO, special encoding and updating operations for DPSO will be adopted. The design parameters are adjusted to attain an approximate optimum global routing solution.The MCNC and GSRC benchmarks are employed for illustrating the feasibility of MDPSO-RA and MDPSO-GR implementation in VLSI global routing. This algorithm can lead to good results in routing optimization.