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 543× speed-up compared to the state-of-the-art PBA algorithm on the design with 1.6 million gates, which outperforms 25–45× over the state-of-the-art parallel PBA algorithm on 40 CPU cores. A fully optimized framework can achieve 3–5× speed-up on top of that.

Composite Current Source (CCS) timing model plays an important role in modern static timing analysis (STA) because it precisely captures the timing behavior of a design at advanced nodes. However, CCS is extremely time-consuming due to its accurate but complicated timing models. To overcome this challenge, we introduce GCS-Timer, a GPU-accelerated CCS-based timing analysis algorithm. Unlike existing methods that perform model order reduction to trade accuracy for speed, GCS-Timer achieves high accuracy through a fast simulation-based analysis using GPU computing. Experimental results show that GCS-Timer can complete CCS analysis with better accuracy and achieve 3.2X faster runtime compared with a 16-threaded industrial standard timer. The source code is available at https://github.com/cuhk-eda/GCS-Timer.

Recent efforts of applying e-graphs in logic synthesis have shown promising results. Nevertheless, e-graph-based gate-level logic optimization suffers from inefficiency and limited extraction quality. In this article, we propose a fast parallel e-matching algorithm for speeding up e-graph rewriting, and an efficient netlist extraction framework with high quality of results in both area and delay. Experiments show that e-graph rewriting can be accelerated by up to 8.3× over a high-performance e-graph library, and our extraction framework achieves 11.0% and 1.0% improvements in size and level on average, compared to the best results of the state-of-the-art netlist extraction method.