Close

Presentation

Anonymous: Constructing Rectilinear Minimum Steiner Tree via Reinforcement Learning
Time
Location
Event Type
Research Manuscript
Virtual Programs
Hosted in Virtual Platform
Keywords
Physical Design and Verification, Lithography and DFM
Topics
EDA
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.