Attention Routing: track-assignment detailed routing using attention-based reinforcement learning

• URL: http://arxiv.org/abs/2004.09473v2
• Date: Fri, 22 May 2020 20:44:33 GMT
• Title: Attention Routing: track-assignment detailed routing using attention-based reinforcement learning
• Authors: Haiguang Liao, Qingyi Dong, Xuliang Dong, Wentai Zhang, Wangyang Zhang, Weiyi Qi, Elias Fallon, Levent Burak Kara
• Abstract summary: 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.
• Score: 0.23453441553817037
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the physical design of integrated circuits, global and detailed routing are critical stages involving the determination of the interconnected paths of each net on a circuit while satisfying the design constraints. Existing actual routers as well as routability predictors either have to resort to expensive approaches that lead to high computational times, or use heuristics that do not generalize well. Even though new, learning-based routing methods have been proposed to address this need, requirements on labelled data and difficulties in addressing complex design rule constraints have limited their adoption in advanced technology node physical design problems. In this work, we propose a new router: attention router, which is the first attempt to solve the track-assignment detailed routing problem using reinforcement learning. Complex design rule constraints are encoded into the routing algorithm and an attention-model-based REINFORCE algorithm is applied to solve the most critical step in routing: sequencing device pairs to be routed. The attention router and its baseline genetic router are applied to solve different commercial advanced technologies analog circuits problem sets. The attention router demonstrates generalization ability to unseen problems and is also able to achieve more than 100 times acceleration over the genetic router without significantly compromising the routing solution quality. We also discover a similarity between the attention router and the baseline genetic router in terms of positive correlations in cost and routing patterns, which demonstrate the attention router's ability to be utilized not only as a detailed router but also as a predictor for routability and congestion.

Related papers

• AlphaRouter: Quantum Circuit Routing with Reinforcement Learning and Tree Search [14.46041554295883]
  This paper introduces a solution that integrates Monte Carlo Tree Search (MCTS) with Reinforcement Learning (RL) Our router, called Alpha RL, outperforms the current state-of-the-art routing methods and generates quantum programs with up to $20%$ less routing overhead.
  arXiv  Detail & Related papers  (2024-10-07T15:10:54Z)
• An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem [67.92544792239086]
  We introduce an NN-based solver to significantly narrow the gap with advanced metaheuristics. First, we propose direction-aware facilitating attention model (DaAM) to incorporate directionality into the embedding process. Second, we design a supervised reinforcement learning scheme that involves supervised pre-training to establish a robust initial policy.
  arXiv  Detail & Related papers  (2024-03-11T02:17:42Z)
• Genetic Algorithms with Neural Cost Predictor for Solving Hierarchical Vehicle Routing Problems [20.684353068460375]
  When vehicle routing decisions are intertwined with higher-level decisions, the resulting optimization problems pose significant challenges for computation. We propose a novel deep-learning-based approach called Genetic Algorithm with Neural Cost Predictor (GANCP) to tackle the challenge. In particular, our proposed neural network learns the objective values of the HGS-CVRP open-source package that solves capacitated vehicle routing problems.
  arXiv  Detail & Related papers  (2023-10-22T02:46:37Z)
• Towards Machine Learning for Placement and Routing in Chip Design: a Methodological Overview [72.79089075263985]
  Placement and routing are two indispensable and challenging (NP-hard) tasks in modern chip design flows. Machine learning has shown promising prospects by its data-driven nature, which can be of less reliance on knowledge and priors.
  arXiv  Detail & Related papers  (2022-02-28T06:28:44Z)
• Fidelity-Guarantee Entanglement Routing in Quantum Networks [64.49733801962198]
  Entanglement routing establishes remote entanglement connection between two arbitrary nodes. We propose purification-enabled entanglement routing designs to provide fidelity guarantee for multiple Source-Destination (SD) pairs in quantum networks.
  arXiv  Detail & Related papers  (2021-11-15T14:07:22Z)
• Deep Reinforcement Learning Aided Packet-Routing For Aeronautical Ad-Hoc Networks Formed by Passenger Planes [99.54065757867554]
  We invoke deep reinforcement learning for routing in AANETs aiming at minimizing the end-to-end (E2E) delay. A deep Q-network (DQN) is conceived for capturing the relationship between the optimal routing decision and the local geographic information observed by the forwarding node. We further exploit the knowledge concerning the system's dynamics by using a deep value network (DVN) conceived with a feedback mechanism.
  arXiv  Detail & Related papers  (2021-10-28T14:18:56Z)
• 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)
• Road Network Guided Fine-Grained Urban Traffic Flow Inference [108.64631590347352]
  Accurate inference of fine-grained traffic flow from coarse-grained one is an emerging yet crucial problem. We propose a novel Road-Aware Traffic Flow Magnifier (RATFM) that exploits the prior knowledge of road networks. Our method can generate high-quality fine-grained traffic flow maps.
  arXiv  Detail & Related papers  (2021-09-29T07:51:49Z)
• Packet Routing with Graph Attention Multi-agent Reinforcement Learning [4.78921052969006]
  We develop a model-free and data-driven routing strategy by leveraging reinforcement learning (RL) Considering the graph nature of the network topology, we design a multi-agent RL framework in combination with Graph Neural Network (GNN)
  arXiv  Detail & Related papers  (2021-07-28T06:20:34Z)
• Track-Assignment Detailed Routing Using Attention-based Policy Model With Supervision [0.27998963147546135]
  We propose a machine learning driven method for solving the track-assignment detailed routing problem. Our approach adopts an attention-based reinforcement learning (RL) policy model. We show that especially for complex problems, our supervised RL method provides good quality solution.
  arXiv  Detail & Related papers  (2020-10-26T16:40:11Z)
• Circuit Routing Using Monte Carlo Tree Search and Deep Neural Networks [1.987599364275123]
  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.
  arXiv  Detail & Related papers  (2020-06-24T10:34:57Z)

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.