Efficient Critical Paths Search Algorithm using Mergeable Heap

Abstract

Path searching is a central step in static timing analysis (STA). State-of-the-art algorithms need to generate path deviations for hundreds of thousands of paths, which becomes the runtime bottleneck of STA. Accelerating path searching is a challenging task due to the complex and iterative path generating process. In this work, we propose a novel path searching algorithm that has asymptotically lower runtime complexity than the state-of-the-art. We precompute the path deviations using mergeable heap and apply a group of deviations to a path in near-constant time. We prove our algorithm has a runtime complexity of O(n log n+k log k) which is asymptotically smaller than the state-of-the-art O(nk). Experimental results show that our algorithm is up to 60× faster compared to OpenTimer and 1.8× compared to the leading path search algorithm based on suffix forest.