Accelerated erasure coding system and method

• US 9,160,374 B2
• Filed: 03/24/2014
• Issued: 10/13/2015
• Est. Priority Date: 12/30/2011
• Status: Active Grant

• Current Assignee: StreamScale, Inc.
• Original Assignee: StreamScale, Inc.
• Inventors: Anderson, Michael H.
• Primary Examiner(s): Tabone, Jr., John J
• Application Number:
  US14/223,740
• Publication Number:
  US 20150012796A1
• Time in Patent Office: 568 Days
• Field of Search: 714/6.24, 714/6.1, 714/6.11, 714/6.2, 714/6.21, 714/6.32, 714/763, 714/752, 714/758, 714/768, 714/770, 714/773, 714/784, 714/786
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 11/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• CPC Class Codes: G06F 12/0238 Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
• CPC Class Codes: G06F 12/06 Addressing a physical block of locations, e.g. base addressing, module addressing, memory dedication G06F12/08 takes precedence
• CPC Class Codes: G06F 2211/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations
• CPC Class Codes: G06F 2211/109 Sector level checksum or ECC, i.e. sector or stripe level checksum or ECC in addition to the RAID parity calculation
• CPC Class Codes: G11C 29/52 Protection of memory contents; Detection of errors in memory contents
• CPC Class Codes: H03M 13/1191 Codes on graphs other than LDPC codes
• CPC Class Codes: H03M 13/134 Non-binary linear block codes not provided for otherwise
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/154 Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial
• CPC Class 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
• CPC Class 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
• CPC Class Codes: H03M 13/3776 using a re-encoding step during the decoding process
• CPC Class Codes: H03M 13/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations
• CPC Class Codes: H03M 13/6502 Reduction of hardware complexity or efficient processing
• CPC Class Codes: H04L 1/0043 Realisations of complexity reduction techniques, e.g. use of look-up tables
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence

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

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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

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.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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.