Transformer-based Reinforcement Learning for Net Ordering in Detailed Routing

Zhanwen Zhou, Hankz Hankui Zhuo, Jinghua Zhou, Wushao WenIJCAI 2025 · DOI

TL;DR

This paper introduces TREND, a novel framework that uses Transformer-based Reinforcement Learning to optimize the order in which connections (nets) are routed in complex integrated circuits. By learning from routing experiences, TREND significantly reduces design rule violations and routing costs compared to existing methods, paving the way for more efficient and cost-effective chip design.

What Problem Does This Paper Address?

Designing integrated circuits (ICs) involves routing millions of tiny wires (nets) on a multi-layered silicon chip. Detailed routing, the final stage of this process, is particularly challenging due to increasingly complex design rules and shrinking feature sizes. A critical factor influencing the success and efficiency of detailed routing is the order in which these nets are processed. Routing nets in a suboptimal order can lead to numerous design rule violations (DRVs), requiring extensive "rip-up and reroute" cycles, which significantly increases design time and cost. While previous approaches have relied on hand-crafted heuristics or simpler machine learning methods, these often struggle to capture the intricate dependencies between nets and the available routing space, limiting their generalization and effectiveness. This paper tackles the problem of automatically learning an optimal net ordering strategy that minimizes DRVs and routing cost.

Methods

The core of the proposed solution, TREND, is a Transformer-based Reinforcement Learning framework. It models the net ordering problem as a Markov Decision Process (MDP).

  • Graph Convolutional Network (GCN) Embedder: To represent the complex relationships and features of nets within a routing region, a GCN is used. It takes net features (like number of pins, accessibility, size) and their spatial overlaps as input, generating a rich embedding for each net.
  • Transformer Encoder: This component processes the GCN embeddings to capture the sequential context and dependencies among neighboring nets, creating enhanced per-net representations.
  • Pointer Network Decoder: This is the key to generating the net order. It sequentially selects the next net to route, taking into account the previously selected nets and the current state of the routing environment. This allows for dynamic decision-making.
  • Critic Network: A separate network estimates the expected routing cost reduction achieved by the actor's policy. This provides a baseline and guides the actor's learning process through policy gradients.

The framework is trained using a combination of GCN, Transformer, and Pointer Network architectures, aiming to learn a policy that maximizes cumulative rewards, which are defined by minimizing routing cost (a weighted sum of wirelength, via count, and DRVs).

Datasets

The paper evaluates TREND on benchmarks from the ISPD-2018 and ISPD-2019 detailed routing contests. These are established datasets in the field, derived from real chip designs and featuring advanced design rules, making them representative of real-world challenges. The ISPD-2019 benchmarks are noted to be more challenging due to enhanced design rules.

Key Insights and Ideas

  • Learning Net Ordering is Crucial: The paper strongly emphasizes that the order of nets significantly impacts detailed routing outcomes, often more than the routing algorithm itself. Suboptimal ordering can lead to extensive rip-up and reroute cycles.
  • Transformer for Sequential Dependencies: The use of a Transformer architecture is effective in capturing the sequential nature of net ordering and the contextual relationships between nets, which is a novel application in this domain.
  • GCN for Spatial Relationships: Integrating GCNs allows the model to effectively encode the complex spatial overlaps and potential conflicts between nets, a critical factor often overlooked by previous methods.
  • Generalization from Small to Large Regions: The training strategy, which involves training on smaller regions first and then fine-tuning on larger ones, demonstrates the potential for learned policies to generalize to more complex scenarios.
  • RL for Complex Optimization: Reinforcement learning proves to be a powerful tool for tackling the combinatorial optimization problem of net ordering in detailed routing, outperforming heuristic-based methods in several aspects.

Key Results

  • Reduced DRVs and Routing Cost: TREND significantly reduces the number of design rule violations (DRVs) and the overall routing cost compared to both a baseline RL approach ("Lin's approach") and the state-of-the-art detailed router TritonRoute.
  • Comparable Wirelength and Via Count: While reducing DRVs and cost, TREND achieves comparable wirelength and via counts to existing methods.
  • Performance on Challenging Benchmarks: The framework shows particular strength on larger and more complex benchmarks, where traditional heuristics might struggle. For instance, it outperforms TritonRoute on several large test cases from the ISPD-2018 and ISPD-2019 contests.
  • Increased Runtime: The paper acknowledges that TREND incurs a higher runtime compared to TritonRoute, primarily due to the feature encoding and net order generation processes. However, it argues that the improved routing quality justifies this trade-off for complex designs.

Limitations and Future Work

  • Runtime for Large Benchmarks: The inference time for TREND on very large benchmarks is noted as a limitation. Future work will focus on optimizing this through novel representation learning techniques and action model learning.
  • Consistent Superiority: While TREND shows significant improvements, it doesn't consistently surpass TritonRoute's heuristic-based approach across all test cases. Future research will explore refining exploration precision with adaptive net selection constraints and improving solution quality through scaled-up training with extended episodes.
  • Adaptive Net Selection: The authors plan to investigate adaptive net selection constraints to improve routing precision.
  • Extended Training: Increasing training duration and coverage of more regions is suggested for better solution quality and convergence.

Summary updated

BibTeX
@inproceedings{zhou2025transformer,
  author = {Zhanwen Zhou and Hankz Hankui Zhuo and Jinghua Zhou and Wushao Wen},
  title = {{Transformer-based Reinforcement Learning for Net Ordering in Detailed Routing}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/1055},
}

Loading related content...

Figure