Cache performance prediction and scheduling on commodity processors with shared caches

A non-transitory computer-readable storage medium comprising computer-executable instructions that, when executed by one or more processors, cause the one or more processors to perform the steps of:

• 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;
• calculating a first estimation adjustment value associated with a first probability that a second set of cache misses for the corresponding thread replace a cache area currently occupied by the corresponding thread;
• estimating a cache occupancy for the given thread based on a previous occupancy E for the given thread, S, O, and the first estimation adjustment value, wherein the estimating of the cache occupancy for the given thread based on the previous occupancy comprises solving for E′ using the equation:
• E′=E·(1−O·p1)+(C−E)·S·p2;
• and
• wherein S is the change in the thread performance counter of the given thread during the predetermined period, O is the sum of changes in all the thread performance counters during the predetermined period minus S, E is the previous occupancy for the following:
• the given thread, S, O, and the first estimation adjustment value, wherein p1 is the probability that the second set of cache misses for the corresponding thread replaces the cache area currently occupied by the corresponding thread, C is a total number of cache areas in a shared last level cache, and p2 is the second probability that the cache miss subsequently consumes the cache area not currently occupied by the corresponding thread;
• and
• assigning computing environment resources to the given thread based on the estimated cache occupancy.

A system to manage thread performance in a computing environment, they system comprising:

• a memory comprising a resource allocation program;
• a shared last level cache;
• and
• a computing device having a plurality of processors, and when program instructions from the resource allocation program are executed by a processor from the plurality of processors, cause the processor to:
• assign 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,
• calculate a self-thread value S as a change in the thread performance counter of a given thread during a predetermined period,
• calculate an other-thread value O as a sum of changes in all the thread performance counters during the predetermined period minus S,
• calculate a first estimation adjustment value associated with a first probability that a second set of cache misses for the corresponding thread replace a cache area currently occupied by the corresponding thread,
• estimate a cache occupancy for the given thread based on a previous occupancy E for the given thread, S, O, and the first estimation adjustment value, wherein the estimating of the cache occupancy for the given thread based on the previous occupancy comprises solving for E′ using the equation:
• E′=E·(1−O·p1)+(C−E)·S·p2,
• and
• wherein S is the change in the thread performance counter of the given thread during the predetermined period, O is the sum of changes in all the thread performance counters during the predetermined period minus S, E is the previous occupancy for the following:
• the given thread, S, O, and the first estimation adjustment value, wherein p1 is the probability that the second set of cache misses for the corresponding thread replaces the cache area currently occupied by the corresponding thread, C is a total number of cache areas in a shared last level cache, and p2 is the second probability that the cache miss subsequently consumes the cache area not currently occupied by the corresponding thread, and
• assign computing environment resources to the given thread based on the estimated cache occupancy.

A computer implemented method for managing 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;
• calculating a first estimation adjustment value associated with a first probability that a second set of cache misses for the corresponding thread replaces a cache area currently occupied by the corresponding thread;
• estimating a cache occupancy for the given thread based on a previous occupancy E for the following:
• the given thread, S, O, and the first estimation adjustment value, wherein estimating cache occupancy further comprises:
• calculating a first component of the cache occupancy by multiplying S by:
• a number of cache areas estimated to be not be occupied by the corresponding thread;
• and a probability that a cache miss subsequently replaces a cache area currently occupied by the corresponding thread;
• calculating a second component of the cache occupancy by multiplying E by a quantity 1 minus O times a second probability that a cache miss subsequently replaces a cache area currently occupied by the corresponding thread;
• and
• adding the first component and the second component to the cache occupancy;
• and
• assigning computing environment resources to the given thread based on the estimated cache occupancy.

A non-transitory computer-readable storage medium comprising computer-executable instructions that, when executed by one or more processors, cause the one or more processors to perform the steps of:

• 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;
• calculating a first estimation adjustment value associated with a first probability that a second set of cache misses for the corresponding thread replace a cache area currently occupied by the corresponding thread;
• estimating a cache occupancy for the given thread based on a previous occupancy E for the given thread, S, O, and the first estimation adjustment value, wherein estimating cache occupancy further comprises:
• calculating a first component of the cache occupancy by multiplying S by:
• a number of cache areas estimated to be not be occupied by the corresponding thread;
• and a probability that a cache miss subsequently replaces a cache area currently occupied by the corresponding thread;
• calculating a second component of the cache occupancy by multiplying E by a quantity 1 minus O times a second probability that a cache miss subsequently replaces a cache area currently occupied by the corresponding thread;
• and
• adding the first component and the second component to the cache occupancy;
• and
• assigning computing environment resources to the given thread based on the estimated cache occupancy.

A system to manage thread performance in a computing environment, they system comprising:

• a memory comprising a resource allocation program;
• a shared last level cache;
• and
• a computing device having a plurality of processors, and when program instructions from the resource allocation program are executed by a processor from the plurality of processors, cause the processor to:
• assign 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,
• calculate a self-thread value S as a change in the thread performance counter of a given thread during a predetermined period,
• calculate an other-thread value O as a sum of changes in all the thread performance counters during the predetermined period minus S,
• calculate a first estimation adjustment value associated with a first probability that a second set of cache misses for the corresponding thread replace a cache area currently occupied by the corresponding thread,
• estimate a cache occupancy for the given thread based on a previous occupancy E for the given thread, S, O, and the first estimation adjustment value, wherein estimating cache occupancy further comprises:
• calculating a first component of the cache occupancy by multiplying S by:
• a number of cache areas estimated to be not be occupied by the corresponding thread;
• and a probability that a cache miss subsequently replaces a cache area currently occupied by the corresponding thread;
• calculating a second component of the cache occupancy by multiplying E by a quantity 1 minus O times a second probability that a cache miss subsequently replaces a cache area currently occupied by the corresponding thread;
• and
• adding the first component and the second component to the cache occupancy, and
• assign computing environment resources to the given thread based on the estimated cache occupancy.

A computer implemented method for managing 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;
• calculating a cache reuse value representing one or more of an intensity of cache reuse by the corresponding thread and an intensity of cache reuse by other threads not including the corresponding thread;
• calculating a first estimation adjustment value associated with a first probability that a second set of cache misses for the corresponding thread replaces a cache area currently occupied by the corresponding thread, wherein calculating the first estimation adjustment value is based at least in part on the thread performance counter and the cache reuse value;
• estimating a cache occupancy for the given thread based on a previous occupancy E for the following:
• the given thread, S, O, and the first estimation adjustment value;
• and
• assigning computing environment resources to the given thread based on the estimated cache occupancy.

A non-transitory computer-readable storage medium comprising computer-executable instructions that, when executed by one or more processors, cause the one or more processors to perform the steps of:

• 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;
• calculating a cache reuse value representing one or more of an intensity of cache reuse by the corresponding thread and an intensity of cache reuse by other threads not including the corresponding thread;
• calculating a first estimation adjustment value associated with a first probability that a second set of cache misses for the corresponding thread replaces a cache area currently occupied by the corresponding thread, wherein calculating the first estimation adjustment value is based at least in part on the thread performance counter and the cache reuse value;
• estimating a cache occupancy for the given thread based on a previous occupancy E for the given thread, S, O, and the first estimation adjustment value;
• adding the first component and the second component to the cache occupancy;
• and
• assigning computing environment resources to the given thread based on the estimated cache occupancy.

A system to manage thread performance in a computing environment, they system comprising:

• a memory comprising a resource allocation program;
• a shared last level cache;
• and
• a computing device having a plurality of processors, and when program instructions from the resource allocation program are executed by a processor from the plurality of processors, cause the processor to:
• assign 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,
• calculate a self-thread value S as a change in the thread performance counter of a given thread during a predetermined period,
• calculate an other-thread value O as a sum of changes in all the thread performance counters during the predetermined period minus S, calculate a cache reuse value representing one or more of an intensity
• of cache reuse by the corresponding thread and an intensity of cache reuse by other threads not including the corresponding thread,
• calculate a first estimation adjustment value associated with a first probability that a second set of cache misses for the corresponding thread replaces a cache area currently occupied by the corresponding thread, wherein calculating the first estimation adjustment value is based at least in part on the thread performance counter and the cache reuse value,
• estimate a cache occupancy for the given thread based on a previous occupancy E for the given thread, S, O, and the first estimation adjustment value, and
• assign computing environment resources to the given thread based on the estimated cache occupancy.