METHOD AND APPARATUS FOR DATA DECOMPRESSION IN THE PRESENCE OF MEMORY HIERARCHIES

• US 20100013678A1
• Filed: 07/17/2008
• Published: 01/21/2010
• Est. Priority Date: 07/17/2008
• Status: Active Grant

• Current Assignee: MediaTek, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Biran, Giora, Franke, Hubertus, Yu, Hao, Golander, Amit
• Granted Patent: US 7,692,561 B2
• Time in Patent Office: Days
• US Class Current: 341/55
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77

Abstract

A method for decompressing a stream of a compressed data packet includes determining whether first data of a data-dictionary for a first decompression copy operation is located in a history buffer on a remote memory or a local memory, and when it is determined that the first data is located in the remote memory, stalling the first decompression copy operation, performing a second decompression operation using second data that is located in the history buffer on the local memory and fetching the first data from the remote memory to the history buffer on the local memory. The method further includes performing the first decompression operation using the first data in the history buffer on the local memory.

Claims

1. A method for decompressing a stream of a compressed data packet, the method comprising:

determining whether first data of a data-dictionary for a first decompression copy operation is located in a history buffer on a remote memory or a local memory;

when it is determined that the first data is located in the remote memory,

stalling the first decompression copy operation;

performing a second decompression operation using second data that is located in the history buffer on the local memory and fetching the first data from the remote memory to the history buffer on the local memory; and

performing the first decompression operation using the first data in the history buffer on the local memory.

2. The method of claim 1, wherein the decompressing is performed using Lempel-Ziv decompression.

3. The method of claim 1, wherein the stalling comprises reserving a space in the history buffer on the local memory that is sufficient in size to fit the first data.

4. The method of claim 3, wherein fetching the first data comprises copying the first data from the remote memory to the reserved space in the history buffer on the local memory.

5. The method of claim 3, wherein performing the second decompression operation comprises outputting the second data into the history buffer on the local memory after the reserved space.

6. The method of claim 1, further comprises initially prefetching a portion of the data-dictionary into the history buffer on the local memory.

7. The method of claim 1, further comprises storing data of the data-dictionary used in a recent decompression into in a caching region of the history buffer on the local memory.

8. The method of claim 7, wherein determining whether the first data is located in the history buffer comprises:

checking whether the first data is present in a region of the history buffer containing newly generated history;

checking whether the first data is present in a region of the history buffer containing prefetched recent history; and

checking whether first data is present in the caching region.

9. A system comprising a hardware decompression engine, the engine comprising:

a history buffer configured to store data of a data-dictionary associated with a compressed data packet; and

a decompression unit configured to asynchronously fetch data of the data-dictionary from a remote memory to the history buffer on the engine, to delay performing of a current decompression operation until its corresponding data has been fetched into the history buffer, and to perform a subsequent decompression operation based on the data in the history buffer while the first decompression operation is delayed.

10. The system of claim 9, wherein the history buffer comprises a committed region and an outstanding region, wherein the committed region includes contiguous data of the data-dictionary used in prior decompression operations and the outstanding region includes at least one space reserved for data of the data-dictionary corresponding to the delayed decompression operations.

11. The system of claim 10, wherein the history buffer further comprises a caching region for storing data of the data-dictionary that was previously copied from the remote memory when performing decompression operations.

12. The system of claim 11, wherein the caching region is associated with a bit vector indicating whether a unit of the data in the caching region contains valid data.

13. The system of claim 10, further comprising a commit pointer for referencing the committed region, wherein the commit pointer is advanced after the completion of each delayed decompression operation.

14. The system of claim 13, wherein the commit pointer is advanced after each copy into the history buffer when there is no delayed decompression operation.

15. The system of claim 9, further comprises an output unit that is configured to asynchronously store a part of the data in the history buffer to the remote memory.

16. The system of claim 9, wherein the decompression unit performs the decompression using Lempel-Ziv decompression.

17. The system of claim 16, further comprises a Huffman decoding unit to decode the compressed data packet into fixed length tokens, where the Huffman decoding unit operates asynchronously with the Lempel-Ziv decompression performed by the decompression unit in a pipelined fashion.

18. The system of claim 9, wherein the decompression unit comprises:

a load engine configured to retrieve data of slow copy operations and store the retrieved data on the engine, wherein the data of the slow copy operations corresponds to data of the data-dictionary of the remote memory;

a copy engine configured to copy literals of literal operations and data of fast copy operations to the history buffer, wherein the data of the fast copy operations corresponds to the data in the history buffer;

a selector configured to route the fast copy operations and literal operations to the copy engine and route the slow copy operations to the load engine.

19. The system of claim 18, wherein the load engine comprises:

an outstanding buffer;

a ready queue;

a stall queue configured to store the slow copy operations;

a load unit configured to retrieve a slow copy operation from the stall queue, load the data of the slow copy operation from the remote memory into the outstanding buffer, modify the slow copy operation to generate a new fast copy operation, and place the new fast copy operation into the ready queue.

20. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for decompressing a stream of compressed data packets, the method steps comprising:

determining whether first data of a data-dictionary for a first decompression copy operation is located in a history buffer on a remote memory or a local memory;

when it is determined that the first data is located in the remote memory,

stalling the first decompression copy operation;

performing a second decompression operation using second data that is located in the history buffer on the local memory and fetching the first data from the remote memory to the history buffer on the local memory; and

performing the first decompression operation using the first data in the history buffer on the local memory.