A Reinforcement Learning Agent for Obstacle-Avoiding Rectilinear Steiner Tree Construction

Po Yan Chen, Bing Ting Ke, Tai Cheng Lee, I. Ching Tsai, Tai Wei Kung, Li Yi Lin, En Cheng Liu, Yun Chih Chang, Yih Lang Li, Mango C.T. Chao

研究成果: Conference contribution同行評審

摘要

This paper presents a router, which tackles a classic algorithm problem in EDA, obstacle-avoiding rectilinear Steiner minimum tree (OARSMT), with the help of an agent trained by our proposed policy-based reinforcement-learning (RL) framework. The job of the policy agent is to select an optimal set of Steiner points that can lead to an optimal OARSMT based on a given layout. Our RL framework can iteratively upgrade the policy agent by applying Monte-Carlo tree search to explore and evaluate various choices of Steiner points on various unseen layouts. As a result, our policy agent can be viewed as a self-designed OARSMT algorithm that can iteratively evolves by itself. The initial version of the agent is a sequential one, which selects one Steiner point at a time. Based on the sequential agent, a concurrent agent can then be derived to predict all required Steiner points with only one model inference. The overall training time can be further reduced by applying geometrically symmetric samples for training. The experimental results on single-layer 15x15 and 30x30 layouts demonstrate that our trained concurrent agent can outperform a state-of-the-art OARSMT router on both wire length and runtime.

原文English
主出版物標題ISPD 2022 - Proceedings of the 2022 International Symposium on Physical Design
發行者Association for Computing Machinery
頁面107-115
頁數9
ISBN(電子)9781450392105
DOIs
出版狀態Published - 13 4月 2022
事件31st ACM International Symposium on Physical Design, ISPD 2022 - Virtual, Online, Canada
持續時間: 27 3月 202230 3月 2022

出版系列

名字Proceedings of the International Symposium on Physical Design

Conference

Conference31st ACM International Symposium on Physical Design, ISPD 2022
國家/地區Canada
城市Virtual, Online
期間27/03/2230/03/22

指紋

深入研究「A Reinforcement Learning Agent for Obstacle-Avoiding Rectilinear Steiner Tree Construction」主題。共同形成了獨特的指紋。

引用此