Location-aware cache-to-cache transfers
Patent 7676637 Issued on March 9, 2010. Estimated Expiration Date: 
April 27, 2024. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.
April 27, 2024. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.Patent ReferencesDistributed shared memory multiprocessor system based on a unidirectional ring bus using a snooping scheme Disk block cache management for a distributed shared memory computer system Transfer of data between processors in a multi-processor system Multiprocessor system and methods for transmitting memory access transactions for the same Method and apparatus for determining CC-NUMA intra-processor delays Cache coherency protocol with tagged intervention of modified values Methods and apparatus for cache intervention Patent #: 7100001 InventorsAssigneeApplicationNo. 10833197 filed on 04/27/2004US Classes:711/144Cache status data bitExaminersPrimary: Kim, MattAssistant: Patel, Kaushikkumar Attorney, Agent or FirmInternational ClassG06F 12/00DescriptionBACKGROUND OF THE INVENTION1. Field of the Invention The present invention relates to computer-based memory systems, and, more particularly, location-aware cache-to-cache transfers. 2. Description of the Related Art A symmetric multiprocessor ("SMP") system generally employs a snoopy mechanism to ensure cache coherence. When a cache miss occurs, the requesting cache may send a cache request to the memory and all its peer caches. When a peer cache receivesthe cache request, it snoops its cache directory and produces a cache snoop response indicating whether the requested data is found and the state of the corresponding cache line. If the requested data is found in a peer cache, the peer cache can sourcethe data to the requesting cache via a cache-to-cache transfer. The memory is responsible for supplying the requested data if the data cannot be supplied by any peer cache. For purposes of this disclosure, a cache-to-cache transfer is referred to as a cache intervention. In a cache intervention, the cache that requests data is referred to as the requesting cache, and the cache that supplies data is referred to asthe supplying cache or the sourcing cache. A cache is said to have intervention responsibility for a memory address to a peer cache, if the cache is responsible for supplying requested data of the memory address to the peer cache. Referring now to FIG. 1, an exemplary SMP system 100 is shown that includes multiple processing units 105 interconnected via an interconnect network 110. Each processing unit 105 includes a processor core 115 and a cache 120. Also connected tothe interconnect network 110 are a memory 125 and some I/O devices 130. The memory 125 can be physically distributed into multiple memory portions, wherein each memory portion is operatively associated with a processing unit 105. The interconnectnetwork 110 serves at least two purposes: (1) sending cache coherence requests to the caches 120 and the memory 125; and (2) transferring data among the caches 120 and the memory 125. The interconnect network 110 can employ different physical networksfor different purposes. For example, an SMP system can broadcast a cache request via direct point-to-point communication channels, and transfer data via a message-passing network such as a mesh or torus network. There are many techniques for achieving cache coherence that are known to those skilled in the art. A number of snoopy cache coherence protocols have been proposed. The MESI coherence protocol and its variations have been widely used in SMPsystems. As the name suggests, MESI has four cache states, modified (M), exclusive (E), shared (S) and invalid (I). I (invalid): The data is not valid. This is the initial state or the state after a snoop invalidate hit. S (shared): The data isvalid, and can also be valid in other caches. This state is entered when the data is sourced from the memory or another cache in the modified state, and the corresponding snoop response shows that the data is valid in at least one of the other caches. E (exclusive): The data is valid, and has not been modified. The data is exclusively owned, and cannot be valid in another cache. This state is entered when the data is sourced from the memory or another cache in the modified state, and thecorresponding snoop response shows that the data is not valid in another cache. M (modified): The data is valid and has been modified. The data is exclusively owned, and cannot be valid in another cache. This state is entered when a store operation isperformed on the cache line. With the MESI protocol, when a cache miss occurs, if the requested data is found in another cache and the cache line is in the modified state, the cache with the modified data supplies the data via a cache intervention, and writes the mostup-to-date data back to the memory. However, if the requested data is found in another cache and the cache line is in the shared state, the cache with the shared data does not supply the requested data. In this case, the memory needs to supply the datato the requesting cache. In modern SMP systems, when a cache miss occurs, if the requested data is found in both the memory and a cache, supplying the requested data to the requesting cache via a cache intervention is often preferred over supplying the requested data tothe requesting cache from the memory, because cache-to-cache transfer latency is usually smaller than memory access latency. Furthermore, when caches are on the same die or in the same package module, there is usually more bandwidth available forcache-to-cache transfers, compared with the bandwidth available for off-chip DRAM accesses. The IBM.RTM. Power 4 system, for example, enhances the MESI coherence protocol to allow more cache interventions. Compared with MESI, an enhanced coherence protocol allows data of a shared cache line to be sourced via a cache intervention. Inaddition, if data of a modified cache line is sourced from one cache to another, the modified data does not have to be written back to the memory immediately. Instead, a cache with the most up-to-date data can be held responsible for memory update whenit becomes necessary to do so. An exemplary enhanced MESI protocol employing seven cache states is as follows. I (invalid): The data is invalid. This is the initial state or the state after a snoop invalidate hit. SL (shared, can be sourced): Thedata is valid, and may also be valid in other caches. The data can be sourced to another cache in the same module via a cache intervention. This state is entered when the data is sourced from another cache or from the memory. S (shared): The data isvalid, and may also be valid in other caches. The data cannot be sourced to another cache. This state is entered when a snoop read hit occurs on a cache line in the SL state. M (modified): The data is valid, and has been modified. The data isexclusively owned, and cannot be valid in another cache. The data can be sourced to another cache. This state is entered when a store operation is performed on the cache line. Me (exclusive): The data is valid, and has not been modified. The data isexclusively owned, and cannot be valid in another cache. Mu (unsolicited modified): The data is valid, and is considered to have been modified. The data is exclusively owned, and cannot be valid in another cache. T (tagged): The data is valid, and hasbeen modified. The modified data has been sourced to another cache. This state is entered when a snoop read hit occurs on a cache line in the M state. When data of a memory address is shared in multiple caches in a single module, the module can include at most one cache in the SL state. The cache in the SL state is responsible for supplying the shared data via a cache intervention when a cachemiss occurs in another cache in the same module. At any time, the particular cache that can source the requested data is fixed, regardless of which cache has issued the cache request. When data of a memory address is shared in more than one module,each module can include a cache in the SL state. A cache in the SL state can source the data to another cache in the same module, but cannot source the data to a cache in a different module. In systems in which a cache-to-cache transfer can take multiple message-passing hops, sourcing data from different caches can result in different communication latency and bandwidth consumption. When a cache miss occurs in a requesting cache, ifrequested data is found in more than one peer cache, a peer cache that is closest to the requesting cache is preferred to supply the requested data to reduce communication latency and bandwidth consumption of cache intervention. Thus, it is generally desirable to enhance cache coherence mechanisms with cost-conscious cache-to-cache transfers to improve overall performance in SMP systems. SUMMARY OF THE INVENTION In one aspect of the present invention, a system of location-aware cache intervention in a computer system is presented. The system comprises a plurality of caches, comprising a first cache and at least one other cache; wherein the first cachemaintains intervention information for at least one memory address, the intervention information indicating for which of the at least one other cache the first cache has intervention responsibility. In a second aspect of the present invention, a system of location-aware cache intervention in a computer system is presented. The system comprises a plurality of cache clusters, comprising a first cache cluster and at least one other cachecluster; wherein each of the plurality of cache clusters comprises at least one cache, the first cache cluster comprises a first cache; and wherein the first cache maintains intervention information for at least one memory address, the interventioninformation indicating for which of the at least one other cache cluster the first cache has intervention responsibility. In a third aspect of the present invention, a system of location-aware cache intervention in a computer system is presented. The system comprises a plurality of caches, comprising a first cache and at least one other cache; wherein the firstcache maintains location information for at least one memory address, the location information for a memory address in the at least one memory address indicating in which of the at least one other cache data of the memory address is cached or likely tobe cached. In a fourth aspect of the present invention, a system of location-aware cache intervention in a computer system is presented. The system comprises a plurality of cache clusters, comprising a first cache cluster and at least one other cachecluster; wherein each of the plurality of cache clusters comprises at least one cache, the first cache cluster comprises a first cache; and wherein the first cache maintains location information for at least one memory address, the location informationfor a memory address in the at least one memory address indicating in which of the at least one other cache cluster data of the memory address is cached or likely to be cached. In a fifth aspect of the present invention, a system for location-aware cache intervention is presented. The system comprises a plurality of caches, comprising a first cache, a second cache and at least one other cache; wherein if the firstcache receives a data request from the second cache, the first cache supplies requested data if the first cache has the requested data, and snoop responses from the at least one other cache indicate that the cache intervention cost of supplying the datafrom the first cache to the second cache is lower than the cache intervention cost of supplying the data from any of the at least one other cache to the second cache. In a sixth aspect of the present invention, a method of location-aware cache intervention in a computer system is presented. The method comprises a first cache receiving a data request from a second cache; the first cache determining orpredicting whether the first cache has the lowest cache intervention cost of any cache that can source requested data to the second cache; and the first cache supplying the requested data to the second cache via a cache intervention, if the first cachedetermines or predicts that the first cache has the lowest cache intervention cost of any cache that can source the requested data to the second cache. BRIEF DESCRIPTION OF THE DRAWINGS The invention may be understood by reference to the following description taken in conjunction with the accompanying drawings, in which like reference numerals identify like elements, and in which: FIG. 1 shows a typical SMP system that includes a number of processing units connected via an interconnect network, wherein each processing unit includes a processor core and a cache; FIG. 2 shows an exemplary SMP system that comprises a number of caches, in accordance with some embodiments of the present invention; FIG. 3 shows an exemplary SMP system that comprises a number of cache clusters, in accordance with some embodiments of the present invention; and FIG. 4 shows an exemplary SMP system that uses a unidirectional ring to generate partially combined snoop response, and uses a data network to transfer data between caches and memory, in accordance with one embodiment of the present invention. DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS Illustrative embodiments of the invention are described below. In the interest of clarity, not all features of an actual implementation are described in this specification. It will be appreciated that in the development of any such actualembodiment, numerous implementation-specific decisions must be made to achieve the developers' specific goals, such as compliance with system-related and business-related constraints, which will vary from one implementation to another. Moreover, it willbe appreciated that such a development effort might be complex and time-consuming, but would nevertheless be a routine undertaking for those of ordinary skill in the art having the benefit of this disclosure. While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof have been shown by way of example in the drawings and are herein described in detail. It should be understood, however, that thedescription herein of specific embodiments is not intended to limit the invention to the particular forms disclosed, but on the contrary, the intention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope ofthe invention as defined by the appended claims. It should be understood that the systems and methods described herein may be implemented in various forms of hardware, software, firmware, or a combination thereof. The methods may be stored on amachine-readable medium, for example, a cache memory, a memory system, or any storage media, having instructions stored thereon for execution by a processor to be performed in a computer system. Location-aware cache intervention allows cost-conscious cache-to-cache transfers in a cache coherent multiprocessor system. With location-aware cache intervention, when a cache receives a data request of a cache miss, if requested data is foundin the cache, the cache can determine (or predict) whether sourcing the data from this cache would result in less intervention cost than sourcing the data from another cache. The decision (or prediction) can be made based on appropriate informationmaintained in the cache or supplied by cache snoop responses from other caches. At any time, the particular cache that can source data depends on the location of the requesting cache. If the requested data is found in more than one cache, the cachethat has (or is predicted to have) the lowest intervention cost is responsible for supplying the data. The intervention cost can be measured by performance metrics that include, but are not limited to, communication latency, bandwidth consumption, loadbalance, power consumption, and other performance metrics. Exemplary SMP systems with snoopy cache coherence support will be used to illustrate embodiments in this disclosure. It should be appreciated that the present invention is not limited to snoopy cache coherence schemes. For example, the presentinvention may employ a directory-based cache coherence scheme, as contemplated by those skilled in the art. Furthermore, it should be appreciated that the present invention is not limited to SMP systems. For example, the present invention may beapplied to a non-symmetric multiprocessor system, as contemplated by those skilled in the art. Referring now to FIG. 2, an exemplary SMP system 200 is shown comprising six processing units (labeled "processing unit 0" to "processing unit 5") that are connected via a bi-directional ring-based interconnect 205, in accordance with someembodiments of the present invention. The system 200 also comprises a memory (not shown) shared by the processing units 0-5. Each processing unit 0-5 includes a processor core (labeled "processor core 0" to "processor core 5") and a cache (labeled"cache 0" to "cache 5"). Although the bi-directional ring-based interconnect 205 is used throughout the discussion, it is understood that the present invention can be applied to systems that use any of a variety of different interconnects. Although sixprocessing units 0-5 are depicted, it is understood that any number of processing units may be included in the system 200. Furthermore, although only one cache is shown in each processing unit 0-5, it is understood that each processing unit 0-5 maycomprise a cache hierarchy with multiple caches, as contemplated by those skilled in the art. Throughout the present disclosure, we use the number of communication hops between requesting and supplying caches to measure the cost of a cache intervention. For example, it takes one hop to source data from cache 2 to cache 3, and two hops tosource data from cache 5 to cache 3. Without losing generality, we use a simple exemplary tie-breaking method for caches with equal communication hops: a cache with a higher identification number is deemed to have less communication cost. Therefore,although sourcing data from cache 2 to cache 4 takes the same number of hops as sourcing data from cache 0 to cache 4, cache 2 is preferred over cache 0 to supply data to cache 4 because identification number 2 is a higher than identification number 0. It is understood that any of a variety of metrics can be used to measure the cost of a cache intervention, as contemplated by those skilled in the art. It is also understood that a different tie-breaking method may be used, as contemplated by thoseskilled in the art. Referring now to FIG. 3, another exemplary SMP system 300 is shown comprising eight processing units (labeled "processing unit 0" to "processing unit 7") that are connected via the bi-directional ring-based interconnect 205. The system 300 alsocomprises a memory (not shown) shared by the processing units 0-7. Each processing unit 0-7 includes a processor core (labeled "processor core 0" to "processor core 7") and a cache (labeled "cache 0" to "cache 7"). The processing units 0-7 are groupedinto four clusters (labeled "cluster 0" to "cluster 3"), wherein each cluster 0-3 includes two processing units 0-7. Although the bi-directional ring-based interconnect 205 is used throughout the discussion, it is understood that the present inventioncan be applied to systems that use any of a variety of different interconnects. Although the system 300 comprises four clusters 0-3 and each cluster 0-3 comprises two processing units 0-7, it is understood that the system 300 can include any number ofclusters and a cluster can include any number of processing units. Furthermore, although only one cache is shown in each processing unit 0-7, it is understood that each processing unit 0-7 may comprise a cache hierarchy with multiple caches, ascontemplated by those skilled in the art. Throughout the present disclosure, we use the number of inter-cluster communication hops to measure the cost of a cache intervention that sources data from a cache 0-7 in a cluster 0-3 to another cache 0-7 in a another cluster 0-3. For example,referring to FIG. 3, it takes one inter-cluster hop to source data from cache 0 to cache 3, and two inter-cluster hops to source data from cache 6 to cache 3. Without losing generality, we use a simple exemplary tie-breaking method for clusters withequal communication hops: a cluster with a higher identification number is deemed to have less communication cost. It is understood that any of a variety of metrics can be used to measure the cost of a cache intervention, as contemplated by thoseskilled in the art. It is also understood that a different tie-breaking method may be used, as contemplated by those skilled in the art. In a first illustrative embodiment, each cache maintains an intervention vector for each cache line with shared data. The intervention vector records for which peer caches the cache has intervention responsibility. The intervention vectorcomprises an intervention bit for each peer cache, indicating whether the cache is responsible for sourcing requested data of the cache line to the peer cache. When a cache receives a data request of a cache miss, it supplies the requested data if thecorresponding intervention vector shows that the cache is responsible for cache intervention to the requesting cache. When a sourcing cache supplies data via a cache intervention, the sourcing cache can offload some of its intervention responsibility to the requesting cache that is to receive the data. Consider a peer cache for which the sourcing cache has theintervention responsibility. If the peer cache is closer to the requesting cache than to the sourcing cache, the intervention responsibility for the peer cache can be transferred to the requesting cache. Referring to FIG. 2, we now describe an example of location-aware cache-to-cache transfers using intervention vectors. In our notation, each intervention vector maintains its intervention bits in sequential order, wherein the right-most-bitcorresponds to cache 0, and the left-most-bit corresponds to cache 5. Assume initially that no cache contains valid data of a given memory address. Consider the following exemplary sequence of cache operations on the address. (1) Cache 1 issues a data request, and the memory (not shown) supplies the requested data. The intervention vector in cache 1 is set to 111111 because cache 1 is the only cache that has the requested data. The intervention vector indicates thatcache 1 has intervention responsibility for all caches. (2) Cache 0 issues a data request, and cache 1 supplies the data. The intervention vector in cache 0 is set to 110001, indicating that cache 0 has intervention responsibility for caches 0, 4 and 5. On the other hand, the intervention vector incache 1 is set to 001110, indicating that cache 1 has intervention responsibility for caches 1, 2 and 3. (3) Cache 3 issues a data request, and cache 1 supplies the data according to its intervention vector. The intervention vector in cache 1 is set to 000010, offloading some intervention responsibility to cache 3. The intervention vector in cache3 is set to 001100, indicating that cache 3 has intervention responsibility for caches 2 and 3. The intervention vector in cache 0 remains unchanged. The table below summarizes the cache operations and the intervention vector updates, as describedabove. The label "-" indicates that a cache contains no valid data and therefore maintains no intervention information. TABLE-US-00001 Cache 0 Cache 1 Cache 2 Cache 3 Cache 4 Cache 5 (0) Initially no -- -- -- -- -- -- cache contains the data (1) Cache 1 -- 111111 -- -- -- -- requests, memory supplies the data (2) Cache 0 110001 001110 -- -- -- -- requests, cache1 supplies the data (3) Cache 3 110001 000010 -- 001100 -- -- requests, cache 1 supplies the data When a cache intervention occurs, intervention responsibility owned by a supplying cache can be split between the supplying cache and the corresponding requesting cache. Sometimes, intervention vectors in other caches also need to be adjusted toensure minimum intervention cost for future cache requests. In the example above, if later cache 4 issues a data request, cache 0 is responsible for sourcing the data according to its intervention vector, although cache 3 is closer to cache 4. Toremedy this problem, when a cache intervention occurs, the receiving cache can take appropriate intervention responsibility from not only the supplying cache, but also other caches as is necessary. In this case, when cache 0 observes that cache 3receives the data, cache 0 can offload intervention responsibility of cache 4 to cache 3, because cache 4 is closer to cache 3 than to cache 0. As a result, the intervention vectors in caches 0 and 3 become 100001 and 011100, respectively. The tablebelow illustrates the intervention vector updates. TABLE-US-00002 Cache 0 Cache 1 Cache 2 Cache 3 Cache 4 Cache 5 (0) Initially no -- -- -- -- -- -- cache contains the data (1) Cache 1 -- 111111 -- -- -- -- requests, memory supplies the data (2) Cache 0 110001 001110 -- -- -- -- requests, cache1 supplies the data (3) Cache 3 100001 000010 -- 001100 -- -- requests, cache 1 supplies the data When a cache issues a data request of a cache miss, it is possible that no cache supplies the requested data, although the data can be found in one or more caches. This can happen in at least two situations. In a first situation, a cachereplaces data of a cache line without transferring its intervention responsibility to other caches. In a second situation, a cache transfers some of its intervention responsibility to another cache, but the cache that is to receive the interventionresponsibility receives a data request before the corresponding intervention responsibility arrives. In the previous example, if cache 3 receives a data request from cache 4 before the offloaded intervention responsibility from cache 0, cache 3 will notsupply the requested data. Meanwhile, cache 0 also will not supply the data because it has transferred the intervention responsibility to cache 3. When a data request cannot be serviced by any cache, the memory can supply the requested data. A combined snoop response can include a combined intervention vector, wherein an intervention bit in the combined intervention vector is set to 1 ifthe corresponding intervention bit is set to 1 in any snooped cache. When a cache receives the requested data from the memory, the cache can assume intervention responsibility for each cache whose corresponding intervention bit is 0 in the combinedintervention vector. Referring again to FIG. 2, we now describe an example of intervention vector updates in case of cache line replacements. Assume initially that no cache contains valid data of a given memory address. Consider the following exemplary sequence ofcache operations on the address. (1) Cache 1 issues a data request, and the memory (not shown) supplies the requested data. The intervention vector in cache 1 is set to 111111. (2) Cache 0 issues a data request, and cache 1 supplies the requested data. The intervention vectors in caches 0 and 1 are set to 110001 and 001110, respectively. (3) Cache 1 replaces the data without informing other caches. As a result, no cache is responsible for cache intervention to caches 1, 2 and 3. (4) Cache 3 issues a data request, and the memory supplies the data. The intervention vector in cache 3 is set to 001110 according to the combined snoop response. The table below summarizes the cache operations and the intervention vectorupdates, as described above. TABLE-US-00003 Cache 0 Cache 1 Cache 2 Cache 3 Cache 4 Cache 5 (0) Initially no -- -- -- -- -- -- cache contains the data (1) Cache 1 -- 111111 -- -- -- -- requests, memory supplies the data (2) Cache 0 110001 001110 -- -- -- -- requests, Cache1 supplies the data (3) Cache 1 110001 -- -- -- -- -- replaces the data (4) Cache 3 110001 -- -- 001110 -- -- requests, memory supplies the data In the previous example, when the data is shared in caches 0 and 3, it is desirable to set the intervention vectors in caches 0 and 3 to be 100011 and 011100, respectively. This can be achieved by redistributing intervention responsibility atthe appropriate time. It is worth noting that the redistribution of intervention responsibility can be determined by the combined snoop response that shows all caches from which the data can be sourced. For a shared cache line, if an intervention bit is set in an intervention vector in a cache, the corresponding intervention bit cannot be set in another intervention vector in another cache. This is simply because no cache can obtainintervention responsibility that is owned by another cache. Therefore, even with imprecise intervention information, there can be at most one cache supplying data for a data request. Reducing the storage overhead resulting from intervention vectors is generally important in the implementation of location-aware cache-to-cache transfers. It is obvious that an intervention vector maintained in a cache does not need to includean intervention bit for the cache itself. Furthermore, intervention information represented by an intervention vector can often be encoded more compactly, because certain intervention bit permutations cannot happen due to various constraints. Referringto FIG. 2, for example, if cache 0 has intervention responsibility for cache 2, it should also have intervention responsibility for cache 1. Similarly, if cache 0 has intervention responsibility for cache 3, it should have intervention responsibilityfor all its peer caches. It can be shown that cache 0 allows the following intervention bit permutations (intervention bits corresponding to caches 1 to 5 are shown). 00000: Cache 0 has no intervention responsibility for any peer cache. 00001: Cache 0has intervention responsibility for cache 1. 00011: Cache 0 has intervention responsibility for caches 1 and 2. 10000: Cache 0 has intervention responsibility for cache 5. 11000: Cache 0 has intervention responsibility for caches 4 and 5. 11111:Cache 0 has intervention responsibility for all its peer caches. It is worth noting that intervention information can be encoded with a cache state to further reduce the storage overhead. Since intervention information is maintained only for a shared cache line, we can incorporate intervention information byemploying a number of distinct shared states in the cache coherence protocol, wherein each shared state represents some particular intervention responsibility. Referring again to FIG. 2, for example, cache 0 can have distinct shared states as follows,wherein each shared state specifies the corresponding intervention responsibility. Shared: Cache 0 has shared data that cannot be sourced to any peer cache. Shared-IR-1: Cache 0 has shared data that can be sourced to cache 1. Shared-IR-1-2: Cache 0has shared data that can be sourced to caches 1 and 2. Shared-IR-5: Cache 0 has shared data that can be sourced to cache 5. Shared-IR-4-5: Cache 0 has shared data that can be sourced to caches 4 and 5. Shared-IR-All: Cache 0 has shared data that canbe sourced to all its peer caches. This is generally equivalent to the exclusive state. In a second illustrative embodiment, caches are grouped into clusters according to proximity. Each cache line with shared data maintains an intervention vector that records cache clusters to which the cache is responsible for supplying the data. The intervention vector comprises an intervention bit for each cache cluster, indicating whether the cache is responsible for sourcing data to that cluster. Maintaining intervention information for cache clusters instead of individual caches can reducestorage space used by intervention vectors. When shared data is cached in a cluster, a cache in the cluster can be selected as the inter-cluster sourcing cache that can source data to a cache in another cluster. For a shared cache line, an intervention vector needs to be maintained onlyin an inter-cluster sourcing cache. In addition, a cache in the cluster can be selected as the intra-cluster sourcing cache that can source data to another cache in the same cluster. For example, the cache that receives the last shared copy in thecluster can be selected as the intra-cluster sourcing cache. If a cluster includes an inter-cluster sourcing cache and an intra-cluster sourcing cache, the inter-cluster sourcing cache and the intra-cluster sourcing cache may be the same cache. When an inter-cluster sourcing cache receives a data request from a requesting cache in another cluster, the inter-cluster sourcing cache supplies requested data to the requesting cache via a cache intervention, if the intervention vector showsthat the inter-cluster sourcing cache has intervention responsibility for the requesting cluster. When a cache supplies data to another cache via an inter-cluster cache intervention, it can offload some of its intervention responsibility to the cachethat is to receive the data. Referring to FIG. 3, we now describe an example of maintaining intervention vectors for cache clusters. In our notation, each intervention vector maintains its intervention bits in sequential order, wherein the right-most-bit corresponds tocache cluster 0, and the left-most-bit corresponds to cache cluster 3. Assume initially that no cache contains valid data of a given memory address. Consider the following exemplary sequence of cache operations on the address. (1) Cache 1 issues a data request, and the memory (not shown) supplies the data. The intervention vector in cache 1 is set to 1111, indicating that cache 1 has intervention responsibility for all clusters. (2) Cache 0 issues a data request, and cache 1 supplies the data. Cache 0 receives intervention information from cache 1, and becomes the sourcing cache in cluster 0. (3) Cache 2 issues a data request, and cache 0 supplies the data. The intervention vector in cache 0 is set to 1001, offloading some of its intervention responsibility to cache 2. The intervention vector in cache 2 is set to 0110, indicatingthat cache 2 has intervention responsibility for clusters 1 and 2. (4) Cache 5 issues a data request, and cache 2 supplies the data according to its intervention vector. The intervention vectors in caches 2 and 5 are set to 0010 and 0100, respectively. The table below summarizes the cache operations and theintervention vector updates, as described above. The label "S" indicates that a cache contains shared data that cannot be sourced to another cache, and the label "-" indicates that a cache contains no valid data and therefore maintains no interventioninformation. TABLE-US-00004 Cluster 0 Cluster 1 Cluster 2 Cluster 3 Cache 0 Cache 1 Cache 2 Cache 3 Cache 4 Cache 5 Cache 6 Cache 7 (0) Initially no -- -- -- -- -- -- -- -- cache contains the data (1) Cache 1 receives -- 1111 -- -- -- -- -- -- the data frommemory (2) Cache 0 receives 1111 S -- -- -- -- -- -- the data from cache 1 (3) Cache 2 receives 1001 S 0110 -- -- -- -- -- the data from cache 0 (4) Cache 5 receives 1001 S 0010 -- -- 0100 -- -- the data from cache 2 It is obvious that an intervention vector maintained in a cache cluster does not need to include an intervention bit for the cache cluster itself. Furthermore, intervention information represented by an intervention vector can often be encodedmore compactly, because certain intervention bit permutations cannot happen due to various constraints. Referring to FIG. 3, for example, if a cache in cache cluster 0 has intervention responsibility for cache cluster 2, it should also have interventionresponsibility for cache clusters 1 and 3. It can be shown that a cache in cache cluster 0 allows the following intervention bit permutations (intervention bits corresponding to cache clusters 1 to 3 are shown). 000: The cache has no interventionresponsibility for any peer cluster. 001: The cache has intervention responsibility for cluster 1. 100: The cache has intervention responsibility for cluster 3. 111: The cache has intervention responsibility for clusters 1, 2 and 3. It is worth noting that intervention information can be encoded with a cache state to further reduce the storage overhead. Since intervention information is maintained only for a shared cache line, we can incorporate intervention information byemploying a number of distinct shared states in the cache coherence protocol, wherein each shared state represents some particular intervention responsibility. Referring again to FIG. 3, for example, a cache in cache cluster 0 can have distinct sharedstates as follows, wherein each shared state specifies the corresponding intervention responsibility. Shared: The cache has shared data that cannot be sourced to another cache. Shared-IR-0: The cache has shared data that can be sourced to another cachein cluster 0. This usually indicates that the cache is an intra-cluster sourcing cache but not an inter-cluster sourcing cache. Shared-IR-0-1: The cache has shared data that can be sourced to another cache in clusters 0 and 1. Shared-IR-0-3: The cachehas shared data that can be sourced to another cache in clusters 0 and 3. Shared-IR-All: The cache has shared data that can be sourced to another cache in any cluster. This usually indicates that the data is only cached in cluster 0. In a third illustrative embodiment, each cache maintains a location vector for each cache line with shared data. The location vector records the caches in which the data is valid. The location vector comprises a location bit for each peercache, wherein the location bit indicates whether the data is being cached in that cache. When a cache receives a data request of a cache miss, the cache supplies the requested data via a cache intervention, if the data is found in the cache, and the corresponding location vector indicates that the cache has a lower cache interventioncost compared with other caches in which the data can also be found. In addition to the requested data, the supplying cache can also provide its location vector information to the requesting cache. When the requesting cache receives the data, therequesting cache can set its location vector according to the location information from the supplying cache. A location-aware cache coherence protocol can choose to maintain precise location information. As a result, when a cache miss occurs, if requested data is resident in one or more caches, exactly one cache will supply the data via a cacheintervention. Alternatively, a location-aware cache coherence protocol can choose to maintain location information as heuristic information that may not necessarily be up-to-date. Consequently, when a cache miss occurs, if requested data is resident inone or more caches, it is possible that more than one cache supplies the data, or no cache supplies the data. In the latter case, a proper mechanism is needed to ensure that the cache miss is eventually serviced. Referring to FIG. 2, we show an example of location-aware cache-to-cache transfers based on precise location information. In our notation, each location vector maintains its location bits in sequential order, wherein the right-most-bitcorresponds to cache 0, and the left-most-bit corresponds to cache 5. Assume initially that no cache contains valid data of a given memory address. Consider the following exemplary sequence of cache operations on the address. (1) Cache 1 issues a data request, and the memory (not shown) supplies the data. The location vector in cache 1 is set to 000010, indicating that the data is valid only in cache 1. (2) Cache 0 issues a data request, and cache 1 supplies the data. The location vectors in caches 0 and 1 are set to 000011, indicating that the data is valid in caches 0 and 1. (3) Cache 2 issues a data request, and cache 1 supplies the data according to the location information. The location vectors in caches 0, 1 and 2 are set to 000111, indicating that the data is valid in caches 0, 1 and 2. (4) Cache 3 issues a data request, and cache 2 supplies the data according to its location information. The location vectors in caches 0, 1, 2 and 3 are set to 001111, indicating that the data is valid in caches 0, 1, 2 and 3. (5) Cache 3 replaces the data from the cache, and informs other caches of the cache line replacement. As a result, the location vectors in caches 0, 1 and 2 are updated to 000111 accordingly. (6) Cache 4 issues a data request, and cache 2 supplies the data according to its location information. The location vectors in caches 0, 1, 2 and 4 are set to 010111, indicating that the data is valid in caches 0, 1, 2 and 4. The table belowsummarizes the cache operations and the location vector updates, as described above. The label "-" indicates that a cache contains no valid data and therefore maintains no location information. TABLE-US-00005 Cache 0 Cache 1 Cache 2 Cache 3 Cache 4 Cache 5 (0) Initially -- -- -- -- -- -- no cache contains the data (1) Cache 1 -- 000010 -- -- -- -- requests, memory supplies the data (2) Cache 0 000011 000011 -- -- -- -- requests, cache1 supplies the data (3) Cache 2 000111 000111 000111 -- -- -- requests, cache 1 supplies the data (4) Cache 3 001111 001111 001111 001111 -- -- requests, cache 2 supplies the data (5) Cache 3 000111 000111 000111 -- -- -- replaces the data (6) Cache 4010111 010111 010111 -- 010111 -- requests, cache 2 supplies the data Maintaining up-to-date location vector information can be difficult and expensive. This is because a cache operation in one cache may not necessarily be observable to another cache. For example, a cache may prefer not to inform other caches incase of replacement of a cache line. This implies that other caches may not be able to update their location vectors accordingly due to the lack of information. Another reason of imprecise location information is the latency of location vector updates. For example, when a cache issues a data request and receives the requested data, it may take some time before other caches are notified. Imprecise location information can be used as heuristic information to improve system performance. With imprecise location vector information, a data request can result in multiple cache interventions or no cache intervention (though the data isvalid in one or more caches). If more than one cache supplies the data, the requesting cache can use the data that arrives first and discard other redundant copies. If no cache supplies the data, the memory can source the data to the requesting cache. An alternative is to reissue the data request if the combined snoop response shows that the data is valid in one or more caches. A particular cache (e.g., the cache with the last received shared copy) can be pre-assigned as the default sourcing cachewhich is responsible for servicing the reissued data request. Referring again to FIG. 2, we show an exemplary scenario in which multiple cache interventions are invoked by a cache request due to imprecise location information. Assume initially that no cache contains valid data of a given memory address. Consider the following exemplary sequence of cache operations on the memory address. (1) Cache 1 issues a data request, and the memory (not shown) supplies the data. The location vector in cache 1 is set to 000010. (2) Cache 0 issues a data request, and cache 1 supplies the data. The location vectors in caches 0 and 1 are set to 000011. (3) Cache 3 issues a data request, and cache 1 supplies the data. The location vectors in caches 1 and 3 are set to 001011, indicating that the data is valid in caches 0, 1 and 3. However, the location vector in cache 0 is not immediatelyupdated. (4) Cache 4 issues a data request, which arrives at cache 0 before the pending location update completes. In this case, both cache 0 and cache 3 will supply the data to cache 4. This is because the imprecise location vector in cache 0incorrectly shows that cache 0 is the closest cache with the requested data. The table below summarizes the cache operations and the location vector updates, as described above. TABLE-US-00006 Cache 0 Cache 1 Cache 2 Cache 3 Cache 4 Cache 5 (0) Initially -- -- -- -- -- -- no cache contains the data (1) Cache 1 -- 000010 -- -- -- -- requests, memory supplies the data (2) Cache 0 000011 000011 -- -- -- -- requests, cache1 supplies the data (3) Cache 3 000011 001011 -- 001011 -- -- requests, cache 1 supplies the data (4) Cache 4 011011 011011 -- 011011 011011 -- requests, cache 0/3 supply the data Referring again to FIG. 2, we show an exemplary scenario in which no cache intervention is invoked by a cache request due to imprecise location information. Assume initially that no cache contains valid data of a given memory address. Considerthe following exemplary sequence of cache operations on the address. (1) Cache 1 issues a data request, and the memory (not shown) supplies the data. The location vector in cache 1 is set to 000010. (2) Cache 0 issues a data request, and cache 1 supplies the data. The location vectors in caches 0 and 1 are set to 000011. (3) Cache 3 issues a data request, and cache 1 supplies the data. The location vectors in caches 0, 1 and 3 are set to 001011, indicating that the data is valid in caches 0, 1 and 3. (4) Cache 3 replaces its data without notifying other caches. (5) Cache 4 issues a data request, and no cache will supply the data. This is because the imprecise location vectors in caches 0 and 1 incorrectly show that cache 3 is to supply the requested data. In this case, the memory will supply the datato cache 4. The table below summarizes the cache operations and the location vector updates, as described above. TABLE-US-00007 Cache 0 Cache 1 Cache 2 Cache 3 Cache 4 Cache 5 (0) Initially -- -- -- -- -- -- no cache contains the data (1) Cache 1 -- 000010 -- -- -- -- requests, memory supplies the data (2) Cache 0 000011 000011 -- -- -- -- requests, cache1 supplies the data (3) Cache 3 001011 001011 -- 001011 -- -- requests, cache 1 supplies the data (4) Cache 3 001011 001011 -- -- -- -- replaces the data (5) Cache 4 010011 010011 -- -- 010011 -- requests, memory supplies the data the data Snoop responses can be used to detect and repair imprecise location information. In the previous example, when cache 4 issues a data request, a snoop response from cache 3 indicates that the requested data is not cached in cache 3. When cache 0observes the snoop response from cache 3, cache 0 will realize that its location information regarding cache 3 is incorrect and therefore can update its location information accordingly. In practice, it is unnecessary for a location vector to include a location bit for the cache in which the location vector is maintained. Instead, each shared cache line can maintain an N-1 bit location vector, where N is number of caches in thesystem. It is worth noting that a location vector of a cache line may be encoded with the corresponding cache state to further reduce implementation overhead. In a fourth illustrative embodiment, caches are grouped into clusters according to proximity. Each cache line with shared data maintains a location vector that records which cache clusters have the shared data. The location vector comprises alocation bit for each cache cluster, indicating whether the data is cached in that cache cluster. Maintaining location information for cache clusters instead of individual caches can reduce storage space used by location vectors. When a cache receivesa data request from a different cluster, the cache supplies the requested data via a cache intervention, if the data is found in the cache, and the corresponding location vector indicates that the cache has a lower cache intervention cost compared withcaches in other clusters in which the data can also be found. Referring to FIG. 3, we now describe an example of maintaining location vectors for cache clusters. In our notation, each location vector maintains its location bits in sequential order, wherein the right-most-bit corresponds to cache cluster 0,and the left-most-bit corresponds to cache cluster 3. Assume initially that no cache contains valid data of a given memory address. Consider the following exemplary sequence of cache operations on the address. (1) Cache 1 issues a data request, and the memory (not shown) supplies the data. The location vector in cache 1 is set to 0001, indicating that the data is valid only in cluster 0. (2) Cache 0 issues a data request, and cache 1 supplies the data. Cache 0 receives location information from cache 1, and becomes the sourcing cache in cluster 0. (3) Cache 2 issues a data request, and cache 0 supplies the data. The location vectors in caches 0 and 2 are set to 0011, indicating that the data is valid in clusters 0 and 1. (4) Cache 5 issues a data request, and cache 2 supplies the data according to its location vector. The location vectors in caches 0, 2 and 5 are set to 0111, indicating that the data is valid in clusters 0, 1 and 2. The table below summarizesthe cache operations and the location vector updates, as described above. The label "S" indicates that a cache contains shared data that cannot be sourced to another cache, and the label "-" indicates that a cache contains no valid data and thereforemaintains no location information. TABLE-US-00008 Cluster 0 Cluster 1 Cluster 2 Cluster 3 Cache 0 Cache 1 Cache 2 Cache 3 Cache 4 Cache 5 Cache 6 Cache 7 (0) Initially no -- -- -- -- -- -- -- -- cache contains the data (1) Cache 1 receives -- 0001 -- -- -- -- -- -- the data frommemory (2) Cache 0 receives 0001 S -- -- -- -- -- -- the data from cache 1 (3) Cache 2 receives 0011 S 0011 -- -- -- -- -- the data from cache 0 (4) Cache 5 receives 0111 S 0111 -- -- 0111 -- -- the data from cache 2 In practice, it is unnecessary for a location vector to maintain a location bit for the cache cluster in which the location vector is maintained. Instead, each shared cache line can maintain an N-1 bit location vector, where N is the number ofcache clusters in the system. It is worth noting that a location vector of a cache line may be encoded with the corresponding cache state to further reduce storage overhead. In a fifth illustrative embodiment, each cache can use snoop responses from its peer caches to determine or predict whether the cache has the lowest cache intervention cost of any cache from which requested data can be supplied. When a cachereceives a data request from a requesting cache, the cache sources the requested data to the requesting cache via a cache intervention, if the cache contains the requested data, and snoop responses from other caches indicate that the requested datacannot be supplied from another cache with lower intervention cost. When a cache is snooped due to a data request, the cache generates a snoop response indicating whether requested data is found and the state of the corresponding cache line. This information can be made available to other caches via variousapproaches. In a first exemplary approach, a snoop response from each cache can be directly sent to all other caches. In a second exemplary approach, a snoop response from each cache can be sent to a snoop response combining component, which generatesa combined snoop response indicating caches from which requested data can be supplied. The combined snoop response can then be sent to all caches in the system. In a third exemplary approach, a combined snoop response can be generated based on apartially combined snoop response ("PCSR") accumulated step-by-step using a unidirectional ring. When a cache miss occurs, the requesting cache sends an initial PCSR with a null value to the subsequent cache in the ring. When a cache receives a PCSR,the cache combines the PCSR with its own snoop response to generate a new PCSR, which is then sent to the subsequent cache in the ring. When a fully combined snoop response is finally generated, it can be sent to all caches in the system. It is worth pointing out that, compared with the previous embodiments described above, location-aware cache intervention based on snoop responses can eliminate the storage overhead resulting from intervention or location vectors. Althoughlocation-aware cache intervention based on snoop responses can reduce bandwidth consumption of cache-to-cache transfers, it may increase latency to service a cache request since requested data cannot be sourced from a cache until corresponding snoopresponses from other caches become available. To reduce latency of servicing a cache request, location-aware cache intervention decision or prediction can be made according to snoop responses from some peer caches instead of all peer caches. Given a requesting cache and a potential sourcingcache, some particular peer caches can be chosen as snoop response required caches, indicating that the potential sourcing cache needs their snoop responses to decide or predict whether the potential sourcing cache should supply data to the requestingcache. The snoop response required caches generally include those peer caches that can source data to the requesting cache with a lower cache intervention cost than the potential sourcing cache. When the potential sourcing cache receives a data requestfrom the requesting cache, the potential sourcing cache supplies the requested data to the requesting cache, if the corresponding snoop responses indicate that the requested data is not found in the snoop response required caches. Referring to FIG. 4, we show an exemplary SMP system, wherein a unidirectional ring is employed to deliver a cache request and its associated snoop responses, and a data network is employed to transfer data between caches and memory. Given arequesting cache, snoop response required caches for a potential sourcing cache include the caches between the requesting cache and the potential sourcing caches along the unidirectional ring. When a cache miss occurs, the requesting cache sends a cacherequest and an initial partially combined snoop response ("PCSR") with a null value to the subsequent cache in the ring. When a cache receives the cache request and its associated PCSR, it initiates a cache intervention to supply the requested data tothe requesting cache, if the data is found in the cache and the PCSR indicates that the data has not been supplied by any previous cache. If the data is not found in the cache, the cache combines the PCSR with its own snoop response to generate a newPCSR, which is then sent to the subsequent cache in the ring. In the example above, requested data of a cache miss may be supplied with lowest cache intervention cost, depending on characteristics of the data network. If the data network is a unidirectional ring in the opposite direction with respect tothe unidirectional ring for cache requests and snoop responses, it can be shown that a cache intervention is initiated from a cache that is closest to the requesting cache. This is because when a cache receives a data request and its associated PCSR,the received PCSR includes snoop responses from all caches that can supply data to the requesting cache with a less number of message-passing hops in the data network. With location-aware cache interventions based on (full or partial) snoop responses, it is worth noting that, for a given cache request, without snoop responses from other caches, a particular cache can determine according to its own cache statewhether it should supply the data to the requesting cache, provided that the cache has the lowest cache intervention cost of any cache with respect to the requesting cache. This observation motivates a simple optimization based on preferred interveningcaches that can be used in SMP systems to improve cache intervention performance. In an SMP system, each cache can be assigned a preferred intervening cache, which is generally a peer cache that can supply data with the lowest cache intervention cost. As the name suggests, a preferred intervening cache is preferred to supplyrequested data if possible. The preferred intervening cache for a requesting cache is usually a neighboring cache in the data network used for cache-to-cache transfers. When a cache miss occurs, the requesting cache sends a data request to its peercaches including the preferred intervening cache. When the preferred intervening cache receives the data request, the preferred intervening cache can supply the requested data immediately if the data is found in the cache. In contrast, when a cacheother than the preferred intervening cache receives the data request, the cache cannot supply the requested data before the cache is notified that the data is not found in the preferred intervening cache. It can be shown that the optimization based on preferred intervening caches can also be incorporated into conventional cache coherence schemes. For example, consider a cache coherence protocol that allows a fixed cache to supply requested dataof a shared cache line at any given time, regardless of the location of the requesting cache. If data of a memory address is shared in more than one cache, a particular cache with the shared data is selected as the owner cache which is responsible forsourcing the data to another cache if necessary. With the preferred intervening cache optimization, when the owner cache receives a cache request from a requesting cache, the owner cache supplies the data only if the snoop response from thecorresponding preferred intervening cache shows that the data cannot be supplied from the preferred intervening cache. The idea of using preferred intervening caches can be generalized to allow multiple preferred intervening caches with different priorities. Each cache can have a first preferred intervening cache, a second preferred intervening cache, and so on. Given a requesting cache, different preferred intervening caches with different priorities generally correspond to different cache intervention costs. For example, when the second preferred intervening cache receives a data request, the second preferredintervening cache initiates a cache intervention only if the data is found in the second preferred intervening cache but not in the first preferred intervening cache. The particular embodiments disclosed above are illustrative only, as the invention may be modified and practiced in different but equivalent manners apparent to those skilled in the art having the benefit of the teachings herein. Furthermore, nolimitations are intended to the details of design herein shown, other than as described in the claims below. It is therefore evident that the particular embodiments disclosed above may be altered or modified and all such variations are considered withinthe scope and spirit of the invention. Accordingly, the protection sought herein is as set forth in the claims below. |
