Scalable GPU-Friendly Parallelization for Sweep-Based Maze Routing

Cheng-Yu Chiang

doi:10.1109/tcad.2026.3737066

Scalable GPU-Friendly Parallelization for Sweep-Based Maze Routing

2026-09-23

0

PRE

AI

DOI：10.1109/tcad.2026.3737066

Original

Original request for help

Save

Abstract

En 中文

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-and-reroute technique that selectively reroutes only overflowed segments, preserving feasible parts of the solution to reduce runtime substantially. Experimental results on the latest ICCAD’19 Contest benchmarks demonstrate that our GPU-friendly maze routing with sweep sharing can significantly improve the efficiency of the state-of-the-art GPU-accelerated maze router.

Keywords:

Physical Design

GPU-Acceleration

Global Routing

Maze Routing

Scalable GPU-Friendly Parallelization for Sweep-Based Maze Routing

Abstract

Journal

Organization

Cited Papers