Anonymous: Constructing Rectilinear Minimum Steiner Tree via Reinforcement Learning
Hosted in Virtual Platform
Physical Design and Verification, Lithography and DFM
DescriptionRectilinear Steiner Minimum Tree (RSMT) is the shortest way to interconnect a net’s n pins using rectilinear edges only. Constructing the optimal RSMT is NP-complete and nontrivial. In this work, we design a neural network model for RSMT construction trained with reinforcement learning. After training, our algorithm constructs RSMT of <= 0.36% length error on average for nets with <= 50 pins. The average time needed to construct one net is fewer than 1.9ms, and is much faster than traditional heuristics of similar quality. This is also the first successful attempt to solve this problem using a machine learning approach.