Visual walkthrough — Bus topologies and arbitration

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

Parent note ne tumhare saamne ek clean-dikhta result rakha tha:

$T_{\text{latency}}\le (N-1)\cdot T_{\max }$

round-robin arbitration ke liye. Lekin yeh number $N-1$ aata kahan se hai? $N$ kyun nahin, ya $N+1$? Aur $T_{\max }$ asal mein kya measure kar raha hai? Yeh page uss inequality ko bilkul pehle idea se rebuild karta hai — koi bhi symbol use nahi hoga jab tak usse draw na kar liya jaaye.

---

Step 0 — Symbols se pehle ke words

Kisi bhi formula se pehle, hum plain-language meanings par agree karte hain aur har ek ko ek picture se pin karte hain.

Masters ki sankhya ko hum $N$ kahenge. Toh $N$ bas kitne devices circle mein hain — ek seedha counting number jaise $N=4$.

Figure mein: chaar rounded boxes ($M_0,M_1,M_2,M_3$) sab ek horizontal bar — bus — ki taraf haath badhate hain. Referee (beech mein chhota circle) ek waqt mein sirf unme se ek ko hi pass kar sakta hai. Baaki sab wait karte hain. Yeh "waiting" hi is page ka poora subject hai.

---

Step 1 — "Circular order" ko ek pointer mein badalna

KYA. Round-robin ka matlab hai: jab ek master khatam karta hai, toh fixed circle mein agla master pehle chance paata hai. Hum "kiska turn hai" ko ek single number $C$ se, yaani ek pointer se, encode karte hain.

Priority list kyun nahin, pointer kyun? Kyunki rule positional hai, importance-based nahin. Koi permanently pehle nahin hai. Sirf yeh matter karta hai ki "pointer abhi kahaan khada hai." Ek integer usse poori tarah capture karta hai.

PICTURE.

Chaar masters ek clock face par baithe hain. Arrow $C$ hai, woh pointer, jo abhi $M_1$ ki taraf point kar raha hai. Chhota curved arrow sirf woh motion dikhata hai jo allowed hai: ek turn ke baad, $C$ ek seat clockwise step karta hai.

Hume modulo ki zaroorat kyun hai? Kyunki koi "seat $N$" nahin hai. Seats numbered hain $0,1,\dots ,N-1$ — total $N$ seats hain. $\mathrm{mod}N$ guarantee karta hai ki pointer sirf koi real seat name kare.

---

Step 2 — "Ek turn mein kitna time lagta hai" — $T_{\max }$ define karna

KYA. Har transaction kuch time leta hai. Alag-alag transactions alag-alag time lete hain, lekin ek sabse lamba possible wala hota hai. Hum us ceiling ko $T_{\max }$ kehte hain.

Average kyun nahin, maximum kyun? Hum ek worst-case sawaal pooch rahe hain ("mujhe kitna wait karna pad sakta hai?"). Worst case ka matlab hai: maano ki tumse aage har master ne sabse dheemi legal transaction li. Averages ek alag sawaal ka jawab denge (typical wait). Real-time guarantees ke liye, sirf ceiling safe hai.

PICTURE.

Teen transactions alag-alag lengths ke saath ek timeline par hain. Ek dashed line $T_{\max }$ mark karti hai — sabse unchai wali. Har real transaction us line ke neeche fit hoti hai:

$T_{\text{transaction}}\le T_{\max }.$

• $T_{\text{transaction}}$ — kisi real turn ki actual length.
• $T_{\max }$ — woh promise: koi bhi single turn itne se zyada nahi chalega.

Yeh ceiling hi hai jo baad mein hume alag-alag times ki ek messy list add karne ki jagah multiply karne deti hai.

---

Step 3 — Woh badkismat moment: "Main apna turn abhi-abhi miss kar gaya"

KYA. Ek chosen master — isse $M_i$ kahein — ke liye sabse bura wait dhundhne ke liye, hum isse sabse badkismat situation mein rakhte hain.

Exactly yahi moment kyun? Pointer seat $i$ se ek tick pehle guzar gaya, bilkul us waqt jab $M_i$ ne decide kiya ki use bus chahiye. Toh $M_i$ ko ab wait karna hoga jab tak pointer poora baaki circle travel kare aur seat $i$ par vapas aa jaaye.

PICTURE.

Pointer (red) $M_i$ (shaded) se theek aage baitha hai. Green arc woh safar dikhata hai jo pointer ko $M_i$ par dobara point karne se pehle abhi karna hai. Woh arc hi woh poori waiting time hai jise hum abhi measure karne wale hain.

---

Step 4 — Exactly kitne masters aage jaate hain, yeh count karna

KYA. Woh seats list karo jinhein pointer $M_i$ par vapas aane se pehle visit karta hai.

Unhein explicitly count kyun karein? Kyunki $N-1$ ka jawab counting se milta hai, guess se nahin. Hum literally queue enumerate karte hain.

PICTURE.

$M_i$ se theek aage se shuru karke, pointer iss order mein visit karta hai:

$M_{(i+1)\mathrm{mod}N},M_{(i+2)\mathrm{mod}N},\dots ,M_{(i+N-1)\mathrm{mod}N}$

• $(i+1)\mathrm{mod}N$ — $M_i$ ke theek baad ki seat.
• $(i+N-1)\mathrm{mod}N$ — $M_i$ se theek pehle ki seat (humse aage wali aakhri). Check karo: $(i+N-1)\mathrm{mod}N=(i-1)\mathrm{mod}N$, exactly $M_i$ ke peechay wali seat. Sahi — yahi aakhri competitor hai.

List count karo: offsets run karte hain $1,2,\dots ,N-1$. Yeh exactly $N-1$ masters hain. Yahan se aata hai $N-1$ — yeh circle mein doosri seats ki sankhya hai. ($N$ total seats, minus apni khud ki = $N-1$ doosri.)

---

Step 5 — Sum ko ceiling se replace karna: bound appear hoti hai

KYA. Har unknown $T_{\text{transaction}}$ ko Step 2 ki ceiling $T_{\max }$ se swap karo.

Hum yeh karne ki permission kyun rakhte hain? Kyunki Step 2 mein humne prove kiya ki har term $\le T_{\max }$ hai. Sum mein har term ko kisi aisi cheez se replace karna jo kam se kam utni badi ho, sum ko sirf bada ya barabar kar sakta hai — kabhi chhota nahin. Toh result ek safe upper bound hai.

PICTURE.

True sum ke uneven bars sab "uthaye" jaate hain ek hi height $T_{\max }$ tak. Total area sirf badhta hai. Ab $N-1$ bars mein se har ek ki identical height hai, toh unhe add karna bas multiplication hai:

${\sum }_{j=1}^{N-1}{T}_{\text{transaction},(i+j)\mathrm{mod}N}\le \underset{\text{kitne}}{\underbrace{(N-1)}}\times \underset{\text{har ek, zyada se zyada}}{\underbrace{T_{\max }}}$

---

Step 6 — Edge cases (koi bhi scenario bina dikhaye mat chhoḍo)

KYA. $N$ ki boundary values aur "koi aur maang nahin raha" wale case ko check karo.

PICTURE.

Case	Kya hota hai	Formula check
$N=1$	Ek master, akela. Koi competition nahin.	$(1-1)\cdot T_{\max }=0$. Wait zero hai — sahi.
$N=2$	Tum aur ek rival.	$(2-1)\cdot T_{\max }=T_{\max }$ — zyada se zyada ek doosre turn ka wait. Sensible.
Idle skip	Aage ki kuch seats actually bus nahin chahti.	Arbiter silent seats ko turant skip karta hai, toh real wait aksar bound se kaafi neeche hoti hai. $\le$ phir bhi hold karti hai — yeh worst case hai, typical case nahin.
Large $N$	Kai masters.	Wait linearly badhti hai: $O(N)$. Yeh round-robin ki cost hai — fairness slow ho jaati hai jab circle bada ho. Ek [[Crossbar

---

Ek-picture summary

Yeh single figure poori kahani ko thread karta hai: pointer abhi $M_i$ se guzara (Step 3) → use $N-1$ seats aage visit karni hain (Step 4) → har visit $T_{\max }$ par capped hai (Step 2) → $N-1$ caps stack karne se total milta hai (Step 5) → aur $N=1$ wala corner poori cheez ko zero par collapse kar deta hai (Step 6).

Recall Feynman retelling — isko ek story ki tarah bolo

Socho chaar dost ek swing share kar rahe hain. Ek rule hai: jab tum swing karo, toh circle mein agla dost swing paata hai — ek pointer bus ring ke around step karta hai. Ab maano tumne pointer ko theek us waqt miss kiya jab tumhe turn chahiye tha. Worst case mein kitna wait? Tumhe pointer ko pehle baaki sabke paas se guzarne dena hoga — woh teen doosre dost hain, yaani $N-1$. Unme se har ek sabse lamba allowed turn, $T_{\max }$, le sakta hai. Toh tumhara worst wait teen lamba turns hai: $(N-1)$ dost times $T_{\max }$ each. Aur agar tum swing par akele the? $N=1$, toh $(1-1)=0$ — koi wait nahin, jo obviously sahi hai. Yahi poora formula hai, aur yeh tumhe kabhi itne se zyada wait nahin karne dega.

Recall Quick self-check

$N-1$ kahan se aata hai? ::: Yeh worst case mein tumse aage doosre masters ki count hai — sab $N$ seats minus tumhari khud ki. $T_{\max }$ kyun, average transaction time kyun nahin? ::: Hum ek worst-case guarantee chahte hain; real-time deadlines ke liye sirf ceiling safe hai. $(C+1)\mathrm{mod}N$ mein $\mathrm{mod}N$ kya karta hai? ::: Yeh pointer ko last seat se vapas seat 0 par wrap karta hai, line ko ek circle mein close karta hai. Tumhara khud ka turn wait mein count kyun nahin hota? ::: Tumhara turn wait ke ant mein inaaam hai, uska hissa nahin. $N=1$ par formula kya deta hai, aur yeh sahi sanity check kyun hai? ::: Zero — ek akela master kisi ka wait nahin karta, toh koi bhi sahi formula yahan vanish ho jaana chahiye.

Yeh bhi dekho: Bus protocols and signals · Cache coherence · PCIe architecture · 6.3.01 Bus topologies and arbitration (Hinglish)