1. Field of the Invention
This invention relates to computer architectures and, more specifically, to a system and method for ensuring data consistency among a plurality of computer system entities.
2. Background Information
A computer system typically comprises one or more processors linked to a main memory by a bus or other interconnect. In most computer systems, main memory organizes the instructions and data being stored into units typically referred to as “blocks” each of which is separately addressable and may be of a fixed size. Instructions and data are typically moved about the computer system in terms of one or more blocks.
Ordinarily, a processor will retrieve data, e.g., one or more blocks, from main memory, perform some operation on it, and eventually return the results back to main memory. Retrieving data from main memory and providing it to a processor can take significant time especially in terms of the high operating speeds of today's processors. To reduce such latencies as well as to reduce the number of times a processor must access main memory, modern processors and/or processor chipsets include one or more cache memories or caches. A cache is a small, fast memory module that is placed in close proximity to the processor. Many caches are static random access memories (SRAMs), which are faster, but more expensive, than dynamic random access memories (DRAMs), which are often used for main memory. The cache is used to store information, e.g., data or instructions, which the processor is currently using or is likely to use in the near future. There are two basic types of caches: “write-through” caches and “write-back” caches.
With a write-through cache, whenever a processor modifies or updates a piece of data in the processor's cache, main memory's copy of that data is automatically updated. This is accomplished by having the processor write the data back to memory whenever the data is modified or updated. A write-back cache, in contrast, does not automatically send modified or updated data to main memory. Instead, the updated data remains in the cache until some more convenient time, e.g., when the processor is idle, at which point the modified data is written back to memory. The utilization of write-back caches typically improves system performance. In some systems, a write-back or victim buffer is provided in addition to the cache. “Victim data” refers to modified data that is being removed from the processor's cache in order to make room for new data received at the processor. Typically, the data selected for removal from the cache is data the processor is no longer using. The victim buffer stores this modified data which is waiting to be written back to main memory. Modified data in the victim buffer is eventually “victimized”, i.e., written back to main memory, at some convenient time.
Symmetrical Multiprocessor (SMP) Systems
Multiprocessor computing systems, such as symmetrical multiprocessor (SMP) systems, provide a computer environment in which software applications may run on a plurality of processors using a single address space or shared memory abstraction. In a shared memory system, each processor can access any data item without a programmer having to worry about where the data is or how to obtain its value. This frees the programmer to focus on program development rather than on managing partitioned data sets and communicating values.
Cache Coherency
Because more than one processor of the SMP system may request a copy of the same memory block from main memory, cache coherency protocols have been developed to ensure that no processor relies on a memory block that has become stale, typically due to a modification or update performed to the block by some other processor. Many cache coherency protocols associate a state with each cache line. A given memory block, for example, may be in a shared state in which copies of the block may be present in the caches associated with multiple processors. When a memory block is in the shared state, a processor may read from, but not write to, the respective block. To support write operations, a memory block may be in an exclusive state. In this case, the block is owned by a single processor which may write to the cache line. When the processor updates or modifies the block, its copy becomes the most up-to-date version, while corresponding copies of the block at main memory and/or other processor caches become stale.
There are two classes of cache coherency protocols: snooping and directory based. With snooping, the caches monitor or snoop all transactions traversing the shared memory bus, looking for transactions that reference a memory block stored at the cache. If such a transaction is detected, the cache updates the status information for its copy of the memory block based on the snoop transaction. In this way, every cache that has a copy of a given memory block also has a copy of the status information of that block. With a directory based protocol, the state of each block is kept in a single, centralized location in the system, called a directory. Status information is not maintained in the individual caches.
FIG. 1 is a highly schematic illustration of a prior art directory 100. Directory 100 has a plurality of entries 102a–d each of which corresponds to a respective memory block. The directory 100 is organized, moreover, such that each entry 102a–d has a plurality of fields or cells for storing state and/or status information for the respective block. In particular, the directory 100 has an address column 103 that stores the address of the memory block, an owner column 104 that stores the identity of the entity, e.g., a processor or main memory itself, that is considered to be the owner of the memory block, and a sharer column 106 that stores the identity of those processors or other system entities that have a shared copy of the block.
The sharer column 106 may have a plurality of sub-columns 106a–c, each of which may contain the identity of a particular processor that has a shared copy of the respective memory block. If a request for shared access to a memory block is received from a first processor, P1, main memory examines the directory entry, e.g., entry 102c, for the block to determine its owner. As memory is itself the owner of the block, memory sends its copy of the block to P1 and enters P1's identifier (ID) into one of the sharer fields, e.g. field 106b, of the respective directory entry, e.g., entry 102c, thereby noting that P1 has a shared copy of the block. Since P1 only requested shared access to the memory block, the contents of the entry's owner field 104 are not modified.
If P1 issues a request for exclusive or write access to some other memory block, e.g., the block corresponding to entry 102d, main memory again examines the contents of entry 102d. Suppose that, at the time the request is received, the owner field reflected that memory was the owner of the memory block as shown in parentheses. In this case, memory sends the block to P1, and replaces the contents of the owner field 104 with P1's ID to reflect that P1, rather than memory, is now the owner of the memory block. P1 may then modify or update the memory block. If a request from a second processor, P2, is subsequently received for a shared copy of this memory block, main memory examines entry 102d of the directory 100 and determines that P1 is the owner of the memory block. Because its copy of the block, i.e., the copy stored at main memory, may be stale, memory does not forward its copy to P2. Instead, memory may be configured to forward the request to P1 and add P2's ID to one of the sharer fields, e.g., field 106a. In response to the forwarded request, P1 may then satisfy P2's request by sending it a copy of the modified memory block from P1's cache. Alternatively, main memory may be configured to force P1 to relinquish ownership of the memory block and return the modified version to memory so that memory can send a copy of the up-to-date version to P2.
It has been recognized that a computer system's cache coherency protocol is a key factor in the system's ultimate performance. Poorly designed cache coherency protocols can result in latencies, bottlenecks, other inefficiencies and/or higher complexity, each of which may reduce performance and/or increase cost. Bottlenecks, for example, often arise in high occupancy controllers, such as directory controllers. “Occupancy” is a term of art and refers to the amount of time a controller is unavailable while it services a current request.
In some cache coherency protocols, when a directory controller receives a request corresponding to a memory block, it thereafter becomes unavailable to service other requests for that memory block until certain acknowledgements to the earlier request are received back at the directory controller. The stalling of later requests or references until the directory controller is once again available may degrade system performance. Thus, efforts have been made to design low occupancy cache coherency protocols, which allow multiple requests to the same memory block to be executing substantially simultaneously within the computer system.
As indicated above, cache coherency refers to what values can be returned by a read. A cache coherency protocol, moreover, ensures that two data processing entities will not have two different values for the same memory block. Data consistency, on the other hand, defines when a written value will be returned by a read. In other words, when will a written value be made available or “visible” to other data processing entities. As the only way to observe a written value is through a read, consistency refers to the ordering properties imposed among reads and writes.
The most straightforward model for memory consistency is called sequential consistency. In a sequentially consistent system, the result of any execution is the same as if the operations of all of the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program. One way to implement sequential consistency is to delay each memory access until the previous memory access has been completed. Although it presents a simple programming paradigm, sequential consistency reduces performance especially in computer systems having large numbers of processors and/or long interconnect delays.
An improvement to sequential consistency is weak consistency. In a weak consistency system, an order is imposed between selected sets of memory reference operations while other operations are considered unordered. One or more memory barrier (MB) or fence operations are utilized to indicate the required order. All memory reference operations issued before the MB are ordered before all memory reference operations issued after the MB. However, no order is required on memory reference operations that are not separated by an MB. Thus, by issuing an MB operation a first processor is guaranteed to see the effect of an earlier write by a second processor to a selected memory block. The effects of the MB operation, however, can reach beyond the second processor's write. In particular, issuance of the MB operation also requires that the first processor see the effects of all writes that preceded the second processor's write. One way to implement such guarantees is to impose an obligation on later writes to ensure completion of all earlier writes. This is known as inheritance.
Because each processor must be able to ensure the completion of earlier writes issued by potentially all other processors in the system, current inheritance schemes do not scale well to computer systems having large numbers of processors. Specifically, current schemes can result in the addition of high capacity components or resources at each processor, some of which may rarely if ever be used. This can result in significant increases in system cost. Thus, a need exists for an efficient inheritance mechanism such that later writes can ensure the completion of earlier writes.