CAREER: HeteroTime: Accelerating Static Timing Analysis with Intelligent Heterogeneous Parallelism

This award is funded in whole or in part under the American Rescue Plan Act of 2021 (Public Law 117-2). As design complexity continues to grow exponentially, the need to efficiently analyze the timing of large hardware designs has become the major bottleneck to the design closure flow. To reduce long analysis runtimes, recent years have seen many parallel static timing analysis (STA) solutions. Despite improved performance, a key fundamental challenge remains unsolved: Almost all existing parallel STA solutions are architecturally constrained by central processing unit (CPU) parallelism, and their scalability results largely plateaued at 8 to 16 CPU cores. Next-generation process technologies will feature more complex scenarios to analyze, resulting in order-of-magnitude higher computational complexity that far exceeds what existing CPU-parallel STA solutions can scale to. Speeding up STA algorithms is thus a high research priority for electronic design automation (EDA) tools to boost the performance of design closure flows. This CAREER project creates a novel open-source STA engine that 1) delivers transformational performance breakthroughs by harnessing the power of heterogeneous computing and machine learning and 2) establishes an open platform for researchers to contribute to design automation research and education. The proposed research and education activities will facilitate technology transfers and enable diverse industry-academia collaborations. This CAREER project researches novel STA algorithms that deliver order-of-magnitude performance breakthroughs by harnessing the power of heterogeneous parallelism and machine learning. It will research novel graphics processing unit (GPU) kernel algorithms and heterogeneous task decomposition strategies to accelerate critical STA problems, including graph-based analysis and path-based analysis, from a novel computing perspective. Furthermore, it will establish a learning-based task execution environment to achieve adaptive performance optimization to different STA workloads under real operating conditions. The research outcomes will enable ultra-fast analysis and optimization algorithms over the current state-of-the-art and substantially improve both turnaround time and quality of results (QoR) for design closure flows. Technical contributions of this project will span a multidisciplinary research community, including EDA, parallel computing, machine learning, and graph algorithms. Results of the project will be made open-source to encourage a wide range of EDA researchers and developers to contribute to the project by sharing new findings, ideas, and educational resources. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.