System and method of encoding data for performing vector calculations in raid storage systems
View Patent ↗The technology described herein involves encoding data representing an array of finite field elements for performing calculations when creating RAID storage systems, characterized in that the bits encoding each element of the Galois field are not arranged sequentially, one after the other, but in increments of n bits, where n>1.
1 . A method of encoding data for parity generation and data recovery in a redundant array of independent disks (RAID) storage system, comprising:
encoding data as elements of GF (2{circumflex over ( )}N), each element comprising N bits;
storing the N bits of each GF (2{circumflex over ( )}N) element non-contiguously in memory with a fixed stride equal to a processor word width in bits, wherein the processor word width is one of a scalar machine-word width and a SIMD vector-register width, thereby forming a bit-sliced representation of the data;
generating parity information for the RAID storage system by performing word-wise logical operations on N bit-planes of the bit-sliced representation using Galois-field arithmetic, wherein addition is implemented as bitwise XOR; and
recovering stored data from the RAID storage system upon failure of at least one memory device of a plurality of memory devices using the generated parity information.
2 . The method of encoding data of claim 1 wherein the scheme for the RAID is RAID 5.
3 . The method of encoding data of claim 1 wherein the scheme for the RAID is RAID 6.
4 . The method of encoding data of claim 1 , further comprising:
splitting data into a plurality of Galois field elements by selecting bits in increments of n bits.
5 . The method of encoding data of claim 1 , further comprising:
calculating a plurality of GF(2{circumflex over ( )}N) field elements utilizing vector architecture of a plurality of central processing units.
6 . The method of encoding data of claim 5 , further comprising:
loading data onto a high-bit register associated with at least one of the plurality of central processing units;
splitting the data loaded onto the high-bit register into separate elements of the plurality of Galois field elements.
7 . The method of claim 1 , further comprising:
executing a vector multiplication operation by an element X when a step size Nis equal to the bit depth of a high-bit register.
8 . The method of claim 1 , further comprising:
receiving recovery information regarding a status of the recovered stored data.
9 . The method of claim 8 , further comprising:
evaluating a performance metric with the recovery information received.
10 . The method of claim 1 , further comprising:
selecting a bit of an element of the plurality of Galois field elements in an increment equal to a bit depth of one element of a vector register.