Method and system for write-through stores of varying sizes

[0002] 1. Technical Field

[0003] The present invention relates in general to an improved method and system for data processing and in particular to an improved method and system for performing write-through stores in a multiprocessor data processing system. Still more particularly, the present invention relates to a method and system for maintaining cache coherency for write-through store operations in a multiprocessor system where the stores are of varying sizes.

[0004] 2. Description of the Related Art

[0005] In a conventional symmetric multiprocessor (SMP) data processing system, all of the processors are generally identical, that is, the processors all utilize common instruction sets and communication protocols, have similar hardware architectures, and are generally provided with similar memory hierarchies. For example, a conventional SMP data processing system may comprise a system memory, a plurality of processing elements that each include a processor and one or more levels of cache memory and a system bus coupling the processing elements to each other and to the system memory. To obtain valid execution results in a SMP data processing system, it is important to maintain a coherent memory hierarchy, that is, to provide a single view of the contents of memory to all of the processors.

[0006] A coherent memory hierarchy is maintained through the use of a selected memory coherency protocol, such as the MESI protocol. In the MESI protocol, an indication of a coherency state is stored in association with each coherency granule (e.g. cache line or sector) of at least all upper level (cache) memories. Each coherency granule can have one of four states, modified (M), exclusive (E), shared (S), or invalid (I), which is indicated by two bits in the cache directory. The modified state indicates that a coherency granule is valid only in the cache storing the modified coherency granule and that the value of the modified coherency granule has not been written to system memory. When a coherency granule is indicated as exclusive, the coherency granule is resident in, of all caches, at that level of the memory hierarchy, only the cache having the coherency granule in the exclusive state. The data in the exclusive state is consistent with system memory, however. If a coherency granule is marked as shared in a cache directory, the coherency granule is resident in the associated cache and in at least one other cache at the same level of the memory hierarchy, all of the copies of the coherency granule being consistent with system memory. Finally, the invalid state indicates that the data and address tag associated with a coherency granule are both in invalid.

[0007] A write-through store updates data at each valid level in the cache hierarchy as well as main memory which corresponds to the address accessed. In particular, a write-through or store-through cache operates to provide a write operation to both the cache memory and the main memory during processor write operations, thus insuring consistency between the data in the cache memory and the main memory. To maintain cache coherency, a coherent write-through store must either flush valid matching cache lines on a processor or modify the data associated with a particular line to reflect the update caused by the write-through store. This ensures that subsequent loads from all processors obtain the newly updated data. Typically, a bus “snooping” technique is utilized to initiate invalidation of cache lines.

[0008] Preferably, a write-through store can be valid data of varying sizes from one byte up to the largest data type for a particular processor. In certain caches, handling write-through stores of varying size poses problems. In particular some caches do not provide a capability to write valid data less than a particular size. Therefore, to write-through data in these caches a cache line must first be flushed and invalidated, utilizing processor cycles. Thereby, the write-through operation passes by the cache onto the next memory without being written. However, it is preferable to maintain data in the caches for reduced latency accessing. In addition, since flushing for each write-through store is inefficient, it is therefore desirable to provide for the write-through of varying sizes of valid data to caches which do not provide the capability to write valid data less than a particular width.

[0009] It is therefore one object of the present invention to provide an improved method and system for data processing.

[0010] It is therefore another object of the present invention to provide an improved method and system for performing write-through stores in a multiprocessor data processing system

[0011] It is yet another object of the present invention to provide an improved method and system for maintaining cache coherency for write-through store operations in a multiprocessor system where the stores are of varying sizes.

[0012] The foregoing objects are achieved as is now described. A method and system for performing write-through store operations of valid data of varying sizes in a data processing system are provided, where the data processing system includes multiple processors that are coupled to an interconnect through a memory hierarchy, where the memory hierarchy includes multiple levels of cache, where at least one lower level of cache of the multiple of levels of cache requires store operations of all valid data of at least a predetermined size. First, it is determined whether or not a write-through store operation is a cache hit in a higher level of cache of the multiple levels of cache. In response to a determination that a cache hit has occurred in the higher level of cache, the write-through store operation is merged with data read from the higher level of cache to provide a merged write-through operation of all valid data of at least the predetermined size to a lower level of cache. The merged write-through operation is performed in the lower level of cache, such that write-through operations of varying sizes to a lower level of cache which requires write operations of all valid data of at least a predetermined size are performed with data merged from a higher level of cache.

[0013] The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself, however, as well as a preferred mode of use, further objects and advantages thereof, will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein:

[0014] FIG. 1 depicts a high level block diagram of a multiprocessor data processing system in accordance with the present invention;

[0015] FIG. 2 illustrates a schematic diagram of a path for reading from and writing to L2 cache according to the method and system of the present invention;

[0016] FIG. 3 depicts a high level block diagram of the address pipeline for an L3 cache;

[0017] FIG. 4 illustrates a block diagram representation of the L2 to L3 store queue depicted in FIG. 3;

[0018] FIG. 5 depicts a timing diagram representation of two write-through store transactions in L3 cache;

[0019] FIG. 6 illustrates a high level logic flowchart of a process for passing a write-through store transaction from a higher level of cache to a lower level; and

[0020] FIG. 7 depicts a high level logic flowchart of a process for issuing a write-through store instruction to L3 cache.

[0021] With reference now to the figures, and in particular with reference to FIG. 1, there is illustrated a high level block diagram of a multiprocessor data processing system in accordance with the present invention. As depicted, data processing system 8 includes a number of processors 10a-10n, which each preferably comprise one of the PowerPC line of processors available from International Business Machines Corporation. In addition to the conventional registers, instruction flow logic and execution units utilized to execute program instructions, each of processors 10a-10nalso includes an associated one of on-board level one (L1) caches 12a-12n, which temporarily stores instructions and data that are likely to be accessed by the associated processor. Although L1 caches 12a-12nare illustrated in FIG. 1, as unified caches that store both instruction and data(both referred to hereinafter simply as data), those skilled in the art will appreciate that each of L1 caches 12a-12ncould alternatively be implemented as bifurcated instruction and data caches.

[0022] In order to minimize latency, data processing system 8 may also include one or more additional levels of cache memory, such as level two (L2) caches 14a-14n, which are utilized to stage data to L1 caches 12a-12n. L2 caches 14a-14nmay be on-chip as depicted with L1 caches 12a-12nor may be off-chip. L2 caches 14a-14nfunction as intermediate storage between level three (L3) caches 15a-15nand L1 caches 12a-12n, and can typically store a much larger amount of data than L1 caches 12a-12n, but at a longer access latency. For example, L2 caches 14a-14nmay have a storage capacity of 512 kilobytes, which L1 caches 12a-12nmay have a storage capacity of 128 kilobytes.

[0023] Data processing system 8 is further supported by lookaside L3 caches 15a-15nwhich are positioned between interconnect 16 and processors 10a-10n. Each of L3 caches 15a-15nis preferably a 4 M byte static random access memory (SRAM). In particular, L3 caches 15a-15nutilize high performance 8 megabit double data rate (DDR) SRAM. Such SRAMs, do not provide a capability to write data less than the width of the SRAM data bus which is typically 4 bytes for the SRAM described. However, these L3 caches 15a-15nsupport write-through store transactions which can vary from one to sixteen bytes by the method and system of the present invention. While a particular SRAM has been described, additional fixed length SRAM caches may also be utilized as will be understood by one skilled in the art. In addition, although FIG. 1 depicts only three levels of cache, the memory hierarchy of data processing system 8 could be expanded to include additional levels (L4, L5, etc.) of serially-connected or lookaside caches.

[0024] As illustrated, data processing system 8 further includes input/output (I/O) devices 20, system memory 18, and non-volatile storage 22, which are each coupled to interconnect 16. I/O devices 20 comprise conventional peripheral devices, such as a display device, keyboard, and graphical pointer, which are interfaced to interconnect 16 via conventional adapters. Nonvolatile storage 22 stores an operating system and other software, which are loaded into volatile system memory 18 in response to data processing system 8 being powered on. Of course, those skilled in the art will appreciate that data processing system 8 can include many additional components which are not shown in FIG. 1, such as serial and parallel ports for connection to network or attached devices, a memory controller that regulates access to system memory 18, etc.

[0025] Interconnect 16, which can comprise one or more buses or a cross-point switch, serves as a conduit for communication transactions between processors 10a-10n, system memory 18, I/O devices 20, and nonvolatile storage 22. A typical communication transaction on interconnect 16 includes a source tag indicating the source of the transaction, a destination tag specifying the intended recipient of the transaction, an address and/or data. Each device coupled to interconnect 16 preferably snoops all communication transactions on interconnect 16.

[0026] Referring now to FIG. 2, there is depicted a schematic diagram of a path for reading and writing the L2 cache according to the method and system of the present invention. An L2 data subarray 30 is provided where data is written to or read from L2 data subarray 30. In particular, the write-through is performed in a high level of cache, such as L2 data subarray 30 which preferably contains a byte of a 32 byte sector of the 512 kilobytes available in an L2 cache. For write-through stores, when performing a write-through of a subset of the 32 byte sector, in the case of a cache hit, the bytes that are not being updated are read out of L2 data subarray 30 through sense amp 32. The bytes being written are forwarded to a respective position of L2 data subarray 30 by write driver 34 and forwarded to L3 cache. The read and forwarded data is merged in a store queue (not shown). Write driver 34 is enabled by a write enable signal which also enables a multiplexer 36. The write enable signal specifies byte by byte whether to output data read from L2 data subarray 30 through multiplexer 36, or to forward the data being written to L2 data subarray 30 through multiplexer 36.

[0027] For all write-through operations, bytes being written are preferably quickly forwarded to an L3 cache as illustrated by path 40. In the case of a write-through operation of 32 bytes that hits in the L2 cache, all data is forwarded to the L3 cache as illustrated by path 40 without merging with data from L2 data subarray 30. While the figure is depicted for a higher level L2 cache passing read/forward data to a lower level L3 cache, other higher level and lower level caches may also be utilized. In addition, while this figures and others following utilize a sector of 32 bytes of data, other sizes of data sectors may also be utilized.

[0028] With reference now to FIG. 3, there is illustrated a high level block diagram of the address pipeline for an L3 cache. An L2 to L3 store queue 80 holds write-through transaction data forwarded from the L2 cache. In particular, for each write-through operation, a 32-byte bit is set if the transaction includes 32 bytes of valid data either from the original write-through store or from a read of the L2 cache. If the 32-byte bit is not set, when the write-through transaction is issued from store queue 80, the write-through transaction is synthesized to a flushing operation and a copy of the queued write-through store transaction is placed in held write-through register 82. A multiplexer 84 decides between transactions from held write-through register 82, store queue 80 and other L3 cache requests 96. When a transaction passes through multiplexer 84, the transaction is placed in L3 pipeline 88. In the present embodiment, L3 pipeline 88 provides three pipeline stages by T1 register 90, T2 register 92 and T3 register 94 where data passes through each pipeline register. In addition, an L3 tag array 86 is provided to maintain a record of data resident in the L3 cache.

[0029] Referring now to FIG. 4, there is illustrated a block diagram representation of the L2 to L3 store queue depicted in FIG. 3. The queue passing operation preferably passes an address 42, data 44, original size attribute 46, other instruction information 48, and a 32-byte bit 50 with each write-through store transaction. 32-byte bit 50 provides an indicator that the write-through transaction has all 32 bytes valid and up-to-date with respect to cache coherency and was originally 32 bytes or hit in the L2 cache (i.e. the data is the merged result of the L2 cache with the write-through data). However, if the transaction included less than 32 valid bytes, then 32-byte bit 50 is not set. Original size attribute 46 tracks the size of the write-through store without merged data such that other memory devices which can write-through data of varying sizes may utilize the original data size in doing so.

[0030] With reference now to FIG. 5, there is depicted a timing diagram representation of two write-through store transactions in L3 cache. In a first example, the 32-byte bit is set as illustrated at reference numeral 66. Since the 32-byte bit is set for the write-through transaction WTA, in the next clock cycle, WTA is passed to the L3 pipeline and possibly written to the L3 cache if that sector is resident and valid as depicted at reference numeral 72. Thereafter, for the next two clock cycles, WTA is passed through the T2 and T3 stages of the L3 pipeline as illustrated at reference numerals 74 and 76. In addition, WTA is passed on to main storage which ignores the 32-byte bit.

[0031] In a second example, the 32-byte bit is not set when the WTB store transaction is made as depicted at reference numeral 64. Since the 32-byte bit is not set, the L3 cannot perform the transaction as is since the transaction may overwrite potentially valid data in L3 cache. In particular, when WTB enters the L3 pipeline, the transaction is interpreted as a flushing operation since the 32-byte bit is not set as depicted at reference numeral 66. By setting the transaction as a WTB flush, a modified sector will be cast out of the L3 cache and the status of that sector updated to invalid. Further, for valid non-modified sectors, no cast out is generated, but the status of the sector is updated to invalid.

[0032] During the cycle that WTB flush is accepted into the L3 pipeline, the entire write-through transaction is registered in the held write-through register as WTB held as depicted at reference numerals 68 and 70. Thereafter, during the cycle after WTB flush is accepted into the L3 pipeline, the WTB held copy of the write-through store requests access to the L3 cache and is placed on the L3 pipeline. When the WTB held is accepted from the pipeline, WTB held sees an invalid sector since it follows the synthesized flush operation. The original write-through store, WTB held, can now be passed directly to the main storage with no need to update the L3 cache since a cache hit will not occur for the write-through operation.

[0033] Referring now to FIG. 6 there is illustrated a high level logic flowchart of a process for passing a write-through store transaction from a higher level of cache to a lower level. As depicted, the process starts at block 100 and proceeds to block 101. Block 101 depicts a determination of whether or not there is a cache hit for the write-through store within a segment of the higher level cache, in particular the L2 cache. If there is not a cache hit, the process passes to block 102. Block 102 illustrates a determination of whether the original write-through store has 32 bytes of valid data. If the original size of the write-through operation is 32 bytes of valid data, the process passes to block 108. Block 108 depicts setting the 32-byte bit for the write-through transaction whereafter the process passes to block 109. If the original size of the write-through operation is not 32 bytes of valid data, the process passes to block 109. Block 109 illustrates passing the write-through operation to the store queue of the L3 cache whereafter the process returns.

[0034] Returning to block 101, if there is a cache hit, the process passes to block 104. Block 104 depicts a determination of whether or not all 32-bytes have been transacted. If all 32 bytes have been transacted, the process passes to block 103. Block 103 illustrates setting the 32-byte bit for the write-through store operation in the store queue.

[0035] Returning to block 104, if all 32 bytes of data are not yet transacted, the process passes to block 105. Block 105 illustrates a determination of whether or not the byte of data is a write-through byte of data. If the data is a write-through byte of data, the process passes to block 106. Block 106 depicts setting the write enable signal for each write-through data byte whereafter the process passes to block 104. If the data is not a write-through byte of data, the process passes to block 107. Block 107 illustrates setting the write enable signal off, such that data is read out of the L2 cache whereafter the process passes to block 104.

[0036] With reference now to FIG. 7 there is depicted a high level logic flowchart of a process for issuing a write-through store operation to L3 cache. As illustrated, the process starts at block 110 and proceeds to block 112. Block 112 depicts a determination of whether or not a 32-byte bit is set for the write-through operation being processed next from the store queue. If the 32-byte bit is not set for the write-through store operation, the process passes to block 114. Block 114 illustrates holding a copy of the write-through operation in a held write-through register. Thereafter, block 116 depicts sending a flush command for the write-through operation to the cache pipeline. Next, block 118 illustrates a determination of whether or not the data in the cache to be flushed is marked as modified. If the data in the cache is marked as modified, the process passes to block 120. Block 120 depicts the generation of a cast out transaction for the data in the cache such that the data is written to another memory level, preferably system memory 18 of FIG. 1. Thereafter, the process passes to block 122. If the cache is not marked modified, the process passes to block 122. Block 122 illustrates marking the data in the cache to be flushed as invalid. Thereafter, block 124 depicts sending the write-through operation in the held write-through register to the L3 cache pipeline. Next, block 126 illustrates passing the write-through operation onto the bus whereby other caches and memory locations may be updated. Since the matching data in the cache is flushed, the write-through operation will not encounter a cache hit in the L3 cache, and therefore will pass the write-through operation on to the next memory level without writing to the L3 cache.

[0037] Returning again to block 112, if the 32-byte bit for the write-through operation being processed next is set, the process passes to block 128. Block 128 depicts sending the write-through operation to the pipeline. Thereafter, block 130 illustrates a determination of whether or not there is a cache hit in the L3 cache for the write-through operation. If there is a cache hit in L3 cache, the process passes to block 132. Block 132 depicts writing the write-through operation data to the L3 cache whereafter the process passes to block 134. If there is not a cache hit in L3 cache, the process passes to block 134. Block 134 illustrates passing the write-through operation to the next memory level whereafter the process returns.

[0038] While the invention has been particularly shown and 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.