A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> B. EXPLORE NEW AND AVAILABLE SI TECHNIQUE <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> B. EXPLORE NEW AND AVAILABLE SI TECHNIQUE <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> B. EXPLORE NEW AND AVAILABLE SI TECHNIQUE <s> The Rectilinear Steiner Minimal Tree (RSMT) problem is an NP-hard problem, which is one of the key problems in VLSI/ULSI physical design. Particle Swarm Optimization (PSO) has been proved to be an efficient intelligent algorithm for optimization designs. This paper presents a RSMT algorithm based on discrete PSO (DPSO), namely BRRA_DPSO, to minimize the wiring length and reduce the number of bends, which is helpful for via reduction and reliability increment in the routing phase. 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 RSMT problem with good quality and converge more rapidly than GA. Moreover, the algorithm can also reduce the number of bends. <s> BIB003 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> B. EXPLORE NEW AND AVAILABLE SI TECHNIQUE <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> BIB004 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> B. EXPLORE NEW AND AVAILABLE SI TECHNIQUE <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> BIB005 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> B. EXPLORE NEW AND AVAILABLE SI TECHNIQUE <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> BIB006 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> B. EXPLORE NEW AND AVAILABLE SI TECHNIQUE <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> BIB007 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> B. EXPLORE NEW AND AVAILABLE SI TECHNIQUE <s> In this paper multiobjective optimization problem simultaneously optimized using PSO algorithm has been attempted. The methodology used in this paper is based upon the information sharing and movement of swarms or particles in a search space. Multiobjective optimization problems are present at physical design level at partitioning process of VLSI circuit optimization. Here present the results of multiobjective optimization of cutsize, delay and sleep time simultaneously using swarm technique (PSO). Results in this paper shows that the NP hard problem effectively solved by PSO algorithm. Here set up the problem as a simultaneously multiobjective optimization and solve it by programming method. Information of the circuit has been given in accordance with circuit netlist files used in ISPD'98 circuit benchmark suite. The proposed approach has a good potential in VLSI circuit partitioning. <s> BIB008 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> B. EXPLORE NEW AND AVAILABLE SI TECHNIQUE <s> Placement process is one of the vital stages in physical desi gn. In this stage, modules and elements of circuit are placed in distinct locations according to optimization basis. Pla cement algorithms try to minimize the longest delay along the paths in the circuit and/or minimize the total wire length. So placement is an important step in circuit architecture. After it, we ca n reach to routing stage. It is known that particle swarm optimization (PSO) is one of the practical evolutionary algorithms for this kind o f applications. In this project, a novel method for optimized module placement has been used. According to this process objectives in this issue were wirelength and overlap removal function, consequently we were forced to use multi-objective particle swarm optimization (MOPSO) in the algorithm. Structure of MOPSO is in a way that introduces set of answers, we had been tried to find a unique answer with mi nimum overlap. This algorithm has less run time as compared with other methods of placement, run time plays an important role in VLSI circuit design. Also the experiments on GSRC benchmarks show that the proposed algorithm is effective, and gives out many optional results for users choice in the physical design of VLSI circuits. <s> BIB009 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> B. EXPLORE NEW AND AVAILABLE SI TECHNIQUE <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> BIB010 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> B. EXPLORE NEW AND AVAILABLE SI TECHNIQUE <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> BIB011 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> B. EXPLORE NEW AND AVAILABLE SI TECHNIQUE <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> BIB012 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> B. EXPLORE NEW AND AVAILABLE SI TECHNIQUE <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> BIB013 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> B. EXPLORE NEW AND AVAILABLE SI TECHNIQUE <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> BIB014 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> B. EXPLORE NEW AND AVAILABLE SI TECHNIQUE <s> Function evaluations (FEs) of many real-world optimization problems are time or resource consuming, posing a serious challenge to the application of evolutionary algorithms (EAs) to solve these problems. To address this challenge, the research on surrogate-assisted EAs has attracted increasing attention from both academia and industry over the past decades. However, most existing surrogate-assisted EAs (SAEAs) either still require thousands of expensive FEs to obtain acceptable solutions, or are only applied to very low-dimensional problems. In this paper, a novel surrogate-assisted particle swarm optimization (PSO) inspired from committee-based active learning (CAL) is proposed. In the proposed algorithm, a global model management strategy inspired from CAL is developed, which searches for the best and most uncertain solutions according to a surrogate ensemble using a PSO algorithm and evaluates these solutions using the expensive objective function. In addition, a local surrogate model is built around the best solution obtained so far. Then, a PSO algorithm searches on the local surrogate to find its optimum and evaluates it. The evolutionary search using the global model management strategy switches to the local search once no further improvement can be observed, and vice versa. This iterative search process continues until the computational budget is exhausted. Experimental results comparing the proposed algorithm with a few state-of-the-art SAEAs on both benchmark problems up to 30 decision variables as well as an airfoil design problem demonstrate that the proposed algorithm is able to achieve better or competitive solutions with a limited budget of hundreds of exact FEs. <s> BIB015 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> B. EXPLORE NEW AND AVAILABLE SI TECHNIQUE <s> Bi-level optimization problems with constraints are well known for wide applications and difficulties. A new particle swarm optimization algorithm (PSO) with dynamic constraint processing is proposed. First, we divide constraints into three cases and design a new PSO based crossover operator to dynamically deal with constraints; second, a normal distribution is added into PSO to work as mutation operator, which will enhance the diversity of the swarm and navigate the search direction. Finally, we give the convergence proof of the proposed algorithm. <s> BIB016 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> B. EXPLORE NEW AND AVAILABLE SI TECHNIQUE <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> BIB017 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> B. EXPLORE NEW AND AVAILABLE SI TECHNIQUE <s> As the best connection model for the multi-pin net of the non-Manhattan architecture global routing problem, the X-architecture Steiner Minimum Tree (XSMT) construction is a Non-deterministic Polynomial hard (NP-hard) problem. The Differential Evolution (DE) algorithm has shown good application effect in solving various NP-hard problems. For this reason, based on the idea of DE algorithm, this paper proposes an XSMT construction algorithm for solving this problem. First of all, because the traditional DE algorithm is designed for continuous problems, the optimization ability is limited in solving discrete problems. This paper proposes a novel crossover operator and mutation operator. At the same time, in order to maintain the effectiveness of the evolutionary algorithm, an Edge-to-Point coding strategy suitable for evolutionary algorithms is proposed to better preserve the optimal substructure of the population. Finally, in order to speed up the convergence speed and quality of the algorithm, this paper proposes an initial solution based on the minimum tree generation algorithm. Experiments show that the effectiveness of the proposed algorithm and related strategies can construct a high-quality XSMT solution. <s> BIB018
The exploration and exploitation abilities of the SI algorithms are well played in the VLSI routing problems, and have contributed greatly to improving the quality and runtime of the routing algorithms. Among the above-mentioned SI techniques, PSO is simple and easy to implement, and has strong global optimization ability. Figure 15 gives a yearly distribution of the SI techniques applied to VLSI routing subproblems in surveyed works. It shows that PSO has become the most widely used SI technique in surveyed VLSI routing problems since 2009. Since this technology was proposed, it has attracted great attention from many scholars. In just a few years, a research hotspot has been formed and a large number of research results have been obtained. In recent years, PSO has been widely used in VLSI partitioning BIB008 , floorplanning and placement BIB001 , BIB009 , routing  BIB005 BIB010 BIB002 BIB004 BIB006 BIB011 BIB012 and other fields BIB015 , BIB016 . Moreover, in our preliminary work BIB003 , BIB004 BIB006 BIB011 BIB012 BIB013  BIB017 ,  , BIB014 , BIB018 , BIB007 , BIB001 ,  , PSO has also been well applied to solve related problems in VLSI physical design. A large number of experimental results show that the PSO algorithm is indeed a beneficial optimization tool and has strong vitality. Therefore, exploring new and available SI techniques is also one of the research directions for future VLSI routing problems.