METHOD AND APPARATUS FOR ENERGY EFFICIENT DECOMPRESSION USING ORDERED TOKENS

• US 20180341722A1
• Filed: 05/25/2017
• Published: 11/29/2018
• Est. Priority Date: 05/25/2017
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Satpathy, Sudhir K., Suresh, Vikram B., Mathew, Sanu K., Gopal, Vinodh
• Granted Patent: US 11,126,663 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 16/9017 using directory or table look-up use of a directory or look-up table in file systems G06F16/13
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: H03M 7/425 for the decoding process only
• CPC Class Codes: H03M 7/6005 Decoder aspects
• CPC Class Codes: H03M 7/6047 Power optimization with respect to the encoder, decoder, storage or transmission
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

In one embodiment, an apparatus comprises a decompression engine to determine a plurality of tokens used to encode a block of data; populate a lookup table with at least two of the tokens in order of increasing token length; disable a first portion of the lookup table and enable a second portion of the lookup table based on a value of a payload of the block of data; and search for a match between a token and the payload in the second portion of the lookup table.

Claims

1. An apparatus comprising:

a decompression engine to;

determine a plurality of tokens used to encode a block of data;

populate a lookup table with at least two of the tokens in order of increasing token length;

disable a first portion of the lookup table and enable a second portion of the lookup table based on a value of a payload of the block of data; and

search for a match between a token and the payload in the second portion of the lookup table.

2. The apparatus of claim 1, wherein the lookup table comprises a content addressable memory (CAM), the first portion of the lookup table comprises a first bank of the CAM, and the second portion comprises a second bank of the CAM.

3. The apparatus of claim 1, the decompression engine to compare the payload against a last token of the second portion of the lookup table to determine whether to enable the second portion of the lookup table.

4. The apparatus of claim 1, wherein the tokens are ordered by increasing numeric value in the lookup table.

5. The apparatus of claim 1, the decompression engine to populate a first table comprising entries for each token length specified by a header associated with the block of data, wherein a first entry of the first table corresponds to a first token length and comprises an address of the lookup table at which a token of the first token length is to be stored.

6. The apparatus of claim 5, the decompression engine to:

identify a token length in the header;

based on a determination that the identified token length is the first token length, write a token of the first token length to the lookup table at an address specified by the first entry; and

update the first entry to store an address of the lookup table at which a next token of the first token length is to be placed.

7. The apparatus of claim 1, the decompression engine to:

determine a lowest valued token of a particular token length; and

activate a segment of the second portion of the lookup table for use in the search for the match, the activation based on a comparison between the lowest valued token and the payload.

8. The apparatus of claim 7, wherein the segment of the second portion of the lookup table is to determine whether a set of least significant bits of the payload match a corresponding set of least significant bits of tokens of the second portion of the lookup table.

9. The apparatus of claim 7, wherein the decompression engine is to deactivate the segment of the second portion of the lookup table for use in a search for a match with a second payload in response to determination that the second payload has a numeric value that is less than a numeric value of the lowest valued token of the particular token length.

10. The apparatus of claim 1, further comprising a battery communicatively coupled to a processor, a display communicatively coupled to the processor, or a network interface communicatively coupled to the processor.

11. A method comprising:

determining a plurality of tokens used to encode a block of data;

populating a lookup table with at least two of the tokens in order of increasing token length;

disabling a first portion of the lookup table and enable a second portion of the lookup table based on a value of a payload of the block of data; and

searching for a match between a token and the payload in the second portion of the lookup table.

12. The method of claim 11, further comprising comparing the payload against a last token of the second portion of the lookup table to determine whether to enable the second portion of the lookup table.

13. The method of claim 11, wherein the tokens are ordered by increasing numeric value in the lookup table.

14. The method of claim 11, further comprising populating a first table comprising entries for each token length specified by a header associated with the block of data, wherein a first entry of the first table corresponds to a first token length and comprises an address of the lookup table at which a token of the first token length is to be stored.

15. The method of claim 11, further comprising:

determining a lowest valued token of a particular token length; and

activating a segment of the second portion of the lookup table for use in the search for the match, the activation based on a comparison between the lowest valued token and the payload.

16. At least one machine readable storage medium having instructions stored thereon, the instructions when executed by a machine to cause the machine to:

determine a plurality of tokens used to encode a block of data;

populate a lookup table with at least two of the tokens in order of increasing token length;

disable a first portion of the lookup table and enable a second portion of the lookup table based on a value of a payload of the block of data; and

search for a match between a token and the payload in the second portion of the lookup table.

17. The at least one medium of claim 16, the instructions when executed to cause the machine to compare the payload against a last token of the second portion of the lookup table to determine whether to enable the second portion of the lookup table.

18. The at least one medium of claim 16, wherein the tokens are ordered by increasing numeric value in the lookup table.

19. The at least one medium of claim 16, the instructions when executed to cause the machine to populate a first table comprising entries for each token length specified by a header associated with the block of data, wherein a first entry of the first table corresponds to a first token length and comprises an address of the lookup table at which a token of the first token length is to be stored.

20. The at least one medium of claim 16, the instructions when executed to cause the machine to:

determine a lowest valued token of a particular token length; and

activate a segment of the second portion of the lookup table for use in the search for the match, the activation based on a comparison between the lowest valued token and the payload.