PaperlayerView exact revision on arXiv

Source-linked AI summary

RollPlace: Improving Macro Placement via Monte Carlo Rollout Search

Qi Zhou, Guojun Liu, Guangzhi Qi, Ming Lu, Jiechu Liu, Zhongli Liu, Jianqun Yang, Xingji Li

arXiv:2610.06316v1cs.AI

TL;DR

Existing ML-based placement methods often generate layouts in one attempt, even though macro-placement sequences can accumulate errors. RollPlace initializes layouts with ML or heuristics and refines them through Monte Carlo search and rollout; it reports better benchmark performance, with scalability and evaluation-resource limits to consider.

  • Problem

    One-pass sequential macro placement can accumulate deviations because earlier macro positions influence later decisions, degrading layout quality.

    Source: §I · p. 1

  • Method

    RollPlace builds a search tree from ML- or heuristic-generated initial layouts and refines candidate sequences through MCTS and swap-based rollout.

    Source: §I · p. 2

  • Results

    RollPlace outperforms state-of-the-art methods across multiple benchmarks; it leads on six of eight circuits and reduces initial HPWL by around 30% on average.

    Source: §I · p. 2, A. Macro Placement Experimental Results · p. 7

  • Takeaways & Limitations

    The conclusion presents iterative refinement as a promising pathway for macro placement and reports robustness across diverse benchmarks.

    Source: §VI · p. 11

    RollPlace faces scalability challenges on benchmarks with exceptionally large macro counts.

    Source: §VI · p. 11

Abstract

from arXiv · show

The application of Reinforcement Learning (RL) in Electronic Design Automation (EDA), particularly for chip placement, has attracted considerable attention in recent years. While existing machine learning (ML)-based approaches have achieved notable progress, they predominantly focus on generating optimal layouts in a single attempt, often producing solutions that require subsequent refinement. To address this limitation, we propose RollPlace, a novel and generalized macro placement framework. RollPlace adopts a two-stage optimization strategy: generating initial placement solutions via machine learning methods or heuristic-based strategies, and refining these layouts efficiently by adjusting specific macros derived from the initial stage. This strategy circumvents the sequential generation constraints inherent in traditional RL-based placement methods. Furthermore, RollPlace seamlessly integrates Monte Carlo Tree Search (MCTS) to balance exploration and exploitation, and employs a rollout mechanism for efficient local search. Extensive experiments on the ISPD 2005 benchmark demonstrate that RollPlace outperforms state-of-the-art methods. Additionally, end-to-end experimental results based on OpenROAD across 19 benchmarks show that RollPlace excels in multiple metrics. The proposed framework offers a robust and scalable solution for addressing the growing complexity of modern chip design challenges.

I. INTRODUCTION

Macro placement is consequential for chip performance, but evaluating a layout requires completing macro placement, and sequential one-pass methods can accumulate errors. RollPlace combines ML or heuristic initialization with Monte Carlo search and rollout refinement; the introduction reports strong benchmark performance.

I. INTRODUCTION

  • Prior ML-based placement work has made notable progress, while macro placement quality is consequential for timing, power consumption, and area utilization.Evaluating a layout typically requires placing all macros, often followed by iterative layout refinement.Source: §I · p. 1
  • One-pass sequential placement can accumulate deviations as earlier macro positions influence later ones, degrading overall layout quality.Benchmarks often contain hundreds of macros, making a single generated sequence long.Source: §I · p. 1
  • RollPlace generates initial sequences with ML or heuristic strategies, then iteratively refines a search tree using MCTS and rollout.Initial sequences can be generated for previously unseen chips, supporting generalization.Source: §I · p. 2
  • A swap-based rollout algorithm targets limited adjustment flexibility for higher-index macros by enabling dynamic position adjustments.The paper reports that this component improves placement quality.Source: §I · p. 2
  • RollPlace consistently outperforms state-of-the-art methods across multiple macro-placement benchmarks and shows advantages in end-to-end OpenROAD evaluation.The reported end-to-end evaluation covers the complete chip-design workflow.Source: §I · p. 2

II. RELATED WORK

Optimization-based macro placement spans partitioning, simulated annealing, and analytical methods, each with different trade-offs or structural challenges. Learning-based approaches include RL and hybrid search methods that address reward sparsity, training demands, and placement quality.

A. Optimization-based Methods

  • Partition-based methods [10], [11] divide circuits into sub-circuits and place them independently, but diverse topologies can make suitable partitioning difficult.The resulting sub-regions are subsequently adjusted to positions on the chip.Source: A. Optimization-based Methods · p. 3
  • Simulated annealing methods – iteratively perturb and evaluate solutions, while DREAMPlace, uses PyTorch to accelerate analytical placement.Quadratic analytical methods are efficient but often lower quality; nonlinear methods approximate costs more accurately with higher computational complexity.Source: A. Optimization-based Methods · p. 3

B. Learning-based Methods

  • RL-based macro placement grew from MDP formulations; MaskPlace uses a wire mask to provide immediate rewards and mitigate sparse-reward learning.PRNet adds overlap area as a penalty in its reward function.Source: B. Learning-based Methods · p. 3
  • ChiPFormer combines offline placement-data training with online fine-tuning for unseen circuits, while EfficientPlace combines local policy learning with global tree search.EfficientPlace is described as sample-efficient, improving placement quality with reduced runtime compared with traditional RL methods.Source: B. Learning-based Methods · p. 3

III. PRELIMINARY

Chip placement arranges movable macros and standard cells under constraints while optimizing design metrics, and the large scale of contemporary benchmarks makes the task computationally complex. The formulation represents macro locations as coordinates and uses HPWL as an efficient wirelength estimate.

III. PRELIMINARY

  • Placement must manage constraints such as overlap, congestion, and density while seeking to reduce wirelength and power consumption.Contemporary benchmarks typically contain hundreds of macros and tens of thousands of standard cells; industrial designs are larger still.Source: §III · p. 4

A. Problem Formulation

  • The macro-placement input is a hypergraph of macros and netlist connections, and a solution specifies each macro’s two-dimensional location.The solution is represented as a sequence of coordinate pairs for the macros.Source: A. Problem Formulation · p. 4
  • HPWL estimates interconnect length efficiently by summing the horizontal and vertical spans of each net’s bounding box.Pin locations depend on macro placement and pin offsets; total HPWL sums the individual net values.Source: A. Problem Formulation · p. 4

B. Notations

The paper represents macro placement as discrete grid coordinates in a sequential decision model. It identifies one-time generation and fixed macro ordering as constraints on refinement and placement quality.

B. Notations

  • A placement solution π assigns each of N macros a coordinate (x_i, y_i) on a discrete M × M grid.The placement instance is a hypergraph H = (V, E).Source: B. Notations · p. 4
  • The framework models placement as sequential decisions, with a stochastic policy generating a solution from the instance and previous solutions.At the first step, the prior decision sequence is empty.Source: B. Notations · p. 4

A. Motivation

  • One-time generation limits later refinement: after sequential placement, the final configuration is fixed, unlike manual placement that permits repositioning macros.The paper argues that fine-tuning generated results is needed for better placement outcomes.Source: A. Motivation · pp. 4–5
  • Fixed macro order can propagate early placement errors into later decisions, motivating dynamic adjustment of placement order.Source: A. Motivation · p. 5

B. Framework

RollPlace generates initial placements using ML or heuristic strategies, then refines them through Monte Carlo rollout search. The search selects candidate sequences, adjusts a sampled subset of macros, and updates its tree using the resulting HPWL.

B. Framework

  • RollPlace generates initial solutions with RL or heuristic strategies, then refines them through Monte Carlo rollout search over a tree of candidate solutions.The process iterates through selection, order exchange, simulation, rollout, and tree update.Source: B. Framework · p. 5

C. Initialize Placement

  • Transferable ML placers or fast placers are recommended for initialization to reduce placement time; ChiPFormer requires only target-chip fine-tuning after pretraining.Source: C. Initialize Placement · p. 5

D. Monte Carlo Rollout Search

  • The adjustment relies on a valid placement remaining valid when a sampled subset is repositioned while the other macros stay fixed, subject to constraints.The paper describes this as equivalent to placing the fixed macros first and then the adjusted subset.Source: D. Monte Carlo Rollout Search · p. 5
  • Selection samples a complete candidate path through the tree, using UCT to balance exploration and exploitation when choosing each child node.The UCT confidence bound uses an estimated node value and visit counts.Source: D. Monte Carlo Rollout Search · pp. 5–6
  • Randomly sampled macro indices are moved to the sequence end for local search, while the remaining macros retain their candidate positions.The selected subsequence is optimized through rollouts; the other macros are placed in the simulation at their existing positions.Source: D. Monte Carlo Rollout Search · p. 6
  • Multiple rollouts can follow one simulation, and the solution with the lowest HPWL is selected for tree updating.Existing nodes are updated; otherwise, the selected solution adds a new node.Source: D. Monte Carlo Rollout Search · p. 6

E. Heuristic Function

RollPlace places each macro using a heuristic that combines legal-position and wire-cost masks. It samples uniformly among minimum-valued coordinates, rather than using WireMask-EA’s nearest-position greedy choice.

E. Heuristic Function

  • The heuristic F_i is the Hadamard product of position mask P_i and wire mask W_i, both dynamically generated from the current placement.The placement policy samples uniformly among coordinates with minimum F_i values.Source: E. Heuristic Function · p. 6
  • Unlike WireMask-EA’s greedy nearest-position choice, RollPlace samples uniformly to explore more candidate positions for better HPWL.Source: E. Heuristic Function · p. 6
  • The position mask marks legal grid locations that satisfy overlap constraints and canvas boundaries.Its grid uses 1 for legal positions and ∞ for illegal positions.Source: E. Heuristic Function · pp. 6–7
  • The wire mask represents the normalized HPWL increase for placing the current macro at each grid position.Source: E. Heuristic Function · p. 7

A. Macro Placement Experimental Results

On ISPD 2005 macro-placement benchmarks, RollPlace’s fine-tuning improves initial HPWL and compares favorably with recent methods. Its search also shows faster, more stable convergence and progressive layout refinement.

A. Macro Placement Experimental Results

B. Congestion Analysis

RollPlace’s congestion results are strong across the benchmark circuits, alongside its focus on HPWL minimization. Congestion is evaluated with RUDY, while density metrics are not reported.

B. Congestion Analysis

  • Congestion is calculated with the RUDY algorithm from Table I placements; DeepPlace is excluded because placement data are unavailable.Density metrics are not reported because RollPlace enforces strict non-overlap during placement.Source: B. Congestion Analysis · p. 8, Table III · p. 9
  • The adaptec2 visualization compares RollPlace with five recent methods using macro layouts; lower HPWL indicates better placement quality.Blue rectangles denote macros.Source: Figure 6 · p. 9
  • RollPlace achieves the best congestion values on seven of eight benchmark circuits and second-best performance on seven of eight benchmarks.Table III standardizes the best congestion values to 1 and marks best and second-best results.Source: B. Congestion Analysis · p. 8, Table III · p. 9

C. Full Placement Analysis

In the independent workflow, macro-placement HPWL does not reliably track full-placement HPWL. RollPlace’s collaborative workflow instead feeds full-placement HPWL into iterative search.

C. Full Placement Analysis

  • A lower macro-placement HPWL does not invariably yield a lower full-placement HPWL in the independent workflow.Fig. 7’s green curve illustrates their evolving relationship.Source: C. Full Placement Analysis · p. 9, Figure 7 · p. 10
  • The collaborative workflow places macros with RollPlace, places standard cells with DREAMPlace, then replaces macro HPWL in the search tree with full-placement HPWL for iterative refinement.This uses full-placement HPWL as the search feedback metric.Source: C. Full Placement Analysis · p. 9
  • The collaborative process establishes a positive correlation between macro and full-placement HPWL, with more consistent and predictable optimization outcomes.The orange curve in Fig. 7 represents the collaborative workflow; Table IV reports full-placement HPWL, where lower values are better.Source: C. Full Placement Analysis · p. 9, Figure 7 · p. 10, Table IV · p. 10

D. Full Placement Experimental Results

In mixed-size full placement, RollPlace reports state-of-the-art results across all evaluated benchmark circuits. The authors attribute the performance to collaborative macro and standard-cell placement optimization.

D. Full Placement Experimental Results

  • RollPlace achieves state-of-the-art full-placement HPWL results across all benchmark circuits.Table IV compares full-placement HPWL, with lower values indicating superior performance.Source: D. Full Placement Experimental Results · p. 10
  • The mixed-size placement objective minimizes HPWL across macros and standard cells together.The reported results are generated through RollPlace’s full-placement workflow.Source: D. Full Placement Experimental Results · p. 10
  • Consistent improvements across diverse benchmarks suggest that integrating macro and standard-cell placement optimization in one framework is important for placement quality.The authors describe the results as validating their collaborative optimization strategy.Source: D. Full Placement Experimental Results · p. 10

E. End-to-End Evaluation

The end-to-end evaluation runs RollPlace through OpenROAD on 19 ChiPBench benchmarks and reports average rankings across design metrics. The conclusion describes iterative local refinement as RollPlace’s core approach and notes limitations in scalability, heuristics, evaluation cost, and timing performance.

E. End-to-End Evaluation

  • The evaluation uses 19 ChiPBench benchmarks at the NanGate45 technology node and constructs an end-to-end process using OpenROAD.Source: E. End-to-End Evaluation · p. 10
  • For ML-based methods using Bookshelf, the workflow converts LEF/DEF results to Bookshelf for macro placement and back afterward; DREAMPlace and Hier-RTLMP natively support LEF/DEF.Source: E. End-to-End Evaluation · p. 10
  • Reported metrics include final-design PPA measures and intermediate congestion, wirelength, HPWL, and MacroHPWL measures.Final PPA metrics are WNS, TNS, NVP, power, and area.Source: E. End-to-End Evaluation · p. 10
  • For this workflow, hMetis clusters standard cells into 64 partitions treated as macros, after which placement is converted back to LEF/DEF for later OpenROAD stages.Source: E. End-to-End Evaluation · pp. 10–11
  • RollPlace achieves the best average ranking in HPWL, congestion, wirelength, and area, while Hier-RTLMP ranks best in regularity, WNS, TNS, NVP, and power.Table V reports average rankings across all benchmarks, with smaller rankings indicating better performance.Source: Table V · p. 11, E. End-to-End Evaluation · p. 11

VI. CONCLUSION

  • RollPlace refines initial layouts through iterative local adjustments with Monte Carlo rollout search and heuristic functions.Source: §VI · p. 11
  • The conclusion reports that RollPlace consistently outperforms recent RL and black-box optimization algorithms and is robust across diverse benchmarks.Source: §VI · p. 11
  • RollPlace faces scalability challenges on exceptionally macro-heavy benchmarks, uses only a simple wire mask, incurs costly full-placement evaluation, and lacks RTL dataflow for state-of-the-art WNS and TNS performance.Source: §VI · p. 11

Related papers

This paper cites

Loading 2610.06316v1…