Erasure code data protection and recovery computation system and method
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
H03M-013/00
H03M-013/15
G06F-011/10
H03M-013/37
출원번호
US-0431629
(2017-02-13)
등록번호
US-10230398
(2019-03-12)
발명자
/ 주소
Schwaderer, William David
출원인 / 주소
Samsung Electronics Co., Ltd.
대리인 / 주소
Lewis Roca Rothgerber Christie LLP
인용정보
피인용 횟수 :
0인용 특허 :
12
초록▼
A system and method for performing erasure code data protection and recovery computations using simple arithmetic and data manipulation functions. Other embodiments set forth techniques for using the computation functions with a multiplicity of compact one-dimension table lookup operations. A set of
A system and method for performing erasure code data protection and recovery computations using simple arithmetic and data manipulation functions. Other embodiments set forth techniques for using the computation functions with a multiplicity of compact one-dimension table lookup operations. A set of assigned multi-threaded processor threads perform computations on data values in parallel to generate erasure code data protection information and to perform data recovery operations using available data and the data protection information. During normal operations, in one embodiment, threads may perform parallel computations using a small set of simple arithmetic operations and data manipulation functions. In other embodiments, the threads may also use a multiplicity of compact one-dimension lookup tables stored within the multi-threaded processor or otherwise accessible by the multi-threaded processor to perform the computations.
대표청구항▼
1. A system for storing data, the system comprising: a first processing circuit;the first processing circuit being configured to send to a second processing circuit: a plurality of input Data Units;a request specifying an erasure code operation to be performed, the erasure code operation being: a pa
1. A system for storing data, the system comprising: a first processing circuit;the first processing circuit being configured to send to a second processing circuit: a plurality of input Data Units;a request specifying an erasure code operation to be performed, the erasure code operation being: a parity generation operation; ora systematic data recovery operation; andone or more constants to be used in performing the erasure code operationwherein the second processing circuit comprises a plurality of cores, a first core of the plurality of cores being configured to:discover, at startup, an identification number of the first core and of a thread to be executed by the first core, andperform an erasure code operation using an input Data Unit stored at a memory address calculated using the identification number. 2. The system of claim 1, wherein the one or more constants comprise: a powers table, listing, for each of a plurality of input values, a power of the input value in a Galois field; anda logarithm table, listing, for each of the plurality of input values, a logarithm of the input value in the Galois field. 3. The system of claim 2, wherein each of the input Data Units is an n-bit number, n being a positive-integer power of 2, and the Galois field is GF(2n). 4. The system of claim 1, wherein the one or more constants comprise an inverse array suitable for performing a systematic data recovery operation. 5. The system of claim 4, wherein the inverse array is a N×N array that when multiplied, in a Galois field, by a N×1 vector produces N recovered Data Units, N being a positive integer. 6. The system of claim 1, wherein the one or more constants comprise a multiplication table. 7. The system of claim 6, wherein the multiplication table lists, for each possible value of a first factor, a product of the first factor and a weight, the weight being one of a plurality of weights used to calculate a Q Erasure Code Data Unit as a weighted exclusive-or of Data Units in a slice. 8. A system for storing data, the system comprising: a first processing circuit;the first processing circuit being configured to send to a second processing circuit: a plurality of input Data Units;a request specifying an erasure code operation to be performed, the erasure code operation being: a parity generation operation; ora systematic data recovery operation; anda kernel, the kernel comprising machine code instructions that when executed by the second processing circuit cause the second processing circuit to perform the erasure code operation,wherein the kernel includes instructions for performing a multiplication of a first factor and a second factor, without conditional operations,wherein the second processing circuit comprises a plurality of cores, a first core of the plurality of cores being configured to:discover, at startup, an identification number of the first core and of a thread to be executed by the first core, andperform an erasure code operation using an input Data Unit stored at a memory address calculated using the identification number. 9. The system of claim 8, wherein the instructions for performing the multiplication of the first factor and the second factor comprise a plurality of left-shift operations and a plurality of addition operations, each addition operation of the plurality of addition operations being a modulo 2 addition operation and corresponding to a corresponding bit of the second factor having a value of 1. 10. A system for storing data, the system comprising: a first processing circuit; anda second processing circuit,the first processing circuit being configured to send to the second processing circuit: a plurality of input Data Units;a request specifying an erasure code operation to be performed, the erasure code operation being: a parity generation operation; ora systematic data recovery operation; andone or more constants to be used in performing the erasure code operation,wherein the second processing circuit comprises a plurality of cores, a first core of the plurality of cores being configured to:discover, at startup, an identification number of the first core and of a thread to be executed by the first core, andperform an erasure code operation using an input Data Unit stored at a memory address calculated using the identification number. 11. The system of claim 10, wherein the first processing circuit is a central processing unit and the second processing circuit is a graphics processing unit. 12. The system of claim 10, wherein the one or more constants comprise: a powers table, listing, for each of a plurality of input values, a power of the input value in a Galois field; anda logarithm table, listing, for each of the plurality of input values, a logarithm of the input value in the Galois field. 13. The system of claim 12, wherein each of the input Data Units is an n-bit number, n being a positive-integer power of 2, and the Galois field is GF(2^n). 14. The system of claim 10, wherein the one or more constants comprise an inverse array suitable for performing a systematic data recovery operation. 15. The system of claim 14, wherein the inverse array is a N×N array that when multiplied, in a Galois field, by a N×1 vector produces N recovered Data Units, N being a positive integer. 16. The system of claim 10, wherein the one or more constants comprise a multiplication table. 17. The system of claim 16, wherein the multiplication table lists, for each possible value of a first factor, a product of the first factor and a weight, the weight being one of a plurality of weights used to calculate a Q Erasure Code Data Unit as a weighted exclusive-or of Data Units in a slice. 18. A method for storing or restoring data, the method comprising: sending, by a first processing circuit to a second processing circuit: a plurality of input Data Units;a request specifying an erasure code operation to be performed, the erasure code operation being: a parity generation operation; ora systematic data recovery operation; andone or more constants to be used in performing the erasure code operation; andperforming, by the second processing circuit, the requested erasure code operation,wherein the second processing circuit comprises a plurality of cores, a first core of the plurality of cores being configured to:discover, at startup, an identification number of the first core and of a thread to be executed by the first core, andperform an erasure code operation using an input Data Unit stored at a memory address calculated using the identification number. 19. The method of claim 18, wherein the first processing circuit is a central processing unit and the second processing circuit is a graphics processing unit.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (12)
Anderson, Michael H.; Mann, Sarah, Accelerated erasure coding system and method.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.