EDIS: Guide | FAQ | New | Search | Bibliography | Index | Feedback

RGDA Arbiter



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'.


Schematic diagram for an RGDA Arbiter:


XDI state graph for an RGDA Arbiter:


Specification in XDI model.


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? ]
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


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.


DI Decompositions

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

  2. An RGDA Arbiter can be implemented using a Mutual-Exclusion Element, two Merges, and two Toggles (not equ):


Using Boolean Gates

No information available

Using Transistors

No information available


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.


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.


[Ebergen89, p. 33]

Last modified at Fri Nov 20 10:11:41 1998
Encyclopaedia of Delay-Insensitive Systems
Copyright © 1995-1998 Tom Verhoeff / Tom.Verhoeff@acm.org