Patent Description:
Compression leads to serial dependencies between the commands or operations used to compress different chunks of data. For example, a first, most recent command compresses a data chunk using a pointer to a second, previous data chunk (plus a modification of the second data chunk in some cases), which was compressed by a second, previous command that represented the second data chunk as a pointer to a third, earlier data chunk (plus a corresponding modification of the third data chunk in some cases), and so on. Multiple chains of serial dependency are interleaved in some command streams. For example, there may be series of (highly compressible) identical commands to copy a prior value (e.g., a DWord, a short word, or a byte) to the output. The series could be matched to a prior pattern of values, which is then used to replicate the pattern to generate the output. However, since the source of the current command in the stream is the result of a prior command in the stream, the identified pattern of commands needs to be executed serially. Execution of the commands is further complicated if the replicated command adds a value (such as one) to generate the next output, e.g., to generate an incrementing series of values.

Operations that are performed by a stream of commands, such as the commands used to implement decompression, are combined to generate a single command that operates within a predetermined address range such as a <NUM> byte window corresponding to a cache line. Commands that are received at a front end of a pipeline are stored in a buffer. As each new command arrives at the front end, the new command is compared to commands that were previously received at the front end and stored in the buffer. If the new command matches one of the previously received commands, the new command and the matching previous command are combined into an aggregate command that is stored in the buffer for eventual dispatch to a back end of the pipeline. In some embodiments, a comparison of the new command with the matching command includes comparing write addresses or read addresses of the new and matching commands, as well as determining whether the write and read addresses are within the same address range such as the <NUM> byte window. The aggregate command is stored in the buffer for comparison with subsequently received commands. The buffer can include multiple different aggregate commands such as aggregate commands associated with interleaved chains of serially dependent commands. In some embodiments, combining the new and matching commands includes defining a mask that is applied to the data in the address range associated with the new and matching commands to identify addresses that are operated on by the aggregate command. For example, if the command stream includes a first command that operates on data at a first offset from a current address and a second command that operates on data at a second offset from a current address, the aggregate command includes a mask that is defined based on the first and second offsets.

<FIG> is a block diagram of a processing system <NUM> that includes a graphics processing unit (GPU) <NUM> for creating visual images intended for output to a display <NUM> according to some embodiments. The GPU <NUM> executes instructions stored in a memory <NUM>. Some embodiments of the memory <NUM> are implemented as a dynamic random access memory (DRAM). However, the memory <NUM> can also be implemented using other types of memory including static random access memory (SRAM), nonvolatile RAM, and the like. In the illustrated embodiment, the GPU <NUM> communicates with the memory <NUM> over a bus <NUM>. However, some embodiments of the GPU <NUM> communicate with the memory <NUM> over a direct connection or via other buses, bridges, switches, routers, and the like. The GPU <NUM> can store information in the memory <NUM> such as the results of the executed instructions. For example, the memory <NUM> can store a copy <NUM> of instructions from a program code that is to be executed by the GPU <NUM>. Some embodiments of the GPU <NUM> include multiple processor cores, compute units, or fixed function circuitry (not shown in the interest of clarity) that independently execute instructions concurrently or in parallel.

The processing system <NUM> includes a central processing unit (CPU) <NUM> for executing instructions. Some embodiments of the CPU <NUM> include multiple processor cores (not shown in the interest of clarity) that independently execute instructions concurrently or in parallel. The CPU <NUM> is also connected to the bus <NUM> and can therefore communicate with the GPU <NUM> and the memory <NUM> via the bus <NUM>. The CPU <NUM> can execute instructions such as program code <NUM> stored in the memory <NUM> and the CPU <NUM> can store information in the memory <NUM> such as the results of the executed instructions. The CPU <NUM> is also able to initiate graphics processing by issuing draw calls to the GPU <NUM>. The GPU <NUM> renders the object to produce values of pixels that are provided to the display <NUM>, which uses the pixel values to display an image that represents the rendered object.

An input/output (I/O) engine <NUM> handles input or output operations associated with the display <NUM>, as well as other elements of the processing system <NUM> such as keyboards, mice, printers, external disks, and the like. The I/O engine <NUM> is coupled to the bus <NUM> so that the I/O engine <NUM> communicates with the GPU <NUM>, the memory <NUM>, or the CPU <NUM>. In the illustrated embodiment, the I/O engine <NUM> reads information stored on an external storage medium <NUM>, such as a compact disk (CD), a digital video disc (DVD), and the like. The external storage medium <NUM> stores information representative of program code used to implement an application such as a video game. The program code on the external storage medium <NUM> is written to the memory <NUM> to form the copy <NUM> of instructions or the program code <NUM> that are to be executed by the GPU <NUM> or the CPU <NUM>, respectively.

The processing system <NUM> also includes a processor <NUM> for performing encryption, decryption, compression, decompression, and other functions used to provide security for information conveyed within the processing system <NUM>, received by the processing system <NUM> from an external entity, or transmitted by the processing system <NUM> to an external entity. Some embodiments of the processor <NUM> decompress data streams that include literal data, pointers indicating a relative location of data, and commands that are applied to compress or decompress the data. The processor <NUM> can also include circuitry that combines operations used to decompress the received data, as discussed below.

In the illustrated embodiment, direct memory access (DMA) logic <NUM> provides access to the memory <NUM>, although some entities access the memory <NUM> directly. The DMA logic <NUM> generates addresses and initiates memory read or write cycles. For example, the GPU <NUM>, the CPU <NUM>, the I/O engine <NUM>, and the processor <NUM> read information from the memory <NUM> and write information to the memory <NUM> via the DMA logic <NUM>. In some embodiments, the processor <NUM> and the DMA logic <NUM> are implemented as a single entity. Some embodiments of the DMA logic <NUM> are used for memory-to-memory data transfer or transferring data between the compute units in the GPU <NUM> or processor cores in the CPU <NUM>. The GPU <NUM> or the CPU <NUM> can perform other operations concurrently with the data transfers being performed by the DMA logic <NUM>, which may provide an interrupt to the GPU <NUM> or the CPU <NUM> to indicate that the transfer is complete.

<FIG> is a block diagram of a decoder <NUM> that is used to decode and decompress information transmitted within or between processing systems according to some embodiments. The decoder <NUM> is implemented in some embodiments of the processing system <NUM> shown in <FIG>. For example, the decoder <NUM> can be implemented in the processor <NUM> or in other entities within the processing system <NUM>. The decoder <NUM> is partitioned into a front end <NUM>, a middle end <NUM>, and a back end <NUM>. The decoder <NUM> includes (or is associated with) a cache <NUM>. Cache lines <NUM> (only one indicated by a reference numeral in the interest of clarity) in the cache <NUM> store compressed data received by the decoder <NUM> and decompressed data produced by executing commands from the bitstream. The cache lines <NUM> have a predetermined length such as <NUM> bytes. In some embodiments, the cache <NUM> is implemented as a buffer and ranges of the cache lines <NUM> are windows into portions of a memory such as an external DRAM or shared SRAM. The buffer does not include tags of the cache lines <NUM>.

The front end <NUM> receives a compressed bitstream that includes literal data that is stored in the memory location indicated by a physical address, pointers that indicate locations of data relative to a current address, and commands that include one or more source addresses of data that are input to the command, a target address of data that is written by the command, and (in some cases) modifications to the input data such as adding, appending, or concatenating a zero to the input data. The front end <NUM> decodes the commands received in the compressed bitstream. In some embodiments, the front end <NUM> decodes the commands based on a Huffman table that is defined using information that preceded the commands in the compressed bitstream. The front end <NUM> provides the decoded commands to the middle end <NUM>.

The middle end <NUM> includes a set of symbol arrays <NUM> that stores symbols received from the front end <NUM>, including the decoded commands. The middle end <NUM> also includes a command assembler <NUM> that generates information that represents the commands. In some embodiments, the command assembler <NUM> provides commands that include a literal length that indicates a number of bytes of literal data that are copied and conditionally added to previously received data, a match length that indicates a number of bytes that are copied from the previously received data, and a match offset that indicates an offset to the previously received data from the end of the offset of the literal data.

An operation (op) combiner <NUM> receives the command information from the command assembler <NUM>. Some embodiments of the op combiner <NUM> are implemented as a flow-through pipeline that is pipelined as deep as needed to satisfy timing requirements, except for a last serialization cycle that pulls out a single back end command from a collapsed array of byte commands. The op combiner <NUM> includes a buffer <NUM> that stores commands received from the command assembler <NUM> and aggregate commands generated by the op combiner <NUM>. The op combiner <NUM> aggregates commands received from the command assembler <NUM> that are associated with the same cache line <NUM>. Some embodiments of the op combiner <NUM> receive a command that includes one or more source (or read) addresses for data read by the received command. The command also includes a destination (or write) address for data that is written by the first command. In some cases, the read and write addresses indicate the beginning of a cache line <NUM> and the command includes offsets that indicates a location for reading or writing data within the cache line <NUM>. The op combiner <NUM> compares the read and write addresses received from the command assembler <NUM> with read and write addresses of commands stored in the buffer <NUM>. A match occurs if the read and write addresses indicate the same cache line <NUM>, e.g., the read and write addresses in the received command and the buffered command are the same. The op combiner <NUM> combines the received command with the buffered command in response to a match between the read and write addresses.

The op combiner <NUM> attempts to collapse as many command packets into as few aggregate commands as possible. The aggregate commands are then provided to the back end <NUM>. Reducing the number of aggregate commands provided to the back end <NUM> optimizes the throughput of the back end <NUM> and, consequently, optimizes the throughput of external memory interfaces. The back end <NUM> examines read addresses in the commands (which include the aggregate commands generated by the op combiner <NUM>) and issues fetch commands as needed. The back end <NUM> also pops, aligns, and expands literal data in the bitstream.

<FIG> is a block diagram of a command <NUM> according to some embodiments. The command <NUM> is received by a decoder that includes an op combiner such as the op combiner <NUM> shown in <FIG>. The command <NUM> operates on data that is stored in one or more cache lines and writes the results of the operation to another cache line, which may or may not be different than the cache lines including the input data. In the illustrated embodiment, the decoder concurrently processes information associated with two cache lines, e.g., so that the decoder can decode commands that use input data that is not aligned with cache line boundaries and therefore straddles the cache lines. The two cache lines are associated with different banks.

The command <NUM> therefore includes addresses <NUM>, <NUM> that indicate the read cache lines <NUM>, <NUM>, respectively. Although the read addresses <NUM>, <NUM> indicate the start addresses of different cache lines <NUM>, <NUM>, some embodiments of the command <NUM> include read addresses <NUM>, <NUM> that indicate the same cache line. The command <NUM> can also include a single read address that indicates either of the cache lines <NUM>, <NUM>. The command <NUM> also includes an address <NUM> that indicates a write cache line <NUM>. Data generated by an operation represented by the command <NUM> is written to a location in the write cache line <NUM>.

Offsets indicate the location of the data in the cache lines <NUM>, <NUM>, <NUM>. The offsets are included in the command <NUM>. For example, the command <NUM> includes information indicating the offset <NUM> from the beginning of the cache line <NUM> to the location of the input data in the cache line <NUM>. For another example, the command <NUM> includes information indicating the offset <NUM> from the beginning of the cache line <NUM> to the location of the input data in the cache line <NUM>. For yet another example, the command <NUM> includes information indicating the offset <NUM> from the beginning of the cache line <NUM> to the location that is written by the command <NUM>. In some embodiments, the portion of the data that is read from the locations in the cache line <NUM>, <NUM> indicated by the addresses <NUM>, <NUM> and the offset <NUM>, <NUM>, respectively, is represented by a mask. Combining the command <NUM> with another command therefore includes merging the masks for the two commands.

<FIG> is a block diagram of a merger <NUM> of masks that represent portions of a cache line <NUM> that are input to different commands according to some embodiments. The merger <NUM> is performed by some embodiments of the op combiner <NUM> shown in <FIG>, e.g., when combining commands to form an aggregate command. The cache line <NUM> is partitioned into portions <NUM> (only one indicated by a reference numeral in the interest of clarity) that represent data such as compressed data from a compressed bitstream. The size of the portions <NUM> is arbitrary and different portions have different sizes in some cases, e.g., one subset of the portions <NUM> can have a size of three bytes and another subset of the portions <NUM> can have a size of one byte.

Masks <NUM>, <NUM> are generated for corresponding commands. In some embodiments, the masks <NUM>, <NUM> are generated based on read addresses and corresponding offsets in the commands that indicate locations of the portions <NUM> that are read by the corresponding commands. The commands also include information indicating sizes of the portions <NUM>. In the illustrated embodiment, the mask <NUM> indicates that the first command reads data from the locations <NUM>, <NUM> in the cache line <NUM>. The mask <NUM> indicates that the second command reads data from the locations <NUM>, <NUM> in the cache line <NUM>. Although the masks <NUM>, <NUM> indicate locations <NUM>, <NUM>, <NUM>, <NUM>, respectively, masks generated for other commands can indicate a single location, locations within multiple cache lines, and the like.

The masks <NUM>, <NUM> are merged to form an aggregate mask <NUM> that is used by a corresponding aggregate command. In the illustrated embodiment, the aggregate mask <NUM> indicates the locations <NUM>, <NUM>, <NUM>, <NUM> that are accessed as inputs to the aggregate command. Using the aggregate mask <NUM> allows the aggregate command to access the locations <NUM>, <NUM>, <NUM>, <NUM> concurrently.

<FIG> is a block diagram of a first portion <NUM> of an op combiner according to some embodiments. The first portion <NUM> is used to implement some embodiments of the op combiner <NUM> shown in <FIG>. The first portion <NUM> includes address assignment circuitry <NUM> that receives a set <NUM> of commands from a front end such as the front end <NUM> shown in <FIG>. In some embodiments, the set <NUM> is received from a command assembler that provides an output address that is represented by a literal length, a match length, and a match offset, as discussed above. The output address is reset as part of each new set <NUM> of commands. Incrementing circuitry <NUM>, <NUM>, <NUM>, <NUM> increments the output addresses of the commands with each new literal and match. The address assignment circuitry <NUM> stores a copy of a current address <NUM> that is being processed by the op combiner. Output from the incrementing circuitry <NUM>-<NUM> is a write address, a literal read address, and a match read address. In some cases, the absolute addresses are subsequently used by the op combiner to compare how the commands align to memory or cache lines of the operation pipeline.

Some embodiments of the address assignment circuitry <NUM> implement the following pseudocode to generate output addresses and update the current address:
<IMG>
<IMG>.

The pseudocode is chained across the set <NUM> of commands, which potentially generates eight subcommands.

Flatten circuitry <NUM> translates literals and matches into a common command that reads and adds literals. The input command packets received from the address assignment circuitry <NUM> generates up to two commands. Clamp circuitry <NUM>, <NUM>, <NUM>, <NUM> clamps the match length of each of the commands received from the address assignment circuitry <NUM>. In some embodiments, each input command is translated into one command clamped to a write; two consecutive read lines are also generated. The resulting valid subcommands are pushed from the clamp circuitry <NUM>-<NUM> into a buffer such as an N*<NUM> (<NUM>) write + N (<NUM>) read first-in-first-out (FIFO) buffer. Thus, if there is a series of matches without literals or literals without matches, they can be collapsed into a single aggregate command. Selection circuitry <NUM> chooses the next valid N(<NUM>) from the same lines. In some embodiments, output from the selection circuitry <NUM> includes N(<NUM>) instances of:.

Alignment circuitry <NUM> calculates lines needed for reading and writing. The alignment circuitry <NUM> also unrolls commands that need to write to more than one cache line. In some embodiments, a cache line is an aligned <NUM> byte address relative to the beginning of the current chunk of data. Reads are executed in one read operation if the writes are limited to one line because two consecutive reads can be performed per write line. As discussed above, the input commands are translated into one command clamped to the write and two consecutive read lines are generated. Commands that are completed and sent on our popped from a buffer (such as the FIFO buffer) in the flatten circuitry <NUM>. Subsequent commands are rotated and pulled in to fill out the next commands in the buffer.

Start/end circuitry <NUM> in the alignment circuitry <NUM> is used to calculate the starting and ending lines for the reads and writes based on the read and write addresses received from the flatten circuitry <NUM>. Unrolling circuitry <NUM> is used to unroll write line transitions and provide the unrolled write lines, read lines, and repeat/rotate information to pick circuitry <NUM>, which chooses the next valid N(<NUM>) from the same lines. In some embodiments, the pick circuitry <NUM> performs an operation that includes picking up to the next N (<NUM>) commands that share the same write and read lines as the first one. For example, the pick circuitry <NUM> operates in a manner similar to the flatten step as a N write + N read FIFO with a filter on the output that only sends the commands with the same read and write lines. Commands that have an unused read bank can be sent with ones that do use the read bank. The output of the pick circuitry <NUM> is:.

Some embodiments of the alignment circuitry <NUM> implement the following pseudocode:
<IMG>
<IMG>.

The output ReadLines can come from different commands as long as two commands don't have differing valid read lines on the same bank.

<FIG> is a block diagram of a second portion <NUM> of an op combiner according to some embodiments. The second portion <NUM> is used to implement some embodiments of the op combiner <NUM> shown in <FIG>. The second portion <NUM> includes byte blast and collect circuitry <NUM> that receives input commands <NUM> from alignment circuitry such as the alignment circuitry <NUM> shown in <FIG>. In the illustrated embodiment, the byte blast and collect circuitry <NUM> receives four input commands <NUM> and the circuitry <NUM> converts the Read {Address, Length} and {Write Address, Num Literals} for the input commands <NUM> into per byte multiplexer controls. The WriteAddress[<NUM>:<NUM>] and WriteLength for each of the input commands <NUM> is converted into a byte mask such as the masks <NUM>, <NUM> shown in <FIG>. For each command whose read and write lines match the read and write lines of the first command, a valid byte is selected. The valid bytes do not overlap.

Some embodiments of the byte blast and collect circuitry <NUM> compute the following for the input commands <NUM>:.

Some embodiments of the byte blast and collect circuitry <NUM> implement the following pseudocode:
<IMG>
<IMG>
<IMG>.

Some embodiments of the second portion implement N (<NUM>) instances of the byte blast and collect circuitry <NUM>. The instances operate on different commands command and remove the filter that detects incompatible read and write lines between commands in the outputs of the alignment block <NUM> shown in <FIG>. This approach has the advantage of performing the byte blast and collect operations more rapidly but can lead to congestion in subsequent operations in the portion <NUM> of the op combiner.

Combine circuitry <NUM> stores a predetermined number of previously collected commands that have incompatible write or read lines, e.g., read and write lines that do not match. The combine circuitry <NUM> combines or aggregates subsequently received commands that are compatible with (e.g., match) one of the stored commands. When a new command is presented, the combine circuitry <NUM> can merge valid read lines with invalid read lines. The combine circuitry <NUM> also merges commands with matching read and write lines by selecting the valid byte data from all compatible commands. If the combine circuitry <NUM> receives a command with incompatible lines, the oldest combined command is pushed out and previously received commands are pushed down to make room for the new command. The (potentially aggregate or combined) commands that are pushed out are provided to a back end such as the back end <NUM> shown in <FIG>.

Some embodiments of the combine circuitry <NUM> store two previously collected commands having read or write addresses that do not match, e.g., incompatible commands. The previous commands are stored in a first combined slot <NUM> and a second combined slot <NUM>. Newly received commands are stored in the first combined slot <NUM> and the oldest combined command is stored in the second combined slot <NUM>. Since there are two combiners <NUM>, <NUM>, which may have the same write lines but different read lines, the combine circuitry <NUM> allows subsequently received commands to jump ahead of a previous command in the second combined slot <NUM> by combining with the command in the first combined slot <NUM>. The combine circuitry <NUM> checks to determine if jumping ahead would violate a read-after-write coherency hazard using the following pseudocode:
<IMG>.

The jump ahead is not permitted if a read-after-write coherency hazard is detected.

Dependencies within the combined or aggregated commands are resolved using resolution circuitry <NUM>. A command that is pushed out of the combine circuitry <NUM> is received by the resolution circuitry <NUM>, which attempts to resolve any read-after-write dependencies in the aggregate command, e.g., using instances of byte-can-go circuitry <NUM>. If the resolution circuitry <NUM> is unable to resolve the dependencies, bytes before the dependency are sent out as a separate command and then the resolution circuitry <NUM> attempts to resolve the dependencies in the remaining bytes. Some embodiments of the resolution circuitry <NUM> implement the following pseudocode:
<IMG>
<IMG>.

In the above pseudocode, the first ByteCanGo[] that is False invalidates prior bytes from consideration by latter bytes with the result being that each false ByteCanGo breaks the command into multiple commands from the <NUM> byte source. Note that there may be many circular dependencies within one command that can be resolved, so potentially many of these may need to be instantiated and pipelined in series to accomplish the goal.

<FIG> is a flow diagram of a method <NUM> of combining matching commands into an aggregate command according to some embodiments. The method <NUM> is implemented in some embodiments of the op combiner <NUM> shown in <FIG> and the op combiner illustrated in <FIG> and <FIG>.

At block <NUM>, the op combiner receives one or more commands, e.g., from a command assembler such as the command assembler <NUM> shown in <FIG>. The received command includes one or more read addresses that indicate locations of source data for the command. The received command also includes a write address that indicates a location of destination data produced by the command. In some embodiments, the read and write addresses indicate locations in cache lines such as <NUM> byte cache lines.

At block <NUM>, the op combiner compares the read and write addresses in the received command to read and write addresses in a buffered command that was previously received by the op combiner. The buffered command can be a newly received (e.g., uncombined or unaggregated) command or an aggregate command that was generated by combining two or more previously received commands.

At decision block <NUM>, the op combiner determines whether the read and write addresses in the received command match the read and write addresses in the buffered command. In some embodiments, a command includes up to two read addresses that refer to two cache lines stored in different banks. Depending on the number of read addresses in the command, the op combiner compares one or two read addresses in the received and buffered commands. If the read and write addresses match, the method <NUM> flows to block <NUM>. If the read and write addresses do not match, the method <NUM> flows to decision block <NUM>.

At block <NUM>, the op combiner combines the received and buffered commands. In some embodiments, combining the received and buffered commands includes merging masks associated with the received and buffered commands such as the masks <NUM>, <NUM> shown in <FIG>. The method <NUM> then flows to block <NUM>.

At decision block <NUM>, the op combiner determines whether there are more buffered commands that can be compared with the received command. If there are additional buffered commands, the method <NUM> flows back to block <NUM>. If there are no additional buffered commands, the method <NUM> flows to block <NUM>.

At block <NUM>, the command is added to the buffer. The command that is added to the buffer is the received command if the read or write addresses in the received command did not match the read and write addresses in any buffered commands. The command that is added to the buffer is a combined or aggregated command if the read or write addresses in the received command match the read and write addresses in one of the buffered commands.

A computer readable storage medium may include any non-transitory storage medium, or combination of non-transitory storage media, accessible by a computer system during use to provide instructions and/or data to the computer system.

The software includes one or more sets of executable instructions stored or otherwise tangibly embodied on a non-transitory computer readable storage medium.

Claim 1:
A method comprising:
receiving a command stream including a first command including at least one first read address for data read by the first command and a first write address for data that is written by the first command, wherein the command stream is received (<NUM>) from a front end (<NUM>) buffer that decoded the first command from a compressed bitstream;
comparing the at least one first read address and the first write address to at least one second read address and a second write address of a second command stored in a buffer;
storing the first command in the buffer in response to the at least one first read address not matching the at least one second read address or the first write address not matching the second write address
removing the first command from the buffer in response to the at least one first read address matching the at least one read second address;
combining the first and second commands to form a first aggregate command in response to the at least one first read address matching the at least one second read address and the first write address matching the second write address, the first aggregate command comprising:
a read address corresponding to the at least one first read address and the at least one second read address; and
a write address corresponding to the first write address and the second write address;
storing the first aggregate command in the buffer in response to the at least one first read address matching the at least one second read address; and
providing the first aggregate command, including both the read address and the write address, to a back end (<NUM>) for execution.