Standard Cell Routing with Reinforcement Learning and Genetic Algorithm in Advanced Technology Nodes

Automated standard cell routing in advanced technology nodes with unidirectional metal are challenging because of the constraints of exploding design rules. Previous approaches leveraged mathematical optimization methods such as SAT and MILP to find optimum solution under those constraints. The assumption those methods relied on is that all the design rules can be expressed in the optimization framework and the solver is powerful enough to solve them. In this paper we propose a machine learning based approach that does not depend on this assumption. In our approach, we apply genetic algorithm to create initial routing candidates and use Reinforcement Learning (RL) to fix the design rule violations incrementally. Our approach does not need to formulate each design rule constraints in a mathematical framework, instead, a design rule checker feedbacks the violations to the RL agent and the agent learns how to fix them based on the data. This approach is more adaptable to future technologies and potentially more scalable than the mathematical optimization approaches. We also implement a grid based layout environment called Stick, which can generate layout data from the grid-based assignment from our router. We demonstrate the effectiveness of our approach on a number of standard cells. We have shown that it can route a cell which is deemed unroutable manually, reducing the cell size by 11%.