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.
.png)
