Reinforcement and supervised learning for combinatorial problems in electronics design automation

Electronic Design Automation (EDA) software automates the IC design process and increases the design efficiency and capabilities. With the scaling of semiconductor technologies, the importance of EDA has rapidly increased. At the heart of most EDA design problems are combinatorial optimization problems, which are usually solved with heuristics, or analytical method in classical methods. Owing to the increasing difficulties of the EDA problems and demand for EDA tools designing increasingly complicated electronic systems, classical EDA algorithms are struggling to keep up with the ever more challenging EDA design tasks. Thus, better and more efficient EDA solutions are urgently needed to address the challenge. In recent years, there have been some major development in the field of machine learning, especially in (deep) reinforcement learning. Recent success of reinforcement learning has been demonstrated in fields including robotics, games as well as combinatorial optimization problems. This motivates us to explore the possibility of applying machine learning specifically reinforcement learning to come up with better EDA algorithms.In this research, we propose new algorithms to solve combinatorial problems in EDA based on reinforcement learning and supervised learning. To achieve this, we identified two research objectives. The first one is to developing reinforcement learning algorithms for solving EDA routing problems that performs better and more efficient than the current EDA routing solutions. Under this research objective, we propose three technical goals: (1) DQN Global Routing that solves global routing with Deep Q-learning; (2) Attention Routing that solves detailed routing with attention-based reinforcement learning; (3) Spectral DQN Routing that solves generic EDA routing and obstacle avoiding routing with combination of DQN and spectral method. Our proposed RL-based routing solutions provide better and more efficient alternatives compared with existing routing solutions.

The second research objective is to develop machine-learning-based algorithm for automatic 2D space partitioning generation with island minimization objective. To achieve this, we propose the GOMLP algorithm that solves the power plane generation with supervised learning. The power plane generation, as an instance of space partitioning generation with island minimization objective has no readily available algorithms to solve. Our proposed method is the first successful attempt in developing automatic power plane generation algorithms by leveraging supervised learning. We also extend the GOMLP to solve multilayer power plane generation problems with the H-GOMLP that combines GOMLP with hierarchical clustering method.