Machine Learning based Circuit Routing
Routing is a problem in Electronics Design Automation (EDA), which sits as the intersection of Electrical Engineering and Computer Science. It is more challenging than path finding in other domains, such as robotics, in that paths cannot intersect in circuit routing – so a greedy, optiomal path can make a solution globally suboptimal or even invalid. An example is given below (from Kahng et al., VLSI Physical Design, 2nd edition, 2022)
Conventionally, circuit routing is done using heuristics. Such algorithms need to be manually designed and maintained. This is laborious and hard, especially after the (corner) cases explode. As believers of Machine Learning, we wanna teach computers to route circuits by learning. This great dream of science has great practical and commercial potentials. We are “dumping” different machine learning techniques onto it: reinforcement learning, computer vision, and even NLP.
Our efforts
- Heatmap Router: An encoder-decoder approach to PCB routing, MS Report, Zachary Johnson, 2022, to be published by ISU library
- Circuit Routing Using Monte Carlo Tree Search and Deep Neural Networks, arXiv
- Circuit Routing Using Monte Carlo Tree Search and Deep Reinforcement Learning, 2022 IEEE VLSI-DAT
Recent, important papers
On Using ML for routing (unfortunately, none of them made to top EDA/AI conferences.)
- Yihao Zhang, DEEP REINFORCEMENT LEARNING ON 1-LAYER CIRCUIT ROUTING PROBLEM, MS Thesis, UIUC, 2018
- A Deep Reinforcement Learning Approach for Global Routing, CMU ME, 2019, which is like the first paper on using Reinforcement Learning for circuit routing
- ATTENTION ROUTING: TRACK-ASSIGNMENT DETAILED ROUTING USING ATTENTION-BASED REINFORCEMENT LEARNING, 2020
- Track-Assignment Detailed Routing Using Attention-based Policy Model With Supervision
- Ranking Cost, arXiv, 2021, Reviews for this paper in ICLR 2021 are worth reading. It was rejected.
On more conventional approaches (from top EDA confs.)
- A Unified Printed Circuit Board Routing Algorithm With Complicated Constraints and Differential Pairs, ASP-DAC 2021
- A Complete PCB Routing Methodology with Concurrent Hierarchical Routing, DAC 2021
Routers
Tutorials
Books
- Kahng et al., VLSI Physical Design, 1st edition, 2011
- Kahng et al., VLSI Physical Design, 2nd edition, 2022
- Alpert et al., Handbook of Algorithms for Physical Design Automation, 2009
Figures
- Dr. Chung-Kuan Cheng, UCSD
- Dr. Yi-Lang Li, National Chiao Tung University, Taiwan
- Haiguang Liao, CMU
Open source projects
- Google Circuit Training This project is more on placement than training
- OpenROAD PCB Router, UCSD