Circuit Routing Using Monte Carlo Tree Search and Deep Neural Networks

• URL: http://arxiv.org/abs/2006.13607v1
• Date: Wed, 24 Jun 2020 10:34:57 GMT
• Title: Circuit Routing Using Monte Carlo Tree Search and Deep Neural Networks
• Authors: Youbiao He, Forrest Sheng Bao
• Abstract summary: We model the circuit routing as a sequential decision-making problem, and solve it by Monte Carlo tree search (MCTS) with deep neural network (DNN) guided rollout. Experiments on randomly generated single-layer circuits show the potential to route complex circuits. The proposed approach can solve the problems that benchmark methods such as sequential A* method and Lee's algorithm cannot solve, and can also outperform the vanilla MCTS approach.
• Score: 1.987599364275123
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Circuit routing is a fundamental problem in designing electronic systems such as integrated circuits (ICs) and printed circuit boards (PCBs) which form the hardware of electronics and computers. Like finding paths between pairs of locations, circuit routing generates traces of wires to connect contacts or leads of circuit components. It is challenging because finding paths between dense and massive electronic components involves a very large search space. Existing solutions are either manually designed with domain knowledge or tailored to specific design rules, hence, difficult to adapt to new problems or design needs. Therefore, a general routing approach is highly desired. In this paper, we model the circuit routing as a sequential decision-making problem, and solve it by Monte Carlo tree search (MCTS) with deep neural network (DNN) guided rollout. It could be easily extended to routing cases with more routing constraints and optimization goals. Experiments on randomly generated single-layer circuits show the potential to route complex circuits. The proposed approach can solve the problems that benchmark methods such as sequential A* method and Lee's algorithm cannot solve, and can also outperform the vanilla MCTS approach.

Related papers

• AICircuit: A Multi-Level Dataset and Benchmark for AI-Driven Analog Integrated Circuit Design [10.354863964933019]
  We present AICircuit, a benchmark for developing and evaluating machine learning algorithms in analog and radio-frequency circuit design. A major obstacle for bearing the power of machine learning in circuit design is the availability of a generic and diverse dataset. We extensively evaluate various ML algorithms on the dataset, revealing the potential of ML algorithms in learning the mapping from the design specifications to the desired circuit parameters.
  arXiv  Detail & Related papers  (2024-07-22T20:32:16Z)
• Finding Transformer Circuits with Edge Pruning [71.12127707678961]
  We propose Edge Pruning as an effective and scalable solution to automated circuit discovery. Our method finds circuits in GPT-2 that use less than half the number of edges compared to circuits found by previous methods. Thanks to its efficiency, we scale Edge Pruning to CodeLlama-13B, a model over 100x the scale that prior methods operate on.
  arXiv  Detail & Related papers  (2024-06-24T16:40:54Z)
• CktGNN: Circuit Graph Neural Network for Electronic Design Automation [67.29634073660239]
  This paper presents a Circuit Graph Neural Network (CktGNN) that simultaneously automates the circuit topology generation and device sizing. We introduce Open Circuit Benchmark (OCB), an open-sourced dataset that contains $10$K distinct operational amplifiers. Our work paves the way toward a learning-based open-sourced design automation for analog circuits.
  arXiv  Detail & Related papers  (2023-08-31T02:20:25Z)
• Adaptive Planning Search Algorithm for Analog Circuit Verification [53.97809573610992]
  We propose a machine learning (ML) approach, which uses less simulations. We show that the proposed approach is able to provide OCCs closer to the specifications for all circuits.
  arXiv  Detail & Related papers  (2023-06-23T12:57:46Z)
• Efficient Quantum Circuit Design with a Standard Cell Approach, with an Application to Neutral Atom Quantum Computers [45.66259474547513]
  We design quantum circuits by using the standard cell approach borrowed from classical circuit design. We present evidence that, when compared with automatic routing methods, our layout-aware routers are significantly faster and achieve shallower 3D circuits.
  arXiv  Detail & Related papers  (2022-06-10T10:54:46Z)
• Ranking Cost: Building An Efficient and Scalable Circuit Routing Planner with Evolution-Based Optimization [49.207538634692916]
  We propose a new algorithm for circuit routing, named Ranking Cost, to form an efficient and trainable router. In our method, we introduce a new set of variables called cost maps, which can help the A* router to find out proper paths. Our algorithm is trained in an end-to-end manner and does not use any artificial data or human demonstration.
  arXiv  Detail & Related papers  (2021-10-08T07:22:45Z)
• On the realistic worst case analysis of quantum arithmetic circuits [69.43216268165402]
  We show that commonly held intuitions when designing quantum circuits can be misleading. We show that reducing the T-count can increase the total depth. We illustrate our method on addition and multiplication circuits using ripple-carry.
  arXiv  Detail & Related papers  (2021-01-12T21:36:16Z)
• Using Reinforcement Learning to Perform Qubit Routing in Quantum Compilers [0.0]
  We propose a qubit routing procedure that uses a modified version of the deep Q-learning paradigm. The system is able to outperform the qubit routing procedures from two of the most advanced quantum compilers currently available.
  arXiv  Detail & Related papers  (2020-07-31T10:57:24Z)
• Attention Routing: track-assignment detailed routing using attention-based reinforcement learning [0.23453441553817037]
  We propose a new router: attention router, which is the first attempt to solve the track-assignment detailed routing problem using reinforcement learning. The attention router and its baseline genetic router are applied to solve different commercial advanced technologies analog circuits problem sets.
  arXiv  Detail & Related papers  (2020-04-20T17:50:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.