Algorithm

Engineering

Critical path method

Embedded system

Theoretical computer science

Systems engineering

Parallel computing

Computer science

Mathematical optimization

Graph

Mathematics

Static timing analysis

Path (computing)

Programming language

Shortest path problem

Fast path

State (computer science)

Path-based Analysis (PBA) is a pivotal step in Static Timing Analysis (STA) for reducing slack pessimism and improving quality of results. Optimization flows often invoke PBA repeatedly with different critical path constraints to verify correct timing behavior under certain logic cone. However, PBA is extremely time consuming and state-of-the-art PBA algorithms are hardly scaled beyond a few CPU threads under constrained search space. In order to achieve new performance milestone, in this work, we propose a new GPU-accelerated PBA algorithm which can handle extensive path constraints and quickly report arbitrary number of critical paths in constrained search space. Experimental results show that our algorithm can generated identical path report and achieve up to 102x speed up on a million-gate design compared to the state-of-the-art algorithm.

GPU-accelerated Critical Path Generation with Path Constraints