GoSteiner: Constructing Rectilinear Steiner Minimum Tree on Directed Graph

The Rectilinear Steiner Minimum Tree (RSMT) problem is a key issue in the back-end physical design of integrated circuits (ICs), which directly affects the quality of the routing. In this work, we formulate the RSMT problem as a sequential decision problem to develop an Actor-Critic reinforcement learning framework named GoSteiner. We utilize a directed graph representation method called GST for RSMT. Additionally, we introduce the Delaunay triangulation graph (DT) and sequentially construct GST on DT to solve the RSMT problem. An edge-aware graph attention network (EGAT) is designed to effectively encode the DT graph and the GST, while a transformer-based decoder is built to output policy. Furthermore, we propose a heuristic method to break high-degree nets (> 50 degrees). This approach fully leverages the critic’s ability to accurately estimate the wirelength of nets, significantly enhancing the quality and efficiency in high-degree nets construction. Experimental results demonstrate that compared with the exact algorithm GeoSteiner, GoSteiner only introduces \(≤ {0.24}% \) wirelength error on the ISPD18/19 benchmarks with million of nets. Meanwhile, the runtime for net within 500 pins is less than 62.37 ms .