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 for a computer memory system implementing data compression, a highly-efficient compression output mechanism 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 methodology for efficiently merging compressed data in a manner such that a compressor mechanism is enabled to write out parallel streams of compressed data from multiple compression engines quickly and with minimal loss of compression ratio. 
     Thus, according to the principles of the invention, there is provided a data compression system comprising: one or more compression engines executing in parallel for receiving uncompressed information words and compressing said information words into one or more compressed information words; a temporary storage queue associated with each compression engine for temporarily storing one or more compressed information words from its respective compression engine; a pre-fetch mechanism for pre-fetching an amount of compressed information words in parallel from each said temporary storage queue; a first processing device for receiving said pre-fetched compressed information words and successively forming a merged word in queue sequence order for output each processing cycle; and, a second processing device for receiving said pre-fetched compressed information words and generating a number of consecutive next available compressed words in queue sequence order when one or more temporary storage queues have exhausted its storage of compressed information words at any time during a processing cycle and, at such time, utilizing said number of consecutive next available compressed words to form said merged word output, whereby output of a complete merged word in each successive cycle is ensured. 
     Advantageously, the compressed data format enables a compressor to write out parallel streams of compressed data from multiple engines quickly and facilitates a decompression engine to extract the individual streams of compressed data easily without separate data delimiters and control. Thus, not only are the advantages of parallel processing with the compression and decompression engines exploited, but also the advantages of enhanced compression throughput and reduced decompression latency. 
    
    
     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. the compressed data format implemented in the present invention. 
     FIG. 3 illustrates a block diagram of the compression output mechanism, namely the merger device. 
     FIG. 4 is a flowchart depicting the methodology employed by the engine drop-out block of the compression output merger mechanism illustrated in FIG.  3 . 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The present invention is related to a system and methodology for organizing and storing compressed data efficiently according to the data format described in commonly-owned, co-pending U.S. patent application Ser. No. 09/569,557 entitled HIGHLY EFFICIENT COMPRESSION DATA FORMAT the contents and disclosure of which is incorporated by reference. 
     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 0x07 and for COQ C  130   c  the word count field W C  is 0x00. 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, the last quadword will be filled with zeros (0) as shown in quadword (Qword  4 ) entries  153   a  and  153   b . Furthermore, 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. 
     FIG. 3 is a detailed illustration of the merger stage  135 . As shown, the merger stage  135  comprises two logic blocks, namely the quad-engine block  140  and the engine drop-out block  145 . From the start of the merger output process, these two blocks  140 ,  145  work together cycle-by-cycle to generate the compressed data output according to the aforementioned compressed data format. Each block  140 , 145  comprises internal multiplexers and registers that work together to generate the compressed data output according to the aforementioned compressed data format. These internal multiplexers and registers are controlled by a select control logic block  139  which receives as input each remaining word counts, W A , W B , W C , and W D  from the respective four engines, and generates a set of select lines  137  for controlling internal multiplexers and registers. These select lines  137  determines which input compressed words will be outputted and what order they should have. The select control logic block  139  additionally detects if an engine has dropped-out. 
     More particularly, the select control logic block  139  first loads the four engines&#39; remaining word counts, W A , W B , W C , and W D  into its internal registers. Then it uses them to generate a set of select lines  137  in subsequent cycles. These select lines determine which input compressed words will be outputted from the quad-engine block  140  and the engine drop-out block  145 . As will be explained in greater detail, during each cycle in the output process each remaining word count will be decremented for each corresponding word outputted. In this manner, both blocks may track compressed data content to check for any engine drop-out. 
     In order to sustain a throughput of four compressed data words (16 bytes) per output cycle, the merger device  135  must pre-fetch four consecutive compressed data words from each respective COQ A-COQ D into its 16-word-wide merger input register  136  each cycle and then forward them to the two logic blocks  140 ,  145 . Specifically, the sixteen compressed words are A n A n+1 A n+2 A n+3 B n B n+1 B n+2 B n+3 C n C n+1 C n+2 C n+3 D n D n+1 D n+2 D n+3  where n is a whole number integer greater than or equal to 0. This is necessary because if one or more engines have exhausted their data, then the merger must use additional words from the remaining engines during the same cycle. For example, if engine C drops out, then two words are needed from engine A to form the output data, i.e., A n B n D n A n+1 . If only engine B has remaining data in its COQ, then four words are needed from engine B to form the output data, i.e., B n B n+1 B n+2 B n+3 . 
     More specifically, the quad-engine block  140  is the main logic block in the merger. It comprises four 4-word-wide pipeline registers labeled qw 0 , qw 1 , qw 2 , and qw 3 . Each register may select from three types of inputs: 1) direct  141 ; 2) pipeline  142 ; or 3) drop-out  143 , with only register q 3  not receiving a pipeline input. Firstly, direct inputs  141  receive compressed words directly from the merger input register  136  with one word from each engine being clocked into each register. For example, the four words A 0 , B 0 , C 0 , and D 0  from the merger input register  136  are clocked into register qw 0  and in the same cycle, the four words, A 1 , B 1 , C 1 , and D 1  are clocked into register qw 1 , and so on for the remaining registers. Secondly, the pipeline input  142  receives the four word inputs from the previous pipe stage. For example, the four word outputs  142  of registers qw 1 , qw 2 , and qw 3  sources to the pipeline input of registers qw 0 , qw 1 , and qw 2 , respectively. Furthermore, the last pipeline input of register qw 3  may be tied to zeros (0) as shown at input  146 . As shown in FIG. 3, only the output  144  of register qw 0  is input to the compressor output register  151  which becomes the output of the merger in each cycle. Thirdly, when an engine A, B, C, D has exhausted its data in its respective COQ, its remaining word count W A , W B , W C , and W D  will become zero. That engine drops out and remains on the sideline for the rest of the output phase with no further data contribution. All subsequent merger output will come from the engine drop-out block  145  via the drop-out inputs  143  of the pipeline registers. 
     The main function of the engine drop-out block  145  is to offload some of the output selection cases from the quad-engine block so that the latter can achieve an optimal throughput. Specifically, the engine drop-out block must handle cases when one or more engines have dropped out at any time during the output process. Given that an engine may contribute from zero to four words during each read of the COQs, the engine drop-out block must generate consecutive compressed words according to the aforementioned compressed data format. Specifically, it utilizes three sets of filters  147   a ,  147   b ,  147   c  in series along with the select lines  137  from the select control logic block  139 . As shown in FIG. 3, the 4-to-3 filter  147   a  handles the case when only one engine has dropped out. Specifically, it receives four compressed words from all four engines (16 words) and produces a twelve-word output after determining which engine has dropped out. For example, if engine C has dropped out, then the data output of filter  147   a  will be A 0 B 0 D 0 A 1 B 1 D 1 A 2 B 2 D 2 A 3 B 3 D 3  (12 words). Similarly, if two engines have dropped out, then the 3-to-2 filter  147   b  receives the four compressed words from the three remaining engines output from the 4-to-3 filter  147   a , and produces an eight-word output after determining which second engine has dropped out. For example, if, besides engine C, engine A has also dropped out, then the filter data output will be B 0 D 0 B 1 D 1 B 2 D 2 B 3 D 3 . Thirdly, if three engines have dropped out, then the 2-to-1 filter  147   c  will also be employed along with the previous two filters for taking the four compressed words from the two remaining engines output from the 3-to-2 filter  147   b  and produces a four-word output after determining which third engine has dropped out. For example, if, besides engines A and C, engine D has also dropped out, then the filter data output will be B 0 B 1 B 2 B 3 . 
     Given all the possible cases of dropped-out engines, the select control logic block  139  then selects from the three filters&#39; outputs using the engine drop-out select multiplexor  148  (FIG. 3) to generate output  149  comprising the twelve (12) consecutive compressed data words, DO 0  to DO 11  at the end of the cycle. 
     FIG. 4 is a flowchart  200  depicting the methodology employed by the engine drop-out block for generating the 12 word output. It is understood that, from the start of the merger output process, drop-out block  145  functions with the quad-engine block  140  synchronously. Given that the remaining word counts W A , W B , W C , W D  for each engine have been pre-loaded by the select control logic block  139  as indicated at step  202 , the engine drop-out block proceeds in accordance with the logic depicted in FIG.  4 . Generally, the logic depicted in FIG. 4 requires that, during each cycle, the engine drop-out block check each word count in alphabetical order. If a word count is non-zero, then it will be decremented and its corresponding compressed data word will be selected as the next most significant word of DO. Otherwise, that engine has dropped out and the engine drop-out block moves on to the next word count. After all four word counts have been checked four times, the engine drop-out block has completed one pass. 
     FIG. 4 is now described in more detail as follows: The individual word counts W A , W B , W C , W D  for each engine are first loaded at step  202 , and the 16 words, e.g., A 0-3 B 0-3 C 0-3 D 0-3  (four from each queue) are read at step  204 . Additionally, index variables i,k are initialized. Then the engine checks each word count in alphabetical order. For example, at step  208 , a determination is made as to whether the engine A has dropped out, i.e., word count W A =0. If the engine has not dropped out, the respective word loaded word A i  for engine A is written to the output DO i    149 , the variable k is incremented, and the respective word count W A  is decremented as indicated at step  210 . Otherwise, if, at step  208 , it was determined that the engine A has dropped out, i.e., word count W A =0, then the process proceeds to determine the status of the word counts for the remaining engines. That is, the process of checking the word count (steps  212 ,  214  and  218 ) and processing the next loaded word if the corresponding engine has not dropped out (steps  213 ,  216  and  219 ) is repeated for each of the remaining engines B, C, D. For each remaining respective engine B, C, D that has not dropped out as indicated by an individual word count W B , W C , W D  being not equal to zero (0) (steps  212 ,  214 ,  218 ), the engine drop-out block will decrement the respective word count and that engine&#39;s corresponding compressed data word will be selected as the next most significant word of DO i  and written to the output  149  in the cycle, as indicated at steps  213 ,  216  and  219 , respectively. Otherwise, that engine has dropped out and the engine drop-out block moves on to the next word count. After all four word counts have been checked the index i is incremented at step  220  and the process steps  208 - 220  are repeated for four times, as indicated by the determination of i=4 at step  225 . 
     During this process, if no engine has dropped out, then the engine drop-out block&#39;s output  149  will be ignored by the quad-engine block  140  which utilizes its direct and pipeline inputs instead for outputting each four compressed words each cycle. If one engine has dropped out, then the twelve (12) words of DO will be used by the quad-engine block  140 . For example, if engine C has dropped out, then the filter data output will be A 0 B 0 D 0 A 1 B 1 D 1 A 2 B 2 D 2 A 3 B 3 D 3 . If there are two or more engines dropped out, such that there are fewer than twelve 12 valid compressed data words from the filters, then the output will be back-filled with zero&#39;s as indicated at step  230 . For example, if, besides engine C, engine A has also dropped out, then the filter data output will be B 0 D 0 B 1 D 1 B 2 D 2 B 3 D 3  followed by four words of zero. These data are then sent to the different pipeline registers in the quad-engine block  140  for output. That is, DO 0-3  will be used by qw 0 , DO 4-7  will be used by qw 1 , etc. 
     All of the above filtering and data selection takes place in parallel within one single cycle. At the end of each cycle, if the sum of the four word count is still non-zero, then the engine drop-out block  145  repeats the previous steps and produces a new 12-word output in the following cycle. When there is only one remaining engine, then each 12-word output consists of only four valid words from that engine followed by eight words of zero. The ability of the engine drop-out block to output 12 words per cycle is important because it sustains the throughput requirement of the merger, which is four compressed data words per cycle. As shown in FIG. 4, at step  235 , when the sum of the four word count is zero, the control signal CRC select  154  will become active and cause the mux  148  to select the CRC  156  for output. 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. 
     In summary, at the start of compression output process, the merger stage  135  first reads quadwords from all four engines&#39; COQs into the merger input register  142 . It then loads them into the four pipeline registers accordingly. A 0 , B 0 , C 0 , and D 0  will be clocked into register qw 0  while A 1 , B 1 , C 1 , and D 1  will be loaded directly into register qw 1 , and so forth. During the next four cycles, each pipeline register will send its 4-word data to the next stage and eventually output them from the register qw 0 . In the fourth cycle a new set of compressed data words are also read from the COQs in order to replenish the pipeline. Furthermore, whenever there is an engine drop out, the engine drop-out block will use its filters to produce twelve (12) consecutive compressed data words. The merger then writes these words into the compressor output register instead. Thus, through pre-fetch and pipelining, the merger is able to efficiently organize, store or transmit compressed data words. 
     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.