System and methods for accelerated data storage and retrieval

• US 7,130,913 B2
• Filed: 07/28/2003
• Issued: 10/31/2006
• Est. Priority Date: 03/11/1999
• Status: Expired due to Term

• Current Assignee: Realtime Data LLC (Realtime Data Compression Systems, Inc.)
• Original Assignee: Realtime Data LLC (Realtime Data Compression Systems, Inc.)
• Inventors: Fallon, James J.
• Primary Examiner(s): Eng, David Y.
• Application Number:
  US10/628,795
• Publication Number:
  US 20040073746A1
• Time in Patent Office: 1,191 Days
• Field of Search: 709/231, 709/233
• US Class Current: 709/231
• CPC Class Codes: G06F 16/1744 using compression, e.g. sparse files
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC
• CPC Class Codes: H04N 19/115 Selection of the code volume for a coding unit prior to coding
• CPC Class Codes: H04N 19/15 by monitoring actual compressed data size at the memory before deciding storage at the transmission buffer
• CPC Class Codes: H04N 19/152 by measuring the fullness of the transmission buffer
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 5/781 on disks or drums
• CPC Class Codes: H04N 5/843 on film
• CPC Class Codes: H04N 5/85 on discs or drums
• CPC Class Codes: H04N 5/907 using static stores, e.g. storage tubes or semiconductor memories H04N5/91 takes precedence
• CPC Class Codes: H04N 9/8042 involving data reduction
• CPC Class Codes: H04N 9/8227 the additional signal being at least another television signal

Abstract

Systems and methods for providing accelerated data storage and retrieval utilizing lossless data compression and decompression. A data storage accelerator includes one or a plurality of high speed data compression encoders that are configured to simultaneously or sequentially losslessly compress data at a rate equivalent to or faster than the transmission rate of an input data stream. The compressed data is subsequently stored in a target memory or other storage device whose input data storage bandwidth is lower than the original input data stream bandwidth. Similarly, a data retrieval accelerator includes one or a plurality of high speed data decompression decoders that are configured to simultaneously or sequentially losslessly decompress data at a rate equivalent to or faster than the input data stream from the target memory or storage device. The decompressed data is then output at rate data that is greater than the output rate from the target memory or data storage device. The data storage and retrieval accelerator method and system may employed: in a disk storage adapter to reduce the time required to store and retrieve data from computer to disk; in conjunction with random access memory to reduce the time required to store and retrieve data from random access memory; in a display controller to reduce the time required to send display data to the display controller or processor; and/or in an input/output controller to reduce the time required to store, retrieve, or transmit data.

Claims

1. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for providing accelerated data storage and retrieval, said method steps comprising:

receiving a data stream at an input data transmission rate which is greater than a data storage rate of a target storage device;

compressing the data stream at a compression rate that increases the effective data storage rate of the data storage device; and

storing the compressed data stream in the target storage devices,

wherein the input data stream comprises one or more data blocks, and

wherein the instructions for performing compression comprise instructions for;

(a) compressing an input data block with a plurality of encoders to provide a set of encoded data blocks;

(b) determining a compression ratio for each of the encoded data blocks;

(c) comparing each compression ratio with an a priori specified compression threshold;

(d) selecting for output an encoded data block in the set having the highest compression ratio and appending a corresponding descriptor, if at least one of the compression ratios exceeds the a priori specified compression threshold; and

(e) repeating steps (a) through (d) for each successive input data block.

2. The program storage device of claim 1, wherein the compression rate is at least equal to the ratio of the input data transmission rate to the data storage rate so as to provide continuous storage of the input data stream at the input data transmission rate.

3. The program storage device of claim 1, further including instructions for performing the steps of:

determining the input data transmission rate and the data compression rate;

comparing the input data transmission rate, the data compression rate and the data storage rate to determine if they are compatible; and

adjusting one or more parameters to obtain compatibility between the input data transmission rate, the data compression rate and the data storage rate, if they are determined to be incompatible.

4. The program storage device of claim 3, wherein the instructions for performing the adjusting step include instructions for performing one of adjusting the input data transmission rate, adjusting the compression rate and a combination thereof.

5. The program storage device of claim 4, wherein the instructions for performing the adjusting step further include instructions for temporarily buffering one of the input data stream, the compressed data stream, and a combination thereof.

6. The program storage device of claim 1, further including instructions for performing the steps of:

retrieving the compressed data stream from the target storage device at a rate equal to a data access rate of the target storage device; and

decompressing the compressed data at a decompression rate that increases the effective data access rate of the target storage device.

7. The program storage device of claim 6, wherein the decompression rate is equal to the ratio of the data access rate to the input data transmission rate so as to obtain an output data transmission rate which is equal to the input data transmission rate.

8. The program storage device of claim 6, wherein the decompression rate is equal to or greater than the ratio of the data access rate to a maximum accepted output data transmission rate so as to provide a continuous and optimal data output transmission rate.

9. The program storage device of claim 6, further including instructions for performing the steps of:

determining the data retrieval rate and the data decompression rate;

comparing the data retrieval rate, the data decompression rate and the output data transmission rate to determine if they are compatible; and

adjusting one or more parameters to obtain compatibility between the data retrieval rate, the data decompression rate and the output data transmission rate if they are determined to be incompatible.

10. The program storage device of claim 9, wherein the instructions for performing the adjusting step include instructions for performing one of adjusting the data retrieval rate, adjusting the decompression rate, and a combination thereof.

11. The program storage device of claim 9, wherein the instructions for performing the adjusting step include instructions for temporarily buffering one of the retrieved data stream, the decompressed data stream, and a combination thereof.

12. The program storage device of claim 1, further including instructions for selecting for output the input data block and appending a null descriptor to the input data block if all of the compression ratios of the corresponding encoded data blocks fall below the a priori compression limit.

13. The program storage device of claim 1, wherein the instructions for the compressing step include instructions for simultaneously compressing the data block with a plurality of encoders in parallel.

14. The program storage device of claim 1 wherein the instructions for performing the compressing step include instructions for sequentially compressing the data block with the plurality of encoders.

15. The program storage device of claim 6, wherein the instructions for performing the decompressing step include instructions for performing the steps of:

(a) extracting an encoding type descriptor from an input data block;

(b) decompressing the data block in accordance with a decoder corresponding to the extracted descriptor; and

(c) repeating steps (a) and (b) for each successive input data block.

16. The program storage device of claim 15, further including instructions for outputting the input data block if the extracted descriptor is a null descriptor.

17. A method for providing accelerated data storage and retrieval, comprising:

receiving a data stream at an input data transmission rate which is greater than a data storage rate of a target storage device;

compressing the data stream at a compression rate that increases the effective data storage rate of the data storage device; and

storing the compressed data stream in the target storage device,

wherein the input data stream comprises one or more data blocks, and

wherein the instructions for performing compression comprise instructions for;

(a) compressing an input data block with a plurality of encoders to provide a set of encoded data blocks;

(b) determining a compression ratio for each of the encoded data blocks;

(c) comparing each compression ratio with an a priori specified compression threshold;

(d) selecting for output an encoded data block in the set having the highest compression ratio and appending a corresponding descriptor, if at least one of the compression ratios exceeds the a priori specified compression threshold; and

(e) repeating steps (a) through (d) for each successive input data block.

18. The method of claim 17, wherein the compression rate is at least equal to the ratio of the input data transmission rate to the data storage rate so as to provide continuous storage of the input data stream at the input data transmission rate.

19. The method of claim 17, further comprising the steps of:

determining the input data transmission rate and the data compression rate;

comparing the input data transmission rate, the data compression rate and the data storage rate to determine if they are compatible; and

adjusting one or more parameters to obtain compatibility between the input data transmission rate, the data compression rate and the data storage rate, if they are determined to be incompatible.

20. The method of claim 19, wherein adjusting comprises one of adjusting the input data transmission rate, adjusting the compression rate and a combination thereof.