A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> 2) APPLYING PSO TO GLOBAL ROUTING <s> The performance of very large scale integration (VLSI) circuits is depends on the interconnected routing in the circuits. In VLSI routing, wire sizing, buffer sizing, and buffer insertion are techniques to improve power dissipation, area usage, noise, crosstalk, and time delay. Without considering buffer insertion, the shortest path in routing is assumed having the minimum delay and better performance. However, the interconnect delay can be further improved if buffers are inserted at proper locations along the routing path. Hence, this paper proposes a heuristic technique to simultaneously find the optimal routing path and buffer location for minimal interconnect delay in VLSI based on particle swarm optimization (PSO). PSO is a robust stochastic optimization technique based on the movement and information sharing of swarms. In this study, location of doglegs is employed to model the particles that represent the routing solutions in VLSI. The proposed approach has a good potential in VLSI routing and can be further extended in future <s> BIB001 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> 2) APPLYING PSO TO GLOBAL ROUTING <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> BIB002
PSO is also widely used for global routing because of its simplicity and the ability to quickly converge to an ideal solution. Minimizing wirelength and reducing congestion are the most common and important tasks for global routing. Liu et al. BIB002 proposed a high-quality VLSI global router in X-architecture called XGRouter, which was based on ILP techniques, partition strategy and PSO. Their ILP formulation, called O-ILP, considers the congestion uniformity to get a more even routing distribution without generating too many hot spots and the solution has no overflowed edges. At the main stage of their algorithm, ILP is formulated from the original routing sub-region and an improved PSO is designed to solve the O-ILP formulation. In their proposed PSO, the 0-1 integer encoding is used for particle encoding, which can satisfy the completeness and non-redundancy principle. And based on the update formula of particles (Eq. (27)), a check strategy is incorporated in the crossover and mutation operators to meet the soundness principle. Finally, not only the wirelength but also the congestion uniformity is considered into the fitness function to generate better solutions. Reference  presents some enhancements based on XGRouter. In this paper, some new types of routing are introduced and PSO algorithm is combined with maze routing. This improved algorithm can be applied to multi-layer routing model, which can achieve good results on overflows and total cost of wirelength. With the continuous development of the manufacturing process and design scale of IC, the feature size is continuously reduced, the parasitic effect of the connection is not negligible, and the interconnection delay exceeds the gate delay, which becomes the main factor determining the performance of the circuit. Therefore, it is necessary to consider other typical performance optimization targets except wirelength, such as delay and power dissipation. Several techniques have been used to reduce interconnection delay − wire sizing, buffer insertion, and buffer sizing. Among them, buffer insertion is the most effective interconnection optimization method to reduce delay. Ayob et al. BIB001 employed PSO to solve buffer insertion problem in VLSI routing, with considerations on wire and buffer obstacles. They used distributed RC network as interconnected model and applied the Elmore Delay formulation to calculate the interconnection delay from source to sink.