TY - GEN
T1 - NeuroEscape
T2 - 42nd IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2023
AU - Chen, Zhiyang
AU - Ho, Tsung Yi
AU - Schlichtmann, Ulf
AU - Chen, Datao
AU - Liu, Mingyu
AU - Yao, Hailong
AU - Yin, Xia
N1 - Publisher Copyright:
© 2023 IEEE.
PY - 2023
Y1 - 2023
N2 - Ordered escape routing is a critical stage for printed circuit board design. State-of-the-art solutions to ordered escape routing are either heuristic and non-optimal, or trapped in exponential time complexity. In this work, for the first time, we prove that ordered escape routing is not only NP-hard, but also hard to approximate in polynomial time, indicating the limitation of optimal algorithms. We further present NeuroEscape, an efficient ordered escape routing method, which is based on reinforcement learning with a Monte-Carlo tree search (MCTS) and heuristic rollouts for design space exploration. A neural policy model is incorporated to further enhance the MCTS process. Theoretical results show that the number of samples required to train the model is upper bounded by a polynomial. Experimental results show that NeuroEscape solves 69% more testcases, with an average acceleration of 19.4x compared with state-of-the-art methods.
AB - Ordered escape routing is a critical stage for printed circuit board design. State-of-the-art solutions to ordered escape routing are either heuristic and non-optimal, or trapped in exponential time complexity. In this work, for the first time, we prove that ordered escape routing is not only NP-hard, but also hard to approximate in polynomial time, indicating the limitation of optimal algorithms. We further present NeuroEscape, an efficient ordered escape routing method, which is based on reinforcement learning with a Monte-Carlo tree search (MCTS) and heuristic rollouts for design space exploration. A neural policy model is incorporated to further enhance the MCTS process. Theoretical results show that the number of samples required to train the model is upper bounded by a polynomial. Experimental results show that NeuroEscape solves 69% more testcases, with an average acceleration of 19.4x compared with state-of-the-art methods.
KW - Monte-Carlo tree search
KW - Neural network
KW - Ordered escaped routing
UR - http://www.scopus.com/inward/record.url?scp=85181403639&partnerID=8YFLogxK
U2 - 10.1109/ICCAD57390.2023.10323718
DO - 10.1109/ICCAD57390.2023.10323718
M3 - Conference contribution
AN - SCOPUS:85181403639
T3 - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
BT - 2023 42nd IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2023 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 28 October 2023 through 2 November 2023
ER -