A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> c: PARTICLE ENCODING <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> c: PARTICLE ENCODING <s> Time delay in very large scale integration circuit routing can be improved using several techniques such as intelligent selection of the size of wire and buffer, and strategic buffer placement.This paper proposes the use of Binary Particle Swarm Optimization to find the best selection of the size of wire and buffer, and ideal location of buffer insertion along the wire. For the proposed approach, a particle epresents a possible solution of the buffer placement problem. The time delay produced by the proposed solution of each particle is then calculated. The particle will try to improve its solution by trying to replicate its best record and swarm best record. The process is repeated until stopping condition is achieved. Swarm best record is taken as the best solution obtained by the proposed approach. A case study is taken to measure the performance of the proposed approach. The proposed approach has a good potential in VLSI routing and can be extended in future. <s> BIB002 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> c: PARTICLE ENCODING <s> Manipulation of wire sizing, buffer sizing, and buffer insertion are a few techniques that can be used to improve time delay in very large scale integration (VLSI) circuit routing. This paper enhances an existing approach, which is based on Particle Swarm Optimization (PSO) for solving routing problem in VLSI circuits. A two-step Binary Particle Swarm Optimization (BPSO) approach, which is based on BPSO, is chosen in this study to improve time delay through finding the best path of wire placement with buffer insertion from source to sink. The best path of wire placement is found in the first step by the first BPSO and then the second BPSO finds the best location of buffer insertion along the wire. A case study is taken to measure the performance of the proposed model and the result obtained compared to the previous PSO approach for VLSI routing. <s> BIB003 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> c: PARTICLE ENCODING <s> Global interconnect delay is increasingly dominated with the scaling of VLSI fabrication technology where wire minimization, wire-sizing and buffer insertion techniques have found remarkable applications. Multiple researches are proven with state-of-art techniques to solve routing and timing optimization problem in VLSI. Metahueristic being an alternate approach, employed successfully Particle Swarm Optimization (PSO) and Firefly Algorithm (FA) in RC delay Model and Binary PSO (BPSO) for iterative RLC delay model to obtain Global optimum but with limitations. This paper proposes a two-step approach using a modified Constricted PSO with mutation factor where the first stage achieves wire minimization and best buffer insertion with simultaneous wire-sizing in the final stage for reduction of interconnect delay using iterative RLC delay model. A comparison has been made between the conduct of the proposed approach and the previous BPSO approach and is found to be better alternative for optimizing VLSI Interconnect delay. <s> BIB004
In this problem model, each of the solution of path routing in each iteration is represented by one particle of PSO. If using a maximum number of 8 doglegs, each particle can be encoded by a seven-vector of position which is from e 1 to e 7 shown in Figure 11 . And e even is the location in grid graph measured from origin along x-axis and e odd is the location in grid graph measured from origin along y-axis BIB001 . One path from source to sink is generated by connecting these continuous segments: source →e 1 →e 2 →e 3 →e 4 →e 5 →e 6 →e 7 →sink. For a more complex case study, number of doglegs can be increased by increasing the vector position, e to n value. Thus particle i with the position and velocity are presented as: The fitness of this algorithm is the delay time calculated accumulatively from source to sink, including both wire segment and wire segment terminated with buffer. Taking Figure 11 for instance, the number of total segments used can be calculated as Eq. (36) where n is a maximum number of dogleg and e a represents the location of a node in grid graph. x so and x si are x-axis coordinates for source and sink. For every 6 segments, a buffer will be placed randomly. From the value of P and the corresponding buffer location, the delay time can be determined using Elmore delay within iterative calculation. However, the algorithm did not perform wire and buffer sizing. Hence, Yusof et al. BIB002 extended Ayob's work by employing Binary Particle Swarm Optimization (BPSO) in buffer insertion and wire sizing in the presence of wire and buffer obstacles. In this algorithm, particle position X can be modelled as follows: where x q represents the type of wire with/without buffer for the respective to grid segment, q. For each x, seven bits are used to represent the case study, where the first 3 bits represent the type of wire used, the fourth bit indicates the use of buffer, and the last 3 bits represent the type of buffer used. The fitness function is determined by capacitance-delay pair (c, t), where c represents the total ground capacitance at node v in a delay model. And a new capacitance-delay pair (c , t ) for the preceding interconnected segment is determined as follows: The particle velocity is updated by Eq. (3) , and the position X , is updated for next iteration t for each bit d, using Eq. (39) based on the probability of the normal distribution. where r is random number of [0,1]. In addition, Yusof et al. BIB003 also proposed a two-step BPSO approach to obtain the best path of wire placement with buffer insertion from source to sink. The algorithm uses two BPSOs respectively to find the shortest path of wire placement and the best location of buffer insertion along the wire. The fitness function used for the second BPSO is the time delay formulation based on the iterative RLC delay model. However, the low exploration capability of BPSO method sometimes leads to a low convergence rate of the routing algorithm. To overcome this drawback, Nath et al. BIB004 proposed a two-step modified constricted PSO with the integration of the mutation (CPSO-MU). PSO-MU discovers the minimal path of placing the wire at first and explores the finest location along the wire for inserting the buffer in the final step. Compared with BIB003 , CPSO-MU can accomplish global convergence with a slighter number of iterations and produce a less interconnect delay.