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

RGD Arbiter



an RGD Arbiter has four input terminals (r_0, d_0, r_1, and d_1) and two output terminals (g_0 and g_1). For each i in {0,1}, signaling starts with r_i followed by a repetition of g_i then concurrently d_i and r_i. The intervals from g_0 to d_0 and from g_1 to d_1 are mutually exclusive (do not overlap).

RGD stands for Request (r_i), Grant (g_i), and Done (d_i).

When An RGD 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 RGD Arbiter:


XDI state graph for an RGD Arbiter:


Specification in XDI model.


Specification in Verdect:

define RGD( r0?, g0!, d0?, r1?, g1!, d1? ) =
       pref *[ r0?; g0!; ]
   ||  pref *[ r1?; g1!; ]
   ||  pref *[ g0!; d0? | g1!; d1? ]
Also available through this link

DI Algebra

Specification in DI Algebra:

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

RGD = [ r0? -> g0! ; [ d0? -> RGD, d1? -> CHAOS ],
        r1? -> g1! ; [ d1? -> RGD, d0? -> CHAOS ],
        d0? -> CHAOS, d1? -> CHAOS
Also available through this link


XDI Report.

The subscripts 0 and 1 can be interchanged systematically.

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


DI Decompositions

  1. An RGD Arbiter can be implemented using an enabled Sequencer and a Merge (not equ):

  2. An RGD Arbiter can be implemented using an RGDA Arbiter and two enabled Joins (equ):


Using Boolean Gates

No information available

Using Transistors

No information available


No information available


Sometimes useful: Input demanding when resource is granted (states 6 and 9) to help guarantee release.


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