Online computation of cache occupancy and performance

Patent metadata

Field	Value
Publication number	US-9396024-B2
Application number	US-25110808-A
Country	US
Kind code	B2
Filing date	Oct 14, 2008
Priority date	Oct 14, 2008
Publication date	Jul 19, 2016
Grant date	Jul 19, 2016

Abstract

Methods, computer programs, and systems for managing thread performance in a computing environment based on cache occupancy are provided. In one embodiment, a computer implemented method assigns a thread performance counter to threads being created to measure the number of cache misses for the threads. The thread performance counter is deduced in one embodiment based on performance counters associated with each core in a processor. The method further calculates a self-thread value as the change in the thread performance counter of a given thread during a predetermined period, and an other-thread value as the sum of all the changes in the thread performance counters for all threads except for the given thread. Further, the method estimates a cache occupancy for the given thread based on a previous occupancy for the given thread, and the calculated shelf-thread and other-thread values. The estimated cache occupancy is used to assign computing environment resources to the given thread. In another embodiment, cache miss-rate curves are constructed for a thread to help analyze performance tradeoffs when changing cache allocations of the threads in the system.

First claim

What is claimed is:

1. A computer implemented method to manage thread performance in a computing environment, the method comprising:
assigning a thread performance counter to threads being created in the computing environment, the thread performance counter measuring a number of cache misses for a corresponding thread;
calculating a self-thread value S as a change in the thread performance counter of a given thread during a predetermined period;
calculating an other-thread value O as a sum of changes in all the thread performance counters during the predetermined period minus S;
estimating a cache occupancy of a cache for the given thread based on estimating cache misses that occurred since a previous estimate of a previous occupancy E for the given thread using the self-thread value S and the other-thread value O and estimating a fraction of the previous occupancy E unaffected by the cache misses that occurred since the previous estimate using the previous occupancy E for the given thread, the self-thread value S and the other-thread value O, wherein the cache occupancy indicating an estimated amount of data that is stored in the cache for the given thread; and
assigning computing environment resources to the given thread based on the estimated cache occupancy.

2. The method as recited in claim 1 , wherein assigning a thread performance counter further includes,
assigning a core performance counter to each core,
first reading the core performance counter when a given thread is scheduled,
second reading the core performance counter when the given thread is descheduled,
updating the thread performance counter for the given thread based on the difference between the second reading and the first reading.

3. The method as recited in claim 1 , wherein estimating cache occupancy further includes,
calculating an occupancy ratio for the given thread as the previous occupancy E divided by a number of cache lines C; and
estimating the cache occupancy for the given thread by adding to the previous occupancy the self-thread value multiplied by one minus the occupancy ratio and by subtracting the other-thread value times the occupancy ratio.

4. The method as recited in claim 3 , wherein estimating cache occupancy further includes,
estimating the cache occupancy for the given thread by using incremental updates when either a fraction S/C or a fraction O/C is bigger than a first predetermined threshold value.

5. The method as recited in claim 3 , further including,
decreasing the value of the predetermined period when a fraction S/C or a fraction O/C is bigger than a second predetermined threshold value.

6. The method as recited in claim 5 , further including,
normalizing S by replacing S with S/(S+O), and
normalizing O by replacing O with O/(S+O).

7. The method as recited in claim 1 , further including,
creating a three-dimensional lookup table for estimating the cache occupancy, the three dimensions of the lookup table being E, S and O,
wherein the cache occupancy is estimated by accessing the lookup table.

8. The method as recited in claim 7 , further including,
quantizing E to associate E with a bucket from a plurality of buckets, each bucket from a plurality of buckets covering a different range of possible E values,
wherein the dimension corresponding to E in the lookup table is quantized according to the plurality of buckets.

9. The method as recited in claim 1 , wherein estimating cache occupancy further includes,
assigning a total misses value M the sum of S and O,
calculating a self-miss ratio f by dividing S by M,
calculating a global-miss ratio g by dividing M by a number of cache lines C,
calculating an exponential factor α as e to the power of minus g, and
estimating the cache occupancy for the given thread as fC(1−α)+αE.

10. The method as recited in claim 1 , further including,
tracking estimated occupancy ratios over a plurality of periods, and
constructing a cache performance curve based on the tracked occupancy ratios,
wherein assigning computing environment resources to the given thread further includes accessing the cache performance curve to analyze impact on performance to the given thread when resources are reallocated to or from the given thread.

11. The method as recited in claim 10 , further including,
detecting changes in the cache performance curve that signal a phase change in the thread, the changes being identified by non-monotonic cache performance curve updates, and
changing a cache update policy as a result of the phase change.

12. The method as recited in claim 10 , wherein constructing a cache performance curve further includes updating values in the cache performance curve using one of,
a simple average algorithm, or
an exponentially weighted moving average algorithm.

13. The method as recited in claim 10 , wherein constructing a cache performance curve further includes filling unknown values in the cache performance curve by interpolation.

14. A computer program embedded in a non-transitory computer-readable storage medium, when executed by one or more processors, for manage resource performance in a computing environment, the computer program comprising:
program instructions for assigning a thread performance counter to threads being created in the computing environment, the thread performance counter measuring a number of cache misses for a corresponding thread;
program instructions for calculating a self-thread value S as a change in the thread performance counter of a given thread during a predetermined period;
program instructions for calculating an other-thread value O as a sum of changes in all the thread performance counters during the predetermined period minus S;
program instructions for estimating a cache occupancy of a cache for the given thread based on estimating cache misses that occurred since a previous estimate of a previous occupancy E for the given thread using the self-thread value S and the other-thread value O and estimating a fraction of the previous occupancy E unaffected by the cache misses that occurred since the previous estimate using the previous occupancy E for the given thread, the self-thread value S and the other-thread value O, wherein the cache occupancy indicating an estimated amount of data that is stored in the cache for the given thread; and
program instructions for assigning computing environment resources to the given thread based on the estimated cache occupancy.

15. The computer program as recited in claim 14 , further including,
program instructions for tracking estimated occupancy ratios over a plurality of periods, and
program instructions for constructing a cache performance curve based on the tracked occupancy ratios.

16. The computer program as recited in claim 15 , further including,
program instructions for detecting changes in the cache performance curve that signal a phase change in the thread, the changes being identified by non-monotonic cache performance curve updates, and
program instructions for changing a cache update policy as a result of the phase change.

17. The computer program as recited in claim 14 , further including,
program instructions for tracking a cache miss ratio for the given thread as the number of cache misses for the given thread divided by a number of total cache references by the given thread.

18. The computer program as recited in claim 14 , further including,
program instructions for tracking a cycles per instruction ratio for the given thread.

19. A system to man

Assignees

• West Richard
• Zaroo Puneet
• Waldspurger Carl A
• Zhang Xiao
• Zheng Haoqiang
• Vmware Inc

Inventors

• West Richard
• Zaroo Puneet
• Waldspurger Carl A
• Zhang Xiao
• Zheng Haoqiang

Classifications

• G06F11/3409

  for performance assessment · CPC title

• G06F12/08

  in hierarchically structured memory systems, e.g. virtual memory systems · CPC title

• G06F12/0804

  with main memory updating (G06F12/0806 takes precedence) · CPC title

• G06F11/3466

  Performance evaluation by tracing or monitoring · CPC title

• G06F12/0802

  Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches · CPC title