Storage device parity computation

• US 20050278612A1
• Filed: 06/10/2004
• Published: 12/15/2005
• Est. Priority Date: 06/10/2004
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Edirisooriya, Samanatha J.
• Granted Patent: US 7,318,190 B2
• Time in Patent Office: Days
• US Class Current: 714/800
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1054 Parity-fast hardware, i.e. dedicated fast hardware for RAID systems with parity

Abstract

Provided are a techniques for receiving a modification to at least one data block. Parity blocks that are to be computed for the at least one data block are determined. At least one common term for computations for the determined parity blocks is determined. A first parity block from the determined parity blocks is computed that generates intermediate parity results for the common term. A second parity block from the determined parity blocks is computed using the intermediate parity results.

Claims

1. A method for computing parity information, comprising:

receiving a modification to at least one data block;

determining parity blocks that are to be computed for the at least one data block;

determining at least one common term for computations for the determined parity blocks;

computing a first parity block from the determined parity blocks that generates intermediate parity results for the common term; and

computing a second parity block from the determined parity blocks using the intermediate parity results.

2. The method of claim 1, further comprising:

storing the intermediate parity results in a storage area for use in computing the second parity block.

3. The method of claim 1, wherein the first parity block is a horizontal parity block and the second parity block is a diagonal parity block.

4. The method of claim 1, further comprising:

computing a last parity block from the determined parity blocks without storing the intermediate parity results.

5. The method of claim 1, wherein the first parity block is computed in a first Random Access Memory (RAM) and wherein the intermediate parity results are stored in a second Random Access Memory (RAM).

6. The method of claim 1, wherein the at least one data block is a first data block, wherein the first parity block is a new first parity block, and wherein computing the new first parity block further comprises:

moving existing data for the first data block into a first storage area;

performing an exclusive-or operation on contents of the first storage area and new data for the first data block, wherein the output of the exclusive-or operation is stored into the first storage area;

storing the contents of the first storage area into a second storage area;

performing an exclusive-or operation on the contents of the first storage area with an existing first parity block for the first data block, wherein the output of the exclusive-or operation is stored into the first storage area; and

.

outputting the new first parity block for the first data block from the first storage area.

7. The method of claim 6, wherein the second parity block is a new second parity block and wherein computing the new second parity block further comprises:

performing an exclusive-or operation on contents of the second storage area and an existing second parity block for the first data block, wherein the output of the exclusive-or operation is stored in the first storage area; and

outputting the new second parity block for the first data block from the first storage area.

8. An article of manufacture for computing parity information, wherein the article of manufacture comprises a computer readable medium storing instructions, and wherein the article of manufacture is operable to:

receive a modification to at least one data block;

determine parity blocks that are to be computed for the at least one data block;

determine at least one common term for computations for the determined parity blocks;

compute a first parity block from the determined parity blocks that generates intermediate parity results for the common term; and

compute a second parity block from the determined parity blocks using the intermediate parity results.

9. The article of manufacture of claim 8, wherein the article of manufacture is further operable to:

store the intermediate parity results in a storage area for use in computing the second parity block.

10. The article of manufacture of claim 8, wherein the first parity block is a horizontal parity block and the second parity block is a diagonal parity block.

11. The article of manufacture of claim 8, wherein the article of manufacture is further operable to:

compute a last parity block from the determined parity blocks without storing the intermediate parity results.

12. The article of manufacture of claim 8, wherein the first parity block is computed in a first Random Access Memory (RAM) and wherein the intermediate parity results are stored in a second Random Access Memory (RAM).

13. The article of manufacture of claim 8, wherein the at least one data block is a first data block, wherein the first parity block is a new first parity block, and wherein the article of manufacture is further operable to:

move existing data for the first data block into a first storage area;

perform an exclusive-or operation on contents of the first storage area and new data for the first data block, wherein the output of the exclusive-or operation is stored into the first storage area;

store the contents of the first storage area into a second storage area;

perform an exclusive-or operation on the contents of the first storage area with an existing first parity block for the first data block, wherein the output of the exclusive-or operation is stored into the first storage area; and

output the new first parity block for the first data block from the first storage area.

14. The article of manufacture of claim 13, wherein the second parity block is a new second parity block and wherein the article of manufacture is further operable to:

perform an exclusive-or operation on contents of the second storage area and an existing second parity block for the first data block, wherein the output of the exclusive- or operation is stored in the first storage area; and

output the new second parity block for the first data block from the first storage area.

15. A system for computing parity information, comprising:

a first storage area at an Input/Output processor;

a second storage area at the Input/Output processor coupled to the first storage area; and

circuitry at the Input/Output processor operable to;

compute a first parity block that generates intermediate parity results for a common term, wherein the intermediate parity results are stored in the second storage area, and wherein the first parity block is output from the first storage area; and

compute a second parity block using the intermediate parity results.

16. The system of claim 15, wherein the circuitry is further operable to:

receive a modification to at least one data block;

determine parity blocks that are to be computed for the at least one data block; and

determine at least one common term for computations for the determined parity blocks.

17. The system of claim 16, wherein the circuitry is further operable to:

compute a last parity block from the determined parity blocks without storing the intermediate parity results.

18. The system of claim 15, wherein the first parity block is a horizontal parity block and the second parity block is a diagonal parity block.

19. The system of claim 15, wherein the first storage area is a first Random Access Memory (RAM) and wherein the second storage area is a second Random Access Memory (RAM).

20. The system of claim 15, wherein the at least one data block is a first data block, wherein the first parity block is a new first parity block, and wherein the circuitry is further operable to:

move existing data for the first data block into a first storage area;

perform an exclusive-or operation on contents of the first storage area and new data for the first data block, wherein the output of the exclusive-or operation is stored into the first storage area;

store the contents of the first storage area into a second storage area;

perform an exclusive-or operation on the contents of the first storage area with an existing first parity block for the first data block, wherein the output of the exclusive-or operation is stored into the first storage area; and

output the new first parity block for the first data block from the first storage area.

21. The system of claim 20, wherein the second parity block is a new second parity block and wherein the circuitry is further operable to:

perform an exclusive-or operation on contents of the second storage area and an existing second parity block for the first data block, wherein the output of the exclusive- or operation is stored in the first storage area; and

output the new second parity block for the first data block from the first storage area.

22. A system, comprising:

a first storage area that is capable of outputting a computed value for a parity block using any stored intermediate parity results;

a second storage area coupled to the first storage area that is capable of storing intermediate parity results;

a first line that is capable of transmitting data to a first exclusive-or gate;

a second multiplexor that is capable of transmitting output to the first exclusive-or gate;

a third multiplexor that is capable of receiving as input the output of the first exclusive-or gate, a variable, and input for a modified data block, and that is capable of outputting data to the first storage area; and

a fourth multiplexor that is capable of receiving as input an output of the first storage area, a variable, and output of the second storage area, and that is capable of outputting data to the second storage area.

23. The system of claim 22, further comprising:

means for computing a first parity block that generates intermediate parity results for a common term, wherein the intermediate parity results are stored in the second storage area, and wherein the first parity block is output from the first storage area; and

means for computing a second parity block using the intermediate parity results.