A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> 1) PROBLEM FORMULATION <s> For the macrocell design style and for routing problems in which the routing regions are irregular, two-dimensional routers are often necessary. In this paper, a new routing technique that can be applied for general two-layer detailed routing problems, including switchboxes, channels, and partially routed areas, is presented. The routing regions that can be handled are very general: the boundaries can be described by any rectilinear edges, the pins can be on or inside the boundaries of the region, and the obstructions can be of any shape and size. The technique is based on an algorithm that routes the nets in the routing region incrementally and intelligently, and allows modifications and rip-up of nets when an existing shortest path is "far" from optimal or when no path exists. The modification steps (also called weak modification) relocate some segments of nets already routed to find a shorter path or to make room for a blocked net. The rip-up and reroute steps (called strong modifiction) remove segments of nets already routed to make room for a blocked connection; these steps are invoked only if weak modification fails. The algorithm has been rigorously proven to complete in finite time and its complexity has been analyzed. The algorithm has been implemented in the "C" programming language. Many test cases have been run, and on all the examples known in the literature the router has performed as well as or better than existing algorithms. In particular, Burstein's difficult switchbox example has been routed using one less column than the original data. In addition, the router has routed difficult channels such as Deutsch's in density and has performed better than or as well as YACR-II on all the channels available to us. <s> BIB001 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> 1) PROBLEM FORMULATION <s> Deep submicron effects, along with increasing interconnect densities, have increased the complexity of the routing problem. Whereas previously we could focus on minimizing wirelength, we must now consider a variety of objectives during routing. For example, an increased amount of timing restrictions means that we must minimize interconnect delay. But, interconnect delay is no longer simply related to wirelength. Coupling capacitance has become a dominant component of delay due to the shrinking of device sizes. Regardless, the most important objective is producing a routable circuit. Unfortunately, this often conflicts with minimizing interconnect delay as minimum delay routes create congested areas, for which an exact routing cannot be realized without violating design rules. In this work, we use the concept of pattern routing to develop algorithms that guide the router to a solution that minimizes interconnect delay - by considering both coupling and wirelength-without damaging the routability of the circuit. The paper is divided into two parts. The first part demonstrates that pattern routing can be used without affecting the routability of the circuit. We propose two schemes to choose a set of nets to pattern route. Using these schemes, we show that the routability is not hindered. The second part builds on the previous part by presenting a framework for coupling reduction using pattern routing. We develop theory and algorithms relating pattern routing and coupling. Additionally, we give suggestions on how to extend our theory and use our algorithms for both global and detailed routing. <s> BIB002 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> 1) PROBLEM FORMULATION <s> In nanometer-scale VLSI technologies, several interconnect issues like routing congestion and interconnect delay have become the main concerns in placement. However, all previous placement approaches optimize some very primitive interconnect models during placement. These models are far from the actual interconnect implementation in the routing stage. As a result, placement solution considered to be good by primitive interconnect models may turn out to be poor after routing. In addition, the placement may not even be routable and timing closure may not be achievable. In this paper, we propose to address the inconsistency between the placement and routing objectives by fully integrating global routing into placement. As a first attempt to this novel approach, we focus on routability issue. We call the proposed algorithm for routing congestion minimization IPR (Integrated Placement and Routing). To ensure the algorithm to be computationally efficient, efficient placement and routing algorithms FastPlace, FastDP and FastRoute are integrated, and well-designed methods are proposed to integrate them efficiently and effectively. Experimental results show that IPR reduces overflow by 36%, global routing wirelength by 3.6%, and runtime by 36% comparing to ROOSTER [5], which is the previous best academic routability-driven placer. <s> BIB003 </s> A Survey of Swarm Intelligence Techniques in VLSI Routing Problems <s> 1) PROBLEM FORMULATION <s> Wire routing, an important step in modern VLSI design, is increasingly responsible for timing closure and manufacturability. The CAD community has witnessed remarkable improvements in speed and quality of global routing algorithms in response to the inaugural ISPD 2007 Global Routing Contest, where prizes were awarded for best results on a new set of large industry benchmarks. In this paper, we review the state of the art in global routing and identify several critical techniques that distinguish top routing algorithms. We also discuss open challenges and offer predictions regarding the future of routing research. <s> BIB004
For global routing, modern designs usually have several metal layers and two adjacent layers are linked by vias as shown in Figure 2 (b). We use a grid diagram to describe the global routing model, that is, the entire routing area is divided into a set of rectangles with rows and columns interlaced. Each Global Routing Cell (GRC) is represented by one vertex, and the adjacency relationship between GRCs is represented by horizontal and vertical edges. For a given set of nets, their pin sets are mapped to the vertices corresponding to the GRC according to the placement of this GRC. Figure 3 gives a GRG which is a set of dotted grids of interlaced rows and columns. Each dotted grid box represents a GRC, and a pin set is placed in the corresponding GRC according to the result of the layout. Each GRC is mapped into GRG as a vertex (v) of GRG, and two GRCs having an adjacency relation are connected by an edge (e) of GRG. So the relationship between GRC and GRG is one-to-one. The global routing problem of VLSI can be described as follows: There is a grid-graph G specifying a set of vertices V and a set of edges E. As shown in Figure 2 , each vertex v i ∈ V corresponds to a rectangular region (or GRC) of the chip, and each edge e ij ∈ E corresponds to a boundary between adjacent vertices. And there is a set of nets N , each net n i ∈ N includes a set of pins P i and each pin corresponds to a vertex v i . The routing solution for a net is to find a tree that connects all pins of the net by using vias and routing edges. A solution of global routing is a set of SMTs in a grid graph, and a net corresponds to a Steiner tree that satisfies constraints. The goal of this phase is to minimize the length of the Steiner trees. When evaluating a routing solution, one is typically concerned with three metrics, that is overflow, wirelength, runtime BIB004 . Overflow refers to the total amount of demand that exceeds capacity over all edges, here the demand corresponds to the number of routes that pass though the vertex BIB002 . In the actual design, we want this index to be as small as possible, ideally zero. The overflow of a routing edge e is defined as shown below: where d e represents the amount of nets that pass through e. The capacity c e of routing edge e represents the number of available routing tracks it contains. Wirelength is the total length of the segments that need to be connected for all nets, and it is desirable to be as small as possible. When using the routing tree models, the wirelength is generally equal to the length of the routing trees. Therefore, in many cases, various minimum trees are needed to be designed to solve the global routing problem. The Steiner tree mentioned above is one of the most common and effective models for solving global routing. In multi-dimensional routing, this calculation can also include vias. Time is an indicator that we are particularly concerned about especially when reusing global routing to guide the layout algorithms BIB003 . For detailed routing based on grid models, the goal is to find a legal routing path on a given routing grid and detour the crowded area as much as possible. The relevant definitions and problem formula for detailed routing are given below BIB001 . Definition 1: Channel (Routing Area). A rectilinear polygonal region between circuit blocks that can be used for interconnections (shown in Figure 4 ). The routing area is a right angle polygon. The location where the pins appear may be in the area or on the boundary. At the same time, we would like to take into account obstacles of various shapes and sizes. Detailed routing requires that all components of each net be connected within the routing area. The primary goal is to make the routing area as small as possible, and second, to minimize the number of vias and the wirelength of each net. At this stage, many other factors are also considered like power consumption, delay, coupling of interconnects, and so on.