Parallelism performance analysis based on execution trace information

• US 6,961,925 B2
• Filed: 04/03/2001
• Issued: 11/01/2005
• Est. Priority Date: 12/23/1998
• Status: Expired due to Fees

• Current Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Original Assignee: CRAY Incorporated (Hewlett-Packard Enterprise Company)
• Inventors: Callahan, Charles David II, Shields, Keith Arnett, Briggs, Preston Pengra III
• Primary Examiner(s): Khatri, Anil
• Assistant Examiner(s): RAMPURIA, SATISH
• Application Number:
  US09/825,434
• Publication Number:
  US 20020129339A1
• Time in Patent Office: 1,673 Days
• Field of Search: 717/128, 717/124, 717/141, 717/158, 717/129, 717/125, 717/135, 702/179, 718/107, 718/104, 712 23-245, 714/154, 709/224
• US Class Current: 717/128
• CPC Class Codes: G06F 11/323 Visualisation of programs or trace data
• CPC Class Codes: G06F 11/3404 for parallel or distributed programming
• CPC Class Codes: G06F 11/3409 for performance assessment
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 11/3636 by tracing the execution of the program
• CPC Class Codes: G06F 11/3664 Environments for testing or debugging software
• CPC Class Codes: G06F 2201/86 Event-based monitoring
• CPC Class Codes: G06F 2201/88 Monitoring involving counting

Abstract

A system for conducting performance analysis for executing tasks. The analysis involves generating a variety of trace information related to performance measures, including parallelism-related information, during execution of the task. In order to generate the trace information, target source code of interest is compiled in such a manner that executing the resulting executable code will generate execution trace information composed of a series of events. Each event stores trace information related to a variety of performance measures for the one or more processors and protection domains used. After the execution trace information has been generated, the system can use that trace information and a trace information description file to produce useful performance measure information. The trace information description file contains information that describes the types of execution events as well as the structure of the stored information. The system uses the trace information description file to organize the information in the trace information file, extracts a variety of types of performance measure information from the organized trace information, and formats the extracted information for display. The system can use default or user-defined functions to extract and format trace information for display. After the system displays one or more types of performance measure information, a user of the system can then interact with the system in a variety of ways to obtain other useful performance analysis information.

Claims

1. A computer-implemented method for analyzing trace information generated during execution of multiple threads of a software program on a first computer, the first computer having multiple processors that each have multiple protection domains that are each able to execute at least one of the multiple threads, each processor having a counter indicating a number of instruction holes during which an instruction is not executed by the processor, each protection domain having a counter indicating a number of instructions issued in the protection domain by all executing threads, the method comprising:

receiving an indication of trace information reflecting a series of events that occurred during the execution, each event associated with execution of one of the multiple threads by one of the protection domains of one of the processors and each event having associated values in the trace information of variables maintained by the executing software program, by the one protection domain, and/or by the one processor;

for each of a plurality of periods of time during which the execution was occurring,

determining from the trace information a number of instructions executed for the software program during the period of time by

identifying multiple protection domains that each executed at least one of the multiple threads during at least a portion of the period of time;

for each of the identified protection domains,

determining a change in the value of the issued instructions counter of the protection domain during the period of time;

determining if all of the instructions issued in the protection domain during the period of time were for one of the multiple threads;

when it is determined that all of the instructions issued in the protection domain during the period of time were for one of the multiple threads, calculating a value for the number of instructions executed for the software program during the period of time by the protection domain to be the determined change; and

when it is determined that all of the instructions issued in the protection domain during the period of time were not for one of the multiple threads, calculating a value for the number of instructions executed for the software program during the period of time by the protection domain to be a portion of the determined change that corresponds to a portion of the period of time during which at least one thread for the software program was executing in the protection domain; and

determining the number of instructions executed for the software program during the period of time to be a sum of the calculated values for each of the identified protection domains; and

determining from the trace information a number of instruction slots available for execution of the instructions of software program during the period of time by

identifying processors that each executed at least one of the multiple threads during the period of time;

for each of the identified processors,

determining a change in the value of the instruction holes counter of the processor during the period of time; and

if all of the instruction holes that occurred during the period of time were attributable to the software program, calculating a value for the number of instruction holes for the processor that are attributable to the software program during the period of time to be the determined change in the value of the instruction holes counter;

calculating a value for the number of instruction holes that are attributable to the software program during the period of time by all of the identified processors to be a sum of the calculated values for each of the identified processors; and

determining the number of instruction slots available for execution of the instructions of software program during the period of time to be a sum of the determined number of instructions executed for the software program during the period of time and of the calculated value for the number of instruction holes that are attributable to the software program during the period of time; and

presenting to a user an indication of the determined number of executed instructions for each of the periods of time and an indication of the determined number of available instruction slots for each of the periods of time,

wherein only one software program can execute in a protection domain at any point in time, and wherein when it is determined that all of the instructions issued in a protection domain during a period of time were not for one of the multiple threads, the calculating of a value for the number of instructions executed for the software program during the period of time by the protection domain includes;

determining from the trace information at least one swap event that occurred in the protection domain during the period of time such that the software program is swapped into the protection domain so as to commence execution of the software program or such that the software program is swapped out of the protection domain so as to suspend execution of the software program;

retrieving for each of the determined swap events an associated value in the trace information of the issued instructions counter of the protection domain; and

using the retrieved associated values to calculate the value for the number of instructions executed for the software program during the period of time by the protection domain to include only increments to the issued instructions counter that occurred while the software program is swapped into the protection domain.

2. The method of claim 1 wherein, for at least one of the identified protection domains for at least one of the periods of time, there are no variable values in the trace information indicating a value for the issued instructions counter of that protection domain at an end of that period of time, and wherein the determining of a second value for the issued instructions counter of that protection domain at the end of that period of time includes estimating the second value based on an extrapolation between earlier and later values for that issued instructions counter.

3. The method of claim 1 wherein, for at least one of the identified processors for at least one of the periods of time, there are no variable values in the trace information indicating a value for the instruction holes counter of that processor at an end of that period of time, and wherein the determining of a second value for the instruction holes counter of that processor at the end of that period of time includes estimating the second value based on an extrapolation between earlier and later values for that instruction holes counter.

4. The method of claim 1 wherein, for at least one of the identified protection domains for at least one of the periods of time, no event occurred during the execution of the software program for that protection domain for that period of time, and including estimating the first and second values for the issued instructions counter of that protection domain.

5. The method of claim 1 wherein, for at least one of the identified processors for at least one period of time, at least one other software program is executing during that period of time, and including, for each of the at least one identified processors:

when it is determined that all of the instruction holes that occurred during that period of time were not attributable to the software program,

calculating a value for the number of instruction holes for that processor that are attributable to the at least one other software programs during that period of time; and

calculating a value for the number of instruction holes for that processor that are attributable to the software program during that period of time to be a difference of a total number of instruction holes for that processor during that period of time and the calculated value for the number of instruction holes for that processor that are attributable to the at least one other software programs.

6. The method of claim 5 wherein the at least one other software programs include only an operating system program, and wherein the calculated value for the number of instruction holes for each processor that are attributable to the operating system are zero.

7. The method of claim 1 wherein at least one of processors performing the execution has multiple streams performing the execution such that each of the multiple streams executes at least one of the threads, and including displaying information about the streams.

8. The method of claim 1 wherein the presenting to the user of the indication of the determined number of executed instructions for each of the periods of time and of the indication of the determined number of available instruction slots for each of the periods of time includes displaying a graph including the indications.

9. The method of claim 8 wherein the displayed indication of the determined number of available instruction slots for each period of time includes a displayed indication of the calculated number of instruction holes that are attributable to the software program during the period of time, with the calculated number of instruction holes displayed in such a manner that a user can visually aggregate the displayed indication of the determined number of executed instructions for that period of time with the displayed indication of calculated number of instruction holes for that period of time.

10. The method of claim 8 wherein the displayed graph includes a time-based axis, and wherein the displayed indications of the determined number of executed instructions and the determined number of available instruction slots for each of the periods of time are points on the graph.

11. The method of claim 10 wherein the displayed graph includes an origin with at least two axes, and including, after the displaying of the indications of the determined number of executed instructions and of the determined number of available instruction slots, redefining at least one of the axes based on a new indicated displayed location.

12. The method of claim 1 including, for at least one of the periods of time, presenting an indication of a logical code block of the software program that was executing during that period of time.

13. The method of claim 12 wherein the presented indication of the logical code block is a name of the logical code block.

14. The method of claim 12 wherein the presented indication of the logical code block is source code of the logical code block.

15. The method of claim 12 wherein the logical code block is a function.

16. The method of claim 1 including presenting at least some of the variable values from the trace information in a tabular format.

17. The method of claim 1 wherein the number of processors identified during each of the periods of time is greater than one, and wherein the determined number of available instruction slots for each of the periods of time is the identified number of processors for that period of time.

18. The method of claim 1 wherein a first number of processors identified during a first period of time is distinct from a second number of processors identified during a second period of time.

19. The method of claim 1, wherein the identified number of processors for at least one of the periods of time is greater than one, and wherein information for each of the processors is aggregated during the presenting of information for those periods of time.

20. The method of claim 19 including normalizing the information for each of the processors prior to the presenting of the information by determining a value for the instruction holes counter of each of the processors at a beginning of the execution of the software program and by subtracting the determined value for each instruction hole counter from each later value of that instruction hole counter.

21. The method of claim 1 wherein information to be presented is determined based on a specification provided by a user.

22. The method of claim 21 wherein the specification is used at the time of the presenting to determine the information to be presented.

23. The method of claim 1 including presenting information about memory references performed during at least one of the periods of time.

24. The method of claim 1 including presenting information about FLOPS performed during at least one of the periods of time.

25. The method of claim 1 including presenting information about a number of the threads in existence during at least one of the periods of time.

26. The method of claim 1 including presenting information about a number of the threads that are blocked during at least one of the periods of time.

27. The method of claim 1 including presenting information about a number of the threads that are ready for execution during at least one of the periods of time.

28. The method of claim 1 including presenting information about contention for locks during at least one of the periods of time.

29. The method of claim 1 wherein the presenting of information is in response to a request by a user.

30. The method of claim 1 wherein the presenting of information is performed automatically without user intervention.

31. The method of claim 1 including generating the indicated trace information.

32. The method of claim 1 wherein the software program is an executable version of a source code program such that execution of the executable version will generate the indicated trace information.

33. The method of claim 32 including generating the executable version by compiling the source code program such that a group of instructions is added to the source code program at a location specified by the user, the added instructions when executed to generate trace information for a type of event specified by the user.

34. The method of claim 32 including generating the executable version by compiling the source code program such that groups of instructions are added to the source code program at a plurality of automatically identified locations of the software, the added instructions when executed to generate trace information of a specified type.

35. The method of claim 34 wherein the automatically identified locations include beginnings of functions having more lines than a threshold.

36. The method of claim 34 wherein the automatically identified locations include ends of functions having more lines than a threshold.

37. The method of claim 34 wherein the automatically identified locations include locations where a compiler adds instructions related to parallelizing the execution of the executable version.

38. The method of claim 37 wherein the instructions related to parallelizing the execution of the executable version are instructions related to a fork.

39. The method of claim 37 wherein the instructions related to parallelizing the execution of the executable version are instructions related to a join.

40. The method of claim 1 including generating the indicated trace information by executing the executable version.

41. The method of claim 40 wherein, during the executing of the executable version, execution of each of the added groups of instructions adds current values of one or more of the variables to the generated trace information.

42. The method of claims 40 wherein information is added to the generated indicated trace information by an executing program other than the software program.

43. The method of claim 42 wherein the other executing program is an operating system.

44. The method of claim 42 wherein the other executing program is a background daemon.

45. The method of claim 1 including analyzing the trace information to extract execution information corresponding to the events that occurred during the execution.

46. The method of claim 45 wherein the analyzing of the trace information includes using a description of specified types of events to identify groups of trace information each reflecting execution of a group of added instructions.

47. The method of claim 46 wherein the analyzing of the trace information includes, when information for an event in the trace information is separated in multiple non-contiguous portions, creating a mapping to assist in retrieving the information for the event.

48. The method of claim 47 including using the identified groups of trace information and the created mapping to extract current values for execution information.

49. The method of claim 45 wherein the analyzing of the trace information includes modifying current values of events so as to be normalized with respect to beginning of the execution.

50. The method of claim 45 wherein the analyzing of the trace information includes modifying current values of events so that the values reflect only the execution of the multiple threads.

51. The method of claim 45 including using information retrieved from created descriptor objects in the trace information.

52. A computer-implemented method for analyzing trace information generated during execution of multiple threads of a software program on a first computer, the first computer having multiple processors that each have multiple protection domains that are each able to execute at least one of the multiple threads, each processor having a counter indicating a number of instruction holes during which an instruction is not executed by the processor, each protection domain having a counter indicating a number of instructions issued in the protection domain by all executing threads, the method comprising:

receiving an indication of trace information reflecting a series of events that occurred during the execution, each event associated with execution of one of the multiple threads by one of the protection domains of one of the processors and each event having associated values in the trace information of variables maintained by the executing software program, by the one protection domain, and/or by the one processor;

for each of a plurality of periods of time during which the execution was occurring,

determining from the trace information a number of instructions executed for the software program during the period of time by

identifying multiple protection domains that each executed at least one of the multiple threads during at least a portion of the period of time;

for each of the identified protection domains,

determining a change in the value of the issued instructions counter of the protection domain during the period of time;

determining if all of the instructions issued in the protection domain during the period of time were for one of the multiple threads;

when it is determined that all of the instructions issued in the protection domain during the period of time were for one of the multiple threads, calculating a value for the number of instructions executed for the software program during the period of time by the protection domain to be the determined change; and

when it is determined that all of the instructions issued in the protection domain during the period of time were not for one of the multiple threads, calculating a value for the number of instructions executed for the software program during the period of time by the protection domain to be a portion of the determined change that corresponds to a portion of the period of time during which at least one thread for the software program was executing in the protection domain; and

determining the number of instructions executed for the software program during the period of time to be a sum of the calculated values for each of the identified protection domains; and

determining from the trace information a number of instruction slots available for execution of the instructions of software program during the period of time by

identifying processors that each executed at least one of the multiple threads during the period of time;

for each of the identified processors,

determining a change in the value of the instruction holes counter of the processor during the period of time; and

if all of the instruction holes that occurred during the period of time were attributable to the software program, calculating a value for the number of instruction holes for the processor that are attributable to the software program during the period of time to be the determined change in the value of the instruction holes counter;

calculating a value for the number of instruction holes that are attributable to the software program during the period of time by all of the identified processors to be a sum of the calculated values for each of the identified processors; and

determining the number of instruction slots available for execution of the instructions of software program during the period of time to be a sum of the determined number of instructions executed for the software program during the period of time and of the calculated value for the number of instruction holes that are attributable to the software program during the period of time; and

presenting to a user an indication of the determined number of executed instructions for each of the periods of time and an indication of the determined number of available instruction slots for each of the periods of time, wherein the software program is an executable version of a source code program such that execution of the executable version will generate the indicated trace information and including generating the executable version by compiling the source code program such that a group of instructions is added to the source code program at a location specified by the user, the added instructions when executed to generate trace information for a type of event specified by the user wherein, for at least some of the groups of instructions to be added to the executable program to generate trace information of a specified type, an additional group of instructions is added to the source code program that when executed create a descriptor object for that group of instructions.

53. The method of claim 52 wherein the additional groups of instructions are added to the source code program in such a manner that the additional groups of instructions will be executed before any of the groups of instructions.

54. A computer-implemented method for analyzing trace information generated during execution of multiple threads of a software program on a first computer, the first computer having multiple processors that each have multiple protection domains that are each able to execute at least one of the multiple threads, each processor having a counter indicating a number of instruction holes during which an instruction is not executed by the processor, each protection domain having a counter indicating a number of instructions issued in the protection domain by all executing threads, the method comprising:

receiving an indication of trace information reflecting a series of events that occurred during the execution, each event associated with execution of one of the multiple threads by one of the protection domains of one of the processors and each event having associated values in the trace information of variables maintained by the executing software program, by the one protection domain, and/or by the one processor;

for each of a plurality of periods of time during which the execution was occurring,

determining from the trace information a number of instructions executed for the software program during the period of time by

identifying multiple protection domains that each executed at least one of the multiple threads during at least a portion of the period of time;

for each of the identified protection domains,

determining a change in the value of the issued instructions counter of the protection domain during the period of time;

determining if all of the instructions issued in the protection domain during the period of time were for one of the multiple threads;

when it is determined that all of the instructions issued in the protection domain during the period of time were for one of the multiple threads, calculating a value for the number of instructions executed for the software program during the period of time by the protection domain to be the determined change; and

when it is determined that all of the instructions issued in the protection domain during the period of time were not for one of the multiple threads, calculating a value for the number of instructions executed for the software program during the period of time by the protection domain to be a portion of the determined change that corresponds to a portion of the period of time during which at least one thread for the software program was executing in the protection domain; and

determining the number of instructions executed for the software program during the period of time to be a sum of the calculated values for each of the identified protection domains; and

determining from the trace information a number of instruction slots available for execution of the instructions of software program during the period of time by

identifying processors that each executed at least one of the multiple threads during the period of time;

for each of the identified processors,

determining a change in the value of the instruction holes counter of the processor during the period of time; and

if all of the instruction holes that occurred during the period of time were attributable to the software program, calculating a value for the number of instruction holes for the processor that are attributable to the software program during the period of time to be the determined change in the value of the instruction holes counter;

calculating a value for the number of instruction holes that are attributable to the software program during the period of time by all of the identified processors to be a sum of the calculated values for each of the identified processor; and

determining the number of instruction slots available for execution of the instructions of software program during the period of time to be a sum of the determined number of instructions executed for the software program during the period of time and of the calculated value for the number of instruction holes that are attributable to the software program during the period of time; and

presenting to a user an indication of the determined number of executed instructions for each of the periods of time and an indication of the determined number of available instruction slots for each of the periods of time wherein during the executing of the executable version, execution of each of the added groups of instructions adds current values of one or more of the variables to the generated trace information and, during the executing of the executable version and before the execution of an added group of instructions, an additional group of added instructions is executed and creates a descriptor object for that added group of instructions.

55. A method for generating trace information reflecting a series of events that occurred during execution of multiple software threads on a first computer, the method comprising:

receiving an indication of a software program for which trace information is to be generated;

receiving indications from a user of one or more locations within the software program at which trace information is to be generated and of one or more types of event each indicating distinct types of trace information; and

automatically producing an executable version corresponding to the software program such that when executed the produced executable version will generate trace information corresponding to multiple events of the types indicated by the user, the producing of the executable version including adding multiple groups of instructions to the software program at the locations specified by the user, each of the added groups of instructions corresponding to one of the types of events indicated by the user such that when executed that added group of instructions will generate the distinct types of trace information for that type of event, the produced executable version having one or more portions which can be executed in parallel with multiple software threads,

so that execution of the produced executable version will generate trace information reflecting a series of events that occurred during execution, wherein, for at least some of the groups of instructions added to the executable program, additional instructions are added to the executable program that when executed creates a descriptor object for that group of instructions.

56. The method of claim 55 wherein the additional groups of instructions are added in such a manner as to be executed before any of the added groups of instructions.

57. The method of claim 55 wherein the first computer has multiple processors that each have multiple protection domains each able to execute at least one of the multiple threads.

58. The method of claim 55 wherein the first computer provides multiple sources of information related to hardware aspects of the first computer that vary with execution of programs on the first computer, and wherein the distinct types of trace information for some of the types of events includes at least one of the sources of information related to the hardware aspects.

59. The method of claim 55 wherein the first computer provides multiple sources of information related to software properties of the first computer that vary with execution of programs on the first computer, and wherein the distinct types of trace information for some of the types of events includes at least one of the sources of information related to the software properties.

60. A method for generating trace information reflecting a series of events that occurred during execution of multiple software threads on a first computer, the method comprising:

receiving an indication of an executable software program that when executed will generate trace information corresponding to multiple events of specified types, the executable software program including multiple groups of instructions added at specified locations and each corresponding to one of the specified types of events; and

generating the trace information by executing the executable software program using multiple software threads on the first computer in such a manner that each of the added group of instructions are executed at least once, each execution of an added group of instructions corresponding to a specified type of event generating trace information of the type for that type of event, wherein, during the executing of the executable software program and before the execution of an added group of instructions, an additional group of added instructions is executed and creates a descriptor object for that added group of instructions.

61. The method of claims 60 wherein information is added to the generated indicated trace information by an executing program other than the executable software program.

62. The method of claim 61 wherein the other executing program is an operating system.

63. The method of claim 61 wherein the other executing program is a background daemon.

64. A method for analyzing trace information generated during execution of multiple threads of a software program on a first computer, the generated trace information reflecting a series of events that occurred during the execution, the method comprising:

receiving an indication of trace information generated during execution of an executable software program using multiple software threads on the first computer, the executable software program including multiple groups of instructions each corresponding to a specified type of event, the execution such that each of the multiple group of instructions are executed at least once and such that each execution of an added group of instructions generates trace information of a type corresponding to the specified type of event for that added group of instructions; and

analyzing the generated trace information to extract execution information corresponding to the events that occurred during the execution, wherein the analyzing of the generated trace information includes using a description of the specified types of events to identify groups of trace information each reflecting execution of a group of added instructions corresponding to those specified types of events and the analyzing of the trace information includes, when information for an event in the generated trace information is separated in multiple non-contiguous portions, creating a mapping to assist in retrieving the information for the event.

65. The method of claim 64 including using the identified groups of trace information and the created mapping to extract current values for execution information.

66. The method of claim 64 wherein the analyzing of the trace information includes modifying current values of events so as to be normalized with respect to beginning of the execution.

67. The method of claim 64 wherein the analyzing of the trace information includes modifying current values of events so that the values reflect only the execution of the multiple threads.

68. The method of claim 64 including using information retrieved from created descriptor objects in the generated trace information.

69. A method performed by a computing system for analyzing trace information generated during execution of a software program on a computing system having multiple processors, comprising:

receiving an indication of trace information;

determining from the trace information a number of instructions issued by the computing system having multiple processors, the instructions issued when the software program is executed;

determining a number of instruction holes that are attributable to the software program; and

calculating a number of instruction slots available for execution of the software programs by the computing system with multiple processors, the calculating based on the determined number of instructions issued and the number of holes instruction.