Pipelined decompression of sliding window compressed data

Patent metadata

Field	Value
Publication number	US-10489159-B2
Application number	US-201715609759-A
Country	US
Kind code	B2
Filing date	May 31, 2017
Priority date	Dec 21, 2016
Publication date	Nov 26, 2019
Grant date	Nov 26, 2019

Abstract

Decompressing sliding window compressed data requires reference to previously decompressed character sequences. Previously decompressed data is stored in a history buffer to satisfy these ‘back references.’ As each decompressed/decoded character is emitted, it is stored in this history buffer. Thus, for each decompressed character that is emitted, the history buffer may need to be accessed at least twice—once to retrieve the backreference, and once to store the emitted character. A pipeline architecture is disclosed that stores decompressed characters in a write queue that coalesces eight or more emitted characters before they are stored in the history buffer memory. This reduces collisions between accessing the history buffer memory to retrieve the backreferences and the storing of the emitted character. This also allows the use of a single-ported memory which is less expensive than a multi-ported memory.

First claim

What is claimed is:

1. An integrated circuit for decompressing a sliding window compression scheme, comprising:
a history buffer memory to hold data corresponding to a sliding window of the sliding window compression scheme, the history buffer memory including a plurality of single-ported memory banks, each of the plurality of single-ported memory banks configured so that at most one of a read or write operation is performed concurrently by a respective single-ported memory bank;
a write queue to receive write data forming a subset of data corresponding to read addresses to be written to the history buffer memory, the write queue to coalesce a plurality of write operations to reduce write operations made to the plurality of single-ported memory banks, the write queue to respond to read operations with corresponding data that is waiting in the write queue to be written to the history buffer memory, the history buffer memory not to be read for the corresponding data in accordance with the write queue responding with the corresponding data.

2. The integrated circuit of claim 1 , further comprising:
a check write queue pipeline stage to query the write queue with read operations for corresponding data waiting in the write queue.

3. The integrated circuit of claim 2 , wherein the check write queue pipeline stage is to receive, in response to a read operation presented to the write queue, data that is waiting in the write queue to be written to the history buffer memory.

4. The integrated circuit of claim 3 , wherein the check write queue pipeline stage is to also receive write data corresponding to write operations to the history buffer memory that are performed by a later pipeline stage.

5. The integrated circuit of claim 4 , further comprising:
a history buffer read pipeline stage to receive data read from the history buffer memory.

6. The integrated circuit of claim 5 , wherein the history buffer read pipeline stage is to also receive write data corresponding to write operations to the history buffer memory that are performed by the later pipeline stage.

7. The integrated circuit of claim 6 , further comprising:
a prefix buffer to provide precomputed history data to be used as data corresponding to at least part of the sliding window of the sliding window compression scheme.

8. The integrated circuit of claim 7 , wherein the history buffer read pipeline stage is to also receive the precomputed history data.

9. A method of maintaining sliding window data for decompressing a sliding window compression scheme, comprising:
reading blocks of sliding window data from a history buffer memory holding data corresponding to a sliding window of the sliding window compression scheme, the history buffer memory including a plurality of single-ported memory banks, each of the plurality of single-ported memory banks configured so that at most one of a reading of a first block of sliding window data and a writing of a second block of sliding window data can be performed concurrently by a respective single-ported memory bank;
coalescing write data forming a subset of data corresponding to read addresses in a write data queue to be written to the history buffer memory in write data blocks;
providing, by the write data queue and in response to a read request, write data stored in the write data queue corresponding to an address of the read request;
in accordance with the write data queue not providing write data stored in the write data queue corresponding to the address of the read request, providing, by the history buffer memory, data read from the history buffer memory that corresponds to the read request.

10. The method of claim 9 , wherein a write queue check pipeline stage receives, from a previous pipeline stage, the address of the read request.

11. The method of claim 10 , wherein the write queue check pipeline stage provides the address of the read request to the write data queue.

12. The method of claim 11 , further comprising:
receiving, by the write queue check pipeline stage, the write data stored in the write data queue corresponding to the address of the read request.

13. The method of claim 12 , further comprising:
receiving, by a history buffer read pipeline stage, data read from the history buffer memory that corresponds to the read request.

14. The method of claim 13 , further comprising:
receiving, by the history buffer read pipeline stage, precomputed history data that corresponds to the read request.

15. The method of claim 11 , further comprising:
receiving, by the write queue check pipeline stage, precomputed history data that corresponds to the read request.

16. A method of decompressing data compressed according to a sliding window compression scheme, comprising:
receiving, by a first pipeline stage, a first block of compressed data, the first block of compressed data including a plurality of symbols representing at least one literal and at least one backreference;
computing, by the first pipeline stage, a respective address for each symbol of the plurality of symbols, the respective address for each symbol corresponding to a respective location in a history buffer memory where a respective atomic data unit associated with a respective symbol is to be read from in the history buffer memory, the history buffer memory storing a first sliding window of atomic data units that have been previously decoded;
querying, by a second pipeline stage, a write queue to determine whether a first atomic data unit included in a subset of data received by the write queue and corresponding to a first symbol of the plurality of symbols is being stored in the write queue;
in response to determining the first atomic data unit is being stored in the write queue, sending the first atomic data unit to the second pipeline stage;
in response to determining the first atomic data unit is not being stored in the write queue, retrieving, by a third pipeline stage, the first atomic data unit from the history buffer memory.

17. The method of claim 16 , further comprising:
determining a second atomic data unit corresponding to a second symbol of the plurality of symbols is not stored in the write queue and is not stored in the history buffer memory;
in response to determining the second atomic data unit is not being stored in the write queue and is not stored in the history buffer memory, receiving, by the second pipeline stage and from a fourth pipeline stage, the second atomic data unit;
in response to determining the second atomic data unit is not being stored in the write queue and is not stored in the history buffer memory, providing the second atomic data unit received from the fourth pipeline stage to the third pipeline stage.

18. The method of claim 16 , further comprising:
determining a second atomic data unit corresponding to a second symbol of the plurality of symbols is not stored in the write queue and is not stored in the history buffer memory;
in response to determining the second atomic data unit is not being stored in the write queue and is not stored in the history buffer memory, receiving, by the third pipeline stage and from a fourth pipeline stage, the second atomic data unit;
in response to determining the second atomic data unit is not being stored in the write queue and is not stored in the history buffer memory, providing the second atomic data unit received from the fourth pipeline stage to the fourth pipeline stage.

19. The method of claim 16 , further comprising:
determining a second atomic data unit corresp

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Vattakandy Amar
• Erickson Michael J
• Havlik Robert W
• Gladding Derek E

Classifications

• G06F12/0857

  by multiple requestors · CPC title

• G06F3/0628

  making use of a particular technique · CPC title

• G06F12/0844

  Multiple simultaneous or quasi-simultaneous cache accessing · CPC title

• G06F3/0608

  Saving storage space on storage systems · CPC title

• G06F13/1642

  with request queuing · CPC title