Data error correction device and methods thereof

A method and device for error detection includes performing error detection for each data word received in a burst access to a memory. When no error is detected, the data words are written to a cache and indicated as valid data. In response to detecting an error in a data word, the error is corrected and the corrected data written to the cache without indicating the data as valid. In addition, the location of the detected error, indicating the data symbol associated with the error, is recorded in an error vector. The error vectors associated with each data word in the burst access are compared to determine whether a detected error was properly corrected.

FIELD OF THE DISCLOSURE

The present disclosure relates to data processing devices and more particularly to error correction for data processing devices.

BACKGROUND

Data processing devices, such as computer servers, are sometimes used in environments where outages can cause major disruptions to operations. Such outages can be caused by memory failures. Accordingly, it is typically desirable to design the data processing device with sufficient redundancy so the device can continue operations even when a particular memory module fails. Some data processing devices employ error correcting codes (ECC) to improve memory reliability.

ECC's typically use Reed-Solomon codes which over-sample a polynomial constructed from the data. The polynomial evaluation is called the check field and is saved with the data in memory. The check field provides for reconstruction of the original data if part of the data, or the check field itself, is lost or garbled. Data is organized in groups of bits called symbols. Loss of any or all bits in a symbol may be recovered. Typically, all data bits from each memory chip are fully contained in a symbol, so loss of any or all bits of a memory chip is fully recoverable. Memory chip width thus determines symbol size.

In particular, when a unit of data (referred to as a data word) is stored in memory, a memory controller calculates a set of checkbits (the check field) based on the value of the data being stored and stores the set of checkbits in memory along with the data. When the data word is requested from memory, the memory controller retrieves the data stored at the data word address and calculates a new set of checkbits. The memory controller compares the new set of checkbits to the stored set of checkbits, whereby a difference in the sets indicates an error in the stored word. In particular, in the event of an error the comparison of checkbits identifies the symbol in the data word where the error is located and which bits in the symbol are to be corrected.

The number of errors in a word that can be detected and corrected depends on the number of checkbits associated with the data word. This is determined by memory system geometry and is associated with intrinsic system characteristics such as cache line size. Cache line size cannot be changed without potentially affecting correct operation of existing programs. For example, in x86 servers with 64-byte cache line size, two 9 byte (72 bit) memory channels are typically coupled to provide 18 byte (144 bit) memory width. Memory chips typically provide data across a 4-beat burst, resulting in each access providing 72 bytes. This is organized as 64 bytes of data and 8 bytes (64 bits) of check bits.

x86 servers employing 4-bit memory chips typically organize ECC with 16 checkbits for each 128-bit data word, with each data word including 36 data symbols with 4 bits per symbol. Codes are often designed with an additional symbol for RAS (Reliability, Availability, and Serviceability). Typical codes provide correction of all single-symbol errors and guarantee detection of all double-symbol errors, providing correction of all single memory chip failures and detection of additional single-bit errors. Increasing symbol size for 8-bit memory chips results in 18 data symbols with 8-bits per symbol. Such an ECC is capable of correcting all single-symbol errors but cannot reliably detect all double-symbol errors. Theory shows that 6.67% of all double-symbol errors will be detected as a single-symbol error, resulting in an error misdetection and miscorrection. That value is too high to be acceptable in enterprise-class servers. Although the likelihood of error misdetection can be eliminated by increasing the number of checkbits associated with a data word, this undesirably increases memory size and is incompatible with cache line size.

The probability of error misdetection can also be reduced by interleaving the bits of multiple data words prior to transmitting the bits to the memory controller for error detection. The data words are reassembled at the memory controller for error detection and correction. Interleaving of the data words reduces the likelihood that a transmission error will cause multiple errors in a single data symbol. However, interleaving undesirably increases memory access latency. Accordingly, an improved method and device for correcting errors in stored data would be useful.

DETAILED DESCRIPTION

A method and device for error detection is disclosed. The method includes performing error detection for each data word received in a burst access to a memory. When no error is detected, the data words are written to a cache and indicated as valid data. In response to detecting an error in a data word, the error is corrected and the corrected data written to the cache without indicating the data as valid. In addition, the location of the detected error, indicating the data symbol associated with the error, is recorded in an error vector. The error vectors associated with each data word in the burst access are compared to determine whether a detected error was properly corrected. The validity of the corrected data is not indicated until after the comparison to ensure that miscorrected data is not accessed. Thus, valid data is made available before error detection is performed on all data words in the burst access, reducing latency, while the comparison of error vectors reduces the likelihood of error miscorrection.

In particular, as described further herein, ECC properties can be utilized so that ECC check field size is increased in response to an error situation. This reduces error miss-correction probability. For example, in one embodiment, during normal (non-error) operation, error detection and correction proceeds as a (19, 16) single symbol error correcting code with a symbol size eight. The data is forwarded to a cache for storage immediately. Check field size is adaptively increased in response to determining a correction cycle is required. Further, if correction is required, data forwarding to the cache is delayed until additional data beats have been examined for errors.

As described herein, a syndrome resulting from a multi-symbol error in symbol columns i and j will not alias to a syndrome produced by single errors in either symbol columns i or j. Accordingly, a transient error mixed in the same memory access as a hard fault will change the indicated symbol-in-error. This is because the hard fault will result in an error across all data beats of the memory access while the transient error will typically result in an error in a single data beat. Thus, the difference in single and multi-symbol errors can be detected by comparing the first detected symbol-in-error against errors detected in other data beats of the memory access. A hard fault will typically point to one symbol-in-error while a transient error will point to a different one.

Use of the above described technique reduces the likelihood of error misdetection and miscorrection. In a particular embodiment, such as an x86 data processing device, each data word includes 18 data symbols of 8 bits each, with two of the symbols containing checkbits. If an error occurs, check field size is dynamically increased to improve error detection capability. This configuration provides for single error correction (SEC) and acceptable values for double error detection (DED). The above described technique can reduce probability of misdetection of a double error as a single error to less than 0.00000038%.

The use of error vectors to record error locations for detected errors in a burst access effectively increases the number of ECC checkbits for each beat in the burst access. This can be better understood with reference toFIG. 1, which illustrates a flow diagram of a particular—embodiment of a method of detecting errors for data stored at a memory. At block102, a data word and associated ECC checkbits are received. At block104, it is determined based on the ECC checkbits whether the data word includes an error. If not, at block106the data word is written to a cache. The method flow moves to block120and it is indicated that the cache line including the word stores valid data.

If, at block104, an error is detected, at block108the error is corrected using the ECC checkbits. The corrected data is stored to the cache at block110. At block112, the effective ECC checkbit size is expanded. In an embodiment, the ECC checkbit size is expanded by detecting errors for other data words of a memory burst associated with the corrected data word. At block114, it is determined whether an error is detected based on the expanded ECC checkbit. If not, this indicates that no misdetection occurred. Accordingly, the method flow moves to block120and it is indicated that the cache line associated with the corrected data stores valid data. If, at block114, an error is detected based on the expanded checkbit size, this indicates an error misdetection for the stored corrected data. This misdetection is reported at block116. In response, appropriate action can be taken; e.g. a memory controller can indicate the corrected data stored at the cache is invalid data.

FIG. 2illustrates a flow diagram of a particular embodiment of a method of detecting errors for data stored at a memory. At block202, a beat in a memory burst is received. The beat includes a data word and associated ECC checkbits. At block204, it is determined, based on the ECC checkbits whether an error is detected in the data word. If not, the method proceeds to block206and the data word is written to the cache. The method flow proceeds to block218, discussed further below.

If, at block204it is determined that the data word includes an error, the method flow proceeds to block212and the error is corrected based on the ECC checkbits. At block214, the corrected data word is written to the cache at a cache line. At block216an error vector associated with the data word is stored, whereby the error vector indicates a location of the detected error. At block218it is determined whether all beats in the memory access burst have been received. If not, the method flow returns to block202to receive additional beats. If all beats have been received, at block220it is determined whether an error was detected for any data words associated with the access burst. If not, at block232it is indicated that the cache line associated with the access burst stores valid data.

If, at block220, it is determined that an error was detected for the access burst, at block222the error vectors are compared to determine the relative locations of detected errors. At block224, it is determined based on the comparison whether a misdetection has occurred. If not, the method moves to block232and it is indicated that the cache line associated with the access burst stores valid data. If a misdetection has occurred, the method moves to block230and the misdetection is reported.

FIG. 3illustrates a block diagram of a particular embodiment of a data processing device300including a memory controller304, a cache305, and a memory308. The memory controller304is connected to a bus370, labeled ADDR1, a bus371labeled CTRL, and a bus372labeled DATA. The memory controller104also includes connections to bi-directional busses374and375. It will be appreciated that although for purposes of discussion busses373-376are illustrated as single bi-directional busses, each illustrated bus can represent multiple uni-directional busses. For example, bus375can represent separate address and data busses. The cache305includes a connection to the bus374. The memory308includes a connection to the bus375.

The memory308is volatile memory, such as random access memory (RAM), and includes a number of memory locations, such as memory locations341,342,343, and344. Each memory location is associated with a unique memory address. In response to receiving a memory address via the bus375, the memory308provides information stored at the associated memory location via the bus375. Each memory location of the memory308is configured to store multiple types of information, including a data word, checkbits associated with the data word, and (optionally) Reliability, Availability, and Serviceability (RAS) information associated with the data word. RAS information is typically encoded in a spare symbol not affiliated with specific sets of memory bits. Rather, the data affiliated with that symbol is implied to be zero and does not require real memory bits. Storing non-zero RAS information results in unique check bit encodings which result in a single-symbol error in the spare symbol location. Indicated bits-in-error identify the original encoded RAS information. For example, at memory location341, the memory stores data word351(labeled DAT1), checkbits352(labeled ECC1), and RAS information353(labeled RAS1). The RAS information represents information designated to enhance the reliability, serviceability, and availability of the data351.

The cache305includes a number of cache locations, such as cache lines361,362,363, and364, whereby each cache line is associated with a unique cache TAG. Each cache line stores multiple types of information, including a data word and validity information associated with the data. For example, cache location361stores data381and associated validity information365. The validity information indicates whether the associated data is valid for use in operations at the data processing device300.

The memory controller304is configured to receive and fulfill memory access requests by providing the requested data. In addition, the memory controller304is configured to manage the storage of data between the memory308, and the cache305so that memory access requests can be efficiently fulfilled. In an embodiment, the memory controller304is configured to ensure that recently requested data is available at the cache305and less recently requested data is available at the memory308. Moreover, the memory controller304ensures that there is data redundancy, so that data stored at the cache305is maintained at the memory308.

To illustrate, a memory access request is initiated at the memory controller304when an address is received via the bus370. In response, the memory controller304determines whether the data associated with the address is stored at the cache305. If so, the memory controller304retrieves the requested data word by providing the cache address associated with the data word via the bus374, and receiving the requested data word via the same bus. The memory controller304then provides the requested data word to the bus372, and provides information via the bus371indicating completion of the memory access request.

If the requested data word is not located at the cache305and is located at the memory308, the memory controller304copies the requested data from the memory308to the cache305, as described below.

To copy data from the memory308to the cache305the memory controller304executes a burst access. As used herein, the term “burst access” refers to retrieving multiple data words from memory in multiple iterations. For purposes of discussion, retrieval of each data word is referred as a “beat” of the burst access. Thus, for purposes of discussion an N-beat burst access refers to a burst access wherein N data words are retrieved. In a particular embodiment, N is 4.

A burst access can be better understood with reference to an example. In the illustrated embodiment ofFIG. 3, the memory308stores data words DATA1, DATA2, DATA3, and DATA4, together with associated ECC checkbits and RAS information, at memory locations341,342,343, and344, respectively. The memory controller304receives an address associated with the data word DATA1via the bus370. In response, the memory controller304determines that DATA1is stored at the memory308, and provides the associated memory address via the bus375. This initiates a burst access, whereby data words DATA1, DATA2, DATA3, and DATA4, together with their associated ECC checkbits and RAS information, are provided in a series of 4 beats. In particular, for the first beat the data word DATA1, ECC checkbits ECC1, and RAS information RAS1are provided via the bus375, for the second beat the data word DATA2, ECC checkbits ECC2, and RAS information RAS2, and so on.

The memory controller304performs error detection and error correction for each beat in the burst access. In particular, the ECC module310performs error correction based on the ECC checkbits associated with the data word. Until an error is detected, the memory controller304copies each data word to the cache and indicates the data is valid in the associated validity information at the cache. In addition, if the target data identified by the received address is indicated as valid data, the memory controller304provides the data immediately via the bus372, and indicates the data has been retrieved via the bus371, so that the associated instruction can be retired.

In response to detecting an error in a beat of a burst memory access, the ECC module310determines if the error is correctable. If not, the ECC module informs the memory controller304, which can take appropriate action. For example, the memory controller304can attempt to re-copy the data from the memory308, or retrieve the data from the non-volatile memory306. If the ECC module310determines that the error is correctable, it stores an error vector at the error vectors320to indicate the symbol containing the error.

The error vectors320can be better understood with reference toFIG. 4, which illustrates a data word402and a corresponding error vector404. In the illustrated embodiment, the data word402includes 8 data symbols, numbered 0 through 7. Each data symbol represents one or more bits of the data word402. The error vector404includes fields numbered 0 through 7, with each field associated with the corresponding symbol of the data word420. The value stored at each field of the error vector404is indicative of whether an error has been detected at the corresponding symbol of the data word402. In the illustrated embodiment, a value of “0” indicates no error has been detected, while a value of “1” indicates an error has been detected. Thus, in the illustrated example ofFIG. 4, field406indicates an error has been detected in symbol2of the data word402.

In response to detecting an error in a beat of a burst access, the ECC module310records error vectors for the data associated with that beat and for the data associated with each subsequent beat at the error vectors420. The recorded error vectors are compared to determine whether any detected error is a correctable or uncorrectable error. This can be better understood with reference toFIGS. 5-8, which illustrate exemplary error vectors and associated memory access beats.

FIG. 5illustrates a sequence500of beats of a memory access. Table501indicates the location of errors and valid data for data transmitted from the memory308to the memory controller memory controller304. In particular, table501sets forth the locations of errors for beats502,504,506, and508. For purposes of discussion, a “P” in table501indicates no error is present for the corresponding symbol, while an “F” indicates an error for the corresponding symbol. Thus, table501indicates there is an error for symbol1of the data associated with each of beats502-508, and also indicates an error for symbol4of the data associated with beat502.

Table511indicates the detected errors at the ECC module510for each of the beats502, whereby rows512,514,516, and518correspond to the detected errors for beats502,504,506, and508, respectively. Thus, in the illustrated embodiment, rows514,516, and518indicate an error has been detected in symbol1of each the data words associated with data beats504,506, and508. As illustrated by table501, this indicates that the ECC module310has correctly detected the errors for these data beats. However, row352indicates that ECC module512has detected for symbol2of the data word associated with beat502. As illustrated in table501, the detected errors indicated by row512do not correspond to the actual errors in the transmitted data associated with beat502, indicating a misdetection.

Table521illustrates a table521showing error vectors522,524,526, and528, based on the detected errors reflected in table511. In particular, vectors522,524,526, and528correspond to rows512,514,516, and518of table511respectively, and indicate the location of detected errors in the data words associated with the data beats502-508.

In operation, in response to detecting an error in beat502, the ECC module310records error vector522to record the location of the detected error, and also records error vectors524-528to record the locations of detected errors for the corresponding data beats. After recording the error vectors522-528, the ECC module310compares the locations of the detected errors and determines whether a misdetection has occurred. Accordingly, in the illustrated example ofFIG. 5, the ECC module310determines that 3 of the 4 error vectors522-528indicated a detected error at symbol1of the corresponding data beat. This indicates a likelihood that a memory chip corresponding to those symbols has a faulty storage location, and further implies that data beat502should have a similar error at symbol1. However, because error vector522, associated with the beat502, does not indicate an error in symbol1, and indicates an error in another symbol (symbol2), the ECC module310determines that the detected error for beat502was a mis-detection. In response, the memory controller304indicates in the cache305that the data associated with all beats are likely to be invalid. It is possible that error data may alias to the original stored data in any given beat. In that case, no error is indicated or correction applied to that beat and the error vector is not considered in error vector comparison.

Referring toFIG. 6, a set600of memory access beats and associated error vectors is illustrated. Tables601,611, and621correspond to tables501,511, and521ofFIG. 5, respectively, and set forth similar information. Accordingly, in the illustrated example ofFIG. 6, the only error in the data words associated with beats602,604,606, and608is at symbol2of each data word associated with beat602. Rows612,614,616, and618of table611indicate that the errors are detected correctly at the ECC module620. In response to detecting the error for beat602, the ECC module420records error vectors622,624,626, and628and compares the indicated error locations. Based on this comparison, the ECC module620determines that the error for the data associated with beat602was correctly detected and corrected. In response, the memory controller indicates that the associated data word stored at the cache305is valid data.Referring toFIG. 7, a set700of memory access beats and associated error vectors is illustrated. Tables701,711, and721correspond to tables501,511, and521ofFIG. 3-5, respectively, and set forth similar information. Accordingly, in the illustrated example ofFIG. 7, no errors are present or detected for beat702. Errors are present in symbols2and4of the data word associated with beat704. However, as indicated by row714of table711, the errors for beat704are misdetected as a single error at symbol5. In addition, errors are present at symbol2of data words associated with beat706and708, respectively. As indicated by rows716and718of table711, these errors are correctly detected by the ECC module110.The ECC module110compares the error locations indicated by error vectors722,724,726, and728. Because all non-zero error vectors did not agree, beats with non-zero error vectors are considered invalid. Accordingly, the memory controller indicates that associated data word(s) stored at the cache305are invalid.Referring toFIG. 8, a set800of memory access beats and associated error vectors is illustrated. Tables801,811, and821correspond to tables501,511, and521ofFIG. 3-5, respectively, and set forth similar information. Accordingly, in the illustrated example ofFIG. 8, actual errors are present at symbols1and2of beat806and symbol2of beat808. As illustrated by table811, errors are detected at symbol4of beat806and at symbol1of beat818. Table821illustrates the error vectors for each of the beats. Because all non-zero error vectors did not agree, beats with non-zero error vectors are considered invalid.

Returning toFIG. 3, when determining where to store data at the cache305, the memory controller304determines whether space is available in the cache, whereby space availability depends in part on whether valid data is stored at a cache location. Thus, a cache location that stores invalid data is indicated as available space in the cache305. The memory controller304writes data words to available space in the cache305. Accordingly, by identifying a miscorrected data word as invalid data, the memory controller304ensures cache location associated with that data word becomes available to store new data.

Other embodiments, uses, and advantages of the disclosure will be apparent to those skilled in the art from consideration of the specification and practice of the disclosure disclosed herein. It will further be appreciated that, although some circuit elements and modules are depicted and described as connected to other circuit elements, the illustrated elements may also be coupled via additional circuit elements, such as resistors, capacitors, transistors, and the like. The specification and drawings should be considered exemplary only, and the scope of the disclosure is accordingly intended to be limited only by the following claims and equivalents thereof.