PaperlayerView exact revision on arXiv

Source-linked AI summary

On Joint Learning for Solving Placement and Routing in Chip Design

Ruoyu Cheng, Junchi Yan

arXiv:2111.00234v2cs.LGcs.AI

TL;DR

Chip-design learning faces challenges in scalability, reward design, and end-to-end placement and routing. DeepPlace and DeepPR combine reinforcement learning with gradient-based placement or routing, and the reported method surpasses a separate placement-and-routing pipeline by a notable margin.

  • Problem

    Chip placement and routing learning faces challenges in scalability, reward design, and end-to-end learning; congestion and HPWL are imperfect proxies for routability and wirelength.

    Source: §3.3.1 · p. 5, §3.5 · p. 6

  • Method

    DeepPlace uses reinforcement learning for sequential macro placement followed by gradient-based standard-cell placement, while DeepPR jointly learns placement and routing using multi-view embeddings and random network distillation for exploration.

    Source: §1 · p. 2, §3.1 · p. 4, §5 · p. 10

  • Results

    The method surpasses a separate placement-and-routing pipeline by a notable margin, and experiments on public benchmarks show solver effectiveness.

    Source: §1 · p. 2, §5 · p. 10

  • Takeaways & Limitations

    DeepPR can use the exact total routed wirelength as the episodic reward for both placement and routing agents, rather than relying only on proxy objectives.

    Source: §3.5 · p. 6

    The model is currently limited to placement with a moderate number of macros because of GNN scalability and the large reinforcement-learning action space.

    Source: §5 · p. 10

Abstract

from arXiv · show

For its advantage in GPU acceleration and less dependency on human experts, machine learning has been an emerging tool for solving the placement and routing problems, as two critical steps in modern chip design flow. Being still in its early stage, there are fundamental issues: scalability, reward design, and end-to-end learning paradigm etc. To achieve end-to-end placement learning, we first propose a joint learning method termed by DeepPlace for the placement of macros and standard cells, by the integration of reinforcement learning with a gradient based optimization scheme. To further bridge the placement with the subsequent routing task, we also develop a joint learning approach via reinforcement learning to fulfill both macro placement and routing, which is called DeepPR. One key design in our (reinforcement) learning paradigm involves a multi-view embedding model to encode both global graph level and local node level information of the input macros. Moreover, the random network distillation is devised to encourage exploration. Experiments on public chip design benchmarks show that our method can effectively learn from experience and also provides intermediate placement for the post standard cell placement, within few hours for training.

1 Introduction

Placement and routing are coupled, time-consuming chip-design stages, while rising IC scale challenges existing EDA methods. The paper combines reinforcement learning with gradient optimization for placement, extends learning to joint placement and routing, and reports better results than a separate pipeline.

1 Introduction

  • Placement maps netlist components to chip locations, and routing connects them; placement quality affects area, timing, and routability.The placement objective includes power, performance, and area while respecting density and congestion constraints.Source: §1 · pp. 1–2
  • DeepPlace uses reinforcement learning to place macros, then gradient-based optimization to arrange standard cells.The authors describe this as end-to-end learning for the joint placement of macros and standard cells.Source: §1 · p. 2
  • DeepPR applies reinforcement learning to jointly solve placement and the subsequent routing task.Source: §1 · p. 2
  • The policy network combines CNN and GNN views of placement inputs, while random network distillation encourages exploration.The two views provide global and node-level information.Source: §1 · p. 2
  • The proposed methods surpass the separate placement-and-routing pipeline by a notable margin.The paper evaluates both joint macro/standard-cell placement and joint placement and routing.Source: §1 · p. 2

2 Related Work

Prior work spans classical placement optimization, learning-based placement, and machine-learning or reinforcement-learning approaches to routing. The paper positions its contribution as combining reinforcement learning with gradient optimization for full placement and jointly learning placement and routing.

2 Related Work

  • Classical placement methods include partitioning, stochastic search, and analytic solvers, with modern analytical placers using gradient-based optimization for large cell sets.Partitioning trades solution quality for speed, while nonlinear optimization offers smoother cost approximations at higher complexity.Source: §2 · p. 2
  • DREAMPlace implements RePlAce operators in PyTorch and reports over 30× speedup against CPU-based tools.Source: §2 · p. 2
  • Learning-based placement includes sequential macro placement with RL and a cyclic RL–simulated-annealing framework [16].The former is learning-based with an objective like analytic solvers; the latter is essentially an annealing solver.Source: §2 · p. 3
  • Routing research includes prediction models, RL for routing directions, attention-based REINFORCE for routing orders, and RL for fixing design-rule violations.Classical routing also decomposes multi-pin nets into two-pin problems.Source: §2 · p. 3
  • The paper combines RL and gradient optimization without clustering to produce full placement, and presents joint placement-routing via RL as a first attempt.It contrasts this with coarse clustered placement and local-density penalties for routability.Source: §2 · p. 3

3 Methodology

The methodology combines sequential reinforcement-learning macro placement with gradient-based standard-cell placement, and extends learning to joint placement and routing. It uses multi-view policy embeddings, extrinsic wirelength and congestion rewards, and intrinsic rewards to guide exploration.

3.1 Problem Formulation

  • The MDP places macros sequentially into valid grid positions, using a layout image and netlist graph as state and terminal wirelength/congestion reward plus per-step RND bonuses.The agent can then fix macro positions for gradient-based standard-cell placement or route the placement and use total wirelength as the reward for both agents.Source: §3.1 · p. 4

3.2 The Structure of Policy Network

  • The policy concatenates CNN global-layout and GNN node embeddings, then uses a fully connected layer to produce probabilities over available positions.The CNN captures the global image, while the GNN provides detailed node embeddings from the netlist graph.Source: §3.2 · p. 5, Figure 3 · p. 5

3.3.1 Extrinsic Reward Design

  • The extrinsic reward combines negative wirelength and congestion, approximating wirelength with HPWL and congestion with RUDY.The congestion threshold is 0.1 in the experiments; the wirelength and congestion terms are weighted according to the chip setting.Source: §3.3.1 · pp. 5–6

3.3.2 Intrinsic Reward Design

  • Random network distillation supplies an intrinsic bonus at each step using the expected embedding error between a fixed random target network and a trainable predictor.The predictor is trained to minimize expected MSE; larger error indicates a novel state and yields a higher bonus.Source: §3.3.2 · p. 6

3.4 Combination with Gradient-based Placement Optimization

  • DREAMPlace performs gradient-based placement of standard cells during reward calculation, with fixed macro positions influencing its solution and improving through agent training.The authors report that its GPU-accelerated implementation reduces runtime to less than a minute.Source: §3.4 · p. 6

3.5 Joint Learning of Placement and Routing

  • DeepPR uses placement solutions as routing-agent training data and uses routed total wirelength as reward for both placement and routing agents.This direct routing objective avoids intermediate cost models that can introduce bias into the placement reward.Source: §3.5 · p. 6

4 Experiments

The experiments evaluate the placement and routing methods on modified ISPD-2005 benchmarks and large-scale designs. DeepPlace outperforms sequential placement in all test cases, while pretraining, runtime, and ablation results examine how the approach behaves.

4.1 Benchmarks and Settings

  • The modified ISPD-2005 suite exchanges most fixed macros for movable ones, and bigblue3 and bigblue4 test scalability on designs with millions of cells.The RL agent places movable macros; the benchmark statistics define design density as total object area divided by placement-region area.Source: §4.1 · pp. 6–7, Table 1 · p. 7

4.2 Pretraining

  • Pretraining on macro-only connectivity improves later placement when moderate: 300 iterations perform best, while 500 iterations can hurt exploration and placement quality.The authors therefore use moderate pretraining before finetuning for subsequent tasks.Source: §4.3 · p. 7, §4.2 · p. 7, Figure 4 · p. 8

4.3 Results on Joint Macro/Standard cell Placement

  • Approximately 4× speedup over RePlace accompanies DeepPlace’s win over sequential learning in every test case.The comparison covers circuits from ISPD-2005.Source: §4.3 · p. 8, Figure 5 · p. 9

4.4 Results on Joint Placement and Routing

  • For larger circuits, the RL module occupies a small share of DeepPlace runtime, and total runtime is approximately 4× faster than RePlace.The RL macro-placement runtime grows more slowly than the gradient-based standard-cell placer’s runtime.Source: §4.3 · p. 8, Figure 5 · p. 9

4.5 Ablation Study

  • Combining global CNN and local GNN embeddings improves over the baseline, while adding RND’s intrinsic reward for exploration surpasses the baseline by a large margin.The baseline shows only modest improvement over the initial random policy; CNN-only and GNN-only embedding results are similar.Source: §4.5 · p. 10, Figure 7 · p. 10

5 Conclusion and Outlook

The paper presents DeepPlace for macro and standard-cell placement and DeepPR for joint placement and routing, using two-view embeddings and distillation to support learning. It reports effectiveness on public benchmarks, while noting limits in macro-count scalability and that full end-to-end learning across placement and routing remains future work.

  • DeepPlace uses reinforcement learning for macro placement and gradient-based optimization for standard-cell placement in an end-to-end pipeline.DeepPR extends reinforcement learning to joint placement and routing.Source: §5 · p. 10
  • The paper’s two-view embedding fuses global and local information, while distillation is used to improve exploration.Source: §5 · p. 10
  • Joint end-to-end learning of macro and standard-cell placement with routing remains future work, which the authors attribute to the scale and complexity of the task.Source: §5 · p. 10
  • The model is limited to a moderate number of macros because of GNN scalability and the large RL action space.Future work includes accounting for macro size and shape to further reduce overlap.Source: §5 · p. 10
  • The paper identifies possible job displacement in the EDA industry as a potential negative societal impact of automated placement and routing.Source: §5 · p. 10
Loading 2111.00234v2…