C-PathGen: An Efficient CPU-Parallel Critical Path Generation Algorithm

Critical Path Generation (CPG) is fundamental for many static timing analysis (STA) applications. As the circuit complexity continues to increase, CPG runtime has quickly become the bottleneck due to its time-consuming and iterative nature. Despite many CPG algorithms introduced by existing timers, nearly all of them are limited to a single CPU thread , leading to long runtime for large CPG queries. To mitigate this runtime challenge, we need a parallel CPG algorithm. However, designing a parallel CPG algorithm is very challenging because we need to strategically partition the path search space into multiple groups that can run in parallel while accommodating different slack priorities. To overcome this challenge, we propose C-PathGen , an exact and efficient CPU-parallel CPG algorithm. Building on our prior CPU-parallel CPG algorithm, PathGen, C-PathGen overcomes its inaccuracy by filtering out non-critical paths. Additionally, to eliminate contention caused by atomic operations on generated paths, we introduce a new exploration strategy that processes the paths directly in place. Compared to PathGen, C-PathGen is 6.8 × –10.3 × faster while producing exact results when dealing with large path queries on industrial circuit graphs.