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

[0001] 1. Technical Field

[0002] The present invention relates to program profiling and more particularly to a system and method for profiling resource use with correlated hardware events.

[0003] 2. Description of the Related Art

[0004] Profiling is an essential and widely used technique to understand the resource use of applications. While efficient tools for the profiling of execution time are available, the choices for detailed profiling of other hardware resources, e.g. cache misses or memory use are very limited or non-existent.

[0005] There is a rich body of literature on sampling and profiling. Typical time profilers sample periodically the sub-routine or code line and instrument each function call. The function call counts are used to reconstruct a call graph. Location based sampling can provide very misleading results. One approach gathers more context by keeping track of the call history. While providing more accurate results, it requires the instrumentation of all function calls analogous to Gprof and book-keeping to track the history, which causes significant overhead. Gprof is an open source profiling program known in the art. Using Gprof often increases execution time by a factor of two or more.

[0006] The memory profiling tools found in the art can be classified into several categories. There are tools with little impact on execution time and memory use which sample the so-called high water mark over time (e.g., the Unix tool top). This is clearly insufficient to localize bottlenecks in large applications. The strategy of sampling at periodic time intervals is not applicable to profiling of memory use by code location or call chain. The performance impact of sampling the state of the heap is too costly and significant errors are possible due to the lack of correlation between memory use and execution time. An application can allocate and deallocate a significant amount of memory in a very short period of time.

[0007] Another category of tools records every allocation and deallocation. If only the code location is sampled, the results can be misleading. Furthermore, the execution time can be several times larger than for an unprofiled run. The recording of entire call chains improves the profiling information, but causes even more overhead. This category provides correct attribution of memory use to call chains, but the memory use analysis is only possible at singular snapshots during the program. It is difficult to hit the interesting spots in large applications that run for many hours. The allocation/deallocation category often increases the runtime of a program by an order of magnitude and also increases the memory use of the application by a factor of two or more rendering it useless for very large applications.

[0008] “Rational Purify” shows similar increases in execution time and memory usage. These tools investigate memory access errors and other problems in small and short program runs, but they are not well suited for the investigation of the memory use of application runs that already require significant time and which already push the memory capacity of a system to its limit without profiling.

[0009] Another common approach is simulation based on code or program traces, which allows detailed analysis of applications but causes far too much execution time overhead for the performance analysis of very large applications. A low overhead sampling approach for memory leak detection has been proposed for sampling code segments adaptively at a rate inversely proportional to their execution frequency. This is not applicable for memory usage due to the lack of correlation of memory usage with execution time or execution frequency. While memory leaks persist after creation, memory allocations have a limited life time.

[0010] Profiling is widely used technique to understand the resource use of applications. While efficient tools for the profiling of execution time are available, the choices for detailed profiling of other hardware resources, e.g., cache misses or memory use are very limited. In the present disclosure, tools are provided with sufficiently accurate insight without adding unacceptable overhead in memory use and execution time for the performance analysis of very large applications.

[0011] In this disclosure, a highly efficient probabilistic method for profiling that provides detailed resource usage information indexed by a full call chain and time is presented. An analytical framework with error estimates permits analyses of different profiling scenarios. This probabilistic approach was employed to implement a memory profiling tool that adds minimal overhead and does not require recompilation or relinking. A tool in accordance with the present principles provides the memory use M_ψ(t) of each call chain ψ over a time line. Experimental results confirm that execution time and memory overhead is less than 10% of the unprofiled, optimized execution.

[0012] A system and method for correlation of resources with hardware events includes sampling a call chain of functions at events 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.

[0013] A system for correlation of resources with hardware events includes a program module stored on computer readable media and configured map resources to call chains. The program module includes a sample module configured to sample a call chain of functions at intervals to determine when functions of the call chain are active; and a mapper configured to map the call chain to hardware events based upon a probabilistic integration of the functions such that when portions of the call chain are active, resources are associated with call chain activity.

[0014] These and other features and advantages will become apparent from the following detailed description of illustrative embodiments thereof, which is to be read in connection with the accompanying drawings.

[0026] Highly efficient probabilistic systems and methods for profiling are provided that include detailed resource usage information indexed by full call chain and time. A call chain is the history of function calls formed when one method calls another method. An analytical framework is provided with estimates of the accuracy for different profiling scenarios. This probabilistic approach is applicable to implement a memory profiling tool that adds minimal overhead and does not require recompilation or relinking. The tool provides the memory use of each call chain over a time line. An upper bound can be provided for the memory overhead compared to an unprocessed run, and experimental results confirm that execution time and memory use overhead is less than 10% of the unprofiled, optimized execution.

[0027] A novel probabilistic profiling approach for general resource use is provided that permits the creation of profiling tools with very small relative overhead, e.g., a small ratio of the time and memory use of the profiled run compared to the time and memory use of the unprofiled run, respectively. The general profiling mechanism permits estimation of resource use R(t) over time for all call chains ψ in a program run for a resource R, e.g., memory use. An analytic framework allows the estimation of error margins for varying scenarios, and upper bounds are provided for the memory overhead for its application in memory profiling.

[0028] A memory profiler has been implemented based on this probabilistic approach. It can be applied to an existing optimized binary without recompiling or relinking. A program run with tracing produces an overview of all call chains that allocated memory and the peak memory that each call chain used. The overview provides information about memory leaks. Additionally, a compressed trace file is created that permits extraction of the memory use of each call chain over the execution time of the program.

[0029] The memory tracing was applied to sizeable very large scale integration (VLSI) design automation applications which ran for many hours and used many GB's of memory. Additionally, worst case scenario routines were traced as well as some standard applications. The experimental results confirm very low relative overhead. Execution time and memory use of traced applications increased by less than 10% in memory and execution time compared to optimized, untraced runs. The worst case scenario experiments confirm that the execution time overhead is in the order of magnitude of the time spent in a malloc subsystem or less.

[0030] Embodiments of the present invention can take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment including both hardware and software elements. In a preferred embodiment, the present invention is implemented in software, which includes but is not limited to firmware, resident software, microcode, etc.

[0031] Furthermore, the invention can take the form of a computer program product accessible from a computer-usable or computer-readable medium providing program code for use by or in connection with a computer or any instruction execution system. For the purposes of this description, a computer-usable or computer readable medium can be any apparatus that may include, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device. The medium can be an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system (or apparatus or device) or a propagation medium. Examples of a computer-readable medium include a semiconductor or solid state memory, magnetic tape, a removable computer diskette, a random access memory (RAM), a read-only memory (ROM), a rigid magnetic disk and an optical disk. Current examples of optical disks include compact disk-read only memory (CD-ROM), compact disk-read/write (CD-R/W) and DVD.

[0032] A data processing system suitable for storing and/or executing program code may include at least one processor coupled directly or indirectly to memory elements through a system bus. The memory elements can include local memory employed during actual execution of the program code, bulk storage, and cache memories which provide temporary storage of at least some program code to reduce the number of times code is retrieved from bulk storage during execution. Input/output or I/O devices (including but not limited to keyboards, displays, pointing devices, etc.) may be coupled to the system either directly or through intervening I/O controllers.

[0033] Network adapters may also be coupled to the system to enable the data processing system to become coupled to other data processing systems or remote printers or storage devices through intervening private or public networks. Modems, cable modem and Ethernet cards are just a few of the currently available types of network adapters.

[0034] An illustrative program shows an extraction of a Gprof-report. The program will be employed to demonstrate context dependency in accordance with the present principles.

[0035] Program A:

[0036]

	extern int fa(unsigned size) {
	unsigned j,tmp=0;
	for (j=0;j<size;j++) {
	tmp+=j; tmp = tmp%5555555;
	}
	}
	extern int fsmall(unsigned size) {
	return fa(size);
	}
	extern int flarge(unsigned size) {
	return fa(size);
	}
	int main(void) {
	unsigned j, tmp;
	for (j=0;j<1000;j++) {
	tmp += fsmall(10);
	tmp += flarge(1000000);
	}
	return tmp;
	}
	index %time self children called name
	[1] 100.0	0.00 65.56       main[1]
		0.00 32.78 1000/1000 fsmall[4]
		0.00 32.78 1000/1000 flarge[3]

[0037] For any form of time profiling the accuracy of the mapping of fractions of the execution time to the program structure is one important consideration. Often a program spends a significant amount of time in a single routine, but this routine is used in different contexts. Thus, profilers like Gprof provide execution time estimates for a call graph, not only for subroutines.

[0038] In program A, Gprof reports that the functions fsmall and flarge require similar amounts of time, but flarge performs 100000 times more operations than fsmall.

[0039] Referring now to the drawings in which like numerals represent the same or similar elements and initially to FIG. 1, a call graph for program A and costs assigned to nodes when binning samples by call location are illustratively shown. In this case binning samples by call location are provided by a subroutine on top of a stack. To establish the call graph, Gprof uses the counts of function calls and assumes that all calls to one function f require the same amount of time. This assumption is often incorrect. The call graph for program A shows how cost is assigned to the nodes. For nodes, main and fa, the cost is 1000010000, and for nodes, fsmall and flarge, the cost in 500005000.

[0040] As this example demonstrates, the execution time of a particular call to a function f may strongly depend on its context. Memory profiling based on call location (e.g., code line or function call etc.) is affected by the same problem. Often the majority of the memory is allocated by a few standard containers that are employed in many different contexts. This is demonstrated by a second example, program B.

[0041] The Valgrind-tool Massif, which is known in the art, is aware of the call chains (the output shown below program B was run with −depth-10), but similar to Gprof it attributes roughly the same amount of resource to fsmall and flarge although it considers call chains of a depth up to 10.

[0042] Program B with extract from Massif-report run with −depth=10:

[0043]

	typedef int *Basetype;
	unsigned findex=0;
	Basetype field[2100000];
	extern int *fa1(unsigned size) {
	return field[findex++] = new int [size];
	}
	extern int *fatop(unsigned size) {
	return fa1(size);
	}
	extern int *fsmall(unsigned size) {
	return fatop(size);
	}
	extern int *flarge(unsigned size) {
	return fatop(size);
	}
	int main(void) {
	int j, *tmp;
	for (j=0;j<1000000;j++) {
	tmp = fsmall(2);
	tmp = flarge(100);
	}
	return (int)tmp;
	}

==3===========================
Context accounted for 49.8% of measured spacetime
0x80484C3: fa1(unsigned)
0x80484F3: fatop(unsigned)
0x8048520: flarge(unsigned)
Called from: 49.8%: 0x8048564: main
---------------------------------
Context accounted for 47.7% of measured spacetime
0x80484C3: fa1(unsigned)
0x80484F3: fatop(unsigned)
0x8048520A: fsmall(unsigned)
Called from: 47.7%: 0x8048554: main

[0044] Full Call Chains: The two examples Program A and Program B demonstrate that the binning of profiling information based on the function call or code line (location) can be misleading. We found that this is the case in particular for very large applications that heavily use standardized containers, e.g., STL.

[0045] For the profiling of execution time, there exists an alternative which causes very low impact and produces accurate assignments of runtimes to call chains, the binning of profiling information by the full call chain. For example, each single sampling event is attributed with the entire call chain present on the stack at the time the sample is taken.

[0046] Monte Carlo Execution Analysis (MCXA) uses this technique, sampling the entire stack of a process or thread at fixed time intervals. The sampling is possible on optimized code since no instrumentation to determine call counts is necessary. In particular, for long running programs, MCXA can use large sampling intervals and thus minimize the execution impact, such that the execution time only grows by a few percent compared to an optimized and unprofiled run. The measured times provided by MCXA are not only much more accurately mapped to call chains when compared to Gprof, they also correlate very closely to the execution time of the optimized code without profiling.

[0047] Referring to FIG. 2, a call tree and costs assigned to nodes for program A are shown when binning samples by call chain. For each path in the call graph there is one leaf node. FIG. 2 shows the call tree for program A and how MCXA assigns costs to nodes (main, fsmall, fa, flarge, fa) based on binning samples by call chain. Note that sampling by call chain cannot be done by considering only the call graph. It is necessary to consider the call tree, which is in general much larger. For each call chain, costs (e.g., at the node main costs include: 1000010000, at each of leaf node in the chain, fsmall and fa, costs include: 10000, and at each leaf node in the chain, flarge and fa costs include: 10⁹) are assigned to a unique leaf node. MCXA profiling of execution time inspired the wish for a similar profiling tool for more general resources, in particular memory use.

[0048] Sampling and Numerical Integration: Many profiling tools use sampling at fixed time intervals. Gprof samples the top of the stack in periodic intervals to determine which function is currently executed and additionally counts how often each function is called. The top of the stack specifies a ‘program counter location’, e.g., the subroutine in which the counter resides or the line number in the code.

[0049] Referring to FIG. 3, a periodic sampling of program counter location is interpreted as a sequence of numerical integrations for call locations A, B, C, D (i.e. chain, function or code line).

[0050] At each point in time during the lifetime of a program or thread exactly one program counter location ψ (e.g. a function or code line) is active. This can be interpreted as a sum of functions:

[0051] $\sum _{\psi }{p}_{\psi }\left(t\right)\mathrm{with}{p}_{\psi }\left(t\right)=\{\begin{array}{cc}1& \mathrm{if}\psi \mathrm{active}\\ 0& \mathrm{otherwise}\end{array}$
for each code location ψ. A code location ψ of the program is called active if it is on top of the stack. This interpretation of execution time sampling explains how well execution time is attributed to the various locations ψ by periodic sampling.

[0052] Profiling attempts to determine the time T for which a code location ψ is active.

[0053] $T=\sum _{\psi }{T}_{\psi }$
is the total execution time of the program since only one subroutine can be at the top of the stack at any given time. Then,

[0054] $T_{\psi }={\int }_0^T{p}_{\psi }\left(t\right)dt$
is the total time that location ψ was active.

[0055] Sampling at periodic time intervals τ can be interpreted as a numerical integration, e.g. as an extended trapezoidal rule

[0056] $T_{\psi }\approx \tau \left(\frac{p_{\psi }\left(\tau \right)}{2}+p_{\psi }\left(2\tau \right)+p_{\psi }\left(3\tau \right)\dots +\frac{p_{\psi }\left(N\tau \right)}{2}\right)+O\left(\frac{{\mathrm{Tp}}_{\psi }^{″}}{N^2}\right).$

[0057] The error bound provided by any (extended) Newton-Cotes formula is not really useful in this case since it contains a derivative of p_ψ(t) which has singularities.

[0058] The periodic sampling can also be interpreted as a pseudoMonte-Carlo integration. Monte-Carlo integration based on a random selection of sampling points provides an approximation whose one standard deviation error estimate decreases with the square root of the number of sampling points.

[0059] $T_{\psi }\approx \frac{T}{N}\sum _{i=1}^N{p}_{\psi }\left(i\tau \right)\pm T\sqrt{\frac{<p_{\psi }>-<p_{\psi }{>}^2}{N}}$

[0060] Periodic sampling points are not random and can be considered a quasi-random sequence of minimal discrepancy, such that the one standard deviation error estimate declines proportional to 1/N instead of

[0061] $\sqrt{\frac{1}{N}}.$
Via the Koksma-Hlawka inequality the error estimate is bound by the product of the variance of the integrated function and the discrepancy of the sequence.

[0062] $\frac{1}{N}\sum _{i=1}^{N}f\left(x_i\right)-\int f\left(u\right)du\le V\left(f\right)D_N\left(x_1,\dots ,x_N\right).$
This interpretation of execution time sampling explains how well execution time is attributed to the various locations ψ by periodic sampling.

[0063] Resource Profiling: Time profiling maps a call chain ψ to the time T_ψ that is spent in ψ. More general resource profiling, e.g. memory profiling, maps a call chain ψ to a function M_ψ(t), the amount of resource that is owned by ψ at a given time t. For example, memory is called “owned” by a call chain ψ if it was allocated under ψ. Cache misses are called owned by ψ if they occurred while ψ was active.

[0064] Referring to FIG. 4, an example of changing memory ownership over time is illustratively shown to demonstrate the problem of memory profiling. Address (location) is plotted versus time. Light blocks 120 are allocated, dark blocks 130 were allocated and then deallocated, i.e., they remained on the heap. Deallocated blocks (130) may be coalesced. Call chains (designated as A, B, C, and D in FIG. 4) are shown only for program routines, not system calls (i.e., allocation).

[0065] For any point in time there can be a large number of call chains that own memory blocks. Furthermore, the ownership can change without that the total amount of memory changes. Thus, general resource profiling is significantly harder than time profiling. Memory profiling is of particular interest since it is a resource that is allocated and deallocated. Profiling, e.g., cache misses can be considered a special case in which only allocations occur.

[0066] Referring to FIG. 5, allocation events as a function over time are illustratively shown. A height of peaks 140 reflects the size of the allocation, not the peak of a δ distribution (δ is Dirac's delta function). FIG. 5 shows another view of the problem of memory profiling. A memory operation can be considered an element s_i in an ordered set S. |s_i| is the size of the allocated block and the sign indicates allocation or deallocation.

[0067] $M\left(t\right)={\int }_0^t\sum _i\left(s_i\delta \left(\tau -t_i\right)\right)d\tau ={\int }_0^{t}B\left(\tau \right)d\tau$
is the memory use as a function of time, t is the time at which (de)allocation i occurred, and δ is Dirac's delta function, a common distribution in mathematics.

[0068] Analogous to time profiling the contributions from the call chains form a sum

[0069] $M\left(t\right)=\sum _{\psi }{M}_{\psi }\left(t\right)$
and the problem can be mapped into a series of numerical integrations. A sample that hits a call chain ψ is counted with contribution zero for all other call chains. The error estimate for a call chain provides information on how well memory usage is attributed to the different call chains. Note that this mapping holds for many other types of resource use events, e.g. cache or Table Look-aside Buffer (TLB) misses, which form discrete events over the time line. If the resource ‘density’ B(t) can be characterized by a continuous function, the numerical integration can be applied directly.

[0070] Since many systems do not correlate well with periodic sampling event driven sampling is employed in accordance with the present principles. A call chain of functions is event sampled to determine when functions of the call chain are active. The call chain is mapped to hardware events based upon a probabilistic integration of the functions such that when portions of the call chain are active, resources are associated with call chain activity. Advantageously, a coordinate transformation is performed which creates a sequence of desirable properties out of what comes from event driven sampling. This will be explained in greater detail hereinafter.

[0071] Event Space Integration: The B_ψ(t) is not a proper function but a distribution and not very suitable for numerical integration. To transform the time integral into something more suitable for numerical integration so that event driven sampling and numerical integration can be performed, we take advantage of the fact that B_ψ(t) is zero in any open interval (t_j,t_j+1). For example, to compute M(t) it is only necessary to evaluate the numerical integral at times t_j.

[0072] Referring to FIG. 6, a coordinate transformation t→γ is introduced which compresses the intervals (t_j,t_j+1) to a single point and which expands the points t_j to intervals (j−1,j] to obtain a distribution B_ψ(γ). FIG. 6 shows allocation events from FIG. 5 as depicted as a distribution. The variable γ is dimensionless. The numbers jε1 . . . N enumerate the (de)allocation operations. It holds that M_ψ(t_j)=M_ψ(j).

[0073] B_ψ(γ) is much better suited for Monte-Carlo integration.

[0074] $M\left(\gamma \right)={\int }_0^{\gamma }{\underset{\_}{B}}_{\psi }\left(\eta \right)d\eta \approx \frac{1}{N}\sum _{i=1}^N\underset{\_}{B}\left({\gamma }_i\right)\pm V\left({\underset{\_}{B}}_{\psi }\right)D_N\left({\gamma }_1,\dots ,{\gamma }_N\right).$
With equidistant sampling points over γ the error decreases like O(1/N) (pseudo-random sequence of minimal discrepancy), with random sampling points over γ the error decreases like √{square root over (N)}. This permits numerical integration techniques to be employed for hardware or activity that does not appropriately comply with a time scale. Instead, a probabilistic integration approach is employed to map activities to different scale so that numerical integration techniques can be employed.

[0075] Variance Reduction: The error estimate is proportional to the variance V(B_ψ(γ)). Locations in γ with large values of |B_ψ(γ)| are more relevant than locations with smaller values. Variance reduction changes the sampling density to sample more relevant regions more densely.

[0076] Importance sampling is a strategy to adjust sampling density relative to the relevance of the data points, here relative to |B_ψ(γ)|.

[0077] $\int fdx=\int \frac{f}{\rho }\rho dx\approx \frac{1}{N}\sum _{i=1}^N\frac{f\left(x_i\right)}{\rho \left(x_i\right)}\pm V\left(\frac{f}{\rho }\right)D_N\left(x_1,\dots x_N\right)$ $\mathrm{with}$ $\int \rho dx=1.$

[0078] The sizes of allocations, i.e., the possible values of f are integer numbers. Thus, it is possible to choose ρ(x) such that f/ρ is a constant by adjusting the sampling density ρ proportional to the block size. There is a selection of sampling points that are advantageous to implement, minimize relative impact and constitute a ρ for which f/ρ is limited by a small and controllable constant.

[0079] Scenarios: The mapping of resource use by call chain to numerical integration provides a set of tools that permits the derivation of strategies for different scenarios. One aspect that determines a particular scenario is the type of measurement that is available. A few scenarios where the present principles are applicable include: Current value, e.g. current amount of memory used; Integrated value, e.g. time spent or number of cache misses since the last measurement; Average value, e.g., average number of cycles per instruction since last measurement; Another aspect is the available trigger of a measurement, e.g., periodic sampling may be used, e.g., measure every x seconds or every y cache misses; random sampling, e.g., trigger measurements at random points with known distribution of the sampling points; event triggers, e.g., trigger a measurement event at an allocation; integration threshold, e.g., trigger a measurement each time a fixed number of events have accumulated; differential threshold, e.g., trigger a measurement each time a moving average leaves a window, e.g. ±N %.

[0080] Furthermore, the scope of the measurement plays a role. A determination of whether the measurement is performed for a process, a thread or the entire system may be made. The combination of available triggers, available types of measurement and the scope of the measurement depend on the system and the resource of interest. A few example scenarios follow to illustrate these concepts.

[0081] Time Profiling: Time profiling by call chain uses an integrated value (e.g. CPU time since last measurement) and periodic sampling (e.g., the dimension of measurement is the same as the sampling dimension). As described, this maps to a rather efficient numerical integration for a single threaded process, since we have a sequence of minimal discrepancy. Additionally, the integrated functions are limited to values of one and zero.

[0082] For a multi-threaded process, the mapping of the scope of the measurement (a process) and the desired result (CPU time per call chain) is less obvious. Now, multiple call chains can be active at one time. Performing a single measurement at periodic time intervals has to randomly select one of the call chains and assign the cumulative CPU time of all threads. When considering the entire event space, the measurements do not form a sequence of minimal discrepancy anymore. Extending the call chain by the thread id and taking one sample for each active thread at periodic times allows a reduction in the measurement error.

[0083] Cache Misses: Performance counters provide integrated measurements, e.g., the number of cache misses incurred on a core, i.e., the measurement scope does not match the desired observation scope of a process or thread. If an integration threshold is available as a trigger, the task is analogous to memory profiling as described above, except that the chain ψ has to be extended by the thread id and process id. Only periodic sampling may be available, and the correlation between time and the number of cache misses may be significant. This creates a scenario similar to time profiling. Again, ψ has to be extended by thread and process id to extract measurements for the desired scope. In this case, periodic sampling in the time domain does not provide a sequence of minimal discrepancy in the domain of interest, i.e., the number of cache misses that occurred so far.

[0084] Due to the strong correlation between elapsed time and cache misses (there is a minimum time spent per cache miss), one can construct bounds for the discrepancy of the sequence used for integration (event driven). For example, since a minimum density of sampling points per cache miss is given and sampling points in periods without cache misses do not contribute to the integral, one may argue that the error behaves at least as well as random sampling, i.e., it decreases with

[0085] $\frac{1}{\sqrt{N}},$
where N is the minimum number of sampling points per cache miss.

[0086] Memory Profiling: Memory profiling by call chain may be performed by sampling the call chain and the current amount of memory used (event driven sampling). This provides a numerical integration. There is no direct correlation between changes in memory use and time, i.e., when mapped onto the memory axis, we cannot even assume random sample points with a known distribution. Additionally, the amount of memory that is currently used may cover a wide selection of values. In short, we cannot provide a quantitative bound for the error estimate. With a different type of measurement and trigger, an error estimate and integration with a sequence of minimal discrepancy can be achieved. Below steps will be described that allow a partitioning of the problem to limit the integrated functions to values of zero and one, and to take advantage of the known correlation of allocations and deallocations. The scope of measurement is the process, since the heap (or set of heaps) of a process is instrumented.

[0087] Implementation: The more practical aspects of the probabilistic approach will now be described for the example of memory profiling with a tool called MemTrac™ in accordance with the present principles, namely, the gathering of call chains with minimal overhead and the improvement of accuracy while maintaining low relative overhead. While we are not able to improve the asymptotic behavior of the error, which decreases with 1/N, we can reduce the error by a significant constant factor.

[0088] Size Bundling: Memory profiling aims to determine M_ψ(t) with predictable accuracy and low relative overhead, e.g., the increase in total memory use and execution time is limited to a few percent of the time and memory used by an optimized and unprofiled run. Fortunately, it is not the absolute but the relative overhead per allocation operation that is of greater importance. Assume a program spends a time t_u using an allocated block B. It takes the time t_m to collect data about the allocation of the block. If t_m<<t_u, then the absolute time t_m can be large without impacting the overall performance of the program significantly.

[0089] A memory block B that was allocated is at least initialized. Thus, for the vast majority of applications there is a lower bound for the time spent on accessing a memory block B. This initialization time T_i(B) grows proportional to the size of B. As long as in the average T_i(B) is significant compared to the time necessary to record an allocation, profiling can afford to create a record of the allocation and deallocation of B.

[0090] So only for blocks B smaller than a certain threshold size S_t, the direct recording of allocation events increases the relative overhead caused by the profiling mechanism. Thus, the memory (de) allocations can be partitioned: M_ψ(t)=M_ψ^<Si(t)+M_ψ^>Si(t) such that the contribution of blocks M_ψ^>Si(t) that are larger than the threshold size is computed exactly. This reduces the range of values obtained at sample points and thus the variance of B_ψ^<Si(t) compared to the variance of B_ψ(t).

[0091] Next, we can partition the problem of approximating M_ψ^<Si(t) into a series of subproblems. The size range 1 . . . b is partitioned into n buckets of allocations of sizes s_i such that each allocation is assigned to the smallest possible bucket.

[0092] $M_{\psi }^{<S_n}\left(t\right)=\sum _{i=1}^n(M_{\psi }^{S_i}\left(t\right)+\Delta \left(S_t\right).$
M_ψ^Si(t) is the memory “owned” by call chain ψ which falls into allocations in size bucket i. The bucketing can be chosen such that the error term Δ(St) is bound by a constant fraction of the memory that is actually owned Δ(S_t)<C₁M_ψ^Si(t)

[0093] Each subproblem determines M_ψ^Si(t) for blocks of one fixed size s_i for all ψ. Since there is typically a strong correlation between call chain and allocated block sizes, this further reduces the variance of the numerical integration for each call chain.

[0094] Page Bundling: Computing the correct memory contributions from call chains above a certain threshold size and bundling smaller allocations into buckets by size corresponds well to a common allocator strategy. Bucket based allocators bundle allocation blocks from one bucket into memory pages, such that one page contributes only blocks of one size corresponding to one bucket. Allocations above a certain size threshold are handled on a per-allocation basis, e.g. by using mmap or a Cartesian tree, which are known allocation techniques.

[0095] Consider the subproblem of profiling allocations of one specific size, i.e., events from one bucket. If there are only allocations, then recording the event of a new page allocation is equivalent to sampling periodically the allocation events. If page allocations are chosen as the sampling points for allocations, the corresponding page deallocation provides a matching sampling point for deallocations. The allocation sample point assigns the entire page to the currently active call chain, and the deallocation can be assigned to the same call chain. This page bundling improves the accuracy of the memory usage estimate by properly incorporating the correlation between allocation and deallocation.

[0096] This scheme can be considered as a form of importance sampling, the sampling density varies from 100% (for block sizes above the threshold) down to a lower bound with varying numbers of blocks per page for the varying buckets. The larger the variance in B(t), the higher is the sampling density.

[0097] In terms of accuracy, if the bucket allocator that is actually used for production runs drives the choice of sampling points with its page allocations, the memory use including heap fragmentation is measured accurately by the memory profiling. Often, this is the more interesting measure for an application, since it is interested in the real resource use. Heap fragmentation includes memory use inside a heap to maintain its data structures, unused memory in blocks due to alignment requirements and marker prefixes, and memory that is held in pages that are partially free.

[0098] Online Compression: Even with the reduction of events by sampling as described above, trace file sizes and the time to write them would be prohibitive if the resulting events were recorded directly. Thus, we employ two forms of online compression that reduce the stream of sampled events to a stream of deltas (changes) associated with call chain indices. A table-based compression permits recording only a call chain index per event and a table that maps full call chains to indices. A lossy compression scheme records only accumulated deltas that may cover multiple events. For this purpose, two dictionaries may be employed.

[0099] A first dictionary, used for the lossy compression, uses call chains as keys and stores the amount currently owned for a call chain. Each allocation event for a call chain increases or decreases the amount owned. A record is only written if the change is larger than a fraction of the last recorded value as illustrated in FIG. 7. This eliminates small fluctuations that otherwise bloat the trace files with controllable impact on the accuracy.

[0100] FIG. 7 is an example for memory development (memory versus time) for a call chain showing recording points (samples) for lossy compression with a threshold of 30%. The large threshold was chosen for illustrative purposes, the threshold may be smaller in practice (e.g., 5% or less).

[0101] A second dictionary provides the mechanism to find a record of an allocating call chain based on the address of a deallocated block. The second dictionary uses the address of an allocated block as a key and holds a reference to the record of the allocating call chain as well as the block size for each block currently used. Upon deallocation the call chain record is updated and the block record deleted. Since each event carries a time stamp each update of a call chain record provides one data point for each M_ψ(t), one of which is non-zero.

[0102] The table based compression of the trace data results from recording only a call chain index from the first dictionary and recording the accumulated call chains from the first dictionary with their indices (table based compression). Note that using the page records to drive the sampling helps to limit the memory overhead due to tracing. For every used block, the tracer has to hold a block record. The block record needs 6*sizeof(void*), but the smallest allocation event to record is the bucketing threshold, in the present case of size 64*sizeof(void*). In fact, in practical applications most events are actually page allocations, in the present implementation of size 1024*sizeof(void*). Thus, the application allocates at least 10 times and on the average 100 times as much memory as the tracer needs to keep track of the blocks. The remaining memory overhead of the tracer is needed for the call chain records.

[0103] Forked Tracing: The implementation of the trace generation with lossy compression and the event generation through instrumenting a bucketing allocator is fairly straightforward. The online accounting generates a fair amount of allocations. Additionally, there are millions of dictionary lookups with rather long keys, the call chains. The most interesting traces were performed on VLSI applications (e.g., Design Rule Checking (DRC) and ‘Layout Versus Schematic’ (LVS)) checking, placement driven logic synthesis) with several hundreds of thousands of lines of code and call chain lengths of dozens of steps. Additionally, the number of call chains is rather unpredictable and can be large. The VLSI LVS application generated events in over 5000 call chains on optimized code.

[0104] To minimize the disturbance of the traced process, only the event generation takes place inside of the traced process itself. The online accounting, compression and trace generation is performed in a child process which is forked at the first trace event. This separates the allocations of the tracing and the traced code and takes advantage of available additional processors. In multi-threaded applications that use multiple heaps, one child can be forked for each heap.

[0105] Due to the sampling, the average throughput of the tracer is about at least 10 times higher than the event generation rate of the traced process over the entire run. This is not the case for short sequences of code that perform mostly allocations, e.g. the building of a linked list. Even on a single processor, the forking of the tracing process reduces the performance impact, since events can be buffered without disturbing the traced process such that short bursts of allocation events do not stall the traced process.

[0106] Referring to FIG. 8, a tracer process with a tracer and data flow are illustratively depicted. A tracer such as a forked tracer 150 traces call chains in an application 152. The application 152 is instrumented to generate call chain addresses which are input to the tracer 150. A buffer 154 may be employed to receive the chain addresses. The tracer 150 creates a trace file 156, which includes time stamped chain index changes (deltas). The tracer 150 may employ dictionary compression as described above.

[0107] Cached Symbol Extraction: Efficient handling of the call chain records (156) is a challenge. There are two performance bottlenecks, the extraction of the symbols from the stack trace and the handling of the call chains as keys. The most significant performance improvement in the call chain handling was achieved by caching symbols for program pointers. The forked process (150) accumulates a dictionary such that, for each pointer encountered on the stack, the text symbol is determined only once via the traceback table, and this lookup occurs in the child process. The stack holds, for each of its steps, the return address in the code. Such a return address is located inside a code block that is associated with a function and the symbolic name of the function is obtained through a traceback table. Finding the traceback table for a return address and extracting the symbol employs one to two orders of magnitude more compute time than tracing one step of the stack and obtaining the return address.

[0108] For programs that use conventional shared libraries, the address of each code location, and thus each return address, is determined when the program is loaded. Thus, the return addresses, traceback tables and symbols are identical for the traced process and for the forked child. Thus, the parent can pass return addresses to the child and the child performs the expensive symbol lookups and maintains a dictionary that maps return addresses to symbols to minimize the lookup costs.

[0109] Thus, the call chains form keys in the form of dozens of pointers and are fairly degenerate, i.e., there are common prefixes and postfixes. Hashing has to evaluate the entire key and a comparison-based tree looks in the average O(log(N)) times at a significant number of call chain steps to determine a difference.

[0110] A tree structure called PATRICIA (known in the art) turned out to be an excellent solution. A PATRICIA is a binary tree based on comparison of individual bits. Rather than comparing a bit of a fixed position on each level of the tree, it records in each node the index of the differentiating bit. In the average case, the number of bits evaluated in a search, insertion or deletion is independent of the key length and logarithmic in the number of elements in the PATRICIA. In the worst case, the number of bit comparisons during an operation is the number of bits in a key.

[0111] Experimental Results: We implemented the memory profiler measuring memory use including heap fragmentation, since this turned out to be the more useful measure. All experiments were performed on an IBM p690. The profiler was attached to executables by replacing the malloc-subsystem through the MALLOCTYPE mechanism of AIX.

[0112] The following is an extract from a memtrac summary report of program B. fsmall uses about 16 bytes per block (8 bytes useable, 8 bytes fragmentation for one pointer prefix and one pointer alignment). flarge uses about 460 bytes per block (400 bytes useable, 60 bytes fragmentation)

[0113] Extract from a memtrac summary report of program B:

fa1( );fatop( );fsmall( );main( );

[0114] Peak: 16194752 Leak; 16194752

fa1( );fatop( );flarge( );main( );

[0115] Peak: 460448128 Leak: 460-448128

[0116] The extract from a memtrac summary report of program B shows the distribution of memory allocations of the call tree of program B with MemTrac. The ratio between the two call chains is not exactly 50 due to internal fragmentation. Fragmentation has a larger relative impact for the 2-pointer blocks than for the 100-pointer blocks, Note also that all memory is correctly reported as leaking. Program B, extended by deallocation of all blocks to program B′, provides an interesting vehicle to estimate worst case impact of tracing, since it spends the maximal fraction possible in allocation and deallocation (the blocks are not even initialized) with a simple allocation pattern that is handled efficiently by the allocator.

[0117]

TABLE 1
Execution time comparisons.
		Raw	Traced	tracefile size
	B: 2000000	2.5	s	3.4	s	4.5	kB
	B′: 2000000	3.2	s	4.8	s	6.6	kB
	B′: 20000000	31	s	46	s	8.3	kB
	B′: 200000000	5 m 15 s	7 m 52 s	10.0	kB
	B″: 20000000	42.5	s	57.5	s	8.3	kB
	gcc	7.0	s	7.1	s	3.6	kB
	gs elisp.ps	34.5	s	34.7	s	116	kB
	scanline	173	s	192	s	5	kB
	LVS	10	hrs	10	hrs	250	MB

[0118] Table 1 shows raw elapsed execution time, elapsed time with tracing and the size of the time line file (i.e. records with time stamp, chain index and memory delta). The first four entries show results for program B and its non-leaking derivative B for different numbers of blocks. The blocks are evenly split in large and small. The ratio of the elapsed times of B′ converges asymptotically to roughly 1.5 with increasing problem size. The fifth entry is for program B″, i.e. program B extended by a simple initialization of the field elements. The absolute time increase for tracing remains 15 seconds, the relative increase is reduced.

[0119] Overall, tracing increased the execution time roughly by 50% of the time that the B* programs spent in the malloc subsystem. This is consistent with observations from real applications, which exhibited execution time inc same order of magnitude as the time spent in subsystem or less.

[0120] The last three entries in Table 1 show trace impact on the Gnu c-compiler and ghostscript, Ghostscript was run in batch mode writing output to ‘/dev/null’ on the emacs lisp manual. The main purpose of the tracer was the investigation of memory use in VLSI design tools. We traced numerous runs of large VLSI applications with hundreds of thousands of lines of code for DRC and LVS checking. The runtimes ranged from minutes to more than 10 hours and memory use ranged from tens of MB up to 18 GB. The tracer used less than 2 GB additional memory on the 10 hour and 18 GB LVS run. The zipped trace file was roughly 250 MB in size and covered more than 5000 call chains that allocated memory. The elapsed time was unchanged within the accuracy of measurement.

[0121] In all application runs that we performed, the increase in total memory used by tracer and traced process combined was less than 10% compared to the untraced run. The increase in total CPU time by tracer and traced process was also less than 10% in all runs compared to the untraced run. For large applications, the impact of tracing on execution time was negligible, i.e., within the range of fluctuations between repeated runs due I/O performance fluctuations (less than 1%).

[0122] The present work provides a memory profiling tool that is capable of handling large VLSI design applications without an intolerable increase in execution time and/or memory. The applications we found that provided proper memory usage results by call chain increased execution time by an order of magnitude and increased memory usage by a factor of two or more. In this disclosure, we present a highly efficient probabilistic approach for profiling general resources which permits measurement of resource use, M_ψ(t), over time for each call chain ψ. The present methods are capable of determining the resource use Mψ(t) for all call chains ψ for an application run. The approach permits construction of profiling solutions for different scenarios, e.g., different types of measurement triggers and value accumulation. An analytical framework maps resource use computation problems to numerical integration which allows the derivation of error estimates for varying profiling scenarios. Furthermore, an upper bound of 10% plus the space for recording call chain symbols can be given for the memory overhead of a traced run compared to an untraced run.

[0123] A probabilistic mechanism has been implemented for the example of memory profiling and demonstrated with experimental results so that the detailed memory use of very large applications can be efficiently profiled. The profiling does not need recompiling or relinking of the application. Profiling increased the elapsed time and total memory use by less than 10% compared to the unprofiled execution of optimized code. The profiling mechanism has been successfully used in the production of VLSI design automation applications as LVS checking, DRC checking, placement driven synthesis and timing.

[0124] Referring to FIG. 9, a system/method for correlation of resources with hardware events is illustratively depicted. In block 202, a call chain of functions is sampled based on events to determine when functions of the call chain are active. Numerical analysis of event driven sampling data is preferably performed such that one standard deviation error estimate declines proportional to 1/N where N is a total number of samples.

[0125] In block 220, the call chain activity is mapped to hardware events or 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 the hardware events or execution times. The mapping may include mapping the call chain to resource use based on the call chain which is active at a given sampling point to correlate the resource use changes measured at this sampling point with the call chain.

[0126] The probabilistic integration of the functions may include a Monte Carlo integration based on mapping event driven sampling points through a coordinate transformation to a pseudo-random sequence. The selection of the coordinate transformation creates a quasi-random sequence of minimal discrepancy. This creates a sequence of desirable properties out of what comes from the event driven sampling.

[0127] In block 222, an error estimate for each sample is employed to determine which chain is active. A Koksma-Hlawka inequality error estimate may be employed, 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). A sample that hits a call chain may be counted as a zero error contribution for all other call chains, and an error estimate may be employed to associate the sample with a call chain. In block 224, the error estimate is proportional to the variance and the variance is reduced to sample relevant regions more frequently by using importance sampling or partitioning the hardware events, such as (de)allocations based on e.g., memory blocks sizes.

[0128] The hardware events may include cache misses, allocation/deallocation of memory locations, time or memory profiling events, etc. In block 226, contributions from a call chain may be profiled by summing the time or memory usage over time using numerical integration to provide a time profile p(t) or memory usage function M(t). In block 228, a profiling strategy may be developed 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, or 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.

[0129] Referring to FIG. 10, a system 300 for correlation of resources with hardware events is illustratively shown in accordance with one illustrative embodiment. A program module 302 may include a processor or software executed on a processor. Program module 302 provides a tool for profiling systems or software which permits efficient analyses in accordance with the present principles. The program module 302 is preferably stored on computer readable media and configured to map resources to call chains in accordance with the methods set forth herein, e.g., in FIG. 9.

[0130] The program module 302 evaluates a system or a program 301 input thereto. The program module 302 includes a sample module 304 configured to sample a call chain of functions based on trigger events to determine when functions of the call chain are active. A mapper 306 is configured to map the call chain 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. The probabilistic integration of the functions may include based on mapping event driven sampling points through a coordinate transformation to a pseudo-random sequence, wherein the selection of the coordinate transformation creates a quasi-random sequence of minimal discrepancy. The coordinate transformation provides a useful sequence where a time based or other sequence would not be useful.

[0131] The mapper 306 may enforce constraints for associating call chains to execution time and/or hardware events or resources. For example, 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), may be employed wherein a sample that hits a call chain is counted as a zero error contribution for all other call chains and an error estimate associates the sample with a call chain.

[0132] The program module 302 is further configured to output a report 308 which correlates call chain activities to hardware events and to actual hardware, such as memory locations or the like.

[0133] Having described preferred embodiments of a system and method for a probabilistic framework for the highly efficient correlation of call chains with hardware events (which are intended to be illustrative and not limiting), it is noted that modifications and variations can be made by persons skilled in the art in light of the above teachings. It is therefore to be understood that changes may be made in the particular embodiments disclosed which are within the scope and spirit of the invention as outlined by the appended claims. Having thus described aspects of the invention, with the details and particularity required by the patent laws, what is claimed and desired protected by Letters Patent is set forth in the appended claims.