JP7561125B2 - Aggregation of commands in a stream based on cache line address - Google Patents

Description

Compression is used to reduce the number of bytes that represent a piece of information, such as to reduce the amount of bandwidth required to send the information over an interface. A typical compression technique uses backward references to represent a current chunk of data as a pointer to a previous chunk of data (or data at another spatial or temporal location) plus information indicating the change to the previous chunk of data. For example, three bytes of data at a first address can be compressed by representing the three bytes of data at the second address as a pointer to a second address offset by one kilobyte (kB) from the first address plus information indicating the change, such as adding one to the three bytes of data at the second address. The data is reconstructed at the destination by copying the previously received data (e.g., the three bytes of data at the second address) and performing the indicated change, such as adding one.

The present disclosure can be better understood, and its numerous features and advantages made apparent to those skilled in the art, by reference to the accompanying drawings. The use of the same reference numbers in different drawings indicates similar or identical elements.

FIG. 1 is a block diagram of a processing system including a graphics processing unit (GPU) for generating visual images intended for output to a display, according to some embodiments. FIG. 2 is a block diagram of a decoder used to decode and decompress information transmitted within or between processing systems according to some embodiments. FIG. 2 is a block diagram of commands according to some embodiments. FIG. 2 is a block diagram of a merger of masks representing portions of a cache line input to different commands, according to some embodiments. FIG. 2 is a block diagram of a first portion of an op combiner according to some embodiments. FIG. 2 is a block diagram of a second portion of an op combiner according to some embodiments. FIG. 4 is a flow diagram of a method for combining matching commands into an aggregate command according to some embodiments.

Compression creates serial dependencies between commands or operations used to compress different chunks of data. For example, a first recent command compresses a chunk of data using a pointer to a second previous chunk of data (possibly with a modification of the second chunk of data), which is compressed by a second previous command that represents the second chunk of data as a pointer to a third, earlier chunk of data (possibly with a corresponding modification of the third chunk of data). Multiple chains of serial dependencies are interleaved in some command streams. For example, there may be a sequence of the same (highly compressible) command to copy previous values (e.g., DWords, short words, or bytes) to the output. This sequence can be matched to a pattern of previous values and used to replicate that pattern to generate the output. However, since the source of the current command in the stream is the result of a previous command in the stream, the identified pattern of commands must be executed serially. Command execution becomes more complicated when the replicated command adds a value (e.g., 1) to generate the next output (e.g., to generate a sequence of incrementing values).

The operations performed by a stream of commands, such as those used to perform decompression, are combined to generate a single command that operates within a predefined address range, such as a 32-byte window corresponding to a cache line. Commands received at the front end of the pipeline are stored in a buffer. As each new command arrives at the front end, the new command is compared to commands previously received at the front end and stored in the buffer. If the new command matches any previously received commands, the new command and the matching previous command are combined into an aggregate command stored in the buffer for eventual dispatch to the back end of the pipeline. In some embodiments, comparing the new command to the matching command includes comparing the write or read addresses of the new command and the matching command and determining whether the write and read addresses are within the same address range, such as a 32-byte window. The aggregate command is stored in a buffer for comparison to subsequently received commands. The buffer can contain multiple different aggregate commands, such as aggregate commands associated with an interleaved chain of serial dependent commands. In some embodiments, combining the new command and the matching command includes defining a mask that is applied to data within an address range associated with the new command and the matching command to identify addresses 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 the current address and a second command that operates on data at a second offset from the current address, the aggregate command includes a mask that is defined based on the first offset and the second offset.

FIG. 1 is a block diagram of a processing system 100 including a graphics processing unit (GPU) 105 for generating visual images intended for output to a display 110, according to some embodiments. The GPU 105 executes instructions stored in a memory 115. Some embodiments of the memory 115 are implemented as dynamic random access memory (DRAM). However, the memory 115 may also be implemented using other types of memory, including static random access memory (SRAM), non-volatile RAM, and the like. In the illustrated embodiment, the GPU 105 communicates with the memory 115 via a bus 120. However, some embodiments of the GPU 105 communicate with the memory 115 via a direct connection or via other buses, bridges, switches, routers, and the like. The GPU 105 may store information in the memory 115, such as results of executed instructions. For example, the memory 115 may store copies 125 of instructions from a program code executed by the GPU 105. Some embodiments of GPU 105 include multiple processor cores, computational units, or fixed function circuits (not shown for clarity) that independently execute instructions simultaneously or in parallel.

The processing system 100 includes a central processing unit (CPU) 130 for executing instructions. Some embodiments of the CPU 130 include multiple processor cores (not shown for clarity) that independently execute instructions, either simultaneously or in parallel. The CPU 130 is also connected to a bus 120 and can communicate with the GPU 105 and memory 115 via the bus 120. The CPU 130 can execute instructions, such as program code 135 stored in the memory 115, and the CPU 130 can store information, such as results of executed instructions, in the memory 115. The CPU 130 can also initiate graphics operations by issuing draw calls to the GPU 105. The GPU 105 renders objects to generate pixel values that are provided to the display 110, which uses the pixel values to display an image representing the rendered objects.

The input/output (I/O) engine 140 processes input or output operations associated with the display 110 or other elements of the processing system 100, such as a keyboard, mouse, printer, or external disk. The I/O engine 140 is coupled to the bus 120 such that the I/O engine 140 communicates with the GPU 105, memory 115, or CPU 130. In the illustrated embodiment, the I/O engine 140 reads information stored on an external storage medium 145, such as a compact disc (CD) or digital video disc (DVD). The external storage medium 145 stores information representing program code used to execute an application, such as a video game. The program code on the external storage medium 145 is written to the memory 115 to form a copy 125 of the instructions or program code 135 that are executed by the GPU 105 or CPU 130.

Processing system 100 also includes processor 150 for performing encryption, decryption, compression, decompression, and other functions (used to provide security for information being communicated within processing system 100, received by processing system 100 from an external entity, or transmitted by processing system 100 to an external entity). Some embodiments of processor 150 decompress data streams that include literal data, pointers indicating the relative location of the data, and commands to be applied to compress or decompress the data. Processor 150 may also include circuitry to combine the operations used to decompress received data, as described below.

In the illustrated embodiment, some entities directly access memory 115, but direct memory access (DMA) logic 155 provides access to memory 115. DMA logic 155 generates addresses and initiates memory read or write cycles. For example, GPU 105, CPU 105, I/O engine 140, and processor 150 read information from memory 115 and write information to memory 115 via DMA logic 155. In some embodiments, processor 150 and DMA logic 155 are implemented as a single entity. Some embodiments of DMA logic 155 are used to transfer data between memories, or between computational units in GPU 105 or processor cores in CPU 130. GPU 105 or CPU 130 may perform other operations simultaneously with the data transfer being performed by DMA logic 155, and DMA logic 155 may provide an interrupt to GPU 105 or CPU 130 to indicate that the transfer is complete.

2 is a block diagram of a decoder 200 used to decode and decompress information transmitted within or between processing systems, according to some embodiments. The decoder 200 is implemented in some embodiments of the processing system 100 shown in FIG. 1. For example, the decoder 200 can be implemented in the processor 150 or other entity within the processing system 100. The decoder 200 is divided into a front end 205, a middle end 210, and a back end 215. The decoder 200 includes (or is associated with) a cache 220. Cache lines 225 (only labeled for clarity) within the cache 220 store compressed data received by the decoder 200 and decompressed data generated by executing commands from the bitstream. The cache lines 225 have a predefined length, such as 32 bytes. In some embodiments, the cache 220 is implemented as a buffer, and the extent of the cache lines 225 is a window into a portion of memory, such as an external DRAM or a shared SRAM. The buffer does not include the tags of the cache lines 225.

The front end 205 receives the compressed bitstream. The compressed bitstream includes literal data stored at a memory location indicated by a physical address, a pointer indicating the location of the data relative to the current address, one or more source addresses of data input to the command, a target address of data to be written by the command, and (possibly) a command including modifications to the input data, such as adding zeros to the input data, appending, concatenating, etc. The front end 205 decodes the commands received in the compressed bitstream. In some embodiments, the front end 205 uses information preceding the command in the compressed bitstream to decode the command based on a defined Huffman table. The front end 205 provides the decoded commands to the middle end 210.

The middle end 210 includes a set of symbol arrays 230 that store symbols received from the front end 205, including the decoded command. The middle end 210 also includes a command assembler 235 that generates information representing the command. In some embodiments, the command assembler 235 provides a command that includes a literal length indicating the number of bytes of literal data to be copied and conditionally added to the previously received data, a match length indicating the number of bytes copied from the previously received data, and a match offset indicating the offset from the end of the literal data offset to the previously received data.

The operation (op) combiner 240 receives command information from the command assembler 235. Some embodiments of the op combiner 240 are implemented as a flow-through pipeline that is pipelined as deeply as necessary to meet timing requirements, except for the final serialization cycle that extracts a single back-end command from the array of collapsed byte commands. The op combiner 240 includes a buffer 245 that stores the commands received from the command assembler 235 and the aggregated command generated by the op combiner 240. The op combiner 240 aggregates the commands received from the command assembler 235 that are associated with the same cache line 225. Some embodiments of the op combiner 240 receive a command that includes one or more source (or read) addresses of data read by the received command. The command also includes a destination (or write) address of data written by the first command. In some cases, the read and write addresses indicate the start of a cache line 225, and the command includes an offset that indicates a location within the cache line 225 to read or write data from. The op combiner 240 compares the read and write addresses received from the command assembler 235 with the read and write addresses of commands stored in the buffer 245. A match occurs if the read and write addresses indicate the same cache line 225, such as when the read and write addresses of the received and buffered commands are identical. The op combiner 240 combines the received command with the buffered command in response to a match between the read and write addresses.

The op combiner 240 attempts to aggregate as many command packets as possible into as few aggregate commands as possible. The aggregate commands are then provided to the backend 215. Reducing the number of aggregate commands provided to the backend 215 optimizes the throughput of the backend 215 and, consequently, the throughput of the external memory interface. The backend 215 examines the read addresses of the commands (including the aggregate commands generated by the op combiner 240) and issues fetch commands as necessary. The backend 215 also pops, aligns, and expands literal data in the bitstream.

3 is a block diagram of a command 300, according to some embodiments. The command 300 is received by a decoder that includes an op combiner, such as op combiner 240 shown in FIG. 2. The command 300 operates on data stored in one or more cache lines and writes the results of the operation to another cache line, which may be the cache line containing the input data or may be different. In the illustrated embodiment, the decoder processes information related to two cache lines simultaneously, so that, for example, the decoder can decode a command that uses input data that is not aligned with a cache line boundary and therefore spans a cache line. The two cache lines are associated with different banks.

Thus, command 300 includes addresses 305 and 310 that point to read cache lines 315 and 320, respectively. Although read addresses 305 and 310 point to starting addresses of different cache lines 315 and 320, some embodiments of command 300 include read addresses 305 and 310 that point to the same cache line. Command 300 may also include a single read address that points to either cache line 315 or 320. Command 300 also includes address 325 that points to write cache line 330. Data produced by the operation represented by command 300 is written to the location of write cache line 330.

The offset indicates the location of the data within cache lines 315, 320, and 330. The offset is included in command 300. For example, command 300 includes information indicating offset 335 from the beginning of cache line 315 to the location of the input data within cache line 315. In another example, command 300 includes information indicating offset 340 from the beginning of cache line 320 to the location of the input data within cache line 320. In yet another example, command 300 includes information indicating offset 345 from the beginning of cache line 330 to the location written by command 300. In some embodiments, the portion of the data to be read from the locations within cache lines 315 and 320 indicated by addresses 305 and 310 and offsets 335 and 340, respectively, is represented by a mask. Thus, combining command 300 with another command includes merging the masks of the two commands.

4 is a block diagram of a merger 400 of masks representing portions of a cache line 405 input to different commands, according to some embodiments. The merger 400 is performed by some embodiments of the op combiner 240 shown in FIG. 2, such as when combining commands to form an aggregate command. The cache line 405 is divided into portions 410 (only portions shown by numbers for clarity) representing data, such as compressed data from a compressed bitstream. The portions 410 may be of any size, and different portions may have different sizes. For example, one subset of the portions 410 may have a size of 3 bytes, and another subset of the portions 410 may have a size of 1 byte.

Masks 415, 420 are generated for the corresponding commands. In some embodiments, masks 415, 420 are generated based on a read address and corresponding offset in the command that indicates the location of portion 410 to be read by the corresponding command. The command also includes information indicating the size of portion 410. In the illustrated embodiment, mask 415 indicates that a first command reads data from locations 425, 430 of cache line 405. Mask 420 indicates that a second command reads data from locations 435, 440 of cache line 405. Although masks 415, 420 each indicate locations 425, 430, 435, 440, masks generated for other commands may indicate a single location, locations within multiple cache lines, etc.

Masks 415 and 420 are merged to form aggregate mask 445 that is used by the corresponding aggregate command. In the illustrated embodiment, aggregate mask 445 indicates locations 425, 430, 435, and 440 that are accessed as inputs to the aggregate command. By using aggregate mask 445, the aggregate command can simultaneously access locations 425, 430, 435, and 440.

5 is a block diagram of a first portion 500 of an op combiner according to some embodiments. The first portion 500 is used to implement some embodiments of the op combiner 240 shown in FIG. 2. The first portion 500 includes an address allocation circuit 505 that receives a set of commands 510 from a front end, such as the front end 205 shown in FIG. 2. In some embodiments, the set 510 is received from a command assembler that provides an output address represented by a literal length, a match length, and a match offset, as described above. The output address is reset as part of each new set of commands 510. Increment circuits 511, 512, 513, and 514 increment the output addresses of the commands with their respective new literals and matches. The address allocation circuit 505 stores a copy of the current address 515 being processed by the op combiner. The outputs from the increment circuits 511-514 are the write address, the literal read address, and the match read address. In some cases, the absolute address is later used by the op combiner to compare how the command aligns to memory or cache lines in the computation pipeline.

Some embodiments of the address assignment circuit 505 implement the following pseudocode to generate the output address and update the current address:
LiteralWriteAddress = currentAddress
SubLiteralOffset = previousMatchOffset
if (hasSubliterals)
SubLiteralAddress = currentAddress - SubLiteralOffset
MatchWriteAddress = currentAddress + LiteralLength
matchWrapsAtWriteStart = MatchLength > MatchOffset
if (matchWrapsAtWriteStart)
MatchRead = MatchOffset
else:
MatchRead = MatchLength
MatchAddress = currentAddress + LiteralLength - MatchOffset
currentAddress += LiteralLength + MatchLength
The pseudocode is chained across a set of commands 510, potentially generating eight sub-commands.

Flatten circuitry 520 converts the literals and matches into a common command to read and add a literal. An input command packet received from address allocation circuitry 505 generates up to two commands. Clamp circuits 521, 522, 523, and 524 clamp the match length of each of the commands received from address allocation circuitry 505. In some embodiments, each input command is converted into one command clamped to a write. Also, two consecutive read lines are generated. The resulting valid sub-commands are pushed from clamp circuits 521-524 into a buffer, such as an Nx2(8) write + N(4) read first-in-first-out (FIFO) buffer. Thus, if there is a match without a literal or a series of literals without a match, these can be combined into a single aggregate command. Selection circuitry 525 selects the next valid N(4) from the same line. In some embodiments, the output from selection circuitry 525 includes the following N(4) instances:
- ReadAddress
- ReadLength: The match can be shorter than the WriteLength. The read is repeated to fill the output.
- HasLiterals: if true, the subcommand has as many literals as the output write length.
- WriteAddress
- WriteLength

The alignment circuit 530 calculates the lines required for the read and write. The alignment circuit 530 also unrolls commands that need to be written to multiple cache lines. In some embodiments, a cache line is a 32-byte address aligned to the beginning of the current chunk of data. Since two consecutive reads can be performed per write line, if the write is limited to one line, the read is performed in one read operation. As described above, the input command is converted to one command clamped to the write, generating two consecutive read lines. The completed command to be sent is popped from the flattening circuit 520 buffer (e.g., FIFO buffer). Subsequent commands are rotated and pulled in to fill out the next command in the buffer.

A start/end circuit 535 of the alignment circuit 530 is used to calculate the start row and end line for the read and write based on the read and write addresses received from the flattening circuit 520. An unrolling circuitry 540 is used to unroll the write line transitions and provide the unrolled write line, read line and repeat/rotation information to a pick circuit 545 that selects the next valid N(4) from the same line. In some embodiments, the pick circuit 545 performs operations including picking up the next up to N(4) commands that share the same write and read lines as the first line. For example, the pick circuit 545 operates similarly to the flattening step as an N write + N read FIFO with a filter on its output that only sends commands with the same read row and write line. Commands with unused read banks can be sent along with commands that use that read bank. The output of the pick circuit 545 is as follows:
- WriteLine: 32-byte aligned address relative to the beginning of the chunk. - WriteLength: Covers to the end of the line, unwraps when it is crossed.
- WriteStart[4:0]: write address in line. - ReadLine[2 Banks]: two not necessarily consecutive 32B read lines. - Bank 0 has an even number of lines.
- Bank 1 has odd lines.
- ReadStart[5:0]: ReadAddress[5:0]
- ReadLength [5:0]: defines where the iteration starts in case of short reads, or nothing in case of long reads.
- RepeatRotate[6:0]: For long copies that need to read their own output and repeat the source data

Some embodiments of the alignment circuit 530 implement the following pseudocode:
#Calculate and limit the operation to the line
{oWriteLine, writeStart[4:0]} = iWriteAddress
writeEnd = min(writeStart + iWriteLength, 32)
length = writeEnd - writeStart
oWriteLength = length

#Calculate read control
readEnd = iReadAddress + iReadLength - 1
firstReadLine = iReadAddress[:5]
lastReadLine = readEnd[:5]
repeatFitsInOneRead = (lastReadLine - firstReadLine) < 2
if (repeatFitsInOneRead or firstCycleOfCommand)
repeatRotate = 0

#Calculate the readout line
if (repeatFitsInOneRead):
oReadLine[firstReadLine[0]] = firstReadLine
oReadLine[lastReadLine[0]] = lastReadLine
else # Walk the read data and start a new read if necessary
readBank = iReadAddress[5]
oReadLine[readBank] = iReadAddress[:5]
readLine2 = (iReadAddress + length - 1)[:5]
readBank2 = readLine2[5]
oReadLine[readBank2] = readLine2

#Detect and proceed
NextWriteAddress = iWriteAddress + length
NextWriteLength = iWriteLength - length
if(repeatFitsInOneRead):
oNextRepeatRotate = (repeatRotate + length) % iReadLength
else:
oNextReadAddress += length

oHasMore = (NextWriteLength > 0)

The output ReadLines can come from different commands as long as the two commands do not have different valid read lines in the same bank.

6 is a block diagram of a second portion 600 of an op combiner according to some embodiments. The second portion 600 is used to implement some embodiments of the op combiner 240 shown in FIG. 2. The second portion 600 includes a byte blast and collect circuit 605 that receives input commands 610 from an alignment circuit, such as the alignment circuit 530 shown in FIG. 5. In the illustrated embodiment, the byte blast and collect circuit 605 receives four input commands 610, and the circuit 605 converts the read {Address, Length} and {Write Address, Num Literals} for the input commands 610 into byte-by-byte multiplexer controls. The WriteAddress[4:0] and WriteLength of each of the input commands 610 are converted into a byte mask, such as masks 415, 420 shown in FIG. 4. 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 are non-overlapping.

Some embodiments of the byte blast and collect circuit 605 calculate the following for the input command 610:
- Output for each byte [0...31]:
o ReadSelect: Which byte of the read line is 0 to 63. The "odd" byte on the MSB.
○ ReadEnable: Whether a read needs to be added ○ LiteralSelect: Which literal in this batch of write lines
■ For each write line, the number ranges from 0 to the sum of (NumLiterals of all commands with the same write line) minus 1.
○ WriteEnable: Whether this byte is enabled ○ LiteralEnable: Whether a literal needs to be added - Collected output for each command:
NumLiterals: The number of literals to pop off.
■ Zero if the next command shares the same write line.
■ If the write line is completed, the total number of literals in the write line. ○ WriteLine: 32-byte aligned address relative to the beginning of the chunk. ○ ReadLine[bank = 0…1]
○ ReadLineEnable [1:0]: Whether a read is required

Some embodiments of the byte blast and collect circuit 605 implement the following pseudocode:
if (newWriteLine)
consumedLiterals = 0

#Calculate the first literal ID
firstLiterals[0] = consumedLiterals
numLiterals[-1] = 0
for command in [0..3]
numLiterals[command] = iHasLiterals[command] ? iWriteLength[command] : 0
totalLiterals[command] = numLiterals[command-1] + numLiterals[command]
firstLiterals[command] = totalLiterals[command-1] + consumedLiterals

for each command with matching lines
writeEnables[31:0] = (~(0xFFFFFFFF << iWriteLength)) << iWriteStart
literalCount

for b in 0 to 31
#Choose the right input command
command = WriteEnables[0..3][b] # is a one hot mux control.
writeStart[4:0] = iWriteStart[command]
numLiterals[5:0] = iWriteLength[command]
oLiteralEnable = iHasLiterals[command]
firstLiteral = firstLiterals[command]
readLength = iReadLength[command]
repeatRotate = iReadRotate[command]
readStart = iReadStart[command]

byteInCommand = b - writeStart

oLiteralSelect[b][4:0] = oLiteralEnable ? byteInCommand+firstLiteral: 31

oReadEnable = readLength > 0
readOffset = (byteInCommand + repeatRotate) % readLength
oReadSelect[b][5:0] = (readStart + readOffset)
oWriteEnable[b] = writeEnables[0..3] [b]!= 0

isLastOfWriteLine = oWriteEnable[31]
totalConsumedLiterals = totalLiterals[LastOne(iCommandValids[0..3]] +
consumedLiterals
oNumLiterals = isLastOfWriteLine ? totalConsumedLiterals : 0
nextConsumedLiterals = totalConsumedLiterals

Some embodiments of the second portion implement N(4) instances of byte blast and collect circuitry 605, which operate on different commands and eliminate filters that detect incompatible read and write lines between commands at the output of alignment block 530 shown in FIG. 5. This approach has the advantage of performing byte blast and collect operations more quickly, but may result in congestion in subsequent operations in op combiner portion 600.

The combiner circuit 615 stores a number of previously collected commands that have incompatible write or read lines (e.g., mismatched read and write lines, etc.). The combiner circuit 615 combines or aggregates any subsequently received commands that are compatible (e.g., match) with one of the stored commands. When a new command is presented, the combiner circuit 615 can merge valid read lines with invalid read lines. The combiner circuit 615 also merges the command with matching read and write lines by selecting valid byte data from all compatible commands. When the combiner circuit 615 receives a command with incompatible lines, the oldest combined command is pushed out and the previously received command is pushed down to create space for the new command. The pushed out (potentially aggregated or combined) command is provided to a backend, such as backend 215 shown in FIG. 2.

Some embodiments of the combine circuit 615 store two previously collected commands that have mismatched read or write addresses, such as incompatible commands. The previous commands are stored in a first combined slot 620 and a second combined slot 625. The newly received command is stored in the first combined slot 620 and the oldest combined command is stored in the second combined slot 625. Because there are two combiners 620, 625 that may have the same write line but different read lines, the combine circuit 615 allows the later received command to jump ahead of the previous command in the second combined slot 625 by combining it with the command in the first combined slot 620. The combine circuit 615 checks to determine if jumping ahead would violate a read-after-write coherency hazard using the following pseudocode:
#Detect and suppress moving ahead of an existing line.
cantCombineToSlot1 = False
for i in 0..1
if(iReadLine[i] == Combined[0].WriteLine):
cantCombineToSlot1 = True
If a read-after-write coherency hazard is detected, jumping ahead is not permitted.

Dependencies in the combined or aggregated command are resolved using a resolution circuit 630. Commands pushed out from the combine circuit 615 are received by the resolution circuit 630, which attempts to resolve read-after-write dependencies in the aggregated command, for example, using an instance of a byte-can-go circuit 635. If the resolution circuit 630 is unable to resolve a dependency, the byte before the dependency is sent out as a separate command, and the resolution circuit 630 then attempts to resolve the dependency for the remaining bytes. Some embodiments of the resolution circuit 630 implement the following pseudocode:
for byte in 0..31
if (iWriteEnable[byte])
readBank = iReadSelect[byte][5]
readLine = iReadLines[readBank]
readOverlapsWriteLine = iWriteLine == readLine
if (readOverlapsWriteLine)
readByte = iReadSelect[byte][4:0]
if (iWriteEnable[readByte])
readIsCopying = !iLiteralEnable[readByte] &&
iReadEnable[readByte]
writeIsAdding = iLiteralEnable[byte] &&
iReadEnable[byte]
writeIsCopying = !iLiteralEnable[byte] &&
iReadEnable[byte]
#If the hazard is just a match without a literal,
#Just copy the original read + literal instead
if(writeIsCopying):
ReadSelect[byte] = ReadSelect[readByte]
LiteralSelect[byte] = LiteralSelect[readByte]
#If the hazard is a read + literal with a read without a literal
#Use original read instead
else if(writeIsAdding && readIsCopying)
ReadSelect[byte] = ReadSelect[readByte]
#Otherwise you cannot combine appends
#There is a read on write hazard
else
ByteCanGo[byte] = False
#Wait until everything is expanded before popping the literal.
oNumLiterals = 0
In the pseudocode above, the first ByteCanGO[] that is False invalidates earlier bytes from consideration by later bytes, so that each false ByteCanGo splits the command from a 32-byte source into multiple commands. Note that there may be many resolvable circular dependencies within a command, so it may be necessary to instantiate many of these and pipeline them in order to achieve the goal.

Figure 7 is a flow diagram of a method 700 for combining matching commands into an aggregate command, according to some embodiments. The method 700 is implemented in some embodiments of the op combiner 240 shown in Figure 2, as well as the op combiners shown in Figures 5 and 6.

At block 705, the op combiner receives one or more commands from a command assembler, such as command assembler 235 shown in FIG. 2. The received command includes one or more read addresses indicating the location of source data for the command. The received command also includes a write address indicating the location of destination data generated by the command. In some embodiments, the read and write addresses indicate locations within a cache line, such as a 32-byte cache line.

At block 710, the op combiner compares the read and write addresses of the received command with the read and write addresses of commands previously received and buffered by the op combiner. The buffered commands may be newly received (e.g., uncombined or unaggregated) commands or aggregated commands created by combining two or more previously received commands.

At decision block 715, the op combiner determines whether the read and write addresses of the received command match the read and write addresses of the buffered command. In some embodiments, the command includes up to two read addresses that reference 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 of the received command and the buffered command. If the read and write addresses match, method 700 proceeds to block 720. If the read and write addresses do not match, method 700 proceeds to decision block 725.

At block 720, the op combiner combines the received command and the buffered command. In some embodiments, combining the received command and the buffered command includes merging masks associated with the received command and the buffered command, such as masks 415 and 420 shown in FIG. 4. The method 700 then proceeds to block 730.

In decision block 725, the op combiner determines whether there are more buffered commands that can be compared to the received command. If there are additional buffered commands, the method 700 returns to block 710. If there are no additional buffered commands, the method proceeds to block 730.

At block 730, the command is added to the buffer. If the read or write address of the received command does not match the read and write addresses of any buffered command, the command added to the buffer is the received command. If the read or write address of the received command matches the read and write addresses of any buffered command, the command added to the buffer is a combined or aggregated command.

As disclosed herein, the method includes receiving a command stream including a first command including at least one first read address of data to be read by the first command and a first write address of data to be written by the first command, comparing the at least one first read address and the first write address with at least one second read address and second write address of a second command stored in a buffer, and combining the first command and the second command 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. In one aspect, receiving the first command includes storing the first command in a 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. In another aspect, the method includes storing a first aggregated command in a buffer in response to the at least one first read address matching the at least one second read address, and deleting the first command from the buffer in response to the at least one first address matching the at least one second address.

In one aspect, the at least one first read address, the at least one second read address, the first write address, and the second write address indicate a cache line having a predetermined length. In another aspect, the method includes identifying at least one first portion of the cache line read by the first command based on at least one first offset indicated in the first command, and identifying at least one second portion of the cache line read by the second command based on at least one second offset indicated in the second command. In yet another aspect, the method includes combining the first command and the second command to generate an aggregate command includes generating a mask indicative of the at least one first portion and the at least one second portion. In yet another aspect, the method includes receiving a command stream including a third command including at least one third read address of data to be read by the third command and a third write address of data to be written by the third command; comparing the at least one third read address and the third write address to at least one fourth read address and fourth write address of a fourth command stored in the buffer; and, in response to the at least one third read address matching the at least one fourth read address and the third write address matching the fourth write address, combining the third command and the fourth command to form a second aggregate command.

In another aspect, the first command and the second command are interleaved with the third command and the fourth command in the command stream. In yet another aspect, the method includes determining whether a dependency exists between the first command and the second command, and combining the first command and the second command includes selectively combining the first command and the second command based on whether the dependency exists.

As disclosed herein, the apparatus includes a buffer configured to store a first command including at least one first read address of data to be read by the first command and a first write address of data to be written by the first command, and an operational combiner configured to compare the at least one first read address and the first write address with at least one second read address and second write address of a second command stored in the buffer, the operational combiner configured to combine the first command and the second command 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. In one aspect, the buffer is configured to store the first aggregate command in response to the at least one first read address matching the at least one second read address, and the first command is deleted from the buffer in response to the at least one first address matching the at least one second address. In another aspect, the at least one first read address, the at least one second read address, the first write address, and the second write address indicate a cache line having a predetermined length.

In one aspect, the operational combiner is configured to identify at least one first portion of the cache line read by the first command based on at least one first offset indicated in the first command, and to identify at least one second portion of the cache line read by the second command based on at least one second offset indicated in the second command. In another aspect, the operational combiner is configured to generate a mask indicative of the at least one first portion and the at least one second portion. In yet another aspect, the buffer is configured to store a third command including at least one third read address of data to be read by the third command and a third write address of data to be written by the third command, the work combiner is configured to compare the at least one third read address and the third write address with at least one fourth read address and fourth write address of a fourth command stored in the buffer, and the operation combiner is configured to combine the third command and the fourth command to form a second aggregate command in response to the at least one third read address matching the at least one fourth read address and the third write address matching the fourth write address.

In one aspect, the buffer is configured to store the second aggregate command. In another aspect, the first command and the second command are interleaved with the third command and the fourth command. In yet another aspect, the operational combiner is configured to determine whether a dependency exists between the first command and the second command, and the operational combiner is configured to selectively combine the first command and the second command based on whether a dependency exists.

As disclosed herein, the method includes comparing a first read address and a write address of a first command in a stream of commands used to compress data to a second read address and a write address of a second command in the stream, and selectively combining the first command and the second command to form an aggregate command based on whether the first read command and the write command indicate a cache line and the second read address and the write address indicate the same cache line. In one aspect, the stream of commands is used to compress graphics data generated by a graphics processing unit.

A computer-readable storage medium includes any non-transitory storage medium or combination of non-transitory storage media that can be accessed by a computer system during use to provide instructions and/or data to the computer system. Such storage media may include, but are not limited to, optical media (e.g., compact discs (CDs), digital versatile discs (DVDs), Blu-ray discs), magnetic media (e.g., floppy disks, magnetic tape, magnetic hard drives), volatile memory (e.g., random access memory (RAM) or cache), non-volatile memory (e.g., read-only memory (ROM) or flash memory), or microelectromechanical systems (MEMS)-based storage media. The computer-readable storage medium (e.g., system RAM or ROM) may be built into the computing system, the computer-readable storage medium (e.g., a magnetic hard drive) may be fixedly attached to the computing system, the computer-readable storage medium (e.g., an optical disk or a Universal Serial Bus (USB)-based flash memory) may be removably attached to the computing system, or the computer-readable storage medium (e.g., network-accessible storage (NAS)) may be coupled to the computer system via a wired or wireless network.

In some embodiments, some aspects of the above techniques may be implemented by one or more processors of a processing system executing software. The software includes one or more sets of executable instructions stored in or tangibly embodied on a non-transitory computer-readable storage medium. The software may include instructions and specific data that, when executed by one or more processors, operate the one or more processors to perform one or more aspects of the above techniques. The non-transitory computer-readable storage medium may include, for example, a magnetic or optical disk storage device, a solid-state storage device such as a flash memory, a cache, a random access memory (RAM), or one or more other non-volatile memory devices. The executable instructions stored on the non-transitory computer-readable storage medium may be source code, assembly language code, object code, or other instruction formats that can be interpreted or executed by one or more processors.

In addition to the above, it should be noted that not all activities or elements described in the general description are required, some of the particular activities or devices may not be required, one or more additional activities may be performed, and one or more additional elements may be included. Moreover, the order in which the activities are listed is not necessarily the order in which they are performed. Also, the concepts have been described with reference to specific embodiments. However, those skilled in the art will recognize that various modifications and variations can be made without departing from the scope of the invention as set forth in the claims. Accordingly, the specification and drawings should be considered in an illustrative and not a restrictive sense, and all such modifications are intended to be included within the scope of the invention.

Benefits, other advantages, and solutions to problems have been described above with respect to specific embodiments. However, the benefits, advantages, solutions to problems, and features by which any benefit, advantage, or solution may occur or be manifested are not to be construed as critical, essential, or essential features of any or all claims. Moreover, the specific embodiments described above are illustrative only, since the disclosed invention may be modified and practiced in different but similar manners apparent to those skilled in the art having the benefit of the teachings herein. No limitations are intended to the details of construction or design shown herein other than as described in the appended claims. It is therefore apparent that the specific embodiments described above may be altered or modified, and all such variations are considered to be within the scope of the disclosed invention. Accordingly, the protection sought herein is set forth in the appended claims.

Claims (16)

1. A method comprising:
receiving a command stream including a first command including at least a first read address of data to be read by the first command and a first write address of data to be written by the first command;
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;
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, combining the first command and the second command to form a first aggregate command for subsequent execution , the first aggregate command including a read address corresponding to the first read address and the second read address, and a write address corresponding to the first write address and the second write address, the write address being distinct from the read addresses;
providing the read address and the write address of the first aggregated command to a backend for execution.
method. receiving the first command includes 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.
2. The method of claim 1. 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 removing the first command from the buffer in response to the at least one first read address matching the at least one second read address.
The method of claim 2. the at least one first read address, the at least one second read address, the first write address, and the second write address indicate a cache line having a predetermined length;
identifying at least one first portion of the cache line to be read by the first command based on at least one first offset indicated in the first command;
and identifying at least one second portion of the cache line to be read by the second command based on at least one second offset indicated in the second command.
2. The method of claim 1. Combining the first command and the second command to generate the first aggregate command includes generating a mask indicative of the at least one first portion and the at least one second portion.
The method of claim 4. receiving the command stream including a third command including at least a third read address of data to be read by the third command and a third write address of data to be written by the third command;
comparing the at least one third read address and the third write address to at least one fourth read address and a fourth write address of a fourth command stored in a buffer;
and in response to the at least one third read address matching the at least one fourth read address and the third write address matching the fourth write address, combining the third command and the fourth command to form a second aggregate command.
2. The method of claim 1. the first command and the second command are interleaved with the third command and the fourth command in the command stream.
The method of claim 6. determining whether a dependency exists between the first command and the second command;
combining the first command and the second command includes selectively combining the first command and the second command based on whether the dependency relationship exists.
2. The method of claim 1. An apparatus comprising:
a buffer configured to store a first command including at least a first read address of data to be read by the first command and a first write address of data to be written by the first command;
an operational combiner configured to compare the at least one first read address and the first write address with at least one second read address and a second write address of a second command stored in the buffer;
The operational combiner comprises:
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, combining the first command and the second command to form a first aggregate command for subsequent execution , the first aggregate command including a read address corresponding to the first read address and the second read address, and a write address corresponding to the first write address and the second write address, the write address being distinct from the read addresses;
providing the read address and the write address of the first aggregate command to a backend for execution;
4. The method of claim 3,
Device. the buffer is configured to store the first aggregate command in response to the at least one first read address matching the at least one second read address;
the first command is removed from the buffer in response to the at least one first read address matching the at least one second read address.
10. The apparatus of claim 9. the at least one first read address, the at least one second read address, the first write address, and the second write address indicate a cache line having a predetermined length;
The operational combiner comprises:
identifying at least one first portion of the cache line to be read by the first command based on at least one first offset indicated in the first command;
and identifying at least one second portion of the cache line to be read by the second command based on at least one second offset indicated in the second command.
10. The apparatus of claim 9. the operational combiner is configured to generate a mask indicative of the at least one first portion and the at least one second portion.
12. The apparatus of claim 11. the buffer is configured to store the third command including at least one third read address of data to be read by the third command and a third write address of data to be written by the third command;
the operational combiner is configured to compare the at least one third read address and the third write address to at least one fourth read address and a fourth write address of a fourth command stored in a buffer;
the operational combiner is configured to combine the third command and the fourth command to form a second aggregate command in response to the at least one third read address matching the at least one fourth read address and the third write address matching the fourth write address.
10. The apparatus of claim 9. the buffer is configured to store the second aggregate command;
14. The apparatus of claim 13. the first command and the second command are interleaved with the third command and the fourth command.
15. The apparatus of claim 14. the operational combiner is configured to determine whether a dependency exists between the first command and the second command;
the operational combiner is configured to selectively combine the first command and the second command based on whether the dependency relationship exists.
10. The apparatus of claim 9.