DAC-CPPR: A fast and accurate approach for common path pessimism removal with divide and conquer on the clock tree

To reduce the redundant pessimism in static timing analysis, common path pessimism removal (CPPR) is widely used as a pivotal step. However, as the amount of pessimism that needs to be removed is path-specific, solving the CPPR problem is very expensive and has become the hurdle in deploying the technology. Even though there exit efficient design-specific pruning heuristics, their performance cannot be guaranteed. In this paper, we introduce DAC-CPPR, a CPPR algorithm that is both efficient and with provably good performance. It is based on Divide and Conquer technique on the clock tree. We prove the algorithm has a logarithmic time complexity proportional to the clock tree nodes. Experimental results demonstrate the effectiveness and efficiency of our algorithms.