Method for identifying reasons for dynamic stall cycles during the execution of a program

• US 5,857,097 A
• Filed: 03/10/1997
• Issued: 01/05/1999
• Est. Priority Date: 03/10/1997
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Weihl, William Edward, Henzinger, Monika Hildegard, Sites, Richard L., Leung, Shun-Tak Albert, Vandevoorde, Mark T.
• Primary Examiner(s): Lim, Krisna
• Application Number:
  US08/814,190
• Time in Patent Office: 666 Days
• Field of Search: 395/392, 395/395, 395/583, 395/183.13, 395/184.01
• US Class Current: 712/236
• CPC Class Codes: G06F 11/34 Recording or statistical evaluation of computer activity, e.g. of down time, of input/output operation ; Recording or statistical evaluation of user activity, e.g. usability assessment
• CPC Class Codes: G06F 11/3409 for performance assessment
• CPC Class Codes: G06F 11/3452 Performance evaluation by statistical analysis
• CPC Class Codes: G06F 2201/815 Virtual
• CPC Class Codes: G06F 2201/865 Monitoring of software
• CPC Class Codes: G06F 2201/88 Monitoring involving counting
• CPC Class Codes: G06F 2201/885 Monitoring specific for caches
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836

Abstract

In a computerized method, performance data collected while a computer system executed instructions of a program are analyzed. The method collects performance data while executing the program. The performance data includes sample counts of instructions executed. The program is analyzed to determine classes of instructions. Instructions of the same equivalence class all execute the identical number of times. The execution frequencies for each instructions of each equivalence class is estimated. The estimated execution frequencies can then be used to determine the average number of cycles required to issue each instruction of each equivalence class. The average number of cycles can be compared with the minimum number of cycles to determine the number of dynamic stall cycles incurred by the instructions. Furthermore, reasons for the dynamic stall cycles can be inferred.

Claims

1. A computerized method for analyzing performance data of a computer system executing instructions of a program, comprising the steps of:

analyzing the program to determine equivalence classes of instructions, each equivalence class containing instructions that have the same execution frequency as each other instruction in that equivalence class;

collecting performance data while executing the instructions of the program; and

estimating an execution frequency for each instruction in the program based on the collected performance data and the determined equivalence classes.

2. The method of claim 1 further comprising:

providing an instruction scheduler with an input array of the instructions of the program to determine a minimum number of cycles required to issue each instruction of the program; and

determining the average number of cycles required to dynamically issue each instruction of the program while the program is executing.

3. The method of claim 2 further comprising:

determining the number of static stall cycles and the number of dynamic stall cycles incurred while issuing each instruction of the program.

4. The method of claim 3 further comprising:

determining reasons for the dynamic stall cycles incurred by each instruction of the program.

5. The method of claim 3 further comprising:

identifying all possible reasons that could cause a particular instruction to incur dynamic stall cycles; and

eliminating reasons which can be ruled out as reasons for the particular instruction to have dynamic stall cycles to determine the possible reasons that caused the particular instruction to incur dynamic stall cycles.

6. The method of claim 5 further comprising:

eliminating instruction-cache misses as a reason depending on a memory address of the particular instruction.

7. The method of claim 5 further comprising:

eliminating data-cache misses as a reason depending on how registers of the processor are referenced by the particular instruction and by previously executed instructions.

8. The method of claim 7 further comprising:

identifying the previously executed instructions by conducting a depth-first search of the control flow graph beginning at the particular instruction.

9. The method of claim 5 further comprising:

eliminating branch misprediction as a reason depending on a location of the particular instruction within a particular basic block.

10. The method of claim 5 further comprising:

eliminating process synchronization as a reason depending on an operator code of the particular instruction and instructions executed immediately preceding the particular instruction.

11. The method of claim 5 further comprising:

eliminating execution unit conflicts as a reason depending on an operator code of the particular instruction.

12. The method of claim 5 further comprising:

eliminating write buffer overflow as a reason depending on an operator code of the particular instruction.

13. The method of claim 2, further comprising the step of:

determining a number of dynamic stalls incurred while issuing each instruction of the program based on the average number of cycles required to issue that instruction and the minimum number of cycles determined for that instruction.

14. The method of claim 1 further comprising:

representing procedures of the program as a control flow graph having nodes and arcs, each node representing a basic block of the program, and the arcs representing execution flows between the basic blocks and the procedures, each instruction of a particular basic block being executed an identical number of times so that the instructions of the basic block form an equivalence class of instructions.

15. The method of claim 14 further comprising:

identifying all nodes and arcs of the control flow graph which have an identical execution frequency;

assigning all the nodes having the identical execution frequency to the same equivalence class.

16. The method of claim 14 further comprising the step of augmenting the control flow graph by:

identifying an entry node and an exit node of each procedure;

connecting the entry and exit nodes of the procedure to each other by a new arc;

decomposing the nodes and arcs of the procedure into strongly connected sub-graphs;

identifying a particular strongly connected sub-graph as a dead-end component if there are no arcs from any of the nodes of the particular strongly connected sub-graph to any nodes in any other strongly connected sub-graph;

redirecting all arcs entering any dead-end component to the exit node of the procedure; and

identifying cycle equivalent nodes and arcs in each of the dead-end components and in the remaining part of the augmented control flow graph excluding the dead-end components to determine the frequency equivalence classes.

17. The method of claim 14 wherein the estimating step first estimates the execution frequency for nodes and arcs of a particular frequency equivalence class that excludes instructions that might incur dynamic stall cycles.

18. The method of claim 17 further comprising:

locally propagating the estimated frequencies of the nodes and arcs of the particular frequency equivalence class to nodes and arcs that are immediately adjacent to the nodes and arcs of the particular frequency equivalence class using flow-in and flow-out constraints of the control flow graph.

19. The method of claim 18 further comprising:

estimating execution frequencies for another frequency class that has at least one issue point.

20. The method of claim 1 wherein the performance data includes sample counts of the instructions, and further comprising:

removing sample anomalies;

ideally scheduling the instructions of the program to determine the minimum number of cycles required to issue each instruction of the program, the minimum number of cycles including the number of static stall cycles incurred by each instruction during issuance;

normalizing the sample counts for each instruction by dividing the sample counts for each instruction by the minimum number of cycles required to issue that instruction;

determining the execution frequency for each equivalence class using the normalized sample counts, the execution frequency being proportional to the number of times each instruction was retired;

dividing the sample count of each instruction by the execution frequency of the equivalence class of that instruction to determine the average number of cycles required to issue the instruction; and

determining the number of dynamic stall cycles incurred by each instruction of the program by subtracting the minimum number of cycles of each instruction from the average number of cycles for that instruction.

21. The method of claim 1 further comprising the steps of:

concurrently issuing, during a single processor cycle, multiple instructions from an issue queue; and

identifying a particular one of the multiple concurrently issued instructions at the head of the issue queue as an issue point.

22. The method of claim 21 further comprising the steps of:

providing an instruction scheduler with an input array of the instructions of the program to produce an ideal schedule of the instructions and static dependencies of the ideal schedule of the instructions;

determining for each node and arc of the control flow graph the execution frequency and a confidence value of the execution frequency for each node and arc;

grouping nodes and arcs having identical execution frequencies into the same equivalence class; and

determining for each instruction the number of cycles that instruction is expected to be at the head of the issue queue.

23. The method of claim 21 wherein the performance data includes sample counts of each instruction, and further comprising the step of:

setting the execution frequency of a particular equivalence class to zero if the particular equivalence class includes at least one issue point, and all instructions of that particular equivalence class have a sample count of zero.

24. The method of claim 1 further comprising:

applying a constraint solver to the estimated execution frequencies to revise the estimated execution frequencies.

25. The method of claim 1 further comprising:

averaging the performance data for the instructions that have the same execution frequency to reduce the statistical variation of the performance data.

26. The method of claim 1, further comprising the step of:

determining the average number of cycles required to issue each instruction of the program based on the collected performance data and determined execution frequency for that instruction.

27. The method of claim 1, further comprising the step of:

determining a minimum number of cycles required to issue each instruction of the program; and

wherein the estimated execution frequency for each instruction is based on the determined minimum number of cycles for that instruction.

28. The method of claim 1, further comprising the step of:

determining a number of dynamic stalls incurred while issuing each instruction of the program depending on the estimated execution frequency for that instruction.

29. A computerized method for analyzing the performance of a computer system executing instructions of a program, comprising the steps of:

analyzing the program to determine equivalence classes of instructions, each equivalence class containing instructions that have the same execution frequency as each other instruction in that equivalence class;

collecting performance data while executing the instructions of the program; and

estimating, based on the collected performance data and equivalence classes, the number of cycles required to issue each of the instructions of the program to a processor of the computer system.

30. The method of claim 29, further comprising the step of:

determining a number of dynamic stalls incurred while issuing each instruction of the program depending on the number of cycles required to issue that instruction.