초록 ▼

One embodiment of the present invention sets forth a technique for performing RAID-6 computations using simple arithmetic functions and two-dimensional table lookup operations. A set of threads within a multi-threaded processor are assigned to perform RAID-6 computations in parallel on a stripe of R

One embodiment of the present invention sets forth a technique for performing RAID-6 computations using simple arithmetic functions and two-dimensional table lookup operations. A set of threads within a multi-threaded processor are assigned to perform RAID-6 computations in parallel on a stripe of RAID-6 data. A set of lookup tables are stored within the multi-threaded processor for access by the threads in performing the RAID-6 computations. During normal operation of a related RAID-6 disk array, RAID-6 computations may be performed by the threads using a small set of simple arithmetic operations and a set of lookup operations to the lookup tables. Greater computational efficiency is gained by reducing the RAID-6 computations to simple operations that are performed efficiently on a multi-threaded processor, such as a graphics processing unit.

대표청구항 ▼

1. A computer-implemented method for computing erasure codes for a redundant array of independent disks (RAID), the method comprising: storing user data associated with a RAID stripe that is defined by a data block common to each disk in the redundant array, wherein, for each byte offset within the

1. A computer-implemented method for computing erasure codes for a redundant array of independent disks (RAID), the method comprising: storing user data associated with a RAID stripe that is defined by a data block common to each disk in the redundant array, wherein, for each byte offset within the data block, user data associated with only N−2 disks is stored, N being the number of disks in the redundant array, and wherein a sliver comprises a set of S bytes per disk within the RAID stripe at a common sliver offset within each disk;calculating a sliver offset for accessing an assigned sliver based on a thread identification number;for each byte offset within the assigned sliver, computing a first erasure code by accumulating a plurality of values generated by performing, across each disk in the redundant array, a first exclusive-or operation based on the byte offset within the data block;for each byte offset within the assigned sliver, computing a second erasure code by accumulating a plurality of values generated by performing, across each disk in the redundant array, a second exclusive-or operation based on a look-up table value; andfor each byte offset within the assigned sliver, storing the first erasure code and the second erasure code along with the user data associated with the N−2 disks. 2. The method of claim 1, wherein the first erasure code and the second erasure code are used to recover user data lost when any one disk in the redundant array fails or when any two disks in the redundant array fail. 3. The method of claim 1, wherein the redundant array is configured as a RAID 6 array, and S is an integral power of two. 4. The method of claim 1, wherein, for each byte offset within the assigned sliver, the look-up table value is based on an identifier for a first disk in the redundant array and a byte value stored on the first disk at the byte offset within the assigned sliver. 5. The method of claim 1, wherein each look-up table value is included in a first look-up table that stores the results of Galois operations performed on a plurality of eight-bit numbers, wherein a first eight-bit number identifies a disk in the redundant array, and a second eight-bit number comprises a byte of user data stored on the identified disk. 6. The method of claim 5, wherein the first look-up table is stored in memory local to a graphics processing unit. 7. The method 6, wherein the user data is stored in the memory local to the graphics processing unit or in a frame buffer memory coupled to the graphics processing unit. 8. The method of claim 5, further comprising the step of generating a first recovery code value based on the first erasure code and valid stored user data. 9. The method of claim 8, further comprising the step of generating a second recovery code value by extracting one or more values from the first look-up table, the second erasure code, the first recovery code, an extracted value from a second look-up table, and the valid stored user data. 10. The method of claim 9, further comprising the step of recovering data lost on a first failed disk in the redundant array via extracting data from a third look-up table based on the second recovery code value, the identifier for the first disk, and an identifier for a second failed disk. 11. The method of claim 10, further comprising the step of recovering data lost on the second failed disk in the redundant array based on the first recovery code and data recovered from the first failed disk. 12. The method of claim 10, wherein the second look-up table and the third look-up table are stored in memory local to a graphics processing unit. 13. The method of claim 1, wherein the steps of calculating, computing the first erasure code, computing the second erasure code, and storing the first and second erasure codes are performed by a thread associated with the thread identification number executing on a processing unit. 14. A computer-readable medium including instructions that, when executed by a processing unit, cause the processing unit to compute erasure codes for a redundant array of independent disks (RAID), by performing the steps of: storing user data associated with a RAID stripe that is defined by a data block common to each disk in the redundant array, wherein, for each byte offset within the data block, user data associated with only N−2 disks is stored, N being the number of disks in the redundant array, and wherein a sliver comprises a set of S bytes per disk within the RAID stripe at a common sliver offset within each disk;calculating a sliver offset for accessing an assigned sliver based on a thread identification number;for each byte offset within the assigned sliver, computing a first erasure code by accumulating a plurality of values generated by performing, across each disk in the redundant array, a first exclusive-or operation based on the byte offset within the data block;for each byte offset within the assigned sliver, computing a second erasure code by accumulating a plurality of values generated by performing, across each disk in the redundant array, a second exclusive-or operation based on a look-up table value; andfor each byte offset within the assigned sliver, storing the first erasure code and the second erasure code along with the user data associated with the N−2 disks. 15. The computer-readable medium of claim 14, wherein the first erasure code and the second erasure code are used to recover user data lost when any one disk in the redundant array fails or when any two disks in the redundant array fail. 16. The computer-readable medium of claim 14, wherein, for each byte offset within the assigned sliver, the look-up table value is based on an identifier for a first disk in the redundant array and a byte value stored on the first disk at the byte offset within the assigned sliver. 17. The computer-readable medium of claim 14, wherein each look-up table value is included in a first look-up table that stores the results of Galois operations performed on a plurality of eight-bit numbers, wherein a first eight-bit number identifies a disk in the redundant array, and a second eight-bit number comprises a byte of user data stored on the identified disk. 18. The computer-readable medium of claim 17, wherein the first look-up table is stored in memory local to a graphics processing unit. 19. The computer-readable medium of claim 18, wherein the user data is stored in the memory local to the graphics processing unit or in a frame buffer memory coupled to the graphics processing unit. 20. The computer-readable medium of claim 17, further comprising the step of generating a first recovery code value based on the first erasure code and valid stored user data. 21. The computer-readable medium of claim 20, further comprising the steps of generating a second recovery code value by extracting one or more values from the first look-up table, the second erasure code, the first recovery code, an extracted value from a second look-up table, and the valid stored user data; and, recovering data lost on a second failed disk in the redundant array via extracting data from a third look-up table based on the second recovery code value, the identifier for the first disk, and an identifier for the second failed disk. 22. The computer-readable medium of claim 21, further comprising the step of recovering data lost on the second failed disk in the redundant array based on the first recovery code and data recovered from the first failed disk. 23. The computer-readable medium of claim 21, wherein the second look-up table and the third look-up table are stored in memory local to a graphics processing unit. 24. The computer-readable medium of claim 14, wherein the steps of calculating, computing the first erasure code, computing the second erasure code, and storing the first and second erasure codes are performed by a thread associated with the thread identification number executing on a processing unit. 25. A computer system, comprising: a central-processing unit;a multi-threaded processing unit coupled to the central-processing unit;a system memory coupled to the central processing unit and the multi-threaded processing unit; anda redundant array of independent disks (RAID) coupled to the central processing unit, multi-threaded processing unit, and the system memory,wherein the multi-threaded processing unit is configured to compute erasure codes for the redundant array by performing the steps of: storing user data associated with a RAID stripe that is defined by a data block common to each disk in the redundant array, wherein, for each byte offset within the data block, user data associated with only N−2 disks is stored, N being the number of disks in the redundant array, and wherein a sliver comprises a set of S bytes per disk within the RAID stripe at a common sliver offset within each disk;calculating a sliver offset for accessing an assigned sliver based on a thread identification number;for each byte offset within the assigned sliver, computing a first erasure code by accumulating a plurality of values generated by performing, across each disk in the redundant array, a first exclusive-or operation based on the byte offset within the data block;for each byte offset within the assigned sliver, computing a second erasure code by accumulating a plurality of values generated by performing, across each disk in the redundant array, a second exclusive-or operation based on a look-up table value; andfor each byte offset within the assigned sliver, storing the first erasure code and the second erasure code along with the user data associated with the N−2 disks.