CN1149494C - Method and system for maintaining cache coherency - Google Patents

Abstract

A method and system for maintaining cache coherency for write-through store operations in a data processing system. A write-through store operation is passed from a particular processor to the system bus through any caches of said multiple levels of cache which are interposed between the particular processor and the system bus. The write-through store operation is performed in any of the interposed caches in which a cache hit for the write-through store operation is obtained. All caches of said multiple levels of cache, which are not interposed between the particular processor and the system bus, are snooped from an external snoop path of the system bus with a data address of said write-through operation until the write-through operation is successful, wherein the cache coherency point for the memory hierarchy is set at the system bus for write-through store operations such that the write-through operation is completed successfully prior to completion of any other instructions to the same data address.

Description

Method and system for maintaining cache coherency

technical field

The present invention relates generally to improved methods and systems for data processing, and more particularly to improved methods and systems for maintaining cache coherency in multiprocessor data processing systems. In addition, the present invention relates more particularly to methods and systems for maintaining cache coherency during write-through store operations in multiprocessor systems.

Background technique

Most modern high-performance data processing system architectures include multiple levels of cache memory in the storage hierarchy. Cache memory is used in data processing systems to provide faster access to frequently used data compared to the time to access system memory, thereby improving overall performance. Levels of cache memory are typically used with progressively longer access latencies. Smaller, faster caches are used at levels within the memory hierarchy close to the processor or processors, while larger, slower caches are used at levels close to system memory.

In a conventional symmetric multiprocessor (SMP) data processing system, all processors are usually identical, all processors using the same common instruction set and the same communication protocol have similar hardware structures, and usually provide similar storage system. For example, a conventional SMP data processing system includes a system memory; a plurality of processing units, each including a processor and one or more levels of cache memory; and a system bus coupling the processing units to each other and to the system memory. Many such systems include at least one level of cache shared between two or more processors. To obtain effective execution results in an SMP data processing system, it is important to obtain a consistent storage hierarchy, ie, provide the same storage content for all processors.

Although designed to maintain cache coherency through snooping, "retrying" responses can cause processor operation errors. In particular, with write-through stores, retrying the same write-through store will be problematic once a write update has been made, and the load is subsequently allowed to read the new data.

Therefore, there is a need to provide a method of maintaining cache coherency in a multiprocessor system, especially maintaining cache coherency for write-through store operations in the presence of retries.

Contents of the invention

It is therefore an object of the present invention to provide an improved method and system for data processing. It is therefore another object of the present invention to provide an improved method and system for maintaining cache coherency in a multiprocessor data processing system.

It is a further object of the present invention to provide an improved method and system for maintaining cache coherency during write-through operations in a multiprocessor system.

The above objects are achieved by the methods and systems presented herein. The method and system of the present invention are used to maintain cache coherency during write-through store operations in a data processing system, wherein the data processing system includes a plurality of processors coupled to a system bus through a memory architecture, wherein the memory architecture includes Multi-level cache memory. Write-through store operations are passed from a particular processor to the system bus through any cache memory of the multi-level cache interposed between the particular processor and the system bus. A write-through store operation may proceed in any inserted cache that is hit by a write-through store operation. all caches of said multi-level cache not interposed between a particular processor system bus listen to the data address of said write-through operation by an external snoop path of the system bus until the write-through operation succeeds, wherein A coherency point for the memory architecture's cache memory is placed on the system bus for write-through store operations, whereby the write-through operation completes successfully before any other instruction to the same data address completes.

The above and other objects, features and advantages of the present invention will become apparent from the following detailed description.

Description of drawings

The novel features of the invention are set forth in the appended claims. However, the invention itself and preferred modes of use, as well as other objects and advantages of the invention, will be best understood by reading the following detailed description with reference to the following exemplary embodiments when read in conjunction with the accompanying drawings, in which:

Figure 1 shows a timing diagram of an error occurring when a write-through store instruction is retried by current snooping techniques;

Figure 2 shows a high-level block diagram of a multiprocessor data processing system according to the present invention;

Figure 3 shows a timing diagram of the performance of direct write store instructions with the self-snooping technique; and

FIG. 4 shows a high-level logic flow chart of the process of performing a write-through storage operation.

Specific implementation

Referring now to the drawings, and in particular to FIG. 2, there is shown a high level block diagram of a multiprocessor data processing system in accordance with the present invention. As shown, data processing system 8 includes a plurality of processor cores 10a-10n paired with other plurality of processor cores 11a-11n, each preferably comprising a PowerPC line of processors available from International Business Machines Corporation. Each processor core 10a-10n and 11a-11n includes an on-board Level 1 (L1) cache memory 12a-12n, in addition to conventional registers, instruction stream logic and execution units for executing program instructions and 13a-13n, can temporarily store instructions and data that may be accessed by the associated processor. Although L1 cache memories 12a-12n and 13a-13n are shown in FIG. 2 as integral cache memories storing instructions and data (hereinafter simply referred to as data), those skilled in the art will understand 12n and 13a-13n can also be implemented with both instruction and data caches.

To reduce latency, data processing system 8 also includes one or more additional levels of cache memory, such as level two (L2) cache memories 14a-14n, for separating data into L1 cache memories 12a-12n and 13a -13n. In other words, L2 caches 14a-14n act as intermediate memory between system memory 18 and L1 caches 12a-12n and 13a-13n and can typically store Much larger volumes of data, but require longer storage latencies. For example, L2 caches 14a-14n have a storage capacity of 256 or 512 kilobytes, and L1 caches 12a-12n and 13a-13n have a storage capacity of 64 or 128 kilobytes. As noted above, although FIG. 2 shows only two levels of cache memory, the storage hierarchy of data processing system 8 may be expanded to include additional levels of cache memory (L3, L4, etc.) connected in series or backed up.

As shown, data processing system 8 also includes input/output (I/O) devices 20 , system memory 18 , and nonvolatile memory 22 , each coupled to interconnect 16 . I/O device 20 includes conventional peripherals such as a display device, keyboard, and graphic pointers connected to interconnect 16 by conventional adapters. Non-volatile memory 22 stores an operating system and other software that is loaded into volatile system memory 18 when data processing system 8 is powered on. Of course, those skilled in the art will appreciate that the data processing system may include many other components not shown in FIG. wait.

An interconnect 16 of one or more buses, including a system bus, acts as a pipeline for communication between the L2 caches 14 a - 14 n , system memory 18 , I/O devices 20 , and non-volatile memory 22 . A typical communication transaction on the interconnect 16 includes a source tag indicating the source of the transaction, a destination tag identifying the intended recipient of the transaction, an address, and/or data. Each device coupled to the interconnect 16 preferably listens to all communication transactions on the interconnect 16 to determine whether the device's identity has been updated as a result of the transaction. An external snoop path from each cache memory to the system bus of interconnect 16 is preferably provided.

A coherent memory architecture is maintained by using a memory coherency protocol of choice, such as the MESI protocol. In the MESI protocol, the storage of a coherent state indication is associated with each coherent block (eg, cache line or sector) of at least all upper-level (cache) memory. Each coherency granule can have one of four states, modified (M), exclusive (E), shared (S), or invalid (I), which can be encoded by two bits in the cache directory. The modified state indicates that the coherency granule is only valid in the cache storing the modified coherency granule, and the value of the modified coherency granule has not been written to system memory. When a coherent granule is indicated as exclusive, the coherent granule resides only in the caches of all caches that have a coherent granule in the exclusive state at the level of the storage hierarchy. However, the data in the exclusive state is consistent with that in system memory. If a coherent granule is marked as shared in the cache directory, then the coherent granule resides in the associated cache and possibly other caches at the same level of the storage hierarchy, all of the coherent granules The copies are all consistent with system memory. Finally, an invalid state indicates that neither the data nor the address tags associated with the coherency block resides in the cache.

Each cache line (block) of data in an SMP system preferably includes an address tag field, a status bit field, a contained bit field, and a value field for storing actual instructions or data. The status bit field and the contained bit field are used to maintain cache coherency (indicating that the value stored in the cache memory is valid) in a multiprocessor computer system. Addresses are marked as a subset of the full address of the corresponding memory block. If the input is valid, a tag in the address tag field compares to the entered address and matches, indicating a cache "hit".

In maintaining cache coherency, a write-through cache store does not assign cache line or gain ownership (E or M state of the MESI protocol) until a store is made in the cache. In particular, write-through or full-store caches operate, providing write operations to the cache and main memory during processor write operations, thereby ensuring coherency between the cache's data and main memory. To maintain cache coherency, a coherent write-through store must invalidate any valid cache line on the processor, handling outside the originating cache line from a particular cache coherency point, to ensure access from all Subsequent loads to the processor get the newly updated data.

Typically, bus "snooping" techniques are used to invalidate cache lines from cache coherency points. Each cache preferably includes snoop logic to snoop. Whenever a read or write is performed, the address of the data is propagated by the originating processor core to all other caches sharing a common bus. Each snoop logic unit snoops an address from the bus and compares the address to an array of address tags for the cache memory. When there is a hit, the snoop response returns, allowing further operations to maintain cache coherency, such as invalidating the cache line that hit. In addition, a "retry" snoop response is issued by the cache's bus snoop logic since the cache has a first modification copy or store that must push out the cache to prevent a proper snoop. When retrying, the processor core that originated the data address will retry the read or write operation.

Figure 1 shows a timing diagram where an error occurs when a write-through store instruction is retried, according to the snooping technique, which is an alternative to the preferred embodiment. In this example, assume an SMP architecture with a processor core 0 and processor core 1, an L1 cache associated with each core, and an L2 cache shared by both processor cores. The point of maintaining cache coherency of the processor in this example is set at the L2 cache. Additional processor cores and levels of cache memory can then be used for purposes of this example not utilized in FIG. 1 .

For this example, the pseudocode sequence is:

Processor Core 0 Processor Core 1

store 2 to A loop: load A

If A! = 2 cycles

Store 3 to A

If a store to processor core 0 occurs, but before a store to processor core 0 occurs again, retrying allows the input and store to proceed to processor core 1, the resulting consistent store state for address A is 2, which is incorrect.

In the first clock cycle 60, shown in the timing diagram, the bus is asserted by core 0 (core OWTST) whereby the address and data (RA) of the write-through store operation is transferred to the L2 cache. Thereafter, at reference numeral 62, the write-through stored data address is propagated on the system bus to all non-originating cores (Core 1), whereby the non-originating edge snoops the data address. Also, during the same cycle, at reference numeral 64, the data address is compared to the L2 tag array to determine if a previous version of the data resides in the L2 cache. In a third cycle, at reference numeral 66, the snooped address is compared to the L1 tag array in the L1 cache associated with core 1 . In addition, an L2 hit returns in the L2 cache, as indicated by reference numeral 68 . Thereafter, L2 data writing is performed by writing a write instruction into the pipeline for updating the L2 cache to "A=2", as indicated by reference numeral 70 . Next, during the fourth clock cycle, the snoop response of the L1 cache of core 1 is returned as a retry, as indicated by reference numeral 72 .

Note that, particularly with the non-preferred snooping technique, the write-through store updates the L2 cache before the snoop response indicating a retry is returned. The retry returns for reasons that include a listen hit for a sector in the M state and a listen hit queued for valid operations. Set core 0 to retry the write-through store operation when the retry is returned by core 1's L1 cache. Cache coherency is maintained at the L2 cache, so write-through stores are retried in the L2 cache and any higher-level caches are updated before sending the write-through operation to the bus.

When "A!=2", processor core 1 waits in a loop. When a store operation from core 0 writes to the L2 cache, even if retry is set in core 0, core 1 arbitrates the loaded bus and propagates the data address indicated by reference numeral 74 . Next, the address is compared to the L2 tag array of the L2 cache, as indicated by reference numeral 76 . Thereafter, an L2 cache hit is received, as indicated by reference numeral 78 . Finally, reading of data in the L2 cache is performed, where "A=2", as indicated by reference numeral 80 . After reading the data after a delay period 81, core 1 aborts the loop and performs a store operation of "store 3 to A".

Core 1 arbitrates the bus transfer store-through operation, wherein the data address of the store-through is propagated, as indicated by reference numeral 82 . Next, an L2 flag comparison is performed, as indicated by reference numeral 84 . Thereafter, an L2 cache hit is received, as indicated by reference numeral 86 . Finally, the data is committed to the pipeline of the L2 cache as a write of "A=3", as indicated by reference numeral 88 .

Since load and store operations from core 1 arbitrate the local bus, retries of core 0 "store 2 to A" operations are delayed until the bus is next available. Core 0 reissues write-through store operations received by the L2 cache, as indicated by reference numeral 90 . The data address is sent locally, thereby snooping the core 1, as indicated by reference numeral 92 . Thereafter, the L1 tags are compared in the L1 cache of core 1, as indicated by reference numeral 94 . Next, the L2 tags are compared in the L2 cache, as indicated by reference numeral 96 . A cache hit is returned by L2, as indicated by reference numeral 98 . Finally, the data is rewritten into the L2 cache, whereby "A=2" is shown at reference numeral 100 .

As mentioned above, if the write-through store is snooped locally and the store is retried, another processor core arbitrating the bus can do a load, see the updated data in the L2 cache, before the original store receives the arbitration again. write storage. The first write-through store will overwrite the data of the second store that depends on the first store.

One possible solution to the problem shown in Figure 1 is to delay the L2 data and address pipeline, whereby the data retry phase follows the commit phase. To do the solution, L2 reads would be separated from L2 writes, or L2 reads would be delayed. In the first case, the complexity of L2 adjudication will increase significantly. In the second case, 2 additional cycles are added to all L2 cache hit conditions, resulting in an undesirable performance penalty.

Another solution is to flush the committed L2 update with the previous state of the write-through operation in a similar manner to that used by the register renaming scheme, which is well known in the art. For a cache, the solution adds additional undesired complexity, which slows down the cache.

Referring now to FIG. 3, a timing diagram illustrating the performance of a write-through store instruction using the self-sense technique is shown in accordance with a preferred embodiment of the present invention. Figure 3 shows the processor operation also shown in Figure 1, however, in Figure 3, self-listening is used to eliminate errors caused by retries. Core 0 issues a write-through store operation received at the L2 cache, thereby making an L2 cache arbitration, as indicated by reference numeral 110 . Next, a comparison of the L2 markers with the array of L2 markers is performed, as indicated by reference numeral 112 . Next, a cache hit tagged in the L2 tag array is received, as indicated by reference numeral 114 . Thus, data written to the L2 cache is placed in the pipeline for execution, as indicated by reference numeral 116 . After a delay 117 , during a write-through store operation arbitrated to write to the system bus of main memory, a self-snoop along the system bus is arbitrated, as indicated by reference numeral 118 . In FIG. 1, the cache coherency point is on the L2 cache for write-through store operations, however in this embodiment, the cache coherency point is on the system bus for write-through store operations. For cache coherent points on the system bus for write-through store operations, if a retry is raised during a self-listen, the write-through operation listens on the system bus as many times as necessary until no return signal is returned, regardless of Other commands wait. In particular, the system bus includes bus arbitration logic that ensures that snooping devices continue to access the bus until write-through stores are consistently completed in all cache memories, so data can be written to main memory.

In addition to self-snooping, local data addresses for write-through store operations are propagated along external snoop paths to non-originating cores, as indicated by reference numeral 120 . Thereafter, L1 markers are compared with L1 marker arrays, as indicated by reference numeral 122 . In the next cycle, the response to the L1 tag comparison is returned, as indicated by reference numeral 124 . If the response is a retry, then the write-through store's address will continue to arbitrate from the snooped system bus until the L1 cache returns a non-retry response.

Once the no-retry response is returned, core 1 arbitrates the local bus for a load, as indicated by reference numeral 126 . Then, in another embodiment, the core 1 load need not wait until the store has been committed to the system bus without retrying. For example, if the load hits and commits in the L2 cache, starting the core 1 load after writing the L2 data as indicated by reference numeral 116 will not break data coherency. Thereafter, an L2 marker is compared to an L2 marker array, as indicated by reference numeral 128 . Next, the tagged L2 hits are returned in the L2 tag array, as indicated by reference numeral 130 . Thereafter, data is read from L2 as indicated by reference numeral 132 . After a delay 133 , core 1 asserts the local bus for write-through storage, as indicated by reference numeral 134 . Thereafter, an L2 marker is compared to an L2 marker array, as indicated by reference numeral 136 . Next, the tagged L2 hits are returned in the L2 tag array, as indicated by reference numeral 138 . Thereafter, the L2 data write is committed, as indicated by reference numeral 140 . As shown in the write-through store of core 1, after the L2 data write indicated by reference numeral 140, the write-through store operation will continue to the system bus to be updated in the main memory, thereby maintaining high speed by self-snooping by the system bus Buffer memory consistency.

FIG. 4 shows a high-level logic flow chart of the process of performing a write-through storage operation. The process begins at block 150 and proceeds to block 152 thereafter. Block 152 shows arbitrating the processor core and local bus to send the address of the write-through store operation to the lower layer of cache memory. Thereafter, block 154 shows comparing the address with the tag array in the lower cache. The next block 156 shows determining whether there is a tagged hit in the lower cache. If there is a tagged hit in the lower cache memory, then the process passes to block 158 . Block 158 shows the committing of data to write in the lower level cache. The process then passes to block 160 . Returning to block 156 , if there are no tagged hits in the lower cache, then the process passes to block 160 . Although not shown, the processes shown in blocks 154, 156 and 158 may be performed on multiple levels of lower cache memory.

Block 160 illustrates passing the write-through store operation to the system bus. Next, block 162 shows arbitrating the system bus to send a write-through store operation to the memory and performing a self-listening of the system bus. Thereafter, block 164 illustrates snooping the address in the untraversed cache through the external snoop path. For example, any cache that is not passed is a path that does not provide a path to the system bus from the processor core that originated the write-through store operation. Next, block 166 shows comparing the snoop address to the tag array in the unpassed cache. Thereafter, block 168 shows determining whether the listener returns to retry. If the intercept returns a retry, then the process passes to block 162 . If the listener does not return to retry, then the process passes to block 170 . Block 170 shows committing the write-through store to main memory. Thereafter, block 172 shows releasing the system bus to the next operation after which the process returns.

Although the present invention has been shown and described with reference to preferred embodiments, it will be understood by those skilled in the art that various changes in form and details may be made without departing from the spirit and scope of the invention. For example, an alternative embodiment allows the pipelining of requests to the system bus, whereby pending requests are committed (get a non-retry response) or complete (read or write associated data) as long as the If the requests are submitted in the same order and the data order is also maintained, then the request can be arbitrated to the same address as the subsequent request waiting.

Claims (8)

1. A method of maintaining cache coherency during a write-through store operation in a data processing system, wherein the data processing system includes a plurality of processors and memory architectures coupled to a system bus, wherein the memory architecture includes several All levels of cache memory, the method includes the following steps: transferring a write-through store operation from a processor to said system bus via a cache memory interposed between said processor and said system bus; performing the store-through operation in any one of the intervening caches that gets a cache hit for the store-through operation; and With the data address of the write-through operation, the external snoop path of the system bus is used to snoop a cache memory not interposed between the processor and the system bus until the write-through operation is successfully performed by This maintains cache coherency. 2. The method for maintaining cache memory coherency during a write-through store operation according to claim 1, said write-through store operation being processed by a cache memory interposed between said processor and said system bus The step that the device transmits to the system bus also includes the following steps: arbitrating a local bus for said processor to transfer said data address for said write-through store operation to said intervening cache memory. 3. The method of maintaining cache memory coherence during a write-through store operation according to claim 1, wherein said cache memory hit in any one of said inserted cache memories that gets said write-through store operation The step of performing the write-through storage operation also includes the following steps: comparing the data address of the write-through operation with an array of address tags in the inserted cache memory; and If the data address matches any tag in the address tag array, a cache hit is returned. 4. The method for maintaining cache memory coherency during a write-through storage operation according to claim 1, wherein the data address of the write-through operation is detected by an external snooping path of the system bus that is not inserted in the The step of maintaining the cache memory between the processor and the system bus until the write-through operation succeeds, thereby maintaining the consistency of the cache memory, further comprising the following steps: arbitrating the system bus for the write-through store operation; communicating the data address of the write-through operation to the external listening path of the system bus; comparing said data address with an array of address tags not in a cache memory interposed between said processor and said system bus; maintaining the data address along the external snoop path in response to any retry response returned to the system bus; and The write-through store operation within system memory of the memory architecture is completed in response to the snoop without a retry condition being returned to the system bus. 5. A system for maintaining cache coherency during write-through store operations in a data processing system, wherein the data processing system includes a plurality of processors and a memory hierarchy coupled to a system bus, wherein the memory hierarchy includes several stages cache memory, the system includes: means for transferring write-through store operations from a processor to said system bus via a cache memory interposed between said processor and said system bus; means for performing said write-through store operation in any one of said intervening caches that gets a cache hit for said write-through store operation; and With the data address of the write-through operation, the external snoop path of the system bus is used to snoop a cache memory not interposed between the processor and the system bus until the write-through operation is successfully performed by This is the means by which cache coherency is maintained. 6. The system for maintaining cache memory coherence during write-through store operations according to claim 5, the write-through store operations are transmitted by a processor through a cache memory interposed between said processor and said system bus The means to the system bus also includes: Arbitration means for arbitrating a local bus for said processor to transfer said data address of said write-through store operation to said intervening cache memory. 7. The system for maintaining cache coherency during a write-through store operation according to claim 5 , performing said The means for write-through storage operation also includes: means for comparing said data address of said write-through operation with an array of address tags in said inserted cache memory; and If the data address matches any tag in the address tag array, then a cache hit is returned. 8. The system for maintaining cache memory coherency during a write-through store operation according to claim 5, wherein, with the data address of the write-through operation, the external snoop path of the system bus is used to snoop a The cache memory between the processor and the system bus, until the write-through operation succeeds, thereby maintaining the coherency of the cache memory, further comprising: means for arbitrating the system bus for the write-through store operation; means for communicating the data address of the write-through operation to the external snoop path of the system bus; means for comparing said data address with an array of address tags not in a cache memory interposed between said processor and said system bus; means for maintaining said data address along said external snoop path in response to any retry response returned to said system bus; and means for completing said write-through store operation within system memory of said memory architecture in response to said snoop without a retry condition being returned to said system bus.

Images