Unified deep reinforcement learning approach for constructing rectilinear and octilinear steiner minimum trees

Abstract

Disclosed is a unified deep reinforcement learning approach for constructing rectilinear and octilinear Steiner minimum trees in the technical field of computer-aided design of integrated circuits, the method including designing an edge point sequence (EPS) based on structural characteristics of a Steiner minimum tree (SMT) to bridge a gap between deep learning model output and an SMT structure; designing a deep learning model for the EPS, and using a negative wirelength of the SMT as a reward to train the deep learning model through the deep reinforcement learning (DRL); providing a corresponding fast and accurate wirelength computation algorithm for a quality assessment of construction solutions to accelerate training of the deep learning model; and constructing diversified construction solutions of SMTs utilizing the stochastic nature of machine learning. The method of the present invention can solve rectilinear Steiner minimum tree (RSMT) and octilinear Steiner minimum tree (OSMT) problems and generate diversified routing topologies.

Dependencies are inferred from the claim text.