Electrical computers and digital data processing systems: input/ – Intrasystem connection – Bus access regulation
Reexamination Certificate
1999-12-28
2003-02-04
Myers, Paul R. (Department: 2781)
Electrical computers and digital data processing systems: input/
Intrasystem connection
Bus access regulation
C370S448000
Reexamination Certificate
active
06516369
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to arbitration in computer systems. More particularly the invention is directed to an arbitration system and method based on a dual rotative and weighted priority scheme for arbitrating access of shared resources to a common bus.
BACKGROUND OF THE INVENTION
In high speed telecommunication networks wherein a plurality of resources share a common bus, arbitration of the requests to access the bus is a critical operation that must insure fairness and be accomplished in a minimum time cycle. Mainly two types of arbiters have been implemented to reach both or either one of these goals. In a first type, which is generally called a linear arbitration, a fixed priority value is associated to each resource and the highest priority requester may prevent access to the bus by the lower priority requesters until it has relinquished control of the bus. This technique suffers the drawback of being unfair. The other general type of arbitration system allows that each requesting device may gain access to the bus in an equitable manner. Several circuit architectures allow this fairness priority arbitration. In the round robin design, the arbiter scans through the input devices as long as an active requester is reached. The time arbitration increases directly with the number of input devices. Moreover, once an active requester is reached, a weighted priority value is computed for it and thus the fairness of the arbitration depends on the design of the priority algorithm. In case of a high number of input devices, the circuits implementation of the priority algorithm is of a large scale.
U.S. Pat. No. 5,519,837 describes a pseudo-round-robin arbiter comprising a multiplicity of arbiter cells for arbitrating among a plurality of requests. The requests are combined in various groupings and simultaneously provided to all the cells which are organized as a multiple levels hierarchy. The outputs of the higher level cells serve as enablements to successively related lower level cells in progression by level. The arbiter cells also receive inputs from respective token lines to initiate control of the grant signals. This type of hierarchical grouping allows that the time delay attributed to arbitrating requests grows logarithmically with the number of requesters; but, on the other hand, the arbitration priority is given to the group which is preliminarily selected by the token bit over the other groups, thereby leading to a less fair design than a flat arbitration scheme, wherein each input request is processed with the same priority value.
Therefore, the present invention is directed towards solving the aforementioned problems. Accordingly, it would be desirable to be able to provide a fair, compact and high speed arbiter.
It is an object of this invention to provide a fair and high speed arbitration circuit for use in connection with based bus systems.
It is another object of the invention to provide such arbiter operating with a fixed priority scheme.
Still further, it is an object of the invention to provide a method for arbitrating access of a plurality of resources to a common bus.
SUMMARY OF THE INVENTION
According to the present invention, a mixed rotative and weighted arbiter is provided. The arbiter is composed of a token circuit which delivers a token vector having one position set active. The token vector as well as a plurality of request signals supplied by requesting devices are input to a rotative arbitration circuit. The rotative arbitration circuit processes a round robin algorithm to output a rotative request vector having input requests ordered from a higher to a lower priority configuration according to the active position of the token vector. The arbiter further comprises a weighted arbitration circuit connected to the output of the rotative arbitration circuit for generating a weighted request vector determining a linear priority configuration of the rotative request vector. A grant generation circuit is connected to the output of the weighted arbitration circuit and to the output of the token circuit to deliver a grant order to the device which may gain access to the bus and a plurality of no grant orders to the others devices.
In the preferred implementation, a token confirm vector is generated simultaneously to the grant order. The token confirm vector which represents the grant
o grant orders configuration is sent to the token circuit to update the content of the cells. The active position which may be the same or a different one than for the previous token vector is shifted to the next position in order to change the priority for the next arbitration cycle.
REFERENCES:
patent: 5519837 (1996-05-01), Tran
patent: 5526496 (1996-06-01), Alnuweiri
patent: 5745708 (1998-04-01), Weppler et al.
patent: 6032218 (2000-02-01), Lewin et al.
patent: 6199124 (2001-03-01), Ramakrishnan et al.
patent: 6653618 (2002-03-01), Hung et al.
patent: 6420901 (2002-07-01), Liu et al.
Dougherty Anne Vachon
Jordan Kevin M.
Myers Paul R.
LandOfFree
Fair and high speed arbitration system based on rotative and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fair and high speed arbitration system based on rotative and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fair and high speed arbitration system based on rotative and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3160200