AI Generated DPL PR v1

[AmurG]

This PR is one version of a DPL improver which only kicks in meaningfully under high core utilization values.

For validation, it is recommended to tune the hyperparameters (detailed here) on any circuit of choice that struggles with high core utilization at or near the highest core utilization value it completes the flow at.

The expected outcome will be a small but meaningful DRWL reduction of 2-3% in the above scenario. Outliers of up to 8% were observed.

Note : For the purpose of CI, the default PR leaves the alternate flow as "on". It should be merged as an alternate setting which is default "off". This is done for testing CI-level regressions.

We are also aware that the hyperparameters should all, in general, solely reside in TCL and not be hardcoded. Please also use a reasonable variation (2-4 choices each) of hyperparameters.

See also : https://github.com/The-OpenROAD-Project/OpenROAD/pull/8874

--AI Generated content follows--

Feature: Two-Pass Congestion-Aware Global Swap (DPL)

Motivation

In high-density designs (utilization > 85%), standard detailed placement optimizations often degrade local routability while pursuing global wirelength reductions. The legacy GlobalSwap algorithm optimized strictly for HPWL (Half-Perimeter Wirelength), frequently moving cells into already congested regions to minimize net length. This "clumping" behavior creates local density hotspots that standard routers cannot resolve, leading to DRC violations and timing degradation due to detour routing.

This PR introduces a Guarded Two-Pass Global Swap strategy. Instead of blind HPWL optimization, it employs a "Profile-Then-Optimize" approach: it first identifies the theoretical minimum wirelength (Pass 1), then re-optimizes the design (Pass 2) using a congestion-aware cost function constrained by a wirelength budget derived from the first pass. This ensures that congestion relief does not come at the cost of uncontrolled wirelength regression.

Technical Implementation

1. Utilization Map Infrastructure

A new UtilizationMap mechanism has been added to the Grid class to quantify local congestion costs.

• Binning: Reuses the existing detailed placement pixel grid.
• Cost Metric: For every pixel $i$, the utilization cost $C_i$ is calculated as a weighted sum of area density and pin density: $$C_i = W_{area} \cdot \frac{Area_i}{MaxArea} + W_{pin} \cdot \frac{Pins_i}{MaxPins}$$ Where $Area_i$ and $Pins_i$ are the accumulated cell area and pin counts overlapping pixel $i$.
• Normalization: The final map is normalized to $[0, 1]$ to provide a consistent cost basis for the optimizer.

2. Two-Pass Optimization Algorithm

The DetailedGlobalSwap solver has been refactored into a state-preserving two-pass workflow:

Pass 1: HPWL Profiling

• Executes a standard global swap with infinite budget.
• Purpose: To find the Target HPWL ($L_{opt}$), representing the best possible wirelength achievable without congestion constraints.
• Rollback: Upon completion, the system utilizes the Journal to atomically undo all moves, restoring the exact initial placement state while retaining the $L_{opt}$ metric.

Pass 2: Guarded Congestion Optimization

• Re-runs the optimization from the initial state.
• Budget Constraint: Defines a maximum allowable wirelength $L_{budget} = L_{opt} \times M_{stage}$, where $M_{stage}$ is a tightening multiplier schedule (e.g., 1.50 $\to$ 1.04).
• Acceptance Criteria: A move is accepted if and only if:
  1. The resulting HPWL $\le L_{budget}$ (Hard Constraint).
  2. The combined profit $P = \Delta HPWL + W_{cong} \cdot \Delta Congestion > 0$ (Soft Objective).
• Dynamics: This allows the solver to accept moves that degrade HPWL (negative $\Delta HPWL$) if they provide significant relief to local congestion ($\Delta Congestion$), provided the global wirelength stays within the calculated budget.

Usage & Configuration

This feature is enabled by default within the improve_placement TCL command.

Enabling / Disabling

There is currently no explicit disable flag exposed to TCL, as the two-pass logic is now the standard behavior for GlobalSwap. To revert to legacy behavior, one would need to modify the C++ source to bypass the profiling pass, though this is not recommended for high-density designs.

Hyperparameter Configuration

User-Configurable (TCL)

These flags control the core search heuristics of the swap engine:

• -x <float> (Tradeoff): Controls the ratio of "Random Exploration" vs. "Smart" (Wirelength-Optimal) moves.
  • Default: 0.2 (20% random / 80% smart).
  • Tuning: Increase to 0.4 or 0.5 for difficult designs to escape local minima.
• -t <float> (Tolerance): Convergence threshold for the HPWL optimization loop.
  • Default: 0.01 (1%).
• -p <int> (Passes): Number of inner-loop optimization passes per stage.

Example:

# High-effort mode for difficult designs
improve_placement -x 0.4 -t 0.005

Internal Compilation Parameters (detailed_global.cxx)

Advanced tuning requires modifying hardcoded constants:

• budget_multipliers: {1.50, 1.25, 1.10, 1.04}. Controls the annealing-like schedule of the wirelength budget.
• area_weight / pin_weight: 0.4 / 0.6. Weights for the utilization map cost function.
• user_knob: 35.0. Scaling factor that determines how much wirelength we are willing to trade for a unit of congestion relief.

Expected Impact

This optimization is specifically targeted at high-density / high-utilization designs (e.g., >85% placement density).

• Better: Local routability and effective timing in congested regions.
• Trade-off: Slight increase in global wirelength compared to a pure HPWL-driven approach, but with significantly improved manufacturability and reduced routing detours.

[maliberty]

DCO needs fixing. It would be helpful to rebase to head of master as this a month old.

[maliberty]

From reading just the description:

• The cost metric in UtilizationMap is not mentioned as being updated. This gives a very static view of congestion that will become increasingly less accurate. Also the computation is per pixel which will produce a very uneven map.
• Δ Congestion is not defined. I can guess but it would be good to define it
• HPWL degrading moves are allowed but no consideration of timing criticality is used. This may degrade critical paths when a non-critical instance could have been moved instead.

[maliberty]

clang-format and clang-tidy would also need addressing.

[maliberty]

In your testing did you measure changes in wns/tns?