Efficient region coherence protocol for clustered shared-memory multiprocessor systems

A system and method of a region coherence protocol for use in Region Coherence Arrays (RCAs) deployed in clustered shared-memory multiprocessor systems which optimize cache-to-cache transfers by allowing broadcast memory requests to be provided to only a portion of a clustered shared-memory multiprocessor system. Interconnect hierarchy levels can be devised for logical groups of processors, processors on the same chip, processors on chips aggregated into a multichip module, multichip modules on the same printed circuit board, and for processors on other printed circuit boards or in other cabinets. The present region coherence protocol includes, for example, one bit per level of interconnect hierarchy, such that the one bit has a value of “1” to indicate that there may be processors caching copies of lines from the region at that level of the interconnect hierarchy, and the one bit has a value of “0” to indicate that there are no cached copies of any lines from the region at that respective level of the interconnect hierarchy.

BACKGROUND OF THE INVENTION

1. Technical Field

The present invention relates in general to the field of computers, and in particular to clustered shared-memory multiprocessors. More particularly, the present invention relates to an efficient region coherence protocol for clustered shared-memory multiprocessor systems.

2. Description of the Related Art

To reduce global bandwidth requirements within a computer system, many modern shared-memory multiprocessor systems are clustered. The processors are divided into groups called symmetric multiprocessing nodes (SMP nodes), such that processors within the same SMP node may share a physical cabinet, a circuit board, a multi-chip module, or a chip, thereby enabling low-latency, high-bandwidth communication between processors in the same SMP node. Two-level cache coherence protocols exploit this clustering configuration to conserve global bandwidth by first broadcasting memory requests for a line of data from a processor to the local SMP node, and only sending memory requests to other SMP nodes if necessary (e.g., if it is determined from the responses to the first broadcast that the requested line is not cached on the local SMP node). While this type of two-level cache coherence protocol reduces the computer system global bandwidth requirements, memory requests that must eventually be broadcast to other SMP nodes are delayed by the checking of the local SMP node first for the requested line, causing the computer system to consume more SMP node bandwidth and power. It is important for performance, scalability, and power consumption to first send memory requests to the appropriate portion of the shared-memory computer system where the cached data is most likely to be found.

There have been prior proposals for improved request routing in two-level cache coherence protocol systems in clustered multiprocessor systems, such as, for example Power6 systems by IBM Corporation. For example, the In, and Ig “pseudo invalid” states in the coherence protocols of such systems are used to predict whether a requested line of data is cached on the local SMP node, or on other SMP nodes. However, there are several limitations to using these states.

First, a line of data must be brought into a processor cache and subsequently must be taken away by intervention to reach one of these states. These states only optimize subsequent requests by the processor to reacquire the cache line of data (temporal locality) and do not optimize the initial access to the data since a line request is sent to all processors. Second, they do not exploit spatial locality beyond the cache line, so a processor must collect and store information for each such line of the cache. Third, these states take up space in the processor's cache hierarchy, displacing valid data. Fourth, these states only help if they can remain in the cache hierarchy long enough, before being replaced by valid data, for the data to be accessed again. Finally, additional states must be added to handle additional levels of hierarchy in the system interconnect (for example where a separate hierarchical level exists for processors on a single chip, on a module, on a board, on an SMP node, or on a cabinet), thereby increasing cache coherence protocol complexity.

Use of these “pseudo invalid” states does not exploit spatial locality beyond the line of data requested, and does not define a region coherence protocol.

There have been prior proposals for Region Coherence Arrays (RCAs) which optimize global bandwidth by keeping track of regions from which the processor is caching lines, and whether other processors are caching lines from those regions. However, these proposals are for multiprocessor systems that are not clustered—that is, there is a single, flat interconnect of processors. As such, these proposals for RCAs are suboptimal for clustered multiprocessor systems having hierarchical interconnects, since they cannot exploit cases where data is shared, for example, by only processors on the same SMP node. Furthermore, these proposals include RCAs which invalidated regions from which the processor is no longer caching lines in response to external requests. This dynamic self-invalidation made it easier for other processors to obtain exclusive access to regions, however the processor receiving the request threw away useful information that could have been used to optimize subsequent requests.

SUMMARY OF THE INVENTION

Disclosed is a system and method of a multilevel region coherence protocol for use in Region Coherence Arrays (RCAs) deployed in clustered shared-memory multiprocessor systems which optimize cache-to-cache transfers (interventions) by allowing broadcast memory requests to be provided to only a portion of a clustered shared-memory multiprocessor system and not requiring that such requests are provided to all processors in the system. The present region coherence protocol is simple to implement and easily scales up as levels of interconnect hierarchy are added to computer system designs. Interconnect hierarchy levels can be devised for logical groups of processors, processors on the same chip, processors on chips aggregated into a multichip module, multichip modules on the same printed circuit board, and for processors on other printed circuit boards, and processors in other cabinets. The present region coherence protocol includes one bit per level of interconnect hierarchy, such that the one bit has a set value of, for example, “1”, to indicate that there may be processors caching copies of lines from the region at that level of the interconnect hierarchy, and the one bit has a non-set value of, for example, “0”, to indicate that there are no cached copies of any lines from the region which includes the requested line at that level of the interconnect hierarchy.

With the present region coherence protocol, Coarse-Grain Coherence Tracking (CGCT) utilizing RCAs can be extended to optimize bandwidth, power, and latency in clustered shared-memory multiprocessor systems by identifying to which level(s) of the interconnect hierarchy to send memory requests, and to send memory requests only to those levels, thereby increasing the efficiency of the protocol. Other levels of the interconnect hierarchy can be skipped, reducing request traffic and power-consumption at those levels, and avoiding the latency of checking those levels for the requested data. The present region coherence protocol is simple and scalable, with state bits taken directly from the snoop response for the region, and requires only one state bit for each level of the interconnect hierarchy. In addition, the present region coherence protocol implements an improved form of dynamic self-invalidation that does not throw away the external status of a region in the process of giving another processor exclusive access to the region, thereby exploiting greater temporal locality. The external status of a region indicates whether processors at a given level of the interconnect hierarchy external to the requesting processor are caching lines from the region.

Additionally, the present region coherence protocol does not encode information about lines cached by the processor, but only encodes the external status of the region. Therefore, on external requests (i.e., requests from another processor for a line of data) the RCA can give another processor exclusive access to the line of data without changing its region coherence state, provided the processor is not caching any lines from the region. However, if the external request is from a level of the interconnect hierarchy that has not previously cached lines from the region, a corresponding bit must be set in the region coherence state to indicate that lines from the region, which includes the requested line, are now being cached by the hierarchical level to which the processor that originated the external request belongs.

DETAILED DESCRIPTION

Reference will now be made in detail to the embodiments of the present invention, examples of which are illustrated in the accompanying drawings, wherein like reference numerals refer to the like elements throughout. The embodiments are described below in order to explain the present invention by referring to the figures. The specific reference numerals assigned to the elements are provided solely to aid in the description and not meant to imply any limitations (structural or functional) on the present invention.

The present invention provides a system and method of a multilevel region coherence protocol for use in Region Coherence Arrays (RCAs) deployed in clustered shared-memory multiprocessor systems which optimize cache-to-cache transfers (interventions) by allowing broadcast memory requests to be provided to only a portion of a clustered shared-memory multiprocessor system and not requiring that such requests are provided to all processors in the system. The present region coherence protocol is simple to implement and easily scales up as levels of interconnect hierarchy are added to computer system designs. Interconnect hierarchy levels can be devised for logical groups of processors, processors on the same chip, processors on chips aggregated into a multichip module, multichip modules on the same printed circuit board processors on other printed circuit boards, and processors in other cabinets. The present region coherence protocol includes one bit per level of interconnect hierarchy, such that the one bit has a set value of, for example, “1”, to indicate that there may be processors caching copies of lines from the region at that level of the interconnect hierarchy, and the bit has a non-set value of, for example, “0”, to indicate that there are no cached copies of any lines from the region which includes the requested line at that level of the interconnect hierarchy.

Referring toFIG. 1, a high level block diagram of an embodiment of a plurality of clustered processors100x. . .100x+nin a multiprocessor shared-memory computer system5, according to an embodiment of the present invention. Each of the plurality of processors100x. . .100x+ncommunicates with each other, and with the system memory130, via a system bus110. Each of the processors100x. . .100x+ncommunicates with the system bus110via a respective bus120. The system memory130communicates with the system bus110via a bus115. The cluster of processors100x. . .100x+nforms a Symmetric Multiprocessor (SMP) node10. The system5includes a plurality of such SMP nodes10, each of which is connected to each other and to the system memory130.

Referring toFIG. 2, there is depicted an embodiment of a processor200which represents each of the plurality of processors100x. . .100x+nof the shared-memory computer system5of the present invention. Processor200includes a processor core270, a memory cache290, and a Region Coherence Array (RCA)280associated with the cache290.

In general, caches in such a system vary in size. For example, the cache290may include a plurality of lines of data which are each 64 bytes in size, where each line is from a region of a system memory130electronically connected to the processor200, and may range in size from 128 bytes (2 lines of data) to 4 k bytes (1 physical page of the system memory130, or 64 lines of data). In general, each cache290includes status of each line stored in the cache290, and each RCA280includes status of a region of the system memory130which includes a plurality of lines of data.

The RCA280is an array of stored meta-data entries located in the cache hierarchy of processor200, and is typically disposed near the lowest-level cache (for example, the L3 cache) of the processor200and is typically accessed in parallel with the lowest-level cache on processor requests and external snoops (described below in greater detail). The RCA280provides the status of a region and is tagged with an address of a defined region of the system memory130. The RCA280is used to keep track of the status of the cache lines of each hierarchical level of cache associated with the processor core270by determining whether any lines within a region around a requested line have been previously cached, and if so the location of where those lines have been cached within the system5. The cache290may be, for example, a lowest-level cache of the processor200in a multi-level hierarchical cache system design, where the RCA280would, in such example, include entries to indicate the status of all the lines in the L3 cache290.

As described above, the shared-memory computer system which includes processor200may be designed such that cache290is a higher-level cache (for example, an L1 cache) and all lower-level caches (for example, L2 and L3 caches, not illustrated) are not disposed within the processor200, but are disposed elsewhere in the system, but are associated with the processor200. In such a case, the RCA280includes a set-associative array of meta-data entries corresponding only to lines of data associated with the L1 cache290, and the all lower-level caches (not illustrated) which are associated with and disposed external to the processor200include an associated respective RCA which includes entries corresponding only to lines of data associated with the respective external lower-level L2 and L3 caches.

Referring toFIG. 2A, each RCA280includes a plurality of entries210each of which may include a valid bit220, one or more parity bits (or ECC bits)230, a region address tag240, a plurality of region coherence state bits250, a plurality of line-count bits260(to keep track of how many lines from the region are cached by the processor200), and a non-zero (NZ) bit265. Each RCA entry210represents a large, aligned region of the system memory130that is a power-of-two multiple of the cache line size, and is no larger than a physical page of the system memory130(for example, no larger than a minimum physical page size supported by the computer system5). The region coherence state bits250summarize the coherence status of the lines in the region, more specifically, the coherence status of lines in the region in the caches of other processors. The line-count bits260summarize whether the processor with which the RCA is associated is caching lines from the region, and are used when responding to other processors' requests to signal that lines are cached from the region around the requested line. The region coherence state bits250are used in conjunction with the line-count bits260to implement a region coherence protocol to more efficiently maintain cache coherence of the system5.

The NZ bit265, if used, is a bit to indicate a non-zero value of the line-count or presence bits260when the NZ bit265has a value of “0” and a zero value when it has a value of “1”. The NZ bit265may be set whenever the line count is incremented or a presence bit is set. The NZ bit265may be cleared (set to a value of “0”) whenever the line count is decremented to zero, or when the last presence bit is cleared. Use of the NZ bit265by the system5allows for faster access for external requests, since only the NZ bit265needs to be read by an external request without reading the value of the entire line count or presence bits260and then comparing that read value to zero to determine whether the line-count or presence bits260have a non-zero value.

In another embodiment, each entry210may also contain one or more bits to implement a least-recently-used (LRU) replacement policy for set-associative and fully-associative arrays. In a further embodiment, each entry210may include one or more presence bits instead of the line-count bits260(for example, one bit per cache line indicating whether the line is cached by the processor200).

Entries210of the RCA280are allocated when lines from a region of memory around the requested line and are brought into the cache hierarchy of the processor200. On broadcast snoops, requests not only check the caches290of other processors200for the requested line, but also check the RCAs280of the other processors200for the region surrounding the requested line. Each processor200responds with both the line status and the region status (whether the processor200is caching lines from the region), and the line response and region status of the processor200are combined with that of other processors200to form a combined snoop response (a line snoop response and region snoop response). Based on the region snoop responses, the region coherence state bits250are updated to reflect whether other processors200are caching lines from the same region, and this information is used to optimize the routing of future processor requests for lines in the region.

The region coherence protocol of the present invention utilizes interconnect hierarchy levels which can be devised for logical groups of processors200, for example, for processors200on the same chip (not illustrated), or aggregated into the same module (not illustrated), or on the same SMP node10, or on the same board (not illustrated), or in the same cabinet, etc., where, for example, the chip level may be at the lowest hierarchical level and the cabinet level may be the highest hierarchical level. Whether there are two or more levels of interconnect hierarchy in the system5, the operation of the region coherence protocol is essentially the same. The bits of the region coherence state bits250would be encoded to indicate the level at which the processor200which has cached the requested line of data is disposed.

The present region coherence protocol includes one bit per level of interconnect hierarchy in the system5, where a set value of “1” for the one bit indicates that there may be processors200caching copies of lines from the region at that level, and a non-set value of “0” for the bit indicates that there are no processors200caching copies of any lines from the region at that level. If a bit is set among the region coherence state bits250, this indicates that at some time in the past, a processor200at that level cached lines from the region which includes the requested line. If the bit is not set among the region coherence state bits250, this indicates that no processors200at that level within the system5currently cache any lines of the region which includes the requested line. The value of the bit(s) of the region coherence state bits250is described herein by way of example, and depends on a choice of design of the system5.

The region coherence state bits250are updated with bits from the region snoop response, which also include one bit per level of the interconnect hierarchy, and are set if cached copies of lines from the region are detected at that level via the RCA280of another processor200. On external requests, if the requested region is present and the line-count has a nonzero value (or a presence bit is set), the processor200sets the bit in the region snoop response corresponding to the lowest level of the interconnect hierarchy that the processor200shares with the requesting processor200. If a global snoop is performed, the region coherence state bits250of the RCA280of the requesting processor200are set to the value of the region snoop response bits. If only the local SMP node10is snooped, the region coherence state bits250for that respective level of the interconnect hierarchy and for lower levels are set to be equal to the value of the level-identifying bits that is returned as the region snoop response. Thus, the region coherence state bits250for higher levels of the hierarchy are unchanged if a broadcast snoop did not get sent to processors200at those higher levels.

The region coherence state bits250, which may be two or more bits, are used to determine where to route subsequent processor requests for lines of the same region. If no region coherence state bits250are set, meaning that no processor200in the system5has the requested line, then no broadcast snoop is required and the request need only obtain data from the system memory130. If one bit of the region coherence state bits250is set, the request need only snoop the corresponding level of the interconnect hierarchy. If multiple bits of the region coherence state bits250are set, the request may need to go to one or more of the corresponding levels to find cached copies of the requested line. The manner in which the request is routed is a system design policy decision.

For example, in a two-level system5which includes multiple SMP nodes10, the system interconnect is structured to allow faster access to processors200on the same SMP node10than for other SMP nodes10. The region coherence bits250of the region protocol would contain two bits. If the first bit of the region coherence bits250of a first processor200is set to a value of “1”, this would indicate that lines from the region of a requested line may exist in a cache290of other processors200of the same SMP node10as the first processor200. If the first bit of the region coherence bits250of a first processor200is set to a value of “0”, this would indicate that no lines from the region of a requested line exist in a cache290of other processors200of the same SMP node10as the first processor200. Similarly, if the second bit of the region coherence bits250of a first processor200is set to a value of “1”, this would indicate that lines from the region of a requested line may exist in a cache290of other processors200of other SMP nodes10than the SMP node10of the first processor200. If the second bit of the region coherence bits250of a first processor200is set to a value of “0”, this would indicate that no lines from the region of a requested line exist in a cache290of other processors200of SMP nodes10of other SMP nodes10than the SMP node10of the first processor200.

The state of the region coherence bits250are independent from each other such that a state of one bit does not imply a state of the other bit. Also, there is no invalid state which is a combination of these bits. In this example, the state “11’ of the region coherence bits250indicates that the requested line may be cached by processors200on the same SMP node10as the first processor200, while the state “10” indicates that no processor200on the same SMP node10as the first processor200is caching the requested line (but that processors200on other SMP nodes10may be.)

For cases where a snoop is not needed at a level of the interconnect hierarchy for coherence, but the physical system memory130resides on a memory controller (not illustrated) at that level, a “silent snoop” may be sent. A silent snoop is a special, non-speculative request that other processors200ignore. Upon receiving a silent snoop request, the memory controller accesses DRAM (not illustrated) and sends the data back to the requesting processor200without waiting for a combined snoop response. Silent snoop requests are ignored by other processors200, and therefore silent snoops have no snoop response.

Multiple policies may be used in cases where multiple region coherence state bits250are set. To minimize bandwidth requirements at the upper levels of the interconnect hierarchy, requests can be pumped from the lowest level of the interconnect hierarchy for which the corresponding region coherence state bit250is set, to the highest level, until a satisfying snoop response is received, indicating that it has been determined the location of where the processor200can get the requested line of data. To eliminate double-pumps (i.e., requests that iteratively snoop levels of the interconnect hierarchy), requests can be sent first to the highest level for which the corresponding region coherence state bit250is set. In another embodiment, memory read requests could be pumped to lower levels of the interconnect hierarchy to attempt to find a source copy of the line of data, and memory write requests could be pumped to the highest level right away to quickly invalidate cached copies of the requested line. In a further embodiment, memory read requests can be sent to the highest level of the interconnect hierarchy right away to minimize latency, while less latency-critical writes are pumped to conserve global bandwidth of the system5.

TABLE 1Other NodesSMP NodeRegion Coherence State Definition00Region not cached elsewhere01Region cached by processors on same SMPnode only10Region cached by processors on other nodesonly, not by processors on the same SMPnode.11Region cached by processors on the SMPnode and other SMP nodes

As shown above in Table 1, an example is depicted of an RCA280for a clustered multiprocessor system5having a two-level interconnect hierarchy. Table 1 depicts an example of the present region coherence protocol embodied as a two-bit region coherence protocol for a clustered shared-memory multiprocessor system5having two levels of interconnect hierarchy (for example, a first level for the local SMP node10, and a second level for all SMP nodes10of the system5). A processor200may send a memory request to either the processors200on the same SMP node10, or to all the SMP nodes10in the system5.

TABLE 2OtherSMPNodesNodeChipRegion Coherence State Definition000Region not cached by other processors001Region cached by other processors on the samechip only010Region cached by other processors on other chipson the same SMP node only011Region cached by other processors on the samechip & other processors in the same SMP nodeonly100Region cached by processors on other SMP nodesonly101Region cached by other processors on the samechip & processors on other SMP nodes only. Notcached by processors on other chips in the sameSMP node.110Region cached by processors on other chips onthe same SMP node & processors on other SMPnodes only111Region cached by other processors on the samechip, other chips on the same SMP node, & otherSMP nodes

As shown above in Table 2, an example is depicted of an RCA280for a clustered multiprocessor system5having a three-level interconnect hierarchy (i.e., a scheme regarding another embodiment of an implementation of the present region coherence protocol) such as, for example, a chip (not illustrated) which includes the processor200, the local SMP node10, and other SMP nodes10.

For the embodiment of Table 1 and/or Table 2, there are one or more bits (in this example, one bit) of the region coherence state bits250for each level to indicate whether a processor200may be caching lines from the region at that respective level. If no bits are set (e.g., the first case, where each of the region coherence state bits250has a zero value), the request does not need to be broadcast to any level of the hierarchy, and the request may simply be sent to the system memory130(i.e., as a silent snoop). If one bit is set, whether for the chip, the SMP node10, or the other SMP nodes10, then only a broadcast to that level of the interconnect hierarchy is needed to obtain the line coherently. If multiple bits of the region coherence state bits250are set, it is a matter of policy of the system5regarding how the system5routes the memory request, where the system5does not waste time and bandwidth snooping levels of the interconnect hierarchy where no cached copies of the requested line are known to exist.

FIG. 3depicts a state diagram300illustrating how the present region coherence protocol may be implemented to operate for the system5having the two-level interconnect hierarchy, as depicted in Table 1. The embodiment ofFIG. 3is for illustrative purposes only and may have other configurations. A state machine implementing this state diagram300might not need to be implemented, for the region coherence state can be updated by simply overwriting one or more of the of the region coherence state bits250. For each state transition of the state diagram300ofFIG. 3there is depicted a request that triggered it, and if it is request of a processor200, then the region snoop response is also shown.

The two region coherence state bits250of this embodiment are conservatively initialized to have a value of “11” on allocation, to indicate that cached copies of lines in the region could be found anywhere in the system5. The left-hand bit of the region coherence state bits250indicates whether there are cached copies of lines on other SMP nodes10, and the right-hand bit indicates whether there are cached copies of lines on the same SMP node10. If the left-hand bit is set to a value of “1”, a global snoop may be required to obtain a copy of the data. In this simple example, this is the action taken, though the SMP node10can be pumped first. If the right-hand bit is set to a value of “1”, there may be cached copies of lines in a cache on the same SMP node10, and a node snoop may save global bandwidth of the system5. If neither bit is set, a silent snoop is sent to the system memory130.

In this embodiment, a global snoop is performed on the first request310for a line in the region. Doing so allows the region coherence state to be updated to reflect the current state of the system5, and avoids a double-pump on the first request to a line in the region. Depending on the region snoop response, the region coherence state may be set to any of the four states (i.e., the “00”, “01”, “10”, and “11” states). To simplify an implementation, the region coherence state bits250may be overwritten with the region snoop response bits from a global snoop. If there is an external request for a line in the region, the bit corresponding to the location of the requesting processor200in the system5may be set, which downgrades the region. Subsequent snoops for requests made by the processor200also update the state with their responses. Global snoops obtain information from all processors200and update all the region coherence state bits250by, for example, overwriting them with bits from the global snoop response. SMP node snoops only obtain information from other processors200on the same SMP node10, and only update the right-hand bits pertaining to the SMP node10and lower levels of the interconnect hierarchy. The “X” in the region snoop response of node snoops represents a “don't care” condition, indicating that X=0, or X=1. Because coherence status was not collected for the levels of the interconnect hierarchy to which these bits pertain, they are not used to update the region coherence state, and so their value is a “don't care” condition.

Referring toFIG. 4, there is illustrated a high level logical flowchart of an embodiment of a region coherence protocol operation400having an external request from a processor of the same SMP node10(for an embodiment of a two-level interconnect hierarchy), according to the present invention. Referring toFIG. 5, there is illustrated a high level logical flowchart of an embodiment of a region coherence protocol operation500having an external request from a processor of another SMP node10(for an embodiment of a two-level interconnect hierarchy), according to the present invention. ForFIGS. 4 and 5, while the process steps are described and illustrated in a particular sequence, use of a specific sequence of steps is not meant to imply any limitations on the invention. Changes may be made with regards to the sequence of steps without departing from the spirit or scope of the present invention. Use of a particular sequence is therefore, not to be taken in a limiting sense, and the scope of the present invention is defined only by the appended claims.

For clarity,FIGS. 4 and 5illustrate actions taken on external snoop requests (from a processor200of the same SMP node10, and from a processor200of another SMP node10, respectively) to generate information regarding where a requested line of data can be found. Note also fromFIGS. 4 and 5that the present region coherence protocol also implements an improved form of dynamic self-invalidation, described above, that does not throw away the external status of a region in the process of giving another processor200exclusive access to the region. The processor200indicates that it has no lines cached even in cases where the region which includes the requested line is indicated in the RCA280, provided the line-count value is zero or all the presence bits have a zero value. Thus, the region is not actually invalidated.

Referring toFIG. 4, a region coherence protocol operation400is depicted having an external request for a line at operation A from a processor of the same SMP node10. For external snoop requests from the same SMP node10, the processor200responds at operation405that it is caching lines from the region of the requested line when the region is indicated in the RCA280of the processor200by an examination of the region coherence state bits250of the RCA280at operation405, and the line-count value (or presence bits value) is equal to a non-zero value as determined at operation420. If it is determined at operation405that the processor200is not caching lines from the region of the requested line, the operation400terminates at operation430. If the region is not indicated in the RCA280at operation405, or if the region is indicated in the RCA280at operation405but there is an associated zero line-count value (or zero value presence bits) determined at operation420, the operation400terminates at operation430and processor200responds that it is not caching lines from the region. At operation410, it is determined whether the region coherence state bits250of the RCA280are set to indicate that lines of the region are being cached in the SMP node10to which the requesting processor200belongs. If not, the region coherence state bits250are set at operation415to indicate the fact.

Region coherence state bits250are not used in the present region coherence protocol to encode information about lines cached by the processor200, since this information is indicated by the line-count bits260. Instead, the region coherence protocol only encodes the region coherence state bits250of the RCA280at operation415to indicate the external status of a region for the benefit of the processor200by indicating whether or not any processor200at a given level of the interconnect hierarchy (in this example, the same SMP node10) is caching lines from the region. Therefore, a region snoop response is based entirely on the value of the line-count bits (or presence bits)260of the RCA280. If there is a valid entry to indicate at operation405that the region is indicated in the RCA280, this indicates that the processor200is caching lines from the region if the line-count bits260indicate at operation420a non-zero value (or the presence bits indicate a non-zero value), and not otherwise. This information is communicated to the requesting processor200via the region snoop response, leaving the region coherence state bits250unchanged. If there is no valid entry at operation405to indicate the region in the RCA280, this indicates that the processor200is not caching any lines from the region.

Referring toFIG. 5, a region coherence protocol operation500is depicted having an external request for a line at operation A from a processor of another SMP node10than the processor200. For external snoop requests from the same SMP node10, the processor200responds at operation505that it is caching lines from the region of the requested line when the region is indicated in the RCA280of the processor200by an examination of the region coherence state bits250of the RCA280at operation505, and the line-count value (or presence bits value) is equal to a non-zero value as determined at operation520. If it is determined at operation505that the processor200is not caching lines from the region of the requested line, the operation500terminates at operation530. If the region is not indicated in the RCA280at operation505, or if the region is indicated in the RCA280at operation505but there is an associated zero line-count value (or zero value presence bits) determined at operation520, the operation500terminates at operation530and processor200responds that it is not caching lines from the region. At operation510, it is determined whether the region coherence state bits250of the RCA280are set to indicate that lines of the region are being cached in the SMP node10to which the requesting processor200belongs. If not, the region coherence state bits250are set at operation515to indicate the fact.

Region coherence state bits250are not used in the present region coherence protocol to encode information about lines cached by the processor200, since this information is indicated by the line-count bits260. Instead, the region coherence protocol only encodes the region coherence state bits250of the RCA280at operation515to indicate the external status of a region for the benefit of the processor200by indicating whether or not any processor200at a given level of the interconnect hierarchy (in this example, another SMP node10) is caching lines from the region. Therefore, a region snoop response is based entirely on the value of the line-count bits (or presence bits)260of the RCA280. If there is a valid entry to indicate at operation505that the region is indicated in the RCA280, this indicates that the processor200is caching lines from the region if the line-count bits260indicate at operation520a non-zero value (or the presence bits indicate a non-zero value), and not otherwise. This information is communicated to the requesting processor200via the region snoop response, leaving the region coherence state bits250unchanged. If there is no valid entry at operation505to indicate the region in the RCA280, this indicates that the processor200is not caching any lines from the region.

In another embodiment, the proposed region protocol can be extended with a form of cooperative state prefetching. If a processor200of a SMP node10has an associated RCA280state that indicates that no processors200outside the same SMP node10are caching lines from the region, it can supply this information to other processors200of the same SMP node10in response to requests sent to the SMP node10. When a processor200on the same SMP node10performs a node pump, it can determine whether other processors200on the SMP node10are caching lines from the requested region and whether other processors200on the same SMP node10have information that processors200outside the SMP node10are caching lines from the requested region. The processor200can use this information to update the state of its RCA280, and avoid a subsequent pump to other SMP nodes10in the system5.

This optimization can be implemented with an additional bit in the combined snoop response for each level of the interconnect hierarchy except the first/lowest level. The bit for each upper level of the interconnect hierarchy is asserted during broadcast snoops if a processor200at a lower level has an RCA280state that indicates there are no processors200caching lines from the region at the upper level. These extra bits can be considered “not cached” bits, since they indicate if a level of the interconnect hierarchy is not caching lines from the region. The “not cached” bits may be effectively a complemented bitwise-AND (NAND) of the upper bits of the RCA280state. For example, during a node snoop a processor200may assert the “not-cached” bit for the level above if the corresponding bit in its RCA280state is clear, or zero.

The processor200receiving the snoop provides the requestor with information about the level above, cooperatively avoiding unnecessary broadcast snoop. If the “not-cached” bit is set in the snoop response for a request, the corresponding bit in the RCA280state for the requestor can be cleared, and subsequent snoop to the corresponding level of the interconnect hierarchy can be avoided. If the snoop response is made available to other processors200of the same SMP node10, they may also clear the corresponding bit in their respective associated RCA280in anticipation of future requests.

It is understood that the use herein of specific names are for example only and not meant to imply any limitations on the invention. The invention may thus be implemented with different nomenclature/terminology and associated functionality utilized to describe the above devices/utility, etc., without limitation. While the present invention has been particularly shown and described with reference to a preferred embodiment, it will be understood by those skilled in the art that various changes in form and detail may be made therein without departing from the spirit and scope of the invention. Furthermore, as utilized in the specification and the appended claims, the term “computer” or “system” or “computer system” or “computing device” includes any data processing system including, but not limited to, personal computers, servers, workstations, network computers, main frame computers, routers, switches, personal digital assistants (PDAs), telephones, and any other system capable of processing, transmitting, receiving, capturing, and/or storing data.

It should be understood that at least some aspects and utilities of the present invention may alternatively be implemented in a computer-storage medium that contains a program product. That is, the present invention can also be embodied as programs defining functions in the present invention as computer-readable codes on a computer-readable medium. The computer-storage medium may be a computer-readable medium, which can include a computer-readable recording medium and/or a computer-readable transmission medium, and/or a computer-readable/writeable recording medium. The computer-readable recording medium is any data storage device that can store data which can be thereafter read by a computer system. Examples of a computer-readable recording medium include read-only memory (ROM), and examples of a computer-readable/writeable recording medium include random-access memory (RAM), CD-ROMs, magnetic tapes, floppy disks, hard disk drives, memory stick devices, and optical data storage devices. The computer-readable recording medium can also be distributed over network coupled computer systems so that the computer-readable code is stored and executed in a distributed fashion. The computer-readable transmission medium can transmit data via a wired or wireless configuration (e.g., wired or wireless data transmission through the Internet). Also, functional programs, codes, and code segments to accomplish the present invention can be easily construed by programmers skilled in the art to which the present invention pertains. Further, it is understood that the present invention may be implemented as a system having means in the form of hardware, software, or a combination of software and hardware as described herein, or their equivalents.