MULTICORE COMPUTER SYSTEM WITH CACHE USE BASED ADAPTIVE SCHEDULING

• US 20130205092A1
• Filed: 02/06/2012
• Published: 08/08/2013
• Est. Priority Date: 02/06/2012
• Status: Active Grant

• Current Assignee: Empire Technology Development LLC (Allied Inventors Management, LLC)
• Original Assignee: Empire Technology Development LLC (Allied Inventors Management, LLC)
• Inventors: Roy, Shaibal, Datta, Soumya
• Granted Patent: US 9,053,029 B2
• Time in Patent Office: Days
• US Class Current: 711/130
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/544 Buffers; Shared memory; Pipes

Abstract

An example multicore environment generally described herein may be adapted to improve use of a shared cache by a plurality of processing cores in a multicore processor. For example, where a producer task associated with a first core of the multicore processor places data in a shared cache at a faster rate than a consumer task associated with a second core of the multicore processor, relative task execution rates can be adapted to prevent eventual increased cache misses by the consumer task.

Claims

1. A multicore computer system including a first core and a second core, the multicore computer system comprising:

a shared cache;

a counter configured to count just-missed misses by the first core, wherein the just-missed misses include cache misses associated with data recently evicted from the shared cache; and

a scheduler configured to, in response to an increase in the just-missed misses counted by the counter, adjust an execution rate of a task associated with the first core relative to an execution rate of a task associated with the second core.

2. The multicore computer system of claim 1, further comprising a cache controller configured to adjust and initialize the counter in response to a command from the scheduler.

3. The multicore computer system of claim 2, wherein the cache controller is configured to maintain a list of cache line addresses associated with data recently discarded from the shared cache, and adjust the counter in response to a request by the first core for the data recently evicted from the shared cache.

4. The multicore computer system of claim 2, wherein the cache controller is configured to provide a counter value to the scheduler upon request by the scheduler.

5. The multicore computer system of claim 1, wherein the scheduler is further configured to adjust the execution rate of the task associated with the first core relative to the execution rate of the task associated with the second core by providing a policy to a cache controller.

6-25. -25. (canceled)

26. A method for optimizing shared cache use in a multicore computer system including a first core and a second core, the method comprising:

accumulating, by a plurality of counters, counts of shared cache just-missed misses by a plurality of cores in a multicore computer system, wherein the just-missed misses include cache misses associated with data recently evicted from the shared cache;

receiving, by a scheduler, one or more counts associated with a counter and also associated with the first core;

detecting, by the scheduler, an increase in just-missed misses associated with the first core based at least in part on the one or more counts received by the scheduler;

adjusting, by the scheduler, in response to the detecting an increase in just-missed misses associated with the first core, an execution rate of a task associated with the first core relative to an execution rate of a task associated with a second core.

27. The method of claim 26, further comprising the scheduler initiating counting by one or more of the plurality of counters by requesting a cache controller to start one or more of the plurality of counters.

28. The method of claim 26, further comprising maintaining, by a cache controller, a list of cache line addresses associated with data recently evicted from the shared cache.

29. The method of claim 26, wherein adjusting the execution rate of the task associated with the first core relative to the execution rate of the task associated with the second core further comprises:

providing a policy to a cache controller.

30. A method for optimizing use of a shared cache in a multicore computer system including a first core and a second core, the method comprising:

requesting a cache controller to count shared cache just-missed misses associated with the first core, wherein the just-missed misses include cache misses associated with data recently evicted from the shared cache;

counting the shared cache just-missed misses associated with the first core;

providing a count of shared cache just-missed misses associated with the first core to a scheduler;

adjusting an execution rate of a task associated with the first core relative to an execution rate of a task associated with a second core.

31. The method of claim 30, wherein the adjusting an execution rate comprises generating a cache usage policy by the scheduler.

32. The method of claim 30, further comprising maintaining a list of cache line addresses associated with data recently evicted from the shared cache, and using the list in counting just missed misses.

33. A method for optimizing use of a shared cache in a multicore computer system including a first core and a second core, the method comprising:

monitoring a rate of shared cache just-missed misses associated with the first core;

determining when the rate of just-missed misses associated with the first core enters a predetermined range; and

when the rate of just missed misses is determined to enter the predetermined range, adjusting an execution rate of a first task associated with the first core relative to an execution rate of a second task associated with the second core.

34. The method of claim 33, further comprising counting just-missed misses associated with the first core using a counter.

35. The method of claim 34, further comprising maintaining a list of cache line addresses associated with data recently evicted from the shared cache and using the list in counting the just-missed misses.

36. The method of claim 33, further comprising providing a counter value to a scheduler upon request by the scheduler.

37. The method of claim 33, further comprising increasing the execution rate of the first task relative to the execution rate of the second task based on a policy generated by a scheduler.

39. The method of claim 33, further comprising increasing the execution rate of the first task relative to the execution rate of the second task by one or more of providing a policy to a cache controller, throttling the second task, and initiating a context switch.

40. A computer readable medium having computer executable instructions for optimizing use of a shared cache in a multicore computer system comprising a first core and a second core, the computer executable instructions comprising:

computer executable instructions for monitoring a rate of shared cache just-missed misses associated with the first core;

computer executable instructions for determining when the monitored rate of shared cache just-missed misses is in a predetermined range; and

computer executable instructions for adjusting an execution rate of a first task associated with the first core relative to an execution rate of a second task associated with the second core when the monitored rate is determined to be in the predetermined range.

41. The computer readable medium of claim 40, further comprising computer executable instructions for counting just-missed misses associated with the first core using a counter.

42. The computer readable medium of claim 41, further comprising computer executable instructions for maintaining a list of cache line addresses associated with data recently evicted from the shared cache and using the list in counting the just-missed misses.

43. The computer readable medium of claim 40, further comprising computer executable instructions for providing a counter value to a scheduler upon request by the scheduler.

44. The computer readable medium of claim 40, further comprising computer executable instructions for increasing the execution rate of the first task relative to the execution rate of the second task in response to a policy received from a scheduler.

45. The computer readable medium of claim 40, further comprising computer executable instructions for adjusting the execution rate of the first task relative to the execution rate of the second task by one or more of providing a policy to a cache controller, throttling the second task, and initiating a context switch.