False sharing problem: Worked examples — Hinglish deep dive

6.1.10 · D3 · Hardware › Parallelism & Multicore › False sharing problem

Kuch bhi shuru karne se pehle, ek measurement pin down karte hain jis par sab kuch tika hai.

Scenario matrix

Har false-sharing situation inhi case classes mein se ek hai. Har worked example us cell ke saath tagged hai jise woh fill karta hai.

#	Case class	Woh question jo yeh answer karta hai	Example
A	Adjacent, tightly packed	Kya neighbouring array elements ek line share karte hain?	Ex 1
B	Boundary straddle	Agar ek variable do lines span kare toh?	Ex 2
C	Zero-cost / no sharing	Kab spacing already humein bachati hai?	Ex 3
D	Degenerate: single writer	Kya ek core ke saath bhi false sharing hoti hai?	Ex 4
E	Padding fix, exact	Exactly kitna padding kaafi hai?	Ex 5
F	Over-alignment trap	8-byte align kyun fail hoti hai, 64 kyun kaam karti hai	Ex 6
G	Limiting case: many cores	Cost kaise scale hoti hai jab cores → large?	Ex 7
H	Real-world word problem	Ek counter benchmark end-to-end time karna	Ex 8
I	Exam twist: partial sharing	Kuch cores clash karte hain, kuch nahi — unhe gino	Ex 9

Hum sab ke liye same tool banate hain: har variable ke liye $line (A) = ⌊ A /64 ⌋$ compute karo, phir dekho kaun se indices collide karte hain.

Worked examples

Worked example Example 1 — Case A: Adjacent packed counters

Ek int 4 bytes ka hota hai. Hamare paas int counter[4] hai jo address 0x1000 se shuru hota hai. Cores 0–3 har ek apne element ko ek loop mein increment karte hain. Kaun se elements ek cache line share karte hain?

Forecast: Abhi guess karo — yeh chaar counters kitni distinct cache lines occupy karte hain? Ek? Do? Chaar?

Har address likho. Element $i$ $0 x 1000 + 4 i$ par baithta hai: toh 0x1000, 0x1004, 0x1008, 0x100C. Yeh step kyun? Addresses hi woh cheez hai jo hardware dekhta hai. Variable names coherence protocol ko kuch nahi lagti.
0x1000 ko decimal mein convert karo. $0 x 1000 = 4096$ . Chaar addresses hain $4096, 4100, 4104, 4108$ . Yeh step kyun? Line-index formula ek plain number divide karta hai; pehle hex chhodni padegi.
Har line index compute karo $⌊ A /64 ⌋$ se: $⌊ 4096/64 ⌋ = 64$ , $⌊ 4100/64 ⌋ = 64$ , $⌊ 4104/64 ⌋ = 64$ , $⌊ 4108/64 ⌋ = 64$ . Yeh step kyun? Equal line indices ⇒ same line ⇒ false sharing. Charon index 64 hain.
Conclusion: charon counters ek cache line mein rehte hain. Har core ka increment baaki teeno copies ko invalidate karta hai → maximal ping-pong. Yeh step kyun? Yeh woh classic worst case hai jiske baare mein parent note ne warn kiya tha.

Verify: $4096 = 64 \times 64$ exactly, aur $4108 - 4096 = 12 < 64$ , toh charon block $[4096, 4159]$ ke andar fit hote hain. Answer: 1 line, full contention. ✓

Worked example Example 2 — Case B: Boundary straddle

Ek struct 16 bytes ka hai, aur unka ek array 0x1000 se shuru hota hai. Kaun sa array element pehla hai jiska start address ek naye cache line mein aata hai, aur kya koi single 16-byte element yahan do lines mein split hota hai?

Forecast: Kya koi element ek line boundary se adha-adha ho jaayega?

Element $i$ $0 x 1000 + 16 i = 4096 + 16 i$ par shuru hota hai. Elements: 4096, 4112, 4128, 4144, 4160, ... Yeh step kyun? Stride sizeof(struct) = 16 hai, 4 nahi; spacing sab kuch set karti hai.
Har ka line index: $⌊ 4096/64 ⌋ = 64$ , $⌊ 4112/64 ⌋ = 64$ , $⌊ 4128/64 ⌋ = 64$ , $⌊ 4144/64 ⌋ = 64$ , $⌊ 4160/64 ⌋ = 65$ . Yeh step kyun? Hum index mein pehla jump dekhte hain. Yeh element 4 (0x1010 = 4160) par hota hai, line 65 ki shuruwat.
Split element check karo. Line 64 bytes $[4096, 4159]$ cover karta hai. Element 3 4144 par shuru hota hai aur $4144 + 15 = 4159$ par khatam — exactly fit. Element 4 fresh 4160 par shuru hota hai. Yeh step kyun? Split tab hoti hai jab ek element ka start aur end alag blocks mein hon. Kyunki $4096$ 64 ka multiple hai aur 16, 64 ko divide karta hai, koi 16-byte element kabhi straddle nahi karta.
Conclusion: naye line mein pehla element element 4 hai; koi element straddle nahi karta kyunki 16, 64 ko evenly divide karta hai aur base line-aligned hai. Yeh step kyun? Straddling tab matter karti hai jab struct $L$ ka divisor nahi hota — tab ek variable do invalidations ka cost le sakta hai.

Verify: Elements 0–3 line 64 share karte hain; element 4 line 65 kholta hai. $4160 = 65 \times 64$ . ✓

Worked example Example 4 — Case D: Degenerate single writer

int counter[4] 0x1000 par, lekin sirf Core 0 hi kabhi write karta hai; Cores 1–3 kabhi array ko touch nahi karte. Kya false sharing hai?

Forecast: Same layout jaise Example 1 — kya answer badalta hai?

Definition yaad karo: false sharing ke liye alag cores se same line par writes chahiye. Yeh step kyun? Layout akela kaafi nahi; writers ka conflict hona chahiye.
Yahan sirf ek core likhta hai. Line Core 0 ke cache mein Modified rehti hai aur kisi aur se kabhi invalidate nahi hoti. Yeh step kyun? Ek single writer ke saath, MESI Modified state kabhi disturb nahi hoti.
Conclusion: Example 1 jaise hi addresses, lekin zero false sharing — kyunki invalidation trigger karne ke liye koi doosra writer nahi hai. Yeh step kyun? Yeh crucial degenerate case hai: false sharing access pattern ki property hai, sirf layout ki nahi.

Verify: Invalidating remote writers ki sankhya $= 0 \Rightarrow$ coherence traffic $= 0$ . ✓ (Dekhein Cache coherence protocols ki akela Modified line sasta kyun rehta hai.)

Worked example Example 5 — Case E: Exact padding fix

Hum chahte hain ki har int counter apni 64-byte line par ho. Padded struct ka size kya hai, aur 4-byte int ke baad kitne padding bytes jaate hain?

Forecast: 60 bytes of padding? 64? Kuch aur?

Padded size formula. sizeof = 4 ko lines ki poori sankhya tak round up karne ke liye: $padded = ⌈ \frac{4}{64} ⌉ \times 64 = 1 \times 64 = 64 bytes .$ Symbol $⌈ x ⌉$ (ceiling) upar round karta hai — hum upar isliye round karte hain kyunki isolate karne ke liye hum kabhi ek whole line se kam use nahi kar sakte. Yeh step kyun? Line mein koi bhi leftover ek neighbour ko use share karne dega.
Padding bytes = padded − payload $= 64 - 4 = 60$ bytes. Yeh step kyun? int 4 use karta hai, toh 60 bytes filler line complete karta hai.
Separation check karo. Element $i$ ab $0 x 1000 + 64 i$ par shuru hota hai. Line indices: $⌊(4096 + 64 i) /64 ⌋ = 64 + i$ — sab distinct. Yeh step kyun? Distinct indices guarantee karte hain ki fix kaam kiya; yeh parent note ka padding formula action mein hai.

Verify: Padded size $64$ , padding $60$ , aur consecutive line indices $64, 65, 66, 67$ sab alag hain. ✓ (C++17 route Cache line size and alignment mein cross-check karo.)

Worked example Example 6 — Case F: The over-alignment trap

Ek colleague har counter ko 8 bytes tak align karta hai aur expect karta hai ki false sharing gaayab ho jaayegi. Addresses ban jaate hain 0x00, 0x08, 0x10, 0x18, 0x20, 0x28, 0x30, 0x38. Pehli cache line mein kitne share karte hain?

Forecast: Kya 8-byte alignment ise fix karta hai?

Decimal addresses list karo: $0, 8, 16, 24, 32, 40, 48, 56$ . Yeh step kyun? Alignment stride set karta hai, lekin 8 ≪ 64.
Har ka line index: $⌊ 0/64 ⌋$ se $⌊ 56/64 ⌋$ tak sab $0$ ke barabar. Yeh step kyun? 64 se neeche ka har address line 0 mein hai. Aath counters, ek line.
64-byte alignment se contrast: addresses $0, 64, 128, 192, \dots$ line indices $0, 1, 2, 3, \dots$ dete hain — sab distinct. Yeh step kyun? Alignment $L$ ke barabar (ya zyada) honi chahiye isolation guarantee karne ke liye; koi bhi chhota multiple variables per line repack karta hai.
Conclusion: 8-byte alignment 8 counters line 0 mein chhodta hai → abhi bhi full false sharing. Sirf $\geq 64$ -byte alignment kaam karta hai. Yeh step kyun? Yeh exactly wahi galti hai jo parent note mein flag ki gayi thi.

Verify: $⌊ 56/64 ⌋ = 0$ toh sab 8 line 0 mein; $⌊ 64/64 ⌋ = 1 \neq = 0$ toh 64-align separate karta hai. ✓

Worked example Example 7 — Case G: Limiting behaviour, many cores

$N$ cores har ek ek single shared 64-byte line mein ek int own karte hain aur sab spin-increment karte hain. Jaise $N$ badhta hai, total coherence cost roughly kaise scale hoti hai? Ek single remote write $\approx 150$ cycles maano.

Forecast: $N$ mein linear? Quadratic? Constant?

Per line-transfer cost fixed hai $T_{coherence} \approx 150$ cycles (ek invalidate-and-fetch round trip). Yeh step kyun? Yeh ping-pong cost ki atomic unit hai.
Rounds jab tak har core ek baar likh le: worst case mein line cores ke beech bounce karti hai, toh sab cores mein $K$ total writes produce karne mein lagbhag $K \times 150$ cycles lagte hain — writes serialize hoti hain. Yeh step kyun? Ek time par sirf ek core line Modified hold kar sakta hai, toh parallelism ek queue mein collapse ho jaati hai.
Limiting behaviour: $K$ total writes ke liye, time $\approx 150 K$ cycles regardless ki aap unhe cores mein kaise split karo — cores add karne se koi speedup nahi milti, aur effective throughput girti hai jaise $N$ badhta hai kyunki contention badh jaati hai. Yeh step kyun? Isliye false sharing Multicore scaling destroy karta hai: woh workload jo "embarrassingly parallel" hona chahiye strictly serially chalti hai.
Numeric anchor: $K = 1 0^{6}$ contended writes $\Rightarrow\approx 150 \times 1 0^{6} = 1.5 \times 1 0^{8}$ cycles. 3 GHz core par woh $0.05$ s pure coherence stall hai. Yeh step kyun? Abstract scaling ko wall-clock feel mein turn karta hai.

Verify: $150 \times 1 0^{6} = 1.5 \times 1 0^{8}$ cycles; $\frac{1.5 \times 1 0 ^{8}}{3 \times 1 0 ^{9}} = 0.05$ s. ✓

Worked example Example 8 — Case H: Real-world benchmark

Do configs 4 cores par $1 0^{7}$ increments per core run karti hain. Padded version: har write $\approx 2$ cycles. False-shared version: har write $\approx 100$ cycles. Core clock $= 2 GHz$ . Dono wall-clock times aur slowdown factor nikalo.

Forecast: Kitne seconds ka fark hai?

Padded total cycles = writes × cost. Lekin padded writes 4 cores par parallel proceed karti hain, toh per-core time $1 0^{7}$ writes use karta hai: $1 0^{7} \times 2 = 2 \times 1 0^{7}$ cycles per core. Yeh step kyun? Koi shared line nahi → cores overlap karte hain → ek core measure karo.
Padded time: $\frac{2 \times 1 0 ^{7}}{2 \times 1 0 ^{9}} = 0.01$ s. Yeh step kyun? cycles ÷ (cycles/second) = seconds. Units: $\frac{cycles}{cycles / s} = s$ .
False-shared total serialize karta hai: sab $4 \times 1 0^{7} = 4 \times 1 0^{7}$ writes queue karte hain, har ek $100$ cycles: $4 \times 1 0^{7} \times 100 = 4 \times 1 0^{9}$ cycles. Yeh step kyun? Contention one-at-a-time force karta hai (Example 7 ki logic).
False-shared time: $\frac{4 \times 1 0 ^{9}}{2 \times 1 0 ^{9}} = 2$ s. Yeh step kyun? Same clock conversion.
Slowdown: $\frac{2}{0.01} = 200 \times$ . Yeh step kyun? Disaster quantify karta hai.

Verify: padded $0.01$ s, shared $2$ s, ratio $200$ . Sanity: parent note ke "50–100×+" ke order-of-magnitude se match karta hai (yahan zyada hai kyunki hum 4 cores par bhi serialize kar rahe hain). ✓

Worked example Example 9 — Case I: Exam twist, partial sharing

Aath int counters 0x3000 par, toh addresses 0x3000, 0x3004, ..., 0x301C (pehle 8). Cache line $L = 64$ . Aath cores har ek ek likhta hai. Kitni distinct cache lines hain, aur kitne cores clash karte hain per line?

Forecast: Sab 8 ek line mein, ya split?

Addresses: $0 x 3000 = 12288$ se $12288 + 4 \times 7 = 12316$ tak. Yeh step kyun? 8 ints mein stride 4 bytes $32$ bytes span karta hai.
Line indices: $⌊ 12288/64 ⌋ = 192$ aur $⌊ 12316/64 ⌋ = 192$ — har ek 192 hai. Yeh step kyun? $12316 - 12288 = 28 < 64$ , toh sab line 192 mein fit hote hain.
Count: 1 distinct line, 8 cores uss par clashing — densest possible contention. Yeh step kyun? Yeh trap answer hai: log assume karte hain ki 8 ints "zaroor" spread out honge, lekin $32$ bytes adhi line hai.
Twist follow-up: do groups of 4 (2 lines) mein split karne ke liye, har int ko 8 bytes tak pad karo? Nahi — Example 6 ne yeh maar diya. Tumhe 64-byte stride chahiye toh har ek apni line khole: 8 counters → 8 lines. Yeh step kyun? Reinforce karta hai ki sirf $\geq L$ stride isolate karta hai.

Verify: $⌊ 12316/64 ⌋ = 192 = ⌊ 12288/64 ⌋$ ; ek line, 8 writers. ✓

Recall Self-test

Sab hex→decimal, phir $⌊ A /64 ⌋$ . Kya ek line boundary se shuru hone wale do variables jo 40 bytes apart hain ek line share karte hain? ::: Haan — $40 < 64$ , dono same index par floor karte hain. Kitne padding bytes ek 4-byte int ko 64-byte line par isolate karte hain? ::: $64 - 4 = 60$ bytes. Kya 8-byte alignment false sharing rok deti hai? ::: Nahi — 8 variables abhi bhi ek 64-byte line mein pack ho jaate hain. Kya false sharing hoti hai agar sirf ek core kabhi line likhti hai? ::: Nahi — false sharing ke liye ≥ 2 alag cores se writes chahiye. False-shared counter loop mein cores add karne se kyun madad nahi milti? ::: Single Modified line sab writes serialize karti hai; parallelism collapse ho jaati hai.

Related building blocks: Cache coherence protocols · Cache line size and alignment · Atomic operations · Lock-free data structures · Memory allocators · NUMA architectures · Multicore scaling · wapas parent topic par.