Cache contention management on a multicore processor based on the degree of contention exceeding a threshold

• US 9,268,542 B1
• Filed: 04/28/2011
• Issued: 02/23/2016
• Est. Priority Date: 04/28/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Mars, Jason, Hundt, Robert, Vachharajani, Neil A.
• Primary Examiner(s): An, Meng
• Assistant Examiner(s): Ghaffari, Abu
• Application Number:
  US13/096,821
• Time in Patent Office: 1,762 Days
• Field of Search: 718/102, 718/104, 718/103, 711/118, 711/141, 711/130, 711/E12.045, 711/E12.052, 711/167
• US Class Current: 1/1
• CPC Class Codes: G06F 13/30 with priority control
• CPC Class Codes: G06F 13/372 using a time-dependent priority, e.g. individually loaded time counters or time slot
• CPC Class Codes: G06F 2209/504 Resource capping
• CPC Class Codes: G06F 2209/508 Monitor
• CPC Class Codes: G06F 8/4442 Reducing the number of cache misses; Data prefetching cache prefetching G06F12/0862
• CPC Class Codes: G06F 9/30 Arrangements for executing machine instructions, e.g. instruction decode for executing microinstructions G06F9/22
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A first indicator of a first number of cache misses to a cache memory of a multicore processor for a first application over a first time period is received. The first application executes on a first core of the processor and a second application simultaneously executes on a second core of the processor during the first time period. The first and second cores share the cache memory. A second indicator of a second number of cache misses to the cache memory for the first application over a second time period is received. During the second time period, the first application executes on the first core and the second application does not execute on the second core. A degree of contention among the first and second applications is determined based on the first and second indicators, and execution of the second application is adjusted based on the determined degree of contention.

Claims

1. A computer-implemented method for cache contention handling, the method comprising:

concurrently executing a first software application on a first core of a multicore processor and a second software application on a different, second core of the multicore processor, the first core and the second core sharing a cache memory of the multicore processor, wherein the first core is arranged to access the shared cache memory when a private cache memory of the first core is unavailable, wherein the second core is arranged to access the shared cache memory when a private cache memory of the second core is unavailable;

identifying that a first number of cache misses by the first software application to the shared cache memory occurred over a first time period during the concurrent execution of the first software application and the second software application on the first core and the second core of the multicore processor, respectively;

identifying that a second number of cache misses by the second software application to the shared cache memory occurred over the first time period;

determining, based on the first number of cache misses by the first software application and the second number of cache misses by the second software application to the shared cache memory over the first time period, that a degree of contention for the shared cache memory among the first software application and the second software application during the first time period exceeds a threshold degree of contention;

accessing data that indicates execution of the first software application on the multicore processor is to be prioritized over execution of the second software application on the multicore processor so as to minimize latency in responding to user inputs directed to the first software application; and

in response to determining that the degree of contention for the shared cache memory during the first time period exceeds the threshold degree of contention, adjusting continued execution of the second software application on the second core so as to reduce the degree of contention for the shared cache memory among the first software application and the second software application, wherein the second software application is chosen for adjusted execution rather than the first software application based on the data that indicates execution of the first software application is to be prioritized over execution of the second software application.

2. The computer-implemented method of claim 1, wherein adjusting continued execution of the second software application on the second core so as to reduce the degree of contention for the shared cache memory comprises temporarily halting execution of the second software application for a period of time, and resuming execution of the second software application when the period of time is passed.

3. The computer-implemented method of claim 2, further comprising:

monitoring the degree of contention for the shared cache memory during the period of time in which execution of the second software application is temporality halted; and

determining when to resume execution of the second software application based on one or more indications of degrees of contention for the shared cache memory at different times during the period of time in which execution of the second software application is temporarily halted.

4. The computer-implemented method of claim 1, wherein adjusting continued execution of the second software application on the second core so as to reduce the degree of contention for the shared cache memory comprises preventing the second software application from accessing the shared cache memory for a period of time during which the first software application continues to execute on the first core and the second software application continues to execute on the second core.

5. The computer-implemented method of claim 4, wherein the second software application is prevented from accessing the shared cache memory until the degree of contention for the shared cache memory among the first software application and the second software application is determined to no longer exceed the threshold degree of contention.

6. The computer-implemented method of claim 1, wherein identifying that the first number of cache misses by the first software application to the shared cache memory occurred over the first period of time comprises accessing an indicator of the first number of cache misses, the indicator being is stored at a shared memory location that is accessible to both the first core of the multicore processor and the second core of the multicore processor.

7. The computer-implemented method of claim 1, further comprising determining a degree of contention for one or more additional shared resources of the multicore processor among the first software application and the second software application,

wherein the one or more additional shared resources are selected from a group comprising a bus, a memory controller, an input-output device, and a network interface device,

wherein a manner in which the continued execution of the second software application on the second core is adjusted is further based on the determined degree of contention for the one or more additional shared resources of the multicore processor.

8. The computer-implemented method of claim 1, wherein the degree of contention for the shared cache memory is determined by a runtime engine that executes on at least one of the first and second cores of the multicore processor at periodic intervals during interrupts of the concurrent execution of at least one of the first software application and the second software application.

9. A computing system including a multicore processor that is adapted for cache contention handling, the computing system configured to perform operations comprising:

concurrently executing a first software application on a first core of the multicore processor and a second software application on a different, second core of the multicore processor, the first core and the second core sharing a cache memory of the multicore processor, wherein the first core is arranged to access the shared cache memory when a private cache memory of the first core is unavailable, wherein the second core is arranged to access the shared cache memory when a private cache memory of the second core is unavailable;

identifying that a first number of cache misses by the first software application to the shared cache memory occurred over a first time period during the concurrent execution of the first software application and the second software application on the first core and the second core of the multicore processor, respectively;

identifying that a second number of cache misses by the second software application to the shared cache memory occurred over the first time period;

determining, based on the first number of cache misses by the first software application and the second number of cache misses by the second software application to the shared cache memory over the first time period, that a degree of contention for the shared cache memory among the first software application and the second software application during the first time period exceeds a threshold degree of contention;

accessing data that indicates execution of the first software application on the multicore processor is to be prioritized over execution of the second software application on the multicore processor so as to minimize latency in responding to user inputs directed to the first software application; and

in response to determining that the degree of contention for the shared cache memory during the first time period exceeds the threshold degree of contention, adjusting continued execution of the second software application on the second core so as to reduce the degree of contention for the shared cache memory among the first software application and the second software application, wherein the second software application is chosen for adjusted execution rather than the first software application based on the data that indicates execution of the first software application is to be prioritized over execution of the second software application.

10. The computing system of claim 9, wherein adjusting continued execution of the second software application on the second core so as to reduce the degree of contention for the shared cache memory comprises temporarily halting execution of the second software application for a period of time, and resuming execution of the second software application when the period of time is passed.

11. The computing system of claim 10, wherein the operations further comprise:

monitoring the degree of contention for the shared cache memory during the period of time in which execution of the second software application is temporality halted; and

determining when to resume execution of the second software application based on one or more indications of degrees of contention for the shared cache memory at different times during the period of time in which execution of the second software application is temporarily halted.

12. The computing system of claim 9, wherein adjusting continued execution of the second software application on the second core so as to reduce the degree of contention for the shared cache memory comprises preventing the second software application from accessing the shared cache memory for a period of time during which the first software application continues to execute on the first core and the second software application continues to execute on the second core.

13. The computing system of claim 12, wherein the second software application is prevented from accessing the shared cache memory until the degree of contention for the shared cache memory among the first software application and the second software application is determined to no longer exceed the threshold degree of contention.

14. The computing system of claim 9, wherein identifying that the first number of cache misses by the first software application to the shared cache memory occurred over the first period of time comprises accessing an indicator of the first number of cache misses, the indicator being stored at a shared memory location that is accessible to both the first core of the multicore processor and the second core of the multicore processor.

15. The computing system of claim 9, wherein the operations further comprise determining a degree of contention for one or more additional shared resources of the multicore processor among the first software application and the second software application,

wherein the one or more additional shared resources are selected from a group comprising a bus, a memory controller, an input-output device, and a network interface device,

wherein a manner in which the continued execution of the second software application on the second core is adjusted is further based on the determined degree of contention for the one or more additional shared resources of the multicore processor.

16. The computing system of claim 9, wherein the degree of contention for the shared cache memory is determined by a runtime engine that executes on at least one of the first and second cores of the multicore processor at periodic intervals during interrupts of the concurrent execution of at least one of the first software application and the second software application.

17. One or more non-transitory computer-readable media having instructions stored thereon that, when executed by one or more computers, cause performance of operations comprising:

concurrently executing a first software application on a first core of a multicore processor and a second software application on a different, second core of the multicore processor, the first core and the second core sharing a cache memory of the multicore processor, wherein the first core is arranged to access the shared cache memory when a private cache memory of the first core is unavailable, wherein the second core is arranged to access the shared cache memory when a private cache memory of the second core is unavailable;

identifying that a first number of cache misses by the first software application to the shared cache memory occurred over a first time period during the concurrent execution of the first software application and the second software application on the first core and the second core of the multicore processor, respectively;

identifying that a second number of cache misses by the second software application to the shared cache memory occurred over the first time period;

determining, based on the first number of cache misses by the first software application and the second number of cache misses by the second software application to the shared cache memory over the first time period, that a degree of contention for the shared cache memory among the first software application and the second software application during the first time period exceeds a threshold degree of contention;

accessing data that indicates execution of the first software application on the multicore processor is to be prioritized over execution of the second software application on the multicore processor so as to minimize latency in responding to user inputs directed to the first software application; and

in response to determining that the degree of contention for the shared cache memory during the first time period exceeds the threshold degree of contention, adjusting continued execution of the second software application on the second core so as to reduce the degree of contention for the shared cache memory among the first software application and the second software application, wherein the second software application is chosen for adjusted execution rather than the first software application based on the data that indicates execution of the first software application is to be prioritized over execution of the second software application.