Worked examples — Bus topologies and arbitration

This page is the practice ground for Bus topologies and arbitration. The parent note gave you the ideas: shared buses, crossbars, fixed-priority and round-robin arbitration, time-division multiplexing (TDM). Here we compute — and we deliberately hunt for the corners: the tiniest system, the biggest, the tie, the starving master, the fully-loaded slot table.

Before we touch a single number, let us pin down the vocabulary so nothing is used unexplained.

---

The scenario matrix

Every question this topic can ask falls into one of these cells. The worked examples below are labelled with the cell they cover, and together they fill the whole table.

Cell	Scenario class	The corner it stresses
A	Shared-bus bandwidth split	many masters, one pipe — the $B/N$ bottleneck
B	Crossbar switch count & aggregate BW	quadratic hardware growth; the $\min (M,S)$ cap
C	Degenerate crossbar ($M=1$ or $S=1$)	when a crossbar collapses to a plain wire
D	Fixed-priority worst-case latency	the starving lowest-priority master
E	Round-robin bounded latency	the $(N-1)T$ guarantee, and the "just-missed-my-turn" worst case
F	TDM bandwidth allocation	fractional slot shares; the unused-slot waste
G	Single-master edge ($N=1$)	arbitration with nobody to fight
H	Real-world word problem	mixed: pick topology + scheme, justify
I	Exam-style twist	a "fair-looking" scheme that still starves

Cells map to examples: A→Ex1, B→Ex2, C→Ex3, D→Ex4, E→Ex5, F→Ex6, G→Ex7, H→Ex8, I→Ex9.

---

Worked examples

Example 1 — Shared bus, the bandwidth split (Cell A)

Forecast: guess the per-master number before reading on. Bigger or smaller than 100 MB/s?

1. Identify the shared resource. Why this step? On a shared bus only one transaction happens at a time (time-division multiplexing). The total $B$ is not multiplied by having more masters — it is divided among them.
2. Apply the split. The saturated per-master share is $B_{\text{per}}=\frac{B}{N}=\frac{133}{10}\text{ MB/s}.$ Why this step? $N=10$ masters take equal turns, so each sees a tenth of the pipe.
3. Compute. $B_{\text{per}}=13.3\text{ MB/s}$.

Verify: Sanity check — 10 masters $\times$ 13.3 MB/s $=133$ MB/s $=B$. The parts add back to the whole pipe. ✓ (This is exactly the "13 MB/s per device" figure from the parent's PCI example.)

---

Example 2 — Crossbar: switches and aggregate bandwidth (Cell B)

Forecast: guess the switch count — is it 7, 11, or something bigger?

Look at the figure: every master row crosses every slave column, and a switch (●) sits at each crossing.

1. Count the crossings. Why this step? Each master needs an independent path to each slave, so the switches form an $M\times S$ grid. $\text{switches}=M\times S=7\times 4=28.$
2. Cap the concurrency. Why this step? Two masters cannot share one slave at the same instant — so the number of simultaneous transfers can never exceed the smaller of $M$ and $S$. $\text{concurrent}=\min (M,S)=\min (7,4)=4.$
3. Aggregate bandwidth. Each of those 4 concurrent links runs at full speed: $B_{\text{agg}}=\min (M,S)\times B_{\text{link}}=4\times 20=80\text{ GB/s}.$

Verify: Only 4 slaves exist, so at most 4 transfers land at once — the bandwidth is bottlenecked by slaves, not the 7 masters. If we'd (wrongly) used $M=7$ we'd claim 140 GB/s, which is impossible: 3 masters would have nowhere to write. The $\min$ is doing real work. ✓

---

Example 3 — Degenerate crossbar (Cell C)

Forecast: Does a crossbar still help here, or has it collapsed?

1. Switch count. $M\times S=5\times 1=5$ switches — just one column. Why this step? With one slave there is only one destination column of the grid.
2. Concurrency cap. $\min (M,S)=\min (5,1)=1$. Why this step? Everybody wants the same slave, so only one transfer can proceed at a time.
3. Aggregate bandwidth. $1\times B_{\text{link}}=B_{\text{link}}$.

Verify: With one slave the crossbar offers no parallelism — it degenerates into a shared bus with an arbiter in front of the single slave. The 5 masters split $B_{\text{link}}$ exactly as in Example 1. So a crossbar only pays off when $S>1$. ✓ This is the degenerate corner that catches people who assume "crossbar = always parallel."

---

Example 4 — Fixed-priority worst-case latency (Cell D)

Forecast: Is $M_2$'s wait bounded or infinite?

1. List who jumps the queue. Why this step? Fixed priority always serves the highest requester first. $M_2$ is served only when no higher master is requesting.
2. Sum the higher-priority transactions. With $N=2$ higher masters each needing $T$: $T_{\text{worst}}={\sum }_{i=0}^{N-1}T=2\times 4=8\text{ µs}$ if $M_0$ and $M_1$ each want the bus exactly once ahead of $M_2$.
3. Now the pathological case. Why this step? If $M_0$ continuously re-requests, step 1 never clears — $M_2$'s wait is unbounded (starvation). The 8 µs figure only holds when higher masters have finite demand.

Verify: Units: $2\times 4\text{µs}=8\text{µs}$, a time — correct. And the honest answer to the second half is $\infty$: fixed priority gives no latency bound to the bottom master. This is exactly why the parent flags "debug port waits indefinitely." ✓

---

Example 5 — Round-robin bounded latency (Cell E)

Forecast: Will round-robin's bound be $4T$, $3T$, or $T$?

The figure shows the circular counter $C$ that hands out turns.

1. Set up the "just-missed" worst case. Why this step? The longest a master $i$ can wait is right after its turn passed — now everyone else goes before it comes around again.
2. Count the intervening masters. In modulo-$N$ order, masters $(i+1),(i+2),\dots ,(i+N-1)$ go first — that is $N-1=3$ masters.
3. Multiply by the per-turn cap. $T_{\text{latency}}\le (N-1)T_{\max }=3\times 3=9\text{ µs}.$

Verify: Every master now has a finite guarantee of 9 µs — no starvation, unlike Example 4 where $M_2$ could wait forever. The price: a busy master waits behind idle ones. Units check: $3\times 3\text{µs}=9\text{µs}$. ✓

---

Example 6 — TDM slot allocation (Cell F)

Forecast: Will the three shares add up to the full 800 MB/s, or is some bandwidth stranded?

1. Slot fraction → bandwidth. Why this step? A master gets the whole pipe only during its slots; over a full cycle it sees the fraction $n_i/N$ of the total $B$. ${\text{BW}}_i=\frac{n_i}{N}\cdot B.$
2. Compute each. ${\text{BW}}_0=\frac{5}{8}\times 800=500,{\text{BW}}_1=\frac{2}{8}\times 800=200,{\text{BW}}_2=\frac{1}{8}\times 800=100\text{ MB/s}.$
3. Check slot conservation. $n_0+n_1+n_2=5+2+1=8=N$. Why this step? If the assigned slots exactly fill the cycle, no slot is idle and no bandwidth is wasted.

Verify: Bandwidths sum to $500+200+100=800=B$ — the whole pipe is accounted for, nothing stranded. Had we assigned only 7 slots, one slot ($100$ MB/s) would sit idle every cycle even if a master is desperate — TDM's rigidity cost. ✓

---

Example 7 — Single master, $N=1$ (Cell G)

Forecast: Does arbitration even mean anything here?

1. Plug $N=1$ into the round-robin bound. $T_{\text{latency}}\le (N-1)T_{\max }=0\times T_{\max }=0.$ Why this step? There is nobody else in the circle, so the master never waits.
2. Arbiter logic needed. Why this step? With one requester there is no conflict to resolve — the grant can be tied permanently high. Zero arbitration gates required.

Verify: A single-master bus needs no arbiter and has zero contention latency — the degenerate baseline every scheme must reduce to. Both formulas ($T_{\text{worst}}$ for fixed priority with 0 higher masters, and $(N-1)T$ for round-robin) correctly collapse to $0$. ✓

---

Example 8 — Real-world word problem: pick the topology (Cell H)

Forecast: Guess the crossbar's speed-up factor over the shared bus.

1. Shared-bus throughput. All 5 masters split one pipe: $40\text{ GB/s}$ total, $8\text{ GB/s}$ each (Cell A logic).
2. Crossbar throughput. Why this step? Independent masters hitting different banks run concurrently, up to $\min (M,S)=\min (5,5)=5$: $B_{\text{agg}}=5\times 40=200\text{ GB/s}.$
3. Speed-up. $200/40=5\times$. The crossbar wins fivefold because the accesses are to different slaves.
4. Arbitration choice. Why this step? Audio DMA needs a guaranteed deadline. Fixed priority could starve it if it's low; round-robin bounds its wait to $(N-1)T$; TDM gives it a reserved slot so its bandwidth is deadline-guaranteed. Choose TDM (or round-robin with a reserved share) — never plain fixed priority for a hard-real-time master.

Verify: Shared $8$ GB/s each vs crossbar $200$ GB/s aggregate; $200=5\times 40$ and speed-up $=5$, exactly $\min (M,S)$ as theory predicts. Units all GB/s. ✓

---

Example 9 — Exam twist: the "fair-looking" scheme that still starves (Cell I)

Forecast: True round-robin bounds waits — does this variant still?

1. Trace the scan. Why this step? "Resume from master 0" is the trap: after each grant the pointer resets to $M_0$, not to $M_0$'s successor. So the scan order is always $M_0,M_1,M_2$ from the top.
2. Follow the greedy master. $M_0$ always requests and is always scanned first → $M_0$ is granted every single round. The scan never reaches $M_2$ while $M_0$ is active.
3. Diagnose. This is fixed priority in disguise — the reset destroys the "rotate the starting point" property that makes real round-robin fair. $M_2$'s wait is unbounded → starvation.
4. The fix. After granting master $C$, advance the start pointer to $(C+1)\mathrm{mod}N$ so the previously-served master goes to the back of the line. Then the bound $(N-1)T_{\max }=2\times 2=4\text{ µs}$ is restored.

Verify: Broken variant: $M_2$ waits $\infty$ (starves). Correct rotating variant: bound $=(3-1)\times 2\text{µs}=4\text{µs}$. The single word "resume from 0 vs from $C+1$" flips fair into unfair — the classic exam gotcha. ✓

---

Recall

Connections

• Parent: Bus topologies and arbitration
• Deeper mesh interconnects: Network-on-Chip
• Point-to-point at scale: PCIe architecture
• Who the masters often are: DMA, and how slaves respond: Memory controllers
• Signalling underneath: Bus protocols and signals
• Why shared reads get complicated: Cache coherence