GAMER: GPU-Accelerated Maze Routing

Shiju Lin*, Jinwei Liu, Evangeline F.Y. Young, Martin D. F. Wong

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

8 Citations (Scopus)

Abstract

Maze routing is usually the most time-consuming step in global routing and detailed routing. A commonly used maze routing method is to start from one pin and iteratively connect the current route to the closest unconnected pin. This method reduces the maze routing problem to multiple multisource-multidestination shortest path problems. The shortest path problem in VLSI routing has: 1) rectilinear routing directions and 2) preferably small via usage. By utilizing these two characteristics, we propose a novel parallel algorithm called GAMER to accelerate the multisource-multidestination shortest path problem for VLSI routing. GAMER decomposes the shortest path search into alternating vertical and horizontal sweep operations, and two parallel algorithms are proposed to accelerate a sweep operation from O(n2) to O(log2n) on a grid graph of n×n. Several techniques of applying GAMER on irregular routing regions are also introduced. Experiments are conducted by integrating GAMER into the state-of-the-art academic global router CUGR. CUGR adopts a two-level maze routing scheme, including coarse-grained routing and fine-grained routing, and they can be accelerated by 19.85× and 2.59×, respectively, with GAMER, achieving an overall speedup of 2.7× without quality degradation.

Original languageEnglish
Pages (from-to)583-593
Number of pages11
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume42
Issue number2
Early online date17 Jun 2022
DOIs
Publication statusPublished - Feb 2023

Scopus Subject Areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

User-Defined Keywords

  • Electronic design automation (EDA)
  • global routing
  • graphics processing unit (GPU) acceleration
  • maze routing
  • physical design

Fingerprint

Dive into the research topics of 'GAMER: GPU-Accelerated Maze Routing'. Together they form a unique fingerprint.

Cite this