# US 11,500,723 B2 · Using parity data for concurrent data authentication, correction, compression, and encryption

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,500,723 B2
- Document ID: US11500723B2
- Status: Granted
- Kind: B2
- Application number: 16/855,901
- Filed: 2020-04-22
- Published: 2020-08-06
- Granted: 2022-11-15
- Earliest claimed: 2011-12-30
- Assignees: Streamscale, Inc.
- Applicants: Streamscale, Inc.
- Inventors: Michael H. Anderson
- Web page: https://patentgrep.com/patent/US11500723B2

## CPC

- G06F 11/1076: {Parity data used in redundant arrays of independent storages, e.g. in RAID systems}
- G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors}
- G06F 3/064: {Management of blocks}
- G06F 3/0683: {Plurality of storage devices}
- G06F 11/1096: {Parity calculation or recalculation after configuration or reconfiguration of the system}
- G06F 12/0238: {Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory}
- G06F 12/06: Addressing a physical block of locations, e.g. base addressing, module addressing, memory dedication (G06F12/08 takes precedence)
- H03M 13/11: using multiple parity bits
- H03M 13/1191: {Codes on graphs other than LDPC codes}
- H03M 13/134: {Non-binary linear block codes not provided for otherwise}
- H03M 13/1515: {Reed-Solomon codes}
- H03M 13/154: {Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial}
- H03M 13/158: {Finite field arithmetic processing}
- H03M 13/373: {with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes}
- H03M 13/3761: {using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes}
- H03M 13/3776: {using a re-encoding step during the decoding process}
- H03M 13/616: {Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations}
- H04L 1/0043: {Realisations of complexity reduction techniques, e.g. use of look-up tables}
- G06F 11/1092: {Rebuilding, e.g. when physically replacing a failing disk}
- G06F 2211/1057: Parity-multiple bits-RAID6, i.e. RAID 6 implementations
- G06F 2211/109: Sector level checksum or ECC, i.e. sector or stripe level checksum or ECC in addition to the RAID parity calculation
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A system for software error-correcting code (ECC) protection or compression of original data using ECC data in a first memory is provided. The system includes a processing core for executing computer instructions and accessing data from a main memory, and a non-volatile storage medium for storing the computer instructions. The software ECC protection or compression includes: a data matrix for holding the original data in the first memory; a check matrix for holding the ECC data in the first memory; an encoding matrix for holding first factors in the main memory, the first factors being for encoding the original data into the ECC data; and a thread for executing on the processing core. The thread includes a Galois Field multiplier for multiplying entries of the data matrix by an entry of the encoding matrix, and a sequencer for ordering operations using the Galois Field multiplier to generate the ECC data.

## Claims

### Claim 1

An accelerated error correcting code (ECC) system comprising:
a processing circuit comprising a processing core, the processing core comprising a plurality of vector registers, each of the vector registers storing at least 16 bytes;
a main memory;
a plurality of data drives, each comprising at least one non-volatile storage medium storing at least one block of original data;
at least three check drives, each comprising at least one non-volatile storage medium storing at least one block of check data corresponding to the at least one block of the original data;
an input/output (I/O) controller configured to store the at least one block of the check data from the main memory to the check drives; and
a non-volatile storage medium storing computer instructions that, when executed by the processing circuit, cause the processing circuit to:
load the at least one block of the original data from the data drives into a data matrix stored in the main memory;
load an encoding matrix comprising a plurality of factors into main memory;
load a lookup table matrix comprising at least two entries into the main memory; and
compute the at least one block of the check data based on the data matrix and the encoding matrix using a thread executed on the processing circuit, the thread comprising:
a parallel lookup multiplier configured to multiply at least one vector of the data matrix by a single factor of the plurality of factors of the encoding matrix to compute parallel lookup multiplier results;
a parallel adder configured to compute a running total of the parallel lookup multiplier results; and
a sequencer configured to:
order load operations of the original data into at least one of the vector registers of the processing core;
compute the check data using the parallel lookup multiplier and the parallel adder; and
store the computed check data from the vector registers of the processing core into a check matrix in the main memory.

### Claim 2 (depends on 1)

The system of claim 1, wherein the processing circuit comprises a plurality of processing cores comprising the processing core,
wherein the thread comprises a plurality of threads,
wherein the non-volatile storage medium further stores computer instructions that, when executed by the processing circuit, cause the processing circuit to execute a scheduler configured to generate check data across the plurality of threads by:
dividing the original data in the main memory into a plurality of data matrices;
dividing the check data in the main memory into a plurality of check matrices;
assigning corresponding ones of the data matrices and the check matrices in the main memory to the plurality of threads, wherein each thread comprises an encoder, the encoder comprising at least a portion of the encoding matrix, a parallel lookup multiplier, a parallel adder, and a sequencer for ordering operations through at least one of the data matrices, corresponding ones of the check matrices, and the at least a portion of the encoding matrix in the main memory using the parallel lookup multiplier and the parallel adder to generate the check data in the main memory; and
assigning the plurality of threads to the plurality of processing cores of the processing circuit to concurrently generate the check matrices in the main memory from corresponding ones of the data matrices in the main memory.

### Claim 3 (depends on 2)

The system of claim 2, wherein the scheduler divides the original data in the main memory and the check data in the main memory into a plurality of stripes, each of the plurality of stripes comprising at least:
one block of the original data; and
one corresponding block of the check data.

### Claim 4 (depends on 3)

The system of claim 3, wherein the scheduler assigns the plurality of stripes to the plurality of threads such that, for each stripe of the plurality of stripes, the check data of the stripe is computed by no more than one of the plurality of threads.

### Claim 5 (depends on 4)

The system of claim 4, wherein each of the plurality of threads corresponding to at least one of the plurality of stripes is assigned to a respective one of the plurality of processing cores of the processing circuit.

### Claim 6 (depends on 1)

The system of claim 1, wherein the data matrix comprises a first number of rows and the data drives comprise the first number of data drives,
wherein the check matrix comprises a second number of rows and the check drives comprise the second number of check drives, and
wherein the encoding matrix comprises a plurality of first factors in the second number of rows and the first number of columns.

### Claim 7 (depends on 1)

The system of claim 1, wherein the parallel lookup multiplier multiplies the at least one vector of the data matrix by the single factor in the encoding matrix at a rate of less than about 2 machine instructions per byte of the data matrix.

### Claim 8 (depends on 1)

The system of claim 1, wherein the processing circuit comprises a plurality of processing cores comprising the processing core and a second processing core,
wherein the thread comprises a plurality of threads comprising a first thread group and a second thread group, and
wherein the non-volatile storage medium further stores computer instructions that, when executed by the processing circuit, cause the processing circuit to perform data operations to compute the check data and to perform I/O operations using the I/O controller by:
assigning the data operations to the first thread group, and not assigning the I/O operations to the first thread group;
assigning the I/O operations to the second thread group, and not assigning the data operations to the second thread group;
assigning the first thread group to the processing core;
assigning the second thread group to the second processing core; and
concurrently executing the first thread group on the processing core and the second thread group on the second processing core to concurrently generate the check data and perform the I/O operations.

### Claim 9

An accelerated error-correcting code (ECC) decoding system comprising:
a processing circuit comprising a processing core, the processing core comprising a plurality of vector registers, each of the vector registers storing at least 16 bytes;
a main memory;
a plurality of data drives, each comprising at least one non-volatile storage medium storing at least one block of original data;
at least three check drives, each comprising at least one non-volatile storage medium storing at least one block of check data corresponding to the at least one block of the original data;
an input/output (I/O) controller configured to store the at least one block of the check data from the main memory to the check drives; and
a non-volatile storage medium storing computer instructions that, when executed by the processing circuit, cause the processing circuit to:
load at least one block of surviving original data from the data drives into a data matrix in the main memory;
load at least one block of surviving check data from the check drives into a check matrix in the main memory;
load a solution matrix comprising a plurality of factors for decoding the check data in the main memory to reconstruct lost original data in the main memory;
loading a lookup table matrix comprising at least two entries in the main memory; and
reconstruct the lost original data based on the at least one block of the surviving original data, the at least one block of the check data, and the solution matrix using a thread executed on the processing circuit, the thread comprising:
a parallel lookup multiplier configured to multiply at least one vector of the data matrix by a single factor of the plurality of factors of the solution matrix to compute parallel lookup multiplier results;
a parallel adder configured to compute a running total of the parallel lookup multiplier results; and
a sequencer configured to:
order load operations of the surviving original data into at least one of the vector registers of the processing core, load operations of the surviving check data into at least one of the vector registers of the processing core, and load operations of the lookup table into at least one of the vector registers of the processing core;
compute the lost original data using the parallel lookup multiplier and the parallel adder; and
store the computed lost original data from the vector registers into the main memory.

### Claim 10 (depends on 9)

The system of claim 9, wherein the processing circuit comprises a plurality of processing cores comprising the processing core,
wherein the thread comprises a plurality of threads,
wherein the non-volatile storage medium further stores computer instructions that, when executed by the processing circuit, cause the processing circuit to execute a scheduler configured to compute the lost original data across the plurality of threads by:
dividing the surviving original data in the main memory into a plurality of data matrices;
dividing the surviving check data in the main memory into a plurality of check matrices;
assigning corresponding ones of the data matrices and the check matrices in the main memory to the plurality of threads, wherein each thread comprises an decoder, the decoder comprising at least a portion of the solution matrix, a parallel lookup multiplier, a parallel adder, and a sequencer for ordering operations through at least one of the data matrices, corresponding ones of the check matrices, and the at least a portion of the solution matrix in the main memory using the parallel lookup multiplier and the parallel adder to decode the check data in the main memory into the lost original data in the main memory; and
assigning the plurality of threads to the plurality of processing cores of the processing circuit to concurrently regenerate portions of the data matrices corresponding to the lost original data in the main memory from corresponding ones of the check matrices in the main memory.

### Claim 11 (depends on 10)

The system of claim 10, wherein the scheduler divides the surviving original data in the main memory and the surviving check data in the main memory into a plurality of stripes, each of the plurality of stripes comprising at least:
one block of the original data; and
one corresponding block of the check data.

### Claim 12 (depends on 11)

The system of claim 11, wherein the scheduler assigns the stripes to the plurality of threads such that, for each stripe of the plurality of stripes, the decoding of the check data of the stripe corresponding to the lost original data is computed by no more than one of the plurality of threads.

### Claim 13 (depends on 12)

The system of claim 12, wherein each of the plurality of threads corresponding to at least one of the plurality of stripes is assigned to a respective one of the plurality of processing cores of the processing circuit.

### Claim 14 (depends on 9)

The system of claim 9, wherein the solution matrix comprises an inverted sub-matrix of an encoding matrix, the factors of the encoding matrix being for encoding the original data into the check data.

### Claim 15 (depends on 9)

The system of claim 9, wherein the parallel lookup multiplier multiplies the at least one vector of the data matrix by the single factor in the solution matrix at a rate of less than about 2 machine instructions per byte of the data matrix.

### Claim 16 (depends on 9)

The system of claim 9, wherein the processing circuit comprises a plurality of processing cores comprising the processing core and a second processing core,
wherein the thread comprises a plurality of threads comprising a first thread group and a second thread group, and
wherein the storage medium further stores computer instructions that, when executed by the processing circuit, cause the processing circuit to perform data operations to regenerate the lost original data and to perform I/O operations using the I/O controller by:
assigning the data operations to the first thread group, and not assigning the I/O operations to the first thread group;
assigning the I/O operations to the second thread group, and not assigning the data operations to the second thread group;
assigning the first thread group to the processing core;
assigning the second thread group to the second processing core; and
concurrently executing the first thread group on the processing core and the second thread group on the second processing core to concurrently regenerate the lost original data and perform the I/O operations.