A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> A. MULTI-LAYER ROUTING BASED ON X-ARCHITECTURE <s> Presents a branch and bound algorithm for computing a hexagonal Steiner minimum tree, where the fixed-topology problems are solved using PCx. Although currently it can only compute optimal solutions for small-sized instances, this algorithm makes it possible for researchers to compare heuristic solutions against optimal solutions for small-sized instances. Our min-min and max-min heuristics have also been shown to be good heuristic algorithms for computing hexagonal Steiner minimum trees, but not as good as the iterated I-Steiner heuristic. We have previously designed a linear time algorithm for computing an optimal layout of a minimum spanning tree, which can be viewed as a fast approximation to hexagonal Steiner minimum trees. <s> BIB001 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> A. MULTI-LAYER ROUTING BASED ON X-ARCHITECTURE <s> Octagonal Steiner Minimal Trees (OSMTs) are used in the global routing phase of pervasive octagonal VLSI layout. The OSMT problem seeks a minimal length spanning structure using edges composed of line segments having one of four equally spaced orientations. The concept of a canonical form is introduced providing a strong framework for the structure and characteristics of OSMTs. An exact algorithm and a variety of pruning techniques are introduced. Random and OR Library instances are solved and compared against rectilinear and Euclidean SMTs. These experiments demonstrate the utility of pervasive octagonal routing, showing that octagonal SMTs are consistently 10% smaller than rectilinear SMTs. <s> BIB002 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> A. MULTI-LAYER ROUTING BASED ON X-ARCHITECTURE <s> In dense integrated circuit designs, management of routing congestion is essential; an over congested design may be unroutable. Many factors influence congestion: placement, routing, and routing architecture all contribute. Previous work has shown that different placement tools can have substantially different demands for each routing layer; our objective is to develop methods that allow "tuning" of interconnect topologies to match routing resources.We focus on congestion minimization for both Manhattan and non-Manhattan routing architectures, and have two main contributions. First, we combine prior heuristics for non-Manhattan Steiner trees and Preferred Direction Steiner trees into a hybrid approach that can handle arbitrary routing directions, via minimization, and layer assignment of edges simultaneously. Second, we present an effective method to adjust Steiner tree topologies to match routing demand to resource, resulting in lower congestion and better routability. <s> BIB003 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> A. MULTI-LAYER ROUTING BASED ON X-ARCHITECTURE <s> In deep sub-micron (DSM) designs, wire delays comprise a significant fraction of the total delay of a design. Therefore, techniques such as non-Manhattan routing, which reduce the total wire length of a design, are highly relevant for today's designs. However, a great deal of effort has gone into the design and development of algorithms to perform Manhattan routing, both in industry and in academia. Therefore, it would be desirable to use existing Manhattan algorithms and tools to perform non-Manhattan routing. In this paper, we describe a technique to perform non-Manhattan routing by combining the results of two related Manhattan routing instances. The second routing instance is derived from the first by rotating the coordinate system by 45/spl deg/. As a result, the Manhattan routes that are computed for the second instance are actually 45 /spl deg/ rotated in the original coordinate system. We combine the results of the two instances to obtain a final routing result that contains non-Manhattan routes. We demonstrate that our router produces highly efficient results, reducing the total wire length by an average 9.8% over a traditional router, with a via-count increase of 2%. <s> BIB004 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> A. MULTI-LAYER ROUTING BASED ON X-ARCHITECTURE <s> In deep sub-micron regime, interconnect delays dominate VLSI circuit design. Thus, construction of cost-effective global routing trees is key to such designs. In order to reduce the interconnect delay, traditional Manhattan (M-) routing architectures are currently being replaced by the diagonal X architectures. A recent routing architecture is based on Y interconnects, involving the pervasive use of 0/spl deg/, 60/spl deg/, and 120/spl deg/ oriented global and semi-global wirings. Unlike the X-routing, Y-routing Is observed to support regular routing grid, which as important for simplifying manufacturing processes and routing and design rule checking algorithms. In this paper, we propose a novel Y-routing algorithm which can solve reasonably sized problems in nominal time. The proposed method is capable of finding routing solutions for problem instances which could not be solved in reasonable time by some recently reported methods. Moreover, it can be easily extended for routing with any uniform orientation. <s> BIB005 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> A. MULTI-LAYER ROUTING BASED ON X-ARCHITECTURE <s> In this paper, we present an X-architecture multilevel full-chip router, called X-Route. Unlike the traditional Λ-shaped multilevel framework that adopts bottom-up coarsening followed by top-down uncoarsening, our multilevel framework runs in the Vshaped manner: top-down uncoarsening followed by bottom-up coarsening. The top-down uncoarsening stage performs octagonal global routing and X-detailed routing for local nets at each level and then refines the solution for the next level. Then, the bottom-up coarsening stage performs the X-detailed routing to reroute failed nets and refines the solution level by level. Since we perform top-down routing first, global long nets are routed earlier. To prevent a wrong decision from blocking the later nets, we keep a dynamic congestion map that records the updated routing congestion information based on the routed nets and the global-path prediction of the unrouted nets. To take full advantage of the X-architecture, we also develop a progressive X-Steiner tree algorithm based on the delaunay triangulation approach for the X-architecture. Compared with the state-of-the-art Λ-shaped multilevel routing for the X-architecture, experimental results show that our X-Route reduces the respective wirelength and average delay by about 14.05% and 30.62%, with better routing completion. <s> BIB006 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> A. MULTI-LAYER ROUTING BASED ON X-ARCHITECTURE <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> BIB007 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> A. MULTI-LAYER ROUTING BASED ON X-ARCHITECTURE <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> BIB008 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> A. MULTI-LAYER ROUTING BASED ON X-ARCHITECTURE <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> BIB009 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> A. MULTI-LAYER ROUTING BASED ON X-ARCHITECTURE <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> BIB010 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> A. MULTI-LAYER ROUTING BASED ON X-ARCHITECTURE <s> With the sharp increase of very large-scale integrated (VLSI) circuit density, we are faced with many knotty issues. Particularly in the routing phase of VLSI physical design, the interconnection effects directly relate to the final performance of circuits. However, the optimization capability of traditional rectilinear architecture is limited; thus, both academia and industry have been devoted to nonrectilinear architecture in recent years, especially octilinear architecture, which is the most promising because it can greatly improve the performance of modern chips. In this article, we design FH-OAOS, an obstacle-avoiding algorithm in octilinear architecture, by constructing an obstacle-avoiding the octilinear Steiner minimal tree (OAOSMT). Our approach first constructs an obstacle-free Euclidean minimal spanning tree (OFEMST) on the given pins based on Delaunay triangulation (DT). Then, two lookup tables about OFEMST’s edge are generated, which can be seen as the information center of FH-OAOS and can provide information support for algorithm operation. Next, an efficient obstacle-avoiding strategy is proposed to convert the OFEMST into an obstacle-avoiding octilinear Steiner tree (OAOST). Finally, the generated OAOST is refined to construct the final OAOSMT by applying three effective strategies. Experimental results on various benchmarks show that FH-OAOS achieves 66.39 times speedup on average, while the average wirelength of the final OAOSMT is only 0.36p larger than the best existing solution. <s> BIB011 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> A. MULTI-LAYER ROUTING BASED ON X-ARCHITECTURE <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 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> A. MULTI-LAYER ROUTING BASED ON X-ARCHITECTURE <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> BIB013
In recent years, more and more researches BIB007 BIB008 BIB009 BIB010 ,  , BIB012 , BIB013 , BIB011 ,  have been conducted on X-architecture SMT construction. However, most of the SI algorithms are used to solve the RSMT problem. Because the early global routing algorithms are based on Manhattan architecture, the wirelength and interconnection delay are optimized by optimizing the Steiner tree topology, transforming the wire width, and inserting buffers, thereby helping to upgrade performance of the chip. Moreover, when the global routing based on Manhattan architecture optimizes the interconnect length, its optimization ability is limited since the routing direction can only be horizontal and vertical. Therefore, it is necessary to change the traditional Manhattan architecture from the root of the problem. The proposed X-architecture model makes up for the limitation of the RST routing directions, which can make full use of the routing area and interconnection resources. So that it can further reduce the chip area, shorten the wirelength, reduce power consumption, and make many performance indicators in the physical design get promoted. At present, most of the research works on solving non-Manhattan architecture Steiner trees are based on exact algorithms BIB001 , BIB002 and traditional heuristic algorithms BIB005 ,  . The time complexity of the exact algorithms grows exponentially with the size of the problem, while the traditional heuristic algorithms are mostly based on greedy strategies and are prone to local extrema. And when constructing Steiner trees, they do not make full use of the geometric properties of non-Manhattan architecture, and cannot guarantee the quality of Steiner trees. Therefore, it is of great practical significance to explore routing algorithms based on various SI techniques. At present, some works BIB007 BIB008 BIB009 BIB010 ,  , BIB012 have applied PSO to X-architecture routing and achieved good results. As IC design enters the nano-field, the number of routing metal layers continues to increase, making multi-layer global routing face a huge challenge. However, the research work on non-Manhattan architecture mainly focuses on the construction of Steiner tree, and there is a lack of research on multi-layer global routing algorithms. The current research status at home and abroad BIB004 BIB006 BIB003 shows that although the non-Manhattan structure can effectively reduce the wirelength and chip area, greatly improve the performance and density of chips, but the cost of the number of vias are increased at the same time. In multi-layer routing, the number and size of vias are key optimization goals. Therefore, constructing an efficient multi-layer global router under the non-Manhattan architecture is an important theoretical and practical work.