Patent EP-0825534-A2 (EP)
Title: Method and apparatus for parity block generation
Inventor: OLDFIELD BARRY J
IPC: G06F3/06
Filed: 1997-01-24
Abstract: An apparatus (10, 11, 12, 60, 61, 62, 63) for generating parity
blocks in a RAID system (FIG. 1, FIG. 5) includes a PRAM control unit (12, 62),
two parity memories (10, 11, 60, 61) each coupled to the PRAM control unit
(12, 62), and in several alternative embodiments, a valid contents memory (63)
for tracking the contents of the parity memories (10, 11, 60, 61). Parity blocks
are generated by performing an exclusive OR operation between all of the
corresponding data words in the data blocks of the stripe. The apparatus (10,
11, 12, 60, 61, 62, 63) stores unmodified data words of the first data block
transferred into one of the parity memories (10, 11, 60, 61). For subsequently
transferred data blocks, the apparatus (10, 11, 12, 60, 61, 62, 63) generates
parity blocks by performing successive exclusive OR operations between data
words in data blocks of the stripe and the corresponding parity generation data
words stored in one of the parity memories (10, 11, 60, 61) as the data words
are transferred over a bus (4, 51) internal to the RAID system. As successive
data blocks of the stripe are transferred over the bus (4, 51), the results of the
exclusive OR operations are alternately stored in the two parity memories (10,
11, 60, 61). Alternately dedicating one parity memory (10, 11, 60, 61) for
storing the results of the exclusive OR operation which will be performed and
one parity memory (10, 11, 60, 61) 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 implementations using a single parity memory, a time delay is
incurred to bring the bus (4, 51) connecting the PRAM control unit to the single
parity memory to the tri-state condition between a read access and a write
access. This delay is eliminated by using two parity memories (10, 11, 60, 61).
In addition, by using two parity memories (10, 11, 60, 61), the read access
operation to one of the parity memories (10, 11, 60, 61) and the write access
operation to the other of the parity memories (10, 11, 60, 61) can be pipelined,
providing a further improvement in the parity block generation rate over
implementations using a single parity memory. In a first embodiment of the 
PRAM control unit (12), a flip/flop (33) tracks which of the two parity memories
(10, 11) contains the valid contents. A second embodiment of the apparatus
(60, 61, 62, 63) uses a valid contents memory (63) and a top counter (26) to
support the generation of the parity block with fragmented in order transfers of
data blocks in the stripe. The valid contents memory (63) stores a set of valid
contents bits used by the PRAM control unit (62) for determining, for each pair
of corresponding memory locations in the parity memories (60, 61), which parity
memory (60, 61) contains the valid contents. For the in order transfer of data
blocks fragments, the top counter (26) tracks into which storage locations in the
parity memories (60, 61) data words have been previously stored. The
preferred embodiment of the apparatus (60, 61, 62, 63) for generating parity
blocks allows generation of parity blocks while data block fragments are
transferred over the bus (51) without regard to order. The preferred
embodiment employs a set of first access bits stored in the valid contents
memory (63) to indicate to which storage locations in the parity memories (60,
61) data words have previously been stored.