Efficient Critical Paths Search Algorithm using Mergeable Heap
Kexing Zhou, Zizheng Guo, Tsung‐Wei Huang, Yibo Lin · 2022 27th Asia and South Pacific Design Automation Conference (ASP-DAC) · 2022
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\times$faster compared to OpenTimer and$1.8\times$compared to the leading path search algorithm based on suffix forest.