Variational path profiling

• US 7,607,119 B2
• Filed: 04/26/2005
• Issued: 10/20/2009
• Est. Priority Date: 04/26/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chilimbi, Trishul, Perelman, Erez
• Primary Examiner(s): Zhen; Wei Y
• Assistant Examiner(s): WANG, RONGFA PHILIP
• Application Number:
  US11/115,924
• Publication Number:
  US 20060242636A1
• Time in Patent Office: 1,638 Days
• Field of Search: None
• US Class Current: 717/101
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 11/3612 by runtime analysis performance monitoring G06F11/3466

Abstract

A run time software test tool instruments a program to perform a low overhead profiling of the program'"'"'s execution, which records the execution time of frequent acyclic control flow paths using hardware performance counters. An analysis of the profiling data is performed to identify those program paths that have significant variation in execution time across different dynamic traversals in the same program run. This variation (measured as the difference between the fastest execution of that path and slower executions) represents the potential speedup that potentially could be achieved if the paths were optimized (such as by the addition of simple pre-fetch optimizations) to do away with these variations. The variational paths are identified to the programmer to guide optimization.

Claims

1. A method of software program execution profiling, comprising:

measuring variation in execution time between iterations of paths through the software program, the variation in execution time measured for multiple iterations of each path over base times for the paths; and

identifying paths having higher execution time variation;

wherein said measuring comprises;

inserting instrumentation code into the software program;

causing the software program to execute under a usage scenario;

recording profiling data by the instrumentation code during said execution of the software program, the profiling data including at least execution times for at least some iterations of at least some paths of the software program; and

performing a path variation analysis determining which of the paths have higher execution time variation; and

wherein said performing path variation analysis comprises;

determining base times of execution of the paths;

determining variation times for multiple iterations of each of the paths as a difference of the execution times of the multiple iterations of each of the paths from the base times; and

determining path variation times for the paths as a sum of the variation times of the multiple iterations of the respective paths.

2. The method of claim 1 wherein said recording profiling data comprises:

periodically sampling traces of the software program execution for low overhead profiling of path execution time variation.

3. The method of claim 2 wherein said recording profiling data comprises:

structuring the instrumentation code according to a bursty tracing framework that transitions between execution of a very lightly instrumented software program version a majority of the time, and occasional execution of a fully instrumented software program version during which path execution time profiling data is recorded.

4. The method of claim 2 wherein said recording current time in the profiling data comprises recording a hardware cycle counter.

5. The method of claim 2 wherein said recording the path signature in the profiling data comprises recording a value indicative of a starting location of the respective path.

6. The method of claim 1 wherein said recording profiling data comprises:

recording at least a path signature and current time at a starting point of a path; and

recording at least a path signature and current time at an end point of a path.

7. The method of claim 6 wherein said recording the path signature in the profiling data comprises recording data indicative of a branch history of the path.

8. The method of claim 1 wherein said performing path variation analysis further comprises:

ranking the paths according to their determined path variation times; and

identifying the paths having the highest determined path variation times as those having higher execution time variation.

9. A variational path profiling tool comprising:

a computer processor configured to perform the actions of;

an execution profiler operative to measure and collect execution timings for a plurality of paths taken during execution of a software program under a usage scenario; and

a path variation time analyzer operative to identify paths having high execution time variation over base times for the paths based on the collected execution timings, the path variation time analyzer comprising;

means to calculate a base time of execution of each of the paths, the base time representing a minimum observed time out of multiple observed times from multiple iterations of the paths;

means to calculate a variation time in excess of the base time for each of multiple iterations of the paths; and

means to calculate a cumulative total variation time of all of the multiple iterations for the respective paths.

10. The variational path profiling tool of claim 9 wherein the execution profiler further comprises:

an instrumenting means for embedding instrumentation code into the software program, the instrumentation code operating upon execution of the software program to record profiling data for the paths, the profiling data including a path identification and execution timing for iterations of the paths.

11. The variational path profiling tool of claim 10 wherein the instrumentation code is structured to profile path execution timings in periodic bursty tracing samples of the software program execution for reduced performance overhead during profiling.

12. The variational path profiling tool of claim 9 wherein the path variation time analyzer further comprises means to rank the paths in order of their total variation times.

13. A method of optimizing a software program, comprising:

profiling execution of the software program using a bursty tracing framework, the profiling measuring execution timings for multiple iterations of a plurality of paths taken during the execution of the software program;

determining base times of execution of the paths, each base time for a path representing a minimum observed time out of multiple observed times from multiple iterations of the paths;

analyzing the variability in execution time of each of the paths in the profiled execution of the software program based in part on the sum of execution time differences of multiple iterations of each path from base times determined for the paths;

identifying a number of top variable paths having the highest variability in execution time over the base times; and

modifying the software program to apply optimizations to avoid stalls from data access at one or more levels of a computer memory hierarchy in the identified top variable paths.

14. The method of claim 13 wherein said applying optimizations comprises inserting one or more operations in a path to effect prefetching for a data access.