GPU-Parallel Routing
The idea
Routing looks sequential: nets are routed one after another, and a maze search settles one cell at a time. Both appearances are misleading, and GPU (Graphics Processing Unit) routing exploits the two hidden layers of parallelism:
A ring is all cells at the same distance from the source, and every cell in a ring relaxes its neighbours independently of the others. That independence is what enables the parallelism, and it changes what a "step" costs:
| model | what one step does | steps to reach the target |
|---|---|---|
| sequential (one CPU (Central Processing Unit) core) | settle one cell from the priority queue | one per settled cell: hundreds or thousands, most never on the path |
| ring-parallel (GPU (Graphics Processing Unit)) | relax every cell of the current ring at once, one thread per cell | one per ring, which is just the path length |
The work is identical; only the schedule changes. A search that settles hundreds of cells finishes in a few dozen parallel steps, and the wider the wavefront, the more threads are busy.
The second layer is across nets: nets whose regions do not overlap cannot conflict, so a batch of them routes in the same pass, with collisions detected afterwards and the losers re-queued, a speculative form of the standard rip-up discipline.
The recipe
Step 1 (parallel relaxation). Replace the priority queue with iterated sweeps: in each sweep, every frontier cell updates its neighbours simultaneously (GAMER's formulation). One sweep per ring.
Step 2 (batch nets). Partition the nets into batches of non-overlapping bounding regions; launch each batch as one GPU pass.
Step 3 (resolve speculatively). After a batch, detect nets whose routes collided on a resource, keep the winners, and re-queue the losers for the next batch at updated congestion prices, the PathFinder economics unchanged, only scheduled differently.
Watch it work: whose thread is each cell?
One net on a 30 x 20 grid with two walls, the same wave run twice. Sequentially, one thread owns every cell, one per step; on the GPU (Graphics Processing Unit), each frontier cell is colored by the thread that owns it, so a step's parallelism is countable. Then the net-batching axis and the current status. Every number is computed from the same wave.
Pros, cons, and the trade-off
Strengths
- Order-of-magnitude speedups reported on academic benchmarks against CPU (Central Processing Unit) global routers.
- The economics survive: PathFinder pricing works unchanged; only the schedule parallelizes.
- Rides hardware trends: routing inherits the GPU (Graphics Processing Unit) performance curve instead of the stalled single-thread curve.
Weaknesses
- Memory: a full-chip routing database strains GPU (Graphics Processing Unit) memory; academic results are on global routing's coarse graph, not the detailed rule deck.
- Speculation wastes work when batches collide heavily, exactly in the congested regions where routing is hard.
- Determinism: production flows demand run-to-run reproducibility, which parallel speculative schedules must be engineered to preserve.
The trade-off
GPU (Graphics Processing Unit) routing changes no answer, only the clock: the same negotiation, scheduled for thousands of threads. The research has settled that the core parallelism works; what remains between contest benchmarks and production is the full rule deck, the memory footprint, and determinism, which is engineering rather than algorithm.
Is it actually used today?
The evidence for GPU (Graphics Processing Unit) routing comes from academic contests and papers, not yet from production flows.
- Research: GAMER (GPU-accelerated maze routing) and the GPU global routers descended from it (FastGR, InstantGR) hold the recent ISPD (International Symposium on Physical Design) contest results with large speedups over CPU (Central Processing Unit) baselines.
- Production: inferred, not verified. Commercial routers advertise CPU parallelism (distributed and multi-threaded); vendor GPU (Graphics Processing Unit) claims so far center on analysis and simulation tools rather than the router itself.
- Open source: InstantGR is a fully open-source GPU (Graphics Processing Unit) global router with state-of-the-art contest results. OpenROAD's mainline routers remain CPU implementations; its GPU work so far is placement-side.