System for and method of capturing application characteristics data from a computer system and modeling target system

1. A method of gathering memory usage information for a program of instructions, the method, executed by a processor and including the steps of:

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

selecting a set of operations from said sequence of operations;

monitoring respective operations of said set of operations;

recording access information associated with respective operations of said set of operations and identifying one or more memory objects being accessed by respective ones of said set of operations;

enabling a watchpoint mechanism operable to detect one or more next operations accessing one or more of said memory objects; and

recording access information about said next operations, the access information recorded includes an estimation of a duration between respective ones of said set of selected operations and corresponding ones of said next operations.

2. The method according to claim 1 wherein said step of recording access information further includes recording at least one of:

an identity of one or more of said monitored operations;

an identity one or more of said next operations; and

an identity of said one of more memory objects being accessed.

3. The method according to claim 1 wherein said step of enabling a watchpoint mechanism includes enabling a hardware device to provide a signal indicative of said next operations accessing said one or more of said memory objects.

4. The method according to claim 1 wherein said step of enabling a watchpoint mechanism includes enabling an externally provided trap mechanism to detect said one or more next operations accessing said one or more of said memory objects.

5. The method according to claim 1 wherein said step of recording further includes recording an association between respective ones of said set of operations and their corresponding next operations.

6. The method according to claim 5 further comprising the step of recording the context identifier (CID) of respective ones of the said associated operations.

7. The method according to claim 1 wherein said selecting step further includes enabling an imprecise hardware trap with a maximum skid of S operations to signal S operations before one of said next operations is executed, and to advance the execution using a technique having less skid, until said one next operation is reached.

8. The method according to claim 1 wherein said step of selecting the said set of operations to be monitored includes executing a phase detection algorithm.

9. The method according to claim 1 wherein a plurality of said steps are implemented by modifying the stream of instructions the first time said instructions are executed in the said sequence.

10. The method according to claim 1 wherein information about several different memory object sizes are monitored in parallel for each of said operations of said set of operations.

11. The method according to claim 1 wherein said step of selecting a set of operations includes dynamically adjusting a ratio of operations to be monitored such that said ratio is increased the longer the program is running.

12. The method according to claim 1 wherein said step of recording access information about said selected set of operations further comprises recording one or more pieces of information selected from the group consisting of:

identities of said selected operations;

identities of said memory objects;

memory addresses being accessed;

identities of memory operations following next after respective ones of said selected set of operations; and

identities of memory operations preceding before respective ones of said selected set of operations.

13. The method according to claim 1 wherein said step of recording access information about said next operations further comprises recording one or more pieces of information selected from the group consisting of:

identities of said next operations;

identities of said memory objects;

memory addresses being accessed;

identities of memory operations following next after respective ones of said next operations; and

identities of memory operations preceding before respective ones of said next operations.

14. The method according to claim 1 wherein said sequence of operations is executed and the instructions of said program of instructions constitutes contents of said memory objects.

15. The method according to claim 1 further including estimating an amount of memory objects used by the sequence, of instructions including the steps of:

estimating a fraction of said monitored instructions for which no next instruction is detected; and

multiplying said fraction with a total number of said operations executed by said sequence of instructions.

16. A method of estimating a cache miss rate for a cache system, the method executed by a processor and including the steps of:

executing a sequence of accesses to a memory system;

recording reuse distance information for a selected fraction of said memory accesses of said sequence;

solving an unknown miss rate variable from an equation equating the total number of memory accesses multiplied by the said miss rate, with a number of unique memory objects in the said sequence plus a sum of the miss probabilities for the said selection fraction of memory accesses divided by the said fraction; and

obtaining the cache miss rate by subtracting a cold miss rate from a value of said miss rate variable.

17. The method according to claim 16 wherein said step of solving an unknown miss rate variable includes modeling a miss probability of second memory access as a function of miss rate, reuse distance, cache size and cache line size.

18. The method according to claim 16 wherein said step of solving for an unknown miss rate variable includes estimating a miss probability including the steps of:

calculating a probability that a memory object remains in a cache after one cache replacement, as one minus the inverted number of possible locations in the cache that the said memory object can occupy;

calculating the expectation of the number of cache replacement between two subsequent accesses to the same memory object as the reuse distance times the miss rate; and

calculating the probability that a memory object does not remain in the cache after said expectation of the number of cache replacements, as one minus the said cache miss probability after one miss raised to the power of the said expectation of the number of cache replacements.

19. A method of estimating a number of unique memory objects accessed for a segment of a program of instructions including the steps of:

executing said program and estimating a representative reuse distance distribution for memory operations of said segment;

estimating an amount of memory operations performed during said segment;

for each natural number between said amount and the number one, using said reuse distance distribution to calculate a probability a memory operation of said distribution has a reuse distance larger than said natural number;

adding all said probabilities together; and

estimating a miss rate of a cache with LRU replacement strategy, including

finding, a smallest reuse distance value for which a number of unique memory objects is larger than the number of memory objects that can be stored in the cache; and

calculating a fraction of said memory operations of said reuse distribution with a reuse value larger than said number of memory objects that can be stored in the cache.

20. An apparatus for gathering memory usage information for a program of instructions, said apparatus comprising:

a processor operating to execute a sequence of operations in response to said program;

selecting logic to select a set of operations from said sequence of operations, the selecting logic including logic to dynamically adjust a ratio of operations to be monitored such that said ratio is increased the longer the program is running;

monitoring logic to monitor respective operations of said set of operations;

a first memory to store access information associated with respective operations of said set of operations including an identify one or more memory objects being accessed by respective ones of said set of operations;

a watchpoint mechanism operable to detect one or more next operations accessing one or more of said memory objects; and

a second memory to store access information about said next operations.

21. The apparatus according to claim 20 wherein said first memory stores said access information about said next operations including one or more pieces of information selected from the group consisting of:

identities of said next operations;

identities of said memory objects;

memory addresses being accessed;

identities of memory operations following next after respective ones of said next operations; and

identities of memory operations preceding before respective ones of said next operations.

22. A non-transitory computer readable medium comprising code for gathering memory usage information, said code comprising instructions for:

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

selecting a set of operations from said sequence of operations;

monitoring respective operations of said set of operations;

recording access information associated with respective operations of said set of operations and identifying one or more memory objects being accessed by respective ones of said set of operations;

enabling a watchpoint mechanism operable to detect one or more next operations accessing one or more of said memory objects;

recording access information about said next operations; and

estimating an amount of memory objects used by the sequence of operations, the estimating including:

estimating a fraction of said monitored instructions for which no next instruction is detected; and

multiplying said fraction with a total number of said operations executed by said sequence of instructions.