Multiplex communications – Channel assignment techniques – Polling
Reexamination Certificate
1999-02-02
2004-03-02
Pham, Chi (Department: 2667)
Multiplex communications
Channel assignment techniques
Polling
C370S461000
Reexamination Certificate
active
06700899
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 scaleable arbiter circuit providing high performance characteristics for use in electronic systems.
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 or memory unit. 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.
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 round robin arbitration, is slightly more complex to implement than fixed priority arbitration. However, round robin arbitration provides the advantage of uniform resource allocation. As a result, the latency imposed on the requesting agents is generally uniform since each requesting agent is provided access to the resource before another agent regains access to the resource.
In many types of electronic systems, an arbitration system must be able to quickly respond to and resolve a large number of agents competing for access to a single resource. One example of a system requiring a high performance arbiter circuit is a network switch. As the number of competing agents increases, the performance of a typical prior art arbitration system decreases, and latencies are incurred. It often becomes necessary for arbiters employing typical prior art arbitration schemes to arbitrate in multiple cycles.
What is needed is an arbiter circuit which provides enhanced performance characteristics, and therefore minimal arbitration latency.
What is also needed is an arbiter circuit wherein the number of requests which may be resolved by the circuit is easily scaleable without incurring much cost.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a high performance arbiter circuit 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 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 includes an arbiter circuit for resolving a plurality of N request signals received from a plurality of agents requesting access to a resource. The arbiter circuit includes: a token distribution circuit responsive to a first clock signal defining a grant cycle, and providing a plurality of token priority signals each corresponding with one of the agents, the distribution circuit being operative to prioritize one of the agents at the beginning of each the grant cycle by asserting the token priority signal corresponding with the prioritized agent; means forming a token ring; and a plurality of N grant devices coupled together by the token ring, each of the grant devices corresponding with an associated one of the agents and being responsive to the corresponding request signal provided by the associated agent, and also being responsive to the token priority signal corresponding with the associated agent, and being further responsive to a corresponding token carry signal, each of the devices being operative to provide a grant signal to its associated agent if the corresponding request signal is asserted and either the corresponding token priority signal or the corresponding token carry signal is asserted.
In one embodiment, the token carry signal received by a particular one of the devices is provided by an adjacent one of the devices via the token ring means, and wherein the token carry signal received by the particular device is asserted by the adjacent device if the request signal received by the adjacent device is not asserted and either of the token priority signal or the token carry signal corresponding with the adjacent device is asserted.
In another embodiment, the token ring means includes a token look ahead device providing enhanced performance characteristics. In this embodiment, each of the grant devices is operative to generate a corresponding token propagate signal in response to the corresponding request signal, and is also operative to generate a corresponding token generate signal in response to the corresponding token priority signal and the corresponding request signal. The token look ahead device is operative to generate the token carry signals in a predictive manner in response to the token propagate signals and the token generate signals.
An important advantage of an arbiter circuit according to the present invention is that the maximum number of requests which may be resolved by the circuit is easily scaleable.
Another advantage of an arbiter circuit according to the present invention is that the operational speed may be enhanced by employing a look ahead carry circuit to arbitrate large numbers of requests in a minimum number of arbitration cycles.
The foregoing and other objects, features, and advantages of the present invention will be apparent from the following detailed description of the preferred embodiment which makes reference to the several figures of the drawing.
REFERENCES:
patent: 4726018 (1988-02-01), Bux et al.
patent: 5132965 (1992-07-01), Zhang
patent: 5216668 (1993-06-01), Zhang
patent: 5301333 (1994-04-01), Lee
patent: 5473604 (1995-12-01), Lorenz et al.
patent: 5566177 (1996-10-01), Bhandari et al.
patent: 5640519 (1997-06-01), Langendorf et al.
patent: 5872936 (1999-02-01), Eckstein
patent: 5890001 (1999-03-01), Hall
patent: 5910954 (1999-06-01), Bronstein et al.
patent: 6076132 (2000-06-01), Chen
patent: 6246692 (2001-06-01), Dai et al.
patent: 6269418 (2001-07-01), Nakamura
Boakye Alexander O.
Broadcom Corporation
Pham Chi
Squire Sanders & Dempsey L.L.P.
LandOfFree
Bit slice 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 Bit slice arbiter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bit slice arbiter will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3200320