Using hardware counters to estimate cache warmth for process/thread schedulers

• US 6,615,316 B1
• Filed: 11/16/2000
• Issued: 09/02/2003
• Est. Priority Date: 11/16/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McKenney, Paul E., Krueger, Phillip E.
• Primary Examiner(s): Yoo, Dohyun
• Assistant Examiner(s): GOODARZI, NASSER MOAZZAMI
• Application Number:
  US09/715,444
• Time in Patent Office: 1,020 Days
• Field of Search: 711/118, 711/133, 711/136, 709/102, 709/108
• US Class Current: 711/118
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 9/5033 considering data affinity

Abstract

A method and computer system for estimating cache warmth for thread schedulers in a processor of a multiprocessor system. A mathematical model based upon a Markov Model of queuing theory is used to determine flow probability. The method incorporates data received from cache counters to measure cache hits, cache misses, cache invalidations and cache roll-outs. Based upon the Model and the data received from the counters and the assumption that cache decays exponentially, a nominal lifetime of a cache line is computed and the state of the system is manipulated in accordance with the computed lifetime of the cache line. The method may be applied to either a two way LRU cache or a four way LRU cache for computing an average lifetime of a cache line. Accordingly, cache affinity and thread migration decisions are enhanced thereby providing an efficient method of operating a computer system.

Claims

1. A method for operating a computer system comprising the steps of:

(a) mathematically modeling cache warmth responsive to a hardware counter of a processor in the system;

(b) computing a nominal lifetime of a cache line based upon said model; and

(c) manipulating the state of the system based upon the lifetime.

2. The method of claim 1, wherein said manipulation step includes scheduling processes on a processor.

3. The method of claim 1, wherein said manipulation step includes transferring processes between processors.

4. The method of claim 1, wherein said manipulation step includes moving data among processor nodes.

5. The method of claim 1, wherein said manipulation step includes retargetting interrupt handlers from one processor to another.

6. The method of claim 1, wherein the counter counts measurements selected from a group consisting of:

cache misses, cache invalidations, cache hits, cache roll-outs, and combinations thereof.

7. The method of claim 1, wherein the step of mathematically modeling is based on a Markov Model of queuing theory.

8. The method of claim 7, further comprising the step of creating a set of linear equations from said Markov Model.

9. The method of claim 8, further comprising the step of building a look-up table from said linear equations.

10. The method of claim 1, wherein said step of mathematically modeling cache warmth comprises the step of estimating cache warmth assuming exponential decay.

11. The method of claim 10, further comprising the step of estimating an initial population of said cache for a subsequent process based upon the cache warmth estimate.

12. The method of claim 1, wherein said manipulation step includes prorating cache line assignments for shared cache.

13. A computer system, comprising:

multiple processors, each processor having an associated cache;

hardware counters for measuring state of the cache;

means for building a mathematical model for estimating cache warmth, said means being responsive to said hardware counters;

means for manipulating the state of the system based upon said cache warmth estimate;

wherein said means for building said mathematical model comprises computing an average lifetime of a given cache line.

14. The system of claim 13, wherein said means for building said mathematical model further comprises assuming exponential decay.

15. The system of claim 13, wherein said hardware counters measure state of the cache selected from a group consisting of:

cache hits, cache misses, cache invalidations, cache roll-outs, and combinations thereof.

16. The system of claim 14, wherein said mathematical model incorporates a Markov Model of queuing theory.

17. The system of claim 16, wherein said Markov Model further comprises modeling an expected decay time in a two way set associative that uses a least-recently used replacement policy.

18. The system of claim 16, wherein said Markov Model further comprises modeling an expected decay time in a four way set associative cache that uses a pseudo-random replacement policy.

19. The system of claim 13, wherein said manipulation means is selected from a group consisting of:

scheduling processes on a processor, transferring processes between processors, moving data among processor nodes, retargetting interrupt handlers from one processor to another, prorating cache line assignments, and combinations thereof.

20. A computer system, comprising:

multiple processors, each processor having an associated cache;

hardware counters for measuring state of the cache;

a mathematical model for estimating cache warmth, wherein said model is responsive to hardware measurements;

said cache warmth estimate manipulating the state of the system;

wherein said model comprises computing a nominal lifetime of a given cache line.

21. The system of claim 20, wherein said model comprises estimating cache warmth assuming exponential decay of cache.

22. The system of claim 20, wherein said hardware counters measure state of the cache selected from a group consisting of:

cache hits, cache misses, cache invalidations, cache roll-outs, and combinations thereof.

23. The system of claim 20, wherein said mathematical model comprises a Markov Model of queuing theory.

24. The system of claim 23, further comprises modeling an expected decay time in a two way set associative that uses a least-recently used replacement policy.

25. The system of claim 23, further comprises modeling an expected decay time in a four way set associative cache that uses a pseudo-random replacement policy.

26. The system of claim 20, wherein said manipulation of the state of the system is selected from a group consisting of scheduling processes on a processor, transferring processes between processors, moving data among processor nodes, retargetting interrupt handlers from one processor to another, prorating cache line assignments, and combinations thereof.

27. An article comprising:

a computer-readable medium having stored thereon computer executable instructions;

means in the medium for obtaining data from a hardware counter;

means for building a mathematical model for estimating cache warmth;

means for computing a nominal lifetime of a cache line based upon said model; and

means in the medium for manipulating the state of the system based upon said cache warmth estimate.

28. The article of claim 27, wherein the medium is a recordable data storage medium.

29. The article of claim 27, wherein the medium is a modulated carrier signal.

30. The article of claim 27, wherein said manipulation means schedules processes on a processor.

31. The article of claim 27, wherein said manipulation means transfers processes between processors.

32. The article of claim 27, wherein said manipulation means moves data among processor nodes.

33. The article of claim 27, wherein said manipulation means retargets interrupt handlers from one processor to another.

34. The article of claim 27, wherein said data obtaining means measures state of the cache selected from the group consisting of cache misses, cache invalidations, cache roll-outs, and cache hits.

35. The article of claim 27, wherein said means for building a mathematical model uses a Markov Model of queuing theory.

36. The article of claim 27, wherein said cache warmth estimate assumes exponential decay of cache.

37. The article of claim 27, wherein said manipulation means prorates cache line assignments for shared cache.