Abstract

Given a set of pins and obstacles in a Very-Large-Scale Integration (VLSI) chip layout, the goal is to develop an optimal routing path with minimal wire length. This work construct Obstacle Avoidance Rectilinear Steiner Minimal Tree (OARSMT) using a deep Q-learning approach, a type of reinforcement learning. It employs union-find data structure, parallel Deep Q-Network and Adam optimizer to train an agent to determine the optimal connection between pins. The DQN approximates Q-values, which reflect the likelihood of selecting an edge. Connections with higher Q-values are those that are obstacle-free, have lower weight values, and favors connections that share common paths. The DQN takes the help Kruskal’s algorithm to construct a rectilinear steiner tree with the above connection constraints. The approach uses multi-threading during the training to handle large datasets. The proposed model returns shorter wire lengths with improvement of 5% for obstacle-based benchmark data. The model also achieves 9.8% less training time on an average due to the parallelization of the DQN. The proposed approach realizes an 85.3 % increase in reward gain than other approaches. The developed method achieved the objective and can attain superior performance not only in VLSI physical design but also in various obstacle based routing.

Authors

Chittaranjan Mohapatra, Nibedita Adhikari
Utkal University, India

Keywords

Deep Reinforcement Learning, Adam Optimizer, OARSMT, VLSI, Physical Design and Routing