Late Breaking Results: Scalable GPU-Friendly Parallelization for Sweep-Based Maze Routing
Cheng-Yu Chiang, Zong-Ying Cai, Chao-Chi Lan, Yan-Jen Chen, Yang Hsu, Yao‐Wen Chang, Hung-Ming Chen · 2025
Global routing is a critical stage in the VLSI design flow, aiming to provide a robust guide for detailed routing and serve as early design feedback for placement. Many approaches have leveraged GPU parallelization to achieve significant acceleration. However, with the fast-growing complexity of modern large-scale designs, recent GPU-accelerated maze routing algorithms, driven by the sweep operation, struggle to find solutions efficiently with limited GPU memory resources. In order to address this issue, this paper proposes a scalable, GPU-friendly sweep-based maze routing that requires significantly less memory and fewer kernel function calls while accelerating overall runtime. We introduce a sweep-sharing technique that allows multiple nets to be routed simultaneously within a single sweeping process, substantially reducing memory consumption and kernel launching overhead. We further propose an edge-level rip-up-andreroute technique that selectively reroutes only overflowed segments, preserving feasible parts of the solution to reduce runtime substantially. Experimental results on the latest ISPD’24 Contest benchmarks demonstrate that our GPUfriendly maze routing with sweep sharing can significantly improve the efficiency of the state-of-the-art GPU-accelerated maze router.