Deadlock avoidance skid buffer

• US 8,726,283 B1
• Filed: 06/04/2007
• Issued: 05/13/2014
• Est. Priority Date: 06/04/2007
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Rubinstein, Oren, Ma, Dennis K., Kujoth, Richard B.
• Primary Examiner(s): Faherty, Corey S
• Application Number:
  US11/757,655
• Time in Patent Office: 2,535 Days
• Field of Search: None
• US Class Current: 718/102
• CPC Class Codes: G06F 9/524 Deadlock detection or avoidance

Abstract

Under some conditions, requests transmitted between different devices in a computing system may be blocked in a way that prevents the request from being processed, resulting in a deadlock condition. A skid buffer is used to allow additional requests to be queued in order to remove the blockage and end the deadlock condition. Once the deadlock condition is removed, the requests are processed and the additional buffer entries in the skid buffer are disabled.

Claims

1. A method for avoiding deadlock during request processing, comprising:

determining a deadlock condition exists that prevents processing of queued requests received from a first processing unit, wherein the first processing unit is configured to reflect requests that access an addressable location in a system memory to a second processing unit to produce at least a portion of the queued requests, wherein the first processing unit receives address translation information for the requests from the second processing unit;

enabling additional entries to accept additional requests from the first processing unit and remove the deadlock condition;

processing the queued requests; and

disabling the additional entries after the additional requests are output from the additional entries and the additional entries are empty.

2. The method of claim 1, wherein locations in the system memory are mapped to addresses that are allocated to and reorganized by the second processing unit.

3. The method of claim 1, wherein the deadlock condition exists when the first processing unit blocks a queued request from the second processing unit.

4. The method of claim 3, wherein the queued request is a snoop request that is output to the first processing unit to update any cached data for the addressable location in the system memory that is stored in the first processing unit.

5. The method of claim 1, wherein the deadlock condition exists when the first processing unit is blocked from outputting an end of interrupt transaction.

6. The method of claim 1, wherein the additional entries are located in a memory bridge device that stores a portion of the queued requests and interfaces between the first processing unit, the system memory, and the second processing unit.

7. The method of claim 1, wherein the second processing unit is configured to process graphics data and store processed graphics data in a portion of a system memory that is allocated to the second processing unit and accessible by the first processing unit.

8. The method of claim 1, further comprising completing the requests that access an addressable location in the system memory using the address translation information received from the second processing unit.

9. The method of claim 1, further comprising determining that the deadlock condition exists when a deadlock counter has reached a limit indicating that a inbound request FIFO is full and has been stalled for a predetermined number of cycles.

10. A method for avoiding deadlock during request processing, comprising:

determining a deadlock condition exists that prevents processing of queued requests received from a first processing unit, wherein the deadlock condition exists when a video processing unit outputs a peer-to-peer request that accesses an addressable location in a system memory to the first processing unit and the peer-to-peer request is reflected by the first processing unit to a graphics processor for address translation;

enabling additional entries to accept additional requests from the first processing unit and remove the deadlock condition;

processing the queued requests; and

disabling the additional entries after the additional requests are output from the additional entries and the additional entries are empty.

11. A system for avoiding deadlock during request processing, comprising:

a first processing unit configured to output requests; and

a skid buffer coupled to the first processing unit and configured to receive the requests, the skid buffer comprising;

an incoming request FIFO configured to store queued requests received from the first processing unit;

skid FIFO entries coupled to the incoming request FIFO and configured to store additional requests received from the first processing unit and output the additional requests to the incoming request FIFO; and

a deadlock detection unit coupled to the incoming request FIFO and the skid FIFO entries and configured to determine a deadlock condition exists that prevents the queued requests from being output, enable the skid FIFO entries to accept the additional requests and remove the deadlock condition, and disable the skid FIFO entries after the additional requests are output from the skid FIFO entries to the incoming request FIFO and the skid FIFO entries are empty.

12. The system of claim 11, further comprising a system memory coupled to the first processing unit and configured to store data in addressable locations that are allocated to and organized by a second processing unit and accessible by the processing unit.

13. The system of claim 12, further comprising a memory bridge device that is coupled between the first processing, the second processing unit, and the system memory.

14. The system of claim 13, wherein the skid buffer is included within the memory bridge device.

15. The system of claim 13, wherein the memory bridge device is configured to reflect an output request received from the first processing unit to the second processing unit when the output request accesses an addressable location in the system memory that is allocated to and organized by the second processing unit.

16. The system of claim 13, wherein the deadlock condition exists when the first processing unit blocks a request for output by the second processing unit through the memory bridge device to the first processing unit.

17. The system of claim 12, wherein the second processing unit is configured to process graphics data and store processed graphics data in the addressable locations of the system memory.

18. The system of claim 12, wherein the skid buffer is included within the second processing unit.

19. The system of claim 11, further comprising a third processing unit that is coupled to the first processing unit and the first processing unit is configured to reflect an output request received from the third processing unit to the second processing unit when the output request accesses an addressable location in the system memory that is allocated to and organized by the second processing unit.

20. The system of claim 19, wherein the deadlock condition exists when the first processing unit blocks a request for output by the second processing unit to the first processing unit.