Mechanism for tracking age of common resource requests within a resource management subsystem

• US 9,755,994 B2
• Filed: 05/21/2012
• Issued: 09/05/2017
• Est. Priority Date: 05/21/2012
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Fetterman, Michael, Gadre, Shirish, Edmondson, John H., Paranjape, Omkar, Rajendran, Anjana, Hill, Eric Lyell, Selvanesan, Rajeshwaran, McCarver, Charles, Mitchell, Kevin, Heinrich, Steven James
• Primary Examiner(s): Wong, Titus
• Application Number:
  US13/476,825
• Publication Number:
  US 20130311686A1
• Time in Patent Office: 1,933 Days
• Field of Search: 710 54
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling

Abstract

One embodiment of the present disclosure sets forth an effective way to maintain fairness and order in the scheduling of common resource access requests related to replay operations. Specifically, a streaming multiprocessor (SM) includes a total order queue (TOQ) configured to schedule the access requests over one or more execution cycles. Access requests are allowed to make forward progress when needed common resources have been allocated to the request. Where multiple access requests require the same common resource, priority is given to the older access request. Access requests may be placed in a sleep state pending availability of certain common resources. Deadlock may be avoided by allowing an older access request to steal resources from a younger resource request. One advantage of the disclosed technique is that older common resource access requests are not repeatedly blocked from making forward progress by newer access requests.

Claims

1. A method for identifying and executing requests for common resources in a processing pipeline, the method comprising:

receiving a plurality of requests for one or more common resources;

storing a different entry in a buffer for each request in the plurality of requests, wherein the entries are stored in a temporal order;

upon determining that a first common resource is available, distributing resource status information associated with the first common resource to each entry included in the buffer,

searching the resource status information distributed to the entries stored in the buffer to identify a subset of entries corresponding to requests that are associated with at least the first common resource;

identifying one or more entries included in the subset of entries that indicate that all common resources, including the first common resource, associated with the requests corresponding to the one or more entries are available;

reading a first entry included in the one or more entries that is the oldest of the one or more entries in order to execute a first cycle of a first request that corresponds to the first entry.

2. The method of claim 1, wherein the first entry indicates that a plurality of cycles of the first request is to be executed, and further comprising causing a first entry in a replay buffer instruction corresponding to the first entry in the buffer to be read into the processing pipeline in order to execute the first cycle of the first request.

3. The method of claim 1, further comprising determining that no other cycles of the first request are to be executed subsequent to executing the first cycle.

4. The method of claim 3, further comprising retiring the first entry from the buffer.

5. The method of claim 4, wherein the first entry is not the oldest entry in the buffer, and further comprising creating a bubble in the buffer to replace the first entry when the first entry is retired.

6. The method of claim 5, further comprising receiving a new request for one or more common resources;

and storing a new entry in the buffer for the new request.

7. The method of claim 6, wherein storing the new entry comprises adding the new entry to a newest position in the buffer, and shifting each entry in the buffer that resides between the bubble and the newest position one entry such that an existing entry in the buffer replaces the bubble.

8. The method of claim 1, further comprising determining that the first entry is the oldest of the one or more entries by determining that the first entry was stored in the buffer prior to any of the other entries included in the one or more entries.

9. The method of claim 1, further comprising determining that the first entry is the oldest of the one or more entries based on a priority scheme or based on the first entry being the least recently accessed entry of the one or more entries.

21. The method of claim 1, further comprising distributing access request status information associated with the first request to a first entry included in the buffer.

22. The method of claim 1, wherein the access request status information associated with the first request includes at least one of address generation unit request status from an address generation unit, arbitration status from an arbitration unit, and L1 cache request status from an L1 cache memory.

10. A subsystem for identifying and executing requests for common resources, comprising:

a processing pipeline; and

a total order queue (TOQ) coupled to the processing pipeline and configured to perform the steps of;

receiving a plurality of requests for one or more common resources;

storing a different entry in a buffer for each request in the plurality of requests, wherein the entries are stored in a temporal order;

upon determining that a first common resource is available, distributing resource status information associated with the first common resource to each entry included in the buffer,

searching the resource status information distributed to the entries stored in the buffer to identify a subset of entries corresponding to requests that are associated with at least the first common resource;

identifying one or more entries included in the subset of entries that indicate that all common resources, including the first common resource, associated with the requests corresponding to the one or more entries are available;

reading a first entry included in the one or more entries that is the oldest of the one or more entries in order to execute a first cycle of a first request that corresponds to the first entry.

11. The subsystem of claim 10, wherein the first entry indicates that a plurality of cycles of the first request is to be executed, and the TOQ is further configured to perform the step of causing a first entry in a replay buffer instruction corresponding to the first entry in the buffer to be read into the processing pipeline in order to execute the first cycle of the first request.

12. The subsystem of claim 10, wherein the TOQ is further configured to perform the step of determining that no other cycles of the first request are to be executed subsequent to executing the first cycle.

13. The subsystem of claim 12, wherein the TOQ is further configured to perform the step of retiring the first entry from the buffer.

14. The subsystem of claim 13, wherein the first entry is not the oldest entry in the buffer, and the TOQ is further configured to perform the step of creating a bubble in the buffer to replace the first entry when the first entry is retired.

15. The subsystem of claim 14, wherein the TOQ is further configured to perform the steps of receiving a new request for one or more common resources;

and storing a new entry in the buffer for the new request.

16. The subsystem of claim 15, wherein storing the new entry comprises adding the new entry to a newest position in the buffer, and shifting each entry in the buffer that resides between the bubble and the newest position one entry such that an existing entry in the buffer replaces the bubble.

17. The subsystem of claim 10, wherein the TOQ is further configured to perform the step of determining that the first entry is the oldest of the one or more entries by determining that the first entry was stored in the buffer prior to any of the other entries included in the one or more entries.

18. The subsystem of claim 10, wherein the TOQ is further configured to perform the step of determining that the first entry is the oldest of the one or more entries based on a priority scheme or based on the first entry being the least recently accessed entry of the one or more entries.

19. A computing device, comprising:

a processor; and

a total order queue (TOQ) coupled to the processor and configured to identify and execute requests for common resources in a processing pipeline associated with the processor, by performing the steps of;

receiving a plurality of requests for one or more common resources;

storing a different entry in a buffer for each request in the plurality of requests, wherein the entries are stored in a temporal order;

upon determining that a first common resource is available, distributing resource status information associated with the first common resource to each entry included in the buffer,

searching the resource status information distributed to the entries stored in the buffer to identify a subset of entries corresponding to requests that are associated with at least the first common resource;

identifying one or more entries included in the subset of entries that indicate that all common resources, including the first common resource, associated with the requests corresponding to the one or more entries are available;

reading a first entry included in the one or more entries that is the oldest of the one or more entries in order to execute a first cycle of a first request that corresponds to the first entry.

20. The computing device of claim 19, wherein the first entry indicates that a plurality of cycles of the first request is to be executed, and the TOQ is further configured to perform the step of causing a first entry in a replay buffer instruction corresponding to the first entry in the buffer to be read into the processing pipeline in order to execute the first cycle of the first request.