Computing Along the Critical Path

Dean Tullsen and Brad Calder

UC San Diego Technical Report, October 1998.


Modern processors come close to executing as fast as true dependencies allow. The particular dependencies that constrain execution speed constitute the critical path of execution. To optimize the performance of the processor, we either have to reduce the critical path or execute it more efficiently. In both cases, it can be done more effectively if we know the actual path.

This paper describes a Critical Path Profiler for efficiently finding the critical dependence path through the complete execution of a program. It is intended to be used for profile-based compiler and processor optimizations. Unlike other critical-path based tools which analyze dependences along a single most-likely path (trace), this one analyzes dependences along every taken path through the code. We present data on the SPEC benchmark suite gathered through the profiler and experiment with potential uses for the profiler as a static critical-path predictor.