Cache-বান্ধব প্রোগ্রাম — loop-এর ক্রম, blocking আর false sharing

১ · প্রোগ্রামারের চোখে cache — line, locality আর row-major ঠিকানা

পর্ব ৪৪ থেকে ৪৭-এ আপনি cache-কে hardware-এর দিক থেকে দেখেছেন: কেন একটি ছোট দ্রুত মেমরি এত কাজ করে (পর্ব ৪৪), ঠিকানা কীভাবে tag, index আর block offset-এ ভাগ হয় (পর্ব ৪৫), set-associative cache আর LRU (পর্ব ৪৬), আর AMAT ও multi-level cache-এর হিসাব (পর্ব ৪৭). এই পর্বে প্রশ্নটা উল্টো দিক থেকে: hardware যেমন আছে তেমনই রেখে, আমি কোড কীভাবে লিখলে কম miss হবে?

প্রোগ্রামারের জন্য পুরো cache-তত্ত্ব তিনটি কথায় নামিয়ে আনা যায়। প্রথম, মেমরি আর cache-এর মধ্যে আনা-নেওয়ার একক একটি cache line — আজকের প্রায় সব x86-64 আর ARM chip-এ ৬৪ byte. একটি double পড়তে চাইলেও পুরো ৬৪ byte আসে, অর্থাৎ পাশের আরও ৭টি double. দ্বিতীয়, spatial locality: একটি byte ছুঁলে তার পাশেরগুলোও শিগগির ছোঁয়া হবে — তাহলে আনা line-এর পুরোটা কাজে লাগে। তৃতীয়, temporal locality: একটি ডেটা আবার ব্যবহার হবে শিগগিরই — তাহলে সেটি তখনো cache-এ থাকে।

Miss-এর তিন ধরন (পর্ব ৪৫–৪৬) প্রোগ্রামারের ভাষায়: compulsory miss — প্রথমবার ছোঁয়ার miss, এড়ানো যায় না, তবে প্রতিটি line-এর সব byte ব্যবহার করে সংখ্যায় কমানো যায়; capacity miss — যে ডেটা একসাথে লাগছে (working set) তা cache-এর চেয়ে বড়; সমাধান working set ছোট করা, যেমন blocking; conflict miss — জায়গা আছে, কিন্তু কয়েকটি line একই set-এ পড়ছে; সমাধান প্রায়ই array-র মাপ ২-এর ঘাত থেকে একটু সরানো। (চতুর্থ ধরন coherence miss আসবে পর্ব ৫৩-এ; এই পর্বের false sharing তারই একটি রূপ।)

Row-major বিন্যাস — a[i][j] মেমরির কোথায়

C-তে double a[R][M] মেমরিতে একটি লম্বা সারি: প্রথমে row 0-র M-টি উপাদান, তারপর row 1-এর, এভাবে। একে বলে row-major ক্রম। Fortran, MATLAB আর Julia উল্টো — column-major: একটি column-এর উপাদান পাশাপাশি। NumPy দুটোই পারে (ডিফল্ট row-major). তাই “কোন loop ভেতরে রাখব” প্রশ্নের উত্তর ভাষাভেদে উল্টে যায়।

উদাহরণ। double a[100][300], base = 0x1000. তাহলে a[2][5]-এর ঠিকানা = 0x1000 + (২ × ৩০০ + ৫) × ৮ = 0x1000 + ৪৮৪০ = 0x1000 + 0x12E8 = 0x22E8. 0x22E8 মানে দশমিকে ৮৯৩৬; line নম্বর = ৮৯৩৬ ÷ ৬৪ → ১৩৯ (ভাগশেষ ৪০), অর্থাৎ line ১৩৯-এর ৪০ নম্বর byte থেকে শুরু। পাশের a[2][6] একই line-এ (offset ৪৮), কিন্তু a[3][5] ঠিক ২৪০০ byte দূরে — ৩৭টিরও বেশি line পরে।

২ · সারি ধরে না কলাম ধরে — loop interchange আর miss গোনা

সবচেয়ে সরল cache-বান্ধব কৌশল loop interchange: nested loop-এর ক্রম অদলবদল, যাতে ভেতরের loop মেমরিতে পাশাপাশি উপাদান ধরে হাঁটে। দুটি loop দেখুন, দুটিই একই যোগফল দেয়:

for (i = 0; i < N; i++) for (j = 0; j < N; j++) s += a[i][j];   /* ij: সারি ধরে  */
for (j = 0; j < N; j++) for (i = 0; i < N; i++) s += a[i][j];   /* ji: কলাম ধরে */

হিসাব। ধরুন এক line-এ B-টি উপাদান (৬৪-byte line-এ double হলে B = ৮, int হলে ১৬)। ij ক্রমে প্রতিটি line-এর প্রথম উপাদানে একটি compulsory miss, পরের B − ১টি hit: প্রতি উপাদানে ১/B miss — double-এ ০.১২৫. ji ক্রমে পরপর দুটি access M·S byte দূরে, তাই প্রতিটি access নতুন line ছোঁয়। একটি column শেষ করতে N-টি আলাদা line লাগে। পরের column-এর উপাদান ওই একই N-টি line-এ আছে — যদি cache সেগুলো ধরে রাখতে পারে, তাহলে ji-ও ১/B-তে নামে; না পারলে প্রতিটি access miss: প্রতি উপাদানে ১.

নিচের stepper-এ একটি খুদে উদাহরণ: int a[4][8], line ১৬ byte (৪টি int), তাই প্রতিটি row দুটি line-এ — মোট ৮টি line L0–L7. Cache fully associative, LRU (পর্ব ৪৬)। ছকে M = miss, H = hit, . = এখনো ছোঁয়া হয়নি।

বাস্তব cache-এ: ২-এর ঘাতের ফাঁদ

বাস্তব L1 fully associative নয়। এই পর্বের C কোড যে runner-এ চলে, সেখানে /sys/devices/system/cpu/cpu0/cache বলে L1 data cache ৩২ KiB, ৮-way, line ৬৪ byte — অর্থাৎ ৬৪টি set. ৩২ KiB = ৫১২টি line, তাই মনে হতে পারে ২৫৬ row-এর একটি double array-র column (২৫৬টি line) আরামে ধরবে। কিন্তু row-এর মাপ ২৫৬ × ৮ = ২০৪৮ byte = ৩২টি line, তাই column-এর পরপর line-এর set index লাফায় ৩২ করে — ৬৪টি set-এর মধ্যে মাত্র ২টি set-এ সব line জড়ো হয়, জায়গা মোট ১৬টি line. একটি set-associative LRU simulator-এ প্রথম ৬৪টি column হাঁটালে ফল:

এজন্য বড় সংখ্যাতাত্ত্বিক কোডে অনেক সময় array-র row একটু লম্বা করে বরাদ্দ করা হয় (leading dimension-এ padding). তবে সবচেয়ে নিশ্চিত সমাধান loop interchange — তাহলে column ধরে হাঁটাই লাগে না। এবার আসল যন্ত্রে মেপে দেখা যাক:

// Row-wise vs column-wise sum of the same 2D array (times vary per run and machine)
#include <stdio.h>
#include <time.h>
#define N 2048
static int a[N][N];                          // 2048 x 2048 int = 16 MiB, row-major

static double now_ms(void) {
    struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec * 1e3 + t.tv_nsec / 1e6;
}
static long sum(int by_row) {
    long s = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            s += by_row ? a[i][j] : a[j][i];   // a[j][i]: next access is 8 KiB away
    return s;
}
int main(void) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) a[i][j] = (i + j) % 10;
    double best[2] = {1e9, 1e9};
    long s[2] = {0, 0};
    for (int rep = 0; rep < 3; rep++)        // repeat, keep the fastest run
        for (int k = 0; k < 2; k++) {
            double t0 = now_ms();
            s[k] = sum(k == 0);
            double t = now_ms() - t0;
            if (t < best[k]) best[k] = t;
        }
    printf("sums: row %ld, column %ld\n", s[0], s[1]);
    printf("row-wise   : %7.1f ms\n", best[0]);
    printf("column-wise: %7.1f ms\n", best[1]);
    printf("column / row = %.1f\n", best[1] / best[0]);
    return 0;
}

sums: row 18874378, column 18874378
row-wise   :    11.2 ms
column-wise:    35.6 ms
column / row = 3.2

৩ · Matrix গুণের ছয় loop-ক্রম — ভেতরের loop-এ কয়টি miss

C = A × B, তিনটিই N × N double, row-major. মূল অঙ্ক C[i][j] += A[i][k] * B[k][j], আর তিনটি loop (i, j, k) যেকোনো ক্রমে সাজানো যায় — ৩! = ৬টি ক্রম, সবগুলো একই ফল দেয় (পূর্ণসংখ্যা-মানের ডেটায় হুবহু; ভগ্নাংশে যোগের ক্রম বদলালে শেষ bit-এ সামান্য পার্থক্য হতে পারে, পর্ব ২৪)। প্রশ্ন: কোনটি cache-বান্ধব?

বিশ্লেষণের কৌশল। ধরে নিন N বড় — এতটাই যে cache একটি column-এর সব line ধরে রাখতে পারে না, এমনকি একটি পুরো row-ও এক loop-চক্র থেকে পরের চক্র পর্যন্ত টেকে না (এটিই পাঠ্যবইয়ের প্রচলিত অনুমান, যেমন Bryant ও O'Hallaron-এর CS:APP বইয়ে)। তখন শুধু ভেতরের loop-এর চলক দেখলেই চলে। একটি array-র সূচকে ভেতরের চলক যদি:

• দ্বিতীয় (ডানের) সূচক হয় → সারি ধরে হাঁটা, stride ১ → প্রতি iteration-এ ১/B miss (double-এ ০.১২৫);
• প্রথম (বাঁয়ের) সূচক হয় → column ধরে হাঁটা, stride N → প্রতি iteration-এ ১ miss;
• কোনো সূচকেই না থাকে → ভেতরের loop জুড়ে একই উপাদান, register-এ রাখা যায় → ০ miss.

এখন ছয়টি ক্রমকে ভেতরের চলক অনুযায়ী তিন জোড়ায় ভাগ করুন। ভেতরে k (ijk, jik): A[i][k] সারি ধরে (০.১২৫), B[k][j] column ধরে (১), C[i][j] স্থির (০) — মোট ১.১২৫. ভেতরে i (jki, kji): A[i][k] column ধরে (১), B[k][j] স্থির, C[i][j] column ধরে (১) — মোট ২. ভেতরে j (kij, ikj): A[i][k] স্থির, B[k][j] আর C[i][j] দুটিই সারি ধরে — মোট ০.২৫.

লক্ষ করুন, সবচেয়ে কম miss-এর ক্রম (ikj) প্রতি iteration-এ একটি store বেশি করে, তবু সাধারণত জেতে — কারণ miss-এর দাম কয়েক দশ থেকে কয়েকশো cycle, আর একটি hit-করা store প্রায় বিনামূল্যে। এখন অনুমানগুলো সত্যি কি না, তা একটি simulator দিয়ে মিলিয়ে দেখা যাক। নিচের মডেল প্রতিটি access-কে একটি fully associative LRU cache-এ চালায়, আর প্রতিটি matrix-এর miss আলাদা গোনে। দুটি মাপ: ৪ line (একটি row-ও ধরে না — পাঠ্যবইয়ের অনুমান) আর ৩২ line (৪টি row ধরে)।

// Cache-miss model for C = A x B (double, 64 x 64, row-major), fully associative LRU cache
const N = 64, LINE = 64, PER = LINE / 8;          // 64 B line = 8 doubles; one row = 8 lines
function run(order, LINES, T) {
  const lru = new Map(), miss = { A: 0, B: 0, C: 0 };
  const touch = (m, base, r, c) => {              // each matrix starts on its own line
    const line = base + Math.floor((r * N + c) / PER);
    if (lru.has(line)) lru.delete(line);
    else { miss[m]++; if (lru.size === LINES) lru.delete(lru.keys().next().value); }
    lru.set(line, 1);                             // Map order = least to most recently used
  };
  const body = (i, j, k) => { touch("A", 0, i, k); touch("B", 1e6, k, j); touch("C", 2e6, i, j); };
  if (T) {                                        // blocked: T x T tiles, ikj inside a tile
    for (let ii = 0; ii < N; ii += T) for (let jj = 0; jj < N; jj += T)
      for (let kk = 0; kk < N; kk += T) for (let i = ii; i < ii + T; i++)
        for (let k = kk; k < kk + T; k++) for (let j = jj; j < jj + T; j++) body(i, j, k);
  } else {
    const v = [0, 0, 0], p = [..."ijk"].map((c) => order.indexOf(c));  // where i, j, k sit
    for (v[0] = 0; v[0] < N; v[0]++) for (v[1] = 0; v[1] < N; v[1]++)     // outer, middle
      for (v[2] = 0; v[2] < N; v[2]++) body(v[p[0]], v[p[1]], v[p[2]]);   // inner loop
  }
  const f = (n) => (n / N ** 3).toFixed(3);
  return `  ${(T ? "tiled T=" + T : order).padEnd(10)} A ${f(miss.A)}  B ${f(miss.B)}` +
         `  C ${f(miss.C)}  total ${f(miss.A + miss.B + miss.C)}`;
}
for (const L of [4, 32]) {
  console.log(`cache = ${L} lines (${L * LINE} B): misses per inner iteration`);
  for (const o of ["ijk", "jik", "jki", "kji", "kij", "ikj"]) console.log(run(o, L, 0));
}
console.log("cache = 32 lines, tiled (tile ii, jj, kk; then i, k, j):");
for (const T of [8, 16]) console.log(run("", 32, T));

cache = 4 lines (256 B): misses per inner iteration
  ijk        A 0.125  B 1.000  C 0.002  total 1.127
  jik        A 0.125  B 1.000  C 0.016  total 1.141
  jki        A 1.000  B 0.016  C 1.000  total 2.016
  kji        A 1.000  B 0.002  C 1.000  total 2.002
  kij        A 0.016  B 0.125  C 0.125  total 0.266
  ikj        A 0.002  B 0.125  C 0.125  total 0.252
cache = 32 lines (2048 B): misses per inner iteration
  ijk        A 0.125  B 1.000  C 0.002  total 1.127
  jik        A 0.125  B 1.000  C 0.016  total 1.141
  jki        A 1.000  B 0.016  C 1.000  total 2.016
  kji        A 1.000  B 0.002  C 1.000  total 2.002
  kij        A 0.016  B 0.002  C 0.125  total 0.143
  ikj        A 0.002  B 0.125  C 0.002  total 0.129
cache = 32 lines, tiled (tile ii, jj, kk; then i, k, j):
  tiled T=8  A 0.016  B 0.016  C 0.002  total 0.033
  tiled T=16 A 0.008  B 0.125  C 0.008  total 0.141

৪ · Blocking বা tiling — working set-কে cache-এর মাপে কাটা

ikj ক্রমেও একটি সমস্যা থেকে যায়। C-এর প্রতিটি row বানাতে পুরো B matrix একবার পড়তে হয়, আর N বড় হলে B (N² × ৮ byte) cache-এ ধরে না — তাই B প্রতিবার মেমরি থেকে নতুন করে আসে, মোট N বার। Temporal locality আছে (B-এর প্রতিটি উপাদান N বার লাগে), কিন্তু পুনর্ব্যবহারের মাঝে এত বেশি ডেটা ছোঁয়া হয় যে সেটি ততক্ষণে cache থেকে সরে গেছে।

Loop tiling (blocking) এর সমাধান: matrix-গুলোকে T × T মাপের ছোট টুকরোয় (tile) ভাগ করে কাজের ক্রম এমনভাবে সাজানো, যাতে একসাথে শুধু কয়েকটি tile লাগে — আর সেগুলো cache-এ ধরে। গণিত বদলায় না: block matrix গুণের নিয়মে C_IJ = Σ_K A_IK · B_KJ, যেখানে প্রতিটি পদ নিজেই একটি ছোট matrix গুণ।

নিচের stepper-এ ৪ × ৪ matrix, T = ২. Tile-এর loop ক্রম ii → jj → kk, আর প্রতিটি tile-এর ভেতরে ikj — অর্থাৎ একটি C-tile পুরো শেষ করে তবে পরেরটিতে যাওয়া।

Simulator-এর সাথে মেলানো যাক। ওপরের মডেলে cache ৩২ line = ২০৪৮ byte = ২৫৬টি double. ৩T² ≤ ২৫৬ ⇒ T ≤ ৯.২, আর ৬৪-কে ভাগ করে এমন T = ৮. সূত্র: ২ ÷ (৮ × ৮) + ১ ÷ (৮ × ৬৪) = ০.০৩১২৫ + ০.০০১৯৫ ≈ ০.০৩৩ — মডেলের “tiled T=8” সারি হুবহু তাই বলছে (A ০.০১৬, B ০.০১৬, C ০.০০২)। এটি ikj-এর ০.১২৯-এর প্রায় চার ভাগের এক ভাগ। আর T = ১৬ নিলে ৩ × ২৫৬ = ৭৬৮টি double লাগে, যা ২৫৬-এর তিন গুণ: tile আর cache-এ ধরে না, B-এর miss ফিরে যায় ০.১২৫-এ, মোট ০.১৪১ — tile বেশি বড় হলে লাভ পুরো উধাও।

আসল cache থেকে tile-এর মাপ — একটি পূর্ণ উদাহরণ

Runner-এর L1 data cache ৩২ KiB = ৩২৭৬৮ byte, double ৮ byte. শর্ত ৩T² × ৮ ≤ ৩২৭৬৮ ⇒ T² ≤ ১৩৬৫.৩ ⇒ T ≤ ৩৬.৯. N = ৫১২-কে ভাগ করে এমন সবচেয়ে বড় ২-এর ঘাত T = ৩২: তিনটি tile = ৩ × ৩২ × ৩২ × ৮ = ২৪৫৭৬ byte = ২৪ KiB, cache-এর তিন-চতুর্থাংশ। পুরো ৩২ KiB না ভরানোর কারণ: cache-এ অন্য ডেটাও থাকে, আর ২-এর ঘাতের stride-এ কিছু conflict miss হয়ই। সূত্রমতে প্রতি iteration-এ miss ≈ ২ ÷ (৮ × ৩২) ≈ ০.০০৭৮ — ikj-এর ০.২৫-এর ৩২ ভাগের এক ভাগ। বাস্তবে সেরা T খুঁজতে কয়েকটি মান (১৬, ৩২, ৪৮, ৬৪) মেপে দেখা হয়; সূত্র শুধু শুরু করার জায়গা দেয়।

// Naive (ijk) vs blocked matrix multiply: same result, different cache behaviour (times vary)
#pragma GCC optimize("O2")               // compile this file at -O2 so memory, not overhead, dominates
#include <stdio.h>
#include <string.h>
#include <time.h>
#define N 512
#define T 32                             // tile: 3 tiles x 32 x 32 x 8 B = 24 KiB < 32 KiB L1d
static double A[N][N], B[N][N], C1[N][N], C2[N][N];
static double now_ms(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t);
                             return t.tv_sec * 1e3 + t.tv_nsec / 1e6; }
int main(void) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) { A[i][j] = (i + j) % 7; B[i][j] = (i * j) % 5; }
    double t0 = now_ms();
    for (int i = 0; i < N; i++)          // naive ijk: inner loop walks DOWN a column of B
        for (int j = 0; j < N; j++) {
            double s = 0;
            for (int k = 0; k < N; k++) s += A[i][k] * B[k][j];
            C1[i][j] = s;
        }
    double t1 = now_ms();
    for (int ii = 0; ii < N; ii += T)     // blocked: finish a T x T tile of C before moving on
        for (int jj = 0; jj < N; jj += T)
            for (int kk = 0; kk < N; kk += T)
                for (int i = ii; i < ii + T; i++)
                    for (int k = kk; k < kk + T; k++) {
                        double aik = A[i][k];
                        for (int j = jj; j < jj + T; j++) C2[i][j] += aik * B[k][j];
                    }
    double t2 = now_ms();
    printf("identical results: %s\n", memcmp(C1, C2, sizeof C1) == 0 ? "yes" : "NO");
    printf("naive ijk : %6.0f ms\nblocked   : %6.0f ms\n", t1 - t0, t2 - t1);
    printf("naive / blocked = %.1f\n", (t1 - t0) / (t2 - t1));
    return 0;
}

identical results: yes
naive ijk :    279 ms
blocked   :     69 ms
naive / blocked = 4.1

Transpose — যেখানে loop interchange কাজ করে না

Matrix transpose dst[j][i] = src[i][j]-এ একটি বিপদ আছে: loop যেভাবেই সাজান, একটি array সারি ধরে আর অন্যটি column ধরে হাঁটবে। ij ক্রমে src-এর miss ১/B, কিন্তু dst column ধরে — প্রতি উপাদানে ১; ji করলে উল্টো। মোট প্রায় ১ + ১/B, interchange কিছুই বদলায় না। সমাধান আবার tiling: একটি T × T tile-এর ভেতরে src-এর T-টি row আর dst-এর T-টি row একসাথে cache-এ থাকে, তাই dst-এর প্রতিটি line-এর B-টি উপাদানই ব্যবহার হয় তার আগে, যতক্ষণ না line সরে যায়।

উদাহরণ (চালানো যায় না, শুধু কাঠামো):

for (int ii = 0; ii < N; ii += T)
    for (int jj = 0; jj < N; jj += T)
        for (int i = ii; i < ii + T; i++)          /* src: T row, সারি ধরে       */
            for (int j = jj; j < jj + T; j++)      /* dst: T row, প্রতিটির B ঘর  */
                dst[j][i] = src[i][j];

একই fully associative LRU মডেলে (N = ৬৪ double, cache ৩২ line) গুনে পাওয়া গেছে: naive transpose-এ প্রতি উপাদানে src ০.১২৫ আর dst ১.০ miss; T = ৮-এর tiled transpose-এ দুটিই ০.১২৫ — মোট ১.১২৫ থেকে ০.২৫, সাড়ে চার গুণ কম।

৫ · ডেটার বিন্যাস — AoS বনাম SoA, padding, alignment আর pointer chasing

Loop-এর ক্রম ঠিক করে দেয় কোন ক্রমে ঠিকানা ছোঁয়া হবে; ডেটার বিন্যাস ঠিক করে দেয় এক line-এ কী কী থাকবে. দ্বিতীয়টি প্রায়ই বেশি জরুরি, আর পরে বদলানো কঠিন — তাই নকশার শুরুতেই ভাবার মতো।

AoS বনাম SoA আর hot/cold ভাগ

একটি সিমুলেশনে ১০ লাখ কণা (particle):

struct particle { double x, y, z, vx, vy, vz; int id; char name[20]; };   /* sizeof = 72 */
struct particle p[1000000];                       /* AoS: array of structs  */
for (i = 0; i < n; i++) p[i].x += p[i].vx * dt;   /* লাগে শুধু x আর vx      */

x86-64-এর সাধারণ ABI-তে struct-টির মাপ ৭২ byte (৬টি double = ৪৮, int ৪, name ২০, মোট ৭২; ৮-এর গুণিতক বলে শেষে padding লাগে না)। Loop প্রতি কণায় লাগে মাত্র ১৬ byte (x আর vx), কিন্তু line আসে পুরো ৭২ byte-এর এলাকা ঢেকে — ১০ লাখ × ৭২ ÷ ৬৪ = ১১ লাখ ২৫ হাজার line. আনা byte-এর মাত্র ১৬ ÷ ৭২ ≈ ২২% কাজে লাগে। এই বিন্যাসের নাম array of structs (AoS).

Struct of arrays (SoA)-এ প্রতিটি field নিজের array-তে: double x[N], vx[N], …; তখন loop ছোঁয় শুধু x আর vx — ২ × ৮ × ১০ লাখ ÷ ৬৪ = আড়াই লাখ line, AoS-এর ৪.৫ ভাগের এক ভাগ। বাড়তি লাভ: পাশাপাশি x-গুলো SIMD register-এ একসাথে তোলা যায় (পর্ব ৪২)। মাঝামাঝি পথ hot/cold splitting: যে field প্রতিটি loop-এ লাগে (hot — অবস্থান, বেগ) সেগুলো এক struct-এ, আর কালেভদ্রে লাগা field (cold — নাম, id, debug তথ্য) আলাদা array-তে, একই index দিয়ে।

Padding, field-এর ক্রম আর cache-line alignment

প্রতিটি field তার alignment-এর গুণিতক ঠিকানায় বসে (পর্ব ০৬), তাই compiler ফাঁকে padding বসায়। struct { char c; double d; int i; }-এর মাপ ২৪ byte (c-এর পরে ৭ byte ফাঁকা, শেষে ৪ byte); বড় থেকে ছোট ক্রমে { double d; int i; char c; } লিখলে ১৬ byte. এক line-এ প্রথমটির ২.৬৭টি, দ্বিতীয়টির ঠিক ৪টি — array-তে ৩৩% কম line. C কোর্সের পারফরম্যান্স আর cache পর্বে padding গোনার একটি চালানো যায় এমন উদাহরণ আছে।

উল্টো দিকে, কখনো ইচ্ছা করে ফাঁকা রাখা হয়। ৬৪ byte বা তার ছোট একটি গুরুত্বপূর্ণ object যদি দুটি line-এর সীমানায় পড়ে, একবার ছুঁতে দুটি miss. C11-এর alignas(64) (C23-এ সরাসরি keyword; C11-এ <stdalign.h>) একটি ভ্যারিয়েবল বা struct-কে ৬৪-এর গুণিতক ঠিকানায় বসায়; heap-এ একই কাজ করে aligned_alloc(64, size), যেখানে size-কেও ৬৪-এর গুণিতক রাখাই নিরাপদ। এর সবচেয়ে বড় ব্যবহার অংশ ৬-এর false sharing.

Linked list বনাম array — pointer chasing

Array-তে পরের উপাদানের ঠিকানা আগেই জানা (base + i·S), তাই out-of-order core (পর্ব ৪০) একসাথে কয়েকটি miss চালু রাখতে পারে, আর prefetcher পরের line আগেভাগে আনে। Linked list-এ পরের node-এর ঠিকানা থাকে এই node-এর ভেতরে: p = p->next. আগের load শেষ না হলে পরের load-এর ঠিকানাই জানা নেই — একে বলে pointer chasing. প্রতিটি miss তখন একা, পরপর অপেক্ষা করে; node-গুলো heap-এ ছড়ানো থাকলে প্রায় প্রতিটি ধাপ একটি পূর্ণ মেমরি latency. Big-O-তে list-এ মাঝখানে ঢোকানো O(1), কিন্তু বাস্তবে প্রায়ই vector জেতে — DSA কোর্সের Linked list পর্বে এই তুলনা আর Array পর্বে row-major বিন্যাস আছে। প্রতিকার: node-গুলো একটি pool বা array থেকে পরপর বরাদ্দ করা, প্রতিটি node-এ কয়েকটি উপাদান রাখা (unrolled list), বা tree-র বদলে B-tree-র মতো চওড়া node — যেখানে একটি node কয়েকটি line জুড়ে অনেক key রাখে।

Prefetch-বান্ধব access আর software prefetch

আধুনিক CPU-তে hardware prefetcher থাকে: পরপর line বা সমান stride-এর access দেখলে সে নিজে থেকেই পরের line-গুলো আনতে শুরু করে। তাই সবচেয়ে prefetch-বান্ধব কোড হলো সরল ক্রমিক বা সমান-stride access. সাধারণভাবে বলা হয়, অনেক prefetcher একটি 4 KiB page-এর সীমা পেরোয় না, তাই খুব বড় stride-এ (প্রতি access-এ নতুন page) সাহায্য কম — নকশা chip-ভেদে আলাদা, আর নির্মাতারা সব বিস্তারিত প্রকাশ করেন না।

ঠিকানা যখন অনিয়মিত কিন্তু আগেভাগে জানা — যেমন sum += a[idx[i]], যেখানে idx আগে থেকেই আছে — তখন GCC আর Clang-এর software prefetch নির্দেশ কাজে লাগতে পারে:

উদাহরণ (চালানো যায় না):

for (i = 0; i < n; i++) {
    if (i + 16 < n) __builtin_prefetch(&a[idx[i + 16]], 0, 1);   /* ১৬ ধাপ আগে চাওয়া */
    sum += a[idx[i]];
}

__builtin_prefetch(ঠিকানা, rw, locality) — rw ০ মানে পড়ার জন্য, ১ মানে লেখার জন্য; locality ০ থেকে ৩, কতদিন cache-এ রাখার ইঙ্গিত। এটি একটি ইঙ্গিত, ভুল ঠিকানায় fault হয় না। কিন্তু লাভ নিশ্চিত নয়: ক্রমিক access-এ hardware আগেই কাজটি করছে, তাই বাড়তি instruction শুধু খরচ; দূরত্ব (এখানে ১৬) কম হলে ডেটা সময়মতো আসে না, বেশি হলে ব্যবহারের আগেই সরে যায়; আর বাড়তি prefetch bandwidth খায়। মেপে লাভ দেখলে তবেই রাখুন, আর অন্য যন্ত্রে আবার মাপুন।

Loop fusion আর fission

Loop fusion: একই array-র ওপর পরপর দুটি loop থাকলে একটিতে মেশানো — for i: b[i] = a[i] * 2; আর for i: c[i] = b[i] + 1; একসাথে করলে b[i] লেখার সাথে সাথে register বা L1 থেকেই পড়া হয়; বড় array-তে না মেশালে দ্বিতীয় loop-এর শুরুতে b-এর প্রথম অংশ cache থেকে সরে গেছে। Loop fission উল্টো: একটি loop যদি একসাথে দশটি array ছোঁয়, তাহলে প্রতি iteration-এ দশটি line জায়গা চায় — conflict আর capacity miss বাড়ে, vectorize করাও কঠিন হয়; দুই-তিনটি ছোট loop-এ ভাগ করলে প্রতিটির working set ছোট। শেষ কথা বলে মাপা।

৬ · Thread-এর সময় — false sharing বনাম true sharing

Multicore chip-এ প্রতিটি core-এর নিজের L1 (আর সাধারণত L2). একই ঠিকানার কপি কয়েকটি core-এর cache-এ থাকলে সবার ছবি এক রাখতে hardware একটি cache coherence protocol চালায় — কীভাবে, MESI-র অবস্থাসহ, তা পর্ব ৫৩-এর বিষয়। এখানে প্রোগ্রামারের জন্য একটি নিয়মই যথেষ্ট: একটি line-এ লিখতে হলে core-কে line-টির একমাত্র মালিক হতে হয়; অন্য সব core-এর কপি বাতিল হয়ে যায়। আর হিসাব হয় পুরো line ধরে, ভ্যারিয়েবল ধরে নয়।

এখান থেকেই false sharing: দুটি thread দুটি আলাদা ভ্যারিয়েবলে লেখে — যুক্তির দিক থেকে কোনো ভাগাভাগি নেই, lock-ও লাগে না — কিন্তু ভ্যারিয়েবল দুটি একই line-এ। ফলে line-টি দুই core-এর মধ্যে ping-pong খেলে।

এবার আসল দুটি thread দিয়ে মাপা যাক। প্রোগ্রামটি POSIX thread ব্যবহার করে; runner-এ -pthread flag ছাড়াই চলে (glibc-র নতুন version-এ pthread মূল library-র অংশ, পর্ব ৪৩-এও একই runner). volatile রাখা হয়েছে যাতে প্রতিটি ++ সত্যিই মেমরিতে লেখা হয় — না হলে -O2-তে compiler পুরো loop-কে একটি যোগে বদলে দিতে পারত।

// False sharing: two threads, two counters -- same cache line vs padded to 64 B (times vary)
#include <pthread.h>
#include <stdalign.h>
#include <stdio.h>
#include <time.h>
#define ITERS 100000000L

struct packed { volatile long a, b; };                  // a and b: 8 bytes apart, one line
struct padded { alignas(64) volatile long a; alignas(64) volatile long b; };  // own lines
static struct packed P;
static struct padded Q;

static void *bump(void *p) {                           // each thread touches only its own counter
    volatile long *c = p;
    for (long i = 0; i < ITERS; i++) (*c)++;
    return NULL;
}
static double run(volatile long *x, volatile long *y) {
    struct timespec t0, t1; pthread_t ta, tb;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    pthread_create(&ta, NULL, bump, (void *)x); pthread_create(&tb, NULL, bump, (void *)y);
    pthread_join(ta, NULL); pthread_join(tb, NULL);
    clock_gettime(CLOCK_MONOTONIC, &t1);
    return (t1.tv_sec - t0.tv_sec) * 1e3 + (t1.tv_nsec - t0.tv_nsec) / 1e6;
}
int main(void) {
    printf("distance a->b: packed %zu B, padded %zu B\n",
           (size_t)((char *)&P.b - (char *)&P.a), (size_t)((char *)&Q.b - (char *)&Q.a));
    double same = run(&P.a, &P.b), apart = run(&Q.a, &Q.b);
    printf("counts: %ld %ld %ld %ld\n", P.a, P.b, Q.a, Q.b);
    printf("same line  : %6.0f ms\n", same);
    printf("padded     : %6.0f ms\n", apart);
    printf("same / padded = %.2f\n", same / apart);
    return 0;
}

distance a->b: packed 8 B, padded 64 B
counts: 100000000 100000000 100000000 100000000
same line  :    423 ms
padded     :    210 ms
same / padded = 2.01

True sharing আর false sharing — কীভাবে চিনবেন, কীভাবে সারাবেন

False sharing-এর সাধারণ জায়গা: প্রতি thread-এর counter-এর array (long hits[NTHREADS]), একটি queue-র head আর tail একই struct-এ পাশাপাশি, আর একটি lock তার পাহারা দেওয়া ডেটার ঠিক পাশে। লক্ষণ: thread বাড়ালে গতি বাড়ে না, অথচ কোনো lock-এর প্রতিযোগিতা নেই। Linux-এর perf c2c টুল এমন line খুঁজে বের করতে বানানো। C++17-এ std::hardware_destructive_interference_size নামে একটি ধ্রুবক আছে, যা padding-এর দূরত্ব বলে; কিছু Intel chip-এ পাশের line-কে জোড়ায় আনা prefetcher থাকায় অনেক লাইব্রেরি ৬৪-এর বদলে ১২৮ byte padding দেয়।

৭ · ঠিকভাবে মাপা — আর কখন মাথা ঘামানোর দরকার নেই

Cache-কৌশলের প্রতিটি দাবি শেষ পর্যন্ত একটি মাপ। আর পারফরম্যান্স মাপা আশ্চর্য রকম সহজে ভুল হয়। এই পর্বের তিনটি C প্রোগ্রাম যে নিয়মগুলো মেনে লেখা, সেগুলো একসাথে:

1. সঠিক ঘড়ি। clock_gettime(CLOCK_MONOTONIC, …) — ন্যানোসেকেন্ডের ঘরে wall-clock time, আর সিস্টেমের সময় বদলালেও পেছনে যায় না। clock() মাপে প্রসেসের CPU time — একাধিক thread-এ সব thread-এর সময় যোগ হয়ে যায়।
2. কয়েকবার চালিয়ে সবচেয়ে কম সময়। শব্দ (অন্য প্রসেস, interrupt, ভাগ করা যন্ত্রে প্রতিবেশীর কাজ) সময় শুধু বাড়াতে পারে, কমাতে নয়। তাই কয়েকবারের সর্বনিম্নটি কোডের আসল খরচের সবচেয়ে কাছের অনুমান।
3. প্রথম ছোঁয়া আলাদা রাখা। একটি বড় array প্রথমবার লিখলে OS প্রতিটি page-এর জন্য একটি page fault সামলায় (পর্ব ৩৮, ৫০)। মাপার আগে array ভরে নিন — ওপরের প্রোগ্রামগুলোতে input array timing-এর আগেই ভরা হয়েছে।
4. ফল ব্যবহার করা। -O2-তে compiler যদি দেখে loop-এর ফল কোথাও লাগে না, পুরো loop মুছে দিতে পারে (dead-code elimination) — সময় আসে প্রায় শূন্য, আর মনে হয় “বিশাল উন্নতি”. তাই ফল print করুন, তুলনা করুন, বা একটি volatile ভ্যারিয়েবলে রাখুন।
5. -O0 দিয়ে বিচার নয়। Optimization level -O0-তে loop-এর নিজের খরচ বিশাল; অংশ ৪-এ একই blocked কোডের লাভ -O0-তে ১.৩ গুণ, -O2-তে ৩.৫ থেকে ৪.৪ গুণ। যে কোড আসলে -O2-তে চলবে, তাকে -O2-তেই মাপুন।
6. সঠিক মাপের ডেটা। সব ডেটা L1-এ ধরলে কোনো loop-ক্রমেই পার্থক্য দেখবেন না। Runner-এর L2 ৫১২ KiB আর L3 ১৬ MiB — মেমরির প্রভাব দেখতে ডেটা এর চেয়ে বড় করুন, আর বলুন কোন মাপে মাপলেন।

Hardware counter — perf stat

সময় বলে “কতটা ধীর”, কিন্তু “কেন” বলে না। CPU-র performance counter সরাসরি cache miss গোনে, আর Linux-এর perf টুল সেগুলো পড়ে। এই runner-এ perf নেই (container-এ সাধারণত counter পড়ার অনুমতিও থাকে না), তাই নিচেরটি নিজের Linux যন্ত্রের জন্য একটি উদাহরণ — সংখ্যার জায়গা ইচ্ছা করে খালি রাখা হলো:

$ gcc -O2 matmul.c -o matmul
$ perf stat -e cycles,instructions,L1-dcache-loads,L1-dcache-load-misses,LLC-load-misses ./matmul

 Performance counter stats for './matmul':
        <সংখ্যা>      cycles
        <সংখ্যা>      instructions              #  <IPC> insn per cycle
        <সংখ্যা>      L1-dcache-loads
        <সংখ্যা>      L1-dcache-load-misses     #  <শতাংশ> of all L1-dcache accesses
        <সংখ্যা>      LLC-load-misses

দুই সংস্করণে L1-dcache-load-misses ÷ (ভেতরের iteration-এর সংখ্যা) হিসাব করে অংশ ৩-এর টেবিলের সাথে মেলানো যায়। Event-এর নাম CPU আর kernel-ভেদে আলাদা (perf list দেখায়), তাই আপেক্ষিক তুলনাই বেশি নির্ভরযোগ্য।

কখন মাথা ঘামাবেন না

Donald Knuth-এর বিখ্যাত সতর্কবাণী — ছোটখাটো দক্ষতার পেছনে আগেভাগে ছোটা (premature optimization) বহু সমস্যার মূল — এখানেও খাটে। একটি loop যদি মোট সময়ের ২% নেয়, তাকে দশ গুণ দ্রুত করলেও পুরো প্রোগ্রাম ২%-এর কম দ্রুত হবে (Amdahl-এর সূত্র, পর্ব ০৩)। ডেটা যদি ছোট আর cache-এ ধরে, loop-ক্রম নিয়ে ভাবনা বৃথা। Matrix গুণ, FFT, sort-এর মতো কাজের জন্য প্রায়ই একটি ভালো library (BLAS, FFTW) আপনার হাতে-লেখা tiling-এর চেয়ে অনেক দ্রুত। আর পড়তে কঠিন কোডের নিজস্ব দাম আছে। নিয়ম: আগে profiler দিয়ে দেখুন সময় কোথায় যায়, তারপর সেখানেই miss গুনুন, পরিবর্তন করুন, ফল মেলান, আবার মাপুন। ব্যতিক্রম একটি: ডেটার বিন্যাস (AoS না SoA, কোন field কোথায়) পরে বদলানো খুব কঠিন, তাই বড় সিস্টেমের নকশার শুরুতেই এটুকু ভেবে রাখা “আগেভাগে” নয়, বুদ্ধিমানের কাজ।

৮ · AI-এর যুগে — cache-কৌশলে AI, আর যাচাইয়ের অভ্যাস

“এই কোড দ্রুত করে দাও” — AI খুব আত্মবিশ্বাসের সাথে tiling, prefetch আর padding যোগ করে দেয়। কিন্তু এই বিষয়ে কয়েকটি ভুল বারবার দেখা যায়:

AI-এর দেওয়া cache-কৌশল হাতে পেলে — চেকলিস্ট

• ভাষাটি row-major না column-major, দেখে নিয়ে ভেতরের loop-এর stride নিজে হিসাব করেছি
• প্রতি iteration-এ miss-এর দাবি হাতে বা একটি ছোট LRU simulator-এ মিলিয়েছি, আর অনুমানগুলো (N, line, cache) লিখে রেখেছি
• Tile-এর মাপ ৩T²·S ≤ cache শর্তে যাচাই করেছি, আর সীমানার অংশ (N ভাগ না গেলে) পরীক্ষা করেছি
• নতুন আর পুরোনো কোডের ফল তুলনা করেছি
• -O2-তে, ফল ব্যবহার করে, কয়েকবার চালিয়ে সবচেয়ে কম সময় মেপেছি — আর মাপের যন্ত্র ও ডেটার মাপ লিখেছি
• Prefetch বা padding-এর লাভ আলাদা করে মেপেছি; লাভ না থাকলে সেটি সরিয়ে দিয়েছি