Bus topologies and arbitration — Hinglish notes

6.3.1 · Hardware › Interconnects, Buses & SoC

Overview

Jab multiple devices ek communication pathway share karna chahte hain, toh hume rules chahiye ki kaun ise use karega aur wo kaise connected hain. Yahi essence hai bus topology ka (physical/logical arrangement) aur bus arbitration ka (conflict resolution jab multiple masters ek saath bus chahte hain).

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}}$$ **Yeh structure kyun?** - **Cost-effective**: Wires ka ek set sabhi devices ko serve karta hai - **Simple protocol**: Sabhi devices sunте hain, addressed device respond karta hai - **Historical**: Early computers (ISA, PCI) mein yahi use hota tha **Limitations:** - **Bandwidth bottleneck**: $N$ masters total bandwidth $B$ share karte hain, toh effective per-master bandwidth $≈ B/N$ - **Electrical loading**: Har device capacitance add karta hai → slower rise times → lower max frequency - **Arbitration overhead**: Arbitration cycles ke dauran bus idle rehti hai > [!example] Classic Example: PCI Bus > - 32-bit ya 64-bit parallel data > - Multiple peripherals ke beech shared (network card, graphics, sound) > - **Clock**: ~33 MHz → 133 MB/s peak (32-bit) > - **Scale par problem**: 10 devices add karne se contention mein effective speed gir ke 13 MB/s per device aa sakti hai ### 2. Crossbar Topology > [!definition] Crossbar Switch > Ek ==crossbar== **switches ka ek matrix** hota hai jo multiple master-slave pairs ke beech **simultaneous connections** allow karta hai, jab tak woh same slave par conflict na karein. **Structure (3×3 example):** ``` Slave₁ Slave₂ Slave₃ Master₁ ●────●──────● │ │ │ Master₂ ●──────●──────● │ │ │ Master₃ ●──────● ``` Har intersection ek programmable switch hai. Master₁, Slave₂ se baat kar sakta hai **jabki** Master₃, Slave₁ se baat kare. **Yeh kaam kyun karta hai?** - **Parallel paths**: $M$ masters, $S$ slaves ko access kar sakte hain, up to $\min(M, S)$ **concurrent transactions** ke saath - **No shared data bus**: Har connection ek independent point-to-point link hai - **Arbitration per slave**: Agar Master₁ aur Master₂ dono Slave₁ chahte hain, toh arbitration **sirf Slave₁ ke liye** hoti hai > [!formula] Crossbar Complexity > **Hardware cost**: $M$ masters aur $S$ slaves ke liye: > $$ > \text{Switch count} = M \times S > $$ > **Kyun?** Har master ko har slave tak path chahiye → switches ka matrix. **Bandwidth scaling**:

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

**Kyun?** Up to $\min(M,S)$ concurrent transfers, har ek link speed par. **Area cost ki derivation:** Har switch ek multiplexer + control logic ≈ $k$ gates hai. $M×S$ switches ke liye:

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

Yeh size mein **quadratic** hai—bade systems ke liye expensive (e.g., 8×8 crossbar = 64 switches). > [!example] Modern SoC Example > ARM AMBA AXI crossbar ek smartphone SoC mein: > - **Masters**: 4 CPU cores, GPU, DMA, camera > - **Slaves**: DRAM controller, ROM, peripherals > - **Advantage**: CPU₀ DRAM read kar raha hai jabki GPU display buffer mein likh raha hai—**zero interference** > - **Cost**: ~50 switches, significant die area ### 3. Point-to-Point Topology > [!definition] Point-to-Point Link > Har device ka ek central hub ya switch se **dedicated connection** hota hai. Koi sharing nahi. Pure ==packet-switched network==. **Structure:** ``` Device₁ ── Switch/Hub ──── Device₂ Device₃ ────┘ └── Device₄ ``` **Yeh approach kyun?** - **Scalability**: Device add karne se doosre slow nahi hote (assuming switch mein capacity hai) - **High frequency**: Short, impedance-matched traces → GHz signaling (PCIe Gen4: 16 GT/s per lane) - **QoS**: Switch traffic ko prioritize kar sakta hai **Arbitration distributed hoti hai**: Har switch port locally arbitrate karta hai. > [!example] PCIe (PCI Express) > - Shared PCI bus ko replace kiya > - Har device ko dedicated lanes milti hain (x1, x4, x16) > - **Gen 3**: 8 GT/s per lane → x16 = 128 GT/s ≈ 16 GB/s > - **Trade-off**: Zyada wiring, zyada complex routing, lekin massive bandwidth ### 4. Hierarchical/Tree Topology > [!definition] Hierarchical Bus > Multiple ==local buses== **bridges** ke through connect hoti hain ek tree banaate hue. Same local bus par devices bandwidth share karti hain; cross-bridge traffic hierarchy se jaati hai. **Structure:** ``` [Root Bus] / \ [Bridge₁] [Bridge₂] / \ / \ Dev₁ Dev₂ Dev₃ Dev₄ ``` **Kyun useful hai?** - **Locality**: Jo devices aksar baat karte hain woh same local bus par rehte hain (low latency) - **Isolation**: High-bandwidth pairs root ko congest nahi karte - **Balanced cost**: Full crossbar se kam wiring, single shared bus se behtar **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 Jab multiple masters ek saath bus request karte hain, toh ==arbitration logic== winner decide karti hai. ### Fixed Priority Arbitration > [!definition] Fixed Priority > Har master ka ek **static priority level** hota hai. Sabse zyada priority wala requester hamesha jeetta hai. **Implementation:** ``` Priority: Master₀ > Master₁ > Master₂ if (REQ₀) GRANT₀; else if (REQ₁) GRANT₁; else if (REQ₂) GRANT₂; ``` **Simple kyun hai?** - Combinational logic—fast (few gate delays) - High-priority masters ke liye deterministic latency **Critical problem: Starvation** Agar Master₀ constantly request kare, toh Master₂ ko **kabhi** bus nahi milegi. > [!formula] Worst-Case Latency > Sabse low-priority master $M_N$ ke liye, jiske $N$ higher-priority masters hain: > $$ > T_{\text{worst}} = \sum_{i=0}^{N-1} T_{\text{transaction}, i} > $$ > **Kyun?** Pathological case mein, $M_N$ ka turn aane se pehle sabhi higher-priority masters queue kar lete hain. > [!example] Real System > - **Master₀**: CPU (priority 3) > - **Master₁**: DMA (priority 2) > - **Master₂**: Debug port (priority 1) Agar CPU bus accesses ka tight loop chalaaye, debug port indefinitely wait karta hai → **system load ke neeche undebuggable ho jaata hai**. > [!mistake] "Fixed priority fair hai kyunki high priority = important" > **Kyun sahi lagta hai:** Important tasks pehle jaane chahiye. > **The fix:** Importance binary nahi hoti. Ek low-priority lekin latency-sensitive task (jaise audio DMA) agar apna deadline miss kare toh audible glitches hote hain. Sabhi masters ke liye ==bounded latency== chahiye. Time-division ya round-robin variants use karo. ### Round-Robin Arbitration > [!definition] Round-Robin > Masters ko **circular order** mein turns milte hain, priority se irrespective. Master $i$ ke bus use karne ke baad, Master $(i+1) \mod N$ next eligible hota hai. **State machine:** - Counter $C$ track karta hai kiska turn hai - Agar Master $C$ request kare, grant karo; warna next par skip karo - Transaction ke baad, $C \leftarrow (C+1) \mod N$ **Fair kyun hai?** Kisi bhi master ke liye maximum wait $(N-1)$ full transactions hai—**bounded starvation**. > [!formula] Maximum Latency > $N$ masters ke liye, har transaction $T_{\text{max}}$ leta hai: > $$ > T_{\text{latency}} ≤ (N-1) \cdot T_{\text{max}} > $$ > **Derivation:** > Worst case mein, Master $i$ ne abhi apna turn miss kiya. Yeh wait karta hai: > - Masters $(i+1), (i+2), \ldots, (i+N-1)$ ke complete hone ka (modulo-$N$ arithmetic mein) > - Woh $N-1$ masters hain, har ek up to $T_{\text{max}}$ le sakta hai **Trade-off:** Critical kaam kar raha CPU utna hi wait karta hai jitna idle DMA → **asymmetric load mein inefficient**. > [!example] Simple I²C Multi-Master > - I²C bus par 3 microcontrollers > - Round-robin: μC₀ → μC₁ → μC₂ → μC₀… > - **Benefit**: Koi bhi μC sensor reads monopolize nahi karta > - **Drawback**: Agar sirf μC₀ active hai, toh μC₁, μC₂ check karne mein arbitration cycles waste hote hain ### Time-Division Multiplexing (TDM) > [!definition] TDM Arbitration > Time **fixed slots** mein divide hoti hai. Har master ko ek repeating schedule mein slot(s) assign hoti hain. **Structure:** ``` Timeline: |Slot₀|Slot₁|Slot₂|Slot₃|Slot₀|Slot₁|... Assigned: M₀ M₁ M₂ M₀ M₁ ``` **Deterministic kyun hai?** - Master ko **exactly pata** hota hai ki usse bus access kab milegi - Slots ke dauran **koi arbitration logic** nahi chahiye—grant pre-determined hai - ==Real-time systems== ke liye ideal > [!formula] Bandwidth Allocation > Agar Master $i$ ko length $N$ ke cycle mein $n_i$ slots milte hain: > $$ > \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** Agar allocated slot wala master usse use na kare, toh slot unused ho jaata hai (round-robin ke unlike, jo next requester par skip karta hai). > [!example] TDMA in FlexRay (Automotive) > - Brake controller, engine, airbag ke liye time slots > - **Brake ko har 3rd slot milta hai** → guaranteed 10 ms response > - Engine crash ho jaaye tab bhi brake controller unaffected rehta hai ### Daisy-Chain Arbitration > [!definition] Daisy-Chain > Ek **grant signal** masters mein series mein ripple karta hai. Chain mein pehla requesting master grant ko intercept kar leta hai. **Circuit:** ``` BUS_GRANT ──→ Master₀ ──→ Master₁ ──→ Master₂ (if REQ₀: block, use bus) (if REQ₁: block, use bus) (if REQ₂: use bus) ``` **Simple hardware kyun?** - Single grant wire - Har master: 1 AND gate (`GRANT_IN & ~MY_REQ → GRANT_OUT`) **Problem: Propagation delay**

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

10 masters par 2 ns/gate = 20 ns arbitration overhead. **Priority physical position hai**—source ke sabse kareeb wala jeetta hai. Fixed priority jaisi hi starvation issue hai. > [!example] Old VME Bus > - Backplane par daisy-chained arbitration > - Slot 1 hamesha Slot 7 se beat karta hai > - **Solution**: Board positions periodically rotate karo (manual fairness!) ### Weighted/Lottery Arbitration > [!definition] Lottery Arbitration > Har master ke paas **tickets** hote hain. Random draw winner select karta hai. Zyada tickets = jeetne ki zyada probability. **Algorithm:** 1. Master $i$ ke paas $w_i$ tickets hain 2. Total tickets $W = \sum w_i$ 3. Random number draw karo $R \in [0, W)$ 4. Master $i$ ko grant karo jahan $\sum_{j=0}^{i-1} w_j ≤ R < \sum_{j=0}^{i} w_j$ **Probabilistic fairness kyun?**

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 ko 1000× zyada bandwidth milti hai! **Fix:** Bandwidth fairness guarantee karne ke liye, **TDM with time slots** ya **weighted arbitration with byte counters** use karo, sirf transaction counts nahi. > [!mistake] "Crossbar saari arbitration khatam kar deta hai" > **Steel-man:** Crossbar parallel paths allow karta hai, toh koi conflicts nahi! **Sach yeh hai:** Crossbar **different slaves** ke beech conflicts khatam karta hai. Lekin agar do masters **ek hi slave ko simultaneously** chahein, toh arbitration **us slave ke port par** abhi bhi zaroori hai. **Example:** 4 CPUs, 1 DRAM controller. Sabhi 4 CPUs ek saath DRAM reads issue karte hain → DRAM controller ka crossbar input abhi bhi 4 mein se arbitrate karta hai → 3 CPUs wait karte hain. **Fix:** True conflict-free parallelism ke liye, kaafi **slaves** chahiye (e.g., 4 DRAM banks) aur **interleaved addressing** taaki different masters naturally different banks hit karein. ## Advanced: Priority Inversion Scenario > [!definition] Priority Inversion > Low-priority task $L$ bus hold karta hai, medium-priority task $M$, $L$ ko preempt karta hai (task scheduler mein), ab high-priority $H$, $L$ ke finish hone ka wait karta hai—lekin $L$ run nahi kar sakta kyunki $M$ run kar raha hai. **$H$, $M$ ka wait karta hai**, priority invert ho jaati hai. **Solution**: ==Priority inheritance== ya ==priority ceiling== protocols. Jab $L$ bus hold kare aur $H$ wait kare, toh $L$ ki priority temporarily $H$ ke level tak boost karo. --- ## Connections - [[Bus protocols and signals]] – in topologies par data/address/control signals kaise kaam karte hain - [[Cache coherence]] – multi-CPU systems mein arbitration ko coherence protocol ke saath coordinate karna hota hai - [[Network-on-Chip]] – point-to-point topology ko routing, packetization ke saath extend karta hai - [[DMA]] – DMA controllers bus masters hote hain jinhe arbitration slots chahiye - [[Memory controllers]] – DRAM controller aksar crossbar mein sabse zyada contested slave hota hai - [[PCIe architecture]] – tiered arbitration ke saath real-world point-to-point topology --- > [!recall]- Feynman: Explain to a 12-year-old > Socho tum aur tumhare doston ko ek hi Xbox use karni hai. **Topology** kuch aisi hai: kya tum ek controller pass karte ho (shared bus)? Ya sabke paas apni screen aur controller hai, aur sirf game cartridge ke liye ladai hoti hai (crossbar)? Ya phir sabke paas apni Xbox hai (point-to-point)? **Arbitration** woh rule hai "kiska turn hai?" Tum keh sakte ho "sabse bada baccha hamesha pehle jaayega" (fixed priority), lekin tab sabse chhote ko kabhi mauka nahi milega—fair nahi! Ya "har koi 10 minute leta hai, turns mein" (round-robin). Ya "har baar parchiyaan nikalo" (lottery). Real computers mein bhi yahi problem hai: CPU, graphics card, aur Wi-Fi chip sabhi **abhi** memory se baat karna chahte hain. Hardware ko ek acha **layout** (topology) chahiye taaki sab ek line mein na phanse, aur fair **turn-taking rules** (arbitration) taaki koi forever wait na kare. > [!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) Arbitration ke liye: **"FRTL"** – Fixed, Round-robin, TDM, Lottery --- #flashcards/hardware Bus topology aur bus arbitration mein key difference kya hai? :: Topology **physical/logical structure** hai ki devices kaise connect hote hain (shared, crossbar, point-to-point). Arbitration woh **protocol** hai jo decide karta hai ki kaunse master ko access milega jab multiple simultaneously request karte hain. Shared bus topology mein jab zyada masters add hote hain toh per-device bandwidth ka kya hota hai? ::: Total bus bandwidth **fixed** rehti hai. Masters add karne se har ek ko chhota fraction milta hai (~B/N for N masters under full contention). Aggregate bandwidth nahi badhti. M×S crossbar switch ka hardware cost kya hai? ::: O(M·S) switches, kyunki M masters mein se har ek ko S slaves mein se har ek tak path chahiye. 8×8 crossbar ke liye = 64 switches. Yeh quadratic scaling crossbar size ko limit karti hai. Fixed-priority arbitration mein starvation kyun hoti hai? ::: Sabse zyada priority wala master bus monopolize kar sakta hai agar woh continuously access request kare. Lower-priority masters ko **kabhi turn nahi milta** jab tak high-priority wala ruk na jaaye. N masters ke saath round-robin arbitration mein master ke liye maximum latency kya hai? ::: $(N-1) \cdot T_{\text{max}}$, jahan $T_{\text{max}}$ sabse lambi transaction time hai. Worst case mein, master ne abhi apna turn miss kiya aur sabhi baaki N-1 masters ke complete hone ka wait karta hai. TDM (time-division multiplexing) arbitration determinism kaise achieve karta hai? ::: Time **fixed slots** mein pre-divide hoti hai jo specific masters ko assign hoti hain. Har master ko **exactly pata** hota hai ki usse access kab milega, apni slot ke dauran zero arbitration delay ke saath. Real-time systems ke liye ideal. TDM arbitration ka main drawback kya hai? ::: **Wasted slots**. Agar koi master apna allocated time slot use na kare, toh woh unused reh jaata hai (round-robin ke unlike jo next requester par skip kar sakta hai). Crossbar topology mein arbitration kab bhi zaroori rehti hai? ::: Jab **multiple masters ek hi slave ko simultaneously target** karein. Crossbar different slaves ke beech conflicts khatam karta hai, lekin har slave ka port competing masters ke beech arbitrate karta rehta hai. Lottery arbitration kaafi cycles mein kya guarantee karta hai? ::: **Probabilistic fairness**. $W$ total mein se $w_i$ tickets wale master ko **average par** $w_i/W$ ke proportional bandwidth milti hai. Single arbitrations non-deterministic hote hain, lekin long-term average converge ho jaata hai. Daisy-chain arbitration mein physical position se priority kyun create hoti hai? ::: Grant signal masters mein **series mein** ripple karta hai. Chain mein pehla requesting master grant ko intercept karta hai aur doosron tak pahunchne se rok deta hai. Source ke kareeb wale masters hamesha door walon se jeet te hain. Designers "round-robin = equal bandwidth" assume karke kya galti karte hain? ::: Round-robin equal **access opportunities** deta hai, equal **bandwidth** nahi. Bade transfers karne wale masters apni turn mein chhote transfers karne walon se zyada bytes lete hain. True bandwidth fairness ke liye time-based ya byte-counted allocation chahiye. Bus arbitration context mein priority inversion kya hai? ::: Low-priority task $L$ bus hold karta hai; medium-priority task $M$ run karta hai ($L$ ko preempt karke); high-priority task $H$ bus release hone ka wait karta hai, lekin $L$ run nahi kar sakta. $H$ effectively $M$ ka wait karta hai, priorities invert ho jaati hain. 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 ```