Parallel entropy encoding on GPU

• US 9,058,223 B2
• Filed: 04/22/2011
• Issued: 06/16/2015
• Est. Priority Date: 04/22/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Shchepetov, Denis Sergeyevich, Sankuratri, Sridhar, Saint Macary, Damien Gerard, Hsieh, Paul Johan
• Primary Examiner(s): Patel, Jayesh A
• Application Number:
  US13/092,713
• Publication Number:
  US 20120268469A1
• Time in Patent Office: 1,516 Days
• Field of Search: 382/232
• US Class Current: 1/1
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H04N 19/436 using parallelised computational arrangements
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
• CPC Class Codes: H04N 19/93 Run-length coding

Abstract

An invention is disclosed for performing entropy encoding in a parallelized manner, using a GPU. In embodiments, an input sequence of integers is received, and run-length encoding is performed on any runs of zeros in parallel operations on the GPU. Then, a plurality of parallelized operations are performed on the run-length encoded sequence to entropy encode the sequence. The value N may be entropy encoded using only N and the value that precedes it in the sequence, N−1, so the encoding may be sub-divided into multiple operations that may be performed in parallel on the GPU. After entropy encoding is performed, a bitstream may be produced using parallelized operations on the GPU.

Claims

1. A method, comprising:

encoding a data with a first encoding scheme to produce an ordered set of values comprising a first value, a second value, and a third value, the first value preceding the second value and the third value in the ordered set, the second value preceding the third value in the ordered set;

executing a first thread on a graphics processing unit (GPU) to encode the first value with a second encoding scheme, based on the first value and a reference value, the reference value being separate from the data and the ordered set of values;

while executing the first thread on the GPU, executing a second thread on the GPU to encode the second value with the second encoding scheme, based on the second value and the first value;

while executing the first thread on the GPU, executing a third thread on the GPU to encode the third value with the second encoding scheme, based on the third value and the second value; and

storing the encoded first, second, and third values in a memory location.

2. The method of claim 1, wherein the first value and the second value belong to an ordered sequence of values, and further comprising:

before executing the first thread, replacing each contiguous sequence of one or more zeros in the ordered sequence of values with a reserved number representing the number of zeroes in the contiguous sequence of zeros, the reserved number having a value outside of a range of values allowed for the first value or the second value.

3. The method of claim 2, further comprising:

inserting a second reserved number into the ordered sequence between each pair of non-zero values, the reserved number having a value outside of a range of values allowed for the first value, the second value, or a value used to represent zero.

4. The method of claim 1, wherein the encoded first value comprises a right prefix representing a rightmost number of bits, and wherein executing the first thread on the GPU to encode the first value with the second encoding scheme, based on the first value and the reference value comprises:

executing the first thread on the GPU to encode the first value with the second encoding scheme, such that the binary representation of the first value equals the binary representation of the right prefix.

5. The method of claim 1, wherein storing the encoded first value and the encoded second value in a memory location further comprises:

storing a reference to a first number of bits and a reference to a second number of bits in a second memory location, the first number of bits representing the encoded first value in binary, and the second number of bits representing the encoded second value in binary.

6. The method of claim 5, wherein,

executing first thread on the GPU to encode the first value with the second encoding scheme comprises:

executing the first thread on the GPU to determine the reference to the first number of bits, based on the first value and the reference value; and

wherein, executing the second thread on the GPU to encode the second value with the second encoding scheme comprises;

executing the second thread on the GPU to determine the reference to the second number of bits, based on the second value and the first value.

7. The method of claim 5, wherein the first value is stored as a first representation of a data type and the second value is stored as a second representation of the data type, the data type having a number of data type bits, the number of data type bits being greater than the representation of the first number of bits or the representation of the second number of bits, and further comprising:

storing in a bitstream the rightmost number of bits of the first representation of the data type equal to the representation of the first number of bits; and

storing in the bitstream, in a position immediately after the rightmost number of bits of the first representation of the data type, the rightmost number of bits of the second representation of the data type equal to the representation of the second number of bits.

8. The method of claim 7, wherein the representation of the first number of bits and the representation of the second number of bits are part of an ordered sequence of values, and further comprising:

executing a third thread on the GPU to calculate a first partial number of bits from the leftmost bit in the bitstream that the rightmost number of bits of the second representation of the data type is to be stored;

while executing the third thread on the GPU, executing a fourth thread on the GPU to calculate a second partial number of bits from the leftmost bit in the bitstream that the rightmost number of bits of the second representation of the data type is to be stored;

executing a fifth thread on the GPU to calculate the sum of the first partial number of bits and the second partial number of bits;

wherein storing in the bitstream the rightmost number of bits of the first representation of the data type comprises;

executing a sixth thread on the GPU for storing the rightmost number of bits of the first representation of the data type; and

wherein storing in the bitstream, in a position immediately after the rightmost number of bits of the first representation of the data type, the rightmost number of bits of the second representation of the data type comprises;

executing a seventh thread on the GPU for storing the rightmost number of bits of the second representation of the data type a number of bits to the right of the beginning of the bitstream equal to the sum.

9. The method of claim 1, wherein the encoded first value comprises an indication of a difference of the number of bits used to represent the reference value in binary and the number of bits used to represent the first value in binary.

10. The method of claim 9, wherein the encoded first value comprises a most significant portion and a least significant portion when represented in binary, the most significant portion comprises the indication, and the least significant portion represents the first value in binary.

11. The method of claim 10, wherein the encoded second value comprises a most significant portion and a least significant portion when represented in binary, the most significant portion comprises the indication, and the least significant portion represents the second value in binary.

12. The method of claim 1, wherein the first value is referenced by a first element of an array and the second value is referenced by a second element of the array.

13. A system, comprising:

a processor; and

a memory communicatively coupled to the processor when the system is operational, the memory bearing processor-executable instructions that, when executed on the processor, the system at least to;

encode data with a first encoding scheme to produce a first value and a second value;

execute a first thread on a graphics processing unit (GPU) to encode the first value with a second encoding scheme, based on the first value and a reference value;

while executing the first thread on the GPU, execute a second thread on the GPU to encode the second value with the second encoding scheme, based on the second value and the first value; and

store the encoded first value and the encoded second value in a memory location.

14. The system of claim 13, wherein the first value and the second value belong to an ordered sequence of values, and wherein the memory further bears processor-executable instructions that, when executed on the processor, cause the system at least to:

before executing the first thread, replace each contiguous sequence of one or more zeros in the ordered sequence of values with a reserved number representing the number of zeroes in the contiguous sequence of zeros, the reserved number having a value outside of a range of values allowed for the first value or the second value.

15. The system of claim 14, wherein the memory further bears instructions that, when executed on the processor, cause the system at least to:

insert a second reserved number into the ordered sequence between each pair of non-zero values, the reserved number having a value outside of a range of values allowed for the first value, the second value, or a value used to represent zero.

16. The system of claim 13, wherein the encoded first value comprises a right prefix representing a rightmost number of bits, and wherein the instructions that, when executed on the processor, cause the system at least to execute the first thread on the graphics processing unit (GPU) to encode the first value with the second encoding scheme, based on the first value and the reference value further cause the system at least to:

execute the first thread on the GPU to encode the first value with the second encoding scheme, such that the binary representation of the first value equals the binary representation of the right prefix.

17. The system of claim 13, wherein the instructions that, when executed on the processor, cause the system at least to store the encoded first value and the encoded second value in a memory location further cause the system at least to:

store a reference to a first number of bits and a reference to a second number of bits in a second memory location, the first number of bits representing the encoded first value in binary, and the second number of bits representing the encoded second value in binary.

18. The system of claim 17, wherein the instructions that, when executed on the processor, cause the system to at least execute the first thread on the GPU to encode the first value with the second encoding scheme further cause the system at least to:

execute the first thread on the GPU to determine the reference to the first number of bits, based on the first value and the reference value; and

wherein the instructions that, when executed on the processor, cause the system to at least execute the second thread on the GPU to encode the first value with the second encoding scheme further cause the system at least to;

execute the second thread on the GPU to determine the reference to the second number of bits, based on the second value and the first value.

19. The system of claim 17, wherein the first value is stored as a first representation of a data type and the second value is stored as a second representation of the data type, the data type having a number of data type bits, the number of data type bits being greater than the representation of the first number of bits or the representation of the second number of bits, and wherein the memory further bears instructions that, when executed on the processor, cause the system at least to:

store in a bitstream the rightmost number of bits of the first representation of the data type equal to the representation of the first number of bits; and

store in the bitstream, in a position immediately after the rightmost number of bits of the first representation of the data type, the rightmost number of bits of the second representation of the data type equal to the representation of the second number of bits.

20. A computer-readable storage device for parallelized entropy encoding of a first value and a second value of an ordered set of values, bearing computer-executable instructions that, when executed on a computer, cause operations comprising:

executing a first thread on a graphics processing unit (GPU) to entropy encode the first value, based on the first value and a reference value, the reference value being separate from the ordered set of values;

while executing the first thread on the GPU, executing a second thread on the GPU to entropy encode the second value, based on the second value and the first value; and

storing the encoded first value and the encoded second value in a memory location.