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

Patent metadata

Field	Value
Publication number	US-9755994-B2
Application number	US-201213476825-A
Country	US
Kind code	B2
Filing date	May 21, 2012
Priority date	May 21, 2012
Publication date	Sep 5, 2017
Grant date	Sep 5, 2017

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.

First claim

What is claimed is:

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.

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

Assignees

• Fetterman Michael
• Gadre Shirish
• Edmondson John H
• Paranjape Omkar
• Rajendran Anjana
• Hill Eric Lyell
• Selvanesan Rajeshwaran
• Mccarver Charles
• Mitchell Kevin
• Heinrich Steven James
• Nvidia Corp

Inventors

• Fetterman Michael
• Gadre Shirish
• Edmondson John H
• Paranjape Omkar
• Rajendran Anjana
• Hill Eric Lyell
• Selvanesan Rajeshwaran
• Mccarver Charles
• Mitchell Kevin
• Heinrich Steven James

Classifications

• G06F9/46

  Multiprogramming arrangements · CPC title

• H04L49/254 Primary

  Centralised controller, i.e. arbitration or scheduling · CPC title