Cache memory, processing unit, data processing system and method for assuming a selected invalid coherency state based upon a request source

At a first cache memory affiliated with a first processor core, an exclusive memory access operation is received via an interconnect fabric coupling the first cache memory to second and third cache memories respectively affiliated with second and third processor cores. The exclusive memory access operation specifies a target address. In response to receipt of the exclusive memory access operation, the first cache memory detects presence or absence of a source indication indicating that the exclusive memory access operation originated from the second cache memory to which the first cache memory is coupled by a private communication network to which the third cache memory is not coupled. In response to detecting presence of the source indication, a coherency state field of the first cache memory that is associated with the target address is updated to a first data-invalid state. In response to detecting absence of the source indication, the coherency state field of the first cache memory is updated to a different second data-invalid state.

CROSS-REFERENCE TO RELATED APPLICATIONS

The present invention is related to the following applications, which are incorporated herein by reference in their entireties:1. U.S. patent application Ser. No. 11/055,305;2. U.S. patent application Ser. No. 11/056,673; and3. U.S. patent application Ser. No. 11/095,734.

BACKGROUND OF THE INVENTION

1. Technical Field

The present invention relates in general to data processing and, in particular, to improved data processing system and cache memories for data processing systems. Still more particularly, the present invention relates to an improved coherency protocol in a cache memory of a data processing system.

2. Description of the Related Art

A conventional symmetric multiprocessor (SMP) computer system, such as a server computer system, includes multiple processing units all coupled to a system interconnect, which typically comprises one or more address, data and control buses. Coupled to the system interconnect is a system memory, which represents the lowest level of volatile memory in the multiprocessor computer system and which generally is accessible for read and write access by all processing units. In order to reduce access latency to instructions and data residing in the system memory, each processing unit is typically further supported by a respective multi-level cache hierarchy, the lower level(s) of which may be shared by one or more processor cores.

Because multiple processor cores may request write access to a same cache line of data and because modified cache lines are not immediately synchronized with system memory, the cache hierarchies of multiprocessor computer systems typically implement a cache coherency protocol to ensure at least a minimum level of coherence among the various processor core's “views” of the contents of system memory. In particular, cache coherency requires, at a minimum, that after a processing unit accesses a copy of a memory block and subsequently accesses an updated copy of the memory block, the processing unit cannot again access the old copy of the memory block.

A cache coherency protocol typically defines a set of cache coherency states stored in a cache directory in association with the cache lines of each cache hierarchy, as well as a set of coherency messages utilized to communicate the cache state information between cache hierarchies. In a typical implementation, the cache state information takes the form of the well-known MESI (Modified, Exclusive, Shared, Invalid) protocol or a variant thereof, and the coherency messages indicate a protocol-defined coherency state transition in the cache directory of the cache at the requestor and/or the recipients of a memory access request.

In conventional multi-processor data processing systems, all levels of cache memory within a cache memory hierarchy are examined to determine their coherency state in response to a memory access request before an operation requesting a memory block is broadcast to other cache hierarchies in the data processing system. In other approaches, such as that disclosed in U.S. patent application Ser. No. 11/095,734, certain cache states are utilized to speculatively omit examination of one or more lower levels of cache memory prior to issuing a request for a memory block on an interconnect fabric. However, the present invention recognizes that such speculation can unnecessarily extend the latency of the memory access request in the subset of cases in which the speculation proves to be incorrect.

SUMMARY OF THE INVENTION

In view of the foregoing, the present invention provides an improved cache memory, processing unit, data processing system, and method of data processing in which a memory block in a cache memory assumes a selected invalid coherency state based upon a request source.

In one embodiment, at a first cache memory affiliated with a first processor core, an exclusive memory access operation is received via an interconnect fabric coupling the first cache memory to second and third cache memories respectively affiliated with second and third processor cores. The exclusive memory access operation specifies a target address. In response to receipt of the exclusive memory access operation, the first cache memory detects presence or absence of a source indication indicating that the exclusive memory access operation originated from the second cache memory to which the first cache memory is coupled by a private communication network to which the third cache memory is not coupled. In response to detecting presence of the source indication, a coherency state field of the first cache memory that is associated with the target address is updated to a first data-invalid state. In response to detecting absence of the source indication, the coherency state field of the first cache memory is updated to a different second data-invalid state.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENT

I. Exemplary Data Processing System

With reference now to the figures and, in particular, with reference toFIG. 1, there is illustrated a high level block diagram of an exemplary embodiment of a cache coherent symmetric multiprocessor (SMP) data processing system in accordance with the present invention. As shown, data processing system100includes multiple processing nodes102a,102bfor processing data and instructions. Processing nodes102a,102bare coupled to a system interconnect110for conveying address, data and control information. System interconnect110maybe implemented, for example, as a bused interconnect, a switched interconnect or a hybrid interconnect.

In the depicted embodiment, each processing node102is realized as a multi-chip module (MCM) containing four processing units104a–104d, each preferably realized as a respective single integrated circuit. The processing units104a–104dwithin each processing node102are coupled for communication by a local interconnect114, which, like system interconnect110, may be implemented with one or more buses and/or switches.

The devices coupled to each local interconnect114include not only processing units104, but also one or more system memories108a–108d. Data and instructions residing in system memories108can generally be accessed and modified by a processor core in any processing unit104in any processing node102of data processing system100. In alternative embodiments of the invention, one or more system memories108can be coupled to system interconnect110rather than a local interconnect114.

Those skilled in the art will appreciate that SMP data processing system100can include many additional unillustrated components, such as interconnect bridges, non-volatile storage, ports for connection to networks or attached devices, etc. Because such additional components are not necessary for an understanding of the present invention, they are not illustrated inFIG. 1or discussed further herein. It should also be understood, however, that the enhancements provided by the present invention are applicable to cache coherent data processing systems of diverse architectures and are in no way limited to the generalized data processing system architecture illustrated inFIG. 1.

Referring now toFIG. 2, there is depicted a more detailed block diagram of an exemplary processing unit104in accordance with the present invention. In the depicted embodiment, each processing unit104includes two processor cores200a,200bfor independently processing instructions and data. Each processor core200includes at least an instruction sequencing unit (ISU) for fetching and ordering instructions for execution and one or more execution units for executing instructions. The instructions executed by the execution unit(s) include instructions that request access to a memory block or cause the generation of a request for access to a memory block.

The operation of each processor core200is supported by a multi-level volatile memory hierarchy having at its lowest level shared system memories108a–108d, and at its upper levels one or more levels of cache memory. In the depicted embodiment, each processing unit104includes an integrated memory controller (IMC)206that controls read and write access to a respective one of the system memories108a–108dwithin its processing node102in response to requests received from processor cores200a–200band operations snooped by a snooper (SNP)222on the local interconnect114. IMC206determines the addresses for which it is responsible by reference to base address register (BAR) logic240.

In the illustrative embodiment, the cache memory hierarchy of each processor core200includes a respective store-through level one (L1) cache226within each processor core200and a respective private level two (L2) cache230. L2 cache230includes an L2 array and directory234and a cache controller comprising a master232and a snooper236. Master232initiates transactions on local interconnect114and system interconnect110and accesses L2 array and directory234in response to memory access (and other) requests received from the associated processor cores200a–200b. Snooper236snoops operations on local interconnect114, provides appropriate responses, and performs any accesses to L2 array and directory234required by the operations.

As shown, private L2 caches230a,230bare coupled for communication by a private communication network270by which each of L2 caches230a,230b, which are otherwise private to their respective cores, can directly intervene read data to the other L2 cache230without any related operation being issued or received on shared local interconnect114. As described in detail in U.S. patent application Ser. No. 11/056,673 referenced above, such direct intervention is preferably performed speculatively (e.g., concurrently with the memory access operation in the requesting L2 cache230) and reduces the likelihood of having to issue a read operation on local interconnect114responsive to a cache miss. To facilitate clarity of description, a private L2 cache230that receives a request for direct intervention from another L2 cache230via a private network270is referred to herein as an “L2.1” cache and this form of direct cache-to-cache intervention via a private communication network270is referred to as an “L2.1 intervention.”

Although each of the illustrated cache hierarchies will be hereafter described as including only L1 and L2 caches, those skilled in the art will appreciate that alternative embodiments may include additional levels (L3, L4, L5 etc.) of on-chip or off-chip in-line or lookaside cache, which may be fully inclusive, partially inclusive, or non-inclusive of the contents the upper levels of cache. For example, the processing unit104may optionally include an L3 cache250including a cache controller252, an L3 cache array260, and an L3 directory254of the contents of L3 cache array260. Although in some embodiments L3 cache array260may be implemented fully on-chip, as shown, in other embodiments L3 cache array260is implemented in memory DIMMs external to processing unit104in order to permit L3 cache array260to have a greater capacity. In various embodiments, L3 cache250may be implemented as inclusive, partially inclusive or non-inclusive of the contents of L2 cache230. Moreover, L3 cache250may be implemented as an in-line or lookaside cache. In the illustrated embodiment, optional L3 cache250is implemented as a “victim” cache that is populated by memory blocks castout or victimized by L2 caches230a,230b. One embodiment of such an arrangement is described in detail, for example, in U.S. patent application Ser. No. 11/055,301, which is assigned to the assignee of the present application and incorporated herein by reference in its entirety.

Each processing unit104further includes an instance of response logic210, which as discussed further below, implements a portion of the distributed coherency signaling mechanism that maintains cache coherency within data processing system100. In addition, each processing unit104includes an instance of forwarding logic212for selectively forwarding communications between its local interconnect114and system interconnect110. Finally, each processing unit104includes an integrated I/O (input/output) controller214supporting the attachment of one or more I/O devices, such as I/O device216. As described further below, I/O controller214may issue operations on local interconnect114and/or system interconnect110in response to requests by I/O device216.

With reference now toFIG. 3, there is illustrated a more detailed block diagram of an exemplary embodiment of L2 array and directory234. As illustrated, L2 array and directory234includes a set associative L2 cache array300and an L2 cache directory302of the contents of L2 cache array300. As in conventional set associative caches, memory locations in system memories108are mapped to particular congruence classes within cache arrays300utilizing predetermined index bits within the system memory (real) addresses. The particular cache lines stored within cache array300are recorded in cache directory302, which contains one directory entry for each cache line in cache array300. As understood by those skilled in the art, each directory entry in cache directory302comprises at least a tag field304, which specifies the particular cache line stored in cache array300utilizing a tag portion of the corresponding real address, a state field306, which indicates the coherency state of the cache line, and a LRU (Least Recently Used) field308indicating a replacement order for the cache line with respect to other cache lines in the same congruence class. L3 directory254may be similarly constructed.

Referring now toFIG. 4, there is depicted a time-space diagram of an exemplary operation on a local or system interconnect110,114of data processing system100ofFIG. 1. The operation begins when a master232of an L2 cache230(or another master, such as an I/O controller214) issues a request402on a local interconnect114and/or system interconnect110. Request402preferably includes a transaction type indicating a type of desired access and a resource identifier (e.g., real address) indicating a resource to be accessed by the request. Common types of requests preferably include those set forth below in Table I.

TABLE IRequestDescriptionREADRequests a copy of the image of a memoryblock for query purposesRWITM (Read-With-Requests a unique copy of the image ofIntent-To-Modify)a memory block with the intent to update(modify) it and requires destruction ofother copies, if anyDCLAIM (Data Claim)Requests authority to promote an existingquery-only copy of memory block to aunique copy with the intent to update(modify) it and requires destruction ofother copies, if anyDCBZ (Data CacheRequests authority to create a new uniqueBlock Zero)copy of a memory block without regard toits present state and subsequently modifyits contents; requires destruction of othercopies, if anyCASTOUTCopies the image of a memory block from ahigher level of memory to a lower levelof memory in preparation for thedestruction of the higher level copyWRITERequests authority to create a new uniquecopy of a memory block without regard toits present state and immediately copy theimage of the memory block from a higherlevel memory to a lower level memory inpreparation for the destruction of thehigher level copyPARTIAL WRITERequests authority to create a new uniquecopy of a partial memory block withoutregard to its present state and immediatelycopy the image of the partial memory blockfrom a higher level memory to a lower levelmemory in preparation for the destruction ofthe higher level copy

Request402is received by the snooper236of L2 caches230, as well as the snoopers222of memory controllers206(FIG. 1). In general, with some exceptions, the snooper236in the same L2 cache230as the master232of request402does not snoop request402(i.e., there is generally no self-snooping) because a request402is transmitted on local interconnect114and/or system interconnect110only if the request402cannot be serviced internally by a processing unit104. Each snooper222,236that receives request402provides a respective partial response406representing the response of at least that snooper to request402. A snooper222within a memory controller206determines the partial response406to provide based, for example, whether the snooper222is responsible for the request address and whether it has resources available to service the request. A snooper236of an L2 cache230may determine its partial response406based on, for example, the availability of its L2 cache directory302, the availability of a snoop logic instance within snooper236to handle the request, and the coherency state associated with the request address in L2 cache directory302.

The partial responses of snoopers222and236are logically combined either in stages or all at once by one or more instances of response logic210to determine a system-wide combined response (CR)410to request402. Subject to the scope restrictions discussed below, response logic210provides combined response410to master232and snoopers222,236via its local interconnect114and/or system interconnect110to indicate the system-wide response (e.g., success, failure, retry, etc.) to request402. If CR410indicates success of request402, CR410may indicate, for example, a data source for a requested memory block, a cache state in which the requested memory block is to be cached by master232, and whether “cleanup” operations invalidating the requested memory block in one or more L2 caches230are required.

In response to receipt of combined response410, one or more of master232and snoopers222,236typically perform one or more operations in order to service request402. These operations may include supplying data to master232, invalidating or otherwise updating the coherency state of data cached in one or more L2 caches230, performing castout operations, writing back data to a system memory108, etc. As discussed further below, if required by request402, a requested or target memory block may be transmitted to or from master232before or after the generation of combined response410by response logic210.

In the following description, partial response of a snooper222,236to a request and the operations performed the snooper in response to the request and/or its combined response will be described with reference to whether that snooper is a Highest Point of Coherency (HPC), a Lowest Point of Coherency (LPC), or neither with respect to the request address specified by the request. An LPC is defined herein as a memory device or I/O device that serves as the repository for a memory block. In the absence of a HPC for the memory block, the LPC holds the true image of the memory block and has authority to grant or deny requests to generate an additional cached copy of the memory block. For a typical request in the data processing system embodiment ofFIGS. 1 and 2, the LPC will be the memory controller206for the system memory108holding the referenced memory block. An HPC is defined herein as a uniquely identified device that caches a true image of the memory block (which may or may not be consistent with the corresponding memory block at the LPC) and has the authority to grant or deny a request to modify the memory block. Descriptively, the HPC may also provide a copy of the memory block to a requestor in response to an operation that does not modify the memory block. Thus, for a typical request in the data processing system embodiment ofFIGS. 1 and 2, the HPC, if any, will be an L2 cache230. Although other indicators may be utilized to designate an HPC for a memory block, a preferred embodiment of the present invention designates the HPC, if any, for a memory block utilizing selected cache coherency state(s) within the L2 cache directory302of an L2 cache230, as described further below with reference to Table II.

Still referring toFIG. 4, the HPC, if any, for a memory block referenced in a request402, or in the absence of an HPC, the LPC of the memory block, preferably has the responsibility of protecting the transfer of ownership of a memory block in response to a request402during a protection window404a. In the exemplary scenario shown inFIG. 4, the snooper236that is the HPC for the memory block specified by the request address of request402protects the transfer of ownership of the requested memory block to master232during a protection window404athat extends from the time that snooper236determines its partial response406until snooper236receives combined response410. During protection window404a, snooper236protects the transfer of ownership by providing partial responses406to other requests specifying the same request address that prevent other masters from obtaining ownership until ownership has been successfully transferred to master232. Master232likewise initiates a protection window404bto protect its ownership of the memory block requested in request402following receipt of combined response410.

Because snoopers222,236all have limited resources for handling the CPU and I/O requests described above, several different levels of partial responses and corresponding CRs are possible. For example, if a snooper222within a memory controller206that is responsible for a requested memory block has queue available to handle a request, the snooper222may respond with a partial response indicating that it is able to serve as the LPC for the request. If, on the other hand, the snooper222has no queue available to handle the request, the snooper222may respond with a partial response indicating that is the LPC for the memory block, but is unable to currently service the request.

Similarly, a snooper236in an L2 cache230may require an available instance of snoop logic and access to L2 cache directory302in order to handle a request. Absence of access to either (or both) of these resources results in a partial response (and corresponding CR) signaling an inability to service the request due to absence of a required resource.

Hereafter, a snooper222,236providing a partial response indicating that the snooper has available all internal resources required to service a request, if required, is said to “affirm” the request. For snoopers236, partial responses affirming a snooped operation preferably indicate the cache state of the requested or target memory block at that snooper236. A snooper236providing a partial response indicating that the snooper236does not have available all internal resources required to service the request may be said to be “possibly hidden.” Such a snooper236is “possibly hidden” because the snooper236, due to lack of an available instance of snoop logic or access to L2 cache directory302, cannot “affirm” the request in sense defined above and has, from the perspective of other masters232and snoopers222,236, an unknown coherency state.

III. Data Delivery Domains

Conventional broadcast-based data processing systems handle both cache coherency and data delivery through broadcast communication, which in conventional systems is transmitted on a system interconnect to at least all memory controllers and cache hierarchies in the system. As compared with systems of alternative architectures and like scale, broadcast-based systems tend to offer decreased access latency and better data handling and coherency management of shared memory blocks.

As broadcast-based system scale in size, traffic volume on the system interconnect is multiplied, meaning that system cost rises sharply with system scale as more bandwidth is required for communication over the system interconnect. That is, a system with m processor cores, each having an average traffic volume of n transactions, has a traffic volume of m×n, meaning that traffic volume in broadcast-based systems scales multiplicatively not additively. Beyond the requirement for substantially greater interconnect bandwidth, an increase in system size has the secondary effect of increasing some access latencies. For example, the access latency of read data is limited, in the worst case, by the combined response latency of the furthest away lower level cache holding the requested memory block in a shared coherency state from which the requested data can be sourced.

In order to reduce system interconnect bandwidth requirements and access latencies while still retaining the advantages of a broadcast-based system, the present invention reduces data access latency by decreasing the average distance between a requesting L2 cache230and an data source. One technique for do so is to reducing the average distance between a requesting L2 cache230and a data source is to permit multiple L2 caches230distributed throughout data processing system100to hold copies of the same memory block in a “special” shared coherency state that permits these caches to supply the memory block to requesting L2 caches230using cache-to-cache intervention via local and system interconnects114,110.

In order to implement multiple concurrent and distributed sources for shared memory blocks in an SMP data processing system, such as data processing system100, two issues must be addressed. First, some rule governing the creation of copies of memory blocks in the “special” shared coherency state alluded to above must be implemented. Second, there must be a rule governing which snooping L2 cache230, if any, provides a shared memory block to a requesting L2 cache230, for example, in response to a bus read operation or bus RWITM operation.

According to the present invention, both of these issues are addressed through the implementation of data sourcing domains. In particular, each domain within a SMP data processing system, where a domain is defined to include one or more lower level (e.g., L2) caches that participate in responding to data requests, is permitted to include only one cache hierarchy that holds a particular memory block in the “special” shared coherency state at a time. That cache hierarchy, if present when a bus read-type (e.g., read or RWITM) operation is initiated by a requesting lower level cache in the same domain, is responsible for sourcing the requested memory block to the requesting lower level cache. Although many different domain sizes may be defined, in data processing system100ofFIG. 1, it is convenient if each processing node102(i.e., MCM) is considered a data sourcing domain. One example of such a “special” shared state (i.e., Sr) is described below with reference to Table II.

While the implementation of data delivery domains as described above improves data access latency, this enhancement does not address the m×n multiplication of traffic volume as system scale increases. In order to reduce traffic volume while still maintaining a broadcast-based coherency mechanism, preferred embodiments of the present invention additionally implement coherency domains, which like the data delivery domains hereinbefore described, can conveniently (but are not required to be) implemented with each processing node102forming a separate coherency domain. Data delivery domains and coherency domains can be, but are not required to be coextensive, and for the purposes of explaining exemplary operation of data processing system100will hereafter be assumed to have boundaries defined by processing nodes102.

The implementation of coherency domains reduces system traffic by limiting inter-domain broadcast communication over system interconnect110in cases in which requests can be serviced with participation by fewer than all coherency domains. For example, if processing unit104aof processing node102ahas a bus read operation to issue, then processing unit104amay elect to first broadcast the bus read operation to all participants within its own coherency domain (e.g., processing node102a), but not to participants in other coherency domains (e.g., processing node102b). A broadcast operation transmitted to only those participants within the same coherency domain as the master of the operation is defined herein as a “local operation”. If the local bus read operation can be serviced within the coherency domain of processing unit104a, then no further broadcast of the bus read operation is performed. If, however, the partial responses and combined response to the local bus read operation indicate that the bus read operation cannot be serviced solely within the coherency domain of processing node102a, the scope of the broadcast may then be extended to include, in addition to the local coherency domain, one or more additional coherency domains.

In a basic implementation, two broadcast scopes are employed: a “local” scope including only the local coherency domain and a “global” scope including all of the other coherency domains in the SMP data processing system. Thus, an operation that is transmitted to all coherency domains in an SMP data processing system is defined herein as a “global operation”. Importantly, regardless of whether local operations or operations of more expansive scope (e.g., global operations) are employed to service operations, cache coherency is maintained across all coherency domains in the SMP data processing system.

In a preferred embodiment, the scope of an operation is indicated in a bus operation by a local/global indicator (signal), which in one embodiment may comprise a 1-bit flag. Forwarding logic212within processing units104preferably determines whether or not to forward an operation received via local interconnect114onto system interconnect110based upon the setting of the local/global indicator (signal) in the operation.

V. Domain Indicators

In order to limit the issuance of unneeded local operations and thereby reduce operational latency and conserve additional bandwidth on local interconnects, the present invention preferably implements a domain indicator per memory block that indicates whether or not a copy of the associated memory block is cached outside of the local coherency domain. For example,FIG. 5depicts a first exemplary implementation of a domain indicator in accordance with the present invention. As shown inFIG. 5, a system memory108, which may be implemented in dynamic random access memory (DRAM), stores a plurality of memory blocks500. System memory108stores in association with each memory block500an associated error correcting code (ECC)502utilized to correct errors, if any, in memory block500and a domain indicator504. Although in some embodiments of the present invention, domain indicator504may identify a particular coherency domain (i.e., specify a coherency domain or node ID), it is hereafter assumed that domain indicator504is a 1-bit indicator that is set (e.g., to ‘1’ to indicate “local”) if the associated memory block500is cached, if at all, only within the same coherency domain as the memory controller206serving as the LPC for the memory block500. Domain indicator504is reset (e.g., to ‘0’ to indicate “global”) otherwise. The setting of domain indicators504to indicate “local” may be implemented imprecisely in that a false setting of “global” will not induce any coherency errors, but may cause unneeded global broadcasts of operations.

Importantly, memory controllers206(and L2 caches230) that source a memory block in response to an operation preferably transmit the associated domain indicator504in conjunction with the requested memory block.

The present invention preferably implements a cache coherency protocol designed to leverage the implementation of data delivery and coherency domains as described above. In a preferred embodiment, the cache coherency states within the protocol, in addition to providing (1) an indication of whether a cache is the HPC for a memory block, also indicate (2) whether the cached copy is unique (i.e., is the only cached copy system-wide) among caches at that memory hierarchy level, (3) whether and when the cache can provide a copy of the memory block to a master of a request for the memory block, (4) whether the cached image of the memory block is consistent with the corresponding memory block at the LPC (system memory), and (5) whether another cache in a remote coherency domain (possibly) holds a cache entry having a matching address. These five attributes can be expressed, for example, in an exemplary variant of the well-known MESI (Modified, Exclusive, Shared, Invalid) protocol summarized below in Table II.

A. Ig State

In order to avoid having to access the LPC to determine whether or not the memory block is known to be cached, if at all, only locally, the Ig (Invalid global) coherency state is utilized to maintain a domain indication in cases in which no copy of a memory block remains cached in a coherency domain. The Ig state is defined herein as a cache coherency state indicating (1) the associated memory block in the cache array is invalid, (2) the address tag in the cache directory is valid, and (3) a copy of the memory block identified by the address tag may possibly be cached in another coherency domain. The Ig indication is preferably imprecise, meaning that it may be incorrect without a violation of coherency.

The Ig state is formed in a lower level cache in response to that cache providing a requested memory block to a requestor in another coherency domain in response to an exclusive access request (e.g., a bus RWITM operation). In some embodiments of the present invention, it maybe preferable to form the Ig state only in the coherency domain containing the LPC for the memory block. In such embodiments, some mechanism (e.g., a partial response by the LPC and subsequent combined response) must be implemented to indicate to the cache sourcing the requested memory block that the LPC is within its local coherency domain. In other embodiments that do not support the communication of an indication that the LPC is local, an Ig state may be formed any time that a cache sources a memory block to a remote coherency domain in response to an exclusive access request.

Because cache directory entries including an Ig state carry potentially useful information, it is desirable in at least some implementations to preferentially retain entries in the Ig state over entries in the I state (e.g., by modifying the Least Recently Used (LRU) algorithm utilized to select a victim cache entry for replacement). As Ig directory entries are retained in cache, it is possible for some Ig entries to become “stale” over time in that a cache whose exclusive access request caused the formation of the Ig state may deallocate or writeback its copy of the memory block without notification to the cache holding the address tag of the memory block in the Ig state. In such cases, the “stale” Ig state, which incorrectly indicates that a global operation should be issued instead of a local operation, will not cause any coherency errors, but will merely cause some operations, which could otherwise be serviced utilizing a local operation, to be issued as global operations. Occurrences of such inefficiencies will be limited in duration by the eventual replacement of the “stale” Ig cache entries.

Several rules govern the selection and replacement of Ig cache entries. First, if a cache selects an Ig entry as the victim for replacement, a castout of the Ig entry is performed (unlike the case when an I entry is selected). Second, if a request that causes a memory block to be loaded into a cache hits on an Ig cache entry in that same cache, the cache treats the Ig hit as a cache miss and performs a castout operation with the an Ig entry as the selected victim. The cache thus avoids avoid placing two copies of the same address tag in the cache directory. Third, the castout of the Ig state is preferably performed as a local operation, or if performed as a global operation, ignored by the LPC of the castout address. If an Ig entry is permitted to form in a cache that is not within the same coherency domain as the LPC for the memory block, no update to the domain indicator in the LPC is required. Fourth, the castout of the Ig state is preferably performed as a dataless address-only operation in which the domain indicator is written back to the LPC (if local to the cache performing the castout).

Implementation of an Ig state in accordance with the present invention improves communication efficiency by maintaining a cached domain indicator for a memory block in a coherency domain even when no valid copy of the memory block remains cached in the coherency domain. As a consequence, an HPC for a memory block can service an exclusive access request (e.g., bus RWITM operation) from a remote coherency domain without retrying the request and performing a push of the requested memory block to the LPC.

B. In State

The In state is defined herein as a cache coherency state indicating (1) the associated memory block in the cache array is invalid, (2) the address tag in the cache directory is valid, and (3) a copy of the memory block identified by the address tag is likely cached, if at all, only by one or more other cache hierarchies within the local coherency domain. The In indication is preferably imprecise, meaning that it may be incorrect without a violation of coherency. The In state is formed in a lower level cache in response to that cache providing a requested memory block to a requester in the same coherency domain in response to an exclusive access request (e.g., a bus RWITM operation).

Because cache directory entries including an In state carry potentially useful information, it is desirable in at least some implementations to preferentially retain entries in the In state over entries in the I state (e.g., by modifying the Least Recently Used (LRU) algorithm utilized to select a victim cache entry for replacement). As In directory entries are retained in cache, it is possible for some In entries to become “stale” over time in that a cache whose exclusive access request caused the formation of the In state may itself supply a shared copy of the memory block to a remote coherency domain without notification to the cache holding the address tag of the memory block in the In state. In such cases, the “stale” In state, which incorrectly indicates that a local operation should be issued instead of a global operation, will not cause any coherency errors, but will merely cause some operations to be erroneously first issued as local operations, rather than as global operations. Occurrences of such inefficiencies will be limited in duration by the eventual replacement of the “stale” In cache entries. In a preferred embodiment, cache entries in the In coherency state are not subject to castout, but are instead simply replaced. Thus, unlike Ig cache entries, In cache entries are not utilized to update domain indicators504in system memories108.

Implementation of an In state in accordance with the present invention improves communication efficiency by maintaining a cached domain indicator for a memory block that may be consulted by a master in order to select a local scope for one of its operations. As a consequence, bandwidth on system interconnect110and local interconnects114in other coherency domains is conserved.

B. Sr State

In the operations described below, it is useful to be able to determine whether or not a lower level cache holding a shared requested memory block in the Sr coherency state is located within the same domain as the requesting master. In one embodiment, the presence of a “local” Sr snooper within the same domain as the requesting master can be indicated by the response behavior of a snooper at a lower level cache holding a requested memory block in the Sr coherency state. For example, assuming that each bus operation includes a scope indicator indicating whether the bus operation has crossed a domain boundary (e.g., an explicit domain identifier of the master or a single local/not local bit), a lower level cache holding a shared memory block in the Sr coherency state can provide a partial response affirming the request in the Sr state only for requests by masters within the same data sourcing domain and provide partial responses indicating the S state for all other requests. In such embodiments the response behavior can be summarized as shown in Table III, where prime (′) notation is utilized to designate partial responses that may differ from the actual cache state of the memory block.

TABLE IIIDomain of masterCachePartial responsePartial responseof read-typestate in(adequate resources(adequate resourcesrequestdirectoryavailable)unavailable)“local” (i.e.,SrSr′ affirmSr′ possiblywithin samehiddendomain)“remote” (i.e.,SrS′ affirmS′ possiblynot within samehiddendomain)“local” (i.e.,SS′ affirmS′ possiblywithin samehiddendomain)“remote” (i.e.,SS′ affirmS′ possiblynot within samehiddendomain)
Assuming the response behavior set forth above in Table III, the average data latency for shared data can be significantly decreased by increasing the number of shared copies of memory blocks distributed within an SMP data processing system that may serve as data sources.

With reference now generally toFIGS. 6A–13, several high level logical flowcharts depicting the logical steps involved in servicing exemplary requests of processor cores200and L2 caches230are given. In particular,FIGS. 6A–7Bdepict the various processes within masters of the requests, andFIGS. 8–13illustrate operations involved with communicating and servicing the requests via local and system interconnects114,110. Even though interconnects110,114are not necessarily bused interconnects, such operations are termed “bus operations” (e.g., bus read operation, bus write operation, etc.) herein to distinguish them from cache or CPU (processor) operations. As logical flowcharts, it should be understood that these figures are not intended to convey a strict chronology of operations and that many of the illustrated operations may be performed concurrently or in a different order than that shown.

A. CPU Operations

With reference first toFIG. 6A–6B, there is depicted a high level logical flowchart of an exemplary method of servicing a processor read operation in a data processing system in accordance with the present invention. As shown, the process begins at block600, which represents a master232in an L2 cache230areceiving a read request from an associated processor core200a. The process then proceeds to block634, which depicts master232initiating a lookup of L2 cache directory302to determine the coherency state, if any, recorded within L2 cache directory302for the target address specified by the memory access operation. Concurrently, at block660master232also issues a speculative intervention request via private communication network270to the L2.1 cache230b(and the optional L3 cache250, if any) to determine the coherency state, if any, recorded within its cache directory302for the target address specified by the memory access operation. In general, master232will receive the results of the lookup of its local L2 directory302in advance of receipt of the results of the L2.1 intervention request.

In response to receipt of the result of the lookup of L2 cache directory302, master232determines at block636whether or not the coherency state, if any, recorded within L2 cache directory302for the target address permits the CPU read operation to be serviced without first accessing a lower level of the memory hierarchy (i.e., whether the coherency state for the target memory block is M, Me, Tx (i.e., T, Tn, Ten), Sr, or S). In response to master232determining at block636that the target address hit in L2 cache directory302in a coherency state that permits the CPU read operation to be serviced without first accessing a lower level of the memory hierarchy, the process proceeds from block636to block638, which illustrates master232ignoring the results of the L2.1 intervention request. Master232then services the CPU read operation by supplying the requested memory block to the requesting processor core200a, as illustrated at block644. Following block644, the process ends at block646.

Returning to block636, if master232determines that the target address did not hit in L2 cache directory302in a coherency state that permits the CPU read operation to be serviced without first accessing a lower level of the memory hierarchy, the process proceeds from block636to block634. Block634depicts a determination of whether or not a castout of an existing cache line is required to accommodate the requested memory block in L2 cache230a. In one embodiment, a castout operation is required at block634and at similar blocks in succeeding figures if the memory block selected as a victim for eviction from the L2 cache230of the requesting processor is marked in L2 directory302as being in any of the M, T, Te, Tn or Ig coherency states. In response to a determination at block634that a castout is required, a cache castout operation is performed, as indicated at block636. Concurrently, the master232determines at block650whether or not the coherency state of the target address is in one of the “tagged” I states (e.g., In or Ig) in L2 cache directory302. If the target address hit in L2 cache directory302in one of the “tagged” I states (e.g., In or Ig), master232ignores the results of the L2.1 intervention request when received (block652) and issues a bus read operation for the target address on the interconnect fabric without waiting for the results of the L2.1 intervention request (block654). A bus read operation is issued because (as explained further below) the “tagged” coherency states are established when a processing core200associated with a different cache hierarchy that is not coupled to the requesting L2 cache230by a private communication network270successfully issues a memory access request (e.g., RWITM or DClaim) on the interconnect fabric to obtain exclusive access to the target memory block. Consequently, it is preferable to issue the bus read operation on the interconnect fabric without incurring the additional latency associated with waiting for the results of the L2.1 intervention request because it is unlikely that the L2.1 cache230bholds the target address in one of the coherency states required to service the CPU read operation, as taught U.S. patent application Ser. No. 11/095,734. After the bus read operation is successfully completed, the process proceeds to blocks644and646, which have been described.

Returning to block650, in response to master232determining that the target address did not hit in L2 cache directory302in one of the “tagged” I states (e.g., In or Ig), master232awaits the results of the L2.1 intervention request. In response to receipt of the results of the L2.1 intervention request, master232determines at block662if the target address hit in the L2.1 cache230bin a coherency state that permits master232to service the CPU read operation (i.e., M, Me, Tx, Sr or S) without issuing a bus operation on the interconnect fabric114,110. If not, the process passes to block654, which has been described. If, however, master232determines at block662that the target address hit in the L2.1 directory302in a coherency state that permits the CPU read operation to be serviced without issuing a request on the interconnect fabric114,110, the process passes to block664, which illustrates L2 cache230areceiving the target memory block from L2.1 cache230b. Master232then determines at block668whether or not it chose to ignore the response to the L2.1 intervention request. If so, master232discards the memory block received by direct intervention from L2.1 cache230bvia private communication network270, as shown at block670, and instead waits to receive the target memory block in response to the bus read operation via the interconnect fabric114,110. Following block670, this branch of the illustrated process ends at block646. If, on the other hand, master232determines at block668that it did not choose to ignore the L2.1 intervention response, master232services the CPU read operation utilizing the data provided by L2.1 cache230b, as shown at block644. The process thereafter ends at block646.

It should be noted that in a small percentage of cases, the speculative bypass of L2.1 cache230bwill prove to be incorrect in that the L2.1 cache230bof the requesting processing unit104holds the required memory block in a coherency state that permits the CPU read operation to be serviced. To avoid errors, L2.1 cache230bsnoops memory access requests on local interconnect114(including those requests issued by the other L2 cache230ain the same processing unit104) and responds to those memory access requests via the interconnect fabric114,110like any other snooper. In this manner, if the speculative bypass of L2.1 cache230bproves to be incorrect, the bus read operation can still be serviced, albeit at a longer latency than would have been incurred if L2.1 cache230bhad directly intervened the memory block via private communication network270.

Referring now toFIG. 6B, there is depicted a more detailed flowchart of the issuance of the bus read operation at block654ofFIG. 6A. As shown, the process begins at block602and then proceeds to block610, which illustrates a determination by master232of whether the bus read operation should be issued as a local operation having a scope limited to only the local interconnect114of L2 cache230aor a global operation transmitted on system interconnect110and all local interconnects114.

In a first embodiment in which each bus operation is initially issued as a local operation and issued as a local operation only once, the determination depicted at block610(and like determinations in succeeding figures) can simply represent a determination by the master232of whether or not the bus read operation has previously been issued as a local bus read operation. In a second alternative embodiment in which local bus operations can be retried, the determination depicted at block610can represent a determination by the master of whether or not the bus read operation has previously been issued more than a threshold number of times. In a third alternative embodiment, the determination made at block610can be based upon a prediction by the master of whether or not a local operation is likely to be successful (e.g., is the HPC or is likely to find the HPC in the local coherency domain).

In response to a determination at block610to issue a global bus read operation rather than a local bus read operation, the process proceeds from block610to block620, which is described below. If, on the other hand, a determination is made at block610to issue a local bus read operation, master232initiates a local bus read operation on its local interconnect114, as illustrated at block612and described below. The local bus read operation is broadcast only within the local coherency domain (e.g., processing node102) containing master232. If master232receives a CR indicating “success” (block614), master232receives the requested memory block and returns the requested memory block (or at least a portion thereof) to the requesting processor core200, as shown at block624. Thereafter, the process returns toFIG. 6Aat block626.

Returning to block614, if the CR for the local bus read operation does not indicate “success”, master232makes a determination at block616whether or the CR definitively indicates that the bus read operation cannot be serviced within the local coherency domain and should therefore be reissued as a global bus read operation. If so (e.g., if an L2 cache230in another coherency domain holds the requested memory block in the M state or Me state), the process passes to block620, which is described below. If, on the other hand, the CR does not definitively indicate that the bus read operation cannot be serviced within the local coherency domain, the process returns from block616to block610, which illustrates master232again determining whether or not to issue a local bus read operation. In this case, master232may employ in the determination any additional information provided by the CR. Following block610, the process passes to either block612, which is described above, or to block620.

Block620depicts master230issuing a global bus read operation as described below. If the CR of the global bus read operation does not indicate “success” at block622, master232repeats the global bus read operation at block620until a CR indicating “success” is received. If the CR of the global bus read operation indicates “success”, the master232receives the requested memory block and returns the requested memory block (or at least a portion thereof) to the requesting processor core200at block624. The process thereafter returns toFIG. 6Aat block626.

Thus, assuming affinity between processes and their data within the same coherency domain, operations, such as the CPU read operation depicted inFIGS. 6A–6B, can frequently be serviced utilizing broadcast communication limited in scope to the coherency domain of the requesting master. The combination of data delivery domains as hereinbefore described and coherency domains thus improves not only data access latency, but also reduces traffic on the system interconnect (and other local interconnects) by limiting the scope of broadcast communication.

Referring now toFIG. 7A–7B, there is illustrated a high level logical flowchart of an exemplary method of servicing a processor update operation in a data processing system in accordance with the present invention. As depicted, the process begins at block700in response to receipt by an L2 cache230of an update request by an associated one of the processor cores200within the same processing unit104. In response to the receipt of the update request, master232of the L2 cache230accesses L2 cache directory302to determine if the memory block referenced by the request address specified by the update request is cached within L2 cache230in M state, as shown at block702. If so, the master232updates the memory block in L2 cache232within the new data supplied by the processor core200, as illustrated at block704. Thereafter, the update process ends at block706.

As shown at blocks710–712, if L2 cache directory302instead indicates that L2 cache230holds the specified memory block in the Me state, master232updates the state field306for the requested memory block to M state in addition to updating the memory block as shown at block704. Thereafter, the process terminates at block706.

Following page connector A toFIG. 7B, if L2 cache directory302indicates that L2 cache230holds the requested memory block in either of the T or Te states (block720), meaning that the L2 cache230is the HPC for the requested memory block and the requested memory block may possibly be held in one or more other L2 caches230, master232must gain exclusive access to the requested memory block in order to perform the requested update to the memory block. The process by which master232gains exclusive access to the requested memory block is shown at block722and following blocks.

According to this process, master232updates the state of the requested memory block in the associated state field306of L2 cache directory302to the M state, as depicted at block722. This upgrade is cache state is permissible without first informing other L2 caches230because, as the HPC, the L2 cache230has the authority to award itself exclusive access to the requested memory block. As illustrated at block724, the snooper236of the L2 cache230provides “downgrade” partial responses to competing DClaim operations snooped on its local interconnect114, if any, by which other masters are seeking ownership of the requested memory block. These partial responses indicate that the other requesters must reissue any such competing operations as bus RWITM operations. In addition, as depicted at block726, master232issues a global bus kill operation on system interconnect110to invalidate any other cached copies of the memory block, as described below.

Master232next determines at blocks790and728whether or not the CR for the bus kill operation indicates that the bus kill operation successfully invalidated all other cached copies of the requested memory block or whether additional local or global “cleanup” (i.e., invalidation of other cached copies) is required. If the CR indicates that additional cleanup is not required, the process proceeds through page connector C to block704ofFIG. 7A, which has been described. If the CR indicates that additional cleanup is required, master232additionally determines whether the CR indicates that the other cached copy or copies of the requested memory block reside entirely within its local coherency domain or whether at least one copy of the requested memory block is cached outside the local coherency domain of master232(blocks790and728). If the CR indicates that each remaining cached copy of the requested memory block resides in the local coherency domain of master232, the snooper236of the requesting L2 cache230continues to downgrade active bus DClaim operations (block786), and the master232of the requesting L2 cache230continues to issue local bus kill operation (block788) limited in scope to the local coherency domain of master232until all other cached copies of the memory block are invalidated. If the CR indicates that at least one remaining cached copy of the requested memory block resides in a remote coherency domain, the process returns to block724, which has been described.

With reference now to block780, if the access to the L2 cache directory302indicates that the requested memory block is held in one of the Tn or Ten states, then master232knows that the requesting L2 cache230is the HPC for the requested memory block and that any other cached copy of the requested memory block is held by a cache in its local coherency domain. Accordingly, master232updates the state of the requested memory block in the associated state field306of L2 cache directory302to the M state, as depicted at block784. In addition, the snooper236of the requesting L2 cache230provides “downgrade” partial responses to any competing DClaim operations snooped on its local interconnect114(block786), and the master232of the requesting L2 cache230continues to issue local bus kill operation (block788) limited in scope to the local coherency domain of master232until any other cached copies of the memory block are invalidated. If the master232determines by reference to the CR for a local bus kill operation that no further local cleanup is required (block790), the process passes through block728and page connector C to block704, which has been described.

Referring now to block730ofFIG. 7A, if the access to L2 cache directory302indicates that the requested memory block is held in the Sr or S states, the requesting L2 cache230is not the HPC for the requested memory block, and master232must gain ownership of the requested memory block from the HPC, if any, or in the absence of an HPC, the LPC, prior to updating the memory block.

Accordingly, master232first determines at block731whether to issue a bus DClaim operation as a local or global operation. If master232makes a determination to issue a global bus DClaim operation, the process proceeds to block740, which is described below. In response to a determination at block731to issue a bus DClaim operation as a local operation, master232issues a local bus DClaim operation at block732, as described below in greater detail. Master232then awaits receipt of the CR of the local bus DClaim operation, which is represented by the collection of decision blocks734,736and738. If the CR indicates “retry” (block734), the process returns to block731, which has been described. If the CR alternatively indicates definitively that the bus DClaim operation cannot be serviced with the local coherency domain (block736), the process proceeds to block740, which is described below. If the CR alternatively indicates “downgrade”, meaning that another requestor has obtained ownership of the requested memory block via a bus DClaim operation, the process passes to block748, which is described below. If the CR alternatively indicates that master232has been awarded ownership of the requested memory block by the HPC based upon the local bus DClaim operation, the process passes through page connector D to block790ofFIG. 7Band following blocks, which have been described.

Block740depicts master232issuing a global bus DClaim operation, as described below. Master232next determines at blocks742-744whether or not the CR for the global bus DClaim operation indicates that it succeeded, should be retried, or was “downgraded” to a RWITM operation. If the CR indicates that the bus DClaim operation should be retried (block742), master232reissues a global bus DClaim operation at block740and continues to do so until a CR other than “retry” is received. If the CR is received indicating that the global bus DClaim operation has been downgraded in response to another requestor successfully issuing a bus DClaim operation targeting the requested memory block, the process proceeds to block746, which is described below. If the CR alternatively indicates that master232has been awarded ownership of the requested memory block by the HPC based upon the global bus DClaim operation, the process passes through page connector D to block790ofFIG. 7Band following blocks, which have been described.

Block746depicts master232of the requesting L2 cache230determining whether or not to issue a bus RWITM operation as a local or global operation. If master232elects to issue a global RWITM operation, the process passes to block754, which is described below. If, however, master232elects to issue a local bus RWITM operation, the process proceeds to block748, which illustrates master232issuing a local bus RWITM operation and awaiting the associated CR. As indicated at block750, if the CR indicates “retry”, the process returns to block746, which represents master232again determining whether to issue a local or global RWITM operation utilizing the additional information, if any, provided in the retry CR. If the CR to the local bus RWTIM operation issued at block748does not indicate “retry” (block750) but instead indicates that the bus RWITM operation was successful in obtaining ownership of the requested memory block (block752), the process passes through page connector D to block790ofFIG. 7B, which has been described. If master232determines at block752that the CR to the local bus RWITM operation indicates that the operation cannot be serviced within the local coherency domain, the process passes to block754and following blocks.

Blocks754and756depict master232iteratively issuing a global bus RWITM operation for the requested memory block, as described below, until a CR other than “retry” is received. In response to master232receiving a non-retry CR indicating that it succeeded in obtaining ownership of the requested memory block (block756), the process passes through page connector D to block790and following blocks, which have been described.

With reference now to block760, if a negative determination has been made at blocks702,710,720,5502and730, L2 cache230does not hold a valid copy of the requested memory block. Accordingly, as indicated at blocks760and770, L2 cache230performs a cache castout operation if needed to allocate a cache line for the requested memory block. Thereafter, the process passes to block746and following blocks as described above.

As has been described, the implementation of Tn and Ten coherency states provides an indication of whether a possibly shared memory block is additionally cached only within the local coherency domain. Consequently, when a requestor within the same coherency domain as a cache holding a memory block in one of the Tn or Ten states issues an exclusive access operation (e.g., a bus DClaim, bus RWITM, bus DCBZ or bus write operation) for the memory block, the scope of broadcast operations, such as bus kill operations, can advantageously be restricted to the local coherency domain, reducing interconnect bandwidth utilization.

Referring now toFIGS. 8–13, exemplary local and global bus operations in an illustrative data processing system100will now be described. Referring first toFIG. 8, there is depicted a high level logical flowchart of an exemplary method of performing a local bus read operation in a data processing system in accordance with the present invention. The process begins at block1300, for example, at block612ofFIG. 6B, with an L2 cache230issuing a local bus read operation on its local interconnect114. The various partial responses that snoopers222,236may provide to distributed response logic210in response to snooping the local bus read operation are represented inFIG. 8by the outcomes of decision blocks1302,1310,1312,1314,1320,1330,1332,1340,1344,1346and1348. These partial responses in turn determine the CR for the local bus read operation.

As shown at block1302, if a snooper236of an L2 cache230affirms the local bus read operation with a partial response indicating that the L2 cache230holds the requested memory block in either the M or Me state, the process proceeds from block1302to block1304. Block1304indicates the operations of the requesting L2 cache230and the affirming L2 cache230in response to the local bus read operation. In particular, the snooper236in the affirming L2 cache230updates the cache state of the requested memory block from M to Tn or from Me to Ten. In addition, the snooper236in the affirming L2 cache230may initiate transmission of the requested memory block to the requesting L2 cache230prior to receipt of the CR (i.e., provides “early” data). Upon receipt, the master232in the requesting L2 cache230places the requested memory block in L2 cache array300in the Sr state. The process ends with distributed response logic210generating a CR indicating “success”, as depicted at block1308.

If, on the other hand, a snooper236of an L2 cache230affirms the local bus read operation with a partial response indicating that the L2 cache230holds the requested memory block in the Tx state (block1310) and an Sr′ snooper236also affirms the bus read operation (block1312), the process passes to block1318. Block1318represents the Sr′ snooper236updating the cache state of the requested memory block to S and initiating transmission of the requested memory block to the requesting L2 cache230prior to receipt of the CR (i.e., provides “early” data). The Tx snooper236remains unchanged. Upon receipt of the requested memory block, the master232in the requesting L2 cache230places the requested memory block in L2 cache array300in the Sr state. The process ends with distributed response logic210generating a CR indicating “success”, as depicted at block1308.

If the complex of partial responses includes a Tx snooper236affirming the local bus read operation (block1310), no Sr′ snooper236affirming the bus read operation (block1312), and a snooper236providing an partial response (e.g., a type of retry) indicating that an Sr′ snooper236may be possibly hidden in the local data delivery domain (block1314), the process passes to block1316. Block1316represents the Tx snooper236that affirmed the bus read operation initiating transmission of the requested memory block to the requesting L2 cache230after receipt of the CR (i.e., provides “late” data) and retaining the requested memory block in the Tx state. Upon receipt, the master232in the requesting L2 cache230places the requested memory block in L2 cache directory300in the S state (since an Sr′ snooper236may be hidden and only one Sr′ snooper236is permitted in each data delivery domain for the requested memory block). The process ends with distributed response logic210generating a CR indicating “success”, as depicted at block1308.

If the complex of partial responses includes a T or Te snooper236affirming the local bus read operation (block1310), no Sr′ snooper236affirming the bus read operation (block1312), and no snooper236providing a partial response that may possibly hide a Sr′ snooper236(block1314), the process passes to block1306. Block1306represents the T or Te snooper236that affirmed the bus read operation initiating transmission of the requested memory block to the requesting L2 cache230after receipt of the CR (i.e., provides “late” data) and retaining the requested memory block in the T or Te state. Upon receipt, the master232in the requesting L2 cache230places the requested memory block in L2 cache array300in the Sr state (since no other Sr′ snooper236exists for the requested memory block in the local data delivery domain). The process ends with distributed response logic210generating a CR indicating “success”, as depicted at block1308.

Referring now to block1320, if no M, Me, or Tx snooper236affirms the local bus read operation, but an Sr′ snooper236affirms the local bus read operation, the local bus read operation is serviced in accordance with block1322. In particular, the Sr′ snooper236affirming the bus read operation initiates transmission of the requested memory block to the requesting L2 cache230prior to receipt of CR and updates the state of the requested memory block in its L2 cache directory302to the S state. The master232in the requesting L2 cache230places the requested memory block in its L2 cache array300in the Sr state. The process ends with distributed response logic210generating a CR indicating “success”, as depicted at block1308.

With reference now to block1324, if no M, Me, Tx or Sr′ snooper236affirms the local bus read operation, but an L2 cache230provides a partial response affirming the local bus read operation indicating that the L2 cache230holds the address tag of the requested memory block in the Ig state. If no M, Me, Tx or Sr′ snooper236is possibly hidden by an incomplete partial response (block1332), distributed response logic210provides a “go global” CR, as depicted at block3164. If, on the other hand, an Ig snooper236affirms the local bus read operation and the complex of partial responses indicates an M, Me, Tx or Sr′ snooper236is possibly hidden, response logic210generates a “retry” CR, as depicted at block1342.

Turning now to block1330, if no M, Me, Tx, Sr′ or Ig snooper236affirms the local bus read operation, and further, if no snooper222provides a partial response indicating that it is responsible (i.e., the LPC) for the requested memory block, the process passes to block1332, which has been described. If, however, no M, Me, Tx, Sr′ or Ig snooper236affirms the local bus read operation, and further, if a snooper222provides a partial response indicating that it is responsible (i.e., the LPC) for the requested memory block, the process proceeds to block1340.

Referring now to block1340, if a snooper222provides a partial response indicating that it is responsible (i.e., the LPC) for the requested memory block but does not affirm the local bus read operation, response logic210generates a CR indicating “retry”, as depicted at block1342. If, however, a snooper222affirms the local bus read operation, the process proceeds to block1344. As indicated by decision block1344, response logic210also generates a “retry” CR at block1342if a memory controller snooper222affirms the bus read operation and an L2 cache snooper236provides a partial response indicating that it may hold the requested memory block in one of the M, Me, Tx or Ig states but cannot affirm the local bus read operation. In each of these cases, response logic210generates a “retry” CR because the bus read operation, if reissued as a local operation, may be able to be serviced without resorting to a global broadcast.

With reference now to block1346, if no M, Me, Tx or Ig snooper236affirms the local bus read operation, no M, Me, Tx or Ig snooper236is possibly hidden, and a memory controller snooper222affirms the local bus read operation, the snooper222affirming the local bus read operation provides the requested memory block and the associated domain indicator504to the requesting L2 cache230in response to the CR, as depicted at each of blocks1350,1352and1354. As shown at blocks1350,1352and1354, the master232of the requesting L2 cache230handles the requested memory block in accordance with the CR and the state of the domain indicator504. In particular, if master232determines at block1360that the domain indicator3004is reset to “global”, meaning that a modified copy of the requested memory block may be cached outside the local domain, master232of the requesting L2 cache230discards the requested memory block, remaining in the I state with respect to the requested memory block. In addition, in light of the “global” domain indicator504, master232interprets the CR as indicating “go global” (block1364), meaning that master232will reissue the bus read operation as a global bus read operation.

If, on the other hand, the domain indicator504is set to indicate “local” (block1360), the master232of the requesting cache230interprets the CR as indicating “success” (block1308) and places both the requested memory block and domain indicator504within its L2 cache array300. The master232also sets the state field306associated with the requested memory block to a state indicated by the CR. In particular, if the partial responses and hence the CR indicate that a Sr′ snooper236may be hidden (block1346), the requesting L2 cache230holds the requested memory block in the S state (block1350) because only one Sr copy of the memory block is permitted in any domain. Alternatively, if the partial responses and CR indicate that no Sr′ snooper236may be hidden, but an S′ snooper236may be hidden, the requesting L2 cache236holds the requested memory block in the Sr state (block1352). Finally, if neither a Sr′ or S′ snooper236may be possibly hidden (block1348), the requesting L2 cache230holds the requested memory block in the Me state (block1354) because the requesting L2 cache230is guaranteed to be the only cache system-wide holding the requested memory block.

With reference now toFIGS. 9A–9B, there is depicted a high level logical flowchart of an exemplary method of performing a global bus read operation in a data processing system implementing Tn and Ten coherency states in accordance with the present invention. The process begins at block1400, for example, at block620ofFIG. 6B, with an L2 cache230issuing a global bus read operation on its local interconnect114. The various partial responses that snoopers222,236may provide to distributed response logic210in response to snooping the global bus read operation are represented inFIG. 9Aby the outcomes of decision blocks1402,1410,1412,1414,1420,1430,1440,1442,1444, and1446. These partial responses in turn determine the CR for the global bus read operation.

As shown at block1402, if a snooper236of an L2 cache230affirms the global bus read operation with a partial response indicating that the L2 cache230holds the requested memory block in either the M or Me state, the process proceeds from block1402through page connector J to block1480ofFIG. 9B. Block1480represents the fact that the M or Me snooper236updates its cache state differently depending upon whether the M or Me snooper236is local (i.e., within the same coherency domain) as the requesting L2 cache230as indicated by the scope indicator in the global bus read operation. In either case, the snooper236in the affirming L2 cache230may initiate transmission of the requested memory block to the requesting L2 cache230prior to receipt of the CR (i.e., provides “early” data), and upon receipt, the master232in the requesting L2 cache230places the requested memory block in its L2 cache array300in the Sr state (blocks1481and1482). However, the snooper236in the affirming L2 cache230updates the state of the requested memory block from M to T or from Me to Te if the snooper236is not local to the requesting L2 cache230(block1481) and updates the state of the requesting memory block from M to Tn or from Me to Ten if the snooper236is local (block1482). The process then returns toFIG. 9Athrough page connector N and ends with distributed response logic210generating a CR indicating “success”, as depicted at block1408.

If a snooper236of an L2 cache230affirms the global bus read operation with a partial response indicating that the L2 cache230holds the requested memory block in any the T, Tn, Te or Ten states (generically designated in block1410as Tx) and an Sr′ snooper236also affirms the bus read operation (block1412), the process passes through page connector M to block1492. Block1492indicates that the affirming Tx snooper236updates the state of the requested memory block differently depending upon whether the scope indicator of the global bus read operation indicated that the snooper236is within the coherency domain of the requesting L2 cache230. In either case, the Sr′ snooper236updates the state of the requested memory block to S and initiates transmission of the requested memory block to the requesting L2 cache230prior to receipt of the CR (blocks1494and1495). Upon receipt, the master232in the requesting L2 cache230places the requested memory block in L2 cache array300in the Sr state (blocks1494and1495). In addition, the Tx snooper236updates the state of the requested memory block, if necessary, from Tn to T or from Ten to Te if the snooper236is not local to the requesting L2 cache230(block1494), but leaves the state of the requested memory block unchanged if the Tx snooper236is local to the requesting L2 cache (block1495). The process then returns toFIG. 9Athrough page connector N and ends with distributed response logic210generating a CR indicating “success”, as depicted at block1408.

If the complex of partial responses includes a Tx snooper236affirming the global bus read operation (block1410), no Sr′ snooper236affirming the bus read operation (block1412), and a snooper236providing an partial response (e.g., a type of retry) indicating that an Sr′ snooper236may exist in the local data delivery domain but did not affirm the global bus read operation, the process passes through page connector L to block1488ofFIG. 9B. Block1488indicates that the affirming Tx snooper236updates the state of the requested memory block differently depending upon whether the scope indicator of the global bus read operation indicated that the snooper236is within the coherency domain of the requesting L2 cache230. In either case, the Tx snooper236that affirmed the global bus read operation initiates transmission of the requested memory block to the requesting L2 cache230after receipt of the CR (blocks1489and1490). Upon receipt, the master232in the requesting L2 cache230places the requested memory block in L2 cache directory300in the S state (since an Sr′ snooper236may be hidden within the local domain the requesting cache236and only one Sr′ snooper236is permitted in each domain for the requested memory block). In addition, the Tx snooper236updates the state of the requested memory block, if necessary, from Tn to T or from Ten to Te if the snooper236is not local to the requesting L2 cache230(block1489), but leaves the state of the requested memory block unchanged if the Tx snooper236is local to the requesting L2 cache (block1490). The process then returns toFIG. 9Athrough page connector N and ends with distributed response logic210generating a CR indicating “success”, as depicted at block1408.

If the complex of partial responses includes a Tx snooper236affirming the global bus read operation, no Sr′ snooper236affirming the bus read operation, and no snooper236providing a partial response that may hide a Sr′ snooper236, the process passes through page connector K to block1484ofFIG. 9B. Block1484indicates that the affirming Tx snooper236updates the state of the requested memory block differently depending upon whether the scope indicator of the global bus read operation indicated that the snooper236is within the coherency domain of the requesting L2 cache230. In either case, the Tx snooper236that affirmed the global bus read operation initiates transmission of the requested memory block to the requesting L2 cache230after receipt of the CR (i.e., provides “late” data), the master232in the requesting L2 cache230places the requested memory block in its L2 cache array300in the Sr state (since no other Sr′ snooper236exists for the requested memory block in the local domain). In addition, the Tx snooper236updates the state of the requested memory block, if necessary, from Tn to T or from Ten to Te if the snooper236is not local to the requesting L2 cache230(block1485), but leaves the state of the requested memory block unchanged if the Tx snooper236is local to the requesting L2 cache (block1486). The process then returns toFIG. 9Athrough page connector N and ends with distributed response logic210generating a CR indicating “success”, as depicted at block1408.

Referring now to block1420, if no M, Me, or Tx snooper236affirms the global bus read operation, but an Sr′ snooper236affirms the global bus read operation, the global bus read operation is serviced in accordance with block1422. In particular, the Sr′ snooper236that affirmed the global bus read operation initiates transmission of the requested memory block to the requesting L2 cache230prior to receipt of CR and updates the state of the requested memory block in its L2 cache directory302to the S state. The master232in the requesting L2 cache230places the requested memory block in L2 cache array300in the Sr state. The process ends with distributed response logic210generating a CR indicating “success”, as depicted at block1408.

Turning now to block1430, if no M, Me, Tx or Sr′ snooper236affirms the global bus read operation, and further, if no snooper222provides a partial response indicating that it is responsible (i.e., the LPC) for the requested memory block, an error occurs that halts processing as shown at block1432because every memory block is required to have an LPC.

Referring now to block1440, if a snooper222provides a partial response indicating that it is responsible (i.e., the LPC) for the requested memory block but does not affirm the global bus read operation, response logic210generates a CR indicating “retry”, as depicted at block1450. As indicated by decision block1442, response logic210similarly generates a “retry” CR at block1450if a memory controller snooper222affirms the global bus read operation and an L2 cache snooper236provides a partial response indicating that it may hold the requested memory block in one of the M, Me, or Tx states but cannot affirm the global bus read operation. In each of these cases, response logic210generates a “retry” CR to cause the operation to be reissued because one of the possibly hidden snoopers236may be required to source the requested memory block to the requesting L2 cache230.

With reference now to block1444, if no M, Me, Tx or Sr′ snooper236affirms the bus read operation, no M, Me, or Tx snooper236is possibly hidden, and a memory controller snooper222affirms the global bus read operation, the snooper222affirming the global bus read operation provides the requested memory block and the associated domain indicator504to the requesting L2 cache230in response to the CR, as depicted at each of blocks1452and1454. As shown at blocks1444,1446,1452,1454and1456, the master232of the requesting L2 cache230handles the requested memory block in accordance with the partial responses compiled into the “success” CR represented at block1408. In particular, if the CR indicates that no Sr′ or S′ snooper236is possibly hidden, the requesting L2 cache230holds the requested memory block in the Me state (block1456); the requesting L2 cache230holds the requested memory block in the Sr state if no Sr′ snooper236is possibly hidden and a S′ snooper236is possibly hidden; and the requesting L2 cache230holds the requested memory block in the S state if an Sr′ snooper236is possibly hidden.

In response to the CR, the memory controller snooper222that is the LPC for the requested memory block then determines whether to update the domain indicator for the requested memory block, as illustrated at blocks1460,1462,1470,1472and1474. If the CR indicates that the new cache state for the requested memory block is Me, the LPC snooper222determines whether it is within the same domain as the requesting L2 cache230(block1460), for example, by reference to the scope indicator in the global bus read operation, and whether the domain indicator504indicates local or global (blocks1460and1472). If the LPC is within the same domain as the requesting L2 cache230(block1460), the LPC snooper222sets the domain indicator504to “local” if it is reset to “global” (block1462and1464). If the LPC is not within the same domain as the requesting L2 cache230(block1460), the LPC snooper222resets the domain indicator504to “global” if it is set to “local” (block1472and1474).

If the CR indicates that the new cache state for the requested memory block is S or Sr, the LPC snooper222similarly determines whether it is within the same domain as the requesting L2 cache230(block1470) and whether the domain indicator504indicates local or global (block1472). If the LPC is within the same domain as the requesting L2 cache230(block1470), no update to the domain indicator504is required. If, however, the LPC is not within the same domain as the requesting L2 cache230(block1470), the LPC snooper222resets the domain indicator504to “global” if it is set to “local” (block1472and1474). Thus, LPC snooper222updates the domain indicator504, if required, in response to receipt of the CR.

Referring now toFIG. 10, there is depicted a high level logical flowchart of an exemplary method of performing a local bus RWITM operation in a data processing system in accordance with the present invention. The process begins at block1500, for example, with a master232of an L2 cache230issuing a local bus RWITM operation its local interconnect114at block748ofFIG. 7A. The various partial responses that snoopers222,236may provide to distributed response logic210are represented inFIG. 10by the outcomes of decision blocks1502,1510,1512,1520,1524,1530,1534,1540and1544. These partial responses in turn determine the CR for the local bus RWITM operation.

If a snooper236affirms the local bus RWITM operation with a partial response indicating that the L2 cache230containing the snooper236holds the requested memory block in either the M or Me state as shown at block1502, the process proceeds from block1502to block1504. Block1504indicates the operations of the requesting L2 cache230and the affirming L2 cache230in response to the local bus RWITM operation. In particular, the snooper236in the affirming L2 cache230updates the cache state of the requested memory block from the M or Me state to the In state and may initiate transmission of the requested memory block to the requesting L2 cache230prior to receipt of the CR (i.e., provides “early” data). Upon receipt of the requested memory block, the master232in the requesting L2 cache230places the requested memory block in its L2 cache array300in the M state. The process ends with distributed response logic210generating a CR indicating “success”, as depicted at block1506.

As indicated parenthetically within block1504, the snooper236in the affirming L2 cache230preferably updates the coherency state of the target memory block from the M or Me state to the I state (instead of the “tagged” In state) in response to receipt of a “possible intervening source” indication in conjunction with the local bus RWITM operation. The “possible intervening source” indication indicates that the requesting L2 cache230is coupled to the affirming L2 cache230by a private network connection270. The “possible intervening source” indication may be transmitted via interconnect fabric114,110as part of the bus operation or via private network connection270and may comprise, for example, a 1-bit signal or a multi-bit processor core identifier or cache identifier. By updating the coherency state to I instead of In, the snooping L2 cache230, in the event that it receives a subsequent CPU read request for the same target memory block from its associated processor core200while the coherency state with respect to the snooping L2 cache230for that memory block is I, will advantageously request the memory block from the requesting L2 cache230via L2.1 intervention via private network connection270in accordance with blocks650and652ofFIG. 6Aprior to issuing a bus read operation on interconnect fabric114,110. In this manner, the access latency for “hot” memory blocks subject to frequent read access by different processor cores200is advantageously reduced. Although not described in detail below, similar updates to the I state rather than to the In state for the special case of the requesting and affirming L2 caches230being coupled by a private network connection are also preferably made for exclusive memory access operations, as illustrated, for example, at blocks1514,1516,1532,1542, and1546ofFIG. 10, blocks1606,1622,1624ofFIG. 11A, blocks1640,1642,1666,1672ofFIG. 11B, blocks1703,1712,1721,1730,1742ofFIG. 12, and blocks1803,1816, and1843ofFIG. 13.

Referring to block1510, if a snooper236affirms the local bus RWITM operation with a partial response indicating that the L2 cache230containing the snooper236holds the requested memory block in any of the T, Tn, Te or Ten states (generically designated as Tx inFIG. 10) and no Sr′ snooper236affirms the local bus RWITM operation (block1512), the process passes to block1514. Block1514represents the Tx snooper236that affirmed the local bus RWITM operation initiating transmission of the requested memory block to the requesting L2 cache230in response to receipt of the CR from response logic210. In response to receipt of the requested memory block, the requesting L2 cache230holds the requested memory block in the M state. All valid affirming snoopers236update their respective cache states for the requested memory block to In.

If the complex of partial responses includes a Tx snooper236and an Sr′ snooper236both affirming the local bus RWITM operation (blocks1510and1512), the process passes to block1516. Block1516represents the Sr′ snooper236that affirmed the local bus RWITM operation initiating transmission of the requested memory block to the requesting L2 cache230prior to receipt of the CR provided by response logic210. In response to receipt of the requested memory block, the requesting L2 cache230holds the requested memory block in the M state. All valid affirming snoopers236update their respective cache states for the requested memory block to In.

As shown at block1517, in either of the cases represented by blocks1514and1516, response logic210generates a CR dependent upon whether the Tx affirming snooper236held the requested memory block in one of the T/Te states or the Tn/Ten states. If the Tx snooper236was T or Te, response logic210generates a CR indicating “cleanup”, as shown at block1518. If, however, the Tx snooper236was Tn or Ten, response logic210advantageously restricts the scope of the cleanup operations to the local domain by generating a CR indicating “local cleanup”, as shown at block1556. The limited scope of cleanup operations is permitted because the existence of a Tn or Ten coherency state guarantees that no remote cache holds the requested memory block, meaning that coherency can be maintained without a wider broadcast of the local bus RWITM operation or attendant bus kill operations.

The local bus RWITM operation cannot be serviced by a L2 cache snooper236without retry if no M, Me, or Tx snooper236(i.e., HPC) affirms the local bus RWITM operation to signify that it can mediate the data transfer. Accordingly, if an Sr′ snooper236affirms the local bus RWITM operation and supplies early data to the requesting L2 cache230as shown at block1520, the master232of the requesting L2 cache230discards the data provided by the Sr′ snooper236, as depicted at block1522.

Block1524represents the differences in handling the local bus RWITM operation depending upon whether a snooper236of an L2 cache230provides a partial response affirming the local bus RWITM operation and indicating that the L2 cache230holds the address tag of the requested memory block in the Ig state. If so, any valid affirming snooper236(i.e., not Ig snoopers236) invalidates the relevant cache entry (block1532). If no M, Me, or Tx snooper236is possibly hidden by an incomplete partial response (block1534), distributed response logic210provides a “go global” CR, as depicted at block1536. If, on the other hand, an Ig snooper236affirms the local bus RWITM operation and the complex of partial responses indicates an M, Me, or Tx snooper236is possibly hidden, response logic210generates a “retry” CR, as depicted at block1538. Thus, the affirmance of the local bus RWITM operation by an Ig snooper236will cause the operation to be reissued as a global operation if no HPC is possibly hidden in the local coherency domain.

If an Ig snooper236does not affirm the local bus RWITM operation at block1524, the local bus RWITM operation is handled in accordance with block1530and following blocks. In particular, if no memory controller snooper222provides a partial response indicating that it is responsible (i.e., the LPC) for the requested memory block (block1530), each valid affirming snooper236updates the requested memory block in its respective L2 cache directory302to the In coherency state (block1532). The CR generated by response logic210depends upon whether any partial responses indicate that an M, Me, or Tx snooper236may be hidden (block1534). That is, if no M, Me, or Tx snooper236may be hidden, response logic210generates a “go global” CR at block1536to inform the master232that the local bus RWITM operation must be reissued as a global RWITM operation. On the other hand, if an M, Me, or Tx snooper236(i.e., an HPC) for the requested memory block may be hidden, response logic210generates a CR indicating “retry”, as depicted at block1538, because the operation may be serviced locally if retried.

Similarly, valid affirming snoopers236update their respective copies of the requested memory block to the In coherency state (block1542), and response logic210provides a “retry” CR for the local bus RWITM operation (block1538) if no M, Me, or Tx snooper236affirms the local bus RWITM operation and a snooper222provides a partial response indicating that it is the LPC but does not affirm the local bus RWITM operation. A “retry” CR is also generated at block1538, and snoopers236invalidate their respective copies of the requested memory block (block1542) if no M, Me, or Tx snooper236affirmed the local bus RWTIM operation (blocks1502,1510), a snooper222affirmed the local bus RWITM operation (block1540), and an M, Me, Tx or Ig snooper236may be possibly hidden (block1544).

As shown at block1546, if no M, Me, or Tx snooper236affirms the local bus RWITM operation or is possibly hidden and the LPC snooper222affirms the local bus RWITM operation, each valid affirming snooper236updates its respective copy of the requested memory block to the In coherency state. In addition, the LPC snooper222provides the requested memory block and associated domain indicator504to the requesting L2 cache230in response to receipt of the CR from response logic210. The master232of the requesting L2 cache230handles the data in accordance with the domain indicator504. In particular, if the domain indicator504is reset to “global”, meaning that a remote cached copy may exist that renders stale the data received from the LPC snooper222, master232discards the data received from the LPC snooper222, maintains an invalid coherency state with respect to the requested memory block (block1552), and interprets the CR provided by response logic210as “go global” (block1536). If, on the other hand, the domain indicator504is set to “local”, meaning that no remote cached copy of the requested memory block renders the data received from the LPC snooper222potentially stale, the master232places the requested memory block and domain indicator504in its L2 cache array300and sets the associated state field306to M (block1546). If the partial responses and hence the CR indicate an S′ or Sr′ snooper236is possibly hidden (block1554), the CR indicates local “cleanup” (block1556), meaning that the requesting L2 cache230must invalidate the other valid locally cached copies of the requested memory block, if any, through one or more local bus kill operations. If no such S′ or Sr′ snoopers236are possibly hidden by incomplete partial responses, the CR indicates “success”, as depicted at block1506.

It will be further appreciated that in some embodiments, the master of the local bus RWITM operation may speculatively perform a local cleanup as shown at block1556prior to receipt of the domain indicator3004from the LPC (block1550). In this manner, the latency associated with data delivery from the LPC can be masked by the one or more local bus kill operations involved in the local cleanup operations.

With reference now toFIGS. 11A–11B, there is illustrated a high level logical flowchart of an exemplary method of performing a global bus RWITM operation in a data processing system in accordance with the present invention. As shown, the process begins at block1600in response to the master232of a requesting L2 cache230issuing a global bus RWITM operation, for example, at block754ofFIG. 7A. If a snooper236affirms the global bus RWITM operation with a partial response indicating that the L2 cache230containing the snooper236holds the requested memory block in the M or Me state as shown at block1602, the M or Me snooper236provides early data to the requesting master232, which holds the requested memory block in the M state (block1604or block1606). Response logic210generates a CR indicating “success”, as shown at block1607. In addition, the M or Me snooper236updates its cache state to either In or Ig depending upon whether or not it is local to (i.e., in the same coherency domain as) the requesting master232(block1603). If the M or Me snooper236determines it belongs to the same coherency domain as the requesting master232, for example, by reference to the scope indicator in the bus operation, the M or Me snooper236updates its cache state for the requested memory block to In (block1606). On the other hand, if the M or Me snooper236determines it does not belong to the same coherency domain as the requesting master232, the M or Me snooper236updates its cache state for the requested memory block to Ig in order to maintain a cached domain indicator for the requested memory block in its coherency domain (block1604). Consequently, no retry-push is required in response to the global bus RWITM operation in order to update the domain indicator504in the LPC system memory108.

Turning now to block1610, if a snooper236affirms the global bus RWITM operation with a partial response indicating that the L2 cache230containing the snooper236holds the requested memory block in either the Tn or Ten state, the process passes to block1612, which represents the Tn or Ten snooper236determining whether or not it is local to the requesting master232. If so, the global bus RWITM operation is handled in accordance with blocks1614and following blocks, which are described below. If, however, the Tn or Ten snooper236affirming the global bus RWITM operation determines that it is not local to the requesting master232, the global bus RWITM operation is serviced in accordance with either block1618or block1620, depending upon whether or not an Sr′ snooper236also affirmed the global bus RWITM operation.

As shown at blocks1618, if an Sr′ snooper236affirmed the global bus RWITM operation, the Sr′ snooper236provides early data to the requesting master232, and the Tn or Ten snooper236that affirmed the global bus RWITM operation updates its cache state for the entry containing the requested memory block to Ig. In response to receipt of the requested memory block, the requesting L2 cache230holds the requested memory block in the M state. In addition, any valid affirming snooper236(i.e., not an Ig snooper236) other than the Tn or Ten snooper236updates its respective cache state for the requested memory block to I. Alternatively, as depicted at block1620, if an Sr′ snooper236does not affirm the global bus RWITM operation, the Tn or Ten snooper236provides late data in response to receipt of the CR. In response to receipt of the requested memory block, the requesting L2 cache230holds the requested memory block in the M state. In addition, the Tn or Ten snooper236updates its cache state to Ig, and any other valid affirming snooper236(i.e., not an Ig snooper236) updates its respective cache state for the requested memory block to I. Thus, if a remote Tn or Ten snooper236affirms the global bus RWITM operation, the affirming Tn or Ten snooper236enters the Ig state in order to maintain a cached domain indicator for the requested memory block in its coherency domain. Consequently, no retry-push is required in response to the global bus RWITM operation in order to update the domain indicator504in the LPC system memory108.

In either of the cases represented by blocks1618and1620, response logic210generates a CR dependent upon whether an S′ or Sr′ snooper236is possibly hidden and thus unable to invalidate its copy of the requested memory block in response to snooping the global bus RWITM operation. If response logic210makes a determination at block1626based upon the partial responses to the global bus RWITM operation that an S′ or Sr′ snooper236is possibly hidden, response logic210generates a CR indicating “cleanup”, as shown at block1628. Alternatively, if response logic210determines that no S′ or Sr′ snooper236is possibly hidden, response logic210generates a CR indicating “success”, as depicted at block1607.

Returning to block1612, if a Tn or Ten snooper236that is local to the requesting master232affirms the global bus RWITM operation, the global bus RWITM operation is serviced in accordance with either block1624or block1622, depending upon whether or not an Sr′ snooper236also affirmed the global bus RWITM operation.

As shown at block1624, if an Sr′ snooper236affirmed the global bus RWITM operation, the Sr′ snooper236provides early data to the requesting master232, and each valid snooper236that affirmed the global bus RWITM operation updates its respective cache state for the entry containing the requested memory block to In. In response to receipt of the requested memory block, the requesting L2 cache230holds the requested memory block in the M state. Alternatively, as depicted at block1622, if an Sr′ snooper236does not affirm the global bus RWITM operation, the Tn or Ten snooper236provides late data in response to receipt of the CR. In response to receipt of the requested memory block, the requesting L2 cache230holds the requested memory block in the M state. In addition, each valid affirming snooper236updates its respective cache state for the requested memory block to In.

In either of the cases represented by blocks1624and1622, response logic210generates a CR dependent upon whether an S′ or Sr′ snooper236is possibly hidden and thus unable to invalidate its copy of the requested memory block in response to snooping the global bus RWITM operation. If response logic210makes a determination at block1625based upon the partial responses to the global bus RWITM operation that an S′ or Sr′ snooper236is possibly hidden, response logic210generates a CR indicating “local cleanup”, as shown at block1632. Thus, the scope of the bus kill operations required to ensure coherency are advantageously limited to the local coherency domain containing the requesting L2 cache230and the (former) Tn or Ten snooper236. Alternatively, if response logic210determines that no S′ or Sr′ snooper236is possibly hidden, response logic210generates a CR indicating “success”, as depicted at block1607.

Following page connector0to block1630ofFIG. 11B, if a T or Te snooper236affirms the global bus RWITM operation, the process passes to block1632, which represents the T or Te snooper236determining whether or not it is local to the requesting master232. If so, the global bus RWITM operation is handled in accordance with blocks1638and following blocks, which are described in detail below. If, however, the T or Te snooper236affirming the global bus RWITM operation determines that it is not local to the requesting master232, the global bus RWITM operation is serviced in accordance with either block1636or block1635, depending upon whether or not an Sr′ snooper236affirmed the global bus RWITM operation.

As shown at blocks1635, if an Sr′ snooper236affirmed the global bus RWITM operation, the Sr′ snooper236provides early data to the requesting master232, and the T or Te snooper236that affirmed the global bus RWITM operation updates its cache state for the entry containing the requested memory block to Ig. In response to receipt of the requested memory block, the requesting L2 cache230holds the requested memory block in the M state. In addition, any valid affirming snooper236other than the T or Te snooper236updates its respective cache state for the requested memory block to I. Alternatively, as depicted at block1636, if an Sr′ snooper236does not affirm the global bus RWITM operation, the T or Te snooper236provides late data in response to receipt of a CR. In response to receipt of the requested memory block, the requesting L2 cache230holds the requested memory block in the M state. In addition, the T or Te snooper236updates its cache state to Ig, and any other valid affirming snooper236updates its respective cache state for the requested memory block to I. Thus, if a remote T or Te snooper236affirms the global bus RWITM operation, the affirming T or Te snooper236enters the Ig state in order to maintain a cached domain indicator for the requested memory block in its coherency domain. Consequently, no retry-push is required in response to the global bus RWITM operation in order to update the domain indicator504in the LPC system memory108.

In either of the cases represented by block1635or block1636, response logic210generates a CR dependent upon whether an S′ or Sr′ snooper236is possibly hidden and thus unable to invalidate its copy of the requested memory block in response to snooping the global bus RWITM operation. If response logic210makes a determination at block1644based upon the partial responses to the bus RWITM operation that an S′ or Sr′ snooper236is possibly hidden, response logic210generates a CR indicating “cleanup”, as shown at block1626. Alternatively, if response logic210determines that no S′ or Sr′ snooper236is possibly hidden, response logic210generates a CR indicating “success”, as depicted at block1607.

Returning to blocks1632and1638, if the T or Te snooper236determines at block3412that it is local the requesting master232, the global bus RWITM operation is serviced in accordance with either block1640or block1642, depending upon whether an Sr′ snooper236also affirmed the global bus RWITM operation. That is, as shown at block1640, if no Sr′ snooper236affirms the global bus RWITM operation (block1638), the T or Te snooper236that affirmed the global bus RWITM operation initiates transmission of the requested memory block to the requesting L2 cache230in response to receipt of the CR (i.e., provides “late” data). In response to receipt of the requested memory block, the requesting L2 cache230holds the requested memory block in the M state. In addition, each valid affirming snooper236updates its respective coherency state for the requested memory block to In. Alternatively, as depicted at block1642, if an Sr′ snooper236affirms the global bus RWITM operation (block1638), the Sr′ snooper236initiates transmission of the requested memory block to the requesting L2 cache230prior to receipt of the CR (i.e., provides “early” data). In response to receipt of the requested memory block, the requesting L2 cache230holds the requested memory block in the M state. In addition, each valid affirming snooper236within the same coherency domain as the requesting master232updates its respective coherency state for the requested memory block to In. Following either block1640or block1642, the process passes to block1644, which has been described.

Referring now to block1650, if no M, Me, or Tx snooper236affirms the global bus RWITM operation, and further, if no snooper222provides a partial response indicating that it is responsible (i.e., the LPC) for the requested memory block, an error occurs causing processing to halt, as depicted at block1652. If, on the other hand, no M, Me, or Tx snooper236affirms the bus RWITM operation and a snooper222provides a partial response indicating that it is responsible (i.e., the LPC) for the requested memory block but does not affirm the bus RWITM operation (block1660), each valid affirming snooper236, if any, updates the coherency state of its respective copy of the requested memory block, either to the In coherency state if the affirming snooper236is within the same coherency domain as the master232or to the I coherency state otherwise (block1672). Response logic210also generates a CR indicating “retry”, as depicted at block1674. In addition, data provided by an Sr′ snooper236affirming the global bus RWITM operation, if any, is discarded by the master232(blocks1668and1670).

As indicated by decision block1662, affirming snoopers236similarly update the coherency states of their respective copies of the requested memory block at block1672and response logic210generates a “retry” CR at block1674if a memory controller snooper222affirms the global bus RWITM operation (block1660) and an L2 cache snooper236provides a partial response indicating that it may hold the requested memory block in one of the M, Me, or Tx states but cannot affirm the global bus RWITM operation (block1662).

With reference now to block1664, if no M, Me, or Tx snooper236affirms the global bus RWITM operation or is possibly hidden, a snooper222affirms the global bus RWITM operation, and a Sr′ snooper236affirms the global bus RWITM operation, the global bus RWITM operation is serviced in accordance with block1642and following blocks, which are described above. Assuming these same conditions except for the absence of an Sr′ snooper236affirming the global bus RWITM operation, the global bus RWITM operation is serviced in accordance with block1666. In particular, in response to the CR, the LPC snooper222provides the requested memory block to the requesting L2 cache230, which obtains the requested memory block in the M state. In addition, each valid affirming snooper236, if any, updates the coherency state of its respective copy of the requested memory block, either to the In coherency state if the affirming snooper236is within the same coherency domain as the master232or to the I coherency state otherwise.

Following block1666, the process passes to blocks1680–1686, which collectively represent the LPC snooper222determining whether or not to update the domain indicator504for the requested memory block based upon whether the LPC snooper222is local to the requesting master232(block1680) and the present state of the domain indicator (blocks1682and1684). If the LPC snooper222is local to the requesting L2 cache230and the domain indicator504in system memory108is set to indicate “local”, no update is required, and the process passes through page connector P to block1625ofFIG. 11A, which has been described. On the other hand, LPC snooper222changes the state of the domain indicator504at block1686if LPC snooper222is local to the requesting master232and domain indicator504is reset to indicate “global” or if LPC snooper222is not local to the requesting master232and domain indicator504is reset to indicate “local”.

If the partial responses indicate an S′ or Sr′ snooper236is possibly hidden (block1644), the requesting L2 cache230receives a “cleanup” CR at block1628, indicating that it must invalidate any other valid cached copies of the requested memory block. If no S′ or Sr′ snoopers236are possibly hidden by incomplete partial responses, response logic210generates a “success” CR, as depicted at block1607.

With reference now toFIG. 12, there is illustrated a high level logical flowchart of an exemplary method of performing a local bus DClaim operation in a data processing system in accordance with the present invention. As shown, the process begins at block1700, for example, with a master232issuing a local bus DClaim operation on a local interconnect114at block732ofFIG. 7A. The various partial responses that snoopers236may provide to distributed response logic210in response to the local bus DClaim operation are represented inFIG. 12by the outcomes of decision blocks1702,1710,1720,1740, and1744. These partial responses in turn determine what CR response logic210generates for the local bus DClaim operation.

As shown at block1702, if any snooper236issues a partial response downgrading the local bus DClaim operation to a bus RWITM operation as illustrated, for example, at blocks748and754ofFIG. 7A, each other affirming snooper236holding the requested memory block in a valid state updates the coherency state of its respective copy of the requested memory block to the In state, as shown at block1703. In response to the local bus DClaim operation and the partial responses, distributed response logic210generates a CR indicating “downgrade”, as shown at block1704. In response to this CR, the master232of the local bus DClaim operation must next attempt to gain ownership of the requested memory block utilizing a local bus RWITM operation, as depicted at block748ofFIG. 7A.

If a snooper236affirms the local bus DClaim operation with a partial response indicating that the L2 cache230containing the snooper236holds the requested memory block in either the T or Te state as shown at block1710, the process passes to block1712. Because no data transfer is required in response to a bus DClaim operation, block1712indicates that the master232in the requesting L2 cache230updates the cache state of the requested memory block in L2 cache directory302to the M state. In addition, each valid affirming snooper236, if any, updates the coherency state of its respective copy of the requested memory block to the In coherency state. As shown at block1718, distributed response logic210generates a CR indicating “cleanup”, meaning that the requesting L2 cache230must issue one or more bus kill operations to invalidate copies of the requested memory block, if any, held outside of the local coherency domain.

As illustrated at block1740, if a Tn or Ten snooper236affirms the local bus DClaim operation, the process passes to block1742. Because no data transfer is required in response to a bus DClaim operation, block1742indicates that the master232in the requesting L2 cache230updates the cache state of the requested memory block in L2 cache directory302to the M state. Each valid affirming snooper236, if any, updates the coherency state for the requested memory block to In. As shown at block1744, distributed response logic210generates a CR that is dependent upon whether the partial responses received by response logic210indicate that an Sr′ or S′ snooper236may be possibly hidden. If not, distributed response logic210generates a response indicating “success”, as shown at block1746, because the presence of the Tn or Ten coherency state guarantees that no L2 cache230outside of the local coherency domain holds a copy of the requested memory block. If the partial responses indicate that an Sr′ or S′ snooper236may be possibly hidden, response logic210generates a CR indicating “local cleanup”, as shown at block1748. Only local cleanup operations are required because the Tn or Ten coherency state again guarantees that no L2 cache230outside of the local coherency domain holds a valid copy of the requested memory block.

Turning now to block1720, if no snooper downgrades the local bus DClaim operation (block1702), no Tx snooper236affirms the local bus DClaim operation (blocks1710and1740), and further, and a snooper236provides a partial response indicating that it may hold the requested memory block in a Tx state but cannot affirm the local bus DClaim operation, each valid affirming snoopers236updates its respective coherency state for the requested memory block to the In state (block1721). In addition, response logic210generates a CR indicating “retry”, as depicted at block1722. In response to the “retry” CR, the requesting master232may reissue the bus DClaim operation as either a local or global operation, as explained above with reference to block736ofFIG. 7A. If, however, no snooper downgrades the local bus DClaim operation (block1702), no Tx snooper236affirms the bus DClaim operation or is possibly hidden (blocks1702,1710,1740, and1720), response logic210provides a “go global” CR, as shown at block1732, and each affirming snooper236, if any, having a valid copy of the requested memory block updates the coherency state of its respective copy of the requested memory block to In, as shown at block1730. In response to the “go global” CR, the master232reissues the bus DClaim operation as a global operation, as depicted at block740ofFIG. 7A.

Referring now toFIG. 13, there is depicted a high level logical flowchart of an exemplary method of performing a global bus DClaim operation in a data processing system in accordance with the present invention. The process begins at block1800, for example, with a master232of an L2 cache230issuing a global bus DClaim operation on system interconnect110at block740ofFIG. 7A. The various partial responses that snoopers222,236may provide to distributed response logic210in response to the global bus DClaim operation are represented inFIG. 13by the outcomes of decision blocks1802,1810,1818,1830,1840,1842and1819. These partial responses in turn determine what CR response logic210generates for the global bus DClaim operation.

As shown at block1802, if any snooper236issues a partial response downgrading the global bus DClaim operation to a bus RWITM operation, each valid affirming snooper236other than the downgrading snooper236updates the coherency state of its copy of the requested memory block, as shown at block1803. That is, each valid affirming snooper236, if any, updates the coherency state of its respective copy of the requested memory block to the In coherency state if the affirming snooper236is within the same coherency domain as the master232and to the I coherency state otherwise. In addition, distributed response logic210generates a CR indicating “downgrade”, as shown at block1804. In response to this CR, the master232of the global bus DClaim operation must next attempt to gain ownership of the requested memory block utilizing a bus RWITM operation, as depicted at blocks748and754ofFIG. 7A.

If a Tx (e.g., T, Te, Tn, or Ten) snooper236affirms the global bus DClaim operation as shown at block1810, the process passes to block1812. Block1812depicts the Tx snooper236determining whether it is local to the requesting master232. If not, the Tx snooper236updates the state of its relevant entry to Ig to maintain a cached domain indicator for the requested memory block as shown at block1814. In addition, the requesting master232updates the coherency state of its copy of the requested memory block to M, and each valid affirming snooper236other than the Tx snooper236updates its coherency state for the requested memory block to I (block1814).

Returning to block1812, if the Tx snooper236determines that it is local to the requesting master232, the global bus DClaim operation is handled in accordance with block1816. In particular, the master232in the requesting L2 cache230updates the state of its copy of the requested memory block to the M state. In addition, each valid affirming snooper236, if any, updates the coherency state of its respective copy of the requested memory block to the In coherency state if the affirming snooper236is within the same coherency domain as the master232and to the I coherency state otherwise.

As shown at blocks1818and1822, if the partial responses indicate that no S′ or Sr′ snooper236is possibly hidden, the process ends with distributed response logic210generating a CR indicating “success” (block1822). If, on the other hand, a determination is made at block1818that at least one partial response indicating the presence of a possibly hidden S′ or Sr′ snooper236was given in response to the global bus DClaim operation, some type of cleanup operation will be required. If the affirming Tx snooper236is within the same coherency domain as the requesting master232and, prior to the operation, was in one of the Te and Ten states, distributed response logic210generates a CR indicating “local cleanup” (block1824), meaning that the requesting L2 cache230must issue one or more local bus kill operations to invalidate the requested memory block in any such hidden S′ or Sr′ snooper236. If the affirming Tx snooper236is not within the same coherency domain as the requesting master232or the affirming Tx snooper236was, prior to the operation, in one of the T or Te coherency states, global cleanup is required, and response logic210generates a CR indicating “cleanup” (block1820). Thus, the presence of a Tn or Ten coherency state can again be utilized to limit the scope of bus kill operations.

Turning now to block1830, if no Tx snooper236affirms the global bus DClaim operation, and further, if no snooper222provides a partial response indicating that it is responsible (i.e., the LPC) for the requested memory block, an error occurs causing processing to halt, as depicted at block1832. If, on the other hand, no Tx snooper236affirms the global bus DClaim operation and a snooper222provides a partial response indicating that it is responsible (i.e., the LPC) for the requested memory block but does not affirm the global bus DClaim operation (block1840), each valid affirming snooper236, if any, updates the coherency state of its respective copy of the requested memory block to the In coherency state if the affirming snooper236is within the same coherency domain as the master232and to the I coherency state otherwise (block1843). In addition, response logic210generates a CR indicating “retry”, as depicted at block1844. As indicated by decision block1842, each valid affirming snooper also updates the coherency state of its respective copy of the requested memory block at block1843, and response logic210similarly generates a “retry” CR at block1844if a memory controller snooper222affirms the bus DClaim operation (block1840) and an Tx snooper236may be possibly hidden (block1842).

As depicted at block1842, if no Tx snooper236affirms the global bus DClaim operation or is possibly hidden and a snooper222affirms the global bus DClaim operation, the global bus DClaim operation is serviced in accordance with block1816, which is described above.

As has been described, the present invention provides a cache memory, processing unit, data processing system and method in which a snooping cache memory updates a directory entry for a target memory block of an exclusive memory access operation to a selected one of multiple invalid coherency states based upon whether or not its receives indication that the source of the memory access request is a possible direct intervention source coupled to the snooping cache memory by a private network connection. In this manner, the snooping cache can then accurately determine, in response to a subsequent memory access request, whether or not to request direct intervention of the target memory block via the private network connection prior to broadcasting on a shared interconnect fabric a bus operation requesting the target memory block.

In the particular embodiment described herein, the private network connection270by which one cache may request direct intervention from another cache affiliated with a different processing unit is depicted and described as coupling all caches at a particular hierarchy level within a particular single integrated circuit processing unit. However, in other embodiments within the scope of the present invention, the private cache-to-cache network connection may have a narrower scope, for example, coupling fewer than all caches at a given hierarchy level within a particular integrated circuit processing unit, or may have a broader scope, for example, coupling caches in multiple different integrated circuit processing units within the same MCM.

It will also be appreciated by those skilled in the art that although the present invention has been described with reference to particular exclusive memory access operations (e.g., local and global bus RWITM and local and global bus DClaim operations), the present invention is also applicable to other exclusive memory access operations that force the cache state of the target memory block in affirming caches to a data-invalid state. Such other exclusive memory access operations may include, for example, local and global bus kill operations, local and global bus DCBZ (Data Cache Block Zero) operations, and local and global bus write operations, which are described in detail in the co-pending applications incorporated by reference above.

While the invention has been particularly shown as 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.