Probabilistic framework for the highly efficient correlation of call chains with hardware events

• US 8,280,683 B2
• Filed: 07/17/2008
• Issued: 10/02/2012
• Est. Priority Date: 07/17/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Finkler, Ulrich Alfons
• Primary Examiner(s): Bui, Bryan
• Application Number:
  US12/175,057
• Publication Number:
  US 20100017791A1
• Time in Patent Office: 1,538 Days
• Field of Search: 702/179, 702/181, 717/145, 717/158
• US Class Current: 702/179
• CPC Class Codes: G06F 11/3409 for performance assessment
• 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 11/3636 by tracing the execution of the program
• CPC Class Codes: G06F 2201/81 Threshold
• CPC Class Codes: G06F 2201/86 Event-based monitoring
• CPC Class Codes: G06F 2201/865 Monitoring of software
• CPC Class Codes: G06F 2201/88 Monitoring involving counting

Abstract

A system and method for correlation of resources with hardware events includes event driven sampling a call chain of functions to determine when functions of the call chain are active. The call chain is mapped to execution times based upon a probabilistic integration of the functions such that when portions of the call chain are active, resources associated with call chain activity are correlated with hardware events.

Claims

1. A method for correlation of resources with hardware events, comprising:

sampling a function call chain to determine when functions of the function call chain are active; and

mapping, using a processor, the function call chain to hardware events based upon a probabilistic integration of the functions such that when portions of the function call chain are active, resources are associated with function call chain activity.

2. The method as recited in claim 1, wherein numerical analysis of event driven sampling data is performed such that one standard deviation error estimate declines proportional to 1/N where N is a total number of samples.

3. The method as recited in claim 1, wherein mapping includes employing a Koksma-Hlawka inequality error estimate, which is bound by a product of the variance of an integrated function in the function call chain and a discrepancy of a sequence of functions in the function call chain (V(f)D_N(x₁, . . . , x_n).

4. The method as recited in claim 1, wherein the probabilistic integration of the functions includes a Monte Carlo integration based on mapping event driven sampling points through a coordinate transformation to a pseudo-random sequence.

5. The method as recited in claim 4, wherein a selection of the coordinate transformation creates a quasi-random sequence of minimal discrepancy.

6. The method as recited in claim 1, wherein mapping includes mapping the function call chain to resource use based on the function call chain which is active at a given sampling point to correlate the resource use changes measured at this sampling point with the function call chain.

7. The method as recited in claim 1, wherein the hardware events include memory allocations or deallocations, the method further comprising profiling contributions from the function call chain by summing the memory usage over time using numerical integration to provide a memory usage function M(t).

8. The method as recited in claim 1, further comprising counting a sample that hits the function call chain as a zero error contribution for all other call chains and employing an error estimate to associate the sample with the function call chain.

9. The method as recited in claim 8, wherein the error estimate is proportional to variance, the method further comprising reducing variance to sample relevant regions more frequently by using importance sampling.

10. The method as recited in claim 1, further comprising developing a profiling strategy based on a measurement type wherein the measurement types include at least one of a current value, an integrated value and an average value of a parameter to be profiled.

11. The method as recited in claim 1, further comprising developing a profiling strategy based on a trigger of a measurement type wherein the triggers include at least one of periodic sampling, random sampling, a specific event, an integration threshold and a differentiation threshold of a parameter to be profiled.

12. A computer readable storage medium comprising a computer readable program for correlation of resources with hardware events, wherein the computer readable program when executed on a computer causes the computer to perform the steps of:

sampling a function call chain to determine when functions of the function call chain are active; and

mapping, using a processor, the call chain to hardware events based upon a probabilistic integration of the functions such that when portions of the function call chain are active, resources are associated with function call chain activity.

13. The computer readable storage medium as recited in claim 12, wherein numerical analysis of event driven sampling data is performed such that one standard deviation error estimate declines proportional to 1/N where N is a total number of samples.

14. The computer readable storage medium as recited in claim 12, wherein mapping includes employing a Koksma-Hlawka inequality error estimate, which is bound by a product of the variance of an integrated function in the function call chain and a discrepancy of a sequence of functions in the function call chain (V(f)D_N(x₁, . . . , x_N).

15. The computer readable storage medium as recited in claim 12, wherein the probabilistic integration of the functions includes a Monte Carlo integration based on mapping event driven sampling points through a coordinate transformation to a pseudo-random sequence.

16. The computer readable storage medium as recited in claim 15, wherein a selection of the coordinate transformation creates a quasi-random sequence of minimal discrepancy.

17. The computer readable storage medium as recited in claim 12, wherein mapping includes mapping the function call chain to resource use based on the function call chain which is active at a given sampling point to correlate the resource use changes measured at this sampling point with the function call chain.

18. The computer readable storage medium as recited in claim 12, wherein the hardware events include memory allocations or deallocations, the method further comprising profiling contributions from the function call chain by summing the memory usage over time using numerical integration to provide a memory usage function M(t).

19. The computer readable storage medium as recited in claim 12, further comprising counting a sample that hits the function call chain as a zero error contribution for all other call chains and employing an error estimate to associate the sample with the function call chain.

20. The computer readable storage medium as recited in claim 19, wherein the error estimate is proportional to variance, the method further comprising reducing variance to sample relevant regions more frequently by using importance sampling.

21. The computer readable storage medium as recited in claim 12, further comprising developing a profiling strategy based on a measurement type wherein the measurement types include at least one of a current value, an integrated value and an average value of a parameter to be profiled.

22. The computer readable storage medium as recited in claim 12, further comprising developing a profiling strategy based on a trigger of a measurement type wherein the triggers include at least one of periodic sampling, random sampling, a specific event, an integration threshold and a differentiation threshold of a parameter to be profiled.

23. A system for correlation of resources with hardware events, comprising:

a program module stored on computer readable storage media and configured map resources to call chains, the program module comprising;

a sample module configured to sample a function call chain to determine when functions of the function call chain are active; and

a mapper configured to map the function call chain to hardware events based upon a probabilistic integration of the functions such that when portions of the function call chain are active, resources are associated with function call chain activity.

24. The system as recited in claim 23, wherein the mapped mapper enforces a Koksma-Hlawka inequality error estimate, which is bound by a product of the variance of an integrated function in the call chain and a discrepancy of a sequence of functions in the call chain (V(f)D_N(x₁, . . . , x_N), wherein a sample that hits the function call chain is counted as a zero error contribution for all other call chains and an error estimate associates the sample with the function call chain.

25. The system as recited in claim 23, wherein the probabilistic integration of the functions includes a Monte Carlo integration based on mapping event driven sampling points through a coordinate transformation to a pseudo-random sequence, wherein a selection of the coordinate transformation creates a quasi-random sequence of minimal discrepancy.