Performing multi-bit error correction on a cache line

• US 8,245,111 B2
• Filed: 12/09/2008
• Issued: 08/14/2012
• Est. Priority Date: 12/09/2008
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Khellah, Muhammad, Lu, Shih-Lien, Chishti, Zeshan A., Alameldeen, Alaa R., Wilkerson, Chris, Wu, Wei, Somasekhar, Dinesh
• Primary Examiner(s): Duncan, Marc
• Application Number:
  US12/331,255
• Publication Number:
  US 20100146368A1
• Time in Patent Office: 1,344 Days
• Field of Search: 714/752, 714/766
• US Class Current: 714/766
• CPC Class Codes: G06F 11/1064 in cache or content addressable memories
• CPC Class Codes: H03M 13/1102 Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
• CPC Class Codes: H03M 13/13 Linear codes
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/2918 with error correction codes in three or more dimensions, e.g. 3-dimensional product code where the bits are arranged in a cube
• CPC Class Codes: H03M 13/2921 wherein error correction coding involves a diagonal direction

Abstract

A processor may comprise a cache, which may be divided into a first and second section while the processor operates in a low-power mode. A cache line of the first section may be fragmented into segments. A first encoder may generate first data bits and check bits while encoding a first portion of a data stream and a second encoder may, separately, generate second data bits and check bits while encoding a second portion of the data stream. The first data bits may be stored in a first segment of the first section and the check bits in a first portion of the second section that is associated with the first segment. The first decoder may correct errors in multiple bit positions within the first data bits using the check bits stored in the first portion and the second decoder may, separately, decode the second data bits using the second set of check bits.

Claims

1. A method comprising:

fragmenting a cache line of a first section of a cache memory into a plurality of segments comprising a first segment and a second segment,

generating a first set of data bits and a first set of check bits while encoding a first region of a data stream,

storing the first set of data bits in the first segment of the first section of the cache memory and the first set of check bits in a first portion of a second section of the cache memory while the cache memory is operational in a low-power mode and otherwise not generating and storing the first set of check bits, wherein the first portion is associated with the first segment of the first section of the cache memory, to enable correcting errors in multiple bit positions within the first set of data bits using the check bits stored in the first portion of the second section of the cache memory while decoding the first set of data bits.

2. The method of claim 1 further comprises,

generating a second set of data bits and a second set of check bits while encoding a second region of the data stream, wherein the second region of the data stream is encoded separately while the first region of the data stream is encoded,

storing the second set of data bits in the second segment and the second set of check bits in a second portion of the second section of the cache memory, wherein the second portion is associated with the second segment, to enable correcting errors in multiple bit positions within the second set of data bits using the check bits stored in the second portion of the second section of the cache memory while decoding the second set of data bits.

3. The method of claim 2, wherein the first set of check bits and the second set of check bits are stored in the second section of the cache memory while the cache memory is operated in the low-power mode.

4. The method of claim 2, wherein encoding of the first region and the second region of the data stream is performed using Orthogonal Latin Square Codes.

5. The method of claim 4, wherein the first set of data bits comprise ‘

m²’

data bits and the first set of check bits comprise ‘

2tm’

check bits, wherein ‘

m’

represents a number of bits used to generate a check bit of the first set of check bits and ‘

t’

represents the number of correctible error bits.

6. The method of claim 5, wherein the decoding comprises generating ‘

m²’

data bits that are corrected for errors in ‘

t’

positions within the first set of data bits.

7. The method of claim 1, wherein the ratio of the size of the first section and the second section of the cache memory is equal to G:

K, wherein G is not equal to K, wherein G and K are integers.

8. The method of claim 1, wherein the ratio of the size of the first section and the second section of the cache memory is equal to G:

K, wherein G is equal to K, wherein G and K are integers.

9. A machine-readable non-transitory storage medium comprising a plurality of instructions that in response to being executed result in a processor comprising:

fragmenting a cache line of a first section of a cache memory into a plurality of segments comprising a first segment and a second segment,

generating a first set of data bits and a first set of check bits while encoding a first region of a data stream,

storing the first set of data bits in the first segment and the first set of check bits in a first portion of a second section of the cache memory while the cache memory is operational in a low-power mode and otherwise not generating and storing the first set of check bits, wherein the first portion is associated with the first segment, to enable correcting errors in multiple bit positions within the first set of data bits using the check bits stored in the first portion of the second section of the cache memory while decoding the first set of data bits.

10. The machine-readable non-transitory storage medium of claim 9 further comprises,

generating a second set of data bits and a second set of check bits while encoding a second region of the data stream, wherein the second region of the data stream is encoded while the first region of the data stream is encoded,

storing the second set of data bits in the second segment and the second set of check bits in a second portion of the second section of the cache memory, wherein the second portion is associated with the second segment, and

correcting errors in multiple bit positions within the second set of data bits using the check bits stored in the second portion of the second section of the cache memory while decoding the second set of data bits.

11. The machine-readable non-transitory storage medium of claim 10, wherein the first set of check bits and the second set of check bits are stored in the second region of the cache memory while the cache memory is operated in the low-power mode.

12. The machine-readable non-transitory storage medium of claim 10, wherein encoding of the first region and the second region of the data stream is performed using Orthogonal Latin Square Codes.

13. The machine-readable non-transitory storage medium of claim 12, wherein the first set of data bits comprise ‘

m²’

data bits and the first set of check bits comprise ‘

2tm’

check bits, wherein ‘

m’

represents a number of bits used to generate a check bit of the first set of check bits and ‘

t’

represents the number of correctible error bits.

14. The machine-readable non-transitory storage medium of claim 13, wherein the decoding comprises generating ‘

m²’

data bits that are corrected for errors in ‘

t’

positions within the first set of data bits.

15. The machine-readable non-transitory storage medium of claim 9, wherein the ratio of the size of the first section and the second section of the cache memory is equal to G:

K, wherein G is not equal to K, wherein G and K are integers.

16. The machine-readable non-transitory storage medium of claim 9, wherein the ratio of the size of the first section and the second section of the cache memory is equal to G:

K wherein G is equal to K, wherein G and K are integers.

17. An apparatus comprising:

a central processing unit, and

a cache memory coupled to the central processing unit including a control logic to create a plurality of sets each comprising at least one data way and at least one ECC way, wherein during a low-power mode of operation the cache memory is to store check bits into the at least one ECC way to enable correction of multi-bit errors in data stored in the at least one data way, and during a non-low-power mode the cache memory is to store data in the at least one data way and the at least one ECC way.

18. The apparatus of claim 17, wherein the control logic is to fragment a cache line of a first section of the cache memory into a plurality of segments comprising a first segment and a second segment.

19. The apparatus of claim 18, further comprising an access logic including a first encoder to generate a first set of data bits and a first set of check bits while encoding a first region of a data stream, wherein the control logic is to store the first set of data bits in the first segment and the first set of check bits in a first portion of a second section of the cache memory, wherein the first portion is associated with the first segment.

20. The apparatus of claim 19, wherein the cache memory further comprises a first decoder, wherein the decoder is to correct errors in multiple bit positions within the first set of data bits using the first set of check bits while decoding the first set of data bits.

21. The apparatus of claim 19, wherein the control logic is to store the first set of check bits in the second section of the cache memory while operated in the low-power mode.

22. The apparatus of claim 19, wherein the ratio of the size of the first section and the second section of the cache memory is equal to G:

K, wherein G is not equal to K, wherein G and K are integers.

23. The apparatus of claim 19, wherein the ratio of the size of the first section and the second section of the cache memory is equal to G:

K, wherein G is equal to K, wherein G and K are integers.