Abstract:
A highly-efficient system and methodology for organizing, storing and/or transmitting compressed data that achieves optimum compression throughput, enhances overall data compressibility, and reduces decompression latency.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     This invention relates generally to the field of data compression systems, and more specifically to an improved method and format for organizing, storing and transmitting compressed data. 
     2. Discussion of the Prior Art 
     Data compression has become increasingly vital in today&#39;s computer systems due to the high demand for data transmission and storage capacity. In particular, main memory compression is now both feasible and desirable with the advent of parallel compression using a cooperative dictionary, as described in commonly-owned U.S. Pat. No. 5,729,228 to Franaszek et al. entitled PARALLEL COMPRESSION AND DECOMPRESSION USING A COOPERATIVE DICTIONARY, incorporated herein by reference. Parallel compression is a relatively new art in the field of compression. Its main concept is to divide a block of uncompressed data into multiple sectors and then assign them to individual engines for both compression and decompression with all engines sharing a cooperative dictionary such that the compression ratio is close to that of a single-engine design. This results in much better latency and throughput than the previous single-engine designs, thus making main memory compression feasible. It is the case however, that latency and throughput objectives may be better achieved provided there is implemented a highly-efficient compressed data format. 
     It would thus be highly desirable to provide a system and method for organizing compressed data efficiently, particularly, compressed data in parallel format, in order to enhance compression throughput and reduce decompression latency in data storage and data transmission systems. 
     SUMMARY OF THE INVENTION 
     It is an object of the invention to provide a system and method for organizing, storing and/or transmitting compressed data efficiently, particularly, by processing compressed data in parallel in order to enhance compression throughput and reduce decompression latency. 
     It is another object of the invention to provide a system and method that for organizing, storing and/or transmitting compressed data efficiently, particularly, by enabling a compressor mechanism to write out parallel streams of compressed data from multiple engines quickly and with minimal loss of compression ratio and, enabling a decompressor&#39;s engines to extract the individual streams of compressed data easily without separate data delimiters and control. 
     Thus, according to the principles of the invention, there is provided a system and methodology for generating compressed data comprising: inputting information units to one or more parallel executing compression engines and compressing said information units into one or more compressed information units; providing a temporary storage queue associated with each compression engine for temporarily storing one or more compressed information units from its respective compression engine; collecting a compressed information unit in parallel from each temporary storage queue and merging each collected compressed information unit to form a merged word; and, successively forming merged words each comprising collected sets of compressed information units from each temporary storage queue to form a series of merged words for transmission or storage thereof. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     Further features, aspects and advantages of the apparatus and methods of the present invention will become better understood with regard to the following description, appended claims, and accompanying drawings where: 
     FIG. 1 depicts generally a block diagram of the main memory system of the invention including hardware compressor and decompressor mechanisms. 
     FIG. 2 illustrates an example format for compressing information according to the principals of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     Referring to FIG. 1, there is depicted a block diagram of a computer system  100  shown including compressor  120 , a main memory  150  and decompressor  180  components. In a conventional application, the compressor mechanism  120  converts uncompressed input data received from a processor and/or cache memory component  102  and stores the resulting compressed data in the main memory  150 . Subsequently, the decompressor component  180  retrieves the compressed data and converts it back to the original uncompressed data for use in the processor/cache  102 . In general, the compressor  120  may comprise two or more parallel, identical engines and, in the embodiment depicted in FIG. 1, it includes four parallel, identical engines indicated as compressor engines labeled A,B,C and D. In the example system depicted in FIG. 1, each block of uncompressed input data, for example, may total 1 Kbyte, which may be divided into four 256-byte sectors, however, it is understood that uncompressed input data may be any multiple byte length, e.g., 512 bytes. During compression, each engine A,B,C and D processes a different (256-byte) sector in parallel, and saves the resultant compressed data in its own corresponding output queue (COQ)  130   a, b, . . . , d . As each sector&#39;s compressibility will vary, the amount of compressed data in each queue may be different. It should be understood that each of the COQs  130   a, b, . . . , d  are deep enough to hold even an uncompressible sector. If the total number of compressed data bits is not a multiple of 32, i.e., at a word boundary, then the last compressed word is padded with 0&#39;s. 
     As further shown in FIG. 1, the compressor  120  further includes an output merger stage  135  implementing functionality for collecting 4-byte-wide compressed data words from each engine&#39;s COQ  130   a, b, . . . , d , and combining them into 16-byte-wide quadwords, for output to the main memory component  150 . 
     FIG. 2 illustrates an example of how the merger stage  135  organizes the compressed data words efficiently according to the format disclosed hereafter. In the example depicted, Engine A&#39;s COQ  130   a , includes compressed data words A 0  through A 7 ; Engine B&#39;s COQ  130   b  includes compressed data words B 0  through B 2 , Engine C&#39;s COQ  130   c  includes compressed data words C 0  and, Engine D&#39;s COQ  130   d  includes compressed data words D 0  through D 4 . The first compressed word of each COQ, namely words A 0 , B 0  , C 0  and D 0 , also includes a respective byte-wide word count field ‘W A ’, ‘W B ’, ‘W C ’ and ‘W D ’ in its most significant byte position, i.e. bits  0  through  7  with each word count field indicating the number of remaining compressed data words for the respective engine. For example, the remaining word count, W A , of COQ A  130   a , is 0×07 and for COQ C  130   c  the word count field W C . is 0×00. The very first compressed data bits following the word count field starts at bit  8 . 
     At the start of compression output  170 , all four COQs  130   a, b, . . . , d , contribute a compressed data word to the merger stage  135  to form the first quadword (A 0 , B 0 , C 0 , D 0 ). Subsequent quadwords will contain compressed data words in the same queue order. When a COQ has exhausted all its compressed data words, it drops out of the output rotation and its corresponding word slot is filled by the next COQ in sequence. For example, as shown in FIG. 2, the merger stage output at quadword (Qword  1 ) entry  151  indicates the absence of compressed data for the output queue COQ  130   c  corresponding to engine c, resulting in the insertion of the next successive quadword D 1  from the next output queue COQ D  130   d . When all the queues have exhausted their compressed data words, a 4-byte cyclic redundancy code (CRC)  155  will then be embedded into the least significant word position of the last quadword, i.e., bits 96 to 127. If there is not enough room in the last quadword, then a new quadword will be appended for storing the CRC. This CRC is generated from the original uncompressed 1 Kbyte input data and is to be used by the decompressor to verify the integrity of the compressed data. 
     Referring back to FIG. 1, there is illustrated a decompressor mechanism  180  including an input “loader” stage  185  having functionality for retrieving the compressed data from the main memory and distributing the data to a corresponding decompressor input queue (DIQ)  190   a, b, . . . , d  associated with a respective parallel decompressor engines A′, B′, C′, and D′. The DIQs  190   a, b, . . . , d  are used as FIFOs for the incoming compressed data words before the latter are processed by the respective engines A′, B′, C′, and D′. The number of decompressor input queues  190   a,b, . . . , d  and corresponding engines A′, B′, C′, and D′ are the same as those in the compressor, e.g., four engines in the example depicted. In each engine, compressed data words are first stored in its own DIQ. Given that the compressed data is stored in the main memory using the format disclosed in this invention, it becomes a relatively simple task for the loader  185  to quickly distribute the data to the DIQs for decompression. This, in turns, lowers the decompression latency significantly. 
     Specifically, at the beginning of decompression, the loader  185  always reads in the first quadword from the main memory. This quadword contains the individual word count ‘W A , W B , W C , W D ’ for each engine. The loader uses the word counts to determine how many more quadwords to retrieve and how to distribute the compressed data words. Initially, it always distributes the compressed data words to the engines in sequence, i.e., A 0 , B 0 , C 0 , D 0 , etc. When the word count for a particular engine has been exhausted, the loader will skip this engine from then on. For example, in FIG. 2, Engine C&#39;s word count W C  is 0. Thus, it drops out of the rotation after the first quadword. Eventually, only Engine A has compressed data words in quadwords Qword  3  and Qword  4 . 
     As the compressed data has been stored in an optimum format according to the invention, the decompressor&#39;s engines A′, B′, C′, and D′ are able to start decompressing the data immediately and simultaneously. This contributes to the low latency as desired for decompression. 
     While the invention has been particularly shown and described with respect to illustrative and preformed embodiments thereof, it will be understood by those skilled in the art that the foregoing and other changes in form and details may be made therein without departing from the spirit and scope of the invention which should be limited only by the scope of the appended claims.