Abstract:
The present invention discloses a method comprising: sending cache request; monitoring power state; comparing said power state; allocating cache resources; filling cache; updating said power state; repeating said sending, said monitoring, said comparing, said allocating, said filling, and said updating until workload is completed.

Description:
[0001]    This application is a continuation of U.S. patent application Ser. No. 12/583,036, filed Aug. 13, 2009, the content of which is hereby incorporated by reference. 
     
    
     FIELD OF THE INVENTION 
       [0002]    The present invention relates to a field of processor design, and, more specifically; to an apparatus for and a method of sharing cache resources between processors. 
       DISCUSSION OF RELATED ART 
       [0003]    Computing power of processors is increasing much faster than bandwidth available from main memory. As a result, increasingly large and complex caches need to be designed to support and feed compute-intensive processors. 
         [0004]    However, allocating more transistors to cache results in the cache occupying a larger portion of die area. Furthermore, available cache resources, no matter how large, are increasingly difficult to allocate. 
         [0005]    In particular, partitioning of the cache resources between different compute engines to obtain optimal performance for different workloads becomes difficult to achieve effectively and efficiently. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0006]      FIG. 1  shows way mask and shared cache according to an embodiment of the present invention. 
           [0007]      FIG. 2  shows flowchart of cache allocation based on power state according to an embodiment of the present invention. 
       
    
    
     DETAILED DESCRIPTION 
       [0008]    In the following description, numerous details, examples, and embodiments are set forth to provide a thorough understanding of the present invention. However, it will become clear and apparent to one of ordinary skill in the art that the invention is not limited to the details, examples, and embodiments set forth and that the invention may be practiced without some of the particular details, examples, and embodiments that are described. In other instances, one of ordinary skill in the art will further realize that certain details, examples, and embodiments that may be well-known have not been specifically described so as to avoid obscuring the present invention. 
         [0009]    An apparatus for and a method of sharing cache resources are disclosed in the present invention. Utilization of a cache can result in a significantly improvement in performance of a compute engine. A large chip may include a level 1 (L1) cache and a level 2 (L2) cache. In general, a last level cache (LLC) is a cache that is located farthest from a compute engine and nearest to main memory. Intelligent sharing of the cache, such as the LLC, between multiple compute engines increases overall performance of a system for a given workload. 
         [0010]    Various embodiments of the apparatus for sharing cache resources according to the present invention will be described first. The present invention envisions an apparatus for dynamically allocating cache resources among compute engines. Allocation of cache resources can be done among multiple compute engines. Allocation of cache resources can also be performed among different types of compute engines. 
         [0011]    As shown in an embodiment of the present invention in  FIG. 1 , the compute engines  110 ,  120  are connected to a cache  300 . The compute engines  110 ,  120  and the cache  300  form part of a system  600 . 
         [0012]    The compute engines  110 ,  120  may be located in a single die, in a single package, in a single board, or in a single sub-system (not shown). In one case, the compute engines include a central processing unit (CPU)  110  and a graphics processing unit (GPU)  120 . In another case, the compute engines include multiple cores. In still another case, the compute engines include system on a chip (SOC). In yet another case, the compute engines are embedded. 
         [0013]    The data array of a highly to fully set-associative cache can be organized into ways. The cache  300  is partitioned into ways  301 ,  302 , . . . ,  309 ,  310  by a way mask  200 . The way mask  200  may be included in cache allocation logic  402 . 
         [0014]    In one case, the way mask  200  is connected with a central controller  400 . The central controller  400  may be located in a power control unit (PCU)  500  of the system  600 . Control for the way mask  200  can be on-chip, on-board, or remote. The control can be performed by hardware, software, firmware, or a combination of the above. The way mask  200  can be programmable using firmware. 
         [0015]    The cache allocation logic  402  evaluates the cache requests  115 ,  125  from the respective compute engines  110 ,  120  and determines which ways  301 ,  302 , . . . ,  309 ,  310  in the cache  300  to access for each of the compute engines  115 ,  125 . The cache allocation logic  402  is usually not located in the PCU  500 . In one case, the cache allocation logic  402  is located between the compute engines  110 ,  120  and the way mask  200 . In another case, the way mask  200  is included in the cache allocation logic  402 . 
         [0016]    Cache allocation heuristics  403  may be located in the PCU  500 . Allocation of cache resources may be based on a parameter or metric or a combination of parameters and metrics. A parameter refers to a physical attribute or property that may change in value. A metric refers to a mathematical function that may be measured or calculated. The metric may be based on one or more parameters. The metric may include an algorithm or equation. 
         [0017]    In one case, the parameter or metric includes power state  401  information. The cache allocation heuristics  403  may use power state  401  information as input and then provide way mask updates  405  as output. 
         [0018]    The parameter or metric of the power state  401  information can be combined with other parameters or metrics to improve decision for allocation of cache resources. The other parameters or metrics can include instructions per cycle (IPC), cache misses per instruction, and memory boundness of the workload. 
         [0019]    The size of a cache  300  allocated to a computing engine can be changed linearly by using selective ways. For smaller cache sizes, set associativity can significantly impact cache performance. However, for larger cache sizes, capacity plays a more important role than set associativity. 
         [0020]    Power savings are optimized by choosing a size for the cache  300  that is closest to a size demanded by an application. Optimizing the size of the cache  300  will also reduce sub-threshold leakage energy dissipation which is proportional to size of the cache  300  in CMOS circuits. 
         [0021]    Compared with selective sets, selective ways is relatively simple to design since only a way mask  200  and corresponding cache allocation logic  402  are required. In one case, the way mask  200  is included in the cache allocation logic  402 . 
         [0022]    The way mask  200  applies to cache fills, but not cache lookups. When allocation changes and a compute engine no longer has access to certain ways, data may no longer be allocated in those ways, but any existing data in those ways may still be looked up. 
         [0023]    Each way in the cache  300  may include a number of subarrays. If desired by circuit implementation, the way mask  200  allows all of the subarrays in a particular way to be enabled or disabled together. Selective ways does not alter set mapping of cache blocks and so avoids a need for flushing blocks in the enabled subarrays upon resizing. 
         [0024]    The present invention also envisions a method of dynamically allocating cache resources among compute engines. Allocation of cache resources can be done among multiple compute engines. Allocation of cache resources can also be performed among different types of compute engines. 
         [0025]    In an embodiment of the present invention as shown in block  10  in  FIG. 2 , a cache request may be sent by one or more compute engines. 
         [0026]    In one case as shown in  FIG. 1 , the CPU  110  sends a cache request  115 . The GPU  120  may independently send a cache request  125 . The cache allocation logic  402  evaluates the cache requests  115 ,  125  from the respective compute engines  110 ,  120  and determines which ways  301 ,  302 , . . . ,  309 ,  310  in the cache  300  to access for each of the compute engines  115 ,  125 . The cache allocation logic  402  is usually not located in the PCU  500 . In one case, the cache allocation logic  402  is located between the compute engines  110 ,  120  and the way mask  200 . In another case, the way mask  200  is included in the cache allocation logic  402 . 
         [0027]    Cache allocation heuristics  403  may be located in the PCU  500 . Allocation of cache resources may be based on a parameter or metric or a combination of parameters or metrics. A parameter refers to a physical attribute or property that may change in value. A metric refers to a mathematical function that may be measured or calculated. The metric may be based on one or more parameters. The metric may include an algorithm or equation. 
         [0028]    In one case, the parameter or metric includes power state  401  information. According to an embodiment of the present invention as shown in block  20  of  FIG. 2 , the power state  401  information for multiple, or all, agents in a chip, package, or system are monitored. 
         [0029]    In one case, the monitoring is continuous and uninterrupted. In another case, the monitoring is continual and repeated. The monitoring may include periodic sampling at regular intervals. The intervals may be measured in duration of time. Alternatively, the intervals may be measured in number of cache accesses. 
         [0030]    In one case, the compute engines are monitored concurrently. In another case, the compute engines are monitored sequentially. In still another case, the compute engines are monitored randomly. In yet another case, the compute engines are monitored based on an arbitrary predetermined schedule. 
         [0031]    According to an embodiment of the present invention as shown in block  30  of  FIG. 2 , the power state  401  is compared. In one case, the power state  401  is compared among different compute engines. In another case, the power state  401  is compared with a setpoint value, a target value, or a range in a specification. 
         [0032]    As shown in  FIG. 1 , the cache allocation heuristics  403  may use power state  401  information as input and then provide way mask updates  405  as output. In particular, the way mask  200  determines how the ways  301 ,  302 , . . . ,  309 ,  310  of the cache  300  are filled under different workloads by various compute engines, such as the CPU  110  and the GPU  120 . 
         [0033]    According to an embodiment of the present invention as shown in block  40  of  FIG. 2 , the way mask  200  is adjusted or controlled to allocate cache resources. In one case, the cache allocation is always adjusted dynamically. In another case, the cache allocation is mostly adjusted dynamically. In still another case, the cache allocation is sometimes adjusted statically. In yet another case, the cache allocation is mostly adjusted statically. 
         [0034]    In one case, the cache allocation is adjusted based on probability and statistics. In another case, the cache allocation is adjusted based on fuzzy logic. In still another case, the cache allocation is adjusted based on real-time feedback. In still another case, the cache allocation is adjusted based on artificial intelligence (AI) learning. 
         [0035]    Adjustment or control of the way mask  200  can be on-chip, on-board, or remote. The adjustment or control of the way mask  200  can be performed by hardware, software, firmware, or a combination of the above. 
         [0036]    The parameter or metric of the power state  401  information for a compute engine includes P-states (frequencies) and C-states (sleep states). The P-states reduce power consumption of the compute engine by altering efficiency of execution. The C-states are used whenever the compute engine has no work or almost no work to do. In general, lower power can be achieved in exchange for accepting or tolerating lower performance or longer wake latency. 
         [0037]    In an embodiment of the present invention as shown in block  30  of  FIG. 2 , the P-states for the various compute engines are compared. 
         [0038]    Next, hardware, software, firmware, or a combination of the above, provides or sends way mask updates  405  to the way mask  200  to partition some, or all, of the ways in the cache  300 . 
         [0039]    In one case, the way mask updates  405  indicate whether to adjust or control the way mask  200 . In another case, the way mask updates  405  indicate how to adjust or control the way mask  200 . In still another case, the way mask updates  405  indicate when to adjust or control the way mask  200 . 
         [0040]    Then, the way mask  200  enables certain ways in the cache  300  and controls which compute engine can use them. As an example, the cache resources can be shifted as needed between the CPU  110  and the GPU  120  based on their respective workloads. In one case, the CPU  110  would use most of the cache during a CPU-intensive workload with minimal graphics activity, such as a Standard Performance Evaluation Corporation (SPEC) benchmark. In another case, the GPU  120  would get most of the cache resources during a Gfx-heavy workload, such as a 3D game. 
         [0041]    The allocation of cache resources need not be complete. A way in the cache  300  can be turned off (such that no compute engine can use it) such as to reduce power consumption. In such a situation, some ways in the cache  300  are not used. 
         [0042]    The allocation of cache resources need not be symmetrical. Allocation of a way in the cache  300  can be exclusive (such that only one compute engine can use the way) or non-exclusive (such that multiple compute engines can share the way). 
         [0043]    As shown for an illustrative purpose in  FIG. 1 , the CPU  110  has access to  10  ways in a cache  300  while GPU  120  only has access to  7  of the  10  ways. In one particular implementation, the dedicated ways  301 ,  302 ,  303 , are only used by the CPU  110  while the dedicated way  310  is only used by the GPU  120 . The shared ways  304 ,  305 ,  306 ,  307 ,  308 ,  309  can be used by either the CPU  110  or the GPU  120 . However, the shared ways  304 ,  305  are usually used by the CPU  110  while the shared ways  306 ,  307 ,  308 ,  309  are usually used by the GPU  120 . 
         [0044]    Other implementations of the ways  301 ,  302 , . . . ,  309 ,  310  may be chosen and used. A library may be maintained of various implementations of the ways  301 ,  302 , . . . ,  309 ,  310 . A lookup table may be maintained of the various implementations of the ways  301 ,  302 , . . . ,  309 ,  310 . 
         [0045]    As shown in an embodiment of the present invention in block  40  of  FIG. 2 , cache resources are allocated for the compute engine that requires more cache resources. In one embodiment, frequency is used to predict cache demand and cache resources are shifted toward the compute engine that is running closest to its maximum frequency. In another embodiment, cache resources are shifted toward the compute engine that spends the least amount of time in a sleep state. 
         [0046]    According to an embodiment of the present invention as shown in block  50  of  FIG. 2 , the cache  300  is filled. The filling of the cache  300  may be based on the allocation of cache resources. 
         [0047]    Then, according to an embodiment of the present invention as shown in block  60  of  FIG. 2 , the power state  401  is updated. 
         [0048]    In an embodiment of the present invention as shown in block  70  of  FIG. 2 , dynamic cache allocation continues until completion of the workload on the compute engines connected to the cache  300 . 
         [0049]    The mechanism described in the present invention is self-correcting in that if an incorrect or sub-optimal decision to remove cache resources from a particular compute engine is made, it will degrade performance on that engine, a parameter or metric such as IPC will drop, utilization will rise, and the frequency will be raised, giving feedback to the cache allocation heuristics  403  to return the cache resources. 
         [0050]    Decisions can also be made on other cache-related parameters, such as shrinking a cache  300  to reduce power consumption when the cache allocation heuristics  403  in  FIG. 1  suggest that a workload of a compute engine is not currently demanding a high level of performance or that it does not require most or all of the available cache resources. 
         [0051]    Allocation decisions can also be made in a similar fashion regarding other shared resources besides cache resources. Other shared (non-cache) resources include other memory subsystem resources, such as memory bandwidth and cooling capacity. For example, memory peripheral hub and memory controller queues for different compute engines may also be allocated dynamically based on feedback from the PCU  500 . 
         [0052]    Allocation of the shared (non-cache) resources may be based on a parameter or metric or a combination of parameters or metrics. A parameter refers to a physical attribute or property that may change in value. A metric refers to a mathematical function that may be measured or calculated. The metric may be based on one or more parameters. The metric may include an algorithm or equation. In one case, the parameter or metric includes power state  401  information. 
         [0053]    Many embodiments and numerous details have been set forth above in order to provide a thorough understanding of the present invention. One skilled in the art will appreciate that many of the features in one embodiment are equally applicable to other embodiments. One skilled in the art will also appreciate the ability to make various equivalent substitutions for those specific materials, processes, dimensions, concentrations, etc. described herein. It is to be understood that the detailed description of the present invention should be taken as illustrative and not limiting, wherein the scope of the present invention should be determined by the claims that follow. 
         [0054]    While the present invention has been described with respect to a limited number of embodiments, those skilled in the art will appreciate numerous modifications and variations therefrom. It is intended that the appended claims cover all such modifications and variations as fall within the true spirit and scope of this present invention.