REST: Revolutionizing Steiner Tree Problem Solving in Chip Routing with Deep Learning

REST is an open-source implementation based on the paper by Liu J. et al (2021). It uses neural networks to solve the Steiner tree routing problem in VLSI design, significantly improving computation speed while maintaining accuracy comparable to traditional algorithms, and providing a new direction for the intelligentization of Electronic Design Automation (EDA) tools.

The Steiner tree problem is a combinatorial optimization problem: given planar pin points, connect them to minimize the total wire length (allowing the introduction of Steiner points to optimize the topology). In VLSI design, it directly affects signal delay, power consumption, routing resources, and chip area. Traditional solutions like the FLUTE and Borah algorithms balance between accuracy and speed.

The core idea of REST is to use neural networks to directly predict the Steiner tree topology and wire length, adopting an encoder-decoder architecture: the encoder encodes pin coordinates into fixed vectors, and the decoder generates the tree structure (similar to neural machine translation). Training is performed on point sets with n=3 to 25, with dynamic batch size adjustment, and takes approximately 6 hours to complete on an RTX4070.

Wire Length Accuracy: Compared to the Borah algorithm, 17 out of 23 scales are better, with an average wire length reduction of 0.74%; compared to FLUTE(A=3), 17 out of 23 scales are better, with a reduction of 0.42%; compared to FLUTE(A=18), only 2 out of 23 scales are better, with an increase of 0.61%. Speed: REST is comparable to FLUTE(A=18) (about 0.85ms for 25 points), much faster than Borah (2400ms for 25 points), and its accuracy is close to FLUTE(A=3).

1. Fast routing estimation: quickly evaluate routing costs during the placement phase; 2. Congestion prediction and optimization: identify congested areas to guide placement; 3. Design space exploration: high-throughput screening of candidate design schemes.

Current limitations: only supports up to 25 points, does not handle obstacles, and only addresses 2D problems. Future directions: divide-and-conquer strategy to solve large-scale problems, support obstacle handling, and extend to multi-layer routing.

REST demonstrates the application potential of machine learning in the traditional EDA field, proving that neural networks can solve structured combinatorial optimization problems. It provides engineers with fast and accurate tools, offers researchers a case of theory-to-application conversion, and indicates that AI-driven EDA tools may break through the bottlenecks of traditional algorithms.