Scholarlink

<p>As chip interconnect density increases, routing problems become increasingly complex. The routing scheme significantly impacts key performance indicators such as chip delay, power consumption, and area. In Very Large-Scale Integration (VLSI) routing, the rectilinear Steiner minimal tree is an excellent interconnect model for multi-pin nets. However, modern VLSI designs require multi-layer obstacle-avoiding routing, where wires must traverse multiple metal layers while avoiding obstacles to ensure connectivity and performance. This makes the Multi-Layer Obstacle-Avoiding Rectilinear Steiner Minimal Tree (ML-OARSMT) problem highly challenging in VLSI physical design. To address this issue, this paper proposes an ML-OARSMT construction algorithm based on deep reinforcement learning. First, a multi-layer obstacle-avoiding spanning graph is constructed by introducing vertex mapping, which connects different layers to handle the multi-layer obstacle-avoiding routing problem. Then, an agent is designed to learn edge selection for constructing the Multi-Layer Obstacle-Avoiding Steiner Tree (ML-OAST) using Double Deep Q-Network (DDQN). Finally, a post-processing stage is applied to further shorten the total wirelength through fast pruning and local optimization. Experimental results demonstrate that the proposed algorithm achieves better wirelength quality compared to state-of-the-art heuristic algorithms. Additionally, an ablation study confirms the effectiveness of DDQN in routing optimization.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Multi-layer obstacle-avoiding rectilinear steiner minimal tree algorithm based on deep reinforcement learning

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年8月21日

查看全文
  • Xing Huang,
  • Yuhan Zhu,
  • Yanbo Xu,
  • Yajun Xie,
  • Genggeng Liu

摘要

As chip interconnect density increases, routing problems become increasingly complex. The routing scheme significantly impacts key performance indicators such as chip delay, power consumption, and area. In Very Large-Scale Integration (VLSI) routing, the rectilinear Steiner minimal tree is an excellent interconnect model for multi-pin nets. However, modern VLSI designs require multi-layer obstacle-avoiding routing, where wires must traverse multiple metal layers while avoiding obstacles to ensure connectivity and performance. This makes the Multi-Layer Obstacle-Avoiding Rectilinear Steiner Minimal Tree (ML-OARSMT) problem highly challenging in VLSI physical design. To address this issue, this paper proposes an ML-OARSMT construction algorithm based on deep reinforcement learning. First, a multi-layer obstacle-avoiding spanning graph is constructed by introducing vertex mapping, which connects different layers to handle the multi-layer obstacle-avoiding routing problem. Then, an agent is designed to learn edge selection for constructing the Multi-Layer Obstacle-Avoiding Steiner Tree (ML-OAST) using Double Deep Q-Network (DDQN). Finally, a post-processing stage is applied to further shorten the total wirelength through fast pruning and local optimization. Experimental results demonstrate that the proposed algorithm achieves better wirelength quality compared to state-of-the-art heuristic algorithms. Additionally, an ablation study confirms the effectiveness of DDQN in routing optimization.