Adaptive speculative decoding

Patent metadata

Field	Value
Publication number	US-10911063-B2
Application number	US-201916592465-A
Country	US
Kind code	B2
Filing date	Oct 3, 2019
Priority date	Oct 3, 2019
Publication date	Feb 2, 2021
Grant date	Feb 2, 2021

Abstract

Examples herein relate to decoding tokens using speculative decoding operations to decode tokens at an offset from a token decoded by a sequential decoding operation. At a checkpoint, a determination is made as to whether tokens to be decoded by the sequential and speculative decoding operations align. If there is alignment, the speculatively decoded tokens after a discard window are committed and made available for access. If there is not alignment, the speculatively decoded tokens are discarded. A miss in alignment and a fullness level of a buffer that stores speculatively decoded tokens are assessed to determine a next offset level for a start of speculative decoding. A size of a discard window can be set using a relationship based on the offset level to improve buffer utilization and to attempt to improve changes of alignments.

First claim

What is claimed is:

1. A data decoder comprising:
a memory and
at least one processor to:
based on a decoding parameter, perform adaptive speculative decode of at least one entropy encoded token relative to a token decoded using a sequential decode and store the at least one speculatively decoded token in a buffer and
adjust a decoding parameter based on convergence between sequential decode and speculative decode or content level of the buffer.

2. The data decoder of claim 1 , wherein the at least one processor is to adjust a second decoding parameter based on the adjusted decoding parameter.

3. The data decoder of claim 2 , wherein the at least one processor is to determine an occurrence of convergence between a sequential decode and a speculative decode and to determine an occurrence of convergence between a sequential decode and a speculative decode, the at least one processor is to:
at a checkpoint, determine if a start of a token to be decoded using the sequential decode aligns with a token to be decoded using the speculative decode;
based on alignment, discard symbols according to the second decoding parameter and commit any non-discarded symbol generated from the speculative decode or
based on non-alignment, discard symbols generated from the speculative decode.

4. The data decoder of claim 1 , wherein the at least one processor is to adjust a second decoding parameter based on the adjusted decoding parameter, wherein the decoding parameter comprises a level of offset and the second decoding parameter comprises a discard window size.

5. The data decoder of claim 1 , wherein the adjust a decoding parameter is to adjust utilization of the buffer.

6. The data decoder of claim 1 , wherein the at least one processor is to perform a sequential decode to sequentially decode at least one token.

7. The data decoder of claim 1 , wherein the at least one processor is to:
perform a second speculative decode to decode one or more tokens based on the adjusted decoding parameter.

8. The data decoder of claim 1 , wherein the at least one processor is to adjust a second decoding parameter based on the adjusted decoding parameter and wherein to adjust a second decoding parameter based on the adjusted decoding parameter, the at least one processor is to:
access a look-up-table configured to specify a second decoding parameter associated with the adjusted decoding parameter.

9. The data decoder of claim 1 , wherein the at least one processor is to adjust a second decoding parameter based on the adjusted decoding parameter and wherein to adjust a second decoding parameter based on the adjusted decoding parameter, the at least one processor is to:
perform a computation based on the adjusted decoding parameter to determine the second decoding parameter.

10. The data decoder of claim 1 , comprising at least two buffers wherein a buffer of the at least two buffers is allocated to store decoded symbols from a first speculative decode and a buffer of the at least two buffers is allocated to store decoded symbols from a second speculative decode and wherein decoding parameters that affect content levels of the at least two buffers are configured based on one or more of convergence between sequential decode and speculative decode or content level of the buffer.

11. The data decoder of claim 1 , wherein the at least one processor is used for decode of entropy encoded tokens by one or more of an offload engine, decryption engine, network interface, central processing unit (CPU), or memory controller and wherein the offload engine or decryption engine comprise using one or more of: a Field Programmable Gate Array (FPGA), application specific integrated circuit (ASIC), or other programmable hardware device.

12. The data decoder of claim 11 , wherein one or more of an offload engine, decryption engine, network interface, central processing unit (CPU), or memory controller are communicatively coupled to a server, data center, or rack.

13. The data decoder of claim 1 , wherein the at least one entropy encoded token comprises Huffman encoded tokens.

14. A computer-implemented method comprising:
speculatively decoding one or more entropy encoded tokens at an offset from an entropy encoded token decoded by sequentially decoding;
determining a content level of a buffer that stores speculatively decoded tokens; and
adjusting a decoding parameter based on the content level of the buffer.

15. The method of claim 14 , comprising adjusting a second decoding parameter based on the adjusted decoding parameter.

16. The method of claim 15 , comprising:
at a checkpoint, determining whether alignment occurs between an entropy encoded token to be decoded by sequentially decoding and an entropy encoded token to be decoded using the speculatively decoding;
based on alignment, saving speculatively decoded tokens based on the second decoding parameter;
adjusting a token starting point for sequentially decoding to be after the speculatively decoded tokens; and
speculatively decoding a token based on the adjusted decoding parameter.

17. The method of claim 14 , comprising:
based on non-alignment, discarding speculatively decoded tokens;
continuing sequential decoding for a next available non-decoded token; and
speculatively decoding at least one token at the adjusted decoding parameter.

18. The method of claim 14 , comprising adjusting a second decoding parameter based on the adjusted decoding parameter and wherein adjusting a second decoding parameter based on the adjusted decoding parameter is based on a look-up-table.

19. The method of claim 14 , comprising adjusting a second decoding parameter based on the adjusted decoding parameter and wherein adjusting a second decoding parameter based on the adjusted decoding parameter is based on a calculation of the second decoding parameter based on the adjusted decoding parameter.

20. The method of claim 14 , wherein the token comprises a token encoded using Huffman encoding.

21. A system comprising:
a memory;
a network interface;
at least one processor communicatively coupled to the memory and the network interface, wherein the at least one processor is to:
speculatively decode at least one token starting at an offset from an entropy encoded token decoded in sequential order;
store speculatively decoded tokens in a buffer in the memory;
at a checkpoint, determine whether alignment occurs between an entropy encoded token to be decoded by the decode in sequential order and an entropy encoded token to be decoded by the speculatively decode; and
adjust a decoding parameter based on alignment or content level of the buffer.

22. The system of claim 21 , wherein the at least one processor is to adjust a second decoding parameter based on the adjusted decoding parameter.

23. The system of claim 22 , wherein the at least one processor is to determine an occurrence of convergence between a sequential decode and a speculative decode and to determine an occurrence of convergence between a sequential decode and a speculative decode, the at least one processor is to:
at a checkpoint, determine if a start of a token to be decoded using the sequential decode aligns with a token to be decoded using the speculative decode;
based on alignment, discard symbols according to the second decoding parameter and commit any non-discarded symbol generated from the speculative decode or
based on non-alignment, discard symbols generated from the s

Assignees

• Intel Corp

Inventors

• Suresh Vikram B
• Satpathy Sudhir K
• Mathew Sanu K

Classifications

• H03M7/6005 Primary

  Decoder aspects · CPC title

• H03M7/3086 Primary

  employing a sliding window, e.g. LZ77 · CPC title

• H03M7/425

  for the decoding process only · CPC title