Indexed by:
Abstract:
The Steiner Minimum Tree (SMT) serves as an optimal connection model for multi-terminal nets in Very Large Scale Integration (VLSI). Constructing both Rectilinear Steiner Minimum Tree (RSMT) and Octilinear Steiner Minimum Tree (OSMT) are known to be NP-hard problems. Simultaneously, constructing multiple topologies of SMTs for a given net holds significant importance in alleviating routing constraints such as alleviating congestion and ensuring timing convergence. However, existing efforts predominantly focus on designing specialized methods to construct a specifically structured SMT for a given net, making it challenging to extend to different structures or topologies of SMTs, while also exhibiting insufficient optimization capabilities. In this work, we propose a unified approach based on Deep Reinforcement Learning (DRL) to address both RSMT and OSMT problems while generating diverse routing topologies. First, we design an Edge Point Sequence (EPS) that leverages the structural characteristics of SMT to connect the output of the deep learning model with the SMT structure. Second, we propose a deep learning model tailored for EPS, employing the negative wirelength of SMT as a reward to train the model using DRL. Third, we provide a corresponding rapid and accurate wirelength computation algorithm for evaluating the quality of the construction solution to expedite model training. Finally, we leverage the stochastic nature of machine learning to construct diverse SMT construction solutions. To the best of our knowledge, this is the first unified approach capable of simultaneously addressing both RSMT and OSMT problems while generating diverse solutions. The proposed unified approach demonstrates superior solution quality and higher efficiency compared to specifically designed algorithms. © 1982-2012 IEEE.
Keyword:
Reprint 's Address:
Email:
Source :
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
ISSN: 0278-0070
Year: 2024
2 . 7 0 0
JCR@2023
CAS Journal Grade:3
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 0
Affiliated Colleges: