Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-01-12
2003-09-16
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S124000, C711S146000
Reexamination Certificate
active
06622214
ABSTRACT:
BACKGROUND OF THE INVENTION
In order to improve the performance of computers having a single central processing unit, computer designers have developed computers which have many central processing units. Often, the central processing units in such multiprocessing computers are connected to each other and to the system's main memory over a single common bus. Recently, however, central processing unit performance is improving at a faster rate than bus performance technology. Faster internal central processor performance results in the need for more external bandwidth. That is, the amount of data transmitted on a common bus must increase to support increased central processing performance. Consequently, the number of central processors which can be connected to a common bus is limited by the bandwidth needed to support the central processors and the total bandwidth of the common bus.
One approach for reducing the bus bandwidth required by each processor in a multiprocessing system has been to place a cache unit between each processor and the common bus. Once data is loaded into a processor's associated cache unit, the processor can access the data in the cache unit without using the common bus. Typically, when a processor obtains data from its cache unit, less data is transmitted over the limited bandwidth of the common bus.
In many cases, a processor will modify a particular data value many times which, in turn, necessitates rewriting the data value back to main memory each time the data value is modified. Rewriting modified data values back to main memory, however, increases the amount of bus bandwidth needed to support a processor. Therefore, if the number of write operations can be reduced, the bus bandwidth required to support a processor can be reduced.
One type of cache unit which reduces the number of write operations is called a “write-back” cache. A write-back cache temporarily stores the modified data values and thus reduces the number of bus transactions needed to write the data values back to main memory. For example, a processor may modify a data value many times in the write-back cache without writing the data back to main memory. The write-back cache ensures that the modified data is eventually written back to main memory.
While write-back caches can be very efficient at reducing the total bus bandwidth required by a multiprocessing system, write-back caches unfortunately create memory coherency problems. For example, each write-back cache contains its own copy of a data value. In such situations, if more than one processor can independently modify a data value, then different versions of the same data value could exist in more than one write-back cache. This would result in erroneous operations, consequently, some mechanism must ensure that all the processors have a consistent view of all data values at all times.
For example, when a processor modifies a data value, the modified data value exists in the write-back cache before it is written back to main memory. In this example, until the write-back cache writes the modified data value back to main memory, the main memory and the other cache units will contain a stale copy of the data value. In order to maintain data integrity, however, the other processors which request the data value must obtain the up-to-date version of the data value, not the stale data value.
The process of ensuring that all the processors have a consistent view of all data values is called cache coherency. One popular and successful set of methods for achieving cache coherency relies on what are called “snooping operations.” While a wide variety of snooping operations exist, basically, the snooping operations in a cache unit monitor the bus transactions on the common bus. The snooping operations identify which transactions affect the contents of a cache unit or which transactions relate to modified data existing in a cache unit. Snooping operations typically require that all the processors and their associated cache units share a common bus. Sharing a common bus allows the cache units to monitor the bus transactions and potentially interfere with a bus transaction when a particular cache unit contains a modified data value.
Cache coherency methods also typically utilize coherency status information which indicates whether a particular data value in a cache unit is invalid, modified, shared, exclusively owned, etc. While many cache coherency methods exist, two popular versions include the MESI cache coherency protocol and the MOESI cache coherency protocol. The MESI acronym stands for the Modified, Exclusive, Shared and Invalid states while the MOESI acronym stands for the Modified, Owned, Exclusive, Shared and Invalid states.
The meanings of the states vary from one implementation to another. Broadly speaking, the modified state usually means that a particular cache unit has modified a particular data value. The exclusive state and owned state usually means that a particular cache unit may modify a copy of the data value. The shared state usually means that copies of a data value may exist in different cache units, while the invalid state means that the data value in a cache unit is invalid.
In operation, the cache units snoop the bus operations and use the coherency status information to ensure cache coherency. For example, assume that a first processor having a first cache unit desires to obtain a particular data value. Furthermore, assume that a second processor having a second cache unit contains a modified version of the data value (the coherency status information indicates that the data value in the second cache unit is in the modified state).
In this example, the first processor initiates a read bus request to obtain the data value. The second cache unit snoops the read bus request and determines that it contains the modified version of the data value. The second cache unit then intervenes and delivers the modified data value to the first processor via the common bus. Depending on the system, the modified data value may or may not be simultaneously written to the main memory.
In another example, assume that the first processor desires to exclusively own a particular data value. Furthermore, assume that a second cache unit contains an unmodified, shared copy of the data value (the coherency status information indicates that the data value in the second cache unit is in the shared state). In this example, the first processor initiates a read bus request which requests data for exclusive use.
The second cache unit snoops the read bus request and determines that it contains a shared copy of the data value. The second cache unit then invalidates its shared data value by changing the data value's coherency status information to the invalid state. Changing the data value's coherency status to the invalid state invalidates the data value within the second cache unit. The first processor then completes the read bus request and obtains a copy of the data value from main memory for exclusive use.
While snooping operations maintain cache coherency on multiprocessing systems with a single common bus, more powerful computers contain more than one bus such that each bus interconnects main memory with multiple processors; however, because a common bus has a growing limitation in the number of processors it can support, a multiple-bus system might be necessary to achieve a desired level of performance. A problem associated with multiple buses is that the processors on one bus cannot monitor the transactions initiated by the processors on the other buses. Consequently, the snooping operations cannot maintain memory coherency in multiple-bus computers.
One way to maintain cache coherency in multiple-bus systems is to broadcast the bus transactions initiated on each bus to all the other buses. Unfortunately, this approach results in having the combined bus bandwidth load of all buses transmitted to each bus. As can be expected, this can significantly reduce system performance and obviate the benefit of multiple buses.
A second appro
Chang Stephen S.
Vogt Pete D.
White George P.
Kim Matthew
Tran Denise
LandOfFree
System and method for maintaining memory coherency in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for maintaining memory coherency in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for maintaining memory coherency in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3030260