Electrical computers and digital data processing systems: input/ – Intrasystem connection – Bus access regulation
Reexamination Certificate
2000-10-05
2003-11-11
Auve, Glenn A. (Department: 2189)
Electrical computers and digital data processing systems: input/
Intrasystem connection
Bus access regulation
C710S240000
Reexamination Certificate
active
06647449
ABSTRACT:
The present invention generally relates to an improved system, method and circuit for performing round robin arbitration. More specifically, it relates to a round robin arbitration system, method and circuit that includes a conditional request masking logic.
Round robin arbitration is generally known and used in the art as a method for resolving contending requests for service access and data transfer over computer networks. It is very common for multiple resources to compete for access and control at any given cycle. As a result, a round robin arbitration circuit is used to arbitrate and determine which one of the resources should be selected. The round robin arbiter is a circuit having a scheduling algorithm, which fairly distributes access to the resources.
Turning to
FIG. 1
, an overall architectural view of the implementation for a prior round robin arbitration implementation is shown. It is well known in the art that round robin arbiters are generally built using two major elements, a barrel shifter
10
and a priority encoder
12
. The barrel shifter is a hardware device that shifts or rotates a data word by any number of bits in a single operation. More specifically, the barrel shifter
10
generally shifts the bits of an input request vector
14
by a number of bit positions specified by the control input, wherein the barrel shifter wraps the bits shifted off one end of the request vector back into the other end. The input request vector contains multiple requests for that cycle, and each request is one bit on the vector. An input request vector with four requests looks like “1011”.
The barrel shifter
10
is generally used to rotate the input request vector according to the most recently serviced request so that the next eligible request is in the first bit position and outputted to the priority encoder
12
. After that step, the priority encoder
12
selects the first active request from the rotated vector to an adder
16
to combine the most recently serviced request with the result from the priority encoder
12
, and the request selection
18
is outputted and stored in a storage element
20
as the new, most recently serviced request for the next cycle.
One problem with the prior method is that the round robin algorithm for selecting the next service request is implemented by a functional element, specifically the barrel shifter
10
and an adder
16
. Because of the use of the barrel shifter
10
and the adder
16
, the prior method is implemented with more logic gates as a result of the shifting of the bits in the input request vector. Consequently, a longer propagation delay is needed to process each cycle.
Accordingly, a primary object of the present invention is to provide an improved system and method for a round robin arbitration that has a shorter propagation delay while requiring fewer logic gates.
Another object of the present invention is to provide an improved system and method for a round robin arbitration that can be implemented with fewer hardware devices.
Yet another object of the present invention is to provide an improved system and method for a round robin arbitration that is very efficient.
A further object of the present invention is to provide an improved system and method for a round robin arbitration that can be implemented with lower costs.
Other objects, features and advantages will become apparent upon reading the detailed description set forth herein, in conjunction with the attached drawings.
BRIEF SUMMARY OF THE INVENTION
The present invention generally relates to an improved system, method, and circuit for a round robin arbitration. More specifically, it relates to a system, method and circuit for a round robin arbitration that includes a conditional request masking logic.
The present invention provides an improved system, method and circuit for a round robin arbitration, which includes an input operable to receive a plurality of requests, a conditional request masking logic to selectively send the plurality of requests to a priority encoder, a priority encoder to output a request from the selected plurality of requests from the conditional request masking logic for servicing, and a storage element to store the most recently serviced request. The conditional request masking logic sends any request from the plurality of requests that has a lower priority according to said priority encoder than the most recently serviced request if such a request exists, otherwise all requests are sent to the priority encoder.
REFERENCES:
patent: 5095460 (1992-03-01), Rodeheffer
patent: 5568485 (1996-10-01), Chaisemartin
“Positional Bus Arbitration Scheme”, IBM Technical Disclosure Bulletin, vol. 34, Issue No. 10A, pp. 20-24, Mar. 1, 1992.
Auve Glenn A.
Hewlett--Packard Development Company, L.P.
Vu Trisha
LandOfFree
System, method and circuit for performing round robin... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System, method and circuit for performing round robin..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System, method and circuit for performing round robin... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3172419