Bus topologies and arbitration: Exercises — Hinglish deep dive

6.3.1 · D4 · Hardware › Interconnects, Buses & SoC › Bus topologies and arbitration

Ye problems L1 (sirf idea pehchano) se lekar L5 (sab kuch ek saath) tak graded hain. Pehle har ek problem khud try karo solution collapse karke, phir kholo. Yahan jo bhi symbol milenge wo sab parent note mein build kiye gaye hain — agar koi term naya lage, pehle woh note dobara padho.

Shuru karne se pehle, ek common picture. Neeche sab kuch teen numbers pe tika hai:

Upar ki figure mental model hai: ek single lane (shared bus), switches ki ek grid (crossbar), aur ek timeline jo slots mein kata hai (TDM). Ise dhyan mein rakho.

L1 — Recognition

Exercise 1.1 (L1)

Ek designer 4 peripherals ko ek common set of address+data+control wires se connect karta hai. Kisi bhi ek instant mein sirf ek hi peripheral transfer kar sakta hai. Is topology ka naam batao aur ek phrase mein bolo ki kyun sirf ek hi transfer ek waqt hoti hai.

Recall Solution

Topology: shared (parallel) bus. Kyun ek waqt mein ek: sab devices same physical wires se connected hain, isliye bus time-division multiplexing use karta hai — single wire ek moment mein sirf ek voltage pattern hold kar sakta hai, isliye exactly ek transaction use own karta hai.

Exercise 1.2 (L1)

Har phrase ko ek topology se match karo: (a) "switches ka matrix, simultaneous master–slave pairs", (b) "har device ka apna dedicated link ek switch tak", (c) "local buses jo bridges se ek tree mein jude hain".

Recall Solution

(a) Crossbar
(b) Point-to-point (jaise PCIe)
(c) Hierarchical / tree bus

L2 — Application

Exercise 2.1 (L2)

Ek shared bus ki total bandwidth $B = 132 MB/s$ hai. Heavy contention mein yeh $N = 6$ masters mein evenly split ho jaati hai. Per-master bandwidth kya hogi?

Recall Solution

Even split ka matlab hai har master ko $B / N$ milta hai: $\frac{132}{6} = 22 MB/s per master.$ Kyun divide karte hain? Wire time-shared hai; agar sab equally busy hain, toh har ek $1/ N$ seconds own karta hai, isliye $1/ N$ bytes bhi.

Exercise 2.2 (L2)

$M = 5$ masters aur $S = 4$ slaves ke saath ek $M \times S$ crossbar banao. (a) Kitne switch points honge? (b) Maximum kitne concurrent transactions ho sakte hain?

Recall Solution

(a) Har master ko har slave tak path chahiye, isliye $switches = M \times S = 5 \times 4 = 20.$ (b) Transactions chhoti side se zyada nahi ho sakti (ek slave ek time mein ek master serve karta hai, aur sirf $S = 4$ slaves hain; isi tarah sirf $M = 5$ masters hain): $min (M, S) = min (5, 4) = 4 concurrent transactions.$

Exercise 2.3 (L2)

Round-robin arbiter, $N = 8$ masters, har transaction zyada se zyada $T_{max} = 200 ns$ leta hai. Ek master ko grant milne se pehle worst-case mein kitna wait karna pad sakta hai?

Recall Solution

Woh master jo abhi abhi apni turn chook gaya, usse baaki $N - 1$ masters ka wait karna padega: $T_{latency} \leq (N - 1) \cdot T_{max} = 7 \times 200 ns = 1400 ns = 1.4 μ s .$ $N - 1$ kyun, $N$ kyun nahi? Master khud apni turn ka wait nahi karta — sirf unka wait karta hai jo circle mein usse aage hain.

L3 — Analysis

Exercise 3.1 (L3)

Fixed-priority arbiter jismein masters ka order $M_{0} > M_{1} > M_{2} > M_{3}$ hai (highest pehle). Har transaction $T_{transaction} = 100 ns$ ka hai. Pathological worst case mein, lowest priority master $M_{3}$ kitna wait kar sakta hai, aur yeh kaunsa phenomenon illustrate karta hai?

Recall Solution

$M_{3}$ ke paas $N = 3$ higher-priority masters hain. Worst case mein woh ek ke baad ek queue karte hain: $T_{worst} = \sum_{i = 0}^{N - 1} T_{transaction, i} = 3 \times 100 ns = 300 ns .$ Lekin agar higher masters baar baar request karte rahen, toh yeh hamesha repeat hota rahega → true worst case unbounded hai. Yeh starvation hai: ek low-priority master ko indefinitely deny kiya ja sakta hai. $300 ns$ sirf higher-priority traffic ke ek "round" ki delay hai; koi guaranteed ceiling nahi hai.

Exercise 3.2 (L3)

Ek system ke liye do arbiters compare karo jismein ek audio DMA hai (har $22.7 μ s$ mein ek sample chahiye, har baar $100 ns$ ka ek transaction) aur ek CPU hai jo bus ko continuously hammer karta hai.

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

Kaun sa arbiter guarantee karta hai ki audio DMA apna deadline meet kare? Numerically justify karo.

Recall Solution

Arbiter A (fixed, CPU high): CPU kabhi yield nahi karta jab tak woh request karta rahta hai → audio DMA unboundedly wait kar sakta hai. $22.7 μ s$ ka deadline guaranteed nahi. Result: audible glitches.

Arbiter B (round-robin): audio DMA ke liye worst wait hai $(N - 1) \cdot T_{max} = 1 \times 100 ns = 100 ns .$ Kyunki $100 ns ≪ 22.7 μ s$ hai, deadline hamesha meet hoti hai bahut bade margin ke saath.

Conclusion: Round-robin (ya TDM slot) zaroori hai. Yahan "less important" master hi latency-critical ek hai — priority ≠ importance.

L4 — Synthesis

Exercise 4.1 (L4)

Ek SoC ko 6 masters ko 6 slaves se connect karna hai. Do candidate fabrics:

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

Compute karo (a) crossbar switch count, (b) crossbar aggregate bandwidth, (c) jab sab 6 masters alag alag slaves se baat karte hain toh shared bus ke mukable crossbar ka bandwidth speedup.

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 total $800 MB/s$ deta hai; crossbar $4800$ deta hai. Speedup $\frac{4800}{800} = 6 \times .$ Cost trade-off: Tumne $36$ switches pay kiye vs $12$ tap points ( $3 \times$ hardware) aur $6 \times$ bandwidth mila — yahi classic crossbar bargain hai, jab tak $M \cdot S$ bahut bada na ho jaaye.

Exercise 4.2 (L4)

$N = 10$ slots ki TDM schedule ek bus pe jiska raw bandwidth $B = 1000 MB/s$ hai. Ek video engine ko $n_{i} = 4$ slots assign kiye gaye hain. (a) Use kaunsi guaranteed bandwidth milegi? (b) Agar ek control CPU ko $1$ slot assign kiya jaaye, toh usse kya bandwidth milegi, aur woh key property kya hai jo TDM guarantee karta hai jo round-robin nahi karta?

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 har master ko ek fixed, pehle se pata hua slot deta hai → uska access time deterministic hai (exactly tab jab uska slot aata hai), aur slot ke dauran zero arbitration overhead hota hai. Round-robin ka grant depend karta hai ki aur kaun request kar raha hai, isliye timing sirf bounded hai, scheduled nahi.

L5 — Mastery

Exercise 5.1 (L5)

Ek smartphone SoC mein hai: 4 CPU cores, 1 GPU, 1 DMA engine, 1 camera ISP = 7 masters, aur 3 slaves: DRAM controller, ROM, peripheral block = 3 slaves.

Requirements:

CPU↔DRAM aur GPU↔peripheral simultaneously aur zero interference ke saath run hone chahiye.
Audio DMA (DMA engine ka part) ka bounded worst-case bus latency hona chahiye.
Die area tight hai.

Interconnect design karo: topology choose karo, switch count do, aur har slave ke liye ek arbitration scheme choose karo, har choice ko teeno requirements ke against justify karo. Phir audio DMA ki worst-case latency compute karo agar DRAM ka arbiter round-robin hai un (zyada se zyada) 6 masters pe jo DRAM ko touch karte hain, $T_{max} = 150 ns$ ke saath.

Recall Solution

Topology — crossbar. Requirement 1 (simultaneous, non-interfering paths) independent point-to-point links per master–slave pair force karta hai → woh hi crossbar hai. Ek single shared bus CPU aur GPU ko serialize kar deta aur requirement 1 fail ho jaati.

Switch count: $M \times S = 7 \times 3 = 21$ switches. Modest — requirement 3 ko $7 \times 7$ full mesh se kahin zyada better satisfy karta hai; chhota slave count ( $S = 3$ ) $M \cdot S$ ko low rakhta hai. Yahi reason hai ki real SoCs mein few slaves aur many masters hote hain.

Arbitration per slave (crossbar per slave arbitrate karta hai, kyunki contention tab hi hoti hai jab do masters same slave chahte hain):

DRAM controller: highest contention. Round-robin (ya weighted round-robin) use karo → bounded latency, requirement 2 satisfy karta hai audio DMA ke liye.
ROM: rarely contended, latency-tolerant → fixed priority theek hai aur sasta bhi.
Peripheral block: GPU↔peripheral path; agar sirf occasionally shared hai, toh fixed priority ya round-robin dono kaam karenge.

Audio DMA worst-case latency at DRAM: Maano 6 masters DRAM target kar sakte hain. Round-robin worst wait: $(N - 1) \cdot T_{max} = 5 \times 150 ns = 750 ns .$ Bounded → requirement 2 meet hua.

Summary table of reasoning:

Simultaneity → crossbar (shared bus nahi).
Bounded latency → hot slave pe round-robin (fixed priority nahi).
Area → chhota $S$ rakhne se $M \times S = 21$ switches, full mesh nahi.

Recall Quick self-check (pehle try karo phir reveal karo)

$B$ total aur $N$ equal masters wale shared bus mein per-master share ::: $B / N$ $M$ masters, $S$ slaves wale crossbar mein switch count ::: $M \times S$ Crossbar max concurrent transactions ::: $min (M, S)$ Round-robin worst-case wait ::: $(N - 1) \cdot T_{max}$ Fixed priority ka failure mode ::: starvation (unbounded low-priority wait) $N$ slots mein se $n_{i}$ slots ke liye TDM ki guaranteed bandwidth ::: $\frac{n _{i}}{N} \cdot B$