RGDA Arbiter

Specifications

Informal

An RGDA Arbiter is a handshake component with four 2-phase handshake ports, two passive (a_0, a_1) and two active (b_0, b_1). Each handshake on a_i encloses one handshake on b_i. Handshakes on b_0 and b_1 are mutually exclusive (no overlapping request-acknowledge intervals); handshakes on a_0 and a_1 may overlap arbitrarily.

RGDA stands for Request (a_i.r), Grant (b_i.r), Done (b_i.a), and Acknowledge (a_i.a). The individual terminals are also referred to as r_i (request), g_i (grant), d_i (done), and a_i (acknowledge).

When an RGDA Arbiter receives two requests, it will grant exactly one of them (and delay the other). The specification leaves the choice open. Often there is a fairness requirement on this choice: if a choice situation arises `infinitely often' then both outputs are chosen `infinitely often'.

XDI

Schematic diagram for an RGDA Arbiter:

[Zoom|FIG]

XDI state graph for an RGDA Arbiter:

[Zoom|FIG]

Specification in XDI model.

Verdect

Specification in Verdect:


define RGDA( r0?, g0!, d0?, a0!, r1?, g1!, d1?, a1! ) =
       pref *[ r0?; g0!; d0?; a0! ]
   ||  pref *[ r1?; g1!; d1?; a1! ]
   ||  pref *[ g0!; d0? | g1!; d1? ]
end

Also available through this link

DI Algebra

Specification in DI Algebra:


NAME = (RGDA Arbiter)
I = { r0, d0, r1, d1 }
O = { g0, g1, a0, a1 }

RGDA = [ r0? -> g0! ; [ d0? -> a0! ; RGDA, d1? -> CHAOS, r0? -> CHAOS ],
         r1? -> g1! ; [ d1? -> a1! ; RGDA, d0? -> CHAOS, r1? -> CHAOS ],
         d0? -> CHAOS, d1? -> CHAOS
       ]
.

Also available through this link

Properties

XDI Report.

The subscripts 0 and 1 can be interchanged systematically:
RGDA(a_0, a_1; b_0, b_1) = RGDA(a_1, a_0; b_1, b_0)

An RGDA Arbiter is not output deterministic, since there is an output choice in state 5. The output nondeterminism is dynamic.

Implementations

DI Decompositions

An RGDA Arbiter can be implemented by an RGD Arbiter and two Forks (not equ):

[Zoom|FIG]
An RGDA Arbiter can be implemented using a Mutual-Exclusion Element, two Merges, and two Toggles (not equ):

[Zoom|FIG]

Using Boolean Gates

No information available

Using Transistors

No information available

Generalizations

The RGDA Arbiter can be generalized to a m-rgda-arbiter, which arbitrates between m passive ports.

Generalizations involving data on return (done/acknowledge) path. Relationship to Interlock Macromodule.

Miscellaneous

In Section 2.2.8 of [Ebergen89, p. 33], the RGDA Arbiter is referred to as ARB component.

Sometimes useful: Input demanding (w.r.t. `done') when resource is granted (states 6 and 9) to help guarantee release of the resource.

Fairness issue.

References

[Ebergen89, p. 33]

RGDA Arbiter

Informal

DI Decompositions

Using Boolean Gates

Using Transistors

Last modified at Fri Nov 20 10:11:41 1998