Scheduling Workloads Based On Cache Asymmetry

• US 20120233393A1
• Filed: 03/08/2011
• Published: 09/13/2012
• Est. Priority Date: 03/08/2011
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Zhao, Li, Iyer, Ravishankar, Jiang, Xiaowei
• Granted Patent: US 8,898,390 B2
• Time in Patent Office: Days
• US Class Current: 711/105
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking
• CPC Class Codes: G06F 2209/483 Multiproc
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

In one embodiment, a processor includes a first cache and a second cache, a first core associated with the first cache and a second core associated with the second cache. The caches are of asymmetric sizes, and a scheduler can intelligently schedule threads to the cores based at least in part on awareness of this asymmetry and resulting cache performance information obtained during a training phase of at least one of the threads.

Claims

1. An apparatus comprising:

a processor including a first cache and a second cache, a first core associated with the first cache and a second core associated with the second cache, the first and second caches asymmetric caches of a common cache level, wherein a scheduler is to schedule a plurality of threads to the first and second cores based at least in part on cache performance information obtained during a training phase of the plurality of threads on the asymmetric caches.

2. The apparatus of claim 1, further comprising a predictor to predict cache performance of a first thread on the second cache during the training phase of the first thread on the first core using the first cache.

3. The apparatus of claim 2, wherein the first cache includes a first tag array and a corresponding data array, a second tag array to model operation of the first cache and a third tag array to model operation of the second cache, wherein the second and third tag arrays are a portion of the size of the first tag array and not having corresponding data arrays.

4. The apparatus of claim 3, wherein the predictor is to measure the cache performance of the first thread on the first cache and to predict the cache performance of the first thread on the second cache during the training phase, and to store the cache performance information for the first thread in a first storage of the processor.

5. The apparatus of claim 4, wherein the scheduler is to schedule the first thread to the first core or to the second core for an execution phase of the first thread following the training phase based on the cache performance information.

6. The apparatus of claim 1, wherein the scheduler is of O(1) complexity.

7. The apparatus of claim 6, wherein the scheduler is to consider a limited number of scheduling scenarios from a plurality of possible scheduling scenarios.

8. The apparatus of claim 7, wherein each of the limited number of scheduling scenarios includes a thread arrival to one of the first and second cores.

9. The apparatus of claim 1, wherein when the first and second caches are private caches, the scheduler is to calculate a first sum of miss rate values for use of the first cache by a first thread and use of the second cache by a second thread, and to calculate a second sum of miss rate values for use of the second cache by the first thread and use of the first cache by the second thread, and to schedule the first and second threads according to the smaller sum.

10. A method comprising:

initiating a thread on a first core of a processor;

measuring cache performance of the thread on a first cache used by the thread and predicting cache performance of the thread on a second cache unused by the thread, the first and second caches of asymmetric size, and storing cache performance information regarding the cache performance in a storage; and

determining a thread-to-core mapping based on the cache performance information.

11. The method of claim 10, further comprising scheduling the thread to the first core or a second core associated with the second cache based on the thread-to-core mapping.

12. The method of claim 11, further comprising executing the thread on the scheduled first or second core in an execution phase of the thread following a training phase in which the cache performance information is stored.

13. The method of claim 11, further comprising computing a sum for each of a plurality of possible schedules for the thread, a second thread, and a third thread on the first and second cores and a third core associated with the second cache.

14. The method of claim 13, further comprising selecting a schedule from the plurality of possible schedules based on the sums.

15. The method of claim 14, further comprising selecting the schedule having a lowest sum, each sum corresponding to:

16. A system comprising:

a processor including first, second, third and fourth cores, the first and second cores coupled to a first shared cache, the third and fourth cores coupled to a second shared cache, the first and second shared caches asymmetric caches of a common cache level, a first predictor to predict cache performance of a first thread on the second shared cache during a training phase of the first thread on the first core and to determine cache performance of the first thread on the first shared cache during the training phase of the first thread, and a second predictor to predict cache performance of a second thread on the first shared cache during a training phase of the second thread on the third core and to determine cache performance of the second thread on the second shared cache during the training phase of the second thread; and

a dynamic random access memory (DRAM) coupled to the processor.

17. The system of claim 16, wherein the first shared cache includes a first tag array and a corresponding data array, a second tag array to model operation of the first shared cache and a third tag array to model operation of the second shared cache, wherein the second and third tag arrays are a portion of the size of the first tag array and not having corresponding data arrays.

18. The system of claim 17, further comprising a scheduler to schedule a plurality of threads to at least some of the first, second, third and fourth cores based at least in part on information from the first predictor and the second predictor.

19. The system of claim 18, wherein the first predictor is to provide information from the second and third tag arrays to the scheduler.

20. The system of claim 18, wherein the scheduler is to compute a cache metric sum for each of a plurality of possible schedules for execution of a plurality of threads on at least some of the first, second, third, and fourth cores, and to select the schedule of the plurality of possible schedules having a smallest cache metric sum.

21. The system of claim 18, wherein the scheduler is of O(1) complexity.

22. The system of claim 21, wherein the scheduler is to consider a limited number of scheduling scenarios from a plurality of possible scheduling scenarios.

23. An apparatus comprising:

first, second, third and fourth cores;

a first shared cache coupled to the first and second cores;

a second shared cache coupled to the third and fourth cores, the first and second shared caches asymmetric caches of a common cache level;

a first predictor to predict cache performance of a first thread on the second shared cache during a training phase of the first thread on the first core; and

a second predictor to predict cache performance of a second thread on the first shared cache during a training phase of the second thread on the third core.

24. The apparatus of claim 23, wherein the first predictor includes a plurality of tag arrays without corresponding data arrays, each of the plurality of tag arrays to model operation of a thread on one of the first shared cache and second shared cache.

25. The apparatus of claim 24, wherein a scheduler is to schedule a plurality of threads to at least some of the first, second, third and fourth cores based at least in part on information from the first predictor and the second predictor.

26. The apparatus of claim 23, wherein the first predictor is further to determine cache performance of the first thread on the first shared cache during the training phase of the first thread.

27. The apparatus of claim 26, wherein the second predictor is further to determine cache performance of the second thread on the second shared cache during the training phase of the second thread.