Methods and apparatus for estimating fair cache miss rates on a chip multiprocessor

1. A method for estimating the fair cache miss rate of a thread executing on a chip multiprocessor having a plurality of processing cores, the method comprising:

identifying a thread for determining the fair cache miss rate of the thread;

executing the thread concurrently on the chip multiprocessor with a plurality of peer threads to measure the actual cache miss rates of the respective threads while executing concurrently;

computing the fair cache miss rate of the thread based on the relationship between the actual miss rate of the thread and the actual miss rates of the plurality of peer threads; and

applying the fair cache miss rate of the thread to a scheduling policy of the chip multiprocessor.

2. The method of claim 1 further comprising:

for a predetermined number of iterations as defined by the scheduling policy, repeating the steps of:

executing the thread concurrently on the chip multiprocessor with a plurality of peer threads to measure the actual cache miss rates of the respective threads while executing concurrently; and

computing the fair cache miss rate of the thread based on the relationship between the actual miss rate of the thread and the actual miss rates of the plurality of peer threads.

3. The method of claim 1 wherein the computing the fair cache miss rate of the thread comprises:

estimating a linear relationship between the actual cache miss rate of the thread and the actual cache miss rates of the plurality of peer threads, wherein estimating the linear relationship provides linear parameters for a gradient value and a constant value.

4. The method of claim 3 wherein estimating a linear relationship between the actual cache miss rate of the thread and the actual cache miss rates of the plurality of peer threads comprises:

applying linear regression to model the expected cache miss rate of the thread in relation to the aggregate miss rates of the plurality of peer threads.

5. The method of claim 3 further comprising:

determining a relational cache miss rate of the thread comprises applying the formula:

RltnalMissRate

⁢

⁢

(

T

)

=

a

*

∑

i

=

1

n

⁢

AcutalMissRate

⁡

(

Ci

)

+

b

wherein RltnalMissRate(T) is the relational cache miss rate of thread T, a is the gradient value, b is the constant value, n is the number of peer threads executing concurrently, Ci is the ith co-executing peer thread, and ActualMissRate(Ci) is the actual miss rate of the Cith co-executing peer thread.

6. The method of claim 5 wherein the computing the fair cache miss rate of the thread comprises:

determining the fair cache miss rate of the thread based on the relationship between the number of peer threads that were executed concurrently, the gradient value and the constant value.

7. The method of claim 5 further comprising:

determining the fair cache miss rate of the thread comprises applying the formula:

FairCacheMissRate

⁡

(

T

)

=

b

1

-

a

*

n

wherein FairCacheMissRate(T) is the fair cache miss rate of thread T, b is the constant value, a is the gradient value, and n is the number of peer threads that were executed concurrently with the thread.

8. The method of claim 1 wherein executing the thread concurrently on the chip multiprocessor with a plurality of peer threads comprises:

executing the thread concurrently on the chip multiprocessor with a plurality of peer threads to measure the actual level 2 (L2) cache miss rates of the respective threads while executing concurrently.

9. The method of claim 1 wherein executing the thread concurrently on the chip multiprocessor with a plurality of peer threads comprises:

concurrently executing a peer thread for each available processing core of the chip multiprocessor.

10. A computerized device comprising:

a memory;

a chip multiprocessor;

a communications interface;

an interconnection mechanism coupling the memory, the chip multiprocessor and the communications interface; and

wherein the memory is encoded with a caching estimator application that when executed on the chip multiprocessor provides a caching estimator process causing the computerized device to be capable of performing the operations of:

identifying a thread for determining the fair cache miss rate of the thread;

executing the thread concurrently on the chip multiprocessor with a plurality of peer threads to measure the actual cache miss rates of the respective threads while executing concurrently;

computing the fair cache miss rate of the thread based on the relationship between the actual miss rate of the thread and the actual miss rates of the plurality of peer threads; and

applying the fair cache miss rate of the thread to a scheduling policy of the chip multiprocessor.

11. The computerized device of claim 10 further comprising:

for a predetermined number of iterations as defined by the scheduling policy, repeating the steps of:

executing the thread concurrently on the chip multiprocessor with a plurality of peer threads to measure the actual cache miss rates of the respective threads while executing concurrently; and

computing the fair cache miss rate of the thread based on the relationship between the actual miss rate of the thread and the actual miss rates of the plurality of peer threads.

12. The computerized device of claim 10 wherein computing the fair cache miss rate of the thread comprises:

estimating a linear relationship between the actual cache miss rate of the thread and the actual cache miss rates of the plurality of peer threads, wherein estimating the linear relationship provides linear parameters for a gradient value and a constant value.

13. The computerized device of claim 12 wherein estimating a linear relationship between the actual cache miss rate of the thread and the actual cache miss rates of the plurality of peer threads comprises:

applying linear regression to model the expected cache miss rate of the thread in relation to the aggregate miss rates of the plurality of peer threads.

14. The computerized device of claim 12 further comprising:

determining a relational cache miss rate of the thread comprises applying the formula:

RltnalMissRate

⁡

(

T

)

=

a

*

∑

i

=

1

n

⁢

ActualMissRate

⁡

(

Ci

)

+

b

wherein RltnalMissRate(T) is the relational cache miss rate of thread T, a is the gradient value, b is the constant value, n is the number of peer threads executing concurrently, Ci is the ith co-executing peer thread, and ActualMissRate (Ci) is the actual miss rate of the Cith co-executing peer thread.

15. The computerized device of claim 14 wherein the computing the fair cache miss rate of the thread comprises:

determining the fair cache miss rate of the thread based on the relationship between the number of peer threads that were executed concurrently, the gradient value and the constant value.

16. The computerized device of claim 14 further comprising:

determining the fair cache miss rate of the thread comprises applying the formula:

FairCacheMissRate

⁡

(

T

)

=

b

1

-

a

*

n

wherein FairCacheMissRate(T) is the fair cache miss rate of thread T, b is the constant value, a is the gradient value, and n is the number of peer threads that were executed concurrently with the thread.

17. The computerized device of claim 10 wherein executing the thread concurrently on the chip multiprocessor with a plurality of peer threads comprises:

executing the thread concurrently on the chip multiprocessor with a plurality of peer threads to measure the actual level 2 (L2) cache miss rates of the respective threads while executing concurrently.

18. The computerized device of claim 10 wherein executing the thread concurrently on the chip multiprocessor with a plurality of peer threads comprises:

concurrently executing a peer thread for each available processing core of the chip multiprocessor.

19. A computer program product having a computer readable medium operable to store computer program logic embodied in computer program code encoded thereon as an encoded set of chip multiprocessor based instructions for performing cache miss rate estimation comprising:

computer program code for identifying a thread for determining the fair cache miss rate of the thread;

computer program code for executing the thread concurrently on the chip multiprocessor with a plurality of peer threads to measure the actual cache miss rates of the respective threads while executing concurrently;

computer program code for computing the fair cache miss rate of the thread based on the relationship between the actual miss rate of the thread and the actual miss rates of the plurality of peer threads;

computer program code for estimating a linear relationship between the actual cache miss rate of the thread and the actual cache miss rates of the plurality of peer threads, wherein estimating the linear relationship provides linear parameters for a gradient value and a constant value; and

computer program code for applying the fair cache miss rate of the thread to a scheduling policy of the chip multiprocessor.

20. A computerized device comprising:

a memory;

a chip multiprocessor;

a communications interface;

an interconnection mechanism coupling the memory, the chip multiprocessor and the communications interface; and

wherein the memory is encoded with caching estimator application that when executed on the chip multiprocessor provides a means for estimating cache miss rates on the chip multiprocessor comprising:

means for identifying a thread for determining the fair cache miss rate of the thread;

means for executing the thread concurrently on the chip multiprocessor with a plurality of peer threads to measure the actual cache miss rates of the respective threads while executing concurrently;

means for computing the fair cache miss rate of the thread based on the relationship between the actual miss rate of the thread and the actual miss rates of the plurality of peer threads;

means for estimating a linear relationship between the actual cache miss rate of the thread and the actual cache miss rates of the plurality of peer threads, wherein estimating the linear relationship provides linear parameters for a gradient value and a constant value; and

means for applying the fair cache miss rate of the thread to a scheduling policy of the chip multiprocessor.