ASIC Backend Design Flow in VLSI (Part-3) : Placement and Routing (PnR)

Two fundamental stages in the VLSI design flow that significantly impact performance, area efficiency, and power consumption are placement and routing. Placement involves determining the optimal location for each logic cell within the chip's layout, while routing involves establishing interconnections between these cells. These stages involve the physical realization of the logical design onto the silicon substrate, determining the locations of individual components and establishing the interconnections between them.

WHAT IS THE SIGNIFICANCE OF PnR ?

Efficient placement and routing are critical for realizing high-performance integrated circuits. A well-executed placement ensures that signals traverse shorter distances, minimizing delays and power consumption. Moreover, it facilitates the implementation of global routing, which interconnects distant blocks efficiently. Effective routing, on the other hand, ensures that signals reach their destinations while adhering to timing constraints and avoiding signal integrity issues such as crosstalk and electromagnetic interference.

CHALLENGES IN PnR

Placement and routing pose several challenges owing to the complex nature of modern VLSI designs. With the increasing density of transistors on a chip, the number of interconnects surges, exacerbating routing congestion. Moreover, meeting stringent timing constraints amidst this congestion becomes arduous. Additionally, balancing conflicting objectives such as area, power, and performance necessitates sophisticated algorithms capable of exploring vast design spaces.

PLACEMENT

Placement algorithms strive to minimize wirelength, thereby reducing signal propagation delays and power consumption. Traditional placement techniques include iterative algorithms like simulated annealing and genetic algorithms, which iteratively refine the placement by swapping cells or perturbing their positions. Modern approaches leverage analytical methods like analytical placement, which formulate placement as an optimization problem solved using mathematical programming techniques. Furthermore, hierarchical placement techniques divide the design into smaller blocks, simplifying the placement problem and enabling parallel processing. Primary features of placement are:

1. Netlist input: The placement process begins with a netlist, which is a logical representation of the circuit design. It consists of a list of components (logic gates, flip-flops, etc.) and their interconnections (nets).
2. Floorplanning: Floorplanning involves defining the overall chip area and partitioning it into functional blocks. This step establishes the initial boundaries for the placement of components and routing channels. Factors such as power grid locations, I/O locations, and core logic regions are considered during floorplanning to optimize the layout for power distribution and signal integrity.
3. Initial Placement: Initial placement assigns a rough position to each component within its designated block. The goal is to minimize wirelength and optimize for timing, power, and area constraints. Heuristic algorithms like simulated annealing, genetic algorithms, or analytical placement methods are commonly used for initial placement.
4. Legalization: Legalization ensures that the initial placement adheres to design rules and constraints specified by the foundry's design rules. These rules govern factors such as component spacing, alignment, and symmetry. Legalization algorithms adjust the positions of components to comply with these rules while minimizing disruption to the placement quality.
5. Optimization: After legalization, placement optimization techniques are applied to further refine the placement quality. Optimization objectives include minimizing wirelength, balancing congestion, and meeting timing constraints. Iterative algorithms or mathematical programming techniques may be employed to iteratively improve the placement quality until design closure is achieved.

ROUTING

Routing algorithms aim to establish interconnections between cells while adhering to design constraints. Primary features of routing are:

1. Global Routing: Global routing determines the high-level path of interconnections (nets) between blocks. It aims to establish a feasible routing topology that satisfies timing constraints while minimizing congestion and wirelength. Algorithms like maze routing, Lee's algorithm, or algorithms based on minimum spanning trees are commonly used for global routing. During global routing, routing resources such as tracks and vias are allocated, and preliminary wire segments are laid out.
2. Detail Routing: Detail routing focuses on routing individual interconnections within the routing channels defined during global routing. It involves selecting specific routing tracks, configuring vias, and resolving conflicts. Detail routing algorithms consider factors such as wire width, spacing, and via minimization to optimize routing density and signal integrity. Techniques like maze routing, A* algorithm, or variations of the routing tree algorithm are employed for detail routing.
3. Routing Optimization: After detail routing, optimization techniques are applied to refine the routing quality and meet design constraints. Optimization objectives include minimizing routing congestion, reducing wirelength, optimizing via count, and ensuring timing closure. Iterative refinement techniques or co-optimization approaches that integrate placement and routing feedback may be employed to achieve design closure.

INTEGRATION & VERIFICATION

Integration of placement and routing is essential for achieving design closure. Iterative refinement techniques iteratively alternate between placement and routing stages, gradually converging towards an optimal solution. Furthermore, co-optimization techniques consider placement and routing concurrently, leveraging global routing feedback to guide the placement process and vice versa. This integrated approach enhances design quality and convergence speed. Primary features are:

1. Integration: Once placement and routing are completed, the physical layout is integrated with other design components such as I/O pads, power grids, and clock distribution networks. Integration involves merging the physical layout with additional design elements while ensuring consistency and adherence to design constraints.
2. Design Rule Check (DRC): Design Rule Check verifies whether the layout adheres to the manufacturing rules and constraints specified by the foundry. DRC identifies violations such as spacing violations, overlap violations, and other geometric violations that could affect manufacturability.
3. Timing Analysis: Timing analysis evaluates the performance of the design by analyzing signal propagation delays and ensuring that timing constraints are met. Techniques such as static timing analysis (STA) or timing-driven placement and routing are used to verify timing closure and optimize for performance.
4. Signal Integrity Analysis: Signal integrity analysis assesses the quality of signal transmission and reception, identifying potential issues such as crosstalk, electromagnetic interference (EMI), and power integrity. Techniques like noise analysis, power distribution network (PDN) analysis, and signal integrity simulation are employed to mitigate signal integrity issues.
5. Design Verification: Once integration and analysis are completed, the physical design undergoes comprehensive verification to ensure functionality, reliability, and compliance with design specifications. Verification methodologies include functional simulation, formal verification, and physical verification (DRC, LVS - Layout vs. Schematic).