What is detailed Routing in VLSI Physical Design?

 

In this article, we have explored the concept of detailed routing in VLSI Physical Design, an essential step in the overall design flow that ensures efficient signal connectivity while optimizing chip area and performance. We begin by discussing the various routing techniques used in modern VLSI design, along with the significance of horizontal and vertical constraints in determining routing feasibility. The video further delves into zone representation and the Horizontal & Vertical Constraint Graph, which are crucial for structuring the routing process systematically. Additionally, we cover different routing methodologies, including channel routing techniques such as the Left Edge Algorithm and Dogleg Routing, as well as switchbox routing and Over-The-Cell (OTC) routing, explaining both the algorithm and methodology behind OTC routing. Finally, we address the modern challenges faced in detailed routing, highlighting the complexities and evolving strategies required to meet the demands of advanced semiconductor technologies.

Design Flow and Detailed Routing:

In VLSI , routing is a crucial step that connects the various components 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.

The layout region is represented during global routing using a coarse grid of global routing cells (gcells) or more general routing regions (channels, switchboxes). After global routing, each net undergoes detailed routing. Objective of detailed routing: Assign route segments of signal nets to specific routing tracks, vias, and metal layers while following global routes and design rules.

Key advantage:

(a) Detailed routing of one gcell can be performed independently as long as routes remain connected across neighboring gcells.

(b) This enables an efficient divide-and-conquer strategy and supports parallel algorithms, allowing detailed routing runtime to theoretically scale linearly with layout size.

(c) Traditional detailed routing occurs within routing regions such as channels and switch boxes. Modern designs use over-the-cell (OTC) routing , allowing routing over standard cells.

Due to technology scaling, modern detailed routers must consider manufacturing rules and the impact of manufacturing faults.

Different Routing Techniques :

i. Channel Routing : Type of detailed routing where connections between terminal pins are routed within a channel with no obstacles. Pins are located on opposite sides of the channel .Conventionally, the channel is oriented horizontally, with pins on the top and bottom. In row-based layouts, routing channels typically have uniform width. In gate-array and standard-cell circuits with more than three metal layers, channel height (number of routing tracks) is also uniform.

ii .Switchbox Routing : Used when pin locations are on all four sides of a fixed-size routing region. More complex than channel routing due to additional constraints. OTC (Over-The-Cell) Routing : Utilizes additional metal tracks (e.g., Metal3, Metal4) that are not obstructed by cells. Allows routes to cross over cells and channels. Only metal layers and tracks not occupied by cells can be used. When cells use only polysilicon and Metal1, routing can be performed on Metal2, Metal3, etc., and unused Metal1 resources.

iii. Classical Channel Routing : Routing area is a rectangular grid with pin locations on top and bottom boundaries. Pins are placed on vertical grid lines or columns. Channel height depends on the number of tracks needed to route all nets. In two-layer routing, one layer is reserved for horizontal tracks while other layer is reserved for vertical tracks. Preferred routing direction is determined by floorplan and standard-cell row orientation. 

Horizontal & Vertical Constraint:

1. Horizontal Constraint : 

A horizontal constraint between two nets occurs when their horizontal segments overlap while being placed on the same track. In the example shown includes one horizontal and one vertical routing layer, nets B and C are horizontally constrained. If the horizontal segments of two nets do not overlap, they can be assigned to the same track without constraints for instance, nets A and B.

2. Vertical Constraint :

 

A vertical constraint between two nets  occurs when they have pins in the same column. This means that the vertical segment extending from the top must stop within a short distance to avoid overlapping with the vertical segment coming from the bottom in the same column. If each net is assigned to a single horizontal track, the horizontal segment of a net from the top must be placed above that of a net from the bottom in the same column. In Fig. , this constraint ensures that net A’s horizontal segment is placed above net B’s. To resolve these constraints, at least three columns are needed to separate the two nets. While a vertical constraint implies a horizontal constraint, the reverse is not always true. However, both constraints must be considered when assigning segments within a channel.

Zone Representation :

In a channel, each horizontal wire segment must extend at least from the leftmost to the rightmost pin of its net. Let S(col) represent the set of nets passing through column col. This includes nets that either (1) have a pin in col or (2) connect to pins on both sides of col. Since horizontal segments cannot overlap, each net in S(col) must be assigned a separate track within that column. However, not all columns are necessary to define the entire channel. If a column i has a net set S(i) that is a subset of another column j (i.e., S(i) ⊆ S(j)), then S(i) can be ignored as it imposes fewer constraints on routing. In the above fig , every S(col) is a subset of at least one of S(c), S(f), S(g), or S(i). These columns (c,f, g, and i) form the minimal set needed, as they collectively include all nets. The relative positions of nets in a channel routing instance, defined by horizontal and vertical constraints, can be represented using horizontal and vertical constraint graphs.  These graphs help to: (1) estimate the minimum number of tracks needed , (2) identify potential routing conflicts.

Horizontal & Vertical Constraint Graph:

1. Horizontal Constraint Graph : 

 

A graphical representation can be used to depict the nets within a channel. This can be done using a Horizontal Constraint Graph (HCG), where: nodes (V) represent the nets in the netlist. Edges (E) exist between two nodes if their corresponding nets belong to the same set S(col), meaning they are horizontally constrained.

Fig. (iv) shows the HCG for the channel routing example in Fig.(iii). The minimum number of tracks required for channel routing can be determined using either the HCG or the zone representation. This minimum is given by the largest S(col) set. 

2. Vertical Constraint Graph : 

Vertical Constraint Graph (VCG) represents vertical constraints in channel routing,  nodes (V) represent nets , directed edges (E) exist between nodes if one net must be placed above another. In Fig. (v), some edges (like B → C) are omitted if they can be inferred from other 

                                      edges (e.g., B → E ).

A cycle in the VCG indicates a conflict where two nets overlap in a column, meaning their horizontal segments would need to be both above and below each other—an impossible situation. This is resolved by splitting the net and adding an extra track . fig(vi).

Channel Routing Algorithms :

Channel routing aims to minimize the number of tracks needed for routing. In gate-array designs, where channel height is usually fixed, algorithms are developed to ensure complete (100%) routing.

1. Left-Edge Algorithm: An early channel routing algorithm was developed by Hashimoto and Stevens. Their simple and widely used left-edge heuristic, based on the VCG and zone representation, efficiently maximizes track usage. The VCG determines the order in which nets are assigned to tracks,

while the zone representation decides which nets can share the same track. Each net uses only one horizontal segment (trunk).

 The left-edge algorithm works as follows:

1. Start with the topmost track.

2. For all unassigned nets, generate the VCG and zone representation.

3. Process nets from left to right, assigning each to the current track if:

- It has no predecessors in the VCG.

- It does not conflict with previously assigned nets.

4. Once a net is assigned, remove it from the unassigned list.

5. Move to the next track and repeat the process until all nets are assigned.

This algorithm finds a solution with the minimum number of tracks if the VCG has no cycles. Yoshimura later improved track selection by considering net length in the VCG, and Yoshimura and Kuh further optimized track usage by splitting nets before constructing the VCG.

Dogleg Routing :

To handle cycles in the VCG, an L-shaped "dogleg" can be used. Doglegs help resolve conflicts in VCGs and reduce the total number of tracks. Dogleg algorithm, developed in the 1970s, eliminates cycles and minimizes routing tracks by extending the left-edge algorithm.

 It splits p-pin nets (p > 2) into p – 1 horizontal segments, but only in columns where the net has a pin, assuming no extra vertical tracks are available. After splitting, the algorithm follows the left-edge approach, with subnets represented in the VCG and zone representation.

Switchbox Routing :

Switchbox routing algorithms are often derived from channel routing techniques. Luk extended a greedy channel router by Rivest and Fiduccia to develop a switchbox routing algorithm with key improvements:

1. Pin assignments are made on all four sides.

2. A horizontal track is assigned automatically to a pin on the left.

3. Jogs are used for top and bottom pins and for horizontal tracks connected to the rightmost pins.

While this algorithm performs similarly to the greedy channel router, it does not guarantee full routability due to fixed switchbox dimensions.

Ousterhout et al. introduced a channel and switchbox router that considers obstacles like pre-routed nets . Cohoon and Heck developed BEAVER , which optimizes routing area and via usage. BEAVER offers flexibility in layer routing and

employs four strategies:

1. Corner-routing – uses horizontal and vertical segments forming bends.

2. Line-sweep routing – handles simple connections and straight segments.

3. Thread-routing – supports various connection types.

4. Layer assignment – optimizes layer usage.

BEAVER surpasses previous academic routers in routing area and via efficiency.

Another notable switchbox router, PACKER, developed by Gerez and Herrmann in

1989 follows three main steps:

1. Routing each net independently without considering capacity constraints.

2. Resolving conflicts using connectivity-preserving local transformations (CPLT).

3. Modifying net segments locally to reduce congestion.

Over-the-Cell (OTC) Routing Algorithms :

Most routing algorithms focus on two-layer routing. However, modern standard-cell designs use multiple layers, requiring

extensions to these algorithms. One common approach places cells back-to- back or without routing channels. Internal

routing primarily uses Poly and Metal1, while higher metal layers (e.g., Metal2 and Metal3) remain unobstructed and are used for over-the- cell (OTC) routing. These layers are

represented by a coarse routing grid of gcells. Nets are first globally routed as Steiner trees and then detail-routed.

Another approach introduces channels between cells, but routing within them is limited to internal layers like Poly and Metal1. Higher metal layers (Metal2, Metal3) handle most routing, making traditional routing channels unnecessary. Instead, routing occurs across the entire chip  rather than in defined channels or switchboxes . 

OTC routing often coexists with channel routing. For example, IP blocks may block routing on lower metal layers, forming channels or switchboxes between them. FPGA fabrics use fewer metal layers to reduce costs, clustering interconnects into channels. FPGAs also include pre-designed components like multipliers and DSP blocks that rely on OTC routing. Modern FPGAs feature express-wires on higher metal layers that cross logic elements.

Modern Challenges in Detailed Routing :

1. Technology Scaling & Wire Widths:

Demand for low-cost, high-performance, and low-power ICs has driven technologyscaling since the 1960s. Different metal layers use wires of varying widths, with wider wires on higher layers improving signal speed but reducing routing tracks. Thicker wires are commonly used for clock, power supply, and global interconnects.

2. Routing Complexity & Layer Configurations:

Modern ICs use different metal layer configurations to optimize performance. Vias connecting wires of different widths block routing resources on layers with smaller pitches.

.

3. Manufacturing Yield & Detailed Routing: 

Yield concerns require via doubling and non-tree routing for redundancy. At advanced nodes, design rules become restrictive, specifying minimum spacing between wires and vias based on width and corner proximity. Forbidden pitch rules prohibit certain wire spacings while allowing others.

4. Via Defects & Mitigation: 

Vias connect wires between metal layers but may misalign or degrade due to electromigration. Partial via failure increases resistance, leading to timing violations; complete failure disconnects nets. Double vias improve reliability but require additional area and adherence to design rules. Congested areas may limit via doubling options.

5. Interconnect Defects & Redundancy Measures:

Shorts & Opens: Shorts (unintended wire connections) are mitigated by increased spacing, though excessive spacing

raises wire length. Opens (broken connections) are addressed via non-tree routing and redundant wiring, which improves

reliability but increases short risks.

6.  Antenna-Induced Defects: 

Excessive charge buildup during plasma etching can damage transistor gates. Mitigation involves controlling metal-to-gate area ratios and rerouting via new or relocated vias.

7. Manufacturability-Aware Routing:

Yield-optimized detailed routing is proposed, but its benefits are hard to quantify pre- manufacturing, limiting industry adoption.

Watch the video lecture here:

Courtesy : Image by www.pngegg.com