Source-linked AI summary
Chip Placement with Deep Reinforcement Learning
Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Jiang, Ebrahim Songhori, Shen Wang, Young-Joon Lee, Eric Johnson, Omkar Pathak, Sungmin Bae, Azade Nazi, Jiwoo Pak, Andy Tong, Kavya Srinivasa, William Hang, Emre Tuncer, Anand Babu, Quoc V. Le, James Laudon, Richard Ho, Roger Carpenter, Jeff Dean
TL;DR
Chip placement is difficult, time-consuming, and still requires extensive human iteration for multi-objective optimization. This paper formulates placement as reinforcement learning, using supervised reward prediction to support transfer across netlists, and reports placements comparable or superior to human experts in under 6 hours. The approach improves with experience on more chip blocks, while its comparisons include a slower convergence than RePlAce and rely on a force-directed standard-cell placer that could be improved.
Problem
Chip placement must optimize power, performance, and area under density and congestion constraints, yet existing tools require human experts to iterate for weeks.
Method
The method trains an RL agent for sequential macro placement and uses supervised placement-quality prediction to learn netlist embeddings for transfer learning.
Results
Placements are superior or comparable to human experts in under 6 hours, while strongest baselines require human experts in the loop and several weeks.
Takeaways & Limitations
The RL agent becomes faster and better on unseen chip blocks as it gains experience across more netlists.
Takeaways & Limitations
RePlAce converges faster, and the method currently relies on a force-directed standard-cell placer that the authors identify as an opportunity for improved accuracy.
Abstract
from arXiv · showhide
In this work, we present a learning-based approach to chip placement, one of the most complex and time-consuming stages of the chip design process. Unlike prior methods, our approach has the ability to learn from past experience and improve over time. In particular, as we train over a greater number of chip blocks, our method becomes better at rapidly generating optimized placements for previously unseen chip blocks. To achieve these results, we pose placement as a Reinforcement Learning (RL) problem and train an agent to place the nodes of a chip netlist onto a chip canvas. To enable our RL policy to generalize to unseen blocks, we ground representation learning in the supervised task of predicting placement quality. By designing a neural architecture that can accurately predict reward across a wide variety of netlists and their placements, we are able to generate rich feature embeddings of the input netlists. We then use this architecture as the encoder of our policy and value networks to enable transfer learning. Our objective is to minimize PPA (power, performance, and area), and we show that, in under 6 hours, our method can generate placements that are superhuman or comparable on modern accelerator netlists, whereas existing baselines require human experts in the loop and take several weeks.
1. Introduction
Chip placement is a complex, time-consuming optimization problem that still requires weeks of human iteration, motivating a learning-based RL approach. The proposed method learns from prior netlists to generate faster, higher-quality placements for unseen chip blocks.
- Motivation: Chip placement maps macros and standard cells onto a chip canvas while optimizing PPA under density and routing-congestion constraints.Existing tools still require human experts to iterate for weeks, and netlist graphs can contain millions to billions of nodes.
- Approach: The method trains an RL agent to sequentially place macros, then uses a force-directed method to place standard cells.Training is guided by a fast, approximate reward signal for each placement.
- Generalization: The proposed approach generalizes to unseen netlists by leveraging experience from previously placed chips.Exposure to greater chip volume and variety makes the agent faster and better at generating optimized placements for new blocks.
- Results: Superior or comparable placements to human experts are generated in under 6 hours, while leading alternatives require human experts and several weeks per block.The method also achieves superior PPA on real Google TPU accelerator chips compared with state-of-the-art baselines.
2. Related Work
Prior placement methods include partitioning, stochastic, and analytic approaches, but they generally optimize each new chip from scratch. This work introduces end-to-end learning-based placement that transfers experience across netlists and directly optimizes target metrics.
- Prior placement methods: Global placement is a longstanding multi-objective optimization challenge involving circuits of increasingly large complexity.Historical approaches fall into partitioning-based, stochastic or hill-climbing, and analytic categories.
- Partitioning methods: Partitioning methods recursively divide netlists and canvases into smaller subproblems, enabling fast execution but limiting scalability as circuits grow.Sub-netlists are placed in subregions using optimal solvers once the subproblems are sufficiently small.
- Stochastic methods: Simulated annealing can produce high-quality solutions but is very slow and difficult to parallelize for increasingly large circuits.It applies random placement perturbations and sometimes accepts non-improving moves according to a gradually reduced temperature.
- Analytic methods: Analytic methods approximate wirelength and density with smooth functions combined into objectives, often requiring hierarchical placement of clusters.Examples include log-sum-exp, weighted-average, Gaussian, and Helmholtz models.
- Learning-based methods: The proposed end-to-end learning-based category learns from past placements, directly optimizes target metrics, and supports adjustable cost-function weights.Unlike methods that optimize each chip from scratch, it leverages prior-chip knowledge for new placements without requiring convex approximations of every target metric.
- Domain adaptation: Domain adaptation transfers knowledge across chip netlists to improve new-netlist results and reduces training time eightfold compared with training from scratch.Prior work focused on speeding policy training, whereas this approach also targets higher-quality generated placements.
3.1. Problem Statement
The problem is to map a netlist graph’s nodes onto a bounded two-dimensional chip canvas while optimizing final power, performance, and area.
- 3.1. Problem Statement: Chip placement maps netlist nodes onto a bounded 2D chip canvas to optimize final power, performance, and area.The netlist is the graph describing the chip.
3.2. Overview of Our Approach
The approach formulates placement as an RL process in which an agent sequentially places macros on feasible canvas locations and receives a final proxy-cost reward. Standard cells are then placed by a force-directed method, and PPO updates the policy from repeated episodes.
- Placement process: The RL agent sequentially places macros, after which a force-directed method produces a rough standard-cell placement.This combines learned macro placement with a conventional standard-cell placement stage.
- Actions: Actions are valid grid-cell placements for the current macro that respect density and blockage constraints.The selected action is the cell placement chosen by the RL policy network.
- States: States represent partial placements using netlist and current-node embeddings, metadata, and a feasibility mask over canvas grid cells.The state is updated after each newly placed macro.
- Reward: The reward is zero until the final step, when it becomes a weighted negative proxy cost based on wirelength and congestion.The reward is designed to be fast to evaluate while correlating with the commercial EDA tool’s true reward.
- Optimization: Repeated episodes train the policy to maximize cumulative reward, with PPO updating the policy parameters.The final reward is passed back to guide policy optimization.
3.3. Reward
The reward minimizes a weighted combination of proxy wirelength and congestion while enforcing density as a hard constraint. Several approximations make reward evaluation fast enough for RL optimization.
- Reward construction: The reward combines proxy wirelength and congestion through a weighted sum, with congestion weight λ set to 0.01.The reward is subject to density constraints.
- Wirelength: Wirelength uses half-perimeter wirelength, a bounding-box approximation whose value roughly tracks Steiner-tree length and correlates with power and timing.The overall cost is a normalized sum across nets.
- Placement procedure: Macros are ordered by descending size, with topological sorting breaking ties to improve feasibility and encourage proximity among connected nodes.After placement, standard cells are placed with force-directed methods and evaluated using commercial EDA tools after legalization.
- Congestion: Proxy congestion is estimated by deterministic routing and averaging the highest 10% of congestion values across grid cells.Separate vertical and horizontal allocations are smoothed with 5 × 1 convolutional filters.
- Constraints: Density is enforced as a hard constraint by masking placements that exceed the target or create infeasible macro overlap.This reduces invalid placements and the optimization search space.
3.4. Action Representation
The canvas is discretized into an m × n grid, and the policy chooses among available macro locations by selecting the highest-probability grid cell.
- Action space: The policy outputs a probability distribution over m × n grid locations for the current macro, and the action is its argmax.The grid defines the discrete action space for placement.
3.5. State Representation
Each state combines graph structure, node and edge attributes, the current macro, and netlist and technology metadata.
- State contents: The state includes netlist adjacency, node features, edge features, the current macro, and metadata such as routing capacity and canvas dimensions.These features support representation learning for chip placement.
4. Domain Transfer: Learning Better Chip Placements from Experience
The method learns transferable placement representations by training a reward-prediction architecture and reusing its encoder in RL policy and value networks. The resulting policy can optimize placements across netlists and generate zero-shot placements rapidly.
- Objective: The objective trains a policy over a dataset of K netlist graphs to maximize expected placement reward.J(θ, G) is the cost function, and Rp,g is the episode reward for placement p on netlist g.
- Objective: The reward is negative weighted wirelength and congestion subject to density constraints, with λ = 0.01 and max density 0.6 in experiments.This approximate reward supports policy optimization.
- Transfer learning: The architecture predicts placement reward on new netlists so its learned representation can transfer to unseen chip blocks.The state space varies substantially in graph size, topology, macro dimensions, and canvas dimensions.
- Supervised pretraining: The supervised dataset contains 10,000 placements from five accelerator netlists, generated across congestion weights and random seeds.Snapshots collected during training provide placements with varying quality and corresponding reward labels.
- Representation learning: A graph neural network embeds node types and adjacency, while metadata is embedded separately and combined for regression of wirelength and congestion.The graph embedding is formed by reducing edge embeddings with a mean function.
- Policy architecture: The prediction layer is removed and the pretrained architecture becomes the encoder for policy and value networks.These networks output placement probabilities and expected reward estimates from graph, current-node, and metadata inputs.
- Inference: Zero-shot placements require one inference step and can be generated in less than a second, while further quality improvement is possible through finetuning.The policy uses a fixed 128 × 128 representation with unused regions masked for smaller grids.
- Optimization: Policy optimization uses Proximal Policy Optimization with a clipped objective based on policy ratios and estimated advantages.The PPO objective constrains updates using clipping around 1 − ϵ and 1 + ϵ.
5. Results
The experiments show that pre-training enables faster convergence, better transfer to unseen blocks, and placements that meet or exceed strong automated and human baselines. Larger and more diverse training datasets improve zero-shot and finetuned placement quality, while the method remains slower than RePlAce.
- Learning from Larger Datasets: Pre-trained policies consistently outperform policies trained from scratch on domain-adaptation results.The comparison includes zero-shot placement and finetuning after 2 and 6 hours.
- Learning from Larger Datasets: More than 30 hours faster convergence was achieved by finetuning a pre-trained policy than by training from scratch on Ariane.The pre-trained policy also starts with and converges to a lower placement cost.
- Learning from Larger Datasets: 2, 5, and 20 training blocks produced progressively better zero-shot and equally finetuned placements on unseen test blocks.Greater training-set variety also reduced overfitting and improved performance on new blocks.
- Visualization Insights: Zero-shot Ariane placements already placed standard cells centrally within a macro surround, while finetuning regularized macros and reduced central congestion.The zero-shot arrangement was described as close to optimal and consistent with physical-design expert intuition.
- Visualization Insights: Donut-shaped macro placements surrounding standard cells reduced total wirelength relative to manual placement visualization.Figure 7 uses white for macros and green for standard cells, with designs blurred for confidentiality.
- Comparing with Baseline Methods: 14.4% higher wirelength and 24.1% higher congestion were produced by simulated annealing on average than by the proposed approach.The comparison used matched CPU-hours in simulation and search over similar numbers of states.
- Comparing with Baseline Methods: The proposed method outperformed RePlAce on placements meeting timing and congestion requirements, although RePlAce converged in 1 to 3.5 hours versus 3 to 6 hours.Some RePlAce placements were infeasible when timing or congestion exceeded the stated technology-dependent thresholds.
- Comparing with Baseline Methods: The method matched or outperformed human placements across WNS, area, power, and wirelength while taking less than 6 hours instead of multiple weeks.Both the method and human experts consistently generated viable placements meeting timing and congestion criteria.
6. Conclusion
The proposed RL-based chip-placement approach enables transfer learning, improving speed and quality with experience. It outperforms state-of-the-art baselines and produces placements comparable or superior to human experts in under 6 hours.
- The RL agent becomes faster and better at chip placement as it gains experience across more chip netlists.
- The method outperforms state-of-the-art baselines on modern accelerator placement.
- Under 6 hours, it generates placements superior or comparable to human experts, while the strongest baselines require experts in the loop and several weeks.