Parallel entropy encoding on GPU

Patent metadata

Field	Value
Publication number	US-9058223-B2
Application number	US-201113092713-A
Country	US
Kind code	B2
Filing date	Apr 22, 2011
Priority date	Apr 22, 2011
Publication date	Jun 16, 2015
Grant date	Jun 16, 2015

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.

First claim

What is claimed:

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

Assignees

• Shchepetov Denis Sergeyevich
• Sankuratri Sridhar
• Saint Macary Damien Gerard
• Hsieh Paul Johan
• Microsoft Technology Licensing Llc

Inventors

• Shchepetov Denis Sergeyevich
• Sankuratri Sridhar
• Saint Macary Damien Gerard
• Hsieh Paul Johan

Classifications

• G06T9/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 title

• G06T9/005

  Statistical coding, e.g. Huffman, run length coding · CPC title

• H04N19/93

  Run-length coding · CPC title

• H04N19/91

  Entropy coding, e.g. variable length coding [VLC] or arithmetic coding · CPC title

• G06F9/52 Primary

  Program synchronisation; Mutual exclusion, e.g. by means of semaphores · CPC title