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%.
Copyright by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or firstname.lastname@example.org. The definitive version of this paper can be found at ACM's Digital Library http://www.acm.org/dl/.