GPU-Accelerated Rectilinear Steiner Tree Generation

Abstract

Rectilinear Steiner minimum tree (RSMT) generation is a fundamental component in the VLSI design automation flow. Due to its extensive usage in circuit design iterations at early design stages like synthesis, placement, and routing, the performance of RSMT generation is critical for a reasonable design turnaround time. State-of-the-art RSMT generation algorithms, like fast look-up table estimation (FLUTE), are constrained by CPU-based parallelism with limited runtime improvements. The acceleration of RSMT on GPUs is an important yet difficult task, due to the complex and non-trivial divide-and-conquer computation patterns with recursions. In this paper, we present the first GPU-accelerated RSMT generation algorithm based on FLUTE. By designing GPU-efficient data structures and levelized decomposition, table look-up, and merging operations, we incorporate large-scale data parallelism into the generation of Steiner trees. An up to 10.47× runtime speed-up has been achieved compared with FLUTE running on 40 CPU cores, filling in a critical missing component in today’s GPU-accelerated design automation framework.

Publication
2022 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)
Zizheng Guo
Zizheng Guo
Ph.D. Student

I am a first-year Ph.D. student in the School of Integrated Circuits at Peking University. My current research interests include data structures, algorithm design and GPU acceleration for combinatorial optimization problems, and the application of reinforcement learning in designing heuristic algorithms.