FPGA Divide-and-Conquer Placement using Deep Reinforcement Learning

Shang Wang, Deepak Ranganatha Sastry Mamillapalli, Tianpei Yang, Matthew E. Taylor

Introduction

In the field of Electronic Design Automation (EDA), placement is a critical step in the physical design flow. It involves the spatial arrangement of logic components on a chip to optimize performance metrics such as wirelength, power, and timing. For Field-Programmable Gate Arrays (FPGAs), this task is particularly challenging due to the fixed, prefabricated grid of logic blocks (CLBs), RAM, and DSPs. Traditional placement methods have long relied on Simulated Annealing (SA) or analytical techniques. However, as design complexity grows, these search-based heuristics face significant scalability and efficiency hurdles.

This paper introduces a novel approach to FPGA placement by leveraging Deep Reinforcement Learning (RL). By modeling the placement process as a Markov Decision Process (MDP) and implementing a "divide-and-conquer" training strategy, the authors demonstrate that RL agents can navigate the astronomical search spaces of chip design to produce layouts that rival industry-standard tools.

The FPGA Placement Challenge

Unlike Application-Specific Integrated Circuits (ASICs), where components can be placed with high flexibility, FPGAs impose strict architectural constraints. Every block must be assigned to a specific, compatible slot on a rigid grid. This environment presents three primary difficulties for standard RL algorithms:

  1. Constraint Complexity: The agent must adhere to legal slot types, making the action space highly constrained.
  2. Dimensionality: The state space for even a modest design is immense. For a netlist of 1,000 blocks, the potential configurations exceed $10^{2500}$, far surpassing the complexity of games like Chess ($10^{120}$).
  3. Sparse Rewards: The quality of a placement is typically only measurable after the entire design is routed. This lack of intermediate feedback makes it difficult for an agent to learn which specific moves contributed to a successful or failed layout.

Methodology

MDP Formulation and Architecture

The authors solve the placement problem using Proximal Policy Optimization (PPO), a robust actor-critic RL algorithm. To process the complex spatial and structural data of an FPGA, they employ a dual-stream neural architecture:

  • State Representation: The agent perceives the FPGA grid through a four-channel image representing capacity, wirelength estimates, and connectivity. This spatial data is processed via a ResNet.
  • Netlist Processing: The connectivity of the logic blocks (the netlist) is processed using a Graph Attention Network (GAT), allowing the agent to understand the relational dependencies between components.
  • Invalid Action Masking: To ensure the agent only selects legal placement slots, the authors implement action masking, which prevents the policy from exploring illegal states and accelerates convergence.

Divide-and-Conquer Training

To address the "curse of dimensionality," the authors propose a decomposition paradigm. Rather than attempting to place all blocks simultaneously, the task is broken into smaller subtasks (e.g., placing 14 or 15 blocks at a time). They explored four distinct settings for transferring knowledge between these subtasks:

  1. Multi-policy, Full Weight Reuse: Separate models for each subtask, inheriting all weights from the previous iteration.
  2. Multi-policy, Representation Reuse: Only the feature-extraction weights (ResNet/GAT) are kept; the decision-making layers (MLP) are reset.
  3. Single Policy, Full Weight Reuse: A single model handles all subtasks sequentially.
  4. Single Policy, Representation Reuse: A single model where decision layers are reset between subtasks.

Experimental Results

The methodology was evaluated using the MCNC20 benchmarks (specifically the tseng.net netlist) and the VTR (Verilog-to-Routing) open-source CAD suite. The RL agent's performance was compared against VTR’s state-of-the-art placement tools.

Performance and Policy Transfer

The study found that the Divide-and-Conquer (Setting 2) approach was the most effective. While a standard RL agent failed to outperform random placement on a full 56-block design, the decomposed agent achieved an average wirelength of 7169. This significantly outperformed the non-decomposed baseline (7591) and approached the optimal wirelength derived by VTR.

The Importance of Resetting

A key insight from the research was the phenomenon of "Negative Policy Transfer." When the agent reused all weights (Settings 1 and 3), it often became trapped in local optima, leading to "entropy collapse" where the agent stopped exploring better strategies. By resetting the decision-making layers while preserving the representation layers, the agent retained its understanding of the FPGA environment but remained flexible enough to discover superior placement strategies for new subtasks.

Conclusion and Future Work

This research demonstrates that Deep RL, when combined with a structured divide-and-conquer strategy, is a viable alternative to traditional FPGA placement heuristics. The use of representation learning allows the agent to generalize across different stages of the placement process.

However, several avenues for future work remain:

  • Multi-Objective Optimization: Current rewards focus on wirelength. Future iterations should incorporate timing (clock speed) and routing congestion.
  • Scalability: While successful on standard benchmarks, the approach must be scaled to modern FPGAs containing millions of logic elements.
  • Reward Shaping: To combat sparse rewards, the authors suggest implementing incremental wirelength estimates to provide the agent with more frequent feedback during the placement process.

Summary updated

Abstract

This paper introduces the problem of learning to place logic blocks in Field-Programmable Gate Arrays (FPGAs) and a preliminary learning-based method. In contrast to previous FPGA placement algorithms, we depart from heuristic search and instead employ Deep Reinforcement Learning (DRL) for the placement task with the objective of minimizing wirelength. To facilitate the agent's decision-making, we design unique state representations that include the chipboard observations and in-terconnections between different blocks. Additionally, we propose the decomposition training paradigm to address the nature of large search space and sparse rewards in the placement problem by dividing the full problem into small subtasks and solving each subtask using DRL respectively. Experiments demonstrate the effectiveness of the decomposition paradigm on FPGA placement tasks.
BibTeX
@misc{wang2024fpga,
  author = {Shang Wang and Deepak Ranganatha Sastry Mamillapalli and Tianpei Yang and Matthew E. Taylor},
  title = {{FPGA Divide-and-Conquer Placement using Deep Reinforcement Learning}},
  year = {2024},
  eprint = {2404.13061},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2404.13061},
}
Figure