Sharing arbiter

Details Sharing arbiter Sharing arbiter

2000-09-20

2004-01-06

Auve, Glenn A. (Department: 2189)

Electrical computers and digital data processing systems: input/

Access arbitrating

C710S107000, C710S113000, C710S119000, C710S309000, C710S241000, C710S242000, C710S243000, C710S244000

Reexamination Certificate

active

06675246

ABSTRACT:

BACKGROUND OF THE INVENTION
Embodiments of this invention relate to the subject of arbitration in electronic circuits, and particularly to arbitration in asynchronous systems.
Because events in asynchronous systems may occur at any time, it is often necessary to choose an action that depends on which of two, or more, sometimes nearly simultaneous events is to be treated first. Devices that make such choices are commonly called arbiters. Arbiters are often used in situations where most of the time the two input events arrive with a relatively large time separation, and it is then easy to make a clean decision as to which event arrived first—we call this situation “an uncontested input request”. Only infrequently do the two input requests arrive nearly simultaneously, and it is in these circumstances that the arbiter really has to work for a living and make a clean decision as to which input has arrived first.
A block diagram of a typical arbiter is shown in
FIGS. 1A and 1B
. The arbiter of
FIG. 1A
has five terminals and is therefore sometimes called a “five-wire” arbiter. It is often used to sequence events and so is frequently called a “Sequencer arbiter” or “Sequencer”. The Sequencer arbiter receives signals on the two request inputs R
1
, R
2
and issues signals on the two grant outputs G
1
, G
2
. The arbiter also receives signals on the “Done” input D.
Many different encodings of the input and output signals of arbiters are possible. For example, each rising transition of an electrical voltage on a wire might be used to signal the event. The signal could also be encoded as a falling transition, or any other change in a voltage, current, light level or similar phenomena. Electrical or other forms of pulses may also be used to encode events.
However the signal is encoded, the arbiter monitors the request inputs and, when a signal is received on one request input, the arbiter sends a signal on the corresponding grant output, unless a grant is already outstanding. A grant is outstanding when one grant signal has been issued but a Done signal has not been received. Where two request signals are received substantially simultaneously, the arbiter unambiguously chooses one of the requests and issues a grant signal on the grant output corresponding to the chosen request. When a Done signal is received, a grant for the unchosen request is issued.
In this way, an arbiter can arbitrate contending accesses to a resource. Two principal forms of arbiter known in the art are the Sequencer arbiter and the RGD arbiter.
The first form of prior art arbiter, the Sequencer arbiter, mentioned above is sometimes also called a “Sequencer”. The communication channel between the Sequencer arbiter and each of its users has a pair of event signals called Request and Grant, and a common Done event signal is shared by all of the users. For two channels, a Sequencer arbiter has five connections and is sometimes referred to as a “five-wire” arbiter, as explained above. A typical Sequencer arbiter is shown in FIG.
1
A. Herein we refer to the five event signals of a Sequencer arbiter as R
1
, G
1
, R
2
, G
2
and D.
The second form of prior art arbiter is the Request, Grant, Done (RGD) arbiter. As its name implies, the communication channel between the RGD arbiter and each of its users has three event signals called Request, Grant and Done, on each of its channels. An RGD arbiter that arbitrates among two channels will have six event signals, three for the first channel of communication (R
1
, G
1
, D
1
), and three for the second channel of communications (R
2
, G
2
, D
2
). The numerical designation identifies the communication channel, and thus the user.
The dot by the D input in
FIG. 1A
is used to indicate the initial state of the arbiter and signifies that the arbiter is initialized as if an input has been received on the D input.
FIG. 1B
shows an RGD arbiter. The dot between the D
1
and D
2
inputs indicates that the arbiter is initialized as if a Done input event has been received on either input D
1
or input D
2
, and that upon the receipt of a request input the arbiter can issue a grant signal.
For both types of arbiters—Sequencer arbiters and RGD arbiters—the request event signals (R
1
and R
2
) and Done event signals (D or D
1
and D
2
) are input signals, while the grant event signals (G
1
and G
2
) are output signals.
The arbiter action in both the above prior art arbiters controls when the arbiter will issue grant signals. The intent of arbitration implies that the arbiter will issue only one grant signal “at a time.” In asynchronous systems, however, the notion of “at a time” must be made more explicit. For the RGD arbiter the conventional rule is that after issuing a grant signal G
1
in response to a request R
1
, the arbiter will issue no further grant signals, G
1
or G
2
, until it receives the Done signal D
1
. The Done signal indicates that whatever action was to occur on that first channel is complete. Thus for the RGD arbiter, after a first request R
1
on channel
1
, and after that channel is given a grant G
1
, a following request on channel
1
or a request on channel
2
the arbiter must wait for the Done signal D
1
before the arbiter can issue a grant signal, either a G
1
or a G
2
respectively. This second grant signal is delayed until channel
1
has finished its action in response to the first grant signal on channel
1
and so indicated via the Done signal D
1
. For the Sequencer arbiter the rule is similar. In the Sequencer arbiter, however, both channels indicate completion with the same common Done signal D. Because only one channel can have an outstanding grant, there is no ambiguity, upon receipt of a Done signal D, regarding which channel indicated a completion.
The Sequencer arbiter and the RGD arbiter are closely related. It is known that one can build a Sequencer arbiter using an RGD arbiter (in addition to other components well known in the art) and vice versa.
Basic to most forms of arbiter is a mutual exclusion (ME) element. The mutual exclusion element is a circuit that executes the RGD arbiter function using a particular communication protocol—four-phase, return to zero signaling. A mutual exclusion element for a two-channel arbiter has two input terminals and two output terminals, with one input terminal and one output terminal associated with each channel. For the first channel, a rising transition on its input terminal signifies request, R
1
, and a falling transition on that same terminal signifies Done, D
1
. The ME element signals a corresponding grant with a rising transition on its G
1
output channel. A falling transition on the G
1
output channel has no significance. Thus, the mutual exclusion element is an RGD arbiter with a particular encoding of communication signals. Mutual exclusion elements commonly form the basis for RGD and Sequencer arbiters that use other communication protocols. The mutual exclusion element is not only a basis for RGD and Sequencer arbiters, but is also useful as a basic element in synchronizers. A synchronizer captures the value of an external signal for use in a synchronous system, ensuring that the captured form of the external signal remains stable during the interval in each clock cycle during which stability is required. The art of designing synchronizers and mutual exclusion elements is well known. See, for example, “Introduction to VLSI Systems”, Chapter 7 [FIG. 7.25 and pages 260-61 in particular] (1980), which is incorporated herein by reference for all purposes.
Arbiters are used to make choices that depend upon the order in which requests reach the arbiter. For example, arbiters can be used to implement a “first-come, first-served” policy for sequencing access to a common resource. In a typical implementation, a second requester will not be issued a grant signal until service of a first grant to a first requester is complete, as indicated by the receipt of a Done signal.
The behavior of the Sequencer arbiter shown in
FIG. 1
can be represented by the eight-state diagram shown in FIG.

Affiliated with

Also associated with

Rating

Sharing 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 Sharing arbiter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sharing arbiter will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3267007