Electrical computers and digital data processing systems: input/ – Access arbitrating
Reexamination Certificate
1999-11-02
2003-09-30
Vo, Tim (Department: 2181)
Electrical computers and digital data processing systems: input/
Access arbitrating
C710S309000, C710S100000
Reexamination Certificate
active
06629176
ABSTRACT:
BACKGROUND
The present invention concerns arbitration within a computing system and pertains specifically to an arbiter architecture that allows rapid implementation of arbitration policies.
Within computer systems it is often necessary to allocate limited resources using some sort of arbitration scheme. For example, arbitration is used to allocate access to resources such as memory, networks, interfaces, busses and so on. Arbitration policies determine winners based on system criteria such as requester need, requester priority and system fairness.
Typically, arbiters are individually designed with logic dependent upon the specific arbitration policies implemented. Arbiters are often in a critical timing path. Early estimates of logic complexity help enable complexity verse speed tradeoffs.
When performing arbitration, some bus protocols, for example the I
2
C bus protocol, use Carrier Sense Multiple Access/Collision Detect (CSMA/CD) for arbitration. See the I
2
C-Bus Specification, Version 2.0, December 1998 (available from Philips Semiconductor, Inc., or on the internet at “http://www-us2. semiconductors.philips.com/acrobat/various/ I2C_BUS_SPECIFICATION
—
2.pdf”, pp. 12-13. The Ethernet protocol also uses CSMA/CD. In CSMA/CD arbitration scheme requesters are not synchronized.
The CAN bus protocol uses Carrier Sense Multiple Access/Collision Detect and Arbitration on Message Priority (CSMA/CD+AMP). In this arbitration scheme the identity (ID) numbers are used during arbitration.
SUMMARY OF THE INVENTION
In accordance with the preferred embodiment of the present invention, an arbiter allocates resources to a set of requesters. The arbiter includes vector assembly logic and sort logic. The vector assembly logic generates, for each arbitration round, an arbitration vector for each requester in the set of requesters. The sort logic receives the arbitration vectors generated by the vector assembly logic. Based on values of the arbitration vectors, the sort logic designates, for each arbitration round, a requester from the set of requesters as winner.
For example, for each arbitration round, the requester from the set of requesters that is designated as the winner is the requester that has a highest arbitration vector value.
In one embodiment of the present invention a simple round robin arbitration policy is implemented. The vector assembly logic includes a counter that generates a count. A decoder receives the count and generating for each requester a single bit arbitration value as the arbitration vector.
In another embodiment of the present invention, a round robin arbitration policy with a right of refusal is implemented. In this case, a counter generates a count. Assembly logic receives the count and receives a ready bit from each requester in the set of requesters. The assembly logic generates for each requester a multiple bit arbitration value as the arbitration vector.
In another embodiment of the present invention, requester priority arbitration policy with tie-breaking capability is implemented. The vector assembly logic includes a counter that generates a count. The assembly logic receives the count and receives a priority vector from each requester in the set of requesters. The assembly logic uses the priority value and the count to generate a multiple bit arbitration value as the arbitration vector. Alternately, both the counter and a ready bit from each requester may be used for tie-breaking.
The bifurcated architecture of the arbiters set out in various embodiments of the present invention allows for rapid implementation of a variety of arbitration policies.
REFERENCES:
patent: 5067071 (1991-11-01), Schanin et al.
patent: 5509125 (1996-04-01), Johnson et al.
patent: 6157989 (2000-12-01), Collins et al.
patent: 6199124 (2001-03-01), Ramakrishman et al.
I2C-Bus Specification, Version 2.0, Dec. 1998 (available from Philips Semiconductor, Inc., or on the internet at “http://www-us2.semiconductors.philips.com/acrobat/various/I2C_BUS_SPECIFICATION_2.pdf”, pp. 12-13.
Agilent Technologie,s Inc.
Vo Tim
LandOfFree
Arbiter architecture allowing rapid implementation of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Arbiter architecture allowing rapid implementation of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arbiter architecture allowing rapid implementation of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3039819