MCMC-Escape: Multi-Capacity Ordered Escape Routing Based on Monte-Carlo Tree Search

Ordered escape routing (OER), which seeks the routing paths from some signal pins to the boundary of a pin array in a given order, is an important research topic for PCB design. Although reinforcement learning based methods for OER have been proposed, the routing capacity between two adjacent pins is assumed to be just one. In this work, we propose MCMC-Escape, a Monte-Carlo tree search (MCTS) based multi-capacity ordered escape router, which includes, in turn, the initial solving approach, the improved Monte-Carlo tree search (improved MCTS) process, and the last routing attempt approach based on wires removing and re-routing. In the improved MCTS, the prior knowledge based pruning strategies and the fine-tuning strategy are proposed to enhance the efficiency of solving multi-capacity OER (MC-OER) problems, while the weight adjusting strategy is proposed to address the path occupancy issues arising from multiple capacity. Experimental results demonstrate that MCMC-Escape can effectively solve large-scale MC-OER problems and outperform existing methods in terms of routing success rate, runtime and wire length. For a set of problems with 50×50 pin array, MCMC-Escape achieves 4X higher success rate of routing with 50% less solving time than MCMCF-Router [
1
], while reducing the average total wire length.