False sharing problem: Foundations — Hinglish deep dive

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

Is page pe kuch bhi assumed nahi hai. False sharing problem samajhne se pehle tumhe kuch ideas chahiye — memory ek ruler of addresses ki tarah, "cache" kya hota hai, "cache line" kya hoti hai, aur thoda sa arithmetic ( $⌊ \cdot ⌋$ , the floor function) jo parent note use karta hai. Hum ek-ek cheez build karte hain, use ek picture se anchor karte hain, phir dikhate hain kaise sab milke is topic mein jud jaata hai.

1. Memory ek lambi numbered street hai

Pehle, computer memory ko ek single bahut lambi street ki tarah imagine karo jahan har byte (ek storage slot jo 0 se 255 tak koi number hold karta hai) ka ek house number hota hai. Woh house number address kehlata hai.

Hexadecimal kyun aur ordinary base-10 kyun nahi? Kyunki memory sizes aur boundaries powers of two hoti hain, aur hex unke saath cleanly align hoti hai: 0x40 exactly 64 decimal mein hai, 0x80 hai 128, aur aage bhi. Figure dekho — har tick ek byte hai; uske neeche number uska address hai.

Recall Hum ek hex address ko ordinary decimal number mein kaise convert karte hain?

Har hex digit 16 ki ek power hai. 0x1000 ke liye: $1 \times 1 6^{3} + 0 + 0 + 0 = 1 \times 4096 = 4096$ . 0x1004 ke liye: $1 \times 1 6^{3} + 0 + 0 + 4 = 4096 + 4 = 4100$ . Hum baad mein exactly yahi do conversions reuse karenge.

2. Ek variable ek address pe rehta hai aur uski ek size hoti hai

Jab tum code mein int counter likhte ho, machine street pe uske liye ek stretch reserve karti hai. Do baatein matter karti hain:

Kahan se start hota hai — uska address, kisi variable $v$ ke liye $addr (v)$ likha jaata hai.
Kitna wide hai — bytes mein uski size, $sizeof (v)$ likha jaata hai.

Toh ek array int counter[2] mein counter[0] ko $addr = 0x1000$ pe rakh sakta hai (bytes 0x1000–0x1003 leke) aur counter[1] uske bilkul baad $0x1004$ pe. Yeh alag-alag variables hain lekin street pe adjacent hain. Is baat ko yaad rakho — yahi pura trap hai.

3. Cache: har core ke paas ek fast desk

Ek core CPU ke andar ek independent worker hai jo instructions run karta hai. Main memory (woh lambi street) bahut door aur slow hai. Isliye har core apne paas ek chhota, fast personal notebook rakhta hai jise cache kehte hain.

Yahan woh catch hai jo poori story shuru karti hai: cache ek baar mein ek byte copy nahi karta.

4. Cache line: transfer ki unit

Jab ek core ko sirf ek byte chahiye hota hai, cache uske aaspaas ka pura ek fixed-size block fetch karta hai. Woh block ek cache line hoti hai. Is poore page mein hum ek cache line ko ek fence ki tarah bhi picture karenge — same 64-byte block ke liye ek visual nickname, kuch aur nahi.

Figure dekho: street ko ab fixed 64-byte fences (cache lines) mein group kiya gaya hai. Notice karo counter[0] (orange) aur counter[1] (teal) dono same fence ke andar hain. Hardware sirf poori fence move kar sakta hai — kabhi bhi sirf ek variable nahi. Yahi parent note ki roommate analogy ka "folder, not the page" hai.

Hum chahte hain ek formula likhna "koi address kis cache line mein belong karta hai?", lekin uske liye ek arithmetic tool chahiye — floor function — jo abhi define nahi kiya. Toh pehle woh tool build karte hain (Section 5), phir formula state karte hain.

5. Floor function $⌊ x ⌋$ — topic ko yeh kyun chahiye

Exactly yahi tool kyun, aur ordinary division ya rounding kyun nahi? Kyunki hum ek grouping question pooch rahe hain: "yeh byte kisi 64-byte fence ke andar kahan hai?" Address ko 64 se divide karke remainder drop karne se exactly fence number milta hai, chahe byte fence ke andar kahin bhi ho. Rounding (jo upar ja sakti hai) fence ke edge ke paas bytes ko agle fence mein galat jagah rakh deti. Floor woh tool hai jo exactly "kaun sa whole block?" ka jawab deta hai.

Ab floor define ho gaya, toh woh promised formula likh sakte hain.

Figure arithmetic ko walk karti hai: address ko 64 se divide karo, ek decimal pe aao, aur floor karo. Dono counters same integer pe floor karte hain — isliye woh ek line share karte hain.

Common mistake "Kya hoga agar koi variable do lines ki boundary ke beech mein ho?"

Yeh tidy condition $⌊ addr (v_{i}) / L ⌋ = ⌊ addr (v_{j}) / L ⌋$ silently assume karti hai ki har variable ek hi cache line ke andar completely fit hota hai — yeh sach hai ek 4-byte int ke liye jo 4-byte boundary pe start hota hai. Ek bada ya misaligned variable do lines span kar sakta hai: uska pehla byte line $k$ pe floor karta hai lekin uska aakhri byte line $k + 1$ pe. Tab woh dono lines ke neighbours ke saath false-share kar sakta hai. Strict test hai "kya do variables ke byte ranges $[addr, addr + sizeof)$ koi common line touch karte hain?" Is foundations page ki har cheez ke liye hum simple single-line case pe stick karte hain; spanning case isliye hai kyun real code Cache line size and alignment ki bhi parwah karta hai.

6. Coherence: copies ko honest rakhna

Agar har core ek line ki apni copy cache karta hai, toh kya hoga jab ek core ek byte change kare? Baaki saari copies ab stale (purani) ho jaati hain. Woh rule jo har core ko ek consistent view deta hai woh cache coherence hai, aur parent note ek specific protocol name karta hai: MESI.

Woh rule jo bite karta hai: ek hi core ek line ko ek baar mein Modified state mein hold kar sakta hai. Isliye har write writer ko baaki sabko invalidate karne ke liye majboor karta hai — aur agar do cores ek hi line ko likhte rehte hain, toh woh ek doosre ki copy nikaalte rehte hain. Woh baar-baar aana-jaana hi woh "ping-pong" hai jo parent note describe karta hai. Tumhe yahan protocol ki poori detail ki zaroorat nahi; Cache coherence protocols use cover karta hai. Bas yaad rakho: ek write poori line ka exclusive ownership maangta hai.

7. Cost, cycles mein measure ki gayi

Parent note cycles mein numbers quote karta hai. Ek cycle CPU clock ki ek tick hai — time ki sabse chhoti unit jo processor count karta hai.

Yeh ~50–100× gap isliye hai ki false sharing ek poore topic ka topic kyun hai: kaam identical hai, lekin hidden coherence traffic uski cost multiply kar deta hai.

Saab kuch milaakar

Neeche ka map bottom-up padha jaata hai aur figures mirror karta hai: addresses ki street (figure s01) aur fence carving (figure s02) se tumhein variables milte hain jo ek line share karte hain; floor arithmetic (figure s03) prove karta hai ki woh share karte hain; coherence ka one-writer rule aur cycle cost us shared line ko false-sharing slowdown mein badal deta hai.

Ise bottom-up padho: memory mein adjacency (s01, s02) aur floor test (s03) aur coherence ka per-line ownership rule = false sharing, aur cycle cost woh hai jo ise hurt karta hai.

Equipment checklist

Right side cover karo aur mechanism page pe jaane se pehle har ek ka jawab do.

Address kya hota hai, aur hum ise hex mein kyun likhte hain? ::: Ek whole number jo memory ka ek byte name karta hai; hex isliye kyunki memory boundaries powers of two hoti hain aur cleanly align hoti hain (0x40 = 64).
0x1000 aur 0x1004 ko decimal mein convert karo. ::: $1 \times 1 6^{3} = 4096$ , aur $4096 + 4 = 4100$ .
$addr (v)$ aur $sizeof (v)$ ka matlab kya hai? ::: Variable $v$ ke pehle byte ka address, aur $v$ kitne consecutive bytes occupy karta hai.
Cache kya hai, aur har core ke paas ek kyun hoti hai? ::: Ek chhoti fast per-core memory copy; usse pahunchne mein ~1–2 cycles lagte hain versus main memory ke liye ~100–200.
Cache line kya hoti hai (aur hamare figures mein "fence" ka kya matlab hai)? ::: Woh sabse chhota block jo cache kabhi bhi ek unit ki tarah move karta hai, $L = 64$ bytes; "fence" bas same block ke liye haari picture-nickname hai.
Address $A$ ka line number compute karo. ::: $⌊ A / L ⌋$ — 64 se divide karo aur neeche round karo.
$⌊ x ⌋$ kya karta hai, aur rounding ki jagah floor kyun? ::: Nearest whole number pe neeche round karta hai; floor exactly "kaun sa whole block?" ka jawab deta hai, kyunki upar rounding se edge bytes agle fence mein galat ja sakti hain.
Do variables ek cache line kab share karte hain, aur woh condition kya assume karti hai? ::: Jab $⌊ addr (v_{i}) / L ⌋ = ⌊ addr (v_{j}) / L ⌋$ ; yeh assume karta hai ki har variable poori tarah ek line ke andar fit hota hai (ek spanning variable do lines ke saath share kar sakta hai).
M, E, S, I letters ka kya matlab hai? ::: Modified, Exclusive, Shared, Invalid — MESI coherence protocol ki chaar cache-line states.
Cache coherence mein "invalidate" ka matlab kya hai? ::: Doosre cores ko majboor karna ki woh line ki apni ab-stale copy throw away kar dein, tumhare likhne se pehle.
Ek line ko ek baar mein kitne cores Modified state mein hold kar sakte hain? ::: Exactly ek.
Cycle kya hota hai, aur local write aur coherence miss ke beech rough cost gap kya hai? ::: Ek CPU clock tick; local ke liye ~1–2 cycles versus remote-modified line ke liye ~100–200, yeh ~50–100× ka gap hai.

Next: woh False sharing problem mechanism page, jahan yeh saare pieces ping-pong timeline mein animate hote hain. Related ground jo tum ab safely explore kar sakte ho: Cache line size and alignment, Cache coherence protocols, Atomic operations, aur Multicore scaling.