Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
2000-12-30
2004-07-13
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S145000
Reexamination Certificate
active
06763434
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates in general to data processing and, in particular, to a data processing system and method for resolving conflicts between memory access requests. Still more particularly, the present invention relates to a data processing system and method for resolving conflicts between requests to modify a cache line in a shared state.
2. Description of the Related Art
A typical symmetric multiprocessor (SMP) data processing system architecture includes a system bus coupled to a plurality of agents, at least one of which (e.g., a memory controller) provides an interface through which a system memory can be accessed. In many data processing system implementations, at least one of the agents, for example, a processor, has one or more associated caches for storing data and/or instructions (hereinafter, both referred to as data) associated with system memory addresses at relatively low access latency as compared to the system memory. Thus, data are available for read and write access by the agents from multiple sources (i.e., caches and system memory) having different associated access latencies.
In data processing systems that cache data, proper system operation depends upon the coordination of accesses satisfied by multiple possible data sources to ensure that read and write accesses to each system memory address are ordered such that agents requesting read access receive correct data. To provide the required coordination of data accesses, a cache coherency protocol is employed, which specifies the possible cache states for data and the caching behavior of the agents. In addition, a bus protocol is employed that, inter alia, specifies the transactions agents issue in response to certain internal operations and the snoop responses agents are required to provide in response to snooping transactions on the system bus. Such snoop responses are compiled to produce a combined response indicating what action, if any, one or more agents are to take in response to the transaction.
Traditional implementations of cache coherency protocols, such as the well-known MESI (Modified, Exclusive, Shared, Invalid) protocol, have required an agent to gain exclusive access to data prior to modifying a locally cached copy, for example, by issuing a read-with-intent-to-modify (RWITM) transaction on the system bus. The RWITM transaction requests that the initiating agent be provided an up-to-date copy of a target cache line and that other agents invalidate their copies of the cache line, if any.
To decrease the latency of stores to cache lines that are held non-exclusively (e.g., in the Shared (S) state), some coherency protocol implementations permit an agent to issue a Dclaim transaction on the system bus to inform other agents that it desires to modify its locally cached copy of a target cache line and that other cached copies of the cache target line, if any, should be invalidated. Thus, a Dclaim differs from a RWITM in that an agent issuing a Dclaim is not requesting a copy of the target cache line. The agent issuing the Dclaim transaction can proceed with its store without violating coherency if it receives a combined response to the Dclaim transaction indicating that all other agents have received the transaction and will invalidate any cached copies of the shared cache line.
In data processing systems that support Dclaim transactions, a central issue that must be addressed by the coherency and bus protocols is how to arbitrate between multiple agents that desire to store to a shared cache line within a relatively small time window. In data processing systems in which transactions on the system bus are strictly ordered (i.e., each transaction issued on the system bus receives a combined response representing the collective response of all the agents prior to the next transaction being issued), conflicts between agents desiring to store to a shared cache line are typically resolved in favor of the agent that first gains ownership of the system bus. That is, the first agent to issue a Dclaim transaction on the system bus receives a combined response indicating that the agent can proceed with its store operation and all other agents must invalidate their copies of the cache line, if any. Thus, all other agents desiring to store to the shared cache line must wait until the store operation completes and then issue a RWITM transaction to acquire the modified cache line for subsequent modification.
The present invention recognizes that arbitration between multiple agents desiring to modify a shared cache line is more complex in data processing systems that pipeline bus transactions (i.e., one or more other transactions may be issued on the system bus prior to the agent issuing an earlier transaction receiving a combined response). The additional complexity arises from the fact that a first agent that desires to modify a shared cache line may be required to provide a snoop response to a second agent's Dclaim transaction prior to receiving a combined response to its own Dclaim transaction. However, without receiving the combined response to its own Dclaim transaction, the first agent does not have enough information to indicate in its snoop response whether the second agent's modifying operation can proceed.
The present invention also recognizes that the coherency and system bus protocols must somehow protect the ownership of a shared cache line by an agent that wins ownership of the shared cache line during arbitration. That is, once the coherency protocol has granted ownership of a shared cache line to a first agent for purposes of modification, the coherency protocol cannot permit another agent to gain ownership of the same cache line until the first agent has completed modification of the cache line and all other agents have agreed to invalidate their cached copies of the line, if any.
SUMMARY OF THE INVENTION
In view of the foregoing, the present invention provides a data processing system and method of communication in a data processing system that arbitrate between conflicting requests to modify data cached in a shared state and that protect ownership of the cache line granted during such arbitration.
According to a preferred embodiment of the present invention, a data processing system includes a plurality of agents coupled to an interconnect that supports pipelined transactions. While data associated with a target address are cached at a first agent among the plurality of agents in a shared state, the first agent issues a transaction on the interconnect. In response to snooping the transaction, a second agent provides a snoop response indicating that the second agent has a pending conflicting store request, and a coherency decision point provides a snoop response granting the first agent ownership of the data. In response to the snoop responses, the first agent is provided with a combined response representing a collective response to the transaction of all of the agents that grants the first agent ownership of the data. In response to the combined response, the first agent is permitted to modify the data. To maintain coherency, the first agent also invalidates other cached copies of the data, if any, preferably by issuing on the interconnect one or more kill transactions specifying the target address associated with the data.
Because the first agent is unaware of its ownership of the data until receipt of the combined response, the coherency decision point protects the grant of ownership to the first agent until the combined response is received by the first agent. Following receipt of the combined response, the first agent can assume responsibility for protecting its ownership of the data until modification of the data is complete, other agents acquiesce to invalidation of their cached copies of the data, if any, and no other agent has an intention to modify a locally cached shared copy of the target cache line. The coherency decision point and the first agent preferably protect the first agent's ownership of the data
Arimilli Ravi Kumar
Dodson John Steven
Guthrie Guy Lynn
Williams Derek Edward
Dillon & Yudell LLP
International Business Machines - Corporation
Kim Matthew
Salys Casimer K.
Thomas Shane M
LandOfFree
Data processing system and method for resolving a conflict... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data processing system and method for resolving a conflict..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data processing system and method for resolving a conflict... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3192046