PaperlayerView exact revision on arXiv

Source-linked AI summary

Routing Dense Layouts with History-Aware Offline Reinforcement Learning using LSTM

Afsara Khan, Austin Rovinski

arXiv:2609.08232v1cs.ARcs.LG

TL;DR

Dense routing can leave persistent violations, and prior offline cost-weight learning was limited to a fixed operating point. This paper uses history-aware offline RL to predict iterative routing costs across conditions. Across eight evaluated designs, it reports an average 92% DRV reduction and 10% runtime improvement over the baseline.

  • Problem

    Fixed or manually designed cost schedules can be brittle as density, local congestion, and the mix of violations change between routing iterations.

    Source: §1 · p. 1

  • Method

    The method uses offline conservative Q-learning with an LSTM policy that conditions cost-weight predictions on router features and recent routing history.

    Source: §1 · p. 1, §4 · p. 4

  • Results

    The model achieved an average 92% DRV reduction and an average 10% runtime improvement over the baseline across eight designs.

    Source: §6 · p. 8

  • Takeaways & Limitations

    The authors present the method as adaptable to any iterative cost-based detailed router through router-specific feature extraction and lightweight software integration.

    Source: §1 · p. 1

Abstract

from arXiv · show

Detailed routing remains a dominant runtime bottleneck in physical design due to increasing complexity of design rules. Modern routers can struggle to resolve persistent violations under dense operating conditions. While recent work leverages reinforcement learning (RL) to dynamically select costs for each routing iteration, we find that this technique struggles with high-density designs where routing solutions are significantly harder. To address this, we present a history-aware offline RL policy which predicts iterative cost weights in these dense regimes to improve convergence across placement densities by utilizing readily available features from the router. Our policy uses conservative Q-learning similarly to prior work; however, our key insight is that addition of a lightweight LSTM architecture and additional features can retain sequence context and improve routing convergence across multiple densities and route guide qualities. Our policy can be integrated into any cost-based router with minimal pipeline changes, as it does not interfere with the core search algorithm. We evaluate our policy on held-out density and adjustment settings, including difficult operating points induced by dense placement and low guide quality. Our policy reduces design rule violations (DRVs) by an average of 92% over the top public baseline while simultaneously reducing runtime by 10%.

1 Introduction

Dense placement leaves fewer tracks for rerouting, making fixed cost schedules brittle as congestion and violation mixes change. The paper applies history-aware offline RL to predict routing costs across these conditions.

1 Introduction

  • The policy combines offline conservative Q-learning with an LSTM and feature engineering to retain routing history and address distribution shifts across operating conditions.The approach also masks density and adjustment inputs during training and uses ratios and logarithms for local signals.Source: §1 · p. 1
  • Gains are consistent across densities and largest when test density lies between training points, though intermediate densities remain nontrivial.The authors relate the largest interpolation gains to learned models behaving more reliably in interpolation than extrapolation.Source: §1 · p. 1
  • CQL+LSTM remains effective as placement density rises, while prior CQL degrades sharply.Figure 1 compares routing performance for aes across placement densities.Source: §1 · p. 1, Figure 1 · p. 2
  • The work contributes a routing dataset, identified state variables and reward components, and an offline RL implementation evaluated across diverse designs in high-utilization regimes.The training and inference implementation is open sourced.Source: §1 · p. 2

2 Related Work

Detailed routers use iterative search and repair, while the weights guiding that search are commonly manually scheduled. Prior routing ML includes prediction and RL, but earlier offline RL cost control was evaluated at a single operating point.

2.1 Detailed Routers

  • Modern detailed routers build on maze or A* search and iterative rip-up-and-reroute, while exposed cost weights are controlled by manually designed schedules.OpenROAD is described as a state-of-the-art academic router derived from TritonRoute.Source: §2.1 · p. 2

2.2 Machine Learning Techniques in Routing

  • Routing ML has included congestion and violation prediction, pin-access prediction, and online RL combining GNNs with PPO.The predictive approaches typically require secondary mechanisms to influence routing behavior.Source: §2.2 · p. 2
  • Prior offline RL learned routing cost weights at one operating point; this work adds history-aware policy inputs and feature engineering for varying regimes and hard cases.The approach is demonstrated using OpenROAD and is described as adaptable to any cost-based router.Source: §2.2 · p. 2

3 Methodology

The methodology controls routing cost weights between iterations and builds training sequences from router state signals. It focuses on dense conditions where routing resources and feature distributions vary with placement and adjustment.

3.1 Routing and Policy

  • Lower global-routing adjustment can free tracks to resolve congested guides, but leaves fewer reserved detailed-routing resources and raises the likelihood of stalls and persistent violations.Lower adjustment is needed only when the guide would otherwise be congested at that density.Source: §3.1 · pp. 2–3
  • The policy resets four shared cost multipliers each iteration from the current routing state, while leaving the core search unchanged.The multipliers penalize DRC violations, nearby violation markers, fixed obstructions, and the influence of old markers.Source: §3.1 · p. 3
  • Cumulative DRV was tested as a runtime proxy, but its correlation with runtime was inconsistent because stubborn late-stage violations and parallel partition work complicate the relationship.Runs with similar total DRV could have large runtime differences.Source: §3.1 · p. 3

3.2 Data Generation

  • The dataset contains about 10,000 routing runs from eight designs across six placement densities and global-routing adjustments from 0.0 to 0.3.Most traces came from adjustments of 0.10 to 0.30, with a smaller, slower portion at 0.00.Source: §3.2 · p. 3
  • A coarse die grid tracks whether violation regions persist, migrate, or cluster, and the derived grid and progress features are contributions of this work.The paper illustrates a region at iterations 0 and 4 in an 11-iteration aes run.Source: §3.2 · pp. 3–4, Figure 2 · p. 3
  • Features use normalized values, relative progress, ratios, and logarithms to stabilize signals across settings; each routing run forms a sequence of states for training.The state also includes previous cost weights and density, adjustment, and design-related signals.Source: §3.2 · pp. 3–4

4 Model Architecture

The architecture treats cost-weight selection as a sequence-aware offline RL problem, using LSTM actor and critics and a reward balancing DRV progress, speed, instance difficulty, and hotspot locality.

  • Two-layer LSTM actor and critics retain episode history; CQL stabilizes training where standard Q-learning exhibited growing Bellman error, gradient explosions, and out-of-distribution overestimation.Source: §4 · p. 4
  • Reward combines progress toward DRV reduction, earlier completion, difficulty-scaled credit, and local hotspot changes, while excluding cumulative DRV and true runtime.Source: §4 · p. 4
  • Feature masking regularizes density and adjustment interactions during training, while validation and test use the full feature set.Source: §4 · p. 4
  • Inputs are normalized, using ratios or logs for wide-ranging features; 100 Optuna trials select CQL hyperparameters to accelerate convergence and avoid instability.Source: §4 · pp. 4–5
  • Early-stopping checks monitor loss and TD-error divergence and action difference; action-difference values above 1.0 are a warning threshold, with persistent increases prompting stops.Source: §4 · p. 5
  • Actor and critic losses flatten near zero, TD error remains low, and conservative loss approaches zero during LSTM–CQL training.Source: §4 · p. 5, Figure 4 · p. 5
  • At each iteration boundary, the router supplies the current state and applies returned multipliers to the next iteration; integration changes four knobs while leaving search unchanged.Source: §4 · p. 5

5 Experimental Results

The evaluation tests the policy across held-out placement densities and harder routing conditions, using converging and baseline-non-converging cases. It reports lower DRVs and runtime, with a small overall wirelength increase.

5.1 Methodology

  • The study evaluates OpenROAD Design Suite circuits in Nangate45 using density sweeps and harder cases where the baseline fails to reach zero DRVs within 65 iterations.For converging cases, test densities fall between training densities with adjustment fixed; hard cases report full convergence or terminal DRVs under the same cap.Source: §5.1 · pp. 5–6

5.2 Reporting format

  • Converging cases use density-versus-iteration plots and paired runtime comparisons, while hard cases report terminal DRVs, runtime, and wirelength.Policy inference overhead is included in reported runtimes.Source: §5.2 · p. 6

5.3 Benchmark Performance

  • At adjustment=0.0, limited routing resources require extensive rip-up and reroute, raising runtimes in the hard cases.Despite the hardest settings at maximum density, ibex and gcd still converged; no non-converging ariane136 point was found within reasonable runtime constraints.Source: §5.3 · pp. 6–7
  • For most designs, model iteration and runtime improvements persisted across held-out densities not seen during training, despite topology differences between densities; all designs in Figure 7 finished with 0 DRVs.Source: §5.3 · p. 6, Figure 7 · p. 7
  • Across both regimes, the model consistently reduces iterations and runtime in converging cases and significantly reduces DRVs in non-converging cases, with a 92% DRV decrease from baseline alongside a 10% runtime improvement.Source: §5.3 · p. 7
  • Wirelength increased 0.32% overall; increases over 1% were balanced by DRV reductions over 90%, and wirelength was not a reward target.For harder cases, inference cost is well under 0.01% of total routing time, though it dominates the speedup for gcd and ibex.Source: §5.3 · p. 8

6 Conclusion

The paper concludes that history-aware offline RL can control iterative routing costs across varying conditions. On eight augmented-density OpenROAD designs, it reports average DRV and runtime improvements over the baseline.

6 Conclusion

  • Across eight augmented-density OpenROAD designs, the model achieved an average 92% DRV reduction and 10% runtime improvement over the baseline.Compared with the prior CQL-only approach, the LSTM-enhanced architecture improved convergence across densities.Source: §6 · p. 8
  • The offline RL model combines an LSTM with design features and DRV history to infer iterative routing cost weights.The authors state that it can be extended to routers using iterative search.Source: §6 · p. 8
  • The authors present the approach as portable to routers that use iterative cost-based algorithms.Its evaluation in this paper uses OpenROAD design-suite circuits with augmented densities.Source: §6 · p. 8
Loading 2609.08232v1…