# US 9,160,374 B2 · Accelerated erasure coding system and method

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

- Number: US 9,160,374 B2
- Document ID: US9160374B2
- Status: Granted
- Kind: B2
- Application number: 14/223,740
- Filed: 2014-03-24
- Published: 2015-01-08
- Granted: 2015-10-13
- Earliest claimed: 2011-12-30
- Assignees: Streamscale, Inc.
- Applicants: Streamscale, Inc.
- Inventors: Michael H. Anderson
- Web page: https://patentgrep.com/patent/US9160374B2

## CPC

- H03M 13/154: {Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial}
- G06F 11/1068: {in sector programmable memories, e.g. flash disk (G06F11/1072 takes precedence)}
- G06F 11/1076: {Parity data used in redundant arrays of independent storages, e.g. in RAID systems}
- G06F 11/1092: {Rebuilding, e.g. when physically replacing a failing disk}
- 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)
- G11C 29/52: Protection of memory contents; Detection of errors in memory contents
- 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/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}
- H03M 13/6502: {Reduction of hardware complexity or efficient processing}
- H04L 1/0043: {Realisations of complexity reduction techniques, e.g. use of look-up tables}
- H04L 1/0057: {Block codes (H04L1/0061, H04L1/0064 take precedence)}
- 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
- 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)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G11C: STATIC STORES (semiconductor memory devices H10B)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

An accelerated erasure coding 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 processing core, storage medium, and computer instructions are configured to implement an erasure coding system, which includes: a data matrix for holding original data in the main memory; a check matrix for holding check data in the main memory; an encoding matrix for holding first factors in the main memory, the first factors being for encoding the original data into the check data; and a thread for executing on the processing core. The thread includes: a parallel multiplier for concurrently multiplying multiple entries of the data matrix by a single entry of the encoding matrix; and a first sequencer for ordering operations through the data matrix and the encoding matrix using the parallel multiplier to generate the check data.

## Claims

### Claim 1

A system for accelerated error-correcting code (ECC) processing comprising:
a processing core for executing computer instructions and accessing data from a main memory, the processing core comprising at least 16 data registers, each of the data registers comprising at least 16 bytes; and
a non-volatile storage medium for storing the computer instructions,
wherein the processing core, the non-volatile storage medium, and the computer instructions are configured to implement an erasure coding system comprising:
a data matrix for holding original data in the main memory;
a check matrix for holding check data in the main memory;
an encoding matrix for holding first factors in the main memory, the first factors being for encoding the original data into the check data; and
a thread for executing on the processing core and comprising:
a parallel multiplier for concurrently multiplying multiple data entries of a matrix by a single factor; and
a first sequencer for ordering operations through the data matrix and the encoding matrix using the parallel multiplier to generate the check data.

### Claim 2 (depends on 1)

The system of claim 1, wherein the parallel multiplier is configured to process the data in units of at least 64 bytes spread over at least four of the data registers at a time.

### Claim 3 (depends on 2)

The system of claim 2, wherein the parallel multiplier is further configured to:
receive an input operand in the at least four of the data registers; and
return with the input operand intact in the at least four of the data registers.

### Claim 4 (depends on 2)

The system of claim 2, wherein consecutive ones of the computer instructions to process each of the units of the data access separate ones of the data registers to permit concurrent execution of the consecutive ones of the computer instructions on the processing core.

### Claim 5 (depends on 1)

The system of claim 1, wherein the parallel multiplier comprises two lookup tables for doing concurrent multiplication of 4-bit quantities across 16 byte-sized entries using the PSHUFB (Packed Shuffle Bytes) or equivalent instruction.

### Claim 6 (depends on 1)

The system of claim 1, wherein the parallel multiplier is further configured to:
receive an input operand in at least one of the data registers; and
return with the input operand intact in the at least one of the data registers.

### Claim 7

A method of accelerated error-correcting code (ECC) processing on a computing system comprising a non-volatile storage medium, a processing core for accessing instructions and data from a main memory, and a computer program comprising a plurality of computer instructions for implementing an erasure coding system, the processing core comprising at least 16 data registers, each of the data registers comprising at least 16 bytes, the method comprising:
storing the computer program on the non-volatile storage medium;
executing the computer instructions on the processing core;
arranging original data as a data matrix in the main memory;
arranging first factors as an encoding matrix in the main memory, the first factors being for encoding the original data into check data, the check data being arranged as a check matrix in the main memory; and
generating the check data using a parallel multiplier for concurrently multiplying multiple data entries of a matrix by a single factor, the generating of the check data comprising ordering operations through the data matrix and the encoding matrix using the parallel multiplier.

### Claim 8 (depends on 7)

The method of claim 7, wherein the generating of the check data further comprises processing the data by the parallel multiplier in units of at least 64 bytes spread over at least four of the data registers at a time.

### Claim 9 (depends on 8)

The method of claim 8, wherein the generating of the check data further comprises:
receiving by the parallel multiplier an input operand in the at least four of the data registers; and
returning by the parallel multiplier the input operand intact in the at least four of the data registers.

### Claim 10 (depends on 8)

The method of claim 8, wherein
consecutive ones of the computer instructions that process each of the units of the data access separate ones of the data registers,
the executing of the computer instructions on the processing core further comprises concurrently executing the consecutive ones of the computer instructions on the processing core.

### Claim 11 (depends on 7)

The method of claim 7, wherein the parallel multiplier comprises two lookup tables and the generating of the check data further comprises using the parallel multiplier with the two lookup tables to do concurrent multiplication of 4-bit quantities across 16 byte-sized entries using the PSHUFB (Packed Shuffle Bytes) or equivalent instruction.

### Claim 12 (depends on 7)

The method of claim 7, wherein the generating of the check data further comprises:
receiving by the parallel multiplier an input operand in at least one of the data registers; and
returning by the parallel multiplier the input operand intact in the at least one of the data registers.

### Claim 13

A non-transitory computer-readable storage medium containing a computer program comprising a plurality of computer instructions for performing accelerated error-correcting code (ECC) processing on a computing system comprising a processing core for accessing instructions and data from a main memory, the processing core comprising at least 16data registers, each of the data registers comprising at least 16 bytes, the computer instructions being configured to implement an erasure coding system when executed on the computing system by performing the steps of:
arranging original data as a data matrix in the main memory;
arranging first factors as an encoding matrix in the main memory, the first factors being for encoding the original data into check data, the check data being arranged as a check matrix in the main memory; and
generating the check data using a parallel multiplier for concurrently multiplying multiple data entries of a matrix by a single factor, the generating of the check data comprising ordering operations through the data matrix and the encoding matrix using the parallel multiplier.

### Claim 14 (depends on 13)

The storage medium of claim 13, wherein the generating of the check data further comprises processing the data by the parallel multiplier in units of at least 64 bytes spread over at least four of the data registers at a time.

### Claim 15 (depends on 14)

The storage medium of claim 14, wherein the generating of the check data further comprises:
receiving by the parallel multiplier an input operand in the at least four of the data registers; and
returning by the parallel multiplier the input operand intact in the at least four of the data registers.

### Claim 16 (depends on 14)

The storage medium of claim 14, wherein
consecutive ones of the computer instructions that process each of the units of the data access separate ones of the data registers,
the executing of the computer instructions on the processing core further comprises concurrently executing the consecutive ones of the computer instructions on the processing core.

### Claim 17 (depends on 13)

The storage medium of claim 13, wherein the parallel multiplier comprises two lookup tables and the generating of the check data further comprises using the parallel multiplier with the two lookup tables to do concurrent multiplication of 4-bit quantities across 16byte-sized entries using the PSHUFB (Packed Shuffle Bytes) or equivalent instruction.

### Claim 18 (depends on 13)

The storage medium of claim 13, wherein the generating of the check data further comprises:
receiving by the parallel multiplier an input operand in at least one of the data registers; and
returning by the parallel multiplier the input operand intact in the at least one of the data registers.