Patent Publication Number: US-7584327-B2

Title: Method and system for proximity caching in a multiple-core system

Description:
BACKGROUND 
   In multi-core processors or processing systems, each core may correspond to a cache memory, accessible only by that core. Furthermore, shared cache memory, accessible to all of the cores, may be provided to extend cache capacity. 
   Cache access time may be affected by propagation delays caused by capacitance of interconnects from a logic circuit, such as a core, to or from the core. In general, cache access time may increase in proportion to such physical properties as the distance between the cache and an accessing logic, the width of the interconnect, etc. Accordingly, some prior art processors may organize a shared cache into multiple chunks and arrange the chunks so that frequently accessed data items are close to the processor(s) (or processing core(s)) that use them. 
   However, prior art caching schemes for moving frequently accessed items close to an accessing logic (e.g., processor core) may be expensive in terms of energy consumed and/or die area. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  shows a system architecture according to embodiments of the invention; 
       FIGS. 2 and 3  illustrate operations that may be used to perform at least one embodiment of the invention; and 
       FIG. 4  shows a multi-processor system in which one or more embodiments of the invention may be used. 
   

   DETAILED DESCRIPTION 
   Embodiments of the invention relate to a technique for caching data in a multiple-core system with shared cache. According to some of the embodiments, data used by the cores may be classified as being of one of a number of types. In one embodiment, the classification may enable handling of the data to be done more efficiently, depending upon the data type. For example, in one embodiment, data classified as a first type may be stored in a shared cache, and in a region of the shared cache that is closest in proximity to a core using the data. By storing the first type of data closest to an accessing logic, such as a core, access time and energy consumption may be reduced if the data is subsequently retrieved for use by the core. Data classified as a second type may, by contrast, only be stored and processed in a core&#39;s private cache. By not storing the second type of data in shared cache, cache usage and energy consumption may be reduced. 
   In embodiments of the invention, data may be classified as being of one of three types: (a) data that is likely to be re-used and likely to be used by one core at a time, (b) data that is unlikely to be re-used and likely to be used by one core at a time, and (c) data that is likely to be used by more than one core at a time. A threshold of the frequency of predicted re-use could be established as a basis for classifying data as type (a) or type (b) data. This threshold could vary depending on applications. However, generally speaking, when type (a) data does not fit in private cache, substantial economies may be realized by moving the data to a region of the shared cache that is closest to a core using the data, because the type (a) data will likely be accessed multiple times by that core before it is accessed by another core and is moved away. Similarly, benefits may be realized by special handling of type (b) data. Data classified as type (b) may not be stored in the shared cache at all, but rather stored only in a private cache. Because type (b) data will likely never be accessed in the shared cache before being evicted, it may reduce energy consumption, and decrease the contention for the shared cache space, to never move type (b) data to shared cache. 
   Type (c) data may be treated as in a conventional memory system with a private cache per core and another level of cache shared among the cores. 
     FIG. 1  shows a system  100  according to embodiments of the invention. The system may comprise a plurality of cores  101 . 1 ,  101 . 2 , . . . ,  101 . n . Each core may have respective private L1 (level one) cache  102 . 1 ,  102 . 2 , . . . ,  102 . n . Although only a single level of private cache is shown, in embodiments there could be multiple levels of private cache. The cores and their associated private cache may be coupled via interconnect  103  to shared cache (also, “last level cache” or LLC) banks  104 . 1 ,  104 . 2 , . . . ,  104 . m  (the correspondence of cores to shared cache banks is not necessarily one-to-one). The system may further comprise a plurality of roaming data pointers (RDPs)  105 . 1 ,  105 . 2 , . . . ,  105 . p  (the correspondence of the RDPs to the shared cache banks and cores is not necessarily one-to-one). The RDPs may point to cores. Collectively, the private and shared caches, and associated hardware may be known as a “cache subsystem.” 
   Conventionally, as processing in a multiple-core system such as system  100  takes place, an address hashing function is performed to determine where to allocate cache lines in the shared cache  104 . 1 ,  104 . 2 , . . . ,  104 . m , store data in them, and find that data. The address hashing function may be designed to distribute the data evenly among all banks. Type (a) data and type (b) data are considered “roaming data” since they are not necessarily in a location defined by this conventional address hashing function. The RDPs may point to cores that have handled roaming data, thereby enabling the roaming data to be located as described in more detail further on. 
   In the arrangement of  FIG. 1 , there is a closest bank in the shared cache to each core. According to embodiments of the invention, data may be classified as type (a) data, and based on the classification, stored in the private cache of the core that is using the data and/or a closest bank in the shared cache to that core. Conventionally, the data would instead be stored in a location in the shared cache determined by the conventional address hashing function described previously and possibly the core&#39;s private cache as well. By storing type (a) data in the closest bank, the data may be subsequently retrieved by that same core with reduced energy consumption and access time compared to the conventional scheme. 
   The classifying of the data as being of a predetermined type may, for example, be at least partly based on logic of a software program operating on the data, which has knowledge of the data based on a programmer&#39;s point of view. Such program logic may propagate type information to the cache subsystem. For example, the instructions in the program may contain bits indicating the classification of data they most often touch. 
   The initial classification provided by the software may be the basis for handling of the data following certain hardware operations on the data, which may reveal properties of the data or the processing environment which are not necessarily apparent to a programmer. These hardware operations may include, for example, evicting the data from private cache because private cache capacity or associativity is exceeded. Such operations are an indication that the data may be part of an important data set that does not fit in the private cache. Accordingly, if the data evicted from private cache is type (a), the evicted data may be stored in a closest bank of shared cache as described above. In  FIG. 1 , this process is illustrated. Cache line  102 . 1   i  is being evicted from private cache  102 . 1  and placed in closest shared cache bank  104 . 1 , as cache line  104 . 1   i . If the data evicted is of type (b) and is dirty (i.e., has been written), the data may be sent back to external memory; otherwise, it may be discarded. In embodiments of the invention, coherence evictions may not trigger the above events. 
   Type (c) data may be treated as in a conventional memory system with a private cache per core and another level of cache shared amongst the cores. For example, one possible coherence protocol would operate as follows. On a private cache miss, the data will be brought into the requesting core&#39;s private cache and also into the shared cache bank corresponding to the shared cache&#39;s address hashing function. On a private cache eviction, if the data is dirty, it will be written back to the shared cache; otherwise, the data is discarded. 
   Events subsequent to the initial classification may indicate that re-classification of data is in order. Accordingly, embodiments of the invention further relate to re-classifying data, for example, from type (a) or (b) to type (c), or from type (c) to type (a) or (b). 
   The preceding has discussed aspects of how data may be classified and handled with respect to shared cache, based on its classification. The discussion now turns to how roaming (type (a) and (b)) data is tracked and located within the cache subsystem. According to embodiments of the invention, when a private cache miss occurs for roaming data, the data may be brought into the requesting core&#39;s private cache. The source of the data could be external memory or could be somewhere in the cache subsystem, depending on earlier events. When the data is brought into the requesting core&#39;s private cache, an entry may be allocated in an RDP for the roaming data. More specifically, the address of the roaming data may be used as input to an RDP address hashing function, whose output identifies a particular RDP in which to make the entry. That RDP entry may store the location of the requesting core. Consequently, the RDP entry indicates the core that last accessed the data, so that the data can be found in the event a different core requests the data. Additionally, when the data is brought into a private cache, it may further have an indicator, such as a flag written to a field of a cache line, storing its type. This information may facilitate identifying and possibly re-classifying data type in ongoing cache subsystem operations. 
   For type (b) data, the corresponding RDP entry may be invalidated after a private cache eviction, after being retained until the eviction in case a core needs to access this data while it is within the cache subsystem. 
   When a private cache miss occurs for a piece of roaming data, before fetching the data from external memory, the RDP corresponding to the RDP address hashing function may be consulted to determine whether the data is still within the cache subsystem. This operation may be performed because, although for roaming data it is likely that one core will use the data at a time, this is not guaranteed. A different core may need to access that same roaming data. Also, the last core to access the data may finish with it and no other core may access the data for some period of time. Either of the latter two conditions may mean that the needed data is still in the cache subsystem and that therefore retrieving the data from external memory is not necessary. If the data does have an RDP entry, the RDP entry will indicate the core that last accessed the data. If the data is roaming, the information in the RDP entry can be used to determine which core or shared cache bank may hold the data. 
   In view of the above discussion,  FIG. 2  shows a data retrieval method according to embodiments of the invention. As shown in block  201 , for a requesting core, on a miss in the private cache, it may be determined whether the missed data is roaming. In embodiments of the invention, a requesting instruction, such as a load, may specify the data&#39;s type, so that the determination as to whether the data is roaming can be made. Alternatively, hardware may predict or determine the data&#39;s type. In any event, if the data is roaming, the bank in the shared cache closest to the requesting core that missed in its private cache may be accessed, as shown in block  202 . If the needed data is found there (block  203 ), it may be supplied to the requesting core, as shown in block  204 . This outcome over time may yield significant savings in interconnect bandwidth, average memory latency, and energy consumption. 
   On the other hand, if the data is roaming but is not found in the closest bank to the requesting core, the data may have been accessed by a different core and consequently moved to that core&#39;s private cache or closest shared cache bank. Accordingly, the RDP corresponding to the data may be determined via the RDP address hashing function, as shown in block  205 . That RDP may be searched for an entry for the data in question, as shown in block  206 . If an entry is found, a message may be sent to the shared cache block and core corresponding to the RDP entry (the current possible locations of the data), and the RDP entry may be changed to point to the requesting core. The message may cause the data to be evicted from the private cache and/or the shared cache block (at least one of which currently stores the data) and sent to the core requesting it. The requesting core may place the data in its private cache. 
   As shown in blocks  207  and  208 , if the data is not roaming, the missed data may be located by conventional methods. That is, the shared cache block corresponding to the shared cache address hashing function may be searched, and the action taken depends on the coherence protocol. 
     FIG. 3  shows another method according to embodiments of the invention. As shown in block  301 , the method may comprise, for a first requesting core, missing roaming data in its private cache. The roaming data may then be brought into the first requesting core&#39;s private cache, from external memory or from somewhere in the cache subsystem, as shown in block  302 . As shown in block  303 , a pointer to the first requesting core may be formed, for example by creating an entry in an RDP. 
   As shown in block  304 , the roaming data may subsequently be evicted from the first requesting core&#39;s private cache. The eviction may be, for example, a capacity or associativity eviction. If the evicted data is type (a) data, it may be stored in shared cache, in a region of the shared cache that is closest to the first requesting core. The data may subsequently be accessed multiple times in the shared cache by the first requesting core and thus may be in just the shared cache or both the private cache of the first requesting core and the shared cache. 
   It may subsequently happen that a second requesting core misses data in its private cache. The second requesting core may accordingly determine whether the missed data is roaming data, as shown in block  305 . Assume the missed data is the roaming data last accessed by the first requesting core. Since the missed data is roaming data, the region of the shared cache that is closest to the second requesting core will be checked, as shown in block  306 . Since the data is not there, the pointer (e.g., the RDP corresponding to the missed data) may be referenced, as shown in block  307 - 308 . 
   The pointer will point to the first requesting core. Consequently, the data may be evicted from either or both of the private cache of the first requesting core or the shared cache bank corresponding to the first requesting core, and sent to the second requesting core, as shown in block  309 . The pointer may be updated to point to the second requesting core, as shown in block  310 . 
   As noted previously, embodiments of the invention may relate to re-classifying data based on events following initial classification. According to the embodiments, if, for example, no RDP entry is found for missed roaming data, the shared cache bank that the data would be stored in if the data were type (c) (i.e., the shared cache bank corresponding to the shared cache address hashing function) may be searched. If found via this search, the data may be re-classified as type (a) or (b) as appropriate, evicted from the shared cache block, sent to the requesting core, and copied into that core&#39;s private cache. In embodiments, the RDP lookup may be performed in parallel with the shared cache lookup. While possibly more expensive in terms of energy consumption and interconnect traffic, such a parallel search may find needed data faster than a serial search. 
   In another re-classifying operation, type (a) or (b) data may be re-classified as type (c) data. For example, it may happen that data was type (a) or type (b) with respect to certain instructions (e.g., a certain part of a program), but is type (c) with respect to other instructions (e.g., a different part of the program). Later instructions may therefore treat this data as non-roaming data. However, because the data was once roaming data, there may exist a corresponding RDP entry. Thus, according to embodiments of the invention, if non-roaming data is missed and the data is not found at the shared cache bank corresponding to the shared cache address hashing function, an RDP entry for the data in the RDP corresponding to the RDP address hashing function may be searched for. If an entry is found, a message may be sent to the shared cache block and core corresponding to the RDP entry (the current possible locations of the data). The message may cause the data to be changed to type (c), evicted from the private cache and/or the shared cache block (at least one of which currently stores the data) and sent to the shared cache bank corresponding to the shared cache address hashing function and the core requesting it. The requesting core may place the data in its private cache. The RDP entry may be invalidated. The foregoing operations allow data to change from type (a) or type (b) to type (c) and still be found. 
     FIG. 4  is a block diagram of a computer system  400  including at least two processors (also, “processor chips” or “processor packages”)  402 ,  407  and memory for use in accordance with an embodiment of the invention. Each processor  402 ,  407  may comprise a plurality of cores  101 . 1 - 101 . n  according to embodiments of the invention. Each core  101 . 1 - 101 . n  may be, for example, a processor core including ALU (arithmetic/logical unit) and FPU (floating point unit) execution units. The processors  402 ,  407  may be coupled to respective memories  401 ,  412  via respective local MCHs (memory controller hubs)  403 ,  409 . 
   The processors  402 ,  407  may further be coupled to a chipset  415  via point-to-point (also, CSI or “Configurable System Interconnect”) interfaces  405 ,  414  and  411 ,  416 . The processors  402 ,  407  may further be coupled to each other via point-to-point interfaces  406 ,  410 . The system  400  may further include high performance graphics logic  419 , which may be coupled to the chipset  415  via an interface  417 . The chipset  415  may be coupled via an interface  418  to additional system components, including a bus bridge  422 , I/O devices  423 , audio I/O logic  424 , keyboard/mouse logic  425 , communication logic  426  such as network interfaces, and data storage  427  (e.g., mass storage such as disk). The data storage  427  may store computer-executable code  428 . System components may be interconnected by buses, such as buses  421 ,  429 . 
   Each of the at least two processors  402 ,  407  may include logic to implement the invention. However, logic to implement the invention need not reside in the two processors. For example, the logic could reside elsewhere on a motherboard including the system  400 . 
   Several embodiments of the invention are specifically illustrated and/or described herein. However, it will be appreciated that modifications and variations of the invention are covered by the above teachings and within the purview of the appended claims without departing from the spirit and intended scope of the invention.