Cache directory array recovery mechanism to support special ECC stuck bit matrix

[0001] The present application is related to copending U.S. patent application Ser. No. 10/418,589 entitled “APPLICATION OF SPECIAL ECC MATRIX FOR SOLVING STUCK BIT FAULTS IN AN ECC PROTECTED MECHANISM” filed Apr. 17, 2003.

[0002] 1. Field of the Invention

[0003] The present invention generally relates to data processing systems, and more particularly to a method and system for correcting an erroneous data bit in a computer system, such as in a cache memory, a bus or communications link, a chip interface, or other locations where error correction code (ECC) may be used.

[0004] 1. Description of the Related Art

[0005] The basic structure of a conventional computer system 10 is shown in FIG. 1. Computer system 10 may have one or more processing units, two of which 12a and 12b are depicted, which are connected to various peripheral devices, including input/output (I/O) devices 14 (such as a display monitor, keyboard, and permanent storage device), memory device 16 (such as random access memory or RAM) that is used by the processing units to carry out program instructions, and firmware 18 whose primary purpose is to seek out and load an operating system from one of the peripherals (usually the permanent memory device) whenever the computer is first turned on. Processing units 12a and 12b communicate with the peripheral devices by various means, including a generalized interconnect or bus 20. Computer system 10 may have many additional components which are not shown, such as serial, parallel and universal bus ports for connection to, e.g., modems or printers. Those skilled in the art will further appreciate that there are other components that might be used in conjunction with those shown in the block diagram of FIG. 1; for example, a display adapter might be used to control a video display monitor, a memory controller can be used to access memory 16, etc. Also, instead of connecting I/O devices 14 directly to bus 20, they may be connected to a secondary (I/O) bus which is further connected to an I/O bridge to bus 20. The computer can have more than two processing units.

[0006] In a symmetric multi-processor (SMP) computer, all of the processing units are generally identical, that is, they all use a common set or subset of instructions and protocols to operate, and generally have the same architecture. A typical architecture is shown in FIG. 1. A processing unit includes a processor core 22 having a plurality of registers and execution units, which carry out program instructions in order to operate the computer. An exemplary processing unit includes the PowerPC™ processor marketed by International Business Machines Corp. The processing unit can also have one or more caches, such as an instruction cache 24 and a data cache 26, which are implemented using high speed memory devices. Caches are commonly used to temporarily store values that might be repeatedly accessed by a processor, in order to speed up processing by avoiding the longer step of loading the values from memory 16. These caches are referred to as “on-board” when they are integrally packaged with the processor core on a single integrated chip 28. Each cache is associated with a cache controller (not shown) that manages the transfer of data between the processor core and the cache memory.

[0007] A processing unit 12 can include additional caches, such as cache 30, which is referred to as a level 2 (L2) cache since it supports the on-board (level 1) caches 24 and 26. In other words, cache 30 acts as an intermediary between memory 16 and the on-board caches, and can store a much larger amount of information (instructions and data) than the on-board caches can, but at a longer access penalty. For example, cache 30 may be a chip having a storage capacity of 256 or 512 kilobytes, while the processor may be an IBM PowerPC™ 604-series processor having on-board caches with 64 kilobytes of total storage. Cache 30 is connected to bus 20, and all loading of information from memory 16 into processor core 22 usually comes through cache 30. Although FIG. 1 depicts only a two-level cache hierarchy, multi-level cache hierarchies can be provided where there are many levels of interconnected caches.

[0008] A cache has many “blocks” which individually store the various instructions and data values. The blocks in any cache are divided into groups of blocks called “sets” or “congruence classes.” A set is the collection of cache blocks that a given memory block can reside in. For any given memory block, there is a unique set in the cache that the block can be mapped into, according to preset mapping functions. The number of blocks in a set is referred to as the associativity of the cache, e.g. 2-way set associative means that for any given memory block there are two blocks in the cache that the memory block can be mapped into; however, several different blocks in main memory can be mapped to any given set. A 1-way set associate cache is direct mapped, that is, there is only one cache block that can contain a particular memory block. A cache is said to be fully associative if a memory block can occupy any cache block, i.e., there is one congruence class, and the address tag is the full address of the memory block.

[0009] An exemplary cache line (block) includes an address tag field, a state bit field, an inclusivity bit field, and a value field for storing the actual instruction or data. The state bit field and inclusivity bit fields are used to maintain cache coherency in a multiprocessor computer system (to indicate the validity of the value stored in the cache). The address tag is a subset of the full address of the corresponding memory block. A compare match of an incoming address with one of the tags within the address tag field indicates a cache “hit.” The collection of all of the address tags in a cache (and sometimes the state bit and inclusivity bit fields) is referred to as a directory, and the collection of all of the value fields is the cache entry array.

[0010] When all of the blocks in a congruence class for a given cache are full and that cache receives a request, whether a “read” or “write,” to a memory location that maps into the full congruence class, the cache must “evict” one of the blocks currently in the class. The cache chooses a block by one of a number of means known to those skilled in the art (least recently used (LRU), random, pseudo-LRU, etc.) to be evicted. If the data in the chosen block is modified, that data is written to the next lowest level in the memory hierarchy which may be another cache (in the case of the L1 or on-board cache) or main memory (in the case of an L2 cache, as depicted in the two-level architecture of FIG. 1). By the principle of inclusion, the lower level of the hierarchy will already have a block available to hold the written modified data. However, if the data in the chosen block is not modified, the block is simply abandoned and not written to the next lowest level in the hierarchy. This process of removing a block from one level of the hierarchy is known as an “eviction.” At the end of this process, the cache no longer holds a copy of the evicted block.

[0011] FIG. 2 illustrates the foregoing cache structure and eviction process. A cache 40 (L1 or a lower level) includes a cache directory 42, a cache entry array 44, an LRU array 46, and control logic 48 for selecting a block for eviction from a particular congruence class. The depicted cache 40 is 8-way set associative, and so each of the directory 42, cache entry array 44 and LRU array 46 has a specific set of eight blocks for a particular congruence class as indicated at 50. In other words, a specific member of the congruence class in cache directory 42 is associated with a specific member of the congruence class in cache entry array 44 and with a specific member of the congruence class in LRU array 46, as indicated by the “X” shown in congruence class 50.

[0012] Each of the blocks in directory 42 are connected to the control logic via an error correction code (ECC) circuit 52. A bit in a given cache block may contain an incorrect value, either due to a soft error (such as stray radiation or electrostatic discharge) or to a hard error (a defective cell). ECCs can be used to reconstruct the proper data stream. Some ECCs can only be used to detect and correct single-bit errors, i.e., if two or more bits in a particular block are invalid, then the ECC might not be able to determine what the proper data stream should actually be, but at least the failure can be detected. Other ECCs are more sophisticated and even allow detection or correction of double errors. These latter errors are costly to correct, but the design tradeoff is to halt the machine when double-bit errors occur. Although only directory 42 is shown with ECC circuits, these circuits can similarly be used with other arrays, such as cache entry array 44.

[0013] The outputs of ECC circuits 52, whose values correspond to (corrected) memory block addresses, are connected to respective comparators 54 each of which also receives the address of the requested memory block. If a valid copy of a requested memory block is in the congruence class 50, then one, and only one, of the comparators 54 will output an active signal. The outputs of comparators 54 are connected to a multiplexer 56 and also to an OR gate 58, whose output controls multiplexer 56. If a cache hit occurs (a requested address matches with an address in cache directory 42), then OR gate 58 activates multiplexer 56 to pass on a signal indicating which member of the congruence class matches the address. This signal controls another multiplexer 60 which receives inputs from each of the entries in cache entry array 44. In this manner, when a cache hit in the directory occurs, the corresponding value is passed through multiplexer 60 to a bus 62.

[0014] If a cache miss occurs, and if all of the blocks in the particular congruence class 50 already have valid copies of memory blocks, then one of the cache blocks in congruence class 50 must be selected for victimization. This selection is performed using the LRU bits for the congruence class in LRU array 46. For each cache block in the class, there are a plurality of LRU bits, for example, three LRU bits per block for an 8-way set associative cache. The LRU bits from each block in the class are provided as inputs to a decoder 64 having an 8-bit output to indicate which of the blocks is to be victimized. This output is coupled to multiplexer 56. In this manner, if OR gate 58 is not active, multiplexer 56 passes on an indication of the cache block to be used based on the outputs of decoder 64.

[0015] The ECC circuits discussed above are one way to deal with soft errors arising in memory cells. Another approach used for dealing with hard errors is to provide redundancy within the arrays (directory, LRU, cache). When a cache chip is fabricated, it can be tested to determine if there are any defective row or column lines in each of the arrays (row and column lines are tested for the entire cache, directory, and LRU). If an array is defective, a fuse can be permanently blown to indicate its defective nature. A comparison is then made inside the array for each accessed address to see if it matches with a defective address. If so, appropriate logic re-routes the address to one of many extra row and column lines formed on the chip, i.e., from redundant bit lines (columns) and word lines (rows). The number of extra bit and word lines may vary depending upon the defect rate and desired chip yield. For a low-defect (larger physical size) cache, two extra lines might be provided for every 256 regular lines, while in a high-defect (smaller physical size) cache, two extra lines might be provided for every eight regular lines.

[0016] With advancements in chip fabrication and computer configurations, L2 and L3 caches are increasing in size, requiring larger on-chip directories and on-chip (or off-chip) data cache entry arrays. These larger, dense arrays decrease the reliability of the overall chip/system due to increased chances of defects that occur in manufacturing or in the field. In order to increase the reliability of these larger directory/data caches, many different means have been traditionally employed to address these problems, such as in-line parity or ECC detection/correction, but there are several disadvantages and limitations with the foregoing approaches. While soft errors (i.e., intermittent faults) are correctable using ECC circuits that repair and re-write the data in the directory, this technique does not solve hard faults where a cache directory bit is stuck either high or low. In-line ECC correction can be used to correct stuck faults, but this approach penalizes access time to the array, since correction is needed with each access, and repeatedly consumes part of the error correction capability. The use of redundant cache lines can partially overcome hard faults, but these redundant structures are wasteful as they take up valuable space on the chip or system board. Redundancy is also limited in its ability to correct a large number of defects. Moreover, hard errors that arise after testing may be not correctable using redundant lines. When these types of hard faults occur, conventional ECC circuits that try to repair and re-write the data will lead to a situation wherein the system repetitively attempts to correct the error without success. In this situation, the machine cannot recover and must be brought down and repaired, costing customers time and money, if full error correction and detection resources are to be maintained.

[0017] In light of the foregoing, it would be desirable to devise and improved method for detecting/correcting hard errors in memory devices such as caches. It would be further advantageous if the method could be implemented without requiring wasteful redundant circuitry or in-line correction which penalizes directory access time and consequently degrades system performance.

[0018] It is therefore one object of the present invention to provide an improved memory structure for a computer system, particularly a cache memory.

[0019] It is another object of the present invention to provide such an improved cache memory which utilizes error correction code (ECC).

[0020] It is yet another object of the present invention to provide an improved method and system for detecting and correcting errors in a computer system, whether in a cache memory or on a system bus, which can solve a hard error (stuck bit) condition without resorting to slow in-line correction.

[0021] The foregoing objects are achieved in a method of correcting an error in a data bit of a computer system, by applying data with a number of bits N to an error correction code (ECC) matrix to yield an error detection syndrome, wherein the ECC matrix has a plurality of rows and columns with a given column corresponding to a respective one of the data bits, and selected bits are set in the ECC matrix along each column and each row such that encoding for the ECC matrix allows N-bit error correction and (N−1)-bit error detection. The resulting error detection syndrome is resolved to detect the error in the data as read from a location of the data processing system. In the illustrative embodiment, the ECC matrix has an odd number of bits set in each row thereof. These properties facilitate the use of an inversion bit for correcting hard faults in the stored data. When an error is dctectcd and after it is corrected, the corrected data is inverted and then rewritten to the storage or transmission media. The corresponding inversion bit for this entry is accordingly set to indicate that the data as currently stored is inverted. Thereafter, the data is re-read fronn the media, and if the error was due to a hard fault (stuck bit), it will appear correct (after applying the polarity indicated by the inversion bit), since the inversion will have changcd the value of the defective bit to the stuck value. The inversion bit may be part of the data itself. In this case, one of the columns in the ECC matrix corresponds to the inversion bit, and each bit in that column of the matrix is set. This matrix may be applied to any location of a computer system which uses ECC, including a bus or communications link or a chip interface, and is particularly useful for memory devices such as cache memory. By including the inversion bit on a system bus with the data, the system bus can invert the polarity of the data to compensate for a known stuck bit on the bus. The particular configuration of the ECC matrix allows detection and correction even if the error arises in the inversion bit (creating an otherwise undetectable error), wherein all of the bits of the data are erroneous because of the effect of the erroneous inversion bit. The ECC matrix defined in this invention will allow for correction/detection on any of the data and ECC bits including errors on the inversion bit itself. This technique allows a system bus to maintain full ECC protection even in the presence of a stuck bit.

[0022] The above as well as additional objectives, features, and advantages of the present invention will become apparent in the following detailed written description.

[0029] The use of the same reference symbols in different drawings indicates similar or identical items.

[0030] As explained in the Background section, conventional error correction code (ECC) circuitry is inadequate for addressing hard errors (stuck bits) in computer devices such as a memory array (e.g., cache) or communications link (e.g., system bus). The present invention solves the problems of stuck bits through a new hardware mechanism that uses a special ECC matrix to recover from stuck fault directory array conditions. The ECC matrix is adapted to apply to a new bit that is included with the cache directory address/tag or system bus transmission, an additional “inversion” bit which indicates the relative polarity of the stored information. The following description implements the invention in a third level (L3) cache directory array, but those skilled in the art will appreciate that it is equally useful for other memory devices which store values (program instructions or operand data).

[0031] FIG. 3A shows an ECC matrix 70 that is designed, according to prior art techniques, for a 48-bit value which includes 41 data bits and 7 ECC bits. This matrix may be used in a conventional manner to check an address tag for any error. If all of the 48 stored bits are correct, then application of the ECC matrix of FIG. 3A will result in a syndrome of all zeros, to indicate that no correction is necessary. The 48-bit value is applied separately to each of the seven rows of the matrix in an XOR fashion, to respectively yield the seven bits of the syndrome. If only one bit is erroneous, the resulting syndrome can be used to detect which bit is in error. In this original ECC matrix 70, as well as all traditional ECC matrices that cover single-bit correct/double-bit detect (SBC/DBC) errors, there are an odd number of bits set in each column that defines the signature for a correctable bit. While some of the rows have an odd number of bits set, other rows have an even number, such as rows 1 and 7 in matrix 70 which each have 20 bits set.

[0032] FIG. 3B shows a representation of an electronic ECC matrix 72 for a 48-bit value which has been modified according to the present invention. In this specific implementation, the modifications are twofold. First, one column of matrix 72 corresponds to an inversion bit that indicates the relative polarity (active-low or active-high) of the stored data, and this column has different bits set compared to the prior art matrix 70. For this example, the inversion bit (IB) is bit number 30 (out of data bits 0:40), and it can be seen in FIG. 3B that all of the bits in the corresponding column of matrix 72 have been set. Secondly, bits have been added to other columns of matrix 72, with the result that each horizontal row in the matrix has an odd number of bits set. As compared with prior art matrix 70, the specific changes made to matrix 72 to yield this characteristic are additional settings for the columns that correspond to data bits 1:2 (in addition to setting of all bits for IB column 30). In particular, two additional bits have been set in the column corresponding to data bit 1, and two additional bits have been set in the column corresponding to data bit 2. The modified columns (relative to prior art matrix 70) have been marked with asterisks in FIG. 3B. Those skilled in the art will appreciate that other settings may be used in similar 48,41 matrices to achieve the same result of all rows having an odd number of bits set. The inversion bit does not have to be accounted for with the ECC matrix.

[0033] With this novel matrix construction and the associated syndrome encoding, ECC matrix 72 acquires the properties for an “N” bit data field covered by the ECC of:

• • [0034] single-bit error detect;
  • [0035] multi-bit error correct;
  • [0036] N-bit error correct; and
  • [0037] (N−1)-bit error detect.
    These last two properties are useful since the inversion bit which indicates the polarity of the data, is also stored and covered by the ECC encoding. If there is a single-bit error on the polarity bit, then the data that is presented to the ECC check logic will have all “N” bits incorrect, but the matrix is built to detect and correct for this case. If a double-bit error occurs and one of the bits in error is the polarity bit, the matrix will also detect this property and indicate this is a double-bit error that is uncorrectable.

[0038] In the illustrative embodiment, the matrix is applied to 48 bits that include 41 data bits dat(0:40) and 7 ECC bits ecc(0:6). The 41 data bits include a 30-bit L3 address tag addr_tag(14:43) corresponding to dat(0:29), the inversion bit corresponding to dat(30), and 10 bits for cache state information (coherency and inclusivity bits) dir_state(0:9) corresponding to dat(31:40). Thus one polarity bit is provided for each entry in the cache directory. “Block code” type ECC encoding is used for this particular example.

[0039] The polarity bit stored in the L3 directory with the address tag and state information (and also covered by the ECC bits) indicates whether the information was stored into the L3 directory with either active-high or active-low polarity. When an ECC error is detected, the stored information can be written back into the L3 directory with the opposite (reverse) polarity. In this manner, a stuck bit fault will subsequently match the reverse polarity data and not cause an error on a subsequent read. The use of the inversion bit thus easily overcomes any single-bit error caused by a hard fault, without requiring redundant storage cells or in-line ECC detection/correction, and further carries out the inversion-correction procedure only as necessary, on-the-fly.

[0040] When a directory read is performed (i.e. at machine dispatch time), the raw/unchecked L3 directory data is sent in parallel thru a “tag compare” pipeline and to an ECC check pipeline. If an error is discovered, the directory machine dispatch sequence is aborted due to an ECC error, and a polarity error correction (PEC) sequence takes control of the directory so it can repair/re-write the directory with the corrected data. Meanwhile, the previously aborted dispatch, when re-attempted, will eventually be successful once the PEC sequence has repaired a single-bit “soft” correctable error (CE).

[0041] In order to mask a single stuck bit fault in the L3 directory (where the array cell is stuck at a 0 or 1), the PEC sequence now has the added ability to control the polarity of the data written to the directory array. The PEC sequence can invert the data written to the array by asserting the dw_invert_bit during a PEC sequence to mask a stuck bit (write the stuck value to the bit). The dw_invert_bit is stored in the directory to log whether the data is inverted in the directory and should thus be inverted when read out. Because the invert bit is stored in the directory, the matrix is enhanced to detect double bit errors and provide single bit correction on all bits including the invert bit as explained above. With the described modifications, ECC matrix 72 will correct single-bit faults on entry, including the dw_invert_bit (due to a soft error or a stuck bit) and will provide double bit error detection involving any two bits in an entry including a double bit error that involves the dw_invert_bit.

[0042] FIG. 4 illustrates the dataflow using the ECC matrix of FIG. 3B as applied to a directory for an 8-way set associative L3 cache. In the write circuitry 80 of the cache directory, the invert bit dw_invert_bit from the machine is first combined with the data by a multiplexer 82. The combined data is used by an ECC generator 84 to yield the ECC bits. Generation of the ECC bits uses the same syndrome encoding upon which ECC matrix 72 is based. The data also passes through an inverter 86 which is controlled by the invert bit, now dat(30). Normal direct writes by the machine (i.e., from a lower level cache or main memory) write the dw_invert_bit to 0. All of the data, including the invert bit and the ECC bits, are then combined with another multiplexer 88 and sent to a latch 90 for eventual writing to the L3 directory array 92.

[0043] While the invert bit controls the polarity at which dat(0:29) and dat(31:40) are written by inverter 86, the polarities of dat(30) and ecc(0:6) are unaffected by the inverter. The polarity of ecc(0:6) is effectively inverted via ECC matrix 72 by setting all of the bits in the column that corresponds to the invert bit (column 30). When dw_invert_bit is equal to zero, dat(0:29) and dat(31:40) will be written to the L3 directory as active high. When dw_invert_bit is equal to one, dat(0:29) and dat(31:40) will be written to the L3 directory as active low.

[0044] When the data is read from L3 directory array 92, it is first written to another latch 94, and then passed through another inverter 96 which is controlled by dat(30). Inversion may be disabled by setting a mode bit which is combined with dat(30) using an AND gate 98. The data, whose polarity has now been appropriately set, is forward to an ECC checker 100 which produces the syndrome, synd(0:6). ECC checker 100 uses ECC matrix 72, which can be hard-wired into the XOR circuitry. The data and syndrome are written to a latch 102 and multiplexer 104. The syndrome is resolved by a decoder 106. A syndrome of “0000000” signifies the data is correct (or at least no errors were detected). A syndrome of “1111111” signifies the data has a CE on the invert bit. Decoder 106 has a series of outputs fix_dat(n) which are individually active when the syndrome indicates a single-bit error for the particular data bit n (dat(0:29,31:40)). Another output fix_invert is active when the syndrome is “1111111”. The fix_dat(n) bits are first combined with the fix_invert bit at an OR gate 108, and then act on the data bits using an XOR gate 110. The fix_invert bit is also applied to the invert bit dat(30) at XOR gate 112. All of the data bits dat(0:40) are then passed to the output latch 114.

[0045] All double-bit errors will result in a synd(0:6) that doesn't match a legal CE syndrome. Because the signature of the synd(0:6) values for CE cases have an odd number of bits set in their signature (including a CE on the dw_invert_bit which has all 7 bits set), a double-bit error will result in the synd(0:6) having an even number of bits set (including the case where the dw_invert_bit itself is involved). ECC matrix 72 has the property that, when you combine two CE syndromes, the resulting syndrome will have an even number of synd(0:6) bits set which indicates a double bit error.

[0046] Although the invention has been described with reference to specific embodiments, this description is not meant to be construed in a limiting sense. Various modifications of the disclosed embodiments, as well as alternative embodiments of the invention, will become apparent to persons skilled in the art upon reference to the description of the invention. For example, the above-description applies the ECC matrix and inversion bit to an address tag for a cache entry (i.e., to the cache directory), but it could also be applied to the cache entry array which holds the values (program instructions or operand data) to which an address tag points. The above-described matrix can also be applied to any element in the system that carries ECC protection, including a system bus. By adding an inversion bit to a system bus and using the inversion technique described above, the system bus can maintain full ECC protection even in the presence of a stuck bit, by inverting the data to always match the stuck bit logic level. It is therefore contemplated that such modifications can be made without departing from the spirit or scope of the present invention as defined in the appended claims.