Parallel decompression and compression system and method for improving storage density and access speed for non-volatile memory and embedded memory devices

• US 6,145,069 A
• Filed: 04/26/1999
• Issued: 11/07/2000
• Est. Priority Date: 01/29/1999
• Status: Expired due to Term

• Current Assignee: Intellectual Ventures I LLC (Intellectual Ventures LLC)
• Original Assignee: Interactive Silicon, Inc.
• Inventors: Dye, Thomas A.
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): KIM, HONG CHONG
• Application Number:
  US09/299,966
• Time in Patent Office: 561 Days
• Field of Search: 711/103, 711/170, 710/68, 714/763, 714/764, 709/247, 382/232, 382/233, 345/521, 345/501, 345/507, 345/509
• US Class Current: 711/170
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

A flash memory controller and/or embedded memory controller including MemoryF/X Technology that uses data compression and decompression for improved system cost and performance. The Compression Enhanced Flash Memory Controller (CEFMC) of the present invention preferably uses parallel lossless compression and decompression engines embedded into the flash memory controller unit for improved memory density and data bandwidth. In addition, the invention includes a Compression Enhanced Memory Controller (CEMC) where the parallel compression and decompression engines are introduced into the memory controller of the microprocessor unit. The Compression Enhanced Memory Controller (CEMC) invention improves system wide memory density and data bandwidth. The disclosure also indicates preferred methods for specific applications such as usage of the invention for solid-state disks, embedded memory and Systems on Chip (SOC) environments. The disclosure also indicates a novel memory control method for the execute in place (XIP) architectural model. The integrated parallel data compression and decompression capabilities of the CEFMC and CEMC inventions remove system bottle-necks and increase performance matching the data access speeds of the memory subsystem to that of the microprocessor. Thus, the invention allows lower cost systems due to smaller data storage, reduced bandwidth requirements, reduced power and noise.

Claims

1. A method for managing solid state memory in a system including a solid state memory and a solid state memory controller coupled to the solid state memory, wherein the solid state memory controller includes a decompression engine, the method comprising:

storing compressed data on the solid state memory;

a device initiating a read of requested data from the solid state memory, wherein the requested data comprises compressed requested data stored on the solid state memory in a compressed format;

the solid state memory controller reading the compressed requested data from the solid state memory;

the solid state memory controller decompressing the compressed requested data to produce uncompressed requested data using parallel decompression, wherein said decompressing comprises;

examining a plurality of codes from the compressed requested data in parallel in a current decompression cycle, wherein each of the plurality of codes describes one or more symbols in the uncompressed requested data;

generating a plurality of selects in parallel in response to said examining the plurality of codes in parallel, wherein each of the plurality of selects points to a symbol in a combined history window; and

generating the uncompressed requested data comprising the plurality of symbols using the plurality of selects; and

the solid state memory controller providing the uncompressed requested data to the device.

2. The method of claim 1, further comprising:

storing the uncompressed plurality of symbols from the current decompression cycle in the combined history window.

3. The method of claim 2,

wherein, in the current decompression cycle prior to said storing the uncompressed plurality of symbols, the combined history window includes an uncompressed plurality of symbols from any previous decompression cycles and zero or more data bytes from the current decompression cycle.

4. The method of claim 1, wherein said examining the plurality or codes includes generating, for each code, size and count information and at least one of a data byte or index information;

and

wherein said generating the plurality of selects in parallel uses the size and count information and at least one of the data byte or index information for each of the plurality of codes.

5. The method of claim 4,

wherein a size for a code defines the number of bits comprising the code;

wherein a count for a code defines the number of symbols in the uncompressed data described by the code.

6. The method of claim 1,

wherein the combined history window includes one or more data bytes from the current decompression cycle;

and

wherein one or more of the plurality of selects in the current decompression cycle point to one or more of the data bytes in the combined history window.

7. The method of claim 6, wherein said generating the plurality of selects in parallel uses index information generated for one or more of the plurality of codes to generate the one or more selects pointing to the one or more of the data bytes in the combined history window.

8. The method of claim 1,

wherein the combined history window includes one or more uncompressed symbols from one or more previous decompression cycles;

and

wherein one or more of the plurality of selects in the current decompression cycle point to one or more of the uncompressed symbols in the combined history window from the one or more previous decompression cycles.

9. The method of claim 8, wherein said generating the plurality of selects in parallel uses index information generated for one or more of the plurality of codes to generate the one or more selects pointing to the one or more of the uncompressed symbols in the combined history window.

10. The method of claim 1, wherein the combined history window includes an uncompressed plurality of symbols from one or more previous decompression cycles and data bytes from the current decompression cycle, wherein said generating the plurality of selects in parallel comprises:

generating a first select to point to a data byte in the combined history window in response to a first code indicating that uncompressed data represented by the first code is the data byte; and

generating a second select to point to a first symbol in the combined history window in response to a second code indicating that uncompressed data represented by the second code includes the first symbol in the combined history window.

11. The method of claim 10, wherein the uncompressed data represented by the second code includes one or more symbols following the first symbol in the combined history window, wherein selects are generated to point to each of the one or more symbols in the combined history window comprising the uncompressed data represented by the second code.

12. The method of claim 1, wherein the combined history window includes an uncompressed plurality of symbols from one or more previous decompression cycles and data bytes from the current decompression cycle, wherein said generating the plurality of selects in parallel comprises:

generating a first select to point to a first symbol being decompressed from a first code in the current decompression cycle, wherein the first select is generated in response to a second code indicating that uncompressed data represented by the second code includes the first symbol, and wherein the first symbol is not in the combined history window.

13. The method of claim 12, further comprising resolving the first select to point to one of a symbol in the current combined history window or a data byte in the current combined history window.

14. The method of claim 13, further comprising copying a second select being generated for the first code to the first select, wherein the second select points to one of a symbol in the combined history window or a data byte in the combined history window.

15. The method of claim 1, wherein the combined history window includes an uncompressed plurality of symbols from one or more previous decompression cycles, wherein storing the uncompressed plurality of symbols from the current decompression cycle in the combined history window includes removing from the combined history window at least a portion of the uncompressed plurality of symbols from the one or more previous decompression cycles.

16. The method of claim 1, wherein said examining the plurality of codes in parallel comprises:

extracting a portion of the compressed data as an input data, wherein the input data includes the plurality of codes;

extracting one or more codes from the input data; and

generating, for each code, size and count information and at least one of a data byte or index information.

17. The method or claim 16, wherein a plurality of decoders are operable to examine the plurality of codes in parallel in the current decompression cycle, wherein said extracting the one or more codes comprises:

a) determining a next decoder in the plurality of decoders;

b) extracting a code from the input data to be a current code in response to determining the next decoder;

c) determining the number of uncompressed symbols to be generated by the current code; and

d) assigning the current code to the net decoder.

18. The method of claim 16, wherein said extracting the one or more codes further comprises determining a size of each of the one or more codes.

19. The method of claim 16, wherein said extracting the one or more codes further comprises:

determining if a code in the input data is a complete code or an incomplete code, wherein the code is extracted from the input data to be the current code in response to determining the code is a complete code.

20. The method of claim 1, wherein said receiving the compressed data, said examining a plurality of codes, said generating a plurality of selects, and said generating the uncompressed data comprising the plurality of symbols are performed substantially concurrently in a pipelined fashion.

21. The method of claim 1, further comprising:

the solid state memory controller reading a header for the compressed requested data from the solid state memory prior to said decompressing the compressed requested data;

wherein the header includes information used in said decompressing the compressed requested data.

22. The method of claim 1, wherein the solid state memory controller further includes a compression engine, the method further comprising:

a device initiating a write of uncompressed data to the solid state memory, wherein the uncompressed data is in an uncompressed format;

the solid state memory controller receiving the uncompressed data from the device;

the solid state memory controller compressing the uncompressed data to produce compressed data, wherein the uncompressed data comprises a plurality of symbols, wherein said compressing comprises;

a) comparing a plurality of symbols from the uncompressed data with each entry in a history table in a parallel fashion, wherein said comparing produces compare results;

wherein the history table comprises entries, wherein each entry comprises at least one symbol, and wherein the method maintains a current count of prior matches which occurred when previous symbols were compared with entries in the history table;

b) determining match information for each of said plurality of symbols based on the current count and the compare results; and

c) outputting compressed data in response to the match information; and

the solid state memory controller storing the compressed data on the solid state memory.

23. The method of claim 22, wherein said outputting compressed data includes:

outputting a count value and an entry pointer for a contiguous match, wherein the entry pointer points to the entry in the history table which produced the contiguous match, wherein the count value indicates a number of matching symbols in the contiguous match.

24. The method of claim 23, wherein said outputting the count value includes encoding a value representing the count value;

wherein more often occurring counts are encoded with fewer bits than less often occurring counts.

25. The method of claim 22, wherein said outputting compressed data further includes:

for non-matching symbols which do not match any entry in the history table, outputting the non-matching symbols.

26. The method of claim 22, further comprising:

d) repeating steps a)-c) one or more times until no more data is available; and

e) when no more data is available, if the current count is non-zero, outputting compressed data for the remaining match in the history table.

27. The method of claim 26, wherein said determining match information includes determining zero or more matches of said plurality of symbols with each entry in the history table.

28. The method of claim 22, wherein the method further maintains a count flag for each entry in the history table;

wherein said determining determines match information for each of said plurality of symbols based on the current count, the count flags, and the compare results.

29. The method of claim 28, wherein said determining match information includes:

resetting the count and count flags if the compare results indicate a contiguous match did not match one of the plurality of symbols.

30. The method of claim 28, wherein the count and count flags for all entries are reset based on the number of the plurality of symbols that did not match in the contiguous match.

31. The method of claim 22, wherein said determining match information includes:

updating the current count according to the compare results.

32. The method of claim 22, wherein said determining match information includes:

determining a contiguous match based on the current count and the compare results;

determining if the contiguous match has stopped matching;

if the contiguous match has stopped matching, then;

updating the current count according to the compare results; and

wherein said outputting compressed data includes outputting compressed data corresponding to the contiguous match.

33. The method of claim 32, wherein said outputting compressed data corresponding to the contiguous match comprises outputting a count value and an entry pointer, wherein the entry pointer points to the entry in the history table which produced the contiguous match, wherein the count value indicates a number of matching symbols in the contiguous match.

34. The method of claim 22, wherein the plurality of symbols includes a first symbol, a last symbol, and one or more middle symbols;

wherein said determining match information includes;

if at least one contiguous match occurs with one or more respective contiguous middle symbols, and the one or more respective contiguous middle symbols are not involved in a match with either the symbol before or after the respective contiguous middle symbols, then;

selecting the one or more largest non-overlapping contiguous matches involving the middle symbols;

wherein said outputting compressed data includes outputting compressed data for each of the selected matches involving the middle symbols.

35. The method of claim 22,

wherein the method further maintains a count flag for each entry in the history table;

wherein said determining determines match information for each of said plurality of symbols based on the current count, the count flags, and the compare results;

wherein said determining match information and said outputting compressed data in response to the match information comprises;

determining zero or more matches of said plurality of symbols with each entry in the history table;

examining the compare results for each entry;

for non-matching symbols which do not match any entry in the history table, outputting the non-matching symbols;

if any entry stopped matching, examining the current count, the count flags, and the compare results for every entry;

determining the contiguous match based on the current count and the compare results;

determining if the contiguous match has stopped matching;

if the contiguous match has stopped matching, then;

outputting a count value and an entry pointer, wherein the entry pointer points to the entry in the history table which produced the contiguous match, wherein the count value indicates a number of matching symbols in the contiguous match; and

updating the current count according to the compare results;

the method further comprising;

e) repeating steps a)-c) one or more times until no more data is available; and

f) when no more data is available, if the current count is non-zero, outputting a count value and an entry pointer for the remaining match in the history table.

36. The method of claim 35, wherein the plurality of symbols includes a first symbol, a last symbol, and one or more middle symbols;

wherein, if the contiguous match has stopped matching, then the method further comprises;

if at least one contiguous match occurs with one or more respective contiguous middle symbols, and the one or more respective contiguous middle symbols are not involved in a match with either the symbol before or after the respective contiguous middle symbols, then;

selecting the largest non-overlapping contiguous matches involving the middle symbols;

outputting a count value and an entry pointer for each of the selected matches involving the middle symbols.

37. The method of claim 22, wherein the plurality of symbols comprise a power of 2 number of symbols.

38. The method of claim 22, wherein the plurality of symbols comprise four symbols.

39. The method of claim 22, further comprising:

generating a header for the compressed data; and

storing the header on the solid state memory;

wherein the header includes information for decompressing the compressed data.