In this article, we dive deep into the world of global routing and the crucial design flow behind it. We begin with an introduction to essential routing terminology and explore the concept of a switchbox in routing. Learn how optimization goals play a vital role in global routing and how routing regions are represented for effective design. We’ll take you through the global routing flow, covering topics like single-net routing, global routing in connectivity graphs, and the key algorithms used for finding the shortest path—Dijkstra’s Algorithm and A* Search. The video also explores the full netlist routing process and the role of a global router. We then discuss optimization techniques for different design types: full custom designs, standard cell designs, and gate array designs. This article offers a comprehensive understanding of global routing, its flow, and optimization strategies, making it a must-read for anyone interested in VLSI design and routing techniques.
Design Flow & Global Routing:
In VLSI , routing is a crucial step that connects the various components like logic gates, transistors, and memory cells on a chip. It involves determining the paths for electrical connections, which are implemented through metal layers on the chip.
Routing is divided into three major stages:
(i) Global, (ii) Detailed & (iii) Specialized Routing.
Global Routing: Initial stage of the routing process, where the chip's overall routing framework is determined. It defines the general paths for each connection/net without focusing on precise details. The goal of global routing is to create an approximate plan for how the nets will be routed across the chip.
Key Aspects of Global Routing:
(i) Calculates approximate net paths and assigns them to regions or grids within the chip.
(ii) Allocates appropriate metal layers for detailed routing without specifying exact geometry.
(iii) Prevents congestion by ensuring sufficient routing space for all nets.
(iv) Divides the chip into grids, systematically determining regions for each net.
(v) Focuses on optimizing overall interconnection layout rather than precise routing geometry.
Detailed & Specialized Routing:
Detailed Routing:
This stage refines global routing into precise, manufacturable paths, finalizing the layout of electrical interconnections for fabrication.
Key Aspects of Detailed Routing:
Detailed routing defines precise wire paths while adhering to design rules, including spacing, width, via placement, and metal layer usage. It optimizes vias, ensures signal integrity by minimizing RC delay and crosstalk, and resolves congestion by redistributing wires or using alternative layers. Special attention is given to power and ground routing to guarantee reliable voltage delivery across the chip.
Specialized Routing:
Specialized routing handles nets with specific requirements, such as clocks, power networks, and high-speed signals, ensuring they meet performance constraints.
Key Aspects of Specialized Routing:
Specialized routing includes critical net and clock routing, ensuring precise timing and reliability. It also covers power and ground distribution, high-speed signal routing and shielding for noise reduction. These ensure optimal performance and signal integrity in complex designs.
Essential Terminology for Global Routing:
1. Routing Track : A routing track represents a horizontal or vertical wiring path that facilitates the routing of signals. Signal nets traverse these paths by alternating between horizontal tracks and vertical columns, connected using inter-layer vias.
2. Routing Region : A routing region is a defined area containing routing tracks or columns. It serves as the guide for allocating wiring paths to connect signal nets efficiently.
3. Uniform Routing Region: These regions consist of evenly spaced horizontal and vertical grid lines, forming what’s known as a "global grid" or "grid." The grid comprises unit cells called "global cells" (gcells). Typically, the spacing between grid lines ranges from 7 to 40 routing tracks, balancing the complexities of chip-scale global routing and detailed routing tasks.
4. Non-Uniform Routing Region: Unlike their uniform counterparts, non-uniform regions are defined by boundaries aligned with external pin connections or macro-cell edges. That regions include channels and switch boxes of varying dimensions.
5. Channel : A channel is a rectangular routing region designed to connect pins located on its two opposite sides, while the other two sides remain pin-free. Channels are further classified as:
(a) Horizontal Channel: Features pins along the top and bottom boundaries.
(b) Vertical Channel: Features pins along the left and right boundaries.
6. Gcells (Global Cells) : Global cells, or gcells, are the fundamental units within a global grid. They serve as the basic building blocks for defining paths in routing regions and are instrumental in the routing process.
What is SwitchBox in Routing?
Switchbox :
A switchbox is a square or rectangular region where multiple channels intersect. These critical structures enable connections between different routing tracks or columns, enhancing the routing network's flexibility.
2-D Switchbox : A 2-D switchbox exists in a single plane and connects horizontal and vertical routing channels within a single metal layer. It serves as a connection hub, enabling routing paths to switch directions (e.g., horizontal to vertical or vice versa) within a specific routing layer. Frequently used in PCB design or simpler VLSI designs where inter-layer routing is minimal or non-existent. The region typically resembles a rectangular or square grid with intersection points for connecting different channels.
3-D Switchbox : A 3-D switchbox incorporates connections across multiple layers of a chip, often through inter-layer vias. It facilitates interconnections not only between horizontal and vertical tracks but also between different metal layers. This capability is crucial for modern multi-layered Ics. Widely used in advanced VLSI designs where chips have multiple layers of metal routing, such as in 3D ICs or multi-layer ASICs. Extends the concept of the 2-D switchbox to include vertical pathways, allowing signals to traverse different physical planes within the chip.
Optimization Goals in Global Routing :
1. Minimizing Total Wire length : Wire length minimization is a fundamental goal in global routing. Reducing the total wire length enhances performance. Shorter wires reduce signal propagation delays, leading to faster circuits. Less wire length means reduced capacitance and, consequently, lower power dissipation. Shorter interconnects decrease the chances of defects and increase manufacturability.
2. Managing Routing Congestion : Congestion arises when multiple signal nets compete for the same routing resources. Effective congestion management ensures efficient resource utilization, prevents overloading specific regions while under utilizing others, avoids unnecessary detours that can increase wire length and delays. Reduces the risk of violating constraints such as spacing between wires.
3. Maximizing Timing Slack : Timing slack refers to the difference between the required arrival time and the actual arrival time of a signal. Maximizing timing slack is crucial for meeting timing constraints. That ensures that all signals arrive within their designated time windows. Provides a buffer against variations in manufacturing or operational conditions.
4. Balancing Via Usage : Vias connect different metal layers in a chip’s layout. Excessive via usage can increase manufacturing costs, lead to reliability issues due to thermal stress, add delays by introducing additional resistance and capacitance. Balancing via usage is therefore vital for cost-efficient and reliable designs.
5. Optimizing for Power Efficiency : Power optimization is critical, especially for portable devices and data centers. Efficient global routing minimizes dynamic power by reducing switching activity and interconnect capacitance, minimizes static power through efficient use of routing resources to minimize leakage.
6. Adapting to Design Constraints : Modern VLSI designs face constraints like fixed-die boundaries, specific routing resources, and pre-defined placement. Optimization ensures that these constraints are respected without compromising the overall design quality.
Representing Routing Regions:
In Global routing channels and switch boxes are represented as graph, where nodes represent routing regions and edges represent adjoining regions.There are 3 graph techniques :
(i) Grid Graph :
Also defined a s Global Grid/ggrid . A uniform grid overlays the chip layout. It consists of horizontal and vertical grid lines that divide the chip into smaller cells, known as global cells (gcells). Grid lines are spaced at regular intervals to balance global and detailed routing complexity.
(ii) Channel connectivity graph :
G = (V,E), where the nodes v ∈ V represent channels, and the edges E represent adjacency of the channels. Capacity of each channel is represented in its respective graph node.
(iii) Switchbox connectivity graph :
G = (V, E), where the nodes v ∈ V represent switch boxes and an edge exists between two nodes if the corresponding switch boxes are on opposite sides of the same channel .
Global Routing Flow :
1. Defining The Routing Regions:
- Partition the layout area into routing regions.
- Allow nets to be routed over standard cells in some cases.
- Structure the routing regions as 2D/3D channels, switch boxes, or other region types.
- Represent the regions, along with their capacities and connections, as a graph.
2. Mapping Nets to the Routing Regions:
- Provisionally assign each net in the design to one or more routing regions to connect all its pins.
- Ensure the number of nets passing through a routing region does not exceed its routing capacity.
- Consider timing and congestion as factors influencing the path selection for each net.
3. Assigning Cross points:
- Assign routes to specific spots/cross points, along the edges of routing areas.
- Align crosspoints to simplify handling designs with millions of cells.
- Enable faster processing through parallel and distributed methods by allowing independent work on each routing area.
- Analyze the dependencies between net connections and the order of routing channels to optimize cross point assignments.
Single Net Routing:
A set of pins that electrically connected is called net. A single-net routing task deals with routing one such net at a time, ensuring it adheres to design rules while optimizing for factors such as wire length, timing, and congestion. For a two-pin net, the task is relatively straightforward, requiring a path between the two pins. For a multi-pin net, the net is decomposed into smaller two-pin sub nets before routing.
Objectives of Single-Net Routing:
1. Minimize Wire length: Reducing the total length of the wire connecting pins minimizes delays and power consumption.
2. Adhere to Design Rules: Ensure the route meets constraints like spacing, via limits, and layer assignments.
3. Avoid Obstacles: Navigate around fixed blocks, macros, and other routed nets.
4. Optimize Timing: Critical nets must be routed with minimal delay to meet performance requirements.
Techniques for Single-Net Routing:
1. Rectilinear spanning tree:
A rectilinear spanning tree connects all terminals (pins) using only direct pin-to-pin connections with vertical and horizontal segments. These connections are restricted to meeting exclusively at pins, meaning that “crossing” edges do not intersect, and no additional junction points (Steiner points) are introduced. When the total length of the segments is minimized, it is called a rectilinear minimum spanning tree (RMST).
2. Rectilinear Steiner tree (RST):
A rectilinear Steiner tree (RST) connects all pin locations and may include additional locations known as Steiner points. While any rectilinear spanning tree for a p-pin net qualifies as an RST, introducing strategically placed Steiner points can often reduce the total net length. An RST becomes a rectilinear Steiner minimum tree (RSMT) when the total length of the segments used to connect all pins is minimized.
Global Routing in Connectivity Graph:
Global Routing in connectivity graph is done in following
sequence steps.
(a) Defining the Routing Regions :
The vertical and horizontal routing regions are formed by stretching the bounding box of cells in each direction until a cell or chip boundary is reached.
(b) Defining the Connectivity Graph:
In the connectivity graph, nodes represent routing regions, edges indicate their continuity, and each node stores the horizontal and vertical capacities of its region.
(c) Determining the Net Order :
The order of net processing can be set before or during routing, based on factors like criticality, pin count, bounding box size (larger gets higher priority), or electrical properties. Some algorithms adjust dynamically based on layout characteristics observed during routing.
(d) Assigning Tracks for all pin Connections :
A horizontal and vertical track are reserved in each pin's routing region to ensure connectivity.
(e) Global Routing of all Nets :
Each net is processed sequentially, involving steps such as net or sub-net ordering, track assignment using a maze-routing algorithm, and capacity updates in the connectivity graph.
Finding Shortest Path by Dijkstra’s Algorithm :
Finds shortest paths from a source node to all other nodes in a graph. Works with graphs that have non-negative edge weights. Commonly used in maze routing and shortest path problems.
Input Parameters :
1. Graph (G(V, E)) with non-negative edge weights (W).
2. Source node (s) as the starting point.
3. Target node (f) as the destination.
Node Groups :
1. Group 1/Unvisited Nodes – Nodes have not been visited.
2. Group 2/Considered Nodes – Nodes visited but shortest
path cost not finalized.
3. Group 3/Known Nodes– Nodes for which the shortest
path cost is determined.
Optimize objectives :
1. Geometric distance , 2. Electrical properties , 3. Routing congestion , 4. Wire densities
Algorithm Initialization :
1. All nodes start in Group 1.
2. The cost of reaching each node is set to infinity (∞) except
for the source node, which has cost 0.
3. Parent of each node is initially unknown.
4. The source node (s) is moved to Group 3 as the first known node.
Algorithm Execution :
While the target node (f) is not reached -
1. Compute the cost of reaching neighboring nodes from the current node.
2. If a node is in Group 1, record its cost and update its parent.
3. If a node is already in Group 2, compare and update its cost if a better (lower-cost) path is found.
4. Select the lowest-cost node in Group 2 and move it to Group 3.
5. Repeat until the target node(f) is added to Group 3.
Path Reconstruction :
Once f is found, back trace from f to s using parent nodes to determine the shortest path.
Efficiency Considerations : Each iteration only considers neighbors of the most recently added node (curr_node), reducing redundant calculations. Nodes move sequentially into Group 3 based on the increasing order of their shortest-path cost. The algorithm stops once the target node (f) is added to Group 3, ensuring an optimal path.
Handling Node Costs : When nodes have traversal costs, each node is replaced by a d-clique (a complete sub-graph of d nodes). Clique edges have weights equal to the original node cost. The original d incident edges are connected to different clique nodes. This transformation ensures that path traversal accounts for node traversal costs efficiently.
Finding Shortest Path : A* Search :
Similar to Dijkstra’s algorithm but extends the cost function. Includes an estimated distance from the current node to the target. Guarantees the shortest path if a path exists. The estimated distance should never exceed the actual distance (admissibility criterion). Efficiency Compared to Dijkstra’s Algorithm Expands only the most promising nodes (best-first search). Reduces the solution space compared to Dijkstra’s algorithm. A tight lower bound estimate can significantly improve runtime. Can be derived from Dijkstra’s algorithm by adding distance-to-target estimates.
Node priority is determined by the sum of:
- Cost from the start node (like Dijkstra’s label).
- Estimated remaining distance to the target.
- Bidirectional A* Search is a variant. Expands nodes from both source and target until regions meet. Reduces the number of nodes considered slightly. However, tracking the order of visited nodes, along with the complexity of implementing an efficient solution, poses significant challenges. In practice, these difficulties can outweigh the potential benefits of bidirectional search.
Methods of Full Netlist Routing:
1. Integer Linear programming:
A linear program (LP) is a mathematical problem that includes a set of conditions (called constraints) and an optional goal/objective function to maximize or minimize. Both the constraints and the objective function must be written as linear equations or inequalities. If all variables in a linear program only take whole number values, it is called an integer linear program (ILP). When these variables are restricted to only 0 or 1, it is referred to as a 0-1 ILP. There are various software tools, like GLPK, CPLEX, and MOSEK, that can solve (integer) linear programs.
The ILP takes 3 inputs :
(1) an W × H routing grid G,
(2) routing edge capacities, and
(3) the netlist Netlist.
The ILP uses 2 sets of variables. The first set includes k Boolean variables, each representing an indicator for one of k specific paths or routes for a net in the Netlist.
- The second set contains k real variables, each of which represents a net weight for a specific route for a net in Netlist.
Rip-Up & ReRoute(RRR):
Modern ILP solvers can handle hundreds of thousands of routes efficiently, but commercial EDA tools require faster and more scalable methods. The rip-up and reroute (RRR) framework addresses this by focusing on problematic nets. When a net faces obstacles or interference, RRR temporarily allows violations, routes all nets, then iteratively removes and reroutes some to reduce conflicts. Alternatively, push-and-shove strategies move existing nets to new positions to resolve congestion or make unroutable nets feasible. A greedy routing approach avoids violations but often causes large detours. In contrast, RRR permits temporary over-capacity routing to optimize overall paths. Allowing violations and rerouting enables more efficient routing with fewer detours than strictly violation-free methods. In the RRR framework, not all violating nets are ripped up, reducing runtime significantly with only a small increase in wire length.
Global Router:
A global router first divides multi-pin nets into two-pin subnets and generates an initial routing solution on a 2D grid. If there are no violations, it assigns layers by mapping the 2D routes onto a 3D grid. If violations occur, problematic nets are ripped up and rerouted iteratively until the design is violation-free or a stopping condition, such as a CPU limit, is reached. Some routers include an optional cleanup pass to minimize wire length after rip-up. Alternatively, some global routers route directly on the 3D grid, which can improve wire length but is slower and may fail to complete routing. Nets are routed using maze and pattern routing, with negotiated congestion routing managing costs. A global router determines paths for two-pin nets while adhering to capacity constraints, prioritizing minimal wire length. It employs maze routing methods like Dijkstra's or A* search to ensure the shortest path between points. However, these methods can be excessively slow, especially when topologies involve edges requiring minimal vias.
Modern routers implement RRR (Rip-up and Reroute) using negotiated congestion routing. In this approach, each edge is assigned a cost or value that represents the demand for that edge. Higher costs discourage nets from utilizing heavily used edges, indirectly encouraging them to explore alternative, less congested paths.
Optimization for Different Design Types :
1. Full Custom Design:
A full custom design features a layout dominated by macro cells with irregular, non-uniform routing regions. Key initial tasks include channel definition and channel ordering. Channel definition partitions the global routing area into routing channels and switchboxes. Channel ordering is determined using floorplan tree. If a part of floorplan cannot be represented using horizontal and vertical cuts atleast one switchbox is used along with channels. Once all of the regions, channels and switchboxes are determined the ents canm be routed. Steiner tree routing and Minimum Spanning tree routing are two methods used. Shortest path is determined by Dijkstra’s algorithm.
Standard Cell Design :
In standard cell design, when the number of metal layers is limited, feedthrough cells are used to route a net across multiple cell rows. If the cell rows and netlist are fixed, the number of unoccupied sites within the cell rows is also fixed, which restricts the number of possible feedthroughs. As a result, standard cell global routing aims to (1) ensure the design is routable and (2) identify a low-congestion solution that minimizes the total wirelength.
Gate Array Design :
In gate array design, the cell sizes and the routing region sizes—i.e., the routing capacities—are fixed. Since adding extra routing resources is not an option to ensure routability, key tasks involve assessing the placement’s routability and finding a feasible routing solution. Additional optimization objectives include minimizing the total routed wire length and reducing the length of the longest timing path.
Watch the video lecture here:
Courtesy: Image by www.pngegg.com
