A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> Algorithm 4 FA for VLSI Routing Problem <s> The performance of very large scale integration (VLSI) circuits is depends on the interconnected routing in the circuits. In VLSI routing, wire sizing, buffer sizing, and buffer insertion are techniques to improve power dissipation, area usage, noise, crosstalk, and time delay. Without considering buffer insertion, the shortest path in routing is assumed having the minimum delay and better performance. However, the interconnect delay can be further improved if buffers are inserted at proper locations along the routing path. Hence, this paper proposes a heuristic technique to simultaneously find the optimal routing path and buffer location for minimal interconnect delay in VLSI based on particle swarm optimization (PSO). PSO is a robust stochastic optimization technique based on the movement and information sharing of swarms. In this study, location of doglegs is employed to model the particles that represent the routing solutions in VLSI. The proposed approach has a good potential in VLSI routing and can be further extended in future <s> BIB001 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> Algorithm 4 FA for VLSI Routing Problem <s> Swarm Intelligence (SI), modelled upon the behaviours of various swarms of animals and insects such as ants, termites, bees, birds, fishes, fireflies, etc. is an emerging area in the field of optimization. SI based algorithms are proclaimed to be robust and efficient optimization tools. This fact is corroborated by a number of practical engineering problems where these algorithms give very satisfactory results. Nowadays VLSI Design has become one of the most intriguing and fervent research field for engineers. Efficient development of a system of a billion chips and blocks on a printed circuit board requires extensive use of optimization in various areas of design such as chip size, separation among components, interconnect length etc. One of the most significant among these is the interconnect wirelength, which determines the overall delay in transmission within the chip. The routing phase in the VLSI Physical Design strives to optimize the interconnect length. Several studies have been and are being conducted to improve the performance of VLSI chips by optimally interconnecting the various components. Various SI based algorithms have already proved their efficiency in this field of routing optimization. In this paper we have proposed a global routing scheme based on contemporary SI algorithms: Firefly Algorithm (FA), and Artificial Bee Colony (ABC) algorithm and have compared the performance of the two. FA produces superior optimization results in comparison to ABC although proving to be quite expensive, computationally. <s> BIB002 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> Algorithm 4 FA for VLSI Routing Problem <s> In Electronic design, interconnected delay minimization owes a lot from VLSI routing which have the concept of Global Routing Phase encapsulated within it, to provide assistance in diminishing wire-length upto an optimal point. Steiner Tree acts as a nucleus which supports the entire concept and is constructed by the terminal nodes whose cost-reduction is the first step towards the goal. Categorically Steiner tree problem is a well-known NP-complete problem; hence metaheuristics could provide good solutions. Particle swarm optimization (PSO)and Firefly algorithm (FA)are proven efficient algorithms in VLSI routing field. This paper is stressed upon the introduction of as self-adaptive mechanism for controlling acceleration coefficient of PSO and analysis of its performance with the existing acceleration coefficient controlled PSO in a defined search space. The paper also tally the results of PSO variants with constriction factor and introduce a new model in modifying the PSO with essence of genetic algorithm and compare the results with Inertia weighted PSO and conventional FA, modeled for VLSI routing. <s> BIB003
1 Define objective function f (x), and maximum number of iterations, maxit; 2 Initialize a population of fireflies x i (i = 1, 2, . . . , q), parameters: γ , β 0 , α, and iteration counter iter = 0; 3 Place the buffers randomly for the population; 4 while iter < maxiter do 5 for i=1 : q (all q fireflies) do 6 for j = 1 : q do 7 if I i < I j then 8 Move firefly i towards j using Eq. (21); 9 Place the buffers randomly for firefly i; 10 Perform correction if necessary; 11 Evaluate new solution according to the f (x), update I i and global best if necessary; 12 Output the firefly with the highest light intensity; Algorithm 4 gives the FA algorithm for VLSI routing optimization problem. The algorithm generates the initial firefly population randomly, and the location of a firefly is evaluated by the fitness function. And light intensity of firefly I i at x i is determined by fitness f (x) using Eq. (31) to Eq. (34) . At each iteration, each firefly will fly to a firefly with larger light intensity, using Eq. (21) as the position update formula, where distance r is the Cartesian distance between the two fireflies. However, after the firefly moves towards another agent, the new position suggested might be invalid due to inexact coordinate location. Therefore, the correction strategy in Step 10 is proposed to mainly focus on two situations: one is that the solution is a decimal, and the easy way is to round it off; the other is that the solution exceeds the coordinate boundary, and the measure taken is to ignore this iteration. Next (Step 11) is the fitness evaluation of the new firefly and the update of the light intensity. The final solution is obtained by continuously iterating and updating the global best. The author compared this method with PSO-based routing algorithm BIB001 and the same optimal solution was obtained. For the routing problem without buffer insertion, the algorithm process is roughly the same as Algorithm 4, only needing to omit Step 3 to Step 9. In BIB003 , FA, the PSO with inertia weight (PSO-W), the PSO with constriction factor (PSO-C) and the PSO with mutation (PSO-MU) are used to minimum wirelength in global routing. And both FA and PSO-MU yield lowest minimum wirelength, but the calculation time consumed by FA is about 6 times that of PSO-MU and 10 times that of PSO-W. It can be seen that traditional FA algorithm has a better optimization capability than traditional PSO algorithm, but a good improved PSO algorithm such as PSO-MU can achieve the same optimization results as traditional FA, and the time complexity is much lower. In BIB002 , FA and ABC are used to connect all terminal nodes under the initial setting of the randomly generated terminal nodes coordinates. And the performance of the two algorithms in terms of minimizing the interconnected length is compared. The experimental results show that FA can achieve shorter wirelength in the search for terminal nodes of RSMT, but the computational cost is larger. Therefore, if our ultimate demand is only time delay reduction by minimizing interconnected wirelength, FA is no doubt a better choice. However if the runtime requirement is higher, it is recommended to choose ABC.