Read completion data management

• US 8,656,117 B1
• Filed: 10/30/2008
• Issued: 02/18/2014
• Est. Priority Date: 10/30/2008
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Wong, Raymond Hoi Man, Duncan, Samuel Hammond, Muliadi, Lukito, Swarna, Madhukiran V.
• Primary Examiner(s): Parikh, Kalpit
• Application Number:
  US12/262,141
• Time in Patent Office: 1,937 Days
• Field of Search: 711/154, 711/167, 710/56, 710/58
• US Class Current: 711/154
• CPC Class Codes: G06F 9/3824 Operand accessing
• CPC Class Codes: G06F 9/3836 Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution

Abstract

An input/output unit for a computer system that is interfaced with a memory unit having a plurality of partitions manages completions of read requests in the order that they were made. A read request buffer tracks the order in which the read requests were made so that read data responsive to the read requests can be completed and returned to a requesting client in the order the read requests were made.

Claims

1. A method of managing read completions in response to multiple read requests from a client, comprising:

tracking an order of the multiple read requests in a read request buffer;

generating first and second subrequests for each of the multiple read requests;

storing data fragments associated with the multiple read requests at locations within multiple read return buffers;

storing pointers to the locations within the multiple read return buffers where the data fragments are stored;

tracking completion of the first and second subrequests for each of the multiple read requests when data fragments associated with the multiple read requests have returned and stored in the multiple read return buffers, to determine whether the multiple read requests have completed;

examining an in-order first-in-first-out (FIFO) unit to determine whether a first read request of the multiple read requests generated by an in-order client has completed in-order, when the first read requests has completed;

storing an index for a second read requests of the multiple read requests generated by an out-of-order client, when the second read request has completed; and

reading out data fragments associated with the multiple read requests from the multiple read return buffers using the stored addresses and based on the tracked order of the multiple read requests.

2. The method according to claim 1, wherein data fragments associated with a read request are read out from the multiple read return buffers if said read request is the next read request for processing and the first and second subrequests for said read request have completed.

3. The method according to claim 2, wherein the read request buffer is a FIFO and the order of the multiple read requests is tracked by storing indices associated with the read requests in the read request buffer in the order they are received.

4. The method according to claim 1, wherein each of the first and second subrequests is associated with one of the multiple read return buffers and a data fragment that is returned in response to a subrequest is stored in the read return buffer associated with said subrequest.

5. The method according to claim 1, wherein the multiple read requests include a first read request and a second read request that is received after the first read request, and the data fragments associated with the first read request are assembled and transmitted to the client before the data fragments associated with the second read request are assembled and transmitted to the client.

6. The method according to claim 5, wherein the read request buffer tracks the order of the first and second read requests by storing indices associated with the first and second read requests as the first and second read requests are received from the client.

7. The method according to claim 1, wherein the pointers are stored in a pointer random access memory (RAM), and wherein both the multiple read return buffers and the pointer RAM reside within an input/output unit.

8. A method of managing read completions in response to read requests from multiple clients, comprising:

receiving multiple read requests from multiple clients, the multiple clients including at least one in-order client that requires read requests to be completed in the order they were issued;

tracking in a read request buffer an order of multiple read requests that are received from each of the in-order clients;

generating subrequests for each read request;

storing data fragments responsive to the multiple read requests in an addressable memory;

storing addresses of the addressable memory at which the data fragments have been stored in an address memory;

tracking completion of the subrequests for each read request when data fragments associated with the subrequests have returned and stored in the addressable memory, to determine whether the multiple read requests have completed;

examining an in-order first-in-first-out (FIFO) unit to determine whether a first read request of the multiple read requests generated by an in-order client has completed in-order, when the first read requests has completed;

storing an index for a second read requests of the multiple read requests generated by an out-of-order client, when the second read request has completed; and

for read requests from an in-order client, reading out data fragments associated with said read requests from the addressable memory using the addresses stored in the address memory and based on the order of the read requests as tracked for said in-order client.

9. The method according to claim 8, wherein tracking completion of the subrequests for each read request is performed in a scoreboard memory, and wherein the scoreboard memory is updated to indicate completion of a subrequest when a data fragment associated with the subrequest is stored in the addressable memory.

10. The method according to claim 9, wherein the data fragments associated with a read request are not read out from the addressable memory until the scoreboard memory indicates that the subrequests associated with said read request have completed.

11. The method according to claim 8, wherein a subrequest is directed to one of multiple memory interfaces and the data fragment associated with said subrequest is received through said one of multiple memory interfaces.

12. The method according to claim 11, wherein the addressable memory includes multiple buffers, each of which is coupled to one of the memory interfaces.

13. The method according to claim 12, further comprising:

for each buffer, maintaining a count of data fragments stored in the buffer,

wherein the count is increased each time a request for a data fragment is issued to the memory interface coupled to said buffer and decreasing the count each time a data fragment is read out from said buffer.

14. The method according to claim 13, further comprising:

suspending a subrequest directed to a memory interface if the count that is maintained for a buffer that is coupled to the memory interface indicates that said buffer is full.

15. The method according to claim 14, further comprising:

directing the suspended subrequest to the memory interface if the count that is maintained for the buffer that is coupled to the memory interface no longer indicates that said buffer is full.

16. A computer system comprising:

a memory unit divided into a plurality of partitions;

a plurality of clients that generate requests to read data from the memory unit; and

an input/output unit having a read request buffer for tracking an order of read requests received from one of the clients, wherein the input/output unit is configured to return completed read data to said one of the clients in accordance with the tracked order, and wherein the input/output unit is configured to generate a first subrequest and a second subrequest for each read request,

wherein the input/output unit is coupled to the memory unit through a plurality of memory interfaces and includes;

multiple read return buffers, each of which is coupled to one of the memory interfaces, for storing data fragments returned through said one of the memory interfaces, a pointer memory that stores addresses of locations within the multiple read return buffers in which the data fragments are stored, a scoreboard memory for tracking completion of the requests to read data, the scoreboard memory indicates when data fragments associated with each read request have returned and stored in the multiple read return buffers to determine whether the requests have completed, an arbiter unit that examines an in-order first-in-first-out (FIFO) unit to determine whether a first read request of the read requests generated by an in-order client has completed in-order, when the first read requests has completed, the arbiter unit also stores an index for a second read requests of the read requests generated by an out-of-order client, when the second read request has completed, and a read data packer that reads out data fragments associated with a read request from the read return buffers using the addresses stored in the pointer memory, assembles the data fragments that have been read out, and returns the assembled data fragments to a requesting client as completed read data.

17. The computer system according to claim 16, wherein the read request buffer is a FIFO for storing indices associated with the requests to read data received from said one of the clients as they are received.

18. The computer system according to claim 17, wherein the input/output unit has an additional read request buffer for tracking an order of read requests received from another one of the clients, wherein the input/output unit is configured to return completed read data to said another one of the clients in accordance with the tracked order.

19. The computer system according to claim 16, further comprising a graphics processing unit, wherein the memory unit is a frame buffer for the graphics processing unit, and the input/output unit is a non-isochronous hub for the graphics processing unit.