Arbitration

Introduction

The goal here is to uniquely select a bus controller.

Non-Pre-Emptive Arbitration: Once a controller a bus it will continue to use the bus until completion. Some specific structures place limits on the maximum cycles or time that a controller can keep a bus. This is not considered in this course.

I.E Devices can’t change their mind, we can’t force action

3-Wire Daisy Chain

Some Terminology

Central Arbiter: The component of the system that detects and grants a bus request (Someone can use the us or not).
Distributed Arbiter: The component of the system that is repeated in each device interface that must become a bus controller at some point in time (Each thing that can be a controller needs one of these, this is the middleman that handles its device becoming the controller).

The CPU is at the end of the daisy chain and thus, has the lowest priority. This keeps the CPU from starving the other bus controllers.

Three wire daisy-chain arbitration systems use two passive pull-up bus lines (bus request and bus busy) and one daisy-chained signal

The Central Arbiter

This asserts ${\text{BusGrant}}_0$ whenever BusBusy is not asserted and BusRequest is asserted
$BusGran{t}_0=BusBusy\cdot \overline{BusRequest}$
There is a finite delay through the central arbiter $t_{CA}\ne 0$

The Distributed Arbiter

The local grant is strictly between the distributed arbiter and its associated device.
Outputs of this arbiter are a function of both inputs and state.
This arbiter circuit is implemented as an asynchronous design.

Once again, there is a finite delay through the distributed arbiter $t_{CA}\ne 0$

Design of the Distributed Arbiter

When a DA wants to use the bus, pulls /BusRequest low to request service.

This arbiter takes control of the bus when it sees a rising edge on the bus grant signal, when the bus is not busy, and the distributed arbiter has a local request.

The distributed arbiter associated with the interface using the bus, pulls /BusBusy low to indicate usage.

The Diagram of Daisy Chain Arbitration

See Learn for the associated ladder diagram but in general:

1. Assert the request
2. Assert /BusRequest
3. Assert Bus Grant 0
4. Assert Grant 1 and /BusBusy
5. Deassert Bus Grant 0
6. Deassert the request
7. Deassert Grant 1 and /BusBusy

Notes For Diagrams

• You can tell which device gets the bus first, because its BusRequest will turn off first
• The Request line causes BusRequest to go low which causes BusGrant to go high for the device which in turn, causes the local Grant line and BusBusy for all the other devices to go high and then it causes BusRequest to go low
• When BusBusy goes low, it causes BusGrant to go low
• When Request goes low, it causes Grant to go low
• To release the bus, the device deasserts Request which causes BusBusy to go high and then it deasserts Grant and then another device can take over the bus

*Note that things propagate here, where one time step is our propagation time, also remember that things are daisy chained here so we will see BusGrant propagate to whatever device made the request to be granted

Priority Uncertain

Once a token has been passed you can’t change your mind, you have to wait. This causes our strict priority order to be broken. This is the same idea as priority inversion in OS.

Quantitatively, if device n makes a request and then device i requests the bus more than $t_{\text{uncertainty}}$ before device n should receive the bus grant where $i\le n$ then priority is obeyed.

Bus Idle

The timing of bus requests is crucial in determining which interface becomes the bus controller. Essentially, if a high priority interface makes a request after the critical time, a lower priority interface may gain control instead.

Monolithic Arbitration System

Basically we just encapsulate the arbitration system and expose the local bus requests and grants.

Non-Daisy-Chained Bus Arbitration Systems

Essentially here, only one bus grant signal is asserted, once a device has the bus it can’t be preempted.

For this system to work, we have an open drain driver in the bus arbiter paired with a pull-up resistor and an active low bus line to avoid conflicts.

$\overline{ID}$s end up on the DMA lines where higher IDs in this case indicate higher priority where 0000 is reserved for an idle bus.