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.

Publication
27th Asia and South Pacific Design Automation Conference (ASP-DAC) 2022
Zizheng Guo
Zizheng Guo
Ph.D. Student

I am a first-year Ph.D. student in the School of Integrated Circuits at Peking University. My current research interests include data structures, algorithm design and GPU acceleration for combinatorial optimization problems, and the application of reinforcement learning in designing heuristic algorithms.