Symbol rotation of cache line codewords for increased reliability with metadata

Patent metadata

Field	Value
Publication number	US-12181971-B1
Application number	US-202318336850-A
Country	US
Kind code	B1
Filing date	Jun 16, 2023
Priority date	Jun 16, 2023
Publication date	Dec 31, 2024
Grant date	Dec 31, 2024

Abstract

Embodiments generally relate to improving reliability of processing cache lines with metadata symbols encoded into parity symbols of codewords. The data and metadata of a cache line are encoded into codewords where each codeword is a number of (1) message symbols, each including message bits from data of the cache line, and (2) parity symbols, each including parity bits determined from the message symbols and a metadata symbol. For each codeword of the cache line, the plurality of message and parity symbols are rotated so that a location of each symbol of one codeword is different from other codewords of the cache line. The codewords of the cache line are then stored in memory as rotated. In this manner, the reliability is improved by rotating symbols of the codewords of the cache line, with metadata symbols encoded into parity of codewords, before storage in memory.

First claim

What is claimed is:

1. A computerized system, comprising:
at least one processor; and
computer memory storing computer-useable instructions that, when executed by the at least one processor, cause the at least one processor to perform operations comprising:
encoding data and metadata of a cache line into a plurality of codewords, each codeword of the plurality codewords comprising a plurality of symbols, the plurality of symbols comprising (1) at least one message symbol comprising message bits and (2) at least one parity symbol comprising parity bits, encoding the data and the metadata of the cache line into the plurality of codewords comprising:
determining the message bits of the at least one message symbol of each codeword based on the data of the cache line;
determining at least one metadata symbol for each codeword based on the metadata of the cache line;
determining the parity bits of the at least one parity symbol of each codeword based on (1) the at least one metadata symbol for each codeword and (2) the at least one message symbol of each codeword; and
for each codeword of the plurality of codewords, omitting the at least one metadata symbol and rotating the plurality of symbols so that a location of each symbol of one codeword is different from other codewords of the plurality of codewords; and

storing each codeword of the plurality of codewords with the corresponding rotation of the plurality of symbols of each codeword.

2. The computerized system of claim 1 , wherein the at least one metadata symbol determined for each codeword is shared by all codewords of the plurality of codewords of the cache line.

3. The computerized system of claim 1 , wherein the at least one metadata symbol determined for each codeword is shared by a number of codewords of the plurality of codewords of the cache line.

4. The computerized system of claim 1 , wherein a number of metadata bits of the at least one metadata symbol determined for each codeword is shared by a number of codewords of the plurality of codewords of the cache line.

5. The computerized system of claim 1 , wherein the operations further comprise:
detecting an error in one codeword of the plurality of codewords based on an expected location of the at least one parity symbol in the one codeword's corresponding rotation of the plurality of symbols; and
correcting the error in the one codeword based on the at least one parity symbol.

6. The computerized system of claim 5 , wherein the correction of the error of the one codeword is based on a maximum likelihood of error correction as determined from errors detected in each corresponding rotation of the plurality of symbols in each codeword of the plurality of codewords.

7. The computerized system of claim 1 , wherein the operations further comprise:
accessing metadata of the cache line by:
accessing the plurality of codewords;
decoding the at least one metadata symbol of each codeword of the plurality of codewords based on the at least one parity symbol in each corresponding rotation of the plurality of symbols; and
determining the metadata of the cache line from the at least one metadata symbol of each codeword of the plurality of codewords.

8. The computerized system of claim 1 , wherein the operations further comprise:
accessing the data of each cache line by:
accessing the plurality of codewords;
accessing a message symbol of each codeword of the plurality of codewords in each corresponding rotation of the plurality of symbols in each codeword; and
determining the data of the cache line from the message bits of each message symbol of each codeword of the plurality of codewords.

9. The computerized system of claim 1 , wherein the at least one parity symbol of each codeword of the plurality of codewords is determined through Reed-Solomon (RS) codes.

10. A computer-implemented method, comprising:
receiving a request for data of a cache line;
responsive to the request for data, accessing metadata of the cache line by:
accessing a plurality of codewords, each codeword of the plurality codewords comprising a plurality of symbols, the plurality of symbols comprising (1) at least one message symbol comprising message bits and (2) at least one parity symbol comprising parity bits;
decoding at least one metadata symbol from the plurality of codewords based on a location of the at least one parity symbol in a corresponding rotation of the plurality of symbols of each codeword of the plurality of codewords; and

determining the metadata of the cache line from the at least one metadata symbol of each codeword of the plurality of codewords; and
based at least on the metadata of the cache line, transmitting the data of the cache line.

11. The computer-implemented method of claim 10 , wherein the at least one metadata symbol determined for each codeword is shared by all codewords of the plurality of codewords of the cache line.

12. The computer-implemented method of claim 10 , wherein the at least one metadata symbol determined for each codeword is shared by a number of codewords of the plurality of codewords of the cache line.

13. The computer-implemented method of claim 10 , wherein a number of metadata bits of the at least one metadata symbol determined for each codeword is shared by a number of codewords of the plurality of codewords of the cache line.

14. The computer-implemented method of claim 10 , further comprising:
detecting an error of a metadata symbol in one codeword of the plurality of codewords based on an expected location of the at least one parity symbol in the one codeword's corresponding rotation of the plurality of symbols; and
correcting the error of the metadata symbol in the one codeword based on the at least one parity symbol.

15. The computer-implemented method of claim 14 , wherein the correction of the error of the metadata symbol is based on a maximum likelihood of error correction as determined from errors detected in the corresponding rotation of symbols in each codeword of the plurality of codewords.

16. The computer-implemented method of 10 , further comprising:
accessing the data of the cache line by:
accessing a message symbol of each codeword of the plurality of codewords in each corresponding rotation of the plurality of symbols in each codeword; and
determining the data of the cache line from the message bits of each message symbol of each codeword of the plurality of codewords.

17. One or more computer storage media having computer-executable instructions embodied thereon that, when executed by a computing system having at least one processor and at least one memory, cause the at least one processor to perform operations comprising:
receiving a request for data of a cache line;
responsive to the request for the data of the cache line, accessing the data of the cache line by:
accessing a plurality of codewords, each codeword of the plurality codewords comprising a plurality of symbols, the plurality of symbols comprising (1) at least one message symbol comprising message bits and (2) at least one parity symbol comprising parity bits;
accessing a message symbol of each codeword of the plurality of codewords in a corresponding rotation of the plurality of symbols of each codeword; and
determining the data of the cache line from the at least one message symbol and the at least one parity symbol of each codeword of the plurality of codewords of each cache line; and

transmitting the data of the cache line.

18. The one or more computer storage media of claim 17 , wherein the operati

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Nemati Majid Anaraki
• Dakshinamoorthy Srikanth
• Weathers Anthony Dwayne
• Kumar Ravinder

Classifications

• G06F2212/1032

  Reliability improvement, data loss prevention, degraded operation etc · CPC title

• G06F12/0875

  with dedicated cache, e.g. instruction or stack · CPC title

• G06F11/1096 Primary

  Parity calculation or recalculation after configuration or reconfiguration of the system · CPC title

• G06F11/1064 Primary

  in cache or content addressable memories · CPC title