A GPU-Accelerated Framework for Path-Based Timing Analysis

As a key routine in static timing analysis (STA), path-based analysis (PBA) plays a very important role in refining the critical path report by reducing excessive slack pessimism. PBA is also well known for its long execution time, which makes it a hot topic for parallel computing in the STA community. However, nearly all of the parallel PBA algorithms are restricted to CPU architectures, which greatly limits their scalability. To achieve a new performance milestone on PBA, we must leverage the high throughput computing in the graphics processing unit (GPU). Therefore, in this work, we propose a new GPU-accelerated PBA framework which contains compact data structures and highly efficient kernels. By integrating with GPU-accelerated preprocessing steps, our framework can also effectively handle extensive critical path constraints. Besides, we highlight many optimization techniques that can overcome the execution bottleneck and further boost the performance. In experiments, we demonstrate 543x speed-up compared to the state-of-the-art PBA algorithm on the design with 1.6 million gates, which outperforms 25x - 45x over the state-of-the-art parallel PBA algorithm on 40 CPU cores. A fully optimized framework can achieve 3x - 5x speed-up on top of that.