Method and apparatus for identifying similar regions of a program's execution

• US 7,802,236 B2
• Filed: 09/09/2003
• Issued: 09/21/2010
• Est. Priority Date: 09/09/2002
• Status: Active Grant

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Perelman, Erez, Hamerly, Gregory, Sherwood, Timothy, Calder, Brad
• Primary Examiner(s): WANG, RONGFA PHILIP
• Application Number:
  US10/659,066
• Publication Number:
  US 20040111708A1
• Time in Patent Office: 2,569 Days
• Field of Search: 717/130, 717/131, 717/134, 717/135, 714 37- 39, 714/41, 714/32, 714/819
• US Class Current: 717/130
• CPC Class Codes: G06F 11/3419 by assessing time
• CPC Class Codes: G06F 11/3447 Performance evaluation by modeling
• CPC Class Codes: G06F 11/3452 Performance evaluation by statistical analysis
• CPC Class Codes: G06F 11/3457 Performance evaluation by simulation
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 2201/865 Monitoring of software
• CPC Class Codes: G06F 2201/88 Monitoring involving counting

Abstract

A method and architecture for analyzing a computer program by finding similar sections of execution of the computer program. Code of the computer program is run over a plurality of intervals of execution, and during the execution of the program, a statistic is tracked for a component. Using the tracked statistic, behavior of the computer program is identified over each of the plurality of intervals of execution, and at least one identified behavior of at least one interval of execution is compared to the behavior of another interval of execution to find similar sections of behavior.

Claims

1. A method of analyzing a computer program, the computer program including instructions of code, the method comprising:

a processor and a memory performing;

selecting a number of continuous instructions that are run in program execution order to define an interval of execution;

running the code of the computer program, wherein said running the code comprises running a plurality of continuous instructions of the code in program execution order, wherein within the plurality of continuous instructions, the code is run over a plurality of the defined intervals of execution, wherein each of the plurality of defined intervals of execution is run over the selected number of continuous instructions;

during said step of running the code, tracking a statistic for a program component;

identifying a behavior of the computer program over each of the plurality of defined intervals of execution over which the code is run based on the tracked statistic;

comparing at least one identified behavior for at least one defined interval of execution over which the code is run to another defined interval of execution over which the code is run to determine similarity between the defined intervals of execution.

2. The method of claim 1 wherein said step of running the code comprises at least one of executing the program on hardware, simulating the program'"'"'s execution in software, direct execution, emulating the program'"'"'s execution in software, and modeling a hypothetical execution in software.

3. The method of claim 2 wherein the statistic comprises at least one of a hardware metric and a hardware-independent metric.

4. The method of claim 3 wherein the statistic comprises at least one of frequency of the component occurring in execution, number of instructions executed, amount of memory used by the program component, time, IPC, performance counters, program counters, and cache miss rate.

5. The method of claim 2 wherein the program component comprises an identifiable section of control flow of the computer program.

6. The method of claim 5 wherein the program component comprises at least one of an instruction, basic block, procedure, loop, load instruction, and branch instruction.

7. The method of claim 5 wherein the program component comprises a basic block, the basic block being a section of the code having a single entry point and a single exit.

8. The method of claim 2 wherein the program component comprises a memory region.

9. The method of claim 2 wherein each of the plurality of intervals of execution is selected independently of particular lines of code of the computer program.

10. The method of claim 2 further comprising:

based on said comparing step, classifying the plurality of defined intervals of execution over which the code is run into at least one cluster, said one or more clusters being based on similarity of behavior.

11. The method of claim 10 further comprising:

selecting at least one representative interval of execution for each of the at least one cluster.

12. The method of claim 11 wherein each of the at least one representative interval of execution is closest to an average behavior of the cluster.

13. The method of claim 12 further comprising:

weighing each of the selected representative intervals of execution based on at least one of a total amount of time, a number of instructions within the cluster, the program component, and the statistic;

wherein the weighted representative intervals collectively represent a complete execution of at least a subset of the computer program;

and further comprising minimizing the number of clusters.

14. The method of claim 11 wherein the representative interval of execution is the earliest interval of execution within a predetermined distance from an average behavior of the cluster.

15. The method of claim 14 further comprising:

weighing each of the selected representative intervals of execution based on at least one of a total amount of time, a number of instructions within the cluster, the program component, and the statistic;

wherein the weighted representative intervals collectively represent a complete execution of at least a subset of the computer program; and

further comprising

minimizing the number of clusters.

16. The method of claim 15 wherein the step of comparing comprises:

comparing each defined interval over which the code is run to the intervals of execution representing at least a subset of execution of the computer program.

17. The method of claim 16 further comprising:

based on said comparing step, identifying an end of an initialization of the computer program.

18. The method of claim 16 further comprising:

based on said comparing step, identifying a length of at least one repeating interval of execution.

19. The method of claim 18 wherein said step of identifying a length comprises performing an analysis of a signal, the signal comprising differences between each identified interval of execution and the interval of execution representing the at least a subset of execution of the computer program.

20. The method of claim 11 further comprising:

weighing each of the selected representative intervals of execution based on at least one of a total amount of time, a number of instructions within the cluster, the program component, and the statistic.

21. The method of claim 20 wherein the weighted representative intervals collectively represent a complete execution of at least a subset of the computer program.

22. The method of claim 21 further comprising:

minimizing the number of clusters.

23. The method of claim 10 further comprising:

minimizing the number of clusters.

24. The method of claim 10 further comprising:

determining a confidence and variance by sampling the defined intervals of execution over which the code is run within a particular cluster for at least one of a hardware metric and a hardware-independent metric.

25. The method of claim 1 wherein the defined intervals of execution comprise at least one of overlapping and non-overlapping intervals;

wherein each of the defined intervals of execution comprises a plural number of continuous instructions in program execution order.

26. The method of claim 2 wherein the behavior identified for a particular one of the defined plurality of intervals of execution over which the code is run is collected in a vector, the vector containing the statistic for at least one element representing at least one component.

27. The method of claim 26 wherein the vector is retained in at least one of the memory, a storage medium, and a table.

28. The method of claim 27 wherein the vector is stored as a signature that represents at least one of the behavior of a complete vector, a projection of the vector, a compressed representation of the vector, a partial representation of the vector, and a subset of the identified behavior collected in the vector.

29. The method of claim 28 further comprising:

storing a phase ID with the signature, wherein the phase ID comprises at least one of a complete signature, a subset of the signature, a partial representation of the signature, a name independent of the signature, and a number.

30. The method of claim 29 wherein the stored phase ID is identified for an interval by looking up the signature in storage and based on said looking up, either using the phase ID stored with the signature or creating a new phase ID.

31. The method of claim 30 wherein the identified behavior and the tracked statistic for at least one interval with a phase ID are stored and associated with one another.

32. The method of claim 31 wherein, if a storage area for storing the phase ID, behavior, and statistic is finite, only a single stored signature for a phase ID, and the phase ID, are stored.

33. The method of claim 30 further comprising, after the phase ID is identified by a signature for an interval:

looking up the phase ID to find the associated statistic for the interval.

34. The method of claim 33 further comprising:

using the found associated statistic, performing at least one of a behavior optimization, statistic optimization, load-time optimization, run-time optimization, and hardware reconfiguration.

35. The method of claim 30 wherein the phase ID is stored in a prediction table, and further comprising:

predicting a phase ID for an interval using the stored phase ID.

36. The method of claim 35 further comprising:

retrieving information for the predicted phase ID;

using the retrieved information, guiding optimization for the computer program.

37. A method of analyzing a computer program, the computer program including instructions of code, the method comprising:

a processor and a memory performing;

selecting a number of continuous instructions that are run in program execution order to define an interval of execution;

running the code of the computer program, wherein said running the code comprises running a plurality of continuous instructions of the code in program execution order, wherein within the plurality of continuous instructions, the code is run over a plurality of the defined intervals of execution, wherein each of the plurality of defined intervals of execution is run over the selected number of continuous instructions;

during said step of running the code, tracking a statistic for a program component;

identifying a behavior of the computer program over each of the plurality of defined intervals of execution over which the code is run based on the tracked statistic;

classifying each of the at least one intervals of execution over which the code is run according to the identified behavior into clusters of similar behavior.

38. The method of claim 37 wherein said step of identifying comprises identifying a frequency of execution of basic blocks of the executed code, wherein each of the at least one basic block comprises a piece of code of the computer program executed from start to finish, said basic block having only one entry point and one exit.

39. The method of claim 38 wherein said step of identifying a frequency provides a group of frequencies for each of the number of defined intervals of execution over which the code is run.

40. The method of claim 39 wherein said step of classifying further comprises:

comparing the identified behavior of one of the defined intervals of execution over which the code is run to the identified behavior of another of the defined intervals of execution over which the code is run to identify a phase.

41. The method of claim 40 further comprising:

identifying an initialization phase;

determining at least one analysis point occurring after execution of the identified initialization phase.

42. The method of claim 38 wherein said step of identifying a frequency of execution for each of the at least one basic block comprises:

for each of the number of defined intervals over which the code is run, determining a interval vector, the interval vector comprising a plurality of ordered elements, each of the plurality of ordered elements relating to a particular basic block and representing a frequency of execution of the particular basic block.

43. The method of claim 38 further comprising:

partitioning the computer program into a set of clusters by comparing the determined interval vectors to one another.

44. The method of claim 43 wherein said step of partitioning further comprises:

determining a group of clusters;

comparing each of the interval vectors to each of the set of clusters;

adding the compared interval vector to a particular cluster based on a goodness of fit between the compared basic block vectors and each of the group of clusters;

changing a centroid of each of the group of clusters;

repeating the comparing, adding, and clustering steps to form the set of clusters.

45. A method of analyzing a computer program, the computer program including instructions of code, the method comprising:

a processor and a memory performing;

selecting a number of continuous instructions that are run in program execution order to define an interval of execution;

running the code, wherein said running the code comprises running a plurality of continuous instructions of the code in program execution order, wherein within the plurality of continuous instructions, the code is run over a plurality of the defined intervals of execution, wherein each of the plurality of defined intervals of execution is run over the selected number of continuous instructions;

during said step of running the code, tracking a statistic for a program component;

identifying a behavior of a hardware-independent metric over each of the plurality of defined intervals of execution over which the code is run based on the tracked statistic;

identifying behavior of the hardware-independent metric over full execution of the code to identify a target behavior;

comparing the identified behavior of each of the plurality of defined intervals of execution over which the code is run to the identified target behavior over full execution of the code to determine a representative interval;

simulating execution of the computer program over the determined representative interval.

46. The method of claim 45 wherein said step of identifying comprises:

deriving a plurality of basic block vectors, each basic block vector representing code blocks of the program executed during the defined interval of execution over which the code is run, the basic block vector being based on frequencies of basic blocks of executed code within execution of the program;

wherein the basic block vector comprises a single dimensional array where a single element in the array exists for a basic block in the program.

47. The method of claim 45 wherein the method is performed in run-time.

48. The method of claim 47 wherein said step of identifying comprises tracking a proportion of instructions executed from different sections of code of the program over which each of the defined plurality of intervals is run;

further comprising, for each of the defined plurality of intervals over which the code is run, classifying the identified behavior into phases corresponding to changes in behavior across the executed code.

49. The method of claim 48 further comprising:

predicting when execution of the code is about to enter a phase change;

predicting a phase entered by the phase change.

50. The method of claim 48 wherein said step of identifying comprises, for each section of code:

capturing an identifier of the section of code;

capturing a number of instructions executed for the section of code.

51. The method of claim 50 further comprising:

reducing a number of the identified sections of code to a lower number.

52. The method of claim 50 further comprising:

comparing each section of code to a section of code in a history;

if the compared section of code varies from the section of code in the history by a greater amount than a predetermined threshold, adding the comparedsection of code to the history.

53. A method of analyzing a computer program, the computer program including instructions of code, the method comprising:

a processor and a memory performing;

selecting an amount of execution time over which continuous instructions of the code are run in program execution order to define an interval of execution;

running the code of the computer program, wherein said running the code comprises running a plurality of continuous instructions of the code in program execution order, wherein within the plurality of continuous instructions, the code is run over a plurality of the defined intervals of execution, wherein each of the plurality of defined intervals of execution is run over the selected amount of execution time;

during said step of running code, tracking a statistic for a program component;

identifying a behavior of the computer program over each of the defined plurality of intervals of execution over which the code is run based on the tracked statistic;

comparing at least one identified behavior for at least one defined interval of execution over which the code is run to another defined interval of execution over which the code is run to determine similarity between the intervals of execution.