Parallel decoding techniques

In various embodiments, an encoded sequence (e.g., a compressed sequence for uncompressed data) that includes variable-length codes is decoded in an iterative fashion to generate a decoded sequence of symbols. During each iteration, a group of threads decode in parallel the codes in the encoded sequence to generate symbols. The group of threads then compute offsets based on the sizes of the symbols. Subsequently, the group of threads generates in parallel a contiguous portion of the decoded sequence based on the symbols, an output address, and the offsets.

BACKGROUND

Field of the Various Embodiments

The various embodiments relate generally to parallel processing systems and, more specifically, to parallel decoding techniques.

DESCRIPTION OF THE RELATED ART

Lossless data encoding algorithms and the corresponding data decoding algorithms are used to reduce the resources required to store and transmit data without incurring any information loss. Oftentimes, a lossless data encoding algorithm executing on a computing device maps a source sequence of literals (e.g., bytes or alphabetic characters) represented as fixed-length “symbols” to an encoded sequence of “codes” having a reduced size. Subsequently, the computing device and/or any number of other computing devices that acquire the encoded sequence execute corresponding data decoding algorithms to map the encoded sequence to a decoded sequence of symbols. The decoded sequence of symbols represents a decoded sequence of literals that is a replica of the source sequence of literals.

Lossless data encoding algorithms are often based on entropy coding techniques that are optimized for a combination of size reduction or “compression ratio” and decoding throughput. In some types of entropy encoding, the lengths of codes vary inversely to the frequency of the corresponding symbols. Accordingly, relatively short codes are used to represent commonly used symbols and relatively longer codes are used to represent infrequently used symbols. In addition to entropy coding, some algorithms can map symbols representing copies or “copy” symbols to “copy” codes. Each copy symbol is a back-reference specifying the locations and length of a string of literals in the source sequence.

One challenge associated with decoding encoded sequences as described above is that, because of the variable lengths of the codes, directly addressing and properly decoding specific codes within an encoded sequence in a non-serial fashion is problematic. As a result, data decoding algorithms are unable to efficiently parallelize the decoding of the resulting encoded sequences and therefore the decoding throughput for client devices capable of parallel processing can be unnecessarily low.

For instance, in one approach to “data-parallel” decoding, a subsequence-based encoding algorithm executing on a computing device partitions a given sequence into symbol-aligned encoded subsequences and generates metadata specifying an input pointer for each encoded subsequence. The metadata is then stored and/or transmitted to other computing device along with the encoded sequence that is made up of the encoded subsequences. On the computing device and/or the other computing devices, a subsequence-based decoding algorithm assigns the input pointers and the corresponding encoded subsequences to different threads. For each thread, the subsequence-based decoding algorithm also computes an output pointer that delineates where the thread is to store literals represented by decoded symbols within the decoded sequence. In parallel to the other threads, each thread sequentially decodes the codes in the assigned encoded subsequence as per the input pointer of the thread and stores the literals represented by the decoded symbols in the decoded sequence as per the output thread of the thread.

One drawback of performing data-parallel decoding based on subsequences is that transmitting and/or storing the metadata reduces the compression ratio. Another drawback is that the threads access memory sparsely when reading from the encoded sequence and when writing to the decoded sequence. As is well-known, accessing memory sparsely can degrade processing efficiency and therefore can decrease the decoding throughput. Yet another drawback of performing data-parallel decoding based on subsequences is that a copy code can be read by one thread before the original string of literals referenced by the copy code is stored in the decoded sequence by another thread. To address this problem, the copy codes are usually stored for deferred processing, consuming additional memory and further decreasing decoding throughput.

As the foregoing illustrates, what is needed in the art are more effective techniques for data-parallel decoding of encoded sequences that include variable-length codes.

SUMMARY

One embodiment of the present invention sets forth a method for decoding an encoded sequence that includes variable-length codes. The method includes determining a first set of codes based on the encoded sequence; decoding the first set of codes to generate a first set of symbols; determining a first set of offsets based on the first set of symbols; and generating a first contiguous portion of a decoded sequence based on the first set of symbols, the first set of offsets, and a first address.

At least one technical advantage of the disclosed techniques relative to the prior art is that, with the disclosed techniques, parallelizing decoding of encoded sequences that include variable-length codes does not reduce compression ratios. In that regard, because the arrangement of the codes within the encoded stream is tailored to facilitate data-parallel processing, threads in a thread group can cooperate to access groups of codes for parallel decoding deterministically and iteratively without requiring metadata that inherently reduces the compression ratio. Furthermore, unlike prior art techniques, because the threads read contiguous words from the encoded sequence and write literals represented by contiguous symbols to the decoded sequence, the decoding throughput is not reduced by sparse memory accesses. And because the thread group incrementally generates the decoded sequence from beginning to end without any gaps, copy codes do not require deferred processing that can adversely impact memory usage and decoding throughput in some prior-art techniques. These technical advantages provide one or more technological improvements over prior art approaches.

DETAILED DESCRIPTION

As described previously herein, one challenge associated with decoding encoded sequences that include variable-length codes is that directly addressing and properly decoding specific codes within an encoded sequence in a non-serial fashion is problematic. In one conventional approach to data-parallel decoding, a subsequence-based encoding algorithm partitions a given sequence into symbol-aligned encoded subsequences and generates metadata specifying an input pointer for each encoded subsequence included in the encoded sequence. A subsequence-based decoding algorithm uses the metadata to configure multiple threads to decode the encoded subsequences in parallel.

On drawback of the above conventional subsequence-based approach to data-parallel decoding is that transmitting and storing the metadata reduces the compression ratio. Another drawback is that because the threads end up accessing memory sparsely when reading from the encoded sequence and when writing to the decoded sequence, the decoding throughput can be decreased. Yet another drawback of the conventional subsequence-based approach to data-parallel decoding is that because the decoded sequence can include gaps, the subsequence-based decoding application can be forced to store copy codes for deferred processing, thereby consuming additional memory and further decreasing decoding throughput.

To address the above problems, an entropy encoding application180systematically rearranges the bits in encoded sequences relative to the corresponding symbols representing the source sequences to facilitate data-parallel decoding. In this fashion, the entropy encoding application180institutes a coding format that renders encoded sequences amenable to decoding using a group of threads or “thread group” executing in parallel. As used herein, a “thread” can be a software thread or a hardware thread.

A “software thread” refers to a thread of execution executing on any type of processing unit. For explanatory purposes only, a group of software threads that decodes an encoded sequence generated by the entropy encoding application180is also referred to herein as a “decoding thread group.” A “hardware thread” refers to an independent hardware process that can be implemented via any number and/or types of fixed-function hardware units (e.g., a copy engine). For explanatory purposes only, a group of one or more fixed-function hardware units that decodes an encoded sequence generated by the entropy encoding application180is also referred to herein collectively as a “parallel decoding unit.”

In general, the entropy encoding application180can execute on any type of processing system, and the resulting encoded sequence can be decoded via a decoding thread group or a parallel decoding unit included in the same processing system of a different processing system. For instance, in some embodiments, both the entropy encoding application180and a parallel decoding application190execute on a multi-core processor. The entropy encoding application180generates an encoded sequence. To decode the encoded sequence, the parallel decoding application190causes a decoding thread group to execute across multiple cores included in the multi-core processor. Some examples of multi-core processors include, without limitation, certain types of central processing units (“CPUs”), graphics processing units (“GPUs”), parallel processing units (“PPUs”), and accelerated processing units (*“APUs”).

For explanatory purposes only, the functionality of the entropy encoding application180, the parallel decoding application190, the decoding thread group, and the parallel decoding unit are described below in conjunction withFIGS. 1-6in the context of some other embodiments that are implemented within a system100. The system100includes, without limitation, a CPU102and a parallel processing subsystem102that includes any number of PPUs. As described in greater detail below, in the embodiments depicted inFIGS. 1-6, the entropy encoding application180executes on the CPU102to generate an encoded sequence. In some embodiments, to decode the encoded sequence, the parallel decoding application190causes a decoding thread group to execute on a streaming multiprocessor (“SM”) included in one of the PPUs. In some other embodiments, the parallel decoding application190can be omitted from the system100and, as depicted inFIG. 2, a parallel decoding unit included in the PPU decodes the encoded sequence.

Note that the techniques described herein are illustrative rather than restrictive and may be altered without departing from the broader spirit and scope of the invention. Many modifications and variations on the functionality provided by the entropy encoding application180, the parallel decoding application190, the decoding thread group, and the parallel decoding unit will be apparent to those of ordinary skill in the art without departing from the scope and spirit of the described embodiments.

Exemplar System Overview

FIG. 1is a block diagram illustrating a system100configured to implement one or more aspects of the present disclosure. As shown, the system100includes, without limitation, a central processing unit (“CPU”)102and a system memory104coupled to a parallel processing subsystem112via a memory bridge105and a communication path113. The memory bridge105is further coupled to an input/output (“I/O”) bridge107via a communication path106, and the I/O bridge107is, in turn, coupled to a switch116.

In operation, the I/O bridge107is configured to receive user input information from input devices108, such as a keyboard or a mouse, and forward the input information to the CPU102for processing via the communication path106and the memory bridge105. The switch116is configured to provide connections between the I/O bridge107and other components of the system100, such as a network adapter118and add-in cards120and121.

As also shown, the I/O bridge107is coupled to a system disk114that can be configured to store content and applications and data for use by the CPU102and the parallel processing subsystem112. As a general matter, the system disk114provides non-volatile storage for applications and data and can include fixed or removable hard disk drives, flash memory devices, compact disc read-only-memory, digital versatile disc read-only-memory, Blu-ray, high definition digital versatile disc, or other magnetic, optical, or solid state storage devices. Finally, although not explicitly shown, other components, such as universal serial bus or other port connections, compact disc drives, digital versatile disc drives, film recording devices, and the like, can be connected to the I/O bridge107as well.

In various embodiments, the memory bridge105can be a Northbridge chip, and the I/O bridge107can be a Southbrige chip. In addition, the communication paths106and113, as well as other communication paths within the system100, can be implemented using any technically suitable protocols, including, without limitation, Accelerated Graphics Port, HyperTransport, or any other bus or point-to-point communication protocol known in the art.

In some embodiments, the parallel processing subsystem112comprises a graphics subsystem that delivers pixels to a display device110that can be any conventional cathode ray tube, liquid crystal display, light-emitting diode display, or the like. In such embodiments, the parallel processing subsystem112incorporates circuitry optimized for graphics and video processing, including, for example, video output circuitry. As described in greater detail below inFIG. 2, such circuitry can be incorporated across one or more parallel processing units (“PPUs”) included within the parallel processing subsystem112. In other embodiments, the parallel processing subsystem112incorporates circuitry optimized for general purpose and/or compute processing. Again, such circuitry can be incorporated across one or more PPUs included within the parallel processing subsystem112that are configured to perform such general purpose and/or compute operations. In yet other embodiments, the one or more PPUs included within the parallel processing subsystem112can be configured to perform graphics processing, general purpose processing, and compute processing operations.

In some embodiments, the parallel processing subsystem112can be integrated with one or more other the other elements ofFIG. 1to form a single system. For example, the parallel processing subsystem112can be integrated with the CPU102and other connection circuitry on a single chip to form a system on a chip (“SoC”). In the same or other embodiments, any number of CPUs102and any number of parallel processing subsystems112can be distributed across any number of shared geographic locations and/or any number of different geographic locations and/or implemented in one or more cloud computing environments (i.e., encapsulated shared resources, software, data, etc.) in any combination.

In some embodiments, the system memory104can include, without limitation, any number of software applications, any number of device drivers (not shown), or any combination thereof. Each of the software applications can reside in any number of memories and execute on any number of processors in any combination. As referred to herein, a “processor” can be any instruction execution system, apparatus, or device capable of executing instructions. Some examples of processors include, without limitation, the CPU102, the parallel processing subsystem112, and the PPUs.

In some embodiments, at least one device driver is configured to manage the processing operations of the one or more PPUs within the parallel processing subsystem112. In the same or other embodiments, the device driver implements application programming interface (“API”) functionality that enables software applications to specify instructions for execution on the one or more PPUs via API calls.

As shown, in some embodiments, the system memory104includes, without limitation, an entropy encoding application180and/or a parallel decoding application190. In some embodiments, the entropy encoding application180is a software application that executes on the CPU102. In some other embodiments, the entropy encoding application180is a software application that executes on any number of PPUs included within the parallel processing subsystem112. In the same or other embodiments, the parallel decoding application190is a software application that executes instructions on any number of PPUs included within the parallel processing subsystem112and/or any number of other parallel processing subsystems112(not shown). In some other embodiments, the parallel decoding application190is a software application that executes on the CPU102.

In some embodiments, the entropy encoding application180executes on an instance of the CPU102that is included in a server device and any number of instances of the entropy encoding application180execute on any number of instances of the parallel processing subsystem112distributed across any number of client devices located in different geographic locations.

In some embodiments, the entropy encoding application180encodes source sequences (not shown inFIG. 1) to generate encoded sequences (not shown inFIG. 1) that reduce the resources required to store and transmit the source sequences without incurring any information loss. As referred to herein, a “sequence” can be any sequence of any number and/or types of discrete portions of data. Some examples of sequences include, without limitation, bitstreams and bytestreams.

For explanatory purposes only, discrete portions of data included in a source sequence are referred to herein as “literals” and are represented by “symbols.” In some embodiments, each literal is a byte or an alphabetic character. In the same or other embodiments, each symbol is either a literal symbol or a copy symbol, where each literal symbol represents a single literal, and each copy symbol represents a copy that generates a string of literals. More precisely, in some embodiments, a copy symbol is a back-reference specifying the location and length of an original sequence of literals that is identical to and proceeds the associated sequence of literals in the source sequence.

As part of generating the encoded sequence for a given source sequence, the entropy encoding application180maps each symbol included in the given encoded sequence to a variable-length code based, at least in part, on entropy encoding techniques. As referred to herein, each “code” can be any discrete portion of data and different codes can be associated with different code types. Furthermore, a group of symbols is mapped to a group of variable-length codes, containing as many codes as there are symbols in the group of symbols. In some embodiments, the lengths of the codes vary inversely to the frequency of the corresponding symbols representing the associated source sequence.

Enabling Efficient Data-Parallel Decoding

As outlined previously herein, to address problems that can be associated with conventional approaches to data-parallel decoding, the entropy encoding application180systematically rearranges the bits of encoded sequences relative to the corresponding symbols representing the source sequences to facilitate data-parallel decoding. In this fashion, the entropy encoding application180institutes a coding format that renders encoded sequences amenable to decoding using a thread group executing in parallel. Again, as used herein, a thread can be a software thread or a hardware thread.

In some embodiments, each of the threads in a thread group is associated with a different thread identifier (“ID”) that uniquely identifies the thread within the thread group. In some embodiments, any number and/or types of techniques (e.g., predication) can be used to disable one or more of the threads in a thread group for any period of time. In the same or other embodiments, the threads in a thread group can synchronize together, collaborate, communicate, or any combination thereof in any technically feasible fashion (e.g., via a shared memory).

In some embodiments, a thread group can be configured to decode a given encoded sequence based on single-instruction, multiple-data (“SIMD”) model in which each thread processes a different set of data based on a single set of instructions. A thread group that is configured based on a SIMD model is also referred to herein as “a SIMD thread group.” In some embodiments, the threads in a SIMD thread group execute in lock-step. In some other embodiments, a thread group can be configured to decode a given encoded sequence based on single-instruction, multiple-thread (“SIMT”) model that, relative to a SIMD model allows different threads to more readily follow divergent execution paths.

As shown, in some embodiments, the entropy encoding application180encodes each of any number of source sequences based on a thread group size182and a word size184. For explanatory purposes only, the functionality of the entropy encoding application180is described herein in the context of encoding a single source sequence to generate a corresponding encoded sequence. However, the thread group size182and the word size184can be used to encode any number of source sequences and can therefore be common to any number of encoded sequences.

The thread group size182specifies the total number of threads that are to be available for decoding the encoded sequence generated by the entropy encoding application180. The thread group size182can be any integer greater than one and can be determined in any technically feasible fashion. For instance, in some embodiments, the thread group size182can be determined based on the architecture of the parallel processing subsystem112.

In some embodiments, the entropy encoding application180formats the encoded sequence such that a thread group having the thread group size182can iteratively determine groups of symbols and store the corresponding groups of literals in contiguous memory to incrementally generate the decoded sequence from beginning to end without any gaps. For explanatory purposes only, an “decoding iteration” refers to a sequence of steps during which the threads in the thread group concurrently acquire different codes based on the encoded sequence, concurrently decode the codes to generate the corresponding symbols, and concurrently store the literals represented by the symbols in contiguous memory.

In the same or other embodiments, the entropy encoding application180can indicate implicitly or explicitly the number of threads that are to be used to process any portion of the encoded sequence during decoding in any technically feasible fashion. For instance, in some embodiments, each block of the encoded sequence is associated with data-parallel processing (e.g., a compressed block) or serial processing (e.g., a header block). During decoding, all threads included in a thread group having the thread group size182process the blocks associated with data-parallel processing and a single thread in the thread group processes the blocks associated with serial processing.

In some embodiments, the word size184specifies the size of fixed-size words also referred to herein as “words” into which the entropy encoding application180packs the codes representing the symbols in the source sequence. In the same or other embodiments, each word is associated with one thread, and each thread is associated with multiple words. The entropy encoding application180then aggregates the words to generate the encoded sequence. As a result, the encoded sequence is a linear array of fixed-sized words.

The word size184can specify any integer number of bits and can be determined in any technically feasible fashion. In some embodiments, the word size184can be determined based on the architecture of the parallel processing subsystem112. For instance, in some embodiments, the word size184is set to the number of bits that the parallel processing subsystem112can read from memory using a single read operation (e.g., 32 bits, 64 bits, etc.).

As shown, the thread group size182is symbolized as “T” and the word size184is symbolized as “B.” For explanatory purposes only, numbering with respect to the entropy encoding application180and the entropy decoding application180is zero-based. Accordingly, the thread IDs associated with a thread group having the thread group size182range from 0 to (T-1). And the initial decoding iteration is the zeroth iteration.

In some embodiments, to encode the source sequence, the entropy encoding application180executes any number and/or types of encoding algorithms to map the symbols representing the literals included in the source sequence to a sequence of codes. The entropy encoding application180then repeatedly assigns contiguous groups of T codes to T thread IDs. Each contiguous group of T codes corresponds to a different decoding iteration. In this fashion, in some embodiments, the entropy encoding application180assigns the xthcode with respect to the source sequence to the thread corresponding to the thread ID of x % T for decoding during the floor(x/T) decoding iteration. The xthsymbol is therefore determined by the thread corresponding to the thread ID of x % T.

For instance, if the thread group size182is 32, then the entropy encoding application180assigns the 0thto 31stcodes with respect to the source sequence to the threads corresponding to the thread IDs 0-31, respectively, for decoding during the 0thdecoding iteration. The entropy encoding application180then assigns the 32ndto 63rdcodes with respect to the source sequence to the threads corresponding to the thread IDs 0-31, respectively, for decoding during the 1st decoding iteration, and so forth.

In some embodiments, the entropy encoding application180packs the codes into words having the word size184and then generates the encoded sequence based on the words. In operation, for each of the thread IDs, the entropy encoding application packs the bits for the assigned codes into words that each have B bits in order of increasing decoding iteration. Notably, each word can begin and/or end with partial codes. For example, if B is 16 bits and the lengths in bits of the first seven codes assigned to a given thread ID are, sequentially with respect to the source sequence, 6, 5, 3, 4, 1, 8, and 5, then the entropy encoding application180generates one word that includes the first three codes and the first half of the fourth code and another word that includes the second half of the fourth code and the next three codes.

For explanatory purposes only, the decoding iteration of a given word refers to the lowest decoding iteration associated with first code included in the word. To generate the encoded sequence, the entropy encoding application arranges the words based on a primary criterion of increasing decoding iteration and a secondary criterion of increasing thread ID. An example of an encoded sequence that the entropy encoding application180generates based on both the thread group size182and the word size184is described in greater detail below in conjunction withFIG. 5.

In some embodiments, the parallel decoding application190decodes any number of encoded sequences that are formatted for data-parallel decoding as described above with respect to the entropy encoding application180. The parallel decoding application190can acquire (e.g., receive, read from memory, etc.) the encoded sequences from any number and/or types of devices internal or external to the system100in any technically feasible fashion. In some embodiments, the parallel decoding application190can receive any number of encoded sequences generated by any number of instances of the entropy encoding application180executing on any number and/or types of processors. In the same or other embodiments, the entropy encoding application180is omitted form the system100.

In some embodiments, the parallel decoding application190decodes each of the encoded sequences based on the thread group size182and optionally the word size184. The parallel decoding application190can determine the thread group size182and the word size184in any technically feasible fashion. For instance, in some embodiments, the thread group size182and the word size184are defined based on the architecture of the parallel processing subsystem112.

For explanatory purposes only, the functionality of the parallel decoding application190is described herein in the context of decoding a single encoded sequence to generate a corresponding decoded sequence. However, the thread group size182and the word size184can be common to any number of encoded sequences and the parallel decoding application190can therefore use the thread group size182and the word size184to decode any number of encoded sequences.

In some embodiments, the parallel decoding application190configures the threads in a thread group having the thread group size182and executing on a processor (e.g., a multithreaded processor included in the parallel processing subsystem112) to decode the encoded sequence in parallel. In the same or other embodiments, the parallel decoding application190can dynamically adjust the number of threads (e.g., disable one or more threads in a thread group having the thread group size182) that the parallel decoding application190uses to decode different portions of the encoded sequence based on any amount and/or type of criteria. For instance, in some embodiments, the parallel decoding application190can configure all threads in the decoding thread group to process blocks associated with data-parallel processing (e.g., compressed blocks) and can configure a single thread in the decoding thread group to process blocks associated with serial processing (e.g., header blocks).

The parallel decoding application190can configure a thread group to decode the encoded sequence in any technically feasible fashion. In some embodiments, the parallel decoding application190configures a group of T threads to each execute a different instance of a decoder kernel192in SIMD fashion, thereby generating a decoding thread group (not shown inFIG. 1). As shown, in some embodiments, the decoder kernel192resides in memory included in the parallel processing subsystem112. More specifically, in some embodiments, the decoder kernel192resides in a parallel processing (“PP”) memory that is coupled to one of the PPUs included within the parallel processing subsystem112. The PPU and the PP memory are described below in conjunction withFIG. 2. The decoding thread group is described in detail below in conjunction withFIGS. 4 and 5.

In some embodiments, any portion (including all) of the functionality of the entropy encoding application180as described herein can be implemented in hardware. In the same or other embodiments, the entropy encoding application180is omitted from the system100. In some embodiments, any portion (including all) of the functionality of the parallel decoding application190as described herein can be implemented in fixed-function hardware that is capable of executing multiple hardware threads. As described in greater detail below in conjunction withFIG. 2, in some embodiments, a fixed-function parallel decoding unit (not shown inFIG. 1) implements the functionality of the parallel decoding application190and the decoding thread group. In the same or other embodiments, the parallel encoding application190is omitted form the system100.

Note that the techniques described herein are illustrative rather than restrictive and may be altered without departing from the broader spirit and scope of the invention. Many modifications and variations on the functionality provided by the entropy encoding application180, the parallel decoding application190, and the decoder kernel192will be apparent to those of ordinary skill in the art without departing from the scope and spirit of the described embodiments.

It will be appreciated that the system shown herein is illustrative and that variations and modifications are possible. The connection topology, including the number and arrangement of bridges, the number of the CPUs102, and the number of the parallel processing subsystems112, can be modified as desired. For example, in some embodiments, the system memory104can be connected to the CPU102directly rather than through the memory bridge105, and other devices can communicate with the system memory104via the memory bridge105and the CPU102. In other alternative topologies, the parallel processing subsystem112can be connected to the I/O bridge107or directly to the CPU102, rather than to the memory bridge105. In still other embodiments, the I/O bridge107and the memory bridge105can be integrated into a single chip instead of existing as one or more discrete devices. Lastly, in certain embodiments, one or more components shown inFIG. 1may not be present. For example, the switch116could be eliminated, and the network adapter118and the add-in cards120,121would connect directly to the I/O bridge107.

FIG. 2is a block diagram of a parallel processing unit (“PPU”)202included in the parallel processing subsystem112ofFIG. 1, according to various embodiments. AlthoughFIG. 2depicts one PPU202, as indicated above, the parallel processing subsystem112can include any number of PPUs202. As shown, the PPU202is coupled to a local PP memory204. The PPU202and the PP memory204can be implemented using one or more integrated circuit devices, such as programmable processors, application specific integrated circuits, or memory devices, or in any other technically feasible fashion.

In some embodiments, the PPU202comprises a graphics processing unit that can be configured to implement a graphics rendering pipeline to perform various operations related to generating pixel data based on graphics data supplied by the CPU102and/or the system memory104. When processing graphics data, the PP memory204can be used as graphics memory that stores one or more conventional frame buffers and, if needed, one or more other render targets as well. Among other things, the PP memory204can be used to store and update pixel data and deliver final pixel data or display frames to the display device110for display. In some embodiments, the PPU202also can be configured for general-purpose processing and compute operations.

As described previously herein in conjunction withFIG. 1, in some embodiments, the system100includes parallel decoding application190that configures a group of T threads to each execute a different instance of the decoder kernel192in SIMD fashion, thereby generating a decoding thread group. As shown, in the same or other embodiments, the decoder kernel192resides in the PP memory204.

In operation, the CPU102is the master processor of the system100, controlling and coordinating operations of other system components. In particular, the CPU102issues commands that control the operation of the PPU202. In some embodiments, the CPU102writes a stream of commands for the PPU202to a data structure (not explicitly shown in eitherFIG. 1orFIG. 2) that can be located in the system memory104, the PP memory204, or another storage location accessible to both the CPU102and the PPU202. A pointer to the data structure is written to a pushbuffer to initiate processing of the stream of commands in the data structure. The PPU202reads command streams from the pushbuffer and then executes commands asynchronously relative to the operation of the CPU102. In embodiments where multiple pushbuffers are generated, execution priorities can be specified for each pushbuffer by an application program via a device driver (not shown) to control scheduling of the different pushbuffers.

As also shown, the PPU202includes an I/O unit205that communicates with the rest of system100via the communication path113and the memory bridge105. The I/O unit205generates packets (or other signals) for transmission on the communication path113and also receives all incoming packets (or other signals) from the communication path113, directing the incoming packets to appropriate components of the PPU202. For example, commands related to processing tasks can be directed to a host interface206, while commands related to memory operations (e.g., reading from or writing to the PP memory204) can be directed to a crossbar unit210. The host interface206reads each pushbuffer and transmits the command stream stored in the pushbuffer to a front end212.

In some embodiments, the I/O unit205transmits commands to a copy engine290. In the same or other embodiments, the copy engine290implements any number and/or types of memory operations including, without limitation, any number and/or types of direct memory access operations. In some embodiments, the copy engine can copy data from one memory to another memory and/or move data within memory. In the same or other embodiments, the copy engine290performs any number and/or type of operations that enable any number of components of the PPU202to access the system memory104independently of the CPU102.

As depicted with a dashed box, in some embodiments, the copy engine290includes, without limitation, a parallel decoding unit292. In some other embodiments, the parallel decoding unit292can be implemented in any component of the PPU202or as a stand-alone unit in the PPU202. The parallel decoding unit292can implement any portion (including all) of the functionality of the parallel decoding application190and/or the decoding thread group as described herein in any technically feasible fashion. In some embodiments, the parallel decoding unit292includes, without limitation, one or more fixed-function hardware units that are collectively and/or individually capable of executing any number of hardware threads to efficiently decode encoded sequences in parallel.

As mentioned above in conjunction withFIG. 1, the connection of the PPU202to the rest of system100can be varied. In some embodiments, the parallel processing subsystem112, which includes at least one PPU202, is implemented as an add-in card that can be inserted into an expansion slot of the system100. In some other embodiments, the PPU202can be integrated on a single chip with a bus bridge, such as the memory bridge105or the I/O bridge107. Again, in still other embodiments, some or all of the elements of the PPU202can be included along with the CPU102in a single integrated circuit or system on a chip.

In operation, the front end212transmits processing tasks received from the host interface206to a work distribution unit (not shown) within a task/work unit207. The work distribution unit receives pointers to processing tasks that are encoded as task metadata (“TMD”) and stored in memory. The pointers to TMDs are included in a command stream that is stored as a pushbuffer and received by the front end212from the host interface206. Processing tasks that can be encoded as TMDs include indices associated with the data to be processed as well as state parameters and commands that define how the data is to be processed. For example, the state parameters and commands could define the program to be executed on the data. The task/work unit207receives tasks from the front end212and ensures that general processing clusters (“GPCs”)208are configured to a valid state before the processing task specified by each one of the TMDs is initiated. A priority can be specified for each TMD that is used to schedule the execution of the processing task. Processing tasks also can be received from a processing cluster array230. Optionally, the TMD can include a parameter that controls whether the TMD is added to the head or the tail of a list of processing tasks (or to a list of pointers to the processing tasks), thereby providing another level of control over execution priority.

The PPU202advantageously implements a highly parallel processing architecture based on the processing cluster array230that includes a set of C GPCs208, where C≥1. Each of the GPCs208is capable of executing a large number (e.g., hundreds or thousands) of threads concurrently, where each thread is an instance of a program (e.g., a kernel). In various applications, different GPCs208can be allocated for processing different types of programs or for performing different types of computations. The allocation of the GPCs208can vary depending on the workload arising for each type of program or computation.

Memory interface214includes a set of D partition units215, where D≥1. Each of the partition units215is coupled to one or more dynamic random access memories (“DRAMs”)220residing within the PP memory204. In some embodiments, the number of the partition units215equals the number of the DRAMs220, and each of the partition units215is coupled to a different one of the DRAMs220. In some other embodiments, the number of the partition units215can be different than the number of the DRAMs220. Persons of ordinary skill in the art will appreciate that the DRAM220can be replaced with any other technically suitable storage device. In operation, various render targets, such as texture maps and frame buffers, can be stored across the DRAMs220, allowing the partition units215to write portions of each render target in parallel to efficiently use the available bandwidth of the PP memory204.

A given GPC208can process data to be written to any of the DRAMs220within the PP memory204. The crossbar unit210is configured to route the output of each GPC208to the input of any partition unit215or to any other GPC208for further processing. The GPCs208communicate with the memory interface214via the crossbar unit210to read from or write to any number of the DRAMs220. In one embodiment, the crossbar unit210has a connection to the I/O unit205in addition to a connection to the PP memory204via the memory interface214, thereby enabling the processing cores within the different GPCs208to communicate with the system memory104or other memory not local to the PPU202. In the embodiment ofFIG. 2, the crossbar unit210is directly connected with the I/O unit205. In various embodiments, the crossbar unit210can use virtual channels to separate traffic streams between the GPCs208and the partition units215.

Again, the GPCs208can be programmed to execute processing tasks relating to a wide variety of applications, including, without limitation, linear and nonlinear data transforms, filtering of video and/or audio data, modeling operations (e.g., applying laws of physics to determine position, velocity and other attributes of objects), image rendering operations (e.g., tessellation shader, vertex shader, geometry shader, and/or pixel/fragment shader programs), general compute operations, etc. In operation, the PPU202is configured to transfer data from the system memory104and/or the PP memory204to one or more on-chip memory units, process the data, and write result data back to the system memory104and/or the PP memory204. The result data can then be accessed by other system components, including the CPU102, another PPU202within the parallel processing subsystem112, or another parallel processing subsystem112within the system100.

As noted above, any number of the PPUs202can be included in the parallel processing subsystem112. For example, multiple PPUs202can be provided on a single add-in card, or multiple add-in cards can be connected to the communication path113, or one or more of the PPUs202can be integrated into a bridge chip. The PPUs202in a multi-PPU system can be identical to or different from one another. For example, different PPUs202might have different numbers of processing cores and/or different amounts of the PP memory204. In implementations where multiple PPUs202are present, those PPUs202can be operated in parallel to process data at a higher throughput than is possible with a single PPU202. Systems incorporating one or more PPUs202can be implemented in a variety of configurations and form factors, including, without limitation, desktops, laptops, handheld personal computers or other handheld devices, servers, workstations, game consoles, embedded systems, and the like.

FIG. 3is a block diagram of a GPC208included in the PPU202ofFIG. 2, according to various embodiments. In operation, the GPC208can be configured to execute a large number of software threads in parallel to perform graphics, general processing and/or compute operations. In some embodiments, each software thread executing on the GPC208is an instance of a particular program executing on a particular set of input data. In some embodiments, SIMD instruction issue techniques are used to support parallel execution of a large number of threads without providing multiple independent instruction units. In some other embodiments, SIMT techniques are used to support parallel execution of a large number of generally synchronized threads, using a common instruction unit configured to issue instructions to a set of processing engines within GPC208. Unlike a SIMD execution regime, where all processing engines typically execute identical instructions, SIMT execution allows different threads to more readily follow divergent execution paths through a given program. Persons of ordinary skill in the art will understand that a SIMD processing regime represents a functional subset of a SIMT processing regime.

Operation of the GPC208is controlled via a pipeline manager305that distributes processing tasks received from a work distribution unit (not shown) within the task/work unit207to one or more SMs310. The pipeline manager305can also be configured to control a work distribution crossbar330by specifying destinations for processed data output by the SMs310.

In some embodiments, the GPC208includes, without limitation, a set of M of the SMs310, where M≥1. In the same or other embodiments, each of the SMs310includes, without limitation, a set of functional units (not shown), such as execution units and load-store units. Processing operations specific to any of the functional units can be pipelined, which enables a new instruction to be issued for execution before a previous instruction has completed execution. Any combination of functional units within a given SM310can be provided. In various embodiments, the functional units can be configured to support a variety of different operations including integer and floating point arithmetic (e.g., addition and multiplication), comparison operations, Boolean operations (e.g., AND, OR, XOR), bit-shifting, and computation of various algebraic functions (e.g., planar interpolation and trigonometric, exponential, and logarithmic functions, etc.). Advantageously, the same functional unit can be configured to perform different operations.

In operation, each of the SMs310is configured to process one or more thread groups. In the context of the SM310, a “thread group” or “warp” refers to a group of threads concurrently executing the same program on different input data, with each thread of the group being assigned to a different execution unit within the SM310. A thread group can include fewer threads than the number of execution units within the SM310, in which case some of the execution units can be idle during cycles when that thread group is being processed. A thread group can also include more threads than the number of execution units within the SM310, in which case processing can occur over consecutive clock cycles. Since each of the SMs310can support up to G thread groups concurrently, it follows that up to G*M thread groups can be executing in the GPC208at any given time.

Additionally, a plurality of related thread groups can be active (in different phases of execution) at the same time within an SM310. This collection of thread groups is referred to herein as a “cooperative thread array” (“CTA”) or “thread array.” The size of a particular CTA is equal to m*k, where k is the number of concurrently executing threads in a thread group, which is typically an integer multiple of the number of execution units within the SM310, and m is the number of thread groups simultaneously active within the SM310.

In some embodiments, each of the threads in a given thread group is assigned a unique thread ID that is accessible to the thread during the thread's execution. The thread ID, which can be defined as a one-dimensional or multi-dimensional numerical value controls various aspects of the thread's processing behavior. For instance, a thread ID may be used to determine which portion of the input data set a thread is to process and/or to determine which portion of an output data set a thread is to produce or write.

Although not shown inFIG. 3, each of the SMs310contains a level one (“L1”) cache or uses space in a corresponding L1 cache outside of the SM310to support, among other things, load and store operations performed by the execution units. Each of the SMs310also has access to level two (“L2”) caches (not shown) that are shared among all the GPCs208in the PPU202. In some embodiments, the L2 caches can be used to transfer data between threads. Finally, the SMs310also have access to off-chip “global” memory, which can include the PP memory204and/or the system memory104. It is to be understood that any memory external to the PPU202can be used as global memory. Additionally, as shown inFIG. 3, a level one-point-five (“L1.5”) cache335can be included within the GPC208and configured to receive and hold data requested from memory via the memory interface214by the SM310. Such data can include, without limitation, instructions, uniform data, and constant data. In embodiments having multiple SMs310within the GPC208, the SMs310can beneficially share common instructions and data cached in L1.5 cache335.

Each of the GPCs208can have an associated memory management unit (“MMU”)320that is configured to map virtual addresses into physical addresses. In various embodiments, the MMU320can reside either within the GPC208or within the memory interface214. The MMU320includes a set of page table entries (“PTEs”) used to map a virtual address to a physical address of a tile or memory page and optionally a cache line index. The MMU320can include address translation lookaside buffers (“TLB”) or caches that can reside within the SMs310, within one or more L1 caches, or within the GPC208.

In graphics and compute applications, the GPC208can be configured such that each of the SMs310is coupled to a texture unit315for performing texture mapping operations, such as determining texture sample positions, reading texture data, and filtering texture data.

In operation, each of the SMs310transmits a processed task to the work distribution crossbar330in order to provide the processed task to another GPC208for further processing or to store the processed task in an L2 cache (not shown), the PP memory204, or the system memory104via the crossbar unit210. In addition, a pre-raster operations (“preROP”) unit325is configured to receive data from the SM310, direct data to one or more raster operations (“ROP”) units within the partition units215, perform optimizations for color blending, organize pixel color data, and perform address translations.

It will be appreciated that the core architecture described herein is illustrative and that variations and modifications are possible. Among other things, any number of processing units, such as the SMs310, the texture units315, or the preROP units325, can be included within the GPC208. Further, as described above in conjunction withFIG. 2, the PPU202can include any number of the GPCs208that are configured to be functionally similar to one another so that execution behavior does not depend on which of the GPCs208receives a particular processing task. Further, each of the GPCs208operates independently of the other GPCs208in the PPU202to execute tasks for one or more application programs. In view of the foregoing, persons of ordinary skill in the art will appreciate that the architecture described inFIGS. 1-3in no way limits the scope of the present disclosure.

As shown, in some embodiments, one of the SMs310is configured to process a decoding thread group390. The decoding thread group390is a thread group having the thread group size182of T, where each of the T threads in the thread group is concurrently executing the decoder kernel192on different data. In some embodiments, each thread of the decoding thread group390is assigned to a different execution unit within the SM310. The decoding thread group390can be configured in any technically feasible fashion. As described previously herein in conjunction withFIG. 1, in some embodiments, the parallel decoding application190configures the SM310to process the decoding thread group390. For explanatory purposes only, references to the thread(s) as used below refer to the thread(s) of the decoding thread group390that are active at any given point in time. The decoding thread group390is described in greater detail below in conjunction withFIGS. 4 and 5.

Parallel Decoding Using Shared Input and Output Pointers

FIG. 4is a more detailed illustration of the decoding thread group390ofFIG. 3, according to various embodiments. The decoding thread group390decodes an encoded sequence402to generate a decoded sequence498. As shown, in some embodiments, the decoding thread group390includes, without limitation, threads410(0)-410(T-1), a shared input pointer404, and a shared output pointer406, where T is the thread group size182. For explanatory purposes only, the thread IDs (not shown) of the threads410(0)-410(T-1) are 0-(T-1), respectively.

In some embodiments, including the embodiment depicted inFIG. 4, the encoded sequence402is formatted for data-parallel processing based on the thread group size182that is symbolized as T and the word size184that is symbolized as B. Further, the encoded sequence402is optimized for a data-parallel decoding process in which threads410(0)-410(T) each decode a single code from the encoded sequence402during each decoding iteration.

In some other embodiments, the encoded sequence402can be optimized for a different type of data-parallel processing and/or a different type of data-parallel decoding process, and the techniques described herein are modified accordingly. For instance, in some embodiments, the codes in the encoded sequence402are not packed into the fixed-length words and therefore the shared input pointer404is replaced with T different input pointers that are provided as metadata, where each of the input pointers is associated with a different thread.

The shared input pointer404and the shared output pointer406are shared across the threads410(0)-410(T-1). In some embodiments, at any given point in time, the shared input pointer404points to the next word that is to be read from the encoded sequence402. In the same or other embodiments, at any given point in time, the shared output pointer406points to the location within the memory allocated for the decoded sequence498immediately following the last literal that the decoding thread group390wrote to the decoded sequence498.

The format of the encoded sequence402and the ability of the threads410to communicate enables one of the threads410, referred to herein as “a lead thread,” to deterministically advance the shared input pointer404and the shared output pointer406as the threads410decode the encoded sequence402. The lead thread can be determined in any technically feasible fashion. In some embodiments, the lead thread is the thread410(0) corresponding to the thread ID of zero.

Importantly, the lead thread advances the shared output pointer406in a monotonically increasing fashion from the beginning of the decoded sequence498to the end of the decoded sequence498. In a corresponding fashion, the decoding thread group390incrementally generates the decoded sequence498from beginning to end without gaps. In some embodiments, including the embodiment depicted inFIG. 4, the lead thread also advances the shared input pointer404in a monotonically increasing fashion from the beginning of the encoded sequence402to the end of the encoded sequence402.

Prior to the zeroth iteration, the parallel decoding application190, the decoding thread group390, and/or the lead thread initialize the shared input pointer404and the shared output pointer to point to the initial word in the encoded sequence402and the start of the memory allocated for the decoded sequence498, respectively. The parallel decoding application190, the decoding thread group390, and/or the lead thread can initialize the shared input pointer404and the shared output pointer406in any technically feasible fashion.

As shown, in some embodiments, the threads410(0)-410(T-1) include, without limitation, input buffers420(0)-420(T-1), refill flags430(0)-430(T-1), input offsets440(0)-440(T-1), decodes462(0)-462(T-1), decode sizes464(0)-464(T-1), and output offsets470(0)-470(T-1). For an integer t from 0 to (T-1), the input buffer420(t), the refill flag430(t), the input offset440(t), the decode462(t), the decode size464(t), and the output offset470(t) are associated with the thread410(t) and are also referred to herein collectively as the “thread-specific variables” of the thread410(t). In some embodiments, each of the threads410writes to the thread-specific variables of the thread410and reads from any number of the thread-specific variables of any number of the threads410(including the thread410).

In some embodiments, at any given point in time, the input buffer420(t) stores any number of complete codes and/or any number of partial codes that are assigned to the thread410(t) that the thread410(t) has not yet decoded. As needed, the thread410(t) copies words that are assigned to the thread410(t) from the encoded sequence402to the input buffer420(t). As needed, the thread410(t) reads and removes codes from the input buffer420(t) in a first in, first out fashion. In some embodiments, prior to the zeroth iteration, the parallel decoding application190and/or any number of the threads410initialize the input buffers420to indicate that the input buffers420are empty.

The refill flags430enable the threads410to consume words from the encoded sequence402in a deterministic fashion that ensures that each of the threads410reads the words assigned to the thread410by the entry encoding application180during the encoding process. The input offsets440(0)-440(T-1) are offsets with respect to the shared input pointer404. The sum of the shared input pointer404and the input offset440(t) is a thread-specific input pointer for the thread410(t). As described in greater detail below, in some embodiments, the input offset440(0) is zero and the threads410(1)-440(T-1) determine the input offsets440(1)-440(T-1), respectively, based on the refill flags430.

The decodes462(0)-462(T-1) store the literal(s) represented by the symbol(s) decoded by the threads410(0)-410(T-1), respectively, before the threads410(0)-410(T-1) concurrently write the decodes462(0)-462(T-1), respectively, to the decoded sequence498as a contiguous sequence of literals. In some embodiments, each of the decodes462is either a single literal that is decoded based on a literal code or a string of literals that is decoded based on a copy symbol.

The decode sizes464(0)-464(T-1) specify the size of the decodes462(0)-462(T-1), respectively. The output offsets470(0)-470(T-1) are offsets with respect to the shared output pointer406. The sum of the shared output pointer406and the output offset470(t) is a thread-specific output pointer for the thread410(t). As described in greater detail below, in some embodiments, the output offset470(0) is zero and the threads410(1)-440(T-1) determine the output offsets470(1)-470(T-1), respectively, based on the decode sizes464.

In some embodiments, to initiate a new decoding iteration, the threads410(0)-410(T-1) concurrently determine the refill flags430(0)-430(T-1), respectively based on the input buffers420(0)-420(T-1), respectively. More precisely, the thread410(t) determines the refill flag430(t) based on the input buffer420(t). The thread410(t) can determine the refill flag430(t) based on the input buffer420(t) in any technically feasible fashion. In some embodiments, if the input buffer420(t) does not include at least one complete code, then the thread410(t) sets the refill flag430(t) to 1 to indicate that the input buffer420(t) is drained of complete signals and requires a refill.

In some other embodiments, if the number of valid bits in the input buffer420(t) is below a constant threshold, then the thread410(t) sets the refill flag430(t) to 1. By setting the constant threshold to a value (in valid bits) that is no smaller than the largest possible code size, the thread410(t) can conservatively determine the refill flag430(t) without tracking the occupancy of the input buffer420(t) based on the codes included in the input buffer420(t).

Subsequently, the threads410(1)-410(T-1) concurrently determine the input offsets440(1)-410(T-1) based on the refill flags430. For an integer x from1to (T-1), the thread410(x) sets the input offset440(x) based on the sum of the refill flags430(0)-430(x-1). In some embodiments, the input offsets440are specified in words and the thread410(x) sets the input offset440(x) to the sum of the refill flags430(0)-430(x-1). Accordingly, the value of the input offset440(x) can range from 0 to x, where 0 indicates that none of the input buffers420(0)-420(x-1) require a refill, and x indicates the all of the input buffers420(0)-420(x-1) require refills. The sum of the refill flags430(0)-430(x-1) is also referred to herein as the (x-1)thelement of the prefix sum of the refill flags430. In some other embodiments, the input offsets440are not specified in words and the thread410(x) converts the sum of the refill flags430(0)-430(x-1) to the units of size associated with the input offsets440to determine the input offset440(x).

Subsequently, the threads410for which the refill flag430is one execute read steps450in lock-step. The threads410for which the refill flag430is zero skip the read steps450. To execute the read step450(x), the thread410(x) reads a word from the encoded sequence402based on the sum of the shared input pointer404and the input offset440(x) and then appends the word to the input buffer420(x). Accordingly, the threads410collectively read as few as zero and as many as T contiguous words from the encoded sequence402. Advantageously, the memory accesses of the encoded sequence402during decoding are therefore dense and aligned.

The threads410(0)-410(T-1) then execute decode steps460(0)-460(T-1), respectively. In some embodiments, during the decode step460(t), the thread410(t) reads and removes a single code from the input buffer420(t) in a first in, first out fashion. As described previously herein in conjunction withFIG. 1, because each word can begin and/or end with a partial word, the single code can include bits from multiple words. The thread410(t) decodes the code to determine a literal symbol representing a single literal that the thread410(t) stores as the decode462(t) or a copy symbol representing a string of literals that the thread410(t) stores as the decode462(t). The thread410(t) then sets the decode size464(t) equal to the size of the decode462(t).

The thread410(t) can decode the code in any technically feasible fashion. For instance, in some embodiments, the thread410(t) executes any number and/or types of decoding algorithms that reverse the mapping of symbols to codes used to generate the encoded sequence402. In some embodiments, the code can be a copy code. Advantageously, because the decoding thread group390incrementally generates the decoded sequence498from beginning to end without gaps, each original string of literals back-referenced via the copy code is already stored in the decoded sequence498or is available from one of the threads410having a lower thread ID. The decoding thread group390therefore does not defer the processing of copy codes.

As shown, the threads410(1)-410(T-1) concurrently determine the output offsets470(1)-470(T-1), respectively, based on the decode sizes464. For an integer x from 1 to (T-1), the thread410(x) sets the output offset470(x) equal to the sum of the decode sizes464(0)-464(x-1). Subsequently, the threads410(0)-410(T-1) execute write steps480(0)-480(T-1), respectively, in lock-step. To execute the write step480(x), the thread410(x) copies the decode462(x) to the decoded sequence498starting at the location specified by the sum of the shared output pointer406and the output offset470(x). In this fashion, the threads410collectively writes a contiguous group of literals corresponding to a contiguous group of symbols to the decoded sequence498. Advantageously, the memory accesses of the decoded sequence498during decoding are therefore dense. In some embodiments, each of the symbols is a byte and the memory accesses of the encoded sequence402during decoding are also aligned.

The lead thread then executes a lead thread step490to advance both the shared input pointer404and the shared output pointer406. As shown, in some embodiments, the thread410(0) is the lead thread. In some embodiments, the shared input pointer404is specified in words and the lead thread increments the shared input pointer404by the sum of the refill flags430(0)-430(T-1). In some other embodiments, the shared input pointer404is not specified in words and the lead thread converts the sum of the refill flags430(0)-430(T-1) to the units of size associated with the shared input pointer404to increment the shared input pointer404. The lead thread increments the shared output pointer406by the sum of the decode sizes464(0)-464(T-1).

The decoding thread group390continues to execute decoding iterations until the decoding thread group390has finished generating the decoded sequence498. In some embodiments, the number of codes included in the encoded sequence402is not a multiple of the thread group size182and the decoding thread group390inactivates each of the threads410when the thread410has decoded all of the codes assigned to the thread410.

Note that the techniques described herein are illustrative rather than restrictive and may be altered without departing from the broader spirit and scope of the invention. Many modifications and variations on the functionality provided by the decoding thread group390will be apparent to those of ordinary skill in the art without departing from the scope and spirit of the described embodiments.

FIG. 5is a conceptual illustration of how the decoding thread group390ofFIG. 4generates the decoded sequence498, according to various embodiments. For explanatory purposes only,FIG. 5depicts a beginning portion of an exemplary instance of the encoded sequence402that is associated with the thread group size182of three threads and the word size184of thirty-two bits.FIG. 5also depicts a portion of the decoded sequence498at a point in time after the decoding thread group390executes decoding iterations530(0)-530(3).

As shown, the encoded sequence402includes, without limitation, words510(0)-510(5) and any number of other words510(depicted with ellipses). Each of the words510includes, without limitation, any integer or non-integer number of codes520. Although not shown, the source sequence is represented by symbols598(0)-598(18), and any number of other symbols598((depicted with ellipses). In the embodiment depicted inFIG. 5, and as described previously herein in conjunction withFIG. 1, the entropy encoding application180encodes the symbols598(0)-598(18) to generate codes520(0)-520(18), respectively. In the embodiment depicted inFIG. 5, for an integer x from 0 to 18, the entropy encoding application180assigns the code520(x) to the thread410(x% 3) for decoding during a decoding iteration530(floor(x/3)). And, for each thread410, the entropy encoding application180packs the bits for the codes520that are assigned to the thread410into words510of thirty-two bits to generate the encoded sequence402.

Consequently, as shown, the word510(0) includes, without limitation, the codes520(0),520(3), and520(6). The word510(1) includes, without limitation, the codes520(1) and520(4). The word510(2) includes, without limitation, the codes520(2) and520(5) as well as an initial portion of the code520(8). The word510(3) includes, without limitation, the codes520(7),520(10), and520(13). The word510(4) includes, without limitation, the remaining portion of the code520(8) and the codes520(11) and520(14). The word510(5) includes, without limitation, the codes520(9),520(12),520(15), and520(18).

Each of the codes520is a literal code or a copy code. Each of the literal codes is annotated with a single integer that specifies the index of a literal502within the source sequence that is represented by a symbol598corresponding to the literal code. Each of the copy codes is annotated with an integer range that specifies the indices of a string of literals502within the source sequence that is represented by the symbol598corresponding to the copy code. For explanatory purposes only, numbering with respect to the source sequence is zero-based. Accordingly, the literal502(0) corresponds to the initial one of the literals502included in the source sequence, the literal502(1) corresponds to next of the literals502included in the source sequence, and so forth.

For instance, the code520(0) is a literal code that is annotated with 0 to indicate that the code520(0) corresponds to the literal502(0) represented by the symbol598(0). The code520(6) is a copy code that is annotated with 6-7 to indicate that the code520(6) corresponds to a copy to a string of literals502(6)-502(7), where the copy is represented by the symbol598(6). And the code520(18) is a literal code that is annotated with 23 to indicate that the code520(18) corresponds to the literal502(23) represented by the symbol598(18).

For explanatory purposes only, the thread410(0) and the words510(0) and510(5) that are decoded by the thread410(0) are depicted via lightly shaded boxes, the thread410(1) and the words510(1) and510(3) that are decoded by the thread410(1) are depicted via darkly shaded boxes, and the thread410(2) and the words510(2) and510(4) that are decoded by the thread410(2) are depicted via moderately shaded boxes. Furthermore, circles annotated with numbers specifying the decoding iterations530are superimposed on arrows to indicate the words510that the decoding thread group390reads from the encoded sequence402, the symbols598that the decoding thread group390determines during decoding, and the literals502that the decoding thread group390writes to the decoded sequence498during each of the decoding iterations530(0)-530(3).

As shown, during the decoding iteration530(0), the threads410(0)-410(2) read the words510(0)-510(2), respectively, from the encoded sequence402. The threads410(0)-410(2) decode the codes520(0)-520(2), respectively, to determine symbols598(0)-598(2), respectively. The threads410(0)-410(2) then write literals502(0)-502(2), respectively, represented by the symbols598(0)-598(2), respectively, to the decoded sequence498.

During the decoding iteration530(1), none of the threads410(0)-410(2) read from the encoded sequence402. The threads410(0)-410(2) decode the codes520(3)-520(5), respectively, to determine symbols598(3)-598(5), respectively. The threads410(0)-410(2) then write literals502(3)-502(5), respectively, represented by the symbols598(3)-598(5), respectively, to the decoded sequence498.

During the decoding iteration530(2), since the word510(1) stores two of the codes520, and the word510(2) stores two and a half of the codes520, the threads410(1) and410(2) read the words510(3) and510(4), respectively, from the encoded sequence402. By contrast, because the word510(0) stores three of the codes520, the thread410(0) does not read from the encoded sequence402during the decoding iteration530(2).

The thread410(0) decodes the code520(6) that is a copy code to determine symbol598(6) representing a copy. More specifically, and for explanatory purposes only, the symbol598(6) represents a copy of a string of literals502(2)-502(3). Accordingly, the thread410(0) writes a string of literals502(6)-502(7) that is a copy of the string of literals502(2)-502(3) to the decoded sequence.

The threads410(1) and410(2) decode the codes520(7) and520(8), respectively, to determine symbols598(7)-598(8), respectively. The threads410(1) and410(2) then write literals502(8)-502(9), respectively, represented by the symbols598(7)-598(8), respectively, to the decoded sequence498.

During the decoding iteration530(3), the thread410(0) reads the word510(5) from the encoded sequence402, but neither the thread410(1) nor the thread410(2) read from the encoded sequence402. The threads410(0)-410(2) decode the codes520(9)-520(11), respectively, to generate symbols598(9)-598(11), respectively. The threads410(0)-410(2) then write literals502(10)-502(12), respectively, represented by the symbols598(9)-598(11), respectively, to the decoded sequence498.

Advantageously, asFIG. 5illustrates graphically, the memory accesses to both the encoded sequence402and the decoded sequence498are dense and aligned. Furthermore, because the decoding thread group390incrementally generates the decoded sequence498from beginning to end, the decoding thread group390does not need to defer the processing of copy codes.

FIG. 6is a flow diagram of method steps for encoded sequences that include variable-length codes, according to various embodiments. Although the method steps are described with reference to the systems ofFIGS. 1-5, persons skilled in the art will understand that any system configured to implement the method steps, in any order, falls within the scope of the present invention.

As shown, a method600begins at step602, where, the parallel decoding application190configures the decoding thread group390to decode the encoded sequence402. At step604, the decoding thread group390sets the shared input pointer404to point to the start of the encoded sequence402, sets the shared output pointer406to point to the start of the memory allocated for the decoded output, and each of the threads410initialize the input buffer420of the thread410to empty. At step606, each of the threads410determine the refill flag430of the thread410based on the input buffer420of the thread410.

At step608, each of the threads410for which the refill flag430is one sets the input offset440of the thread410equal to the sum of the refill flags430of the threads410having lower thread IDs. At step610, each of the threads410for which the refill flag430is one reads the word510from the location in the encoded sequence402corresponding to the sum of the shared input pointer404and the input offset440of the thread410and appends the word510to the input buffer420of the thread410.

At step612, each of threads410decodes the next one of the codes520in the input buffer420of the thread410to determine the decode462of the thread410, removes the code520from the input buffer420, and sets the decode size464of the thread410equal to the size of the decode462of the thread410. At step614, each of the threads410sets the output offset470of the thread410equal to the sum of the decode sizes464of the threads410having lower thread IDs. At step616, each of the threads410writes the decode462of the thread410to the location in the decoded sequence498corresponding to the sum of the shared output pointer406and the output offset470of the thread410.

At step618, the lead thread (e.g., the thread410(0)) advances the shared input pointer404by the sum of the refill flags430and advances the shared output pointer406by the sum of the decode sizes464. At step620, the decoding thread group390deactivates any of the threads410that have finished decoding the codes520assigned to the thread410. At step622, the decoding thread group390determines whether any of the threads410are active. If, at step622, the decoding thread group390determines that none of the threads410are active, then the method600terminates.

If, however, at step622, the decoding thread group390determines that at least one of the threads410is active, then the method600returns to the step606, where the threads410determine the refill flags430of the threads. The decoding thread group390continues to cycle through steps606-622until, at step622, the decoding thread group390determines that none of the threads410are active. The method600then terminates.

In sum, the disclosed techniques can be used to efficiently decode an encoded sequence via a thread group of software or hardware threads to generate a decoded sequence in increments of contiguous groups of symbols from beginning to end without gaps. In some embodiments, an entropy encoding application generates the encoded sequence based on a thread group size denoted as T and a word size denoted as B. The entropy encoding application maps symbols representing literals included in the source sequence to a sequence of codes. The entropy encoding application repeatedly assigns contiguous groups of T codes to T thread IDs from 0 to T-1. Accordingly, the entropy encoding application assigns the xthcode with respect to the source sequence to the thread corresponding to the thread ID of x % T for decoding during the floor(x/T) decoding iteration. For each thread ID, the entropy encoding application packs the bits for the assigned codes into words that each have B bits. To generate the encoded sequence, the entropy encoding application arranges the words based on a primary criterion of increasing decoding iteration and a secondary criterion of increasing thread ID.

In some embodiments, a parallel decoding application decodes the encoded sequence to generate a decoded output. The parallel decoding application configures a group of T threads to each execute a different instance of a decoder kernel, thereby generating a decoding thread group. A lead thread included in the decoding thread group sets a shared input pointer to point to the start of the encoded sequence and a shared output pointer to point to the beginning of memory allocated for the decoded output. Each thread initializes an input buffer of the thread to indicate that the input buffer is empty. The threads then execute decoding iterations until the decoding thread group finishes decoding the encoded sequence.

During each decoding iteration, each thread sets a refill flag of the thread to zero if at least one complete code remains in the input buffer of the thread and sets the refill flag of the thread to one otherwise. Each thread having a refill flag of one sets the input offset of the thread equal to the sum of the refill flags of the threads having lower thread IDs. Each thread having a refill flag of one reads the word at the location within the encoded sequence that corresponds to the sum of the shared input pointer and the input offset of the thread and appends the word to the input buffer of the thread. Importantly, threads having refill flags of zero do not read from the encoded sequence during the decoding iteration.

Each thread extracts the first remaining code from the input buffer of the thread and decodes the code to determine the decode of the thread. The threads can decode the codes using any number and/or types of decoding algorithms. Each thread sets the decode size of the thread equal to the size of the decode. Each thread sets the output offset of the thread equal to the sum of the decode sizes of the threads having lower thread IDs. Subsequently, each thread writes the decode of the thread to the decoded output starting at the location corresponding to the sum of the shared output pointer and the output offset of the thread. To finish the decoding iteration, the lead increments the shared input pointer by the sum of the refill flags and increments the shared output pointer by the sum of the decode sizes.

At least one technical advantage of the disclosed techniques relative to the prior art is that, with the disclosed techniques, decoding thread groups do not require metadata to efficiently decode encoded sequences that include variable-length codes in parallel. More specifically, the format the entropy encoding application institutes by systematically rearranging the codes relative to the corresponding symbols enables the threads in the decoding thread group to deterministically access groups of codes for parallel decoding without any additional information. And, unlike prior art techniques, because the threads read any number (including zero) of contiguous words from the encoded sequence and append a group of contiguous literals to the decoded sequence during each decoding iteration, the decoding throughput is not reduced by sparse memory accesses. Furthermore, because the decoding thread group incrementally generates the decoded output from beginning to end without gaps, literals referenced by each copy symbol are available when the decoding thread group decodes the corresponding copy code. Consequently, relative to prior-art techniques that store copy codes for deferred processing, the decoding thread group can more efficiently decode copy codes. These technical advantages provide one or more technological improvements over prior art approaches.