RESOURCE MANAGEMENT SUBSYSTEM THAT MAINTAINS FAIRNESS AND ORDER

• US 20130311999A1
• Filed: 05/21/2012
• Published: 11/21/2013
• Est. Priority Date: 05/21/2012
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: Michael Fetterman, Omkar Paranjape, Steven James Heinrich
• Inventors: FETTERMAN, Michael, Gadre, Shirish, Edmondson, John H., Paranjape, Omkar, Rajendran, Anjana, Hill, Eric Lyell, Selvanesan, Rajeshwaran, McCarver, Charles, Mitchell, Kevin, Heinrich, Steven James
• Granted Patent: US 9,836,325 B2
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/507 Low-level
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals

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 managing requests for common resources in a processing pipeline, the method comprising:

receiving a first request for a first common resource;

determining that the first common resource is not available for allocation to requests;

in response, delaying servicing the first request;

subsequent to delaying servicing, receiving a second request for the first common resource;

subsequent to receiving the second request, determining that the first common resource has become available for allocation to requests; and

making the first common resource available to the first request, prior to making the first common resource available to the second request.

2. The method of claim 1, further comprising creating a first entry in a first buffer for the first request to track the age of the first request, wherein the first entry indicates that the first request is associated with at least the first common resource.

3. The method of claim 2, further comprising, upon receiving the second request, searching the first buffer for any entry corresponding to a request that is associated with the first common resource.

4. The method of claim 3, further comprising identifying via the first entry that the first request is associated with the first common resource, and, in response, determining that the first request should be serviced prior to the second request.

5. The method of claim 2, further comprising creating a second entry in the first buffer for the second request to track the age of the second request, wherein the second entry indicates that the second request is associated with at least the first common resource.

6. The method of claim 5, upon determining that the first common resource is available, searching the first buffer for any entry corresponding to a request that is associated with the first common resource.

7. The method of claim 6, further comprising identifying via the first entry and the second entry that the first request and the second request are associated with the first common resource and that the first request is older than the second request, and, in response, determining that the first request should be serviced prior to the second request.

8. The method of claim 2, further comprising causing a first entry to be created in a replay buffer that corresponds to the first entry in the first buffer, wherein the first entry in the replay buffer includes execution information associated with the first request that is used for replay operations associated with the first request.

9. The method of claim 2, wherein the first entry further includes information that indicates the status of the first common resource.

10. The method of claim 9, wherein the status of the first common resource is that the first common resource is needed by the first request but not allocated to the first request or that the first common resource is locked and unavailable to the first request.

11. A subsystem for managing requests for common resources in a processing pipeline, comprising:

a total order queue (TOQ) configured to perform the steps of;

receiving a first request for a first common resource;

determining that the first common resource is not available for allocation to requests;

in response, delaying servicing the first request;

subsequent to delaying servicing, receiving a second request for the first common resource;

subsequent to receiving the second request, determining that the first common resource has become available for allocation to requests; and

making the first common resource available to the first request, prior to making the first common resource available to the second request.

12. The subsystem of claim 11, wherein the TOQ is further configured to perform the step of creating a first entry in a first buffer for the first request to track the age of the first request, wherein the first entry indicates that the first request is associated with at least the first common resource.

13. The subsystem of claim 12, wherein the TOQ is further configured to perform the step of, upon receiving the second request, searching the first buffer for any entry corresponding to a request that is associated with the first common resource.

14. The subsystem of claim 13, wherein the TOQ is further configured to perform the steps of identifying via the first entry that the first request is associated with the first common resource, and, in response, determining that the first request should be serviced prior to the second request.

15. The subsystem of claim 12, wherein the TOQ is further configured to perform the step of creating a second entry in the first buffer for the second request to track the age of the second request, wherein the second entry indicates that the second request is associated with at least the first common resource.

16. The subsystem of claim 15, wherein the TOQ is further configured to perform the step of, upon determining that the first common resource is available, searching the first buffer for any entry corresponding to a request that is associated with the first common resource.

17. The subsystem of claim 16, wherein the TOQ is further configured to perform the steps of identifying via the first entry and the second entry that the first request and the second request are associated with the first common resource and that the first request is older than the second request, and, in response, determining that the first request should be serviced prior to the second request.

18. The subsystem of claim 12, wherein the TOQ is further configured to perform the step of causing a first entry to be created in a replay buffer that corresponds to the first entry in the first buffer, wherein the first entry in the replay buffer includes execution information associated with the first request that is used for replay operations associated with the first request.

19. The subsystem of claim 12, wherein the first entry further includes information that indicates the status of the first common resource, and the status of the first common resource is that the first common resource is needed by the first request but not allocated to the first request or that the first common resource is locked and unavailable to the first request.

20. A computing device, comprising:

a total order queue (TOQ) configured to manage requests for common resources in a processing pipeline by performing the steps of;

receiving a first request for a first common resource;

determining that the first common resource is not available for allocation to requests;

in response, delaying servicing the first request;

subsequent to delaying servicing, receiving a second request for the first common resource;

subsequent to receiving the second request, determining that the first common resource has become available for allocation to requests; and

making the first common resource available to the first request, prior to making the first common resource available to the second request.