What is Global Routing in VLSI Physical Design?

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

Read More

What is Placement in VLSI Physical design?

Design Flow & Placement:

In the VLSI design flow, placement is a crucial step in the physical design. It comes after Partitioning and Floor planning. Logic Synthesis converts a high-level RTL design into a netlist of gates and cells. Partitioning divide the larger design into smaller modules. Floor planning allocates general areas for major components and defines regions for standard cells, macros, pin assignment allocates input/output (I/O) pins. Placement is the process of determining the optimal locations for standard cells, macros, and other modules within a chip’s layout. It aims to achieve the best balance between performance, power, and area (PPA) while minimizing wire length, congestion, and delays. 

Placement Phases: There are 2 placement phases in PD. 

(1) Global Placement : Provides a rough layout of the cells and modules to minimize wire length and congestion. Focuses on overall optimization but allows overlaps between cells.

(2) Detailed Placement : Adjusts the positions to remove overlaps and ensure cells are aligned with legal sites or predefined rows on the chip. Minimizes wire length deviations introduced during legalization. 

After placement, the routing phase connects all components with metal wires, finalizing the design's physical layout.

Objective & Challenges of Placement:

Placement is a critical step that transforms a logical design into a physically realizable layout. It ensures that the layout is timing-efficient, power-optimized, and routable, forming a bridge between logic synthesis and routing in the IC design flow.

# Placement Constraints and Objectives:

(1) Minimize Wire length : Shorter wires reduce signal delays and improve performance.

(2) Timing Closure : Placement must ensure paths meet the required timing.

(3) Power Optimization : Efficient placement helps reduce dynamic and leakage power.

 

(4) Congestion Control : Placement must prevent routing congestion to ensure the design is routable.

# Challenges in Placement :

(1) Handling Large Netlists: Efficiently placing millions of cells

(2) Preventing Overlaps: Global placement often creates dense clusters that need to be legalized.

(3) Timing vs. Wire length Trade-offs : Minimizing wire length can sometimes degrade timing performance, and vice versa.

(4) Macro Handling: Large blocks (macros) need special consideration to avoid placement gaps and routing blockages.

Different Types of Placement :

Optimization in Placement:

In placement, the optimization objectives focus on achieving high performance, low power consumption, and manufacturability.

1. Wire length Minimization :

Objective: Reduce the total wire length to lower signal propagation delays, power consumption, routing congestion.

Impact: Reducing wire length improves timing (faster circuits) and reduces the likelihood of routing congestion.

2. Overlap Minimization :

Objective: Ensure that no two cells overlap after placement, especially during the detailed placement phase.

Impact: Non-overlapping placement improves routability and allows legalization (alignment with power rails).

3. Timing Optimization :

Objective: Minimize signal delays by reducing interconnect delays that affect the overall clock cycle.

Impact : Enhances the performance of the circuit by ensuring faster data propagation through critical paths.

4. Row Length Equality :

Objective: Ensure equal row lengths during standard-cell placement to avoid inefficient use of layout space.

Impact: Uniform rows prevent area wastage and ensure even wire distribution, reducing routing congestion.

5. Congestion Minimization :

Objective: Avoid high-density areas where wiring overlaps or routing resources become constrained.

Approach:

(i) Spreading cells: Cells are distributed more evenly by scaling their positions and moving them out of dense regions.

(ii) Congestion-aware placement: Similar to density estimation, routing congestion is estimated on a grid to guide placement.

Impact: Reducing congestion ensures routability and avoids post-routing failures.

6. Power Optimization:

Objective: Minimize the power consumed by interconnects and switching activities.

Approach:

(i) Reduce wire length to lower dynamic power (caused by signal switching across long nets).

(ii) Place high-activity cells closer to minimize interconnect delay and energy consumption.

Impact: Leads to low-power designs, which are essential for battery-powered devices.

7. Legalization:

Objective: Align cells to discrete rows and ensure legal locations after global placement.

Approach:

(i) Snap cell coordinates to grid points that correspond to power rails.

(ii)Optimize wire length and overlap during incremental legalization.

Impact: Produces valid placements that meet manufacturing requirements w/o overlaps/misplaced cells.

8. Temperature-Based Optimization (Annealing):

Objective: Use simulated annealing to explore various placements and escape local minima in the optimization process.

Impact: Aims for a global optimum solution by balancing interconnect minimization and overlap reduction as the temperature decreases.

These objectives collectively ensure that the chip layout achieves high performance, efficient power usage, low congestion, and manufacturability. Different algorithms may emphasize some objectives over others based on design constraints and priorities.

Modern Placement:

Modern placement in EDA refers to advanced methods which combines mathematical optimization, multi-objective considerations, and sophisticated algorithms to address the demands of current chip designs, balancing efficiency, scalability, and performance while considering design constraints, including wire length, timing, power, and congestion. # Key Aspects of Modern Placement:

1. Multi-Objective Optimization: Modern placement aims to optimize multiple goals at once, like shortening wire length, saving power, managing heat, improving timing, and easing routing. This approach is key for high-performance, power-efficient chip designs.

2. Analytic and Force-Directed Methods: Analytic Methods: These use mathematical models like quadratic and nonlinear optimization to approximate interconnect lengths and solve placement as an optimization problem. Quadratic methods are popular due to their computational efficiency, while nonlinear methods provide better accuracy for designs with various component sizes. Force-Directed Methods: Here, cells are treated as objects subject to attractive and repulsive forces. Attraction represents connectivity, by closely connected cells to move closer, and repulsion prevents overlapping by spreading cells apart.

3. Hierarchy and Clustering Techniques: To handle large-scale designs, modern placement algorithms use clustering, which groups highly interconnected cells together in early stages. This reduces the complexity of initial placement and allows for more efficient optimization. After clustering, cells are progressively "un-clustered" and refined in stages, allowing for scalable placement even with millions of components.

4. Legalization and Detailed Placement: Legalization ensures that cells are moved to exact, non-overlapping legal positions, typically aligning with a grid, while minimizing disturbance to the global placement. Detailed Placement then fine-tunes cell positions to reduce minor overlaps and improve wire length and timing by making small local adjustments.

Min-cut Placement :

Min-cut placement is a method in chip design where a circuit's layout is divided or partitioned repeatedly into smaller regions to minimize the number of connections or cuts between these regions. The aim is to balance the number of components in each region while reducing the connections that cross boundaries, which helps minimize wire length and improves timing. Min-cut placement effectively balances components and reduces interconnections, laying a foundation for efficient routing and timing optimization in later stages.

# How min-cut placement generally works:

1. Partitioning: The design area is repeatedly split into smaller sections, each with about the same number of cells. During each split, an algorithm picks a dividing line and tries to keep closely connected parts on the same side to reduce the number of connections crossing the line.

2. Objective: The main objective is to minimize the number of "cuts" or interconnections between partitions, as these inter-partition connections can lead to longer wires and increased delay.

3. Balancing Cells: Min-cut placement also strives to balance the number of components in each partition. This balancing is important because it prevents one area from becoming congested while another has unused space.

4. Hierarchical Refinement: Min-cut placement is a hierarchical approach. Each sub-region is further divided until each partition is small enough that detailed placement techniques can be applied to finalize the exact locations of cells within each region.

5. Advantages and Applications: Min-cut placement is well-suited for large designs and can handle hierarchical structures efficiently. Tools like Capo, which is a popular min-cut placer, are used to achieve routable placements, especially in designs with high density and many fixed obstacles.

# There are 2 approaches to divide the layout :

1. Alternating Cutline Directions :

Alternating cutline Directions is a technique in partition-based placement where the direction of cutlines alternates between horizontal and vertical during recursive partitioning. The design area is split into regions, ensuring a balanced distribution of cells in both axes. By alternating the cutline direction, the method avoids skewness, maintains compact layouts, and reduces wire length. Closely connected components are grouped to minimize routing congestion. This structured placement simplifies later stages, like legalization and optimization. It is especially effective for large, complex circuits with dense interconnections.

2. Repeating Cutline Directions :

Repeating Cutline Directions is a technique in partition-based placement where the same cutline direction (horizontal or vertical) is used repeatedly during multiple levels of recursive partitioning. This approach divides the design area into increasingly smaller regions along a single axis, creating elongated partitions in one direction. It may simplify some placement strategies but risks uneven distribution, potentially increasing wire length and routing congestion. Repeating cutline directions can be suitable for designs with specific constraints, like high connectivity along one axis. However, it is less commonly used compared to alternating cutline directions due to its limitations in achieving balanced layouts.

Analytic Placement :

Analytic placement is a technique in chip design that uses mathematical optimization methods to determine the locations of circuit components on a chip. The goal of analytic placement is to minimize an objective function, usually related to the circuit’s performance, such as total wire length/delay, by treating the placement problem as a mathematical optimization task.

# Key Aspects of Analytic Placement:

1. Optimization-Based Approach: Analytic placement relies on mathematical optimization methods like numerical analysis or linear programming. Unlike heuristic methods, it formulates placement as an objective function and seeks to find the optimal configuration of cells to minimize this function. The approach involves treating placable objects (like cells) as dimensionless points initially, which simplifies the mathematical calculations.

2. Objective Functions: The most common objective function in analytic placement is wire length minimization, often using a quadratic function (squared Euclidean distance) to approximate the total wire length. Quadratic wire length models make it easier to apply mathematical techniques, but other functions, such as nonlinear ones, may be used for greater accuracy. In addition to wire length, other objectives like minimizing circuit delay, reducing congestion, or achieving better timing are sometimes considered.

3.Two Main Stages: Global Placement: This is the first stage, where cells are positioned to minimize the objective function across the entire layout. At this stage, overlaps are allowed, and cells may form clusters. Detailed Placement: In the second stage, cells are moved slightly to remove overlaps and achieve legal positions while keeping the objective function optimized.

4. Convex Optimization and Convexity: In quadratic placement, the placement problem often becomes a convex quadratic optimization problem. Convexity ensures that any local minimum solution is also a global minimum, making it possible to solve the problem efficiently by setting the partial derivatives of the objective function to zero.

5. Additional Techniques for Spreading: After the initial analytic placement, cells may be too close to each other, creating overlaps. Dedicated techniques like cell spreading are applied to ensure non-overlapping placement. This involves redistributing cells to avoid congestion while preserving the optimization of the objective function.

6. Types of Analytic Placement:

Quadratic Placement: Uses a quadratic cost function, which emphasizes minimizing longer connections. Quadratic placement is efficient and scalable.

Nonlinear Placement: Uses more complex, nonlinear functions to represent interconnects, providing better accuracy, especially for components with diverse sizes, but it can be computationally slower than quadratic methods.

# Advantages and Limitations:

Advantages: Analytic placement is systematic, scalable, and provides highly optimized results for wire length and other performance metrics. It is also suitable for very large designs due to its mathematical rigor.

Limitations: Analytic methods may require complex handling for real-world design constraints, such as routing congestion or timing requirements. Some methods, particularly nonlinear optimization, can be slower and require careful tuning for stability.

Analytic placement is widely used in EDA tools because it provides an efficient, scalable way to produce high-quality placements that lay the foundation for effective routing and timing optimization.

# Why Analytic Placement Matters ?

As chip designs grow increasingly complex, the need for precise and efficient placement methods has never been greater. Analytic placement provides the mathematical rigor and computational power needed to meet modern design requirements, ensuring faster, smaller, and more power-efficient chips. With its blend of theoretical elegance and practical impact, analytic placement remains a cornerstone of VLSI design, driving innovation in one of the most challenging engineering domains.

Simulated Annealing :

Simulated annealing is a heuristic optimization technique used in placement algorithms, particularly in the global placement phase of VLSI design. It mimics the physical process of annealing in metallurgy, where materials are slowly cooled to minimize internal energy and achieve a stable configuration. The following are key aspects of simulated annealing placement:

# Basic Principles :

1. Cost Function:

- Placement quality is evaluated using a cost function, which combines factors.

- Wirelength: Often computed using the half-perimeter wirelength (HPWL) metric.

- Cell Overlap: Quantifies overlaps between cells, penalizing large overlaps more heavily.

- Row Inequality: Penalizes deviations in row lengths, which could cause inefficiencies

2. Cooling Schedule:

- The process starts at a high temperature, allowing more random placement changes.

- As the temperature decreases, the algorithm becomes less tolerant of changes that increase cost.

- The temperature is reduced gradually using a cooling factor, alpha, which may vary during the process:

(a) Initial Phase: High cooling rate e.g., alpha = 0.8 to explore configurations broadly.

(b) Middle Phase: Slower cooling e.g., alpha = 0.95 for fine-tuning.

(c) Final Phase: Rapid cooling alpha = 0.8 for convergence.

# Algorithm Steps:

1. Initialization: Begin with a high temperature and a random initial placement of cells.

2. Placement Perturbation: Modify the placement by moving or swapping cells to generate new configurations.

3. Cost Evaluation: Calculate the cost of the new placement. If the new cost is lower, accept the change. If the cost is higher, accept the change with a probability based on the current temperature and cost difference.

4. Iterative Cooling: Reduce the temperature and repeat the perturbation and evaluation steps until the system "freezes" (temperature reaches a minimum threshold).

5. Equilibrium: At each temperature level, the algorithm runs enough iterations to achieve equilibrium, ensuring stability before cooling further.

# Applications : Effective for standard-cell placement, in designs with constraints like limited feed through cells/uneven layouts.

# Advantages:

1. Flexibility in handling complex cost functions.

2. Ability to escape local minima by accepting worse solutions at higher temperatures.

# Challenges:

1. Computationally intensive due to the large number of iterations.

2. Parameter tuning (e.g., cooling schedule, acceptance ratio) requires expertise.

# Example Tool : TimberWolf

1. A popular placement tool using simulated annealing.

2. Incorporates detailed cost functions and strategies for cell spreading, overlap minimization, and optimization of wiring directions.

3. This method is a robust approach for achieving high-quality placements in the design of integrated circuits.

Global Placement :

In Global placement components like cells and circuit modules are assigned approximate locations across the layout area. The primary goal at this stage is to minimize a cost function, related to wire length or timing constraints, without enforcing exact legal positions or preventing overlaps.

1. Optimization without Exact Positions: Components are placed to minimize interconnect length and congestion, but positions are not finalized.

2. Independent x and y optimization: Placement simplifies the process by optimizing cell locations separately along x, y axes.

3. Use of Mathematical Models: Quadratic or nonlinear models are used to achieve optimal placement.

4. Preliminary Layout: Provides a rough layout, leaving exact, overlap-free positions for detailed placement.

5. Foundation for Legalization: Serves as a starting point for legalization and detailed placement to finalize a feasible and efficient layout.

6. Global placement is crucial for creating an efficient starting point for further optimizations that lead to a functional and high-performance chip layout.

Legalization :

Legalization is a process that adjusts the positions of circuit components/cells on a chip layout to ensure they meet specific physical design constraints.

After the initial/ global placement, components may not align to designated legal positions, such as rows or grid points, and may even overlap. Legalization corrects these issues by moving cells to valid positions while minimizing disruption to the optimized layout.

# Key Aspects of Legalization:

1. Aligning to Legal Positions: Cells are moved to specific legal sites, often aligning with power rails or rows. This ensures that the design complies with the manufacturing requirements, which mandate cells to be placed at predefined locations to ensure proper connections and spacing.ns to ensure proper connections and spacing.

2. Removing Overlaps: During global placement, cells may be placed too close to each other, creating overlaps. Legalization removes these overlaps by shifting cells slightly, while trying to maintain the overall structure and objective of the initial placement.

3. Minimizing Disturbance: Legalization aims to make only minimal adjustments to the positions of cells to preserve the optimized parameters like wire length or timing achieved during global placement. Excessive movement can increase wire length, affect timing, and create new congestion, so algorithms are designed to balance legality with minimal disruption.

4. Handling Physical Constraints:

Legalization accounts for physical design constraints, such as spacing rules, row alignment, and fixed cell locations. It also adapts to different sizes of components, including standard cells and larger macro blocks.

5. Legalization Algorithms:

Common algorithms for legalization include:

(i) Greedy Algorithms: Quickly place each cell in the nearest legal position, but may need refinement for optimal results.

(ii) Sliding Window or Branch-and-Bound: Works by reordering and slightly shifting cells within a defined window to achieve legal placement.

(iii) Dynamic Programming and Linear Programming: These techniques offer more systematic approaches to legalizing placements, especially for complex layouts with mixed cell sizes.

6. Integration with Detailed Placement:

Legalization is often followed by detailed placement, a fine-tuning stage where small adjustments further optimize the layout to improve performance metrics, such as reducing wire length or improving timing.

# Importance of Legalization:

Legalization is critical because it ensures the layout complies with all physical design rules and manufacturing constraints while retaining as much of the optimization from global placement as possible. This step is necessary before routing, as a legalized layout provides a reliable foundation for connecting the components without further conflicts or overlaps.

Detailed Placement :

Detailed placement follows global placement and legalization. During detailed placement, the precise positions of circuit cells are fine-tuned to improve design metrics like wire length, timing, power, and congestion. This stage aims to enhance the quality of the initial placement by making minor adjustments to cell positions without violating legal constraints by avoiding overlaps and maintaining alignment to rows.

# Key Aspects of Detailed Placement: 1. Fine-Tuning Cell Positions: Detailed placement fine-tunes the global placement layout by making minor, localized adjustments to enhance design quality while staying close to the original configuration. 2. Optimizing Wire length and Timing: The main goal of detailed placement is to minimize wire length, reducing delays and improving timing, especially along critical paths. 3. Congestion and Density Management : Congestion arises from densely packed cells, causing routing issues. Detailed placement algorithms spread cells to ease routing and prevent hotspots. 4. Improvement Techniques: Cell Swapping: Exchanging the positions of neighboring cells to reduce wire length or improve timing. Cell Sliding and Shifting: Adjusting cells slightly within rows or gaps to optimize spacing and align with power rails or tracks. Group Movement: Moving groups of cells within a sliding window to improve alignment and reduce wire length.

5. Window-Based Optimization: Detailed placement is often performed within small, localized windows or regions to reduce computational complexity and allow more focused optimization. The algorithms may reorder cells within these windows to minimize disruption to the overall placement.

6. Handling Unused Space: If there is unused space between cells in a row, detailed placement may shift cells slightly to either side or distribute them evenly, ensuring that no gaps lead to wasted area.

7. Ensuring Legalized Placement: Detailed placement adheres to legal positions determined during legalization, maintaining cell alignment and spacing to prevent design rule violations.

# Importance of Detailed Placement:

Detailed placement is crucial because it provides the final adjustments needed to optimize performance metrics before the routing stage. By fine-tuning the positions of cells, detailed placement improves wire length, timing, and congestion, resulting in a more efficient and high-performing chip layout.

Watch the video here:

Courtesy : Image by www.pngegg.com

Read More