Bus topologies and arbitration

Overview

When multiple devices need to share a communication pathway, we need rules for who gets to use it and how they're connected. This is the essence of bus topology (the physical/logical arrangement) and bus arbitration (conflict resolution when multiple masters want the bus simultaneously).

Bus Topologies

1. Shared/Parallel Bus Topology

Structure:

\downarrow \quad \quad \downarrow \qquad \quad \downarrow \qquad \quad \downarrow \\ \boxed{\text{Address Bus (shared)} \parallel \text{Data Bus (shared)} \parallel \text{Control Lines}}$$ **Why this structure?** - **Cost-effective**: One set of wires serves all devices - **Simple protocol**: All devices listen, addressed device responds - **Historical**: Early computers (ISA, PCI) used this **Limitations:** - **Bandwidth bottleneck**: $N$ masters share total bandwidth $B$, so effective per-master bandwidth $≈ B/N$ - **Electrical loading**: Each device adds capacitance → slower rise times → lower max frequency - **Arbitration overhead**: Bus idle during arbitration cycles > [!example] Classic Example: PCI Bus > - 32-bit or 64-bit parallel data > - Shared among multiple peripherals (network card, graphics, sound) > - **Clock**: ~33 MHz → 133 MB/s peak (32-bit) > - **Problem at scale**: Adding 10 devices might drop effective speed to 13 MB/s per device under contention ### 2. Crossbar Topology > [!definition] Crossbar Switch > A ==crossbar== is a **matrix of switches** allowing **simultaneous connections** between multiple master-slave pairs, as long as they don't conflict on the same slave. **Structure (3×3 example):** ``` Slave₁ Slave₂ Slave₃ Master₁ ●────●──────● │ │ │ Master₂ ●──────●──────● │ │ │ Master₃ ●──────● ``` Each intersection is a programmable switch. Master₁ can talk to Slave₂ **while** Master₃ talks to Slave₁. **Why does this work?** - **Parallel paths**: $M$ masters can access $S$ slaves with up to $\min(M, S)$ **concurrent transactions** - **No shared data bus**: Each connection is an independent point-to-point link - **Arbitration per slave**: If Master₁ and Master₂ both want Slave₁, arbitration happens **only for Slave₁** > [!formula] Crossbar Complexity > **Hardware cost**: For $M$ masters and $S$ slaves: > $$ > \text{Switch count} = M \times S > $$ > **Why?** Each master needs a path to each slave → matrix of switches. **Bandwidth scaling**:

\text{Aggregate bandwidth} = \min(M, S) \times B_{\text{link}}

**Why?** Up to $\min(M,S)$ concurrent transfers, each at link speed. **Derivation of area cost:** Each switch is a multiplexer + control logic ≈ $k$ gates. For $M×S$ switches:

\text{Gate count} ≈ k \cdot M \cdot S = O(M \cdot S)

This is **quadratic** in size—expensive for large systems (e.g., 8×8 crossbar = 64 switches). > [!example] Modern SoC Example > ARM AMBA AXI crossbar in a smartphone SoC: > - **Masters**: 4 CPU cores, GPU, DMA, camera > - **Slaves**: DRAM controller, ROM, peripherals > - **Advantage**: CPU₀ reading DRAM while GPU writes to display buffer—**zero interference** > - **Cost**: ~50 switches, significant die area ### 3. Point-to-Point Topology > [!definition] Point-to-Point Link > Each device has a **dedicated connection** to a central hub or switch. No sharing. Pure ==packet-switched network==. **Structure:** ``` Device₁ ── Switch/Hub ──── Device₂ Device₃ ────┘ └── Device₄ ``` **Why this approach?** - **Scalability**: Adding a device doesn't slow others (assuming switch has capacity) - **High frequency**: Short, impedance-matched traces → GHz signaling (PCIe Gen4: 16 GT/s per lane) - **QoS**: Switch can prioritize traffic **Arbitration is distributed**: Each switch port arbitrates locally. > [!example] PCIe (PCI Express) > - Replaced shared PCI bus > - Each device gets dedicated lanes (x1, x4, x16) > - **Gen 3**: 8 GT/s per lane → x16 = 128 GT/s ≈ 16 GB/s > - **Trade-off**: More wiring, more complex routing, but massive bandwidth ### 4. Hierarchical/Tree Topology > [!definition] Hierarchical Bus > Multiple ==local buses== connected through **bridges** forming a tree. Devices on the same local bus share bandwidth; cross-bridge traffic goes through the hierarchy. **Structure:** ``` [Root Bus] / \ [Bridge₁] [Bridge₂] / \ / \ Dev₁ Dev₂ Dev₃ Dev₄ ``` **Why useful?** - **Locality**: Devices that talk frequently stay on the same local bus (low latency) - **Isolation**: High-bandwidth pairs don't congest the root - **Balanced cost**: Less wiring than full crossbar, better than single shared bus **Bandwidth formula:**

B_{\text{effective}} = \begin{cases} B_{\text{local}} & \text{intra-bus} \ \min(B_{\text{local}}, B_{\text{bridge}}) & \text{inter-bus} \end{cases}

## Bus Arbitration Schemes When multiple masters request the bus simultaneously, ==arbitration logic== decides the winner. ### Fixed Priority Arbitration > [!definition] Fixed Priority > Each master has a **static priority level**. Highest priority requester always wins. **Implementation:** ``` Priority: Master₀ > Master₁ > Master₂ if (REQ₀) GRANT₀; else if (REQ₁) GRANT₁; else if (REQ₂) GRANT₂; ``` **Why simple?** - Combinational logic—fast (few gate delays) - Deterministic latency for high-priority masters **Critical problem: Starvation** If Master₀ constantly requests, Master₂ **never** gets the bus. > [!formula] Worst-Case Latency > For lowest-priority master $M_N$ with $N$ higher-priority masters: > $$ > T_{\text{worst}} = \sum_{i=0}^{N-1} T_{\text{transaction}, i} > $$ > **Why?** In pathological case, all higher-priority masters queue up before $M_N$ gets a turn. > [!example] Real System > - **Master₀**: CPU (priority 3) > - **Master₁**: DMA (priority 2) > - **Master₂**: Debug port (priority 1) If CPU runs tight loop of bus accesses, debug port waits indefinitely → **system undebuggable under load**. > [!mistake] "Fixed priority is fair because high priority = important" > **Why it feels right:** Important tasks should go first. > **The fix:** Importance isn't binary. A low-priority but latency-sensitive task (like audio DMA) missing its deadline causes audible glitches. Need ==bounded latency== for all masters. Use time-division or round-robin variants. ### Round-Robin Arbitration > [!definition] Round-Robin > Masters get turns in **circular order**, regardless of priority. After Master $i$ uses the bus, Master $(i+1) \mod N$ is next eligible. **State machine:** - Counter $C$ tracks whose turn it is - If Master $C$ requests, grant; else skip to next - After transaction, $C \leftarrow (C+1) \mod N$ **Why fair?** Maximum wait for any master is $(N-1)$ full transactions—**bounded starvation**. > [!formula] Maximum Latency > For $N$ masters, each transaction taking $T_{\text{max}}$: > $$ > T_{\text{latency}} ≤ (N-1) \cdot T_{\text{max}} > $$ > **Derivation:** > In worst case, Master $i$ just missed its turn. It waits for: > - Masters $(i+1), (i+2), \ldots, (i+N-1)$ to complete (in modulo-$N$ arithmetic) > - That's $N-1$ masters, each taking up to $T_{\text{max}}$ **Trade-off:** CPU doing critical work waits the same as idle DMA → **inefficient under asymetric load**. > [!example] Simple I²C Multi-Master > - 3 microcontrollers on I²C bus > - Round-robin: μC₀ → μC₁ → μC₂ → μC₀… > - **Benefit**: No μC monopolizes sensor reads > - **Drawback**: If only μC₀ active, wasted arbitration cycles checking μC₁, μC₂ ### Time-Division Multiplexing (TDM) > [!definition] TDM Arbitration > Time is divided into **fixed slots**. Each master gets assigned slot(s) in a repeating schedule. **Structure:** ``` Timeline: |Slot₀|Slot₁|Slot₂|Slot₃|Slot₀|Slot₁|... Assigned: M₀ M₁ M₂ M₀ M₁ ``` **Why deterministic?** - Master knows **exactly when** it gets bus access - **No arbitration logic** needed during slots—grant is pre-determined - Ideal for ==real-time systems== > [!formula] Bandwidth Allocation > If Master $i$ gets $n_i$ slots per cycle of length $N$: > $$ > \text{BW}_i = \frac{n_i}{N} \cdot B_{\text{total}} > $$ > **Example:** $N=8$ slots, $n_{\text{CPU}}=5$, $n_{\text{DMA}}=3$: > $$ > \text{BW}_{\text{CPU}} = \frac{5}{8} \times 100 \text{ MB/s} = 62.5 \text{ MB/s} > $$ **Drawback: Wasted slots** If Master allocated a slot doesn't need it, slot goes unused (unlike round-robin, which skips to next requester). > [!example] TDMA in FlexRay (Automotive) > - Time slots for brake controller, engine, airbag > - **Brake gets every3rd slot** → guaranteed10 ms response > - Even if engine crashes, brake controller unaffected ### Daisy-Chain Arbitration > [!definition] Daisy-Chain > A **grant signal** riples through masters in series. First master in chain that is requesting intercepts the grant. **Circuit:** ``` BUS_GRANT ──→ Master₀ ──→ Master₁ ──→ Master₂ (if REQ₀: block, use bus) (if REQ₁: block, use bus) (if REQ₂: use bus) ``` **Why simple hardware?** - Single grant wire - Each master:1 AND gate (`GRANT_IN & ~MY_REQ → GRANT_OUT`) **Problem: Propagation delay**

T_{\text{arbitration}} = N \cdot t_{\text{gate}}

For 10 masters at 2 ns/gate = 20 ns arbitration overhead. **Priority is physical position**—nearest to source wins. Same starvation issue as fixed priority. > [!example] Old VME Bus > - Daisy-chained arbitration on backplane > - Slot 1always beats Slot 7 > - **Solution**: Rotate board positions periodically (manual fairness!) ### Weighted/Lottery Arbitration > [!definition] Lottery Arbitration > Each master holds **tickets**. Random draw selects winner. More tickets = higher probability of winning. **Algorithm:** 1. Master $i$ has $w_i$ tickets 2. Total tickets $W = \sum w_i$ 3. Draw random number $R \in [0, W)$ 4. Grant to master $i$ where $\sum_{j=0}^{i-1} w_j ≤ R < \sum_{j=0}^{i} w_j$ **Why probabilistic fairness?**

P(\text{Master } i \text{ wins}) = \frac{w_i}{W}

\text{BW}A = \frac{1 \text{ byte}}{T{\text{transaction}}} \quad \text{BW}B = \frac{1024 \text{ bytes}}{T{\text{transaction}}}

Master B gets 1000× more bandwidth! **Fix:** To guarantee bandwidth fairness, use **TDM with time slots** or **weighted arbitration with byte counters**, not just transaction counts. > [!mistake] "Crossbar eliminates all arbitration" > **Steel-man:** Crossbar allows parallel paths, so no conflicts! **The truth:** Crossbar eliminates conflicts between **different slaves**. But if two masters want the **same slave simultaneously**, arbitration is still needed **at that slave's port**. **Example:** 4 CPUs, 1 DRAM controller. All4 CPUs issue DRAM reads at once → DRAM controller's crossbar input still arbitrates among the 4 →3 CPUs wait. **Fix:** For true conflict-free paralelism, need enough **slaves** (e.g., 4 DRAM banks) and **interleaved addressing** so different masters naturally hit different banks. ## Advanced: Priority Inversion Scenario > [!definition] Priority Inversion > Low-priority task $L$ holds bus, medium-priority task $M$ prempts $L$ (in task scheduler), now high-priority $H$ waits for $L$ to finish—but $L$ can't run because $M$ is running. **$H$ waits for $M$**, inverting priority. **Solution**: ==Priority inheritance== or ==priority ceiling== protocols. When $L$ holds bus and $H$ waits, boost $L$'s priority to $H$'s level temporarily. --- ## Connections - [[Bus protocols and signals]] – how data/address/control signals work on these topologies - [[Cache coherence]] – arbitration must coordinate with coherence protocol in multi-CPU systems - [[Network-on-Chip]] – extends point-to-point topology with routing, packetization - [[DMA]] – DMA controllers are bus masters requiring arbitration slots - [[Memory controllers]] – DRAM controller is often the most-contended slave in crossbar - [[PCIe architecture]] – real-world point-to-point topology with tiered arbitration --- > [!recall]- Feynman: Explain to a 12-year-old > Imagine you and your friends all want to use the same Xbox. The **topology** is like: do you pass one controller around (shared bus)? Or does everyone have their own screen and controller, and you only fight over which game cartridge to use (crossbar)? Or does everyone get their own Xbox entirely (point-to-point)? **Arbitration** is the rule for "whose turn is it?" You could say "oldest kid always goes first" (fixed priority), but then youngest never plays—not fair! Or "everyone gets 10 minutes, taking turns" (round-robin). Or "we draw straws each time" (lottery). Real computers have the same problem: the CPU, the graphics card, and the Wi-Fi chip all want to talk to memory **right now**. The hardware needs both a good **layout** (topology) so they're not all stuck in one line, and fair **turn-taking rules** (arbitration) so nobody waits forever. > [!mnemonic] SCPD Topologies > **S**hared – Single wire, Simple Slow with many masters > **C**rossbar – Concurrent, Costly (M×S switches) > **P**oint-to-point – Parallel lanes, PCIe, Packetized > **D**aisy-chain – Dominance by position (old technique) For arbitration: **"FRTL"** – Fixed, Round-robin, TDM, Lottery --- #flashcards/hardware What is the key difference between bus topology and bus arbitration? :: Topology is the **physical/logical structure** of how devices connect (shared, crossbar, point-to-point). Arbitration is the **protocol** for deciding which master gets access when multiple request simultaneously. In a shared bus topology, what happens to per-device bandwidth as more masters are added? ::: Total bus bandwidth is **fixed**. Adding masters means each gets a smaller fraction (~B/N for N masters under full contention). Aggregate bandwidth does not increase. What is the hardware cost of an M×S crossbar switch? ::: O(M·S) switches, because each of M masters needs a path to each of S slaves. For8×8 crossbar = 64 switches. This quadratic scaling limits crossbar size. Why does fixed-priority arbitration cause starvation? ::: The highest-priority master can monopolize the bus if it continuously requests access. Lower-priority masters **never get a turn** until the high-priority one stops. What is the maximum latency for a master in round-robin arbitration with N masters? ::: (N-1) · T_max, where T_max is the longest transaction time. In worst case, the master just missed its turn and waits for all other N-1 masters to complete. How does TDM (time-division multiplexing) arbitration achieve determinism? ::: Time is pre-divided into **fixed slots** assigned to specific masters. Each master knows **exactly when** it gets access, with zero arbitration delay during its slot. Ideal for real-time systems. What is the main drawback of TDM arbitration? ::: **Wasted slots**. If a master doesn't need its allocated time slot, it goes unused (unlike round-robin which can skip to the next requester). In a crossbar topology, when is arbitration still needed? ::: When **multiple masters target the same slave** simultaneously. Crossbar eliminates conflicts between different slaves, but each slave's port still arbitrates among competing masters. What does lottery arbitration guarantee over many cycles? ::: **Probabilistic fairness**. A master with w_i tickets out of W total gets bandwidth proportional to w_i/W **on average**. Single arbitrations are non-deterministic, but long-term average converges. Why does daisy-chain arbitration create priority by physical position? ::: The grant signal ripples through masters **in series**. The first requesting master in the chain intercepts the grant and blocks it from reaching others. Nearest-to-source masters always win over farther ones. What mistake do designers make assuming "round-robin = equal bandwidth"? ::: Round-robin gives equal **access opportunities**, not equal **bandwidth**. Masters doing large transfers get more bytes per turn than masters doing small transfers. True bandwidth fairness requires time-based or byte-counted allocation. What is priority inversion in bus arbitration context? ::: Low-priority task L holds bus; medium-priority task M runs (preempting L); high-priority task H waits for L to release bus, but L can't run. H effectively waits for M, inverting priorities. Fix: priority inheritance. ## 🖼️ Concept Map ```mermaid flowchart TD P[Shared communication pathway] -->|needs| T[Bus topology] P -->|needs| A[Bus arbitration] T -->|type| SB[Shared parallel bus] T -->|type| CB[Crossbar switch] A -->|resolves| C[Master conflicts] SB -->|uses| TDM[Time-division multiplexing] SB -->|suffers| BN[Bandwidth bottleneck B/N] SB -->|example| PCI[PCI bus 133 MB/s] CB -->|allows| CT[Concurrent transactions] CB -->|cost| HW[Switch count M x S] CB -->|arbitrates| PS[Per-slave conflicts] PS -->|is form of| A ``` ## 🔊 Hinglish (regional understanding) > [!intuition]- Hinglish mein samjho > ![[audio/6.3.01-Bus-topologies-and-arbitration.mp3]] ## 🔊 Hinglish (regional understanding) > [!intuition]- Hinglish mein samjho > Chalो, ek simple analogy se samajhte hai. Socho ek single-lane bridge hai jo kai villages ko connect karta hai. Ab problem yeh hai ki jab multiple devices ko ek hi communication pathway share karni ho, toh humein rules chahiye — kaun pehle use karega (yeh hai arbitration) aur devices physically kaise connected hai (yeh hai topology). Bina arbitration ke data collision hoga, aur galat topology se bottleneck ban jayega. Yahi core problem hai jise bus topologies aur arbitration solve karte hai. > > Ab teen main topologies hai. Shared bus mein saare devices ek hi set of wires pe hang karte hai — sasta aur simple hai, lekin ek time pe sirf ek transaction ho sakta hai, isliye agar N masters hai toh har ek ko bandwidth ka sirf B/N milta hai (jaise PCI bus mein hota tha). Crossbar topology mein ek switches ka matrix hota hai, jisse multiple master-slave pairs ek saath baat kar sakte hai, jab tak woh same slave pe conflict na karein. Iska fayda yeh ki CPU DRAM read kar raha ho aur GPU display buffer likh raha ho — bilkul zero interference. Lekin cost M×S switches ki hoti hai, matlab quadratic — bada system mahenga ho jaata hai. Aur point-to-point mein har device ka dedicated connection central switch se hota hai, koi sharing nahi. > > Yeh why-matters isliye important hai kyunki aajkal har smartphone ke SoC mein yeh concepts directly use hote hai — jaise ARM AMBA AXI crossbar. Jab tumhare phone mein 4 CPU cores, GPU, camera sab ek saath memory access karte hai, tab yahi topology decide karti hai ki system smooth chalega ya lag karega. Toh yeh samajhna ki kab shared bus theek hai (cost-sensitive, simple systems) aur kab crossbar chahiye (high-performance, parallel access) — yeh ek hardware engineer ke liye fundamental design trade-off hai. Bas yaad rakhna: performance chahiye toh paisa (die area) dena padega!

Overview

Bus Topologies

1. Shared/Parallel Bus Topology

Go deeper — visual, from zero

Test yourself — Interconnects, Buses & SoC

Connections