A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> b: OST 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> BIB001 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> b: OST 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> BIB002 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> b: OST 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> BIB003 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> b: OST 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> BIB004 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> b: OST 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> BIB005 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> b: OST 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> BIB006 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> b: OST 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> BIB007
Liu et al. BIB002 , BIB003 , Huang et al. BIB003 , BIB004 , and Liu et al. BIB005 BIB006  BIB007 have done a lot of research work on the construction of Octagonal Steiner Minimum Tree (OSMT) based on the following interconnected structure, and have achieved excellent results. Interconnected Structure. There are four choices for line segment L of connecting pins A and B as shown in Figure 9 . And BIB002 gives four definitions about selection of Steiner points. Definition 6: Choice 0 (as shown in Figure 9 (b)). The Choice 0 of Steiner point corresponding to edge L is defined as leading rectilinear side first from A to Steiner point S, and then leading non-rectilinear side to B. Definition 7: Choice 1 (as shown in Figure 9 (c)). The Choice 1 of Steiner point corresponding to edge L is defined as leading non-rectilinear side first from A to Steiner point S, and then leading rectilinear side to B. Definition 8: Choice 2 (as shown in Figure 9(d) ). The Choice 2 of Steiner point corresponding to edge L is defined as leading vertical side first from A to Steiner point S, and then leading horizontal side to B. Definition 9: Choice 3 (as shown in Figure 9 (e)). The Choice 3 of Steiner point corresponding to edge L is defined as leading horizontal side first from A to Steiner point S, and then leading vertical side to B. Particle Encoding. Based on the above design of interconnected wire, BIB002 uses numerical encoding called Edgeto-Point encoding to represent each candidate OST: For a net with n pins, a spanning tree would have n-1 edges, n-1 Steiner points and one extra bit which is the fitness of particle. Besides, two bits represent the two vertices of each edge. Namely, the particle is encoded with a numerical string of 3×(n-1)+1. For example, a particle can be expressed as follows: where the number '0.0100' is the fitness of the particle and each number in bold represents the Steiner point choice. Taking the first substring (7, 6, 0) for instance, it represents one edge of the spanning tree which is composed of Vertex 7, Vertex 6 and the Steiner point choice (Choice 0). Reference BIB002 introduces mutation and crossover operations as particle update strategies like BIB001 . Like the problems of RST, we also study related problems of OST such as Obstacle-Avoiding Octagonal Steiner Minimum Tree (OAOSMT). References BIB003 BIB004 BIB005 consider the construction of OST with key issues such as obstacles, delay and number of bends, also based on this encoding method and particle update strategies, while using Union-Find Sets (UFS) to prevent the generation of invalid solutions. Reference  constructs OSMT based on self-adapting PSO with an effective Hybrid Transformation Strategy (HTS) to enlarge the search space. While BIB007 presents a unified algorithm for both octagonal and rectilinear SMT construction, and also applies HTS to PSO, which can achieve a better wirelength optimization. These two algorithms both have an ability to obtain multiple topologies of Steiner trees with the same wirelength, so that it can provide different topology options for congestion optimization in global routing.