Mechanism for waking common resource requests within a resource management subsystem

• US 10,095,548 B2
• Filed: 05/21/2012
• Issued: 10/09/2018
• 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): Tang, Kenneth
• Application Number:
  US13/476,848
• Publication Number:
  US 20130311996A1
• Time in Patent Office: 2,332 Days
• Field of Search: 718104, 711150, 710261
• CPC Class Codes: G06F 2209/503 Resource availability
• CPC Class Codes: G06F 9/5016 the resource being the memory

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 waking up a request for a common resource, where the request has been put to sleep within a buffer, the method comprising:

determining that a first common resource is available for allocation to any request included in a plurality of requests;

determining that the availability of the first common resource satisfies a first wake-up condition for a first request included in the plurality of requests that has been put to sleep within the buffer, wherein a second common resource needed by the first request remains unavailable;

in response, waking up the first request so that the first request can be further analyzed for execution;

determining, at a total order queue, that the unavailability of the second common resource is a transient condition; and

in response, allowing the execution of a first cycle of the first request.

2. The method of claim 1, wherein a second common resource remains unavailable for the first request, and further comprising preventing any cycles of the first request from executing until the second common resource becomes available.

3. The method of claim 1, wherein a second common resource remains unavailable for the first request, and further comprising putting the first request back to sleep until the second common resource becomes available.

4. The method of claim 1, wherein a second common resource remains unavailable for the first request because the second common resource has been made available to a second request, and further comprising stealing the second common resource from the second request so that the second common resource is available to the first request.

5. The method of claim 4, wherein stealing the second common resource comprises changing an entry in the buffer corresponding to the second request to indicate that the second common resource is not available to the second request.

6. The method of claim 4, wherein stealing the second common resource occurs only after a predetermined amount of time has elapsed.

7. The method of claim 4, wherein the first request corresponds to an entry in the buffer that is the entry that has been sleeping in the buffer longer than any other request included in the plurality of requests.

8. The method of claim 1, further comprising determining that the availability of the first common resource satisfies a first wake-up condition for one or more other requests, and waking up the one or more other requests so that the one or more other requests can be further analyzed for execution.

9. The method of claim 8, wherein a broadcast wake-up operation is implemented to wake up the first request and the one or more other requests.

10. The method of claim 1, further comprising, in response to waking up the first request, analyzing the first request for execution.

11. The method of claim 1, wherein, upon determining that the unavailability of the second common resource is a transient condition, the first request is eligible for execution immediately.

12. The method of claim 1, wherein, upon determining that the unavailability of the second common resource is a transient condition, the first request is eligible for execution after a finite delay.

13. A subsystem for waking up a request for a common resource, where the request has been put to sleep within a buffer, comprising:

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

determining that a first common resource is available for allocation to any request included in a plurality of requests;

determining that the availability of the first common resource satisfies a first wake-up condition for a first request included in the plurality of requests that has been put to sleep within the buffer, wherein a second common resource needed by the first request remains unavailable;

in response, waking up the first request so that the first request can be further analyzed for execution;

determining that the unavailability of the second common resource is a transient condition; and

in response, allowing the execution of a first cycle of the first request.

14. The subsystem of claim 13, wherein a second common resource remains unavailable for the first request, and the TOQ is further configured to perform the step of preventing any cycles of the first request from executing until the second common resource becomes available.

15. The subsystem of claim 13, wherein a second common resource remains unavailable for the first request, and the TOQ is further configured to perform the step of putting the first request back to sleep until the second common resource becomes available.

16. The subsystem of claim 13, wherein a second common resource remains unavailable for the first request because the second common resource has been made available to a second request, and the TOQ is further configured to perform the step of stealing the second common resource from the second request so that the second common resource is available to the first request.

17. The subsystem of claim 16, wherein stealing the second common resource comprises changing an entry in the buffer corresponding to the second request to indicate that the second common resource is not available to the second request.

18. The subsystem of claim 16, wherein stealing the second common resource occurs only after a predetermined amount of time has elapsed.

19. The subsystem of claim 16, wherein the first request corresponds to an entry in the buffer that is the entry that has been sleeping in the buffer longer than any other request included in the plurality of requests.

20. The subsystem of claim 13, further comprising determining that the availability of the first common resource satisfies a first wake-up condition for one or more other requests, and waking up the one or more other requests so that the one or more other requests can be further analyzed for execution.

21. A computing device, comprising:

a processor that executes a total order queue (TOQ) configured to wake up a request for a common resource, where the request has been put to sleep within a buffer by performing the steps of;

determining that a first common resource is available for allocation to any request included in a plurality of requests;

determining that the availability of the first common resource satisfies a first wake-up condition for a first request included in the plurality of requests that has been put to sleep within the buffer, wherein a second common resource needed by the first request remains unavailable;

in response, waking up the first request so that the first request can be further analyzed for execution;

determining that the unavailability of the second common resource is a transient condition; and

in response, allowing the execution of a first cycle of the first request.