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

# 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
```

### 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
]
.
```

## 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

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

[Zoom|FIG]
2. 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]