Quantized queue length arbiter

Details Quantized queue length arbiter Quantized queue length arbiter

1999-11-29

2001-06-12

Tokar, Michael (Department: 2819)

Electronic digital logic circuitry

Multifunctional or programmable

Having details of setting or programming of interconnections...

C326S037000, C326S046000, C710S241000

Reexamination Certificate

active

06246256

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to a method and apparatus for resource arbitration in electronic systems. More specifically, the present invention relates to a method and apparatus for resolving requests between a plurality of queues based on a number of data packets currently enqueued at each queue.
2. Description of the Prior Art
In many different types of electronic systems, multiple agents including hardware units and software modules compete for access to a single resource such as an interconnect bus, memory unit, or output buffer. For example, in computer systems, multiple agents may simultaneously request access to a memory device. As another example, in network switches, multiple agents may simultaneously request access to a routing resource such as a packet routing address look up table or a network output port. In such systems, agents generally issue resource requests to gain exclusive access to the resource for a period of time. Such systems require means for arbitrating between the requests in order to determine which agent gains control of the resource when two or more agents are simultaneously competing for control of the resource.
Typically, electronic systems include an arbitration system for arbitrating between requests received from the multiple requesting agents, and for granting access to a selected one of the requesting agents. After one of the requesting agents gains access to the resource, it performs a particular operation and relinquishes access to the resource upon completion of the particular operation or expiration of the predetermined time period, whichever occurs first. However, as the number of competing agents requiring access to a resource increases, the performance of a typical arbitration system decreases, and latencies are incurred.
There are a number common types of arbitration schemes used for implementing arbitration systems. In accordance with one types of arbitration scheme, called “fixed priority arbitration”, resource access is granted to a requesting agent having a highest priority. Thus, the highest priority agent is guaranteed to experience very low latency. However, the fixed priority arbitration scheme “starves” requesting agents assigned with a low priority when an agent assigned with the highest priority is frequently requesting access to the resource.
Another type of arbitration scheme, referred to as weighted round robin arbitration, is widely used for managing multiple priority queues. As an example, consider that four queues designated queue_
3
, queue_
2
, queue_
1
, and queue_
0
having different priorities are attributed initial weight values of 4, 3, 2, and 1 respectively. In this case, the queues will be considered in the sequence queue_
3
, queue_
2
, queue_
1
, queue_
0
, queue_
3
, queue_
2
, queue_
1
, queue_
3
, queue_
2
, queue_
3
. Therefore, queue_
3
has four tries for access to the resource, queue_
2
has three tries, queue_
2
has two tries, and queue_
1
has a try. In varying prior art weighted round robin arbitration methods, the initial weight values are programmed by software or fixed after power up of the arbiter system.
What is needed is an arbiter system which provides enhanced performance characteristics, and therefore minimal arbitration latency in resolving requests between a plurality of N queues requiring access to a resource.
What is also needed is an arbiter system which provides fast and fair arbitration for resolving requests between a plurality of N queues requiring access to a resource.
Further needed is an arbiter system which provides improved load balancing in resolving requests between a plurality of N queues requiring access to a resource.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a high performance arbiter system for use in electronic systems, the arbiter circuit providing a high operating frequency, and therefore minimal arbitration latency.
It is another object of the present invention to provide an arbiter system for use in an electronic system including a plurality of queues competing for access to a resource, the arbiter system arbitrating between the queues based on queue lengths associated with the queues.
It is another object of the present invention to provide an arbiter circuit wherein the number of requests which may be resolved by the circuit is easily scaleable without incurring much cost.
Briefly, a presently preferred embodiment of the present invention provides a queue length arbiter system for selecting from a plurality of N queues requiring access to a resource. The arbiter system includes: an arbitration circuit; and a plurality of N weight circuits each being associated with a corresponding one of the queues, and being operative to store a corresponding weight count value, and also being operative to initialize the corresponding weight count value to a corresponding initial weight value determined based on a length value indicative of a number of data portions enqueued at the corresponding queue at an initial time, and being further operative to decrease the corresponding weight count value in response to a corresponding one of a plurality of N grant signals, and also being operative to generate a corresponding one of a plurality of N weight count signals, the corresponding weight count signal carrying the corresponding weight count value.
The arbitration circuit includes: a plurality of N weight checking circuits associated with corresponding ones of the queues, each of the weight checking circuits being operative to generate a corresponding one of a plurality of N select signals indicative of a corresponding selected one of the queues in response to each of the weight count signals, the corresponding selected queue being determined based on each of the weight count values; and a resolving circuit responsive to each of the select signals, and being operative to choose one of the weight checking circuits, and also being operative to provide the grant signals, the grant signals indicating a granted queue that is selected by the chosen weight circuit.
The arbiter system further includes a timing circuit operative to generate a load counter signal in response to the weight count signals, the load counter signal being indicative of the initial time, each of the weight circuits being responsive to the load counter signal. The timing circuit comprises logic for determining the initial time by determining whether each of the weight count values is equal to zero.
The arbiter system further includes: a plurality of N length determining circuits communicatively coupled with corresponding ones of the queues, each of the length determining circuits being operative to generate a corresponding length signal carrying a corresponding one of the length values, each of the weight count circuits being responsive to a corresponding one of the length signals; and a plurality of N weight determining circuits each being operative to generate a corresponding initial weight signal carrying a corresponding one of the initial weight values in response to a corresponding one of the length signals, the corresponding initial weight value being determined based on a corresponding one of the length values.
Each of the weight determining circuits further includes: a comparator circuit for receiving the corresponding length value, the comparator circuit being operative to generate a control signal indicative of whether the corresponding length value is greater than or equal to a maximum weight value; and a multiplexer having a first input for receiving the corresponding length value, a second input for receiving the maximum weight value, an output, and a select input for receiving the control signal, the multiplexer being operative to provide an output signal carrying the maximum weight value if the control signal indicates that the corresponding length value is greater than or equal to the maximum weight value.
Each of the weight checking circuits includes logic operative to determine whether each of

Affiliated with

Also associated with

Rating

Quantized queue length arbiter does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Quantized queue length arbiter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantized queue length arbiter will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2542329