US 5,856,989 A · Method and apparatus for parity block generation

Abstract

An apparatus for generating parity blocks in a RAID system includes a PRAM control unit, two parity memories each coupled to the PRAM control unit, and in several alternative embodiments, a valid contents memory for tracking the contents of the parity memories. Parity blocks are generated by performing an exclusive OR operation between all of the corresponding data words in the data blocks of the stripe. Results of the exclusive OR operations are alternately stored in the two parity memories. Alternately dedicating one parity memory for storing the results of the exclusive OR operation which will be performed and one parity memory from which the results of the previous exclusive OR operation are loaded allows computation of the parity block to be performed at a higher rate than configurations which use a single parity memory. In a first embodiment of the PRAM control unit, a flip/flop tracks which of the two parity memories contains the valid contents. A second embodiment of the apparatus uses a valid contents memory and a top counter to support the generation of the parity block with fragmented in order transfers of data blocks in the stripe. The preferred embodiment of the apparatus for generating parity blocks allows generation of parity blocks while data block fragments are transferred over the bus without regard to order. The preferred embodiment employs a set of first access bits stored in the valid contents memory to indicate to which storage locations in the parity memories data words have previously been stored.

Claims20

Dependent claims

An apparatus for generating parity data from a plurality of data words, comprising:

a first parity memory including a first set of memory locations;
a second parity memory including a second set of memory locations and;
a parity generation and control unit arranged for receiving said plurality of data words and coupled to said first and said second parity memory, said parity generation and control unit for storing and loading parity generation data words to and from said first and said second parity memory so that said memory locations of said first set of memory locations and said memory locations of said second set of memory locations alternate between sending and receiving said parity generation data words to and from said parity generation and control unit during the generation of said parity data.

In a redundant array storage system including a bus, a plurality of data storage devices, a parity generation and control unit, a first and a second parity memory for storing a plurality of parity generation data words, and a means for determining which of said first and said second parity memory contains valid contents and which of said first and said second parity memory contains invalid contents, a method for generating parity data from a plurality of data words during transfer of said data words over said bus, said method comprising the steps of:

loading a first one of said plurality of parity generation data words from the one of said first and said second parity memory containing said valid contents into said parity generation and control unit;
loading a first one of said plurality of data words from said bus into said parity generation and control unit;
performing an exclusive OR operation using said first one of said plurality of parity generation data words and said first one of said plurality of data words as operands, yielding a result;
and
storing said result in the one of said first and said second parity memory containing invalid contents.

2 more elements

In a redundant array memory system, an apparatus for generating a parity block from a plurality of data blocks each including a plurality of data words, said apparatus comprising:

a means for selectively performing exclusive OR operations yielding parity generation data words;
a means for loading arranged to receive said plurality of data words from said redundant array memory system and coupled to said means for performing exclusive OR operations;
a first parity memory including a first set of memory locations;
a second parity memory including a second set of memory locations;
and
a means for selectively storing and selectively loading arranged for receiving said parity generation data words from said means for performing exclusive OR operations, said means for selectively storing and selectively loading arranged for storing and loading said parity generation data words to and from said first and said second parity memory so that said memory locations of said first set of memory locations and said memory locations of said second set of memory locations alternate between sending and receiving said parity generation data words to and from said means for selectively storing and loading during the generation of said parity block with said means for selectively storing and selectively loading arranged for sending said parity generation data words to said means for selectively performing exclusive OR operations.

3 more elements

Dependencies are inferred from the claim text.

Method and apparatus for parity block generation

Life of this patent

Method and apparatus for parity block generation

Life of this patent

Abstract

Claims20