Bus topologies and arbitration: Worked examples — Hinglish deep dive

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

Yeh page Bus topologies and arbitration ki practice ground hai. Parent note ne tumhe ideas diye: shared buses, crossbars, fixed-priority aur round-robin arbitration, time-division multiplexing (TDM). Yahan hum compute karte hain — aur deliberately corners dhundte hain: sabse chhota system, sabse bada, tie, starving master, fully-loaded slot table.

Koi bhi number chhune se pehle, vocabulary pin down kar lete hain taaki kuch bhi bina explain ke use na ho.

Scenario matrix

Is topic ka har sawal in cells mein se kisi ek mein aata hai. Neeche ke worked examples mein label hai ki woh kaun si cell cover karte hain, aur milke poori table fill karte hain.

Cell	Scenario class	Jo corner yeh stress karta hai
A	Shared-bus bandwidth split	kaafi masters, ek pipe — $B / N$ bottleneck
B	Crossbar switch count & aggregate BW	quadratic hardware growth; $min (M, S)$ cap
C	Degenerate crossbar ( $M = 1$ ya $S = 1$ )	jab crossbar ek plain wire ban jaata hai
D	Fixed-priority worst-case latency	starving lowest-priority master
E	Round-robin bounded latency	$(N - 1) T$ guarantee, aur "just-missed-my-turn" worst case
F	TDM bandwidth allocation	fractional slot shares; unused-slot waste
G	Single-master edge ( $N = 1$ )	arbitration jab koi ladhne wala hi nahi
H	Real-world word problem	mixed: topology + scheme choose karo, justify karo
I	Exam-style twist	ek "fair-lagta" scheme jo phir bhi starve karta hai

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

Worked examples

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

Forecast: Padhne se pehle per-master number guess karo. 100 MB/s se zyada ya kam?

Shared resource identify karo. Yeh step kyun? Shared bus par ek time mein sirf ek transaction hoti hai (time-division multiplexing). Zyada masters hone se total $B$ multiply nahi hota — woh divide ho jaata hai.
Split apply karo. Saturated per-master share hai $B_{per} = \frac{B}{N} = \frac{133}{10} MB/s .$ Yeh step kyun? $N = 10$ masters baari-baari equal turns lete hain, to har ek pipe ka ek-daswan hissa dekhta hai.
Compute karo. $B_{per} = 13.3 MB/s$ .

Verify: Sanity check — 10 masters $\times$ 13.3 MB/s $= 133$ MB/s $= B$ . Parts milke poore pipe ke barabar hain. ✓ (Yeh bilkul wahi "13 MB/s per device" figure hai jo parent ke PCI example mein thi.)

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

Forecast: Switch count guess karo — kya yeh 7 hai, 11, ya kuch bada?

Figure dekho: har master row har slave column ko cross karti hai, aur har crossing par ek switch (●) baith ta hai.

Crossings count karo. Yeh step kyun? Har master ko har slave tak ek independent path chahiye, isliye switches ek $M \times S$ grid banate hain. $switches = M \times S = 7 \times 4 = 28.$
Concurrency cap lagao. Yeh step kyun? Do masters ek hi slave ko ek saath share nahi kar sakte — isliye simultaneous transfers ki sankhya kabhi bhi $M$ aur $S$ mein se chhote se zyada nahi ho sakti. $concurrent = min (M, S) = min (7, 4) = 4.$
Aggregate bandwidth. Un 4 concurrent links mein se har ek full speed par chalta hai: $B_{agg} = min (M, S) \times B_{link} = 4 \times 20 = 80 GB/s .$

Verify: Sirf 4 slaves hain, isliye ek saath zyada se zyada 4 transfers land ho sakti hain — bandwidth slaves se bottleneck ho rahi hai, 7 masters se nahi. Agar hum (galti se) $M = 7$ use karte to 140 GB/s claim karte, jo impossible hai: 3 masters ke paas likhne ki jagah hi nahi hoti. $min$ asli kaam kar raha hai. ✓

Example 3 — Degenerate crossbar (Cell C)

Forecast: Kya crossbar yahan bhi help karta hai, ya collapse ho gaya?

Switch count. $M \times S = 5 \times 1 = 5$ switches — sirf ek column. Yeh step kyun? Ek slave hone par grid mein sirf ek destination column hoti hai.
Concurrency cap. $min (M, S) = min (5, 1) = 1$ . Yeh step kyun? Sab same slave chahte hain, isliye ek waqt mein sirf ek transfer proceed kar sakti hai.
Aggregate bandwidth. $1 \times B_{link} = B_{link}$ .

Verify: Ek slave ke saath crossbar koi parallelism offer nahi karta — yeh ek shared bus mein degenerate ho jaata hai jiske aage single slave ke liye ek arbiter hai. 5 masters $B_{link}$ ko exactly Example 1 jaisa split karte hain. To crossbar tab hi fayda karta hai jab $S > 1$ ho. ✓ Yeh woh degenerate corner hai jo un logon ko pakadta hai jo assume karte hain "crossbar = hamesha parallel."

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

Forecast: Kya $M_{2}$ ka wait bounded hai ya infinite?

Queue mein aage kaun jaata hai, list karo. Yeh step kyun? Fixed priority hamesha sabse bade requester ko pehle serve karta hai. $M_{2}$ tab serve hota hai jab koi bhi higher master request nahi kar raha.
Higher-priority transactions sum karo. $N = 2$ higher masters ke saath, har ek $T$ ke liye: $T_{worst} = \sum_{i = 0}^{N - 1} T = 2 \times 4 = 8 µs$ agar $M_{0}$ aur $M_{1}$ $M_{2}$ se pehle exactly ek-ek baar bus chahte hain.
Ab pathological case. Yeh step kyun? Agar $M_{0}$ continuously re-request karta rahe, to step 1 kabhi clear nahi hota — $M_{2}$ ka wait unbounded (starvation) hai. 8 µs figure tabhi kaam aata hai jab higher masters ki demand finite ho.

Verify: Units: $2 \times 4 µs = 8 µs$ , ek time — correct. Aur doosre half ka honest answer $\infty$ hai: fixed priority bottom master ko koi latency bound nahi deta. Yahi wajah hai ki parent "debug port indefinitely wait karta hai" flag karta hai. ✓

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

Forecast: Kya round-robin ka bound $4 T$ hoga, $3 T$ , ya $T$ ?

Figure circular counter $C$ dikhata hai jo turns distribute karta hai.

"Just-missed" worst case set up karo. Yeh step kyun? Master $i$ sabse zyada tab wait karta hai jab uski turn abhi-abhi nikal gayi ho — ab baaki sab pehle jaate hain phir uski baari aati hai.
Beech mein aane wale masters count karo. Modulo- $N$ order mein, masters $(i + 1), (i + 2), \dots, (i + N - 1)$ pehle jaate hain — yeh $N - 1 = 3$ masters hain.
Per-turn cap se multiply karo. $T_{latency} \leq (N - 1) T_{m a x} = 3 \times 3 = 9 µs .$

Verify: Har master ke paas ab 9 µs ki finite guarantee hai — koi starvation nahi, unlike Example 4 jahan $M_{2}$ forever wait kar sakta tha. Iska price: ek busy master idle ones ke peeche wait karta hai. Units check: $3 \times 3 µs = 9 µs$ . ✓

Example 6 — TDM slot allocation (Cell F)

Forecast: Kya teen shares milke poore 800 MB/s banengi, ya kuch bandwidth stranded rahegi?

Slot fraction → bandwidth. Yeh step kyun? Ek master poora pipe sirf apne slots ke dauran leta hai; ek poore cycle mein yeh total $B$ ka $n_{i} / N$ fraction dekhta hai. $BW_{i} = \frac{n _{i}}{N} \cdot B .$
Har ek compute karo. $BW_{0} = \frac{5}{8} \times 800 = 500, BW_{1} = \frac{2}{8} \times 800 = 200, BW_{2} = \frac{1}{8} \times 800 = 100 MB/s .$
Slot conservation check karo. $n_{0} + n_{1} + n_{2} = 5 + 2 + 1 = 8 = N$ . Yeh step kyun? Agar assigned slots cycle exactly fill karte hain, to koi slot idle nahi aur koi bandwidth waste nahi hoti.

Verify: Bandwidths ka sum $500 + 200 + 100 = 800 = B$ — poora pipe account ho gaya, kuch stranded nahi. Agar hum sirf 7 slots assign karte, ek slot ( $100$ MB/s) har cycle mein idle rehta, chahe koi master desperate ho — TDM ki rigidity ka cost. ✓

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

Forecast: Kya yahan arbitration ka koi matlab bhi hai?

$N = 1$ ko round-robin bound mein plug karo. $T_{latency} \leq (N - 1) T_{m a x} = 0 \times T_{m a x} = 0.$ Yeh step kyun? Circle mein aur koi hai hi nahi, isliye master kabhi wait nahi karta.
Arbiter logic ki zaroorat. Yeh step kyun? Ek requester ke saath koi conflict resolve karna hi nahi hai — grant permanently high tied ho sakta hai. Zero arbitration gates chahiye.

Verify: Ek single-master bus ko koi arbiter nahi chahiye aur zero contention latency hai — woh degenerate baseline jis tak har scheme ko reduce hona chahiye. Dono formulas ( $T_{worst}$ fixed priority ke liye 0 higher masters ke saath, aur round-robin ke liye $(N - 1) T$ ) correctly $0$ par collapse karte hain. ✓

Example 8 — Real-world word problem: topology choose karo (Cell H)

Forecast: Shared bus par crossbar ka speed-up factor guess karo.

Shared-bus throughput. Sab 5 masters ek pipe split karte hain: $40 GB/s$ total, $8 GB/s$ each (Cell A logic).
Crossbar throughput. Yeh step kyun? Independent masters alag-alag banks hit karte hue concurrently run karte hain, $min (M, S) = min (5, 5) = 5$ tak: $B_{agg} = 5 \times 40 = 200 GB/s .$
Speed-up. $200/40 = 5 \times$ . Crossbar paanchguna jeetta hai kyunki accesses alag slaves par hain.
Arbitration choice. Yeh step kyun? Audio DMA ko ek guaranteed deadline chahiye. Fixed priority isko starve kar sakta hai agar yeh low priority par hai; round-robin uski wait $(N - 1) T$ tak bound karta hai; TDM isko ek reserved slot deta hai isliye uski bandwidth deadline-guaranteed hai. TDM choose karo (ya round-robin with reserved share) — hard-real-time master ke liye kabhi plain fixed priority nahi.

Verify: Shared $8$ GB/s each vs crossbar $200$ GB/s aggregate; $200 = 5 \times 40$ aur speed-up $= 5$ , exactly $min (M, S)$ jaisa theory predict karta hai. Units sab GB/s. ✓

Example 9 — Exam twist: "fair-lagta" scheme jo phir bhi starve karta hai (Cell I)

Forecast: True round-robin waits bound karta hai — kya yeh variant bhi karta hai?

Scan trace karo. Yeh step kyun? "Master 0 se resume karo" yahi trap hai: har grant ke baad pointer $M_{0}$ par reset hota hai, $M_{0}$ ke successor par nahi. To scan order hamesha $M_{0}, M_{1}, M_{2}$ upar se hota hai.
Greedy master follow karo. $M_{0}$ hamesha request karta hai aur hamesha pehle scan hota hai → $M_{0}$ ko har single round mein grant milta hai. Jab tak $M_{0}$ active hai scan kabhi $M_{2}$ tak nahi pahuncha.
Diagnose karo. Yeh disguise mein fixed priority hai — reset woh "starting point rotate karo" property destroy kar deta hai jo real round-robin ko fair banati hai. $M_{2}$ ka wait unbounded hai → starvation.
Fix. Master $C$ ko grant karne ke baad, start pointer $(C + 1) mod N$ par advance karo taaki already-served master line ke peeche chala jaaye. Tab bound $(N - 1) T_{m a x} = 2 \times 2 = 4 µs$ restore ho jaata hai.

Verify: Broken variant: $M_{2}$ $\infty$ wait karta hai (starves). Correct rotating variant: bound $= (3 - 1) \times 2 µs = 4 µs$ . "0 se resume vs $C + 1$ se resume" ek single word fair ko unfair mein flip kar deta hai — classic exam gotcha. ✓

Recall

Round-robin worst-case wait

N

masters ke liye, per-turn cap

T_{m a x}

(N - 1) T_{m a x}

Crossbar switch count

M

masters aur

S

slaves ke liye

M \times S

Crossbar peak concurrent transfers

min (M, S)

TDM bandwidth ek master ke liye jiske paas

N

slots mein se

n_{i}

slots hain, pipe

B

par

\frac{n _{i}}{N} B

Fixed priority ek real-time master ke liye unsafe kyun ho sakti hai

lowest-priority master indefinitely starve kar sakta hai (unbounded latency)

S = 1

wala crossbar kya ban jaata hai

ek plain shared bus (koi parallelism nahi,

min (M, 1) = 1

)

Connections

Parent: Bus topologies and arbitration
Deeper mesh interconnects: Network-on-Chip
Point-to-point at scale: PCIe architecture
Masters kaun hote hain aksar: DMA, aur slaves kaise respond karte hain: Memory controllers
Neeche signalling: Bus protocols and signals
Shared reads complicated kyun ho jaate hain: Cache coherence