Bus topologies and arbitration: Exercises — Hardware deep dive

These problems are graded from L1 (just recognise the idea) up to L5 (put everything together). Try each one first with the solution collapsed, then open it. Every symbol you meet here was built in the parent note — if a term feels new, re-read that note first.

Before we start, one quick shared picture. Everything below rests on three numbers:

The figure above is the mental model: a single lane (shared bus), a grid of switches (crossbar), and a timeline cut into slots (TDM). Keep it in view.

L1 — Recognition

Exercise 1.1 (L1)

A designer connects 4 peripherals to one common set of address+data+control wires. Only one peripheral can transfer at any instant. Name this topology and state, in one phrase, why only one transfer happens at a time.

Recall Solution

Topology: shared (parallel) bus. Why one at a time: all devices tap the same physical wires, so the bus uses time-division multiplexing — the single wire can hold only one voltage pattern at a moment, so exactly one transaction owns it.

Exercise 1.2 (L1)

Match each phrase to a topology: (a) "matrix of switches, simultaneous master–slave pairs", (b) "each device has its own dedicated link to a switch", (c) "local buses joined by bridges into a tree".

Recall Solution

(a) Crossbar
(b) Point-to-point (e.g. PCIe)
(c) Hierarchical / tree bus

L2 — Application

Exercise 2.1 (L2)

A shared bus has total bandwidth $B = 132 MB/s$ . Under heavy contention it is split evenly among $N = 6$ masters. What is the per-master bandwidth?

Recall Solution

Even split means each master gets $B / N$ : $\frac{132}{6} = 22 MB/s per master.$ Why divide? The wire is time-shared; if everyone is equally busy, each owns $1/ N$ of the seconds, hence $1/ N$ of the bytes.

Exercise 2.2 (L2)

Build an $M \times S$ crossbar with $M = 5$ masters and $S = 4$ slaves. (a) How many switch points? (b) What is the maximum number of concurrent transactions?

Recall Solution

(a) Each master needs a path to each slave, so $switches = M \times S = 5 \times 4 = 20.$ (b) You cannot run more transactions than the smaller side allows (a slave serves one master at a time, and there are only $S = 4$ of them; likewise only $M = 5$ masters): $min (M, S) = min (5, 4) = 4 concurrent transactions.$

Exercise 2.3 (L2)

Round-robin arbiter, $N = 8$ masters, each transaction takes at most $T_{max} = 200 ns$ . What is the worst-case wait a master can experience before it is granted?

Recall Solution

A master that just missed its turn must wait for the other $N - 1$ masters: $T_{latency} \leq (N - 1) \cdot T_{max} = 7 \times 200 ns = 1400 ns = 1.4 μ s .$ Why $N - 1$ and not $N$ ? The master itself doesn't wait for its own turn — only for everyone ahead of it in the circle.

L3 — Analysis

Exercise 3.1 (L3)

Fixed-priority arbiter with masters ordered $M_{0} > M_{1} > M_{2} > M_{3}$ (highest first). Each transaction is $T_{transaction} = 100 ns$ . In the pathological worst case, how long can the lowest priority master $M_{3}$ wait, and what phenomenon does this illustrate?

Recall Solution

$M_{3}$ has $N = 3$ higher-priority masters. In the worst case they queue ahead one after another: $T_{worst} = \sum_{i = 0}^{N - 1} T_{transaction, i} = 3 \times 100 ns = 300 ns .$ But if the higher masters keep requesting, this repeats forever → the true worst case is unbounded. This is starvation: a low-priority master can be indefinitely denied. The $300 ns$ figure is only the delay per "round" of higher-priority traffic; there is no guaranteed ceiling.

Exercise 3.2 (L3)

Compare two arbiters for a system with an audio DMA (needs a sample every $22.7 μ s$ , one $100 ns$ transaction each) and a CPU hammering the bus continuously.

Arbiter A: fixed priority, CPU highest.
Arbiter B: round-robin, $N = 2$ , $T_{max} = 100 ns$ .

Which arbiter guarantees the audio DMA meets its deadline? Justify numerically.

Recall Solution

Arbiter A (fixed, CPU high): CPU never yields while it keeps requesting → audio DMA can wait unboundedly. Deadline of $22.7 μ s$ not guaranteed. Result: audible glitches.

Arbiter B (round-robin): worst wait for audio DMA is $(N - 1) \cdot T_{max} = 1 \times 100 ns = 100 ns .$ Since $100 ns ≪ 22.7 μ s$ , the deadline is always met with enormous margin.

Conclusion: Round-robin (or a TDM slot) is required. The "less important" master here is the latency-critical one — priority ≠ importance.

L4 — Synthesis

Exercise 4.1 (L4)

A SoC must connect 6 masters to 6 slaves. Two candidate fabrics:

Shared bus: single link, $B = 800 MB/s$ , cost $\approx 6 + 6 = 12$ tap points.
Full crossbar: each link $B_{link} = 800 MB/s$ .

Compute (a) crossbar switch count, (b) crossbar aggregate bandwidth, (c) the bandwidth speedup of crossbar over shared bus when all 6 masters talk to 6 distinct slaves.

Recall Solution

(a) $M \times S = 6 \times 6 = 36$ switches. (b) Aggregate $= min (M, S) \times B_{link} = 6 \times 800 = 4800 MB/s$ . (c) Shared bus delivers $800 MB/s$ total; crossbar delivers $4800$ . Speedup $\frac{4800}{800} = 6 \times .$ Cost trade: you paid $36$ switches vs $12$ tap points ( $3 \times$ hardware) for $6 \times$ bandwidth — the classic crossbar bargain, good until $M \cdot S$ grows too large.

Exercise 4.2 (L4)

TDM schedule of length $N = 10$ slots on a bus of raw bandwidth $B = 1000 MB/s$ . A video engine is assigned $n_{i} = 4$ slots. (a) What guaranteed bandwidth does it receive? (b) If a control CPU is assigned $1$ slot, what bandwidth does it get, and what is the key property TDM guarantees that round-robin does not?

Recall Solution

(a) $BW_{i} = \frac{n _{i}}{N} \cdot B = \frac{4}{10} \times 1000 = 400 MB/s$ . (b) CPU: $\frac{1}{10} \times 1000 = 100 MB/s$ . Key property: TDM gives each master a fixed, known-in-advance slot → its access time is deterministic (exactly when its slot comes round), with zero arbitration overhead during the slot. Round-robin's grant depends on who else is requesting, so timing is only bounded, not scheduled.

L5 — Mastery

Exercise 5.1 (L5)

A smartphone SoC has: 4 CPU cores, 1 GPU, 1 DMA engine, 1 camera ISP = 7 masters, and 3 slaves: DRAM controller, ROM, peripheral block = 3 slaves.

Requirements:

CPU↔DRAM and GPU↔peripheral must run simultaneously with zero interference.
Audio DMA (part of the DMA engine) must have bounded worst-case bus latency.
Die area is tight.

Design the interconnect: choose the topology, give the switch count, and pick an arbitration scheme per slave, justifying each choice against the three requirements. Then compute audio DMA's worst-case latency if DRAM's arbiter is round-robin over the (at most) 6 masters that touch DRAM, with $T_{max} = 150 ns$ .

Recall Solution

Topology — crossbar. Requirement 1 (simultaneous, non-interfering paths) forces independent point-to-point links per master–slave pair → that is a crossbar. A single shared bus would serialise CPU and GPU and fails requirement 1.

Switch count: $M \times S = 7 \times 3 = 21$ switches. Modest — satisfies requirement 3 far better than a $7 \times 7$ full mesh; the small slave count ( $S = 3$ ) keeps $M \cdot S$ low. This is exactly why real SoCs have few slaves and many masters.

Arbitration per slave (crossbar arbitrates per slave, since contention only happens when two masters want the same slave):

DRAM controller: highest contention. Use round-robin (or weighted round-robin) → bounded latency, satisfying requirement 2 for the audio DMA.
ROM: rarely contended, latency-tolerant → fixed priority is fine and cheap.
Peripheral block: GPU↔peripheral path; if only occasionally shared, fixed priority or round-robin both work.

Audio DMA worst-case latency at DRAM: Suppose up to 6 masters can target DRAM. Round-robin worst wait: $(N - 1) \cdot T_{max} = 5 \times 150 ns = 750 ns .$ Bounded → requirement 2 met.

Summary table of reasoning:

Simultaneity → crossbar (not shared bus).
Bounded latency → round-robin on the hot slave (not fixed priority).
Area → small $S$ keeps $M \times S = 21$ switches, not a full mesh.

Recall Quick self-check (reveal after trying)

Per-master share of a shared bus with $B$ total and $N$ equal masters ::: $B / N$ Crossbar switch count for $M$ masters, $S$ slaves ::: $M \times S$ Crossbar max concurrent transactions ::: $min (M, S)$ Round-robin worst-case wait ::: $(N - 1) \cdot T_{max}$ The failure mode of fixed priority ::: starvation (unbounded low-priority wait) TDM's guaranteed bandwidth for $n_{i}$ of $N$ slots ::: $\frac{n _{i}}{N} \cdot B$