A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> a: RST CONSTRUCTION USING PSO <s> Floorplanning is an important issue in the very large-scale integrated (VLSI) circuit design automation as it determines the performance, size, yield and reliability of VLSI chips. This paper proposes a novel intelligent decision algorithm based on the particle swarm optimization (PSO) technique to obtain a feasible floorplanning in VLSI circuit physical placement. The PSO was applied with integer coding based on module number and a new recommended value of acceleration coefficients for optimal placement solution. Inspired by the physics of genetic algorithm (GA), the principles of mutation and crossover operator in GA are incorporated into the proposed PSO algorithm to make this algorithm to break away from local optima and achieve a better diversity. Experiments employing MCNC and GSRC benchmarks show that the proposed algorithm is effective. The proposed algorithm can avoid local minimum and performs well in convergence. The experimental results of the proposed method in this paper can also greatly help floorplanning decision making in VLSI circuit design automation. <s> BIB001 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> a: RST CONSTRUCTION USING PSO <s> The obstacle-avoiding rectilinear Steiner minimum tree (OARSMT) problem is one of the fundamental problems in the physical design of Very Large Scale Integrated (VLSI) circuits, especially in routing, which is known to be NP-complete. It becomes more important than ever for VLSI designs which need to consider numerous obstacles such as macro cells, IP blocks and pre-routed nets. Particle Swarm Optimization (PSO) has been proved to be an efficient intelligent algorithm for optimization designs. In this paper, an improved Discrete Particle Swarm Optimization (DPSO) algorithm is proposed for solving the OARSMT problem optimally. Meanwhile, the corresponding evaluation function and the operators inspired from the Genetic Algorithm (GA) are designed. The obstacle-avoiding measure is then presented to construct an OARSMT, which avoiding obstacles by generate virtual vertexes of the real vertexes. Experimental results on several benchmarks show that the proposed method achieves good performance in routing optimization significantly. <s> BIB002 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> a: RST CONSTRUCTION USING PSO <s> The Octagonal Steiner Minimal Tree (OSMT) problem is an NP-hard problem, which is one of the key problems in non-Manhattan routing. Particle Swarm Optimization (PSO) has been proved to be an efficient intelligent algorithm for optimization designs. This paper presents an OSMT algorithm based on discrete PSO (DPSO), namely OSMT_DPSO, to optimize the wire length. In order to solve the problem of the slow convergence rate of PSO used for a high-dimensional space optimization, a self-adapting strategy that can adjust the learning factors, and combine with the crossover and mutation operators of Genetic Algorithm (GA) is proposed. The experimental results show that the proposed algorithm can efficiently provide the solution of OSMT problem with good quality. Moreover, the algorithm can obtain several topologies of OSMTs which is beneficial for optimizing congestion in VLSI global routing stage. <s> BIB003 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> a: RST CONSTRUCTION USING PSO <s> Rapid advances in VLSI technology has increased the chip density by constantly increasing the number of constituents on a single chip, as well as decreasing the chip feature size. In such a complex scenario the primary objective is to limit the power-delay product of the system. It can be done by reducing the interconnect delay by optimizing the wire lengths i.e. by the proper interconnection of all the nodes. The minimum cost of interconnection of all nodes can be found by a Rectilinear Steiner Minimal Tree (RSMT) formed by the nodes. The problem of finding a RSMT is an NP-complete one. Particle Swarm Optimization (PSO) is an efficient swarm intelligence algorithm which boasts of fast convergence and ease of implementation, capable of solving such a problem. This paper presents a novel discrete particle swarm optimization (DPSO) to solve the NP-complete problem i.e. finding the RSMT. A modified Prim's Algorithm has been adopted for the purpose of finding the cost of the RSMT. A unique modification to the traditional PSO has been done by introducing the Mutation operation of Genetic Algorithm (GA) which produces up to 20% reduction in the wire lengths or cost of interconnections. Two versions of the DPSO algorithm - one with linearly decreasing inertia weight and another with self-adaptive inertia weight - have been employed and their results have been compared. Comparisons have also been made between the results available from recent work and our algorithm and the latter has established itself to superior in optimizing the interconnect lengths and thereby finding the lowest wire lengths. <s> BIB004 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> a: RST CONSTRUCTION USING PSO <s> The Obstacle-Avoiding Octagonal Steiner Minimal Tree (OAOSMT) problem has been proved to be a NP-hard problem, and it is very important for Very Large Scale Integration (VLSI) Non-Manhattan routing problem. In this paper, we present an efficient algorithm called OA_OST_DPSO for Obstacle-Avoiding Octagonal Steiner Minimal Tree construction. In our algorithm, according to the feature of OAOSMT problem, we construct an appropriate particle coding model and a fitness evaluation function. Meanwhile we integrate the crossover and mutation operator of genetic algorithm (GA) into the Particle Swarm Optimization (PSO) algorithm. Besides, edge transformation is employed to make the particles have the ability to achieve the more optimal solution while Union-Find partition is used to prevent the generation of invalid solution. Finally, our algorithm uses a dynamic parameter strategy, in order to make sure that the search is more efficient. The experimental results show that our algorithm has a good performance, can in the presence of obstacle, greatly shorten the length of the wiring. <s> BIB005 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> a: RST CONSTRUCTION USING PSO <s> Very large scale integration (VLSI) circuit partitioning is an important problem in design automation of VLSI chips and multichip systems; it is an NP-hard combinational optimization problem. In this paper, an effective hybrid multi-objective partitioning algorithm, based on discrete particle swarm optimzation (DPSO) with local search strategy, called MDPSO-LS, is presented to solve the VLSI twoway partitioning with simultaneous cutsize and circuit delay minimization. Inspired by the physics of genetic algorithm, uniform crossover and random two-point exchange operators are designed to avoid the case of generating infeasible solutions. Furthermore, the phenotype sharing function of the objective space is applied to circuit partitioning to obtain a better approximation of a true Pareto front, and the theorem of Markov chains is used to prove global convergence. To improve the ability of local exploration, Fiduccia-Matteyses (FM) strategy is also applied to further improve the cutsize of each particle, and a local search strategy for improving circuit delay objective is also designed. Experiments on ISCAS89 benchmark circuits show that the proposed algorithm is efficient. <s> BIB006 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> a: RST CONSTRUCTION USING PSO <s> Meta-heuristic algorithms have a great impact in the wire length minimization at the stage of Global Routing in electronic design automation (EDA). Particle Swarm Optimization (PSO) has already been proved as a good tool in wire length optimization. Investigations carried out regarding the parameter tuning of Discrete PSO (DPSO), develops two variants of DPSO namely Linearly decreasing inertia weight DPSO and self tuned acceleration constant DPSO which exhibit better results than before. Here in this paper, we propose some other variants of DPSO and analyze the results for wire length optimization. The result establishes the fact of even better optimization along with better convergence rate, stability and lesser time complexity. The technique of incorporating mutation process in the proposed DPSO algorithm is highly successful in the Global Routing problem in EDA. <s> BIB007 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> a: RST CONSTRUCTION USING PSO <s> Obstacle-avoiding Steiner minimal tree (OASMT) construction has become a focus problem in the physical design of modern very large-scale integration (VLSI) chips. In this article, an effective algorithm is presented to construct an OASMT based on X-architecturex for a given set of pins and obstacles. First, a kind of special particle swarm optimization (PSO) algorithm is proposed that successfully combines the classic genetic algorithm (GA), and greatly improves its own search capability. Second, a pretreatment strategy is put forward to deal with obstacles and pins, which can provide a fast information inquiry for the whole algorithm by generating a precomputed lookup table. Third, we present an efficient adjustment method, which enables particles to avoid all the obstacles by introducing some corner points of obstacles. Finally, an excellent refinement method is discussed to further enhance the quality of the final routing tree, which can improve the quality of the solution by 7.93p on average. To our best knowledge, this is the first time to specially solve the single-layer obstacle-avoiding problem in X-architecture. Experimental results show that the proposed algorithm can further shorten wirelength in the presence of obstacles. And it achieves the best solution quality in a reasonable runtime among the existing algorithms. <s> BIB008 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> a: RST CONSTRUCTION USING PSO <s> Constructing a timing-driven Steiner tree is very important in VLSI performance-driven routing stage. Meanwhile, non-Manhattan architecture is supported by several manufacturing technologies and now well appreciated in the chip manufacturing circle. However, limited progress has been reported on the non-Manhattan performance-driven routing problem. In this paper, an efficient algorithm, namely, TOST_BR_MOPSO, is presented to construct the minimum-cost spanning tree with a minimum radius for performance-driven routing in Octilinear architecture (one type of the non-Manhattan architecture) based on multi-objective particle swarm optimization (MOPSO) and Elmore delay model. Edge transformation is employed in our algorithm to make the particles have the ability to achieve the optimal solution while Union-Find partition is used to prevent the generation of invalid solution. For the purpose of reducing the number of bends which is one of the key factors of chip manufacturability, we also present an edge-vertex encoding strategy combined with edge transformation. To our best knowledge, no approach has been proposed to optimize the number of bends in the process of constructing the non-Manhattan timing-driven Steiner tree. Moreover, the theorem of Markov chain is used to prove the global convergence of our proposed algorithm. Experimental results indicate that the proposed MOPSO is worthy of being studied in the field of multi-objective optimization problems, and our algorithm has a better tradeoff between the wire length and radius of the routing tree and has achieved a better delay value. Meanwhile, combining edge transformation with the encoding strategy, the proposed algorithm can significantly reduce nearly 20 % in the number of bends. <s> BIB009 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> a: RST CONSTRUCTION USING PSO <s> As the basic model for very large scale integration routing, the Steiner minimal tree (SMT) can be used in various practical problems, such as wire length optimization, congestion, and time delay estimation. In this paper, an effective algorithm based on particle swarm optimization is presented to construct a multilayer obstacle-avoiding X-architecture SMT (ML-OAXSMT). First, a pretreatment strategy is presented to reduce the total number of judgments for the routing conditions around obstacles and vias. Second, an edge transformation strategy is employed to make the particles have the ability to bypass the obstacles while the union-find partition is used to prevent invalid solutions. Third, according to the feature of ML-OAXSMT problem, we design an edge-vertex encoding strategy, which has the advantage of simple and effective. Moreover, a penalty mechanism is proposed to help the particle bypass the obstacles, and reduce the generation of via at the same time. Experimental results show that our algorithm from a global perspective of multilayer structure can achieve the best solution quality among the existing algorithms. Finally, to our best knowledge, we redefine the edge cost and then construct the obstacle-avoiding preferred direction X-architecture Steiner tree, which is the first work to address this problem and can offer the theory supports for chip design based on non-Manhattan architecture. <s> BIB010 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> a: RST CONSTRUCTION USING PSO <s> 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. <s> BIB011 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> a: RST CONSTRUCTION USING PSO <s> The Steiner minimal tree (SMT) problem is an NP-hard problem, which is the best connection model for a multi-terminal net in global routing problem. This paper presents a unified algorithm for octagonal and rectilinear SMT construction based on hybrid transformation strategy (HTS) and self-adapting particle swarm optimization. Firstly, an effective HTS is proposed to enlarge the search space and improve the convergence speed. Secondly, the proposed HTS in the evolutionary process may produce an ineffective solution, and consequently the crossover and mutation operators of genetic algorithm (GA) based on union-find sets is proposed. Thirdly, a self-adapting strategy that can adjust the acceleration coefficients is proposed to further improve the convergence and the quality of the proposed algorithm. Finally, the hybrid transformation can be applied to GA and the proposed algorithm can be applied to rectilinear architecture. To our best knowledge, the proposed algorithm is the first unified algorithm to solve the SMT construction under both octagonal and rectilinear architecture. The experimental results show that the proposed algorithm can efficiently provide a better solution for SMT problem both in octagonal and rectilinear architectures than others. Moreover, the algorithm can obtain several topologies of SMT, which is beneficial for optimizing congestion in VLSI global routing stage. <s> BIB012
Dong et al.  proposed a routing algorithm based on discrete particle swarm optimization (DPSO-RA), aiming at length and the bound of connectivity rate. The algorithm adopts a novel encoding and several update operations for DPSO, and achieves interconnection of all destination nodes in VLSI. Particle Encoding. Each particle represents an MST. DPSO-RA encodes the particle by establishing Steiner Matrix. A particle X i is a matrix and is expressed as: where n is the number of components waiting for interconnection. Each bit of the particle encoding corresponds a node in the Steiner Matrix, and is valued in binary. The nodes to be connected, called ''terminal nodes'', are taken as input from the user or are generated randomly in the form of x and y-coordinates. If a node is selected to construct the RST, the value of the bit is '1', otherwise '0'. Usually, the matrix will be reduced by deleting some rows and columns that do not have any terminal nodes. Steiner Matrix is established by the horizontal and vertical lines' cross-points of the components. And it represents the possible locations of the Steiner nodes of RST. Figure 7 (a) shows a Steiner Matrix of 10 components (blue) to be connected. Its corresponding particle is shown in Figure 7 (b). The velocity V i of particle X i is also a matrix, expressed as follows: where each bit of the velocity represents the probability of selecting the corresponding node in Steiner Matrix. Fitness Function. The cost of MST is the fitness value of this particle, which is calculated by Prim's algorithm. Update Operation. DPSO-RA redefines the operations of PSO and uses Eq. (3) and (4) as the position and velocity of the particle respectively. Definition 3: ''−'' Operation. The result of ''−'' operation between two particle locations is a velocity. Definition 4: ''+'' Operation. The result of ''+'' operation between two velocities is a new velocity. Definition 5: ''×'' Operation. The parameters c 1 and c 2 are constants, r 1 and r 2 are random numbers between 0 and 1. The result of ''×'' operation between a velocity and parameters is still a velocity. Algorithm Processes. Step 1. Initialize the particle swarm. Step 2. Calculate the fitness value of each particle. Step 3. Update pbest and gbest. Step 4. Calculate the self-adaptive inertia weight for each particle. Step 5. Update the velocity and position of particles. Step 6. If the termination condition is met, the algorithm ends. Otherwise return to Step 2. References BIB004 and BIB007 also use Steiner Matrix to encode the particles, and introduce the mutation operation of GA into DPSO. In BIB004 , a matrix corresponding to a particle represents both position and velocity. Its velocity is updated by Eq. (3), while Eq. (4) is not used to update the position of the particle. The algorithm updates the position by selecting only some bits of the position matrix of the particles from the previous generation. This is the mutation process they introduced that can increase the efficiency and robustness of DPSO. Reference BIB007 uses PSO algorithm with constriction factor, that is, Eq. (7) is used to update the velocity and Eq. (4) is used to update the position. This algorithm adapts a novel mutation operation by selection of some bits of the previous position vector along with the information of the initial Steiner Matrix. Shen et al. BIB002 considered wirelength and obstacles at the same time and then proposed a novel OARSMT construction algorithm, which avoids obstacles by generating virtual vertexes of the real vertexes. The algorithm designs the following obstacle-avoiding strategy for the case where the three types of routing across obstacles shown in Figure 8 . Take Figure 8(a) as an example. First, vertices S and T respectively produce corresponding virtual vertices, which have the same horizontal coordinate with the left (or right) edge of the obstacle and the same vertical coordinate with the original vertices. Next, sequentially connect S, S , T and T , and dismantle the violate edges. The OARSMT construction is divided into the following two steps: (1) Divide all the pins of the net into k groups, and generate corresponding RSTs based on the above-mentioned obstacleavoiding strategy. The algorithm places the pins that are close to each other in a group, while making the amount of each group of pins (at least two pins) as small as possible. (2) Wirelength minimization is the optimization goal, and then BIB002 connects all of the groups considered as real vertexes to construct the final RST. In this algorithm, Prüfer number  is used to encode the solution of RST, and 0-1 coding is used to select Steiner points. For example, a particle is represented by: where the Prüfer number is {2,5,4,5,4}, and the Steiner point selection scheme is {0,1,0,0,1}, the total length of this tree is 100 and the obstacles quantities of this particle is 15. The algorithm introduces crossover and mutation operators inspired from GA to handle Prüfer numbers which are discrete magnitude. Based on SPSO (Eq. (3) ), the following position update formula is given for solving the discrete problems: Eq. (27) uses the ''+'' operation to connect the following three parts, in other words two operations including mutation and crossover operation. (1) Mutation operation: where F represents the mutation operator from GA with the probability of ω, and r 0 is a random number on the interval [0, 1). (2) Crossover operation: where F 1 , F 2 represent the crossover operators that influence self-cognitive and social-cognitive respectively, and the probabilities are c 1 and c 2 . r 1 and r 2 are random numbers on the interval [0, 1). This paper proposes a novel framework of PSO to solve OARMST problem and extends the application of SI algorithm in VLSI physical design. Many of the later works BIB003 BIB005 BIB008 BIB009 BIB010  BIB012 ,  , BIB011 , BIB006 , BIB001 are also based on this PSO framework of Eq. (27) .