Exercises — False sharing problem

Har ek ka line index compute karo — yahi ek test hai jo matter karta hai. $\lfloor \frac{4096}{64}\rfloor =\lfloor 64\rfloor =64,\lfloor \frac{4100}{64}\rfloor =\lfloor 64.06\rfloor =64.$ Same line index $\Rightarrow$ haan, yeh false-share karte hain. Bytes alag hain, lekin transfer ki unit (poori line 64) identical hai, toh har write doosre core ke cache se line bahar kar deti hai.

$\lfloor \frac{4096}{64}\rfloor =64,\lfloor \frac{4160}{64}\rfloor =\lfloor 65\rfloor =65.$ Alag line indices ($64\ne 65$) $\Rightarrow$ koi false sharing nahi. Note karo $4160-4096=64=L$, toh doosra variable exactly ek line baad shuru hota hai — woh sabse chhota gap jo unhe poori tarah separate kar deta hai.

Pehli line addresses $4096$ se $4096+63=4159$ tak span karti hai (yeh woh 64 bytes hain jinki line index 64 hai). Har int 4 bytes occupy karta hai, toh kitne fit honge? $64/4=16$ ints ek line mein fit hote hain, lekin hamare paas sirf 8 hain, toh saare 8 counter[0..7] ek hi cache line share karte hain. Agar 8 alag cores apne-apne counter ko hammer karein, toh saatey 8 ek line par collide karte hain — worst case.

int = 4 bytes, toh element $k$ $8192+4k$ par baitta hai. Element $k$ ka line index: $\lfloor \frac{8192+4k}{64}\rfloor =128+\lfloor \frac{4k}{64}\rfloor =128+\lfloor \frac{k}{16}\rfloor .$ $k=0$ ke liye: $128+0=128$. $k=15$ ke liye: $128+\lfloor 15/16\rfloor =128+0=128$. Same line — yeh false-share karte hain. Actually saare indices $\mathrm{0..15}$ line 128 dete hain, toh is 16-int (64-byte) array ka har element ek hi line mein rehta hai. Koi bhi pair kabhi separate nahi hota — yeh array ek badi collision zone hai.

Slowdown factor: $\frac{T_{\text{false}}}{T_{\text{local}}}=\frac{150}{2}=75\times .$ $N=10^7$ increments ke liye: $\text{local: }2\times 10^7=2\times 10^7\text{ cycles},\text{false: }150\times 10^7=1.5\times 10^9\text{ cycles}.$ False-sharing version identical program output ke liye 75 guna zyada kaam karta hai.

Kyunki struct sirf 13 bytes ka hai (16 tak padded) aur ek line boundary par start hota hai, har field ka line index struct ke base line index ke equal hai. counter (offset 4), checksum (offset 8), done (offset 12) saare ek hi 64-byte line ke andar aate hain. Teeno cores ek line par false-share karte hain — ek three-way ping-pong, two-way se bhi zyada nasty kyunki har write do remote copies ko invalidate karta hai.

Har element ko apni line mein force karne ke liye, consecutive elements ke beech stride $\ge L=64$ hona chahiye. Toh padded struct size 64 ka multiple hona chahiye: $\text{padded\_size}=\lceil \frac{\text{sizeof(value)}}{L}\rceil \times L=\lceil \frac{4}{64}\rceil \times 64=1\times 64=64\text{ bytes}.$ Padding bytes chahiye: $64-4=60$. Memory actually used 64 mein se 4 bytes hai, toh useful fraction $4/64=6.25\%$ hai; waste ratio $60/64=93.75\%$ hai. Dekho Memory allocators jisme allocators cache-aligned blocks return kar sakte hain.

Element $i$ ka value $B+64i$ par rehta hai. Uska line index hai $\lfloor \frac{B+64i}{64}\rfloor =\frac{B}{64}+i$ (division exact hai kyunki $B$ 64 ka multiple hai, aur $64i/64=i$). Toh element $i$ ka line index $\frac{B}{64}+i$ hai. $i\ne j$ ke liye: $\frac{B}{64}+i\ne \frac{B}{64}+j,$ toh line indices alag hain — koi shared line nahi, koi false sharing nahi. Padding ne "same line" ko "line index har element ke saath exactly 1 badhta hai" mein badal diya.

sizeof(Bad) = 32 + 4 = 36 bytes (assume karo extra alignment padding nahi hai). Element $i$ $B+36i$ par shuru hota hai; uska value $B+36i+32$ par hai.

• Element 0 value: offset $32$, line index $\lfloor 32/64\rfloor =0$ (base line ke relative).
• Element 1 value: offset $36+32=68$, line index $\lfloor 68/64\rfloor =1$.

Yahan elements 0 aur 1 ittefaqan alag lines mein land karte hain (0 vs 1) — lekin yeh offsets ki kismat hai, guarantee nahi. Element 1 value (offset 68) aur element 2 value (offset $72+32=104$, line $\lfloor 104/64\rfloor =1$) dono line index 1 dete hain → woh collide karte hain! Half-padding fragile hai: sahi fix L3.2 ki tarah full-line stride of 64 hai.

std::hardware_destructive_interference_size (standard ka naam "$L$ jo hot data separate karta hai") use karo alignas ke saath:

#include <new>
struct alignas(std::hardware_destructive_interference_size) Cell {
    double value;
};
Cell arr[4];   // each Cell begins on its own line

Mechanism: alignas(k) har Cell ko ek aise address par start hone ke liye force karta hai jo $k$ ka multiple ho, aur sizeof(Cell) bhi $k$ ke multiple tak round up hoti hai — toh stride $k$ ban jaati hai. $k=L$ choose karna distinct line indices guarantee karta hai (L3.2 proof). Kyun adapt karta hai: constant compiler dwara target architecture ke liye provide kiya jaata hai, toh 128-byte lines wale CPU par yeh automatically 128 ban jaata hai — koi hard-coded 64 nahi jo break ho.

Atomic operations se Atomics guarantee karte hain ki har increment indivisible hai (koi torn read/write nahi), lekin ek atomic RMW ko phir bhi line Modified state mein chahiye, toh coherence invalidations phir bhi trigger hote hain. Saate 8 bins ek line mein hone se, har core ka atomic increment line bounce karata hai — parent note ka ping-pong, bilkul unchanged. Do-part fix:

1. Rakho std::atomic<long> correctness ke liye (safe concurrent updates).
2. Add karo padding/alignment taaki har bin ko apni line mile:

struct alignas(64) Bin { std::atomic<long> v; };
Bin bin[8];

Ab correctness aur performance dono handle hain. Dekho Lock-free data structures jinmein structures yeh padding default assume karti hain.

Padded cost: $64\text{ cores}\times 64\text{ bytes}=4096$ bytes = 4 KiB, versus $64\times 4=256$ bytes unpadded — ek $16\times$ blow-up, lekin absolute terms mein tiny. Kab pad na karo: False sharing sirf writes par bura lagta hai jinhe exclusive ownership chahiye. Agar counters almost hamesha read hote hain (Shared state kaafi saare caches mein simultaneously hold ho sakti hai — reads invalidate nahi karte), toh coherence traffic negligible hai aur padding sirf space aur cache capacity waste karti hai. NUMA connection: NUMA machine par ek aur bada cost yeh hai ki core ka counter remote memory mein rakha ho. Line boundary tak padding zaroori hai lekin kaafi nahi — tum chahte ho ki har core ki line uske local NUMA node mein allocate ho taaki reads/writes on-socket rahein. Dekho NUMA architectures aur Multicore scaling.

Saare cores mein total increments: $N\times I=8\times 5\times 10^6=4\times 10^7$. Cores parallel chalte hain, toh wall-clock time per-core kaam se set hoti hai (har core $I$ increments karta hai) — lekin full false sharing ke under ping-pong writes ko serialize karta hai, toh hum aggregate cycles ko bottleneck resource maan ke chalte hain.

(b) Unpadded (serialized ping-pong): total cycles = $N\cdot I\cdot t_{\text{far}}=4\times 10^7\times 160=6.4\times 10^9$ cycles. $T_{\text{unpad}}=\frac{6.4\times 10^9}{3.2\times 10^9}=2.0\text{ seconds}.$

(a) Padded (fully parallel, har core local): har core independently $I\cdot t_{\text{loc}}=5\times 10^6\times 2=1\times 10^7$ cycles karta hai, aur saate 8 ek saath chalte hain, toh wall-clock cycles = $1\times 10^7$. $T_{\text{pad}}=\frac{1\times 10^7}{3.2\times 10^9}=3.125\times 10^{-3}\text{ s}=3.125\text{ ms}.$

Speed-up: $\frac{T_{\text{unpad}}}{T_{\text{pad}}}=\frac{2.0}{3.125\times 10^{-3}}=640\times .$ Padding ne 2-second ka kaam 3 milliseconds mein kar diya.

$I=5\times 10^6$, $t_{\text{far}}=160$, $f=3.2\times 10^9$ ke saath: $T(N)=N\cdot 5\times 10^6\cdot 160/3.2\times 10^9=N\times 0.25$ s.

• $N=1$: $0.25$ s
• $N=2$: $0.50$ s
• $N=4$: $1.00$ s
• $N=8$: $2.00$ s

Time core count ke saath linearly badhti hai — negative scaling. Ideal parallel time flat rehti hai $T_{\text{ideal}}=5\times 10^6\cdot 2/3.2\times 10^9=3.125\times 10^{-3}$ s par, $N$ se independent. Yeh Multicore scaling failure ka sabse sharp illustration hai: false sharing extra cores ko benefit se coherence-traffic tax mein badal deta hai. Fix (padding) flat ideal curve restore kar deta hai.

Unpadded: $M/s=2048/4=512$ counters fit hote hain. Full line tak padded: $M/L=2048/64=32$ counters fit hote hain. 8 cores ke liye tumhe 8 padded counters chahiye = $8\times 64=512$ bytes $\le 2048$ — haan, padding aasaani se fit hoti hai (budget ka ek chauthai use karta hai). Apparent $16\times$ waste per element yahan irrelevant hai kyunki 8, 32-counter ceiling se kaafi neeche hai.

Do addresses ke liye line index test hai ::: $\lfloor A/L\rfloor$ equal $\Rightarrow$ woh false-share karte hain. Elements isolate karne ke liye minimum stride hai ::: exactly $L$ (64 bytes), ek full line. Atomics fix karte hain ::: correctness (races), false-sharing performance nahi. Ek int ko ek line tak pad karna waste karta hai ::: $60/64=93.75\%$ us block ka. False sharing scaling ko ::: negative banata hai — time core count ke saath badhta hai.