Priority Based Bus Arbiters Avoiding Deadlock And Starvation On Buses That Support Retrying Of Transactions

• US 20100095036A1
• Filed: 10/14/2008
• Published: 04/15/2010
• Est. Priority Date: 10/14/2008
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Kanuri, Mrudula, Mittal, Aditya, Malladi, Venkata
• Granted Patent: US 8,370,552 B2
• Time in Patent Office: Days
• US Class Current: 710/117
• 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. A system comprising:

a plurality of components to form a plurality of data units, each data unit being destined to a corresponding one of said plurality of components, a destined component being designed to request retransmission of a data unit;

an arbiter to receive said plurality of data units and to transmit each data unit to a corresponding destined component on a first bus, said arbiter comprising;

a memory to store a high priority queue and a low priority queue;

a queuing block to store each of said plurality of data units in either said high priority queue or said low priority queue; and

a scheduler to transmit data units in said high priority queue with a higher priority compared to data units in said low priority queue,

in a time slot, said scheduler to determine a starvation condition for said low priority queue and to cause a first data unit in said low priority queue to be transmitted on said first bus when said starvation condition is present,

said scheduler to retransmit said first data unit only a first pre-specified number of times on said first bus, and then clearing said starvation condition even if said first data unit is not accepted by a corresponding destined component such that any data units in said high priority queue can be sent in a subsequent time slot.

2. The system of claim 1, further comprising an up bus and a down bus, each being a unidirectional bus, said down bus comprising said first bus, and wherein said plurality of components send said plurality of data units to said arbiter on said up bus.

3. The system of claim 2, wherein said scheduler is designed to maintain a starvation counter and increment said starvation counter if data unit is available in said low priority queue when a data unit from said high priority queue is transmitted, wherein said starvation condition comprises said starvation counter being equal to a second pre-specified number,

wherein clearing said starvation counter comprises resetting said starvation counter to a third pre-specified value.

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

5. The system of claim 4, further comprising 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.

6. The system of claim 5, wherein each of said plurality of components is designed to request retransmission by asserting a corresponding one of retransmit request lines, wherein said arbiter examines the retransmit line of said destined component to decide to retransmit said first data unit.

7. The system of claim 6, wherein said plurality of components comprise a random access memory (RAM), a processor, a bridge and a graphics controller.

8. An arbiter for use in a system with a first unidirectional bus, said system further comprising a component designed 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;

a scheduler to determine which of said queues is to be allocated each of a sequence of time slots, said scheduler to provide higher priority for said low priority queue upon occurrence of a starvation condition for said low priority queue and to said high priority queue otherwise,

said scheduler to retransmit a first data unit in said low priority only a pre-specified number of times in successive time slots before clearing said starvation condition.

9. The arbiter of claim 8, wherein said scheduler is designed to maintain a starvation counter and increment said starvation counter if 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 starvation condition comprises said starvation counter being equal to a second pre-specified number,

wherein clearing said starvation counter comprises resetting said starvation counter to a third pre-specified value.

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

11. The arbiter of claim 10, wherein said system further comprising 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.

12. The arbiter of claim 11, wherein each of said plurality of components is designed to request retransmission by asserting a corresponding one of retransmit request lines, wherein said scheduler is designed to examine the retransmit line of said destined component to decide to retransmit said first data unit.

13. A method implemented in an arbiter associated with a unidirectional bus, 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 each of a sequence of time slots, wherein said determining comprises providing higher priority for said low priority queue upon occurrence of a starvation condition for said low priority queue, and for said high priority queue otherwise;

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

retransmitting said first data unit on said upon receiving said retransmit request, wherein said first data unit is transmitted only a pre-specified number of times in successive time slots before clearing said starvation condition.

14. The method of claim 13, further comprising:

initializing a starvation counter to a start value;

incrementing said starvation counter if 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 starvation condition comprises said starvation counter being equal to a second pre-specified number,

wherein clearing said starvation counter comprises resetting said starvation counter to said start value.

15. The method of claim 13, 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.

16. The method of claim 13, further comprising:

initializing a transmit counter to an initial value;

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

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

setting said starvation counter to said start value if said transmit counter has reached said threshold value, thereby clearing said starvation condition.

17. The method of claim 13, wherein said pre-specified number equals 1.

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