Computer method and apparatus for analyzing program instructions executing in a computer system

• US 6,009,514 A
• Filed: 10/30/1998
• Issued: 12/28/1999
• Est. Priority Date: 03/10/1997
• Status: Expired due to Term

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Henzinger, Monika Hildegard, Sites, Richard L., Weihl, William Edward, Leung, Shun-Tak Albert, Vandevoorde, Mark T.
• Primary Examiner(s): Lim, Krisna
• Application Number:
  US09/183,734
• Time in Patent Office: 424 Days
• Field of Search: 712/216, 712/219, 712/236, 714/37, 714/47
• 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 an instruction of a program executing in a computer system, comprising the steps of:

determining an average number of cycles incurred to issue the instruction dependent on a sample count collected for the instruction;

determining a number of stall cycles incurred while issuing the instruction dependent on the determined average number of cycles and a predetermined minimum number of cycles for the instruction; and

determining and providing reasons for the stall cycles.

2. A computerized method as claimed in claim 1, wherein the instruction is an operating system instruction.

3. A computerized method as claimed in claim 1, wherein the instruction is an application program instruction.

4. A computer system comprising:

a central processing unit connected to a memory system by a bus; and

a performance analysis routine located in the memory system responsive to a request for analyzing an instruction of a program executing in the central processing unit, which;

determines an actual number of cycles incurred to issue the instruction dependent on an sample count for the instruction;

determines a number of stall cycles incurred while issuing the instruction dependent on the determined actual number of cycles and a predetermined number of cycles for the instruction; and

determines and provides reasons for the stall cycles.

5. A computerized method for pre-execution analysis of a program 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 procedures, each instruction of a particular block being executed an identical number of times so that the instructions of the basic block form an equivalence class of instructions;

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

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