Asynchronous reorder buffer

A data buffer incorporated in the read return path between a processing pipeline and a frame buffer enables data reads from the buffer to be in a different order from data writes to the buffer. With this buffer, the frame buffer no longer is required to process read requests in any particular order and can be configured for improved processing speeds. The buffer includes a RAM to which data from the frame buffer is written according to a first order and from which data is read according to a second order. The buffer may be configured with multiple RAMs if the speed of data arriving from the frame buffer is greater than the write speed of the RAM.

FIELD OF THE INVENTION

The present invention relates generally to read data buffers, and more specifically, to a read data buffer that allows data reads from the buffer to be in a different order than data writes to the buffer.

BACKGROUND

In graphics processing, frame buffers are used to store data that are needed by various processing pipelines. When a processing pipeline requests data from a frame buffer, the requested data is retrieved from the frame buffer and returned along a read return path via a read data buffer. The read data buffer is implemented as a first-in, first-out (FIFO) buffer and is placed in the read return path to buffer the requested data. This buffer ensures that the requested data arrives at the processing pipeline when the processing pipeline is ready to use it.

A simple example of how a read request from a processing pipeline is carried out is described below with reference toFIG. 1. As shown inFIG. 1, the processing pipeline110issues a series of read requests to a frame buffer120. In response to the read requests, the frame buffer120retrieves the data, in the order they were requested, and writes them into the read data buffer130, in the order they were retrieved, which is the same as the order they were requested. When the processing pipeline110is ready to use the requested data, it reads the data from the read data buffer130, in the order they were written into the read data buffer130, which is the same as the order they were retrieved from the frame buffer120and requested by the processing pipeline110.

SUMMARY OF THE INVENTION

The present invention provides a data buffer that allows data reads from the buffer to be in a different order than data writes to the buffer. With such a data buffer incorporated in a read return path between a processing pipeline of a graphics processing unit and a frame buffer, the frame buffer no longer is required to process read requests and return data in any particular order and can be configured for improved processing speeds.

A data buffer according to an embodiment of the present invention is incorporated in a read return path between a processing pipeline of a graphics processing unit and a frame buffer. The data buffer includes an addressable memory for storing data blocks received from the frame buffer, and an address lookup table that stores for each data block stored in the addressable memory, a unique identifier for the data block and the address of said addressable memory at which the data block is stored. In response to a read request for a certain data block stored in the addressable memory that includes a unique identifier for the certain data block, the address lookup table retrieves the address of the addressable memory associated with the unique identifier for the certain data block, and a read operation is carried out on the addressable memory using the retrieved address.

The data buffer may further comprise a score board memory that maintains a valid bit for all of the unique identifiers stored in the address lookup table. A valid bit for a unique identifier is set to “1” when the data block associated with the unique identifier is stored in the addressable memory and is available to be read from its location in the addressable memory. When a read request for a certain data block stored in the addressable memory is issued, the score board memory receives this read request and returns a read valid signal if the valid bit for the unique identifier for the certain data block is set as valid. After returning the read valid signal, the score board memory resets the valid bit for the unique identifier for the certain data block as invalid.

A data buffer according to another embodiment of the present invention is incorporated in a read return path between a processing pipeline and a memory unit and the data blocks retrieved from the memory unit are supplied to the data buffer at an input clock rate that is greater than the write speed of the addressable memory inside the data buffer. In order to write the incoming data stream into its addressable memory, the data buffer converts the incoming data stream to be wider and slower using a register that is clocked at the input clock rate and a multiplexer that is clocked at half the input clock rate and coupled to the input and the output of the register. The multiplexer receives at each cycle of half the input clock rate, the data blocks that are output from the register and input into the register, and supplies these data blocks to two addressable memory units. The data buffer further includes an address lookup table that stores for each data block stored in the addressable memory units, a unique identifier for the data block and the address of said addressable memory units at which the data block is stored. In response to a read request for a certain data block stored in the addressable memory units that includes a unique identifier for the certain data block, the address lookup table retrieves the address of the addressable memory units associated with the unique identifier for the certain data block, and a read operation is carried out on the addressable memory units using the retrieved address.

The multiplexer has first and second modes of operation. The multiplexer in the first mode of operation causes the data block that is output from the register and received at the multiplexer to be written into the first addressable memory unit and the data block that is input into the register and received at the multiplexer to be written into the second addressable memory unit. The multiplexer in the second mode of operation causes the data block that is output from the register and received at the multiplexer to be written into the second addressable memory unit and the data block that is input into the register and received at the multiplexer to be written into the first addressable memory unit. To distribute an equal amount of data to be loaded into each of the two addressable memory units, the multiplexer alternates between the two modes based on the amount of input data (0, 1 or 2 input cycles of data), the location of the available data (at the register input or register output or both) and a state bit that indicates which of the addressable memory units was last selected for a data load.

The present invention also provides a method of buffering a data stream from a frame buffer that is generated in response to a read request from a processing pipeline of a graphics processing unit. In this method, the data stream is buffered in an addressable memory for an asynchronous read by the processing pipeline. The method according to an embodiment of the present invention includes the steps of converting the data stream to be wider and slower, storing data blocks from the converted data stream in the addressable memory, and for each data block stored in the addressable memory, storing a unique identifier for the data block in an address lookup table. The converting step may include the steps of supplying the data stream at a first clock rate to a multiplexer, delaying the data stream by one clock cycle of the first clock rate and then supplying the delayed data stream to the multiplexer, and outputting a wider data stream from the multiplexer at a second clock rate that is half the first clock rate.

DETAILED DESCRIPTION

FIG. 2illustrates a processing pipeline210, a frame buffer220, and a read data buffer230according to an embodiment of the present invention. The processing pipeline210may be, for example, a part of the raster operation unit (ROP) of a graphics processing unit (GPU). The frame buffer220is a memory unit that stores data for various components of the GPU including the ROP. The frame buffer220is configured for more optimal processing relative to the frame buffer120ofFIG. 1. Typically, frame buffer reads, such as from the frame buffer120, are processed in the order they were requested. More advanced configurations of frame buffers, such as the frame buffer220, process frame buffer reads in the order that is the most efficient for memory accesses. For example, read requests may be reorganized so that memory access to the same rows or banks are processed together.

In operation, the processing pipeline210issues a series of read requests to the frame buffer220. In response to the read requests, the frame buffer220returns the requested data to the processing pipeline210via the read data buffer230. The system ofFIG. 2operates differently from the system ofFIG. 1in the following ways. First, the read data buffer230enables data reads from it to be in a different order than data writes to it. Second, because of this ability of the read data buffer230to reorder data reads with respect to data writes, the system ofFIG. 2is operable with advanced frame buffers, like the frame buffer220, which may not necessarily return read data in the order of the read requests.

An example of how a series of read requests issued by the processing pipeline210are carried out by the system ofFIG. 2is described below. First, the processing pipeline210issues a series of read requests to the frame buffer220in the following order: request—1, request—2, request—3, request—4, and request—5. In response to the read requests, the frame buffer220retrieves data in the order it determines to be the most optimal for memory accesses: e.g., data—3, data—4, data—2, data—5, and data—1, where data_n corresponds to data requested by request_n, and returns them in that order to the read data buffer230. The read data buffer230receives this data in the order returned by the frame buffer220and enables the processing pipeline210to read them in a different order, i.e., the order of its read requests, namely data—1, data—2, data—3, data—4, and data—5.

FIG. 3is a block diagram of the read data buffer230according to an embodiment of the invention. As shown, the read data buffer230includes the following memory units: a register310, RAMs320,330, read address FIFOs340,350, write address FIFOs360,370, an address RAM380, and a score board395. The RAMs320,330are used to store data blocks (e.g., 16-byte data chunks) arriving from the frame buffer220for reading by the processing pipeline210at a later time. Each such data block is assigned a unique tag so that it can be identified during subsequent reads from the RAMs320,330using this tag. There are various ways of assigning the unique tags for the data blocks. In the embodiment of the present invention illustrated herein, the unique tag is assigned as the address at which the data would have been stored in a conventional read data buffer, such as read data buffer130.

The read address FIFOs340,350store addresses of the RAMs320,330that are available for new data blocks arriving from the frame buffer220. When a new data block arrives from the frame buffer220, an address is popped off from the read address FIFOs340,350and the new data block is stored in the RAMs320,330at that address. This address and the unique tag assigned to this new data block are stored together in the write address FIFOs360,370. Addresses and unique tags are unloaded from the write address FIFOs360,370through a multiplexer375as soon as they become available, and stored in the address RAM380. The address RAM380is configured as a lookup table that associates the unique tags of data blocks with addresses of RAMs320,330at which the data blocks are stored. The score board395keeps track of the validity of tags. A tag is valid when its associated data block is stored in one of the RAMs320,330and the data block is available to be read. A valid tag has a valid bit set to “1” in the score board395.

The read data buffer230inFIG. 3is configured with the register310, and a pair of RAMs320,330, write address FIFOs360,370and read address FIFOs340,350to accommodate data blocks arriving at the read data buffer230at a higher clock rate than the individual write speed of the RAMs320,330. The register310is clocked at the input data rate, and enables the data blocks to be loaded double wide at half rate into the RAMs320,330.

An example of how the register310is used to enable the data blocks to be loaded double wide at half rate into the RAMs320,330is given below. There may be zero, one, or two data blocks arriving at the data return buffer230to be written into the RAMs320,330at each half rate cycle. If there are two data blocks, the first data block is stored in the register310. One cycle later, the first data block stored in the register310and the second data block arrive at the multiplexer315.

The multiplexer315operates at the half rate cycle and has first and second modes of operation. The multiplexer315in the first mode of operation causes the data block that is output from the register310and received at the multiplexer315to be written into the RAM320and the data block that is input into the register310and received at the multiplexer315to be written into the RAM330. The multiplexer315in the second mode of operation causes the data block that is output from the register310and received at the multiplexer315to be written into the RAM330and the data block that is input into the register310and received at the multiplexer315to be written into the RAM320.

To distribute an equal amount of data to be loaded into each of the two addressable memory units, the multiplexer alternates between the two modes based on the amount of input data (0, 1 or 2 input cycles of data), the location of the available data (at the register input or register output or both) and a state bit that indicates which of the addressable memory units was last selected for a data load. The table below describes how the multiplexer mode is selected based on these parameters.

Alternatively, the multiplexer mode is controlled based on the number of free positions in each RAM320,330, such that when only one data block appears at the register input and output, it is always loaded into the RAM320,330with the most free locations.

The tags associated with the data blocks arrive at the read data buffer230at the same speed as the data blocks, and the register310is used to enable the tags to be loaded double wide at half rate into the write address FIFOs360,370in the same manner as the data blocks.

Before a data block is written to RAM320, a write address corresponding to an available memory location in RAM320is picked off from the read address FIFO340, and the data block is written to that memory location. Before a data block is written to RAM330, a write address corresponding to an available memory location in RAM330is picked off from the read address FIFO350, and the data block is written to that memory location.

In addition, when a data block is written to a memory location in the RAM320or330, the tag of the data block and the address corresponding to that memory location are stored in the corresponding write address FIFO360or370. Tags and write addresses stored in the write address FIFOs360,370are unloaded into the address RAM380through multiplexer375as soon as they become available in the write address FIFOs360,370. The multiplexer375is controlled so that the tags and write addresses are unloaded from the write address FIFOs360,370with round robin priority. The address RAM380stores the tags and the write addresses unloaded from the write address FIFOs360,370in a lookup table. The unloaded tags are also supplied to the score board395, which sets a valid bit associated with each of the unloaded tags. A valid bit for a tag indicates that the tag is being used and that the tag has an associated data block stored in one of the RAMs320,330. The lookup table stored in the address RAM380provides the address of the RAMs320,330where the associated data block is stored.

For a data block read from the read data buffer230, the processing pipeline210sends the tag associated with the desired data block to the read data buffer230. This tag is supplied to the score board395and the address RAM380. The score board395is accessed and the valid bit for this tag is examined to see whether the data block is available in the RAMs320,330for a read operation. If the data block is available (e.g., the valid bit is set to “1”), the address corresponding to the tag is retrieved from the lookup table stored in the address RAM380. The data block is then retrieved from the RAMs320,330using the retrieved address and output through multiplexer385to the processing pipeline210. In addition, the valid bit associated with the tag is reset to “0” in the score board395, and the address associated with this tag is alternately pushed into the read address FIFOs340,350through multiplexer355and becomes available for reuse. Upon power-up or reset of the read data buffer230, the read address FIFOs340,350are populated with all of the addresses of RAMs320,330.

FIG. 4is a flow diagram that illustrates the process steps that are carried out in response to read requests issued by a processing pipeline. In step410, the processing pipeline210issues a series of read requests to the frame buffer220for data needed by the processing pipeline210. In step420, data are returned by the frame buffer220responsive to the read requests in the order it determines to be the most optimal. In step430, the data returned by the frame buffer220are written to the read data buffer230in the order they were returned by the frame buffer220. The data blocks written in the read data buffer are marked with unique tags so that they can be retrieved by the processing pipeline210using the same tags. In step440, the processing pipeline210retrieves the requested data blocks from the read data buffer230in the order it needs them using the unique tags. Generally, this is the same order as the order of the read requests that were issued to the frame buffer220.

FIG. 5is a flow diagram that illustrates the process steps that are carried out by the read data buffer230to buffer a data stream from the frame buffer220. In step510, the frame buffer220returns a data stream to the read data buffer230in response to read requests from the processing pipeline210. In step520, the read data buffer230converts the data stream to be double wide and clocked at half the incoming rate. This is done so that addressable memory units in the read data buffer230used for buffering the data stream can accommodate the speed of the incoming data stream. In step530, the data blocks from the converted data stream are stored in the addressable memory units. In step540, a unique identifier and the write address for each data block stored in the addressable memory are stored in an address lookup table. The address lookup table is used in subsequent, asynchronous reads of the data blocks stored in the addressable memory units.

While foregoing is directed to embodiments in accordance with one or more aspects of the present invention, other and further embodiments of the present invention may be devised without departing from the scope thereof, which is determined by the claims that follow. Claims listing steps do not imply any order of the steps unless such order is expressly indicated.