Cache Effect Measurement

কেন এই প্রজেক্ট

Cache hierarchy লেসনে আমরা শিখেছি L1/L2/L3 কেন আলাদা আলাদা লেভেলে থাকে, inclusive বনাম exclusive policy কী, আর সাইজ বাড়ার সাথে সাথে latency কেন বাড়ে। কিন্তু এই সংখ্যাগুলো — “L1 প্রায় ৪ সাইকেল, L2 প্রায় ১২ সাইকেল, L3 প্রায় ৪০ সাইকেল” — বই থেকে মুখস্থ করা এক জিনিস, আর নিজের মেশিনে নিজে মেপে বের করা সম্পূর্ণ ভিন্ন অভিজ্ঞতা।

এই প্রজেক্টে আমরা কোনো lscpu বা spec sheet না দেখেই শুধু একটা timing experiment দিয়ে বের করব:

আপনার CPU-র L1 data cache ঠিক কত KB
L2 ঠিক কত KB/MB
L3 (shared) ঠিক কত MB
cache line size ঠিক কত বাইট (প্রায় সবসময় ৬৪B, কিন্তু আপনি অনুমান না করে নিজে প্রমাণ করবেন)

মূল কৌশল একটাই: memory-এ একটা নির্দিষ্ট আকারের এলাকা বারবার র‍্যান্ডম প্যাটার্নে ঘুরে ঘুরে অ্যাক্সেস করুন, আর সেই অ্যাক্সেসের গড় সময় মাপুন। যতক্ষণ এলাকাটা cache-এর কোনো এক লেভেলে পুরোপুরি ধরে, গড় সময় কম আর স্থির থাকবে। এলাকাটা যখন সেই লেভেলের সাইজ ছাড়িয়ে যায়, গড় সময় হঠাৎ লাফিয়ে ওঠে — এই লাফটাই একটা cliff, আর cliff-এর ঠিক আগের সাইজটাই সেই cache লেভেলের প্রকৃত ধারণক্ষমতা।

কেন সহজ “strided sum” যথেষ্ট না — এটাই প্রথম আর সবচেয়ে গুরুত্বপূর্ণ শিক্ষা

Benchmarking methodology লেসনের একটা কেন্দ্রীয় সতর্কতা এখানে সরাসরি প্রযোজ্য: latency মাপতে গিয়ে সবচেয়ে স্বাভাবিক ভুলটা হলো এরকম কিছু লেখা —

// ভুল পদ্ধতি — এইটা latency মাপে না, throughput-এর একটা বিকৃত মিশ্রণ মাপে
volatile long sum = 0;
for (size_t i = 0; i \< n; i += stride)
    sum += arr[i];

এটা দুইটা কারণে মিথ্যা সংখ্যা দেয়:

Memory-level parallelism। প্রতিটা arr[i] লোড আগেরটার উপর নির্ভর করে না — এগুলো স্বাধীন। একটা modern out-of-order CPU-র একসাথে ১০-১২টা in-flight memory request পাঠানোর ক্ষমতা থাকে, তাই CPU একসাথে অনেকগুলো cache miss ওভারল্যাপ করে ফেলে। মাপা সময় তখন “per-access latency” না, “latency ÷ parallelism-factor” — যেটা প্রকৃত single-access latency-র চেয়ে অনেক কম দেখাবে।
Hardware prefetcher। স্থির stride-এ sequential অ্যাক্সেস প্যাটার্ন CPU-র stream prefetcher সহজেই ধরে ফেলে, আর ডেটা সত্যিকারের অ্যাক্সেসের আগেই L1-এ নিয়ে আসে। ফলে একটা DRAM-বাউন্ড অ্যাক্সেসও L1-hit-এর মতো দ্রুত দেখাতে পারে।

সমাধান — pointer chasing। একটা array বানান যেখানে প্রতিটা স্লট পরের কোন স্লটে যেতে হবে সেটা র‍্যান্ডমভাবে বলে দেয়, আর সেই চেইন অনুসরণ করুন:

idx = arr[idx];   // পরের ঠিকানা আগের লোডের ফলাফল থেকে আসে

এখানে idx-এর পরের মান জানতে হলে আগের লোড সম্পূর্ণ শেষ হতে হবে — এটা একটা সত্যিকারের data dependency chain। CPU এখানে কোনোভাবেই দুইটা লোড ওভারল্যাপ করতে পারে না (পরেরটার ঠিকানাই এখনো জানা নেই), আর অ্যাক্সেস প্যাটার্ন র‍্যান্ডম বলে prefetcher-ও কিছু অনুমান করতে পারে না। এটাই কেন -O2/-O3-এ কম্পাইল করলেও এই লুপ নিরাপদ — কম্পাইলার optimize করে dependency chain-টা সরাতে পারে না, কারণ সরালে প্রোগ্রামের অর্থই বদলে যাবে।

ধাপে ধাপে

১. একটা random cycle তৈরি করা

nটা স্লট নিয়ে একটা single cycle পারমুটেশন বানাব — মানে arr[i]-কে বারবার অনুসরণ করলে ঠিক n ধাপ পর আবার শুরুর বিন্দুতে ফিরে আসবে, আর প্রতিটা স্লট ঠিক একবার ভিজিট হবে প্রতি lap-এ। Fisher-Yates shuffle দিয়ে একটা random permutation বানিয়ে, তারপর সেটাকে একটা cycle-এ রূপান্তর করলেই হয়:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static long *build_random_cycle(size_t n) {
    long *arr = malloc(n * sizeof(long));
    size_t *perm = malloc(n * sizeof(size_t));
    for (size_t i = 0; i \< n; i++) perm[i] = i;

    for (size_t i = n - 1; i > 0; i--) {          // Fisher-Yates shuffle
        size_t j = rand() % (i + 1);
        size_t tmp = perm[i]; perm[i] = perm[j]; perm[j] = tmp;
    }
    for (size_t i = 0; i \< n; i++)                 // পারমুটেশনকে single cycle-এ গাঁথা
        arr[perm[i]] = perm[(i + 1) % n];

    free(perm);
    return arr;
}

২. Timed pointer-chase

static double time_chase(long *arr, size_t warmup_hops, size_t timed_hops) {
    volatile long sink = 0;
    size_t idx = 0;

    for (size_t i = 0; i \< warmup_hops; i++)       // পেজ ফল্ট/allocation খরচ টাইমিং থেকে বাদ
        idx = arr[idx];

    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    for (size_t i = 0; i \< timed_hops; i++)
        idx = arr[idx];
    clock_gettime(CLOCK_MONOTONIC, &t1);

    sink = idx;                                     // dead-code elimination ঠেকানো
    (void)sink;

    double secs = (t1.tv_sec - t0.tv_sec) + (t1.tv_nsec - t0.tv_nsec) / 1e9;
    return secs / (double)timed_hops * 1e9;          // ns/hop
}

timed_hops-কে একটা fixed সংখ্যায় (যেমন ৫০ লক্ষ) রাখুন — array যত ছোটই হোক, cycle বারবার wrap করে চলতেই থাকবে, তাই সব working-set size-এর জন্য একই সংখ্যক hop মাপা যায়, ফলাফল সরাসরি তুলনাযোগ্য হয়।

৩. Working-set sweep — cliff খোঁজা

int main(void) {
    srand((unsigned)time(NULL));
    size_t sizes_kb[] = {4, 8, 16, 32, 64, 128, 256, 512,
                          1024, 2048, 4096, 8192, 16384, 32768, 65536};
    size_t num_sizes = sizeof(sizes_kb) / sizeof(sizes_kb[0]);

    printf("working_set_KB,ns_per_access\n");
    for (size_t s = 0; s \< num_sizes; s++) {
        size_t n = (sizes_kb[s] * 1024) / sizeof(long);
        long *arr = build_random_cycle(n);
        double ns = time_chase(arr, n * 2, 5000000);
        printf("%zu,%.3f\n", sizes_kb[s], ns);
        free(arr);
    }
    return 0;
}

gcc -O2 -o cache_measure cache_measure.c && ./cache_measure > results.csv দিয়ে চালান — CSV আউটপুট সরাসরি plot বা টেবিলে বসানো যাবে। রিগর বাড়ানোর তিনটা সহজ উপায়: (১) taskset -c 0 ./cache_measure দিয়ে একটা নির্দিষ্ট কোরে pin করুন যাতে migration মাঝপথে cache cold না করে দেয়; (২) প্রতিটা সাইজ ৫ বার চালিয়ে সর্বনিম্ন মানটা রাখুন (median না — কারণ OS noise শুধু সময় বাড়ায়, কখনো কমায় না, তাই minimum-ই “কোনো ইন্টারফেরেন্স ছাড়া” অবস্থার সবচেয়ে কাছের অনুমান); (৩) background-এ ভারী প্রোগ্রাম বন্ধ রাখুন।

৪. ফলাফল পড়া — একটা উদাহরণ

নিচেরটা একটা বাস্তব ডেস্কটপ CPU-তে চালানো উদাহরণ ফলাফল (আপনার সংখ্যা ভিন্ন হবে — এটা কোনো universal টেবিল না):

working set	ns/access
4 KB	1.1
8 KB	1.1
16 KB	1.1
32 KB	1.2
64 KB	3.4
128 KB	3.5
256 KB	3.6
512 KB	3.8
1024 KB	3.9
2048 KB	14.0
4096 KB	14.5
8192 KB	15.0
16384 KB	15.5
32768 KB	89.0
65536 KB	91.0

এখানে তিনটা cliff স্পষ্ট:

৩২KB → ৬৪KB-এ ১.২ → ৩.৪ ns (প্রায় ৩×): এর মানে L1 data cache = 32 KB। ৩২KB পর্যন্ত পুরো working set L1-এ থাকে (~১ ns), ৬৪KB-এ কিছু অংশ ছিটকে L2-তে পড়ে।
1MB → 2MB-এ ৩.৯ → ১৪.০ ns: L2 = 1 MB।
16MB → 32MB-এ ১৫.৫ → ৮৯.০ ns: L3 = 16 MB, আর ৮৯ ns হলো এই মেশিনের প্রকৃত DRAM random-access latency।

লক্ষ্য করুন cliff-গুলো বাস্তবে একদম-এক-লাইনে-লাফানো instant step না-ও হতে পারে — associativity আর replacement policy-র কারণে L2/L3-এর কাছাকাছি ২-৩ ধাপ ধরে ধীরে ধীরে বাড়তে পারে। আপনার কাজ “ঠিক কোন সারিতে লাফালো” খোঁজা না, বরং “কোথায় সংখ্যাটা রুক্ষভাবে ২×-৩×+ হয়ে গেল” সেই অঞ্চল চিহ্নিত করা।

Cache line size — stride-doubling experiment

Working-set sweep আমাদের cache-এর মোট সাইজ দেয়, কিন্তু line size (একবার miss হলে ঠিক কত বাইট একসাথে আসে) মাপতে ভিন্ন একটা experiment লাগে।

ধারণা। একটা বিশাল buffer নিন (LLC-র চেয়ে অনেক বড়, যাতে প্রতিটা নতুন line ছোঁয়া মানেই আসল miss)। সেই buffer-এ বহু “chunk” ছড়িয়ে দিন, একটা থেকে আরেকটা কয়েক MB দূরে (যাতে এক chunk-এ touch করা line অন্য chunk-এ কোনো কাজে না লাগে)। chunk ভ্রমণের ক্রম randomize করুন (prefetcher ঠেকাতে)। প্রতিটা chunk-এর ভেতরে, একটা candidate stride S-এ ৪টা ঠিকানা touch করুন: base+0·S, base+1·S, base+2·S, base+3·S।

S যদি প্রকৃত line size-এর চেয়ে ছোট হয়, তাহলে এই ৪টা ঠিকানার কয়েকটা একই physical cache line-এ পড়বে — প্রথমটা miss, বাকিগুলো hit। গড় খরচ কম।
S যদি line size-এর সমান বা বড় হয়, চারটাই আলাদা line-এ পড়ে — সবগুলোই miss। গড় খরচ পুরো miss latency-তে গিয়ে সমতল হয়ে যায় — আরও বড় S করলেও গড় খরচ আর বাড়ে না, কারণ আগে থেকেই ১০০% miss।

তাই গ্রাফটা দেখতে হবে: S ছোট থাকতে গড় খরচ stride-এর সমানুপাতে বাড়ে, আর S line size ছুঁলে/ছাড়ালে হঠাৎ বাড়া বন্ধ হয়ে সমতল হয়ে যায় — সেই সমতল হওয়ার শুরুর বিন্দুটাই cache line size।

#define CHUNK_GAP  (4 * 1024 * 1024)   // চাংকের মধ্যে ৪MB ফাঁক
#define NUM_CHUNKS 200
#define TOUCHES_PER_CHUNK 4

int main(void) {
    srand((unsigned)time(NULL));
    size_t total = (size_t)NUM_CHUNKS * CHUNK_GAP;
    unsigned char *buf = malloc(total);
    for (size_t i = 0; i \< total; i += 4096) buf[i] = 1;   // পেজ fault-in

    size_t order[NUM_CHUNKS];
    for (int i = 0; i \< NUM_CHUNKS; i++) order[i] = i;
    for (int i = NUM_CHUNKS - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        size_t t = order[i]; order[i] = order[j]; order[j] = t;
    }

    size_t strides[] = {8, 16, 32, 64, 128, 256, 512};
    printf("stride_bytes,ns_per_touch\n");
    for (size_t si = 0; si \< sizeof(strides)/sizeof(strides[0]); si++) {
        size_t stride = strides[si];
        volatile unsigned char sink = 0;
        struct timespec t0, t1;
        clock_gettime(CLOCK_MONOTONIC, &t0);
        for (int c = 0; c \< NUM_CHUNKS; c++) {
            unsigned char *base = buf + order[c] * (size_t)CHUNK_GAP;
            for (int k = 0; k \< TOUCHES_PER_CHUNK; k++)
                sink += base[k * stride];    // stride*3 সবসময় CHUNK_GAP-এর চেয়ে অনেক ছোট
        }
        clock_gettime(CLOCK_MONOTONIC, &t1);
        (void)sink;
        double secs = (t1.tv_sec - t0.tv_sec) + (t1.tv_nsec - t0.tv_nsec) / 1e9;
        double ns_per_touch = secs / (NUM_CHUNKS * TOUCHES_PER_CHUNK) * 1e9;
        printf("%zu,%.2f\n", stride, ns_per_touch);
    }
    free(buf);
    return 0;
}

উদাহরণ ফলাফল (একই মেশিন, DRAM miss ~৯০ ns ধরে):

stride (bytes)	ns/touch
8	11.2
16	22.5
32	45.0
64	89.5
128	90.1
256	89.8
512	90.3

64 বাইটে গিয়ে বৃদ্ধি থেমে যাচ্ছে আর সমতল হয়ে যাচ্ছে (~৯০ ns, প্রায় পুরো DRAM miss latency) — মানে cache line size = 64 বাইট। এটাই x86-64-এর প্রায় সব আধুনিক প্রসেসরের universal মান, কিন্তু এখন সেটা আপনি ধরে নেননি, প্রমাণ করেছেন।

একটা সতর্কতা: TOUCHES_PER_CHUNK ছোট (৪) রাখা হয়েছে ইচ্ছাকৃতভাবে — অনেক বড় হলে hardware stream prefetcher chunk-এর ভেতরের নিয়মিত stride ধরে ফেলতে পারে, ফলাফল দূষিত করবে। এটাও benchmarking methodology-র একটা বাস্তব শিক্ষা: measurement যন্ত্রটাই যাতে যে জিনিস মাপছে সেটাকে বিকৃত না করে ফেলে।

নিজেকে চ্যালেঞ্জ করুন

প্রকৃত spec-এর সাথে মিলান — lscpu (Linux) বা sysctl -a | grep cache (macOS) বা Windows-এ CPU-Z চালিয়ে আপনার মাপা cliff-গুলো প্রকৃত L1/L2/L3 সাইজের সাথে কতটা মেলে দেখুন, পার্থক্য থাকলে কেন হতে পারে ভাবুন (associativity, shared vs per-core L3)
Associativity-জনিত সীমা — cache শুধু capacity না, associativity দিয়েও সীমাবদ্ধ; একই working-set size-এ কিন্তু ইচ্ছাকৃত conflict-inducing stride (Level 3-এর Cache Simulator প্রজেক্টের মতো) ব্যবহার করে দেখান capacity-এর মধ্যে থাকা সত্ত্বেও hit rate খারাপ হতে পারে
Read বনাম write latency — idx = arr[idx] (read-only chase)-এর পাশে একটা write-heavy ভ্যারিয়েন্ট বানান (arr[idx] = idx; idx = next;), write-back cache-এ dirty line lookup-এর অতিরিক্ত খরচ আছে কি না মাপুন
Multi-core cliff — দুইটা থ্রেড একসাথে ভিন্ন কোরে চালিয়ে shared L3-এ contention-এর প্রভাব মাপুন (single-thread ফলাফলের সাথে তুলনা)
perf দিয়ে যাচাই — Linux-এ perf stat -e L1-dcache-load-misses,LLC-load-misses ./cache_measure চালিয়ে hardware performance counter থেকে সরাসরি miss count দেখে আপনার টাইমিং-ভিত্তিক অনুমানের সাথে ক্রস-চেক করুন

এটা যেখানে গিয়ে মিশবে

এখানে যা শিখলেন	পরে কোথায় লাগবে
Pointer-chasing দিয়ে সত্যিকারের latency মাপা, prefetcher/MLP ফাঁকি এড়ানো	এই মডিউলেরই Benchmarking Methodology লেসন — statistical rigor, warm-up, বহু ট্রায়াল
L1/L2/L3 সাইজ ও line size-এর নিজের-মাপা সংখ্যা	এই মডিউলেরই Matrix Multiply Optimization প্রজেক্ট — tile size ঠিক এই সংখ্যাগুলো থেকে বাছাই হবে
Cache miss latency-র বাস্তব cost	Level 11-এর False Sharing লেসন — একই timing-based measurement কৌশল multi-thread contention-এ প্রয়োগ হবে
Single-machine memory hierarchy latency	Level 11-এর NUMA Topology লেসন — মাল্টি-সকেট মেশিনে cross-node latency আরেকটা, বড় cliff
Hardware-নির্ভর performance বোঝা	Level 12 (Virtualization/Cloud)-এ container CPU pinning ও NUMA-aware scheduling — এই hierarchy না বুঝলে সেই টিউনিং অন্ধের মতো

মাইলস্টোন

আগে যা পড়া দরকার