To Rip or not to Rip: A Reinforcement Learning-based Rip-up and Reroute Algorithm for Global Routing
Routing, including global routing and detailed routing, has been a critical step in the design of integrated circuits. Most of the existing global routers will firstly use techniques like pattern routing and layer assignment to quickly generate a routing solution and optimize total wirelength and via usage. Then rip-up and reroute (RRR) scheme will be applied to iteratively reduce the number of overflows in the whole design. However, compared with initial routing stage, RRR will be much more time consuming. It will rip up all the nets that pass through overflowed area and reroute them sequentially. Even if the routing resources in one routing cell is overused by 1, the router will rip up all the nets that are routed on the routing cell, as it does not know which net will be the best choice to rip up. In this way, RRR may be doing a lot of redundant work. Besides, some initial routing solutions that are optimal in terms of wirelength will also be wasted when they are ripped up, causing a loss of routing quality. Therefore, in this project, we propose to use reinforcement learning to help decide which nets to rip up in each RRR iterations. An actor-critic based Proximal Policy Optimization (PPO) agent is trained for this task. Experimental results show that the proposed approach can successfully reduce the number of rerouted nets with little loss of routing quality on the ICCAD’19 global routing contest benchmarks, which demonstrate the effectiveness of our model.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Reroute, Don't Remove: Recoverable Visual Token Routing for Vision-Language Models
Vision-language models (VLMs) project images into hundreds to thousands of visual tokens, making decoder inference expensive in both attention computation and KV-cache memory. Existing visual-token reduction methods larg…
SecureRouter: Encrypted Routing for Efficient Secure Inference
Cryptographically secure neural network inference typically relies on secure computing techniques such as Secure Multi-Party Computation (MPC), enabling cloud servers to process client inputs without decrypting them. Alt…
CFR-RL: Traffic Engineering with Reinforcement Learning in SDN
Traditional Traffic Engineering (TE) solutions can achieve the optimal or near-optimal performance by rerouting as many flows as possible. However, they do not usually consider the negative impact, such as packet out of …
Reinforcement LearningReinforcement Learning (RL)Reroute Prediction Service
The cost of delays was estimated as 33 billion US dollars only in 2019 for the US National Airspace System, a peak value following a growth trend in past years. Aiming to address this huge inefficiency, we designed and d…
PredictionAlphaRoute: Large Language Models as Semantic Optimizers for Multi-Objective Routing
Very Large Scale Integration (VLSI) global routing is an NP-hard combinatorial optimization problem requiring signal net assignment across capacity-constrained 3D grids while minimizing congestion, wirelength, and via tr…