System for and Method of Capturing Performance Characteristics Data From A Computer System and Modeling Target System Performance

• US 20080244533A1
• Filed: 03/26/2008
• Published: 10/02/2008
• Est. Priority Date: 03/26/2007
• Status: Active Grant

• Current Assignee: Rogue Wave Software Incorporated (Perforce Software Incorporated)
• Original Assignee: Acumem AB (Perforce Software Incorporated)
• Inventors: Nilsson, Mats, Berg, Erik, Hagersten, Erik, Zeffer, Hakan, Petterson, Mikael, Vesterlund, Magnus
• Granted Patent: US 8,539,455 B2
• Time in Patent Office: Days
• US Class Current: 717/128
• CPC Class Codes: G06F 11/3447 Performance evaluation by modeling
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning
• CPC Class Codes: G06F 2201/88 Monitoring involving counting
• CPC Class Codes: G06F 2201/885 Monitoring specific for caches

Abstract

A system for, method of and computer program product captures performance-characteristic data from the execution of a program and models system performance based on that data. Performance-characterization data based on easily captured reuse distance metrics is targeted, defined as the total number of memory references between two accesses to the same piece of data. Methods for efficiently capturing this kind of metrics are described. These data can be refined into easily interpreted performance metrics, such as performance data related to caches with LRU replacement and random replacement strategies in combination with fully associative as well as limited associativity cache organizations. Methods for assessing cache utilization as well as parallel execution are covered.

Claims

1. A method of recording memory usage information for a program of instructions including the steps of:

starting to execute a sequence of operations in response to said program of instructions;

selecting a set of operations from said sequence of operations;

recording memory usage information associated with respective operations of said set of operations;

wherein at least one of said steps of starting, selecting and recording is implemented by modifying said sequence of operations after the execution has started to provide a modified sequence of operations having functionality enabling said at least one step; and

wherein said modified sequence of operations is re-modified again to remove said enabling functionality after at least one of said steps of starting, selecting and recording has been performed so as to provide a re-modified sequence of operations.

2. The method according to claim 1 wherein said re-modified sequence of operations executes faster than said modified sequence of operations.

3. The method according to claim 1 wherein said re-modification is performed in response to a completion of activity of at least one of said steps of starting, selecting and recording.

4. The method according to claim 1 wherein said re-modification is performed after it has been determined that at least one of said steps of starting, selecting and recording should not presently be performed.

5. The method according to claim 4 wherein said re-modified sequence of operations is identical to said sequence of operation of said program of instructions.

6. The method according to claim 1 wherein said step of recording memory usage information further includes recording an identity of an instruction of said program corresponding to a selected operation of said selected set of operations.

7. The method according to claim 1 wherein said step of recording memory usage information further includes recording an identity of a data object accessed by a selected operation of said selected set of operations.

8. The method according to claim 1 wherein said sequence of operations are partitioned into groups of operations and at least one group of said groups of operation is re-modified between executing two such said groups of operations.

9. A method of reconstructing a sequence of instructions executed by a program of instructions including the steps of:

starting to execute a sequence of operations in response to said program of instructions;

selecting a set of operations from said sequence of operations; and

,

recording memory usage information associated with respective operations of said set of operations from which several partial sequences of said sequences of instructions can be determined;

determining one of said partial sequences wherein a first sequence of instructions is followed by a second sequence of instructions;

determining that said second sequence of instructions is followed by a third sequence of instructions; and

reconstructing a longer sequence of instructions to be said first sequence followed by said second sequence followed by said third sequence.

10. A method of identifying a cycle of instructions in a program of instructions including the steps of:

starting to execute a sequence of operations in response to said program of instructions;

selecting a set of operations from said sequence of operations;

recording memory usage information associated with respective operations of said set of operations; and

identifying a partial sequence of operations from said memory usage information;

wherein a cycle of instructions is identified to be a set of instructions corresponding to a cyclic set of operations of said partial sequence of operations that occur between a recurring operation and an immediately subsequent occurrence of said recurring operation, including said recurring operation.

11. The method according to claim 10, further including the step of counting a number of recorded instructions between the recurrences of said recurring operation and to identify said number as the number of instructions executed in said cycle of instructions.

12. The method according to claim 10, wherein said cycle of instructions is only considered if said cyclic set of operations all have some determined parts of their call stack identical.

13. The method according to claim 10, wherein said step of identifying a partial sequence of operations includes identifying a plurality of sequences of operations and combining said plurality of sequences to form said partial sequence.

14. The method according to claim 13, wherein the cycle is selectively terminated in response to said immediately subsequent operation having a part of its corresponding call stack in common with a call stack corresponding to an earlier occurrence of said recurring operation.

15. A method of identifying data-chained instructions in a program of instructions including the steps of:

starting to execute a sequence of operations in response to said program of instructions;

selecting a set of operations from said sequence of operations;

recording memory usage information associated with respective operations of said set of operations; and

based on said memory usage information, detecting an identity of a first operation of said sequence of operations accessing a data object and an identity of a second operation of said sequence of operations accessing said data object so as to identify data-chained instructions.

16. The method according to claim 15 wherein a third operation associated with a third instruction is identified as accessing a same data object as either said first or said second operation and, in response, determining that said third instruction is data-chained on the instructions corresponding to said first and said second operation.

17. The method according to claim 16 wherein said data-chain property is only identified in response to said first, second and third operations all having at least a portion of their call stacks identical.

18. The method according to claim 17 wherein the data chain is recursively extended to comprise and identify instructions belonging to the same data chain.

19. The method according to claim 18 wherein it is further determined that the data object accessed by a write instruction can be used to identify the data structure accessed by a read instruction, if said write instruction and said read instruction belong to the same data chain.

20. The method according to claim 18 wherein it is further determined that the a first operation and a second operation are data dependent if they belong to the same data chain and at least one of said operations is of write type.

21. A method of detecting performance shortcomings for a program of instructions including the steps of:

starting to execute a sequence of operations in response to said program of instructions;

selecting a set of operations from said sequence of operations;

recording memory usage information associated with respective operations of said set of operations;

based on said memory usage information determining for a part of said program of instructions corresponding to said set of operations, at least one of the following properties;

(i) temporal reuse distance,

(ii) spatial reuse distance,

(iii) spatial usage; and

,

based on at least one of said properties determining a performance shortcoming of said program of instructions.

22. The method according to claim 21, wherein:

said selection of set of operations corresponds to a subset of instructions of said program;

wherein said subset of instructions comprises either (i) a single instruction or (ii) several instructions belonging to the same cycle of instructions and further are determined to be data-chained; and

,

wherein said at least one property and said performance shortcoming are attributed to said subset of instructions.

23. The method according to claim 22, wherein said performance shortcoming is determined to be poor spatial usage if said property spatial usage, for said subset of instructions, is determined to be below a threshold.

24. The method according to claim 23, wherein said spatial locality is with respect to some specific cache size.

25. The method according to claim 22, wherein said performance shortcoming is determined to be completely inefficient loop nesting, if for all said subsets of instructions of a loop, the respective said property spatial locality is lower than a threshold.

26. The method according to claim 22, wherein said performance shortcoming is determined to be partially inefficient loop nesting if said spatial reuse distance, for said subset of instructions, is higher than a threshold.

27. The method according to claim 22, wherein said performance shortcoming is determined to be sparse data layout if said property spatial locality, for said subset of instructions, is lower than a threshold when evaluated for infinitely large caches.

28. The method according to claim 21, wherein said performance shortcoming is determined to be an unused data reuse blocking opportunity, said method further comprising the steps of:

identifying a spatial or temporal reuse of a data object from one instruction to itself or to another instruction in the same loop; and

,

establishing that either of said properties of spatial reuse distance or temporal reuse distance for said reuse of a data object is greater than a threshold.

29. The method according to claim 21, wherein said performance shortcoming is determined to be unused data reuse loop fusion opportunity, said method further comprising the steps of:

identifying a spatial or temporal reuse of a data object from an instruction in a first loop to an instruction in a different second loop; and

establishing that either of said properties spatial or temporal reuse distance of said reuse of a data object is above a certain threshold.

30. The method according to claim 21, wherein a predetermined type of said performance shortcoming is used to select a corresponding passage in a manual.