Method and apparatus for achieving fair cache sharing on multi-threaded chip multiprocessors

• US 20080059712A1
• Filed: 08/29/2006
• Published: 03/06/2008
• Est. Priority Date: 08/29/2006
• Status: Active Grant

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Fedorova, Alexandra
• Granted Patent: US 8,069,444 B2
• Time in Patent Office: Days
• US Class Current: 711/130
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

In a computer system with a multi-core processor having a shared cache memory level, an operating system scheduler adjusts the CPU latency of a thread running on one of the cores to be equal to the fair CPU latency which that thread would experience when the cache memory was equally shared by adjusting the CPU time quantum of the thread. In particular, during a reconnaissance time period, the operating system scheduler gathers information regarding the threads via conventional hardware counters and uses an analytical model to estimate a fair cache miss rate that the thread would experience if the cache memory was equally shared. During a subsequent calibration period, the operating system scheduler computes the fair CPU latency using runtime statistics and the previously computed fair cache miss rate value to determine the fair CPI value.

Claims

1. A method for achieving fair cache memory sharing in a processor having a plurality of cores, each of which has a thread running thereon, and a cache memory that is shared by the threads, the method comprising:

(a) computing for a thread a fair CPU latency as a product of thread cycles per instruction which that thread would experience when the cache memory was equally shared and a CPU time quantum for that thread;

(b) measuring an actual CPU latency as a product of thread cycles per instruction which that thread experiences and the CPU time quantum for that thread; and

(c) adjusting the actual CPU latency of the thread to be equal to the fair CPU latency.

2. The method of claim 1 wherein step (c) is performed by an operating system scheduler by adjusting the CPU time quantum allotted to the thread.

3. The method of claim 1 wherein step (a) comprises:

(a1) during a reconnaissance time period, gathering information regarding the thread via conventional hardware counters; and

(a2) using an analytical model to estimate a fair cache miss rate that the thread would experience if the cache memory was equally shared.

4. The method of claim 3 wherein step (a) further comprises:

(a3) during a calibration period subsequent to the reconnaissance period, using runtime statistics and the fair cache miss rate value computed in step (a2) to determine the fair CPI value that the thread would experience if cache memory was equally shared.

5. The method of claim 4 wherein step (b) comprises:

(b1) during the calibration period, measuring the actual CPI value of a thread and comparing the fair CPI value determined in step (a3) to the actual CPI value for that thread.

6. The method of claim 3 wherein step (a2) further comprises, during the reconnaissance time period, measuring cache memory miss rates for the thread as that thread operates with other co-runners and deriving a linear equation to estimate a fair cache miss rate that the thread would experience if the cache memory was equally shared.

7. The method of claim 1, further comprising repeating calibration periods periodically during runtime.

8. The method of claim 7 further comprising repeating the reconnaissance period periodically with a longer time period that the repetition period at which the calibration periods are repeated.

9. The method of claim 1 further comprising:

(d) after adjusting the CPU time quantum of a thread during a time slot in step (c), selecting another thread that is running in that time slot; and

(e) adjusting a CPU time quantum of that other thread to compensate for the adjustment made to the thread.

10. Apparatus for achieving fair cache memory sharing in a processor having a plurality of cores, each of which has a thread running thereon, and a cache memory that is shared by the threads, the apparatus comprising:

a mechanism that computes for a thread a fair CPU latency as a product of thread cycles per instruction which that thread would experience when the cache memory was equally shared and a CPU time quantum for that thread;

a mechanism that measures an actual CPU latency as a product of thread cycles per instruction which that thread experiences and the CPU time quantum for that thread; and

an operating system scheduler that adjusts the actual CPU latency of the thread to be equal to the fair CPU latency.

11. The apparatus of claim 10 wherein the operating system scheduler adjusts the actual CPU latency of the thread by adjusting the CPU time quantum allotted to the thread.

12. The apparatus of claim 10 wherein the mechanism that computes for a thread a fair CPU latency comprises:

a mechanism operable during a reconnaissance time period, that gathers information regarding the thread via conventional hardware counters; and

a mechanism that uses an analytical model to estimate a fair cache miss rate that the thread would experience if the cache memory was equally shared.

13. The apparatus of claim 12 wherein the mechanism that computes for a thread a fair CPU latency further comprises:

a mechanism operable during a calibration period subsequent to the reconnaissance period, that uses runtime statistics and the fair cache miss rate value computed by the mechanism that uses an analytical model to estimate a fair cache miss rate to determine the fair CPI value that the thread would experience if cache memory was equally shared.

14. The apparatus of claim 13 wherein the mechanism that measures an actual CPU latency comprises:

a mechanism operable during the calibration period, that measures the actual CPI value of a thread and compares the fair CPI value determined by the mechanism for determining the fair cache value to the actual CPI value for that thread.

15. The apparatus of claim 12 wherein the mechanism that estimates a fair cache miss rate further comprises a mechanism, operable during the reconnaissance time period, that measures cache memory miss rates for the thread as that thread operates with other co-runners and derives a linear equation to estimate a fair cache miss rate that the thread would experience if the cache memory was equally shared.

16. The apparatus of claim 10, further comprising a mechanism that causes processing during the calibration periods to be repeated periodically during runtime.

17. The apparatus of claim 16 further comprising a mechanism that causes processing during the reconnaissance period to be repeated periodically with a longer time period that the repetition period at which processing during the calibration periods are repeated.

18. The apparatus of claim 10 further comprising:

a mechanism operable after the mechanism for adjusting the CPU time quantum of a thread adjusts the CPU time quantum of that thread, that selects another thread that is running in that time slot; and

a mechanism that adjusts a CPU time quantum of that other thread to compensate for the adjustment made to the thread.

19. Apparatus for achieving fair cache memory sharing in a processor having a plurality of cores, each of which has a thread running thereon, and a cache memory that is shared by the threads, the apparatus comprising:

means for computing for a thread a fair CPU latency as a product of thread cycles per instruction which that thread would experience when the cache memory was equally shared and a CPU time quantum for that thread;

means for measuring an actual CPU latency as a product of thread cycles per instruction which that thread experiences and the CPU time quantum for that thread; and

means for adjusting the actual CPU latency of the thread to be equal to the fair CPU latency.

20. The apparatus of claim 19 wherein the means for adjusting the actual CPU latency of the thread comprises an operating system scheduler that adjusts the CPU time quantum allotted to the thread.