Priority based bus arbiters avoiding deadlock and starvation on buses that support retrying of transactions

• US 8,370,552 B2
• Filed: 10/14/2008
• Issued: 02/05/2013
• Est. Priority Date: 10/14/2008
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Mittal, Aditya, Kanuri, Mrudula, Malladi, Venkata
• Primary Examiner(s): PHAN, RAYMOND NGAN
• Application Number:
  US12/250,566
• Publication Number:
  US 20100095036A1
• Time in Patent Office: 1,575 Days
• Field of Search: 710111-119, 710240-244
• US Class Current: 710/113
• CPC Class Codes: G06F 13/366 using a centralised polling arbiter

Abstract

A scheduler provided according to an aspect of the present invention provides higher priority for data units in a low priority queue upon occurrence of a starvation condition, and to packets in a high priority queue otherwise. The scheduler permits retransmission of a data unit in the lower priority queue when in the starvation condition, but clears the starvation condition when the data unit is retransmitted a pre-specified number of times. As a result, the data units in the higher priority queue would continue to be processed, thereby avoiding a deadlock at least in certain situations.

Claims

1. An arbiter for use in a system, said system comprising a component configured to request retransmission of data units, said arbiter comprising:

a high priority queue and a low priority queue;

a queuing block to store a first set of data units in said high priority queue and a second set of data units in said low priority queue; and

a scheduler to determine which of said queues is to be allocated time slots of a sequence of time slots, said scheduler to provide higher priority for said low priority queue upon occurrence of a predetermined condition for said low priority queue and to said high priority queue otherwise, wherein said scheduler retransmits a first data unit in said low priority queue for up to a pre-specified number of times in successive time slots before clearing said predetermined condition.

2. The arbiter of claim 1, wherein said scheduler is configured to maintain a counter and operable to increment said counter if a data unit is available in said low priority queue when a data unit from said high priority queue is transmitted on said bus, wherein said predetermined condition comprises said counter being equal to a second pre-specified number, wherein clearing said counter comprises resetting said counter to a third pre-specified value.

3. The arbiter of claim 2, wherein said arbiter comprises an up arbiter to receive corresponding requests from said plurality of components for an up bus, said up arbiter granting said up bus to only one of said plurality of components in a time slot, wherein the granted component transmits a corresponding data unit to said queuing block in said arbiter in the granted time slot.

4. The arbiter of claim 3, wherein said system further comprises a clock generator to generate a clock signal, said clock signal having a plurality of successive cycles, each time slot corresponding to one of said plurality of successive cycles.

5. The arbiter of claim 4, wherein said plurality of components are configured to request retransmission by asserting corresponding ones of retransmit request lines, wherein said scheduler is operable to examine the retransmit lines of said plurality components to determine whether to retransmit said first data unit.

6. A method implemented in an arbiter, said method comprising:

storing a first set of data units in a high priority queue and a second set of data units in a low priority queue;

determining which of said queues is to be allocated time slots of a sequence of time slots, wherein said determining comprises providing higher priority for said low priority queue upon occurrence of a predetermined condition for said low priority queue, and for said high priority queue otherwise;

transmitting a first data unit on a unidirectional bus to a first component and receiving a retransmit request in response; and

retransmitting said first data unit upon receiving said retransmit request,

wherein said first data unit is transmitted up to a pre-specified number of times in successive time slots before clearing said predetermined condition.

7. The method of claim 6, further comprising:

initializing a first counter to a start value;

incrementing said first counter if a data unit is available in said low priority queue when a data unit from said high priority queue is transmitted in a time slot,

wherein said predetermined condition comprises said first counter being equal to a second pre-specified number, wherein clearing said first counter comprises resetting said first counter to said start value.

8. The method of claim 6, further comprising:

receiving corresponding requests from a plurality of components for an up bus;

granting said up bus to only one of said plurality of components in each time slot; and

receiving a corresponding data unit from the granted component in the granted time slot,

wherein said storing stores each received data unit in one of said low priority queue and said high priority queue.

9. The method of claim 6, further comprising:

initializing a second counter to an initial value;

incrementing said second counter each time said first data unit is transmitted or retransmitted;

checking whether said second counter has reached a threshold value; and

setting said first counter to said start value if said second counter has reached said threshold value, thereby clearing said predetermined condition.

10. The method of claim 6, wherein said pre-specified number equals 1.

11. The method of claim 6, wherein said pre-specified number is an integer greater than or equal to 2.

12. A system comprising:

a plurality of components forming a plurality of data units, the data units to be transmitted to corresponding destination components of the plurality of components, wherein the destination components are configured to request retransmission of the data units; and

an arbiter operable to receive the plurality of data units and operable to transmit the plurality of data units to the corresponding destination components, wherein the arbiter comprises;

a high priority queue and a low priority queue, wherein the plurality of data units are stored in one of the high priority queue and the low priority queue; and

a scheduler operable to transmit, in a time slot, data units in the high priority queue with a higher priority compared to data units in the low priority queue, until the scheduler determines a predetermined condition exists for the low priority queue and causes a first data unit in the low priority queue to be transmitted, wherein the scheduler is operable to retransmit the first data unit up to a first predetermined number of attempts and then clear the predetermined condition, allowing a data unit in the high priority queue to be transmitted in a subsequent time slot.

13. The system of claim 12, further comprising an up bus and a down bus, wherein the up bus and down bus are unidirectional buses, wherein the arbiter is operable to transmit the plurality of data units to corresponding destination components on the down bus, and wherein the plurality of components send the plurality of data units to the arbiter on the up bus.

14. The system of claim 13, wherein the scheduler comprises a counter and increments the counter when a data unit is available in the low priority queue when a data unit from the high priority queue is transmitted, wherein the predetermined condition comprises the counter equal to a second predetermined number of attempts, and wherein clearing the predetermined condition comprises resetting the counter to a third predetermined value.

15. The system of claim 14, wherein the arbiter is operable to receive corresponding requests from the plurality of components for the up bus, the arbiter further operable to grant the up bus to only one of the plurality of components in a time slot, and wherein the granted component transmits a corresponding data unit to a queuing block of the arbiter for storing the corresponding data unit in one of the high priority queue and the low priority queue in the granted time slot.

16. The system of claim 15, further comprising a clock generator to generate a clock signal, the clock signal having a plurality of successive cycles, each time slot corresponding to one of the plurality of successive cycles.

17. The system of claim 16, wherein the plurality of components are configured to request retransmission by asserting a corresponding one of retransmit request lines, wherein the arbiter examines the retransmit line of the destination component to determine whether to retransmit the first data unit.

18. The system of claim 17, wherein the plurality of components comprises a random access memory (RAM), a processor, a bridge and a graphics controller.