A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> 1) PROBLEM DESCRIPTION <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> BIB001 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> 1) PROBLEM DESCRIPTION <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> BIB002
The Steiner Minimum Tree (SMT) problem is to connect all pins through some extra points (called Steiner points) to achieve a minimal total length in VLSI routing. In most routing problems, the segments can only route horizontally or vertically. This kind of routing tree is called Rectilinear Steiner Tree (RST). Rectilinear Steiner Minimum Tree (RSMT) construction is a NP-hard problem, which is as follows BIB002 : Given a set of points in the plane, the RSMT problem seeks to connect the points with a RST, which is a tree made up of horizontal and vertical line segments with the minimum cost. The cost of any edge in the tree is the rectilinear or Manhattan distance between its endpoints, and the cost of a tree is the sum of its edge costs. However, this way of routing only horizontally and vertically limits the optimization of wirelength, so more research-oriented non-Manhattan architectures were proposed BIB001 ,  . Non-manhattan architecture routing trees mainly include Hexagonal Steiner Tree (HST) BIB001 and Octagonal Steiner Tree (OST)  . The routing directions of HST are considered at 0 • , 60 • and 120 • to the horizontal direction called Y-routing, while OST with X-routing allows 45 • and 135 • directions in additon to traditional horizontal and vertical orientations. The non-Manhattan architecture related issues involved in this paper refers to X-architecture. Diversification of interconnection structures improves routing quality and improves chip performance.