Flexible redundant array of independent disks (RAID) computation device

1. A method for calculating M number of redundancy blocks for multiple (N) data blocks of a plurality (D) of words each, the method comprising:

receiving the number (M) of redundancy blocks by a calculator that comprises multiple (R) calculation units and a buffer having a buffer size;

configuring the calculator according to M and R, wherein the configuring includes determining a size of each data block in response to a ratio between the buffer size and a number of activated calculation units;

concurrently calculating, if M equals R, by the multiple (R) calculation units of the calculator, R sets of parity vectors, wherein each set includes a plurality (D) of parity vectors; and

calculating the M redundancy blocks based on the R sets of parity vectors.

2. The method according to claim 1 , comprising:

concurrently calculating, if M is smaller than R, by a subset of M calculation units of the calculator, M sets of parity vectors, each set including a plurality (D) of parity vectors; and

calculating the M redundancy blocks based on the M sets of parity vectors.

3. The method according to claim 1 , comprising:

calculating, if M equals one, by a single calculation unit of the calculator, a single set of parity vectors that includes a plurality (D) of parity vectors; and

calculating a redundancy block based on the set of parity vectors.

4. The method according to claim 3 , wherein if M exceeds R, then calculating up to R parity blocks at a time until calculating the zeroth till (M−1)'th parity block.

5. The method according to claim 1 , wherein if M exceeds R, and M modulo R equals a difference X, the method further comprising:

selecting a certain set of R rows of a Vandermonde matrix;

concurrently calculating by the multiple (R) calculation units of the calculator, R sets of parity vectors, each set including a plurality (D) of parity vectors, wherein the calculating comprises processing the certain set of R rows of the Vandermonde matrix;

if there are more than R rows of the Vandermonde matrix that were not processed, then selecting a new certain set of R rows of the Vandermonde matrix and concurrently calculating by the multiple (R) calculation units of the calculator, new R sets of parity vectors, wherein the calculating comprises processing the new certain set of R rows of the Vandermonde matrix;

if there are X rows of the Vandermonde matrix that were not processed, then selecting a further certain set of X rows of the Vandermonde matrix and concurrently calculating by X calculation units of the calculator, further X sets of parity vectors, wherein the calculating comprises processing the further certain set of X rows of the Vandermonde matrix; and

calculating the M redundancy blocks based on all sets of the parity vectors.

6. The method according to claim 1 , wherein different calculation units calculate different sets of parity vectors by multiplying different rows of a Vandermonde matrix by intermediate vectors driven from the multiple data blocks.

7. The method according to claim 1 , wherein different values of M represent different redundant array of independent disks (RAID) levels.

8. The method according to claim 1 , wherein R is not smaller than four.

9. The method according to claim 1 , further comprising receiving multiple coefficients of a Vandermonde matrix in descriptors of the data blocks.

10. The method according to claim 1 , wherein an adding operation of the calculator is executed by exclusive OR (XOR) gates.

11. A system for calculating M number of redundancy blocks for multiple (N) data blocks of a plurality (D) of words each, the system comprising:

a memory unit that is arranged to receive the number (M) of redundancy blocks;

a calculator that comprises multiple (R) calculation units and a buffer having a buffer size; and

a controller that is arranged to configure the calculator according to M and R including determining a size of each data block in response to a ratio between the buffer size and a number of activated calculation units,

wherein the multiple (R) calculation units are arranged to concurrently calculate, if M equals R, R sets of parity vectors, each set including a plurality (D) of parity vectors, and

wherein the calculator is further arranged to calculate the M redundancy blocks based on the R sets of parity vectors.

12. The system according to claim 11 , wherein if M is smaller than R, then a subset of M calculation units of the calculator are arranged to calculate M sets of parity vectors, each set including a plurality (D) of parity vectors, and

wherein the calculator is further arranged to calculate the M redundancy blocks based on the M sets of parity vectors.

13. The system according to claim 12 , wherein different values of M represent different redundant array of independent disks (RAID) levels.

14. The system according to claim 11 , wherein if M equals one, then a single calculation unit of the calculator is arranged to calculate a single set of parity vectors that includes a plurality (D) of parity vectors, and

wherein the calculator is further arranged to calculate a redundancy block based on the set of parity vectors.

15. The system according to claim 11 , wherein if M exceeds R, and M modulo R equals a difference X, then:

the controller is arranged to select a certain set of R rows of a Vandermonde matrix, wherein the multiple (R) calculation units are arranged to concurrently calculate R sets of parity vectors, each set including a plurality (D) of parity vectors, and wherein the calculating comprises processing the certain set of R rows of the Vandermonde matrix;

if there are more than R rows of the Vandermonde matrix that were not processed, then the controller is arranged to select a new certain set of R rows of the Vandermonde matrix, wherein the multiple (R) calculation units are arranged to concurrently calculate new R sets of parity vectors, and wherein the calculating comprises processing the new certain set of R rows of the Vandermonde matrix; and

if there are X rows of the Vandermonde matrix that were not processed, then the controller is arranged to select a further certain set of X rows of the Vandermonde matrix and X calculation units are arranged to calculate further X sets of parity vectors, wherein the calculating comprises processing the further certain set of X rows of the Vandermonde matrix, and wherein the calculator is further arranged to calculate the M redundancy blocks based on all sets of the parity vectors.

16. The system according to claim 11 , wherein different calculation units are arranged to calculate different sets of parity vectors by multiplying different rows of a Vandermonde matrix by intermediate vectors driven from the multiple data blocks.

17. A method for reconstructing N number of information blocks of a plurality (D) of words each, the method comprising:

receiving a value of N, by a calculator that comprises multiple (R) calculation units and a buffer having a buffer size, wherein the N information blocks are selected from a group of (N+M) information blocks, the group of (N+M) information blocks comprising N data blocks and M parity blocks;

configuring the calculator according to N and R, wherein the configuring includes determining a size of each reconstructed data block in response to a ratio between the buffer size and a number of activated calculation units;

concurrently calculating, if N equals R, by the multiple (R) calculation units of the calculator, R sets of reconstructed data vectors, each set including a plurality (D) of reconstructed data vectors; and

generating N reconstructed data blocks based on the R sets of reconstructed data vectors.

18. The method according to claim 17 , comprising:

concurrently calculating, if N is smaller than R, by a subset of N calculation units of the calculator, N sets of reconstructed data vectors, each set including a plurality (D) of reconstructed data vectors; and

calculating the N reconstructed data blocks based on the N sets of reconstructed data vectors.

19. The method according to claim 18 , wherein R is not smaller than four.

20. The method according to claim 19 , wherein if N exceeds R, then calculating up to R reconstructed data blocks at a time until calculating the zeroth till (N−1)'th reconstructed data block.

21. The method according to claim 18 , further comprising receiving multiple coefficients of an inverted matrix in descriptors of the reconstructed data blocks.

22. The method according to claim 18 , wherein an adding operation of the calculator is executed by exclusive OR (XOR) gates.

23. The method according to claim 17 , comprising:

calculating, if N equals one, by a single calculation unit of the calculator, a single set of reconstructed data vectors that includes a plurality (D) of reconstructed data vectors; and

calculating a reconstructed data block based on the set of reconstructed data vectors.

24. The method according to claim 17 , wherein if N exceeds R, and N modulo R equals a difference X, the method further comprising:

selecting a certain set of R rows of an inverted matrix, wherein:

the inverted matrix is calculated by inverting a reduced matrix,

the reduced matrix is calculated by reducing M rows of an input matrix that comprises (N+M) rows,

the input matrix comprises a first group of N rows and a second group of M rows,

the first group of rows form a unity matrix, and

the second group of rows form a Vandermonde matrix;

concurrently calculating, by the multiple (R) calculation units of the calculator, R sets of reconstructed data vectors, each set including a plurality (D) of reconstructed data vectors, wherein the calculating comprises processing the certain set of R rows of the inverted matrix;

if there are more than R rows of the inverted matrix that were not processed, then selecting a new certain set of R rows of the inverted matrix and concurrently calculating, by the multiple (R) calculation units of the calculator, new R sets of reconstructed data vectors, wherein the calculating comprises processing the new certain set of R rows of the inverted matrix;

if there are X rows of the inverted matrix that were not processed, then selecting a further certain set of X rows of the inverted matrix and concurrently calculating, by X calculation units of the calculator, further X sets of reconstructed data vectors, wherein the calculating comprises processing the further certain set of X rows of the inverted matrix; and

calculating the N reconstructed data blocks based on all sets of the reconstructed data vectors.

25. The method according to claim 24 , wherein different calculation units calculate different sets of reconstructed data vectors by multiplying different rows of the inverted matrix by intermediate vectors driven from the N reconstructed data blocks.

26. A system for reconstructing N number of information blocks of a plurality (D) of words each, the system comprising:

a memory unit adapted to receive a value of N;

a calculator that comprises multiple (R) calculation units and a buffer having a buffer size; and

a controller that is arranged to configure the calculator in response to R and N including determining a size of each reconstructed data block in response to a ratio between the buffer size and a number of activated calculation units,

wherein the multiple calculation units are arranged to concurrently calculate, if N equals R, by the multiple (R) calculation units of the calculator, R sets of reconstructed data vectors, each set including a plurality (D) of reconstructed data vectors,

wherein the calculator is further arranged to generate N reconstructed data blocks based on the R sets of reconstructed data vectors, and

wherein the N information blocks are selected from a group of (N+M) information blocks, the group of (N+M) information blocks comprising N data blocks and M parity blocks.

27. The system according to claim 26 , wherein if N is smaller than R, then a subset of N calculation units of the calculator are arranged to calculate N sets of reconstructed data vectors, each set including a plurality (D) of reconstructed data vectors, and

wherein the calculator is further arranged to calculate the N reconstructed data blocks based on the N sets of reconstructed data vectors.

28. The system according to claim 26 , wherein if N equals one, then a single calculation unit of the calculator is arranged to calculate a single set of reconstructed data vectors that includes a plurality (D) of reconstructed data vectors, and

wherein the calculator is further arranged to calculate a reconstructed data block based on the set of reconstructed data vectors.

29. The system according to claim 26 , wherein if N exceeds R, and N modulo R equals a difference X, then:

the controller is arranged to select a certain set of R rows of an inverted matrix, wherein:

the inverted matrix is calculated by inverting a reduced matrix,

the reduced matrix is calculated by reducing N rows of an input matrix that comprises (N+M) rows,

the input matrix comprises a first group of N rows and a second group of M rows,

the first group of rows form a unity matrix, and

the second group of rows form a Vandermonde matrix;

wherein the multiple (R) calculation units are arranged to concurrently calculate R sets of reconstructed data vectors, each set including a plurality (D) of reconstructed data vectors, and wherein the calculating comprises processing the certain set of R rows of the inverted matrix;

if there are more than R rows of the inverted matrix that were not processed, then the controller is arranged to select a new certain set of R rows of the inverted matrix, wherein the multiple (R) calculation units are arranged to concurrently calculate new R sets of reconstructed data vectors, and wherein the calculating comprises processing the new certain set of R rows of the inverted matrix; and

if there are X rows of the inverted matrix that were not processed, then the controller is arranged to select a further certain set of X rows of the inverted matrix and X calculation units are arranged to calculate further X sets of reconstructed data vectors, wherein the calculating comprises processing the further certain set of X rows of the inverted matrix, and wherein the calculator is further arranged to calculate N reconstructed data blocks based on all sets of the reconstructed data vectors.

30. The system according to claim 26 , wherein different calculation units are arranged to calculate different sets of reconstructed data vectors by multiplying different rows of the inverted matrix by intermediate vectors driven from the N reconstructed data blocks.