Flexible parity generation circuit

• US 5,675,726 A
• Filed: 11/08/1995
• Issued: 10/07/1997
• Est. Priority Date: 03/12/1992
• Status: Expired due to Term

• Current Assignee: EMC Corporation (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Carmichael, Richard D., Brant, William A., Nielson, Michael E., Tang, Tin S., Hohenstein, Gerald Lee
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Palys, Joseph E.
• Application Number:
  US08/555,331
• Time in Patent Office: 699 Days
• Field of Search: 395/182.04, 395/182.07, 395/183.08, 395/441, 395/182.05, 395/405, 395/439, 395/454, 395/484, 395/494, 395/495, 371/40.4, 371/49.2, 371/51.1
• US Class Current: 714/6.21
• 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
• CPC Class Codes: G11B 20/1833 by adding special lists or symbols to the coded information G11B20/1806, G11B20/1866 take precedence

Abstract

A redundant array computer system having a high-speed CPU bus and lower-speed I/O buses, in which parity blocks are generated for a plurality of data blocks from multiple CPU bus logical channels in a randomly-interleaved manner to provide enhanced I/O transfer rates. For example, such a system may have two channels for processing two sets of data. The parity generation technique employs switching means to switch channels on the CPU bus between the first set and the second set, generating parity information that can be transferred independently over two I/O buses. The parity generation technique achieves an effective I/O bus transfer rate more closely matched to the speed of the CPU bus. The invention shares a single XOR gate and related support circuitry between multiple logical channels by providing a configurable electronic memory, thus achieving economies in implementation. For certain system applications, it may be desirable to utilize the RAM as a large, unified FIFO. Thus, the system can be adapted to generate parity information for very large blocks of data in a single channel.

Claims

1. A method for generating redundancy blocks associated with a multiplicity of data blocks for each of a plurality of data channels in conjunction with a data block modification operation, said method comprising the steps of:

logically partitioning a memory device into a like plurality of data storage locations corresponding to said plurality of data channels;

storing a first data block and associated first at least one redundancy block from a first of said plurality of data channels in a first of said data storage locations;

interleaving and storing a second data block and associated second at least one redundancy block from a second of said plurality of data channels in a second of said data storage locations timewise during the storing of said first data block and said associated first at least one redundancy block;

modifying said first data block to a modified first data block;

inputting said modified first data block to said first of said data storage locations;

and computing an associated modified first at least one redundancy block based upon said first data block, said associated first at least one redundancy block, and said modified first data block.

2. The method of claim 1 further comprising the step of:

replacing in a first of said data storage locations said first data block with said modified first data block; and

further replacing in a first of said data storage locations said associated first at least one redundancy block with said associated modified first at least one redundancy block.

3. The method of claim 1 further comprising the steps of:

also modifying said second data block to a modified second data block;

also inputting said modified second data block to said second of said data storage locations; and

also computing an associated modified second at least one redundancy block based upon said second data block, said associated second at least one redundancy block and said modified second data block.

4. The method of claim 1 wherein said step of storing is carried out by the step of:

writing said first data block and associated first at least one redundancy block into a portion of said first of said data storage locations.

5. The method of claim 1 wherein said step of computing is carried out by the step of:

XORing said first data block, said associated first at least one redundancy block and said modified first data block to provide said associated modified first at least one redundancy block.

6. The method of claim 1 wherein said step of logically partitioning is carried out by a like plurality of first-in/first-out registers.

7. The method of claim 6 wherein said step of logically partitioning is further carried out by the step of:

selectively enabling an individual one of said plurality of first-in/first out registers corresponding to a selected one of said plurality of data channels.

8. The method of claim 1 wherein said step of logically partitioning is carried out by at least one randomly accessible memory array.

9. The method of claim 8 wherein said step of logically partitioning is further carried out by the step of:

addressing a selected one of said plurality of data storage locations of said randomly accessible memory array corresponding to a selected one of said plurality of data channels.

10. The method of claim 9 wherein said step of addressing is carried out by the step of:

coupling a counter to each of said plurality of data channels to provide a pointer to a portion of each of said data storage locations for said step of storing.

11. The method of claim 10 wherein said step of coupling is carried out by the step of:

programming each of said counters to a block size of said data blocks on each of said plurality of data channels.

12. The method of claim 1 wherein said step of interleaving and storing a second data block comprises randomly interleaving said second data block in said second of said data storage locations.

13. The method of claim 1 wherein said step of computing an associated modified first at least one redundancy block comprises performing at least one logical XOR operation on said first data block, said associated first at least one redundancy block, and said modified first data block.

14. The method of claim 13 wherein said step of computing an associated modified first at least one redundancy block comprises computing an associated modified first at least one parity block.

15. A multi-channel redundancy block generation circuit comprising:

an input data bus for receiving data blocks and associated redundancy blocks from a plurality of logical data channels;

a memory device logically partitioned into a like plurality of data storage locations, each corresponding to one of said plurality of logical data channels;

a switching circuit operatively coupled to said data input bus for selectively applying said data blocks and associated redundancy blocks from said plurality of logical data channels in a timewise interleaved manner to at least one data input of said memory device;

an address selector circuit operatively coupled to an address input of said memory device for directing said data blocks and associated redundancy blocks from said plurality of logical data channels to a desired location in a corresponding one of said plurality of data storage locations in said memory device;

a multi-input redundancy block generator coupled to at least one output of said memory device for generating at least one redundancy block in response to data maintained in a portion of a particular one of said plurality of data storage locations; and

an output data bus coupled to receive an output of said multi-input redundancy block generator for transferring said at least one redundancy block to a corresponding one of said plurality of logical data channels.

16. The multi-channel redundancy block generation circuit of claim 15 wherein said memory device comprises a plurality of first-in/first-out registers.

17. The multi-channel redundancy block generation circuit of claim 15 wherein said memory device comprises a randomly accessible memory device having a plurality of non-overlapping data storage locations.

18. The multi-channel redundancy block generation circuit of claim 15 wherein said switching circuit further selectively applies said data blocks and associated redundancy data blocks for a selected one of said plurality of logical data channels to said at least one input of said memory device.

19. The multi-channel redundancy block generation circuit of claim 18 wherein outputs from a particular one of said plurality of data storage locations in said memory device corresponding to said selected one of said plurality of logical data channels are output to said multi-input redundancy block generator.

20. The multi-channel redundancy block generation circuit of claim 15 further comprising:

an addressing circuit coupled to an address input of said memory device for directing said data blocks and associated redundancy blocks for each of said plurality of logical data channels to a corresponding one of said like plurality of data storage locations.

21. The multi-channel redundancy block generation circuit of claim 20 wherein said addressing circuit further comprises:

a counter associated with each of said plurality of logical data channels for providing a count to said addressing circuit indicating a pointer to a portion of one of said data storage locations corresponding to a selected one of said logical data channels.

22. The multi-channel redundancy block generation circuit of claim 21 wherein said counter is programmable with a block size of said data blocks on each of said plurality of logical data channels.

23. The multi-channel redundancy block generation circuit of claim 15 wherein said multi-input redundancy block generator is a two input redundancy block generator.

24. A multi-channel redundancy block generation circuit, comprising:

an input data bus for receiving data blocks and associated redundancy blocks from a plurality of logical data channels;

a memory device logically partitioned into a like plurality of data storage locations, each corresponding to one of said plurality of logical data channels;

a switching circuit operatively coupled to said data input bus for selectively applying said data blocks and associated redundancy blocks from said plurality of logical data channels in a timewise, interleaved manner to at least one data input of said memory device;

an address selector circuit operatively coupled to an address input of said memory device for directing said data blocks and associated redundancy blocks from said plurality of logical data channels to a desired location in a corresponding one of said plurality of data storage locations in said memory device;

a multi-input redundancy block generator coupled to at least one output of said memory device for generating at least one redundancy block in response to data maintained in a portion of a particular one of said plurality of data storage locations; and

an output data bus coupled to receive an output of said multi-input redundancy block generator for transferring said at least one redundancy block to a corresponding one of said plurality of logical data channels.