Prefetching — ডেটা লাগার আগেই নিয়ে আসা

আগে এটা বুঝি

আগের লেসনে আমরা দেখেছি CPU কীভাবে control flow নিয়ে অনুমান করে — কোন branch নেওয়া হবে, আর সেই অনুমানের উপর ভিত্তি করে speculatively কাজ চালিয়ে যায়। এই লেসনে সম্পূর্ণ ভিন্ন এক ধরনের অনুমান — CPU আপনার পরের memory access কোথায় হবে তা অনুমান করার চেষ্টা করে, আর অনুমান সঠিক মনে হলে সেই ডেটা explicit request আসার আগেই cache-এ নিয়ে আসে। একে বলে hardware prefetching।

mathematics/asymptotic-notation লেসনে আমরা একটা রহস্যময় সংখ্যা দেখেছিলাম — sequential array traversal আর random pointer-chasing traversal, দুটোই ঠিক n টা ধাপ, একই কাজ, তবু বড় n-এ ১০-২০ গুণ পার্থক্য। সেই সময় ব্যাখ্যা ছিল “prefetcher পরেরটা আগেই আনে সিকোয়েনশিয়ালে, কিন্তু random access-এ prefetcher অসহায়”। এই লেসনের কাজ সেই একটা বাক্যকে সম্পূর্ণভাবে ভেঙে দেখানো — prefetcher ঠিক কীভাবে কাজ করে, আর ঠিক কেন এটা pointer chasing-এ ভেঙে পড়ে।

মূল ধারণা

Hardware prefetcher — একটা dedicated pattern-detector

advanced-architecture/cache-hierarchy-inclusive-exclusive লেসনে দেখা হয়েছে cache কেন দরকার — locality of reference-এর সুযোগ নিতে। কিন্তু cache নিজে থেকে “ভবিষ্যদ্বাণী” করে না — এটা শুধু যা request করা হয়েছে (আর তার পুরো cache line) রেখে দেয়। Prefetcher একটা আলাদা, dedicated hardware unit (প্রতিটা core-এ, কখনো L1-এর জন্য একটা, L2-এর জন্য আরেকটা আলাদা prefetcher) যেটা load/store unit-এর memory access stream (বা cache miss-এর address stream) ক্রমাগত পর্যবেক্ষণ করে। যদি একটা recognizable pattern দেখা যায়, prefetcher নিজে থেকেই (কোনো software instruction ছাড়াই) সেই pattern অনুযায়ী পরবর্তী ঠিকানার data-কে speculatively cache-এ load করার request পাঠায়।

এটাকে আগের লেসনের সাথে সরাসরি তুলনা করা যায়:

	Branch prediction (আগের লেসন)	Hardware prefetching (এই লেসন)
কী অনুমান করে	পরে কোন instruction চলবে	পরে কোন data address লাগবে
ভুল হলে দাম	Pipeline flush, cycle অপচয়	শুধু একটা wasted cache-fill, cache pollution
Speculative?	হ্যাঁ — control-flow speculation	হ্যাঁ — data-address speculation
Software-এর কাছে দৃশ্যমান?	না (microarchitectural)	না (microarchitectural)

দুটোই speculative execution-এর একই বৃহত্তর দর্শনের অংশ — “অতীতের প্যাটার্ন দেখে ভবিষ্যতের প্রয়োজন আগেভাগে অনুমান করে, hardware resource আগেই ব্যবহার করে ফেলা” — কিন্তু ভুল prediction-এর দাম সম্পূর্ণ ভিন্ন মাত্রার। Branch misprediction-এ পুরো pipeline flush হয় (কয়েক থেকে কয়েক ডজন cycle)। ভুল prefetch-এ শুধু একটা অপ্রয়োজনীয় cache line লোড হয়ে যায় — pipeline-এ কোনো প্রভাব নেই, শুধু cache space আর memory bandwidth-এর একটা ছোট অপচয়। এই কম দামের কারণেই hardware prefetcher তুলনামূলক “আক্রমণাত্মক” হতে পারে — ভুল হলে খরচ কম।

ভেতরে কী ঘটছে

Sequential prefetcher — সবচেয়ে সরল রূপ

সবচেয়ে basic prefetcher নিয়ম: “cache line N access হয়েছে? তাহলে N+1-ও লাগতে পারে, আগেই এনে রাখি।” একে next-line prefetcherও বলা হয়। যুক্তি সহজ — locality of reference এই assumption-এর উপরই দাঁড়িয়ে (পাশের ডেটা লাগার সম্ভাবনা বেশি)।

Stride prefetcher — একটা নির্দিষ্ট mechanism

বাস্তব CPU-তে সবচেয়ে গুরুত্বপূর্ণ প্রকার হলো stride prefetcher — এটা শুধু “পরের লাইন” ধরে নেয় না, বরং কতটা দূরত্বে (stride) পরপর access হচ্ছে সেটা সক্রিয়ভাবে শেখে। Mechanism-টা concrete ভাবে দেখা যাক — একটা “stride reference table” কল্পনা করুন, প্রতিটা entry একটা নির্দিষ্ট load instruction-এর (তার program counter/PC দিয়ে identify করা) জন্য তিনটা জিনিস মনে রাখে:

struct StrideEntry {
    address  last_addr;      // সর্বশেষ যে ঠিকানা access হয়েছিল
    int64_t  last_stride;    // শেষ দুইটা access-এর মধ্যে দূরত্ব
    int      confidence;     // এই stride কতবার সঠিক প্রমাণিত হয়েছে
};

প্রতিটা নতুন miss address আসার সাথে সাথে:

new_stride = new_addr - entry.last_addr গণনা করা হয়
যদি new_stride == entry.last_stride, তাহলে confidence++ (একই প্যাটার্ন আবার দেখা গেছে)
যদি না মেলে, confidence কমে বা রিসেট হয় (প্যাটার্ন ভেঙে গেছে বা নতুন)
confidence একটা threshold (সাধারণত ২-৩) পার হলে, prefetcher সক্রিয় হয়ে যায় — new_addr + confirmed_stride × degree ঠিকানায় একটা speculative load পাঠায় (degree মানে কতগুলো ভবিষ্যৎ access একসাথে আগে থেকে আনা হবে, prefetch distance-এর একটা অংশ)

for (i = 0; i \< n; i++) sum += arr[i];   // int array, 4 byte/element

Access #   ঠিকানা      new_stride   confidence   prefetcher active?
   1       0x1000         —            0              না
   2       0x1004        +4            1              না
   3       0x1008        +4            2              হ্যাঁ! (threshold=2 ধরা হলো)
   4       0x100C        +4            3         → prefetch 0x1010+ আগেই শুরু
   5       0x1010        +4            3         (cache-এ আগে থেকেই আছে — hit!)

একটা array-sum loop-এ stride prefetcher-এর state ট্রেস।

লক্ষ্য করুন — প্রথম দুই-তিনটা access-এ prefetcher শুধু “শেখে”, কোনো prefetch পাঠায় না (এটাই warm-up cost, খুব ছোট loop-এ prefetcher পুরো সুবিধা নাও দিতে পারে)। একবার প্যাটার্ন confirmed হলে, এটা সামনে এগিয়ে যেতে থাকে, DRAM latency (~২০০ cycle) হাইড করার জন্য যথেষ্ট দূরত্বে।

Prefetch distance-এর হিসাব — কেন 'কতটা এগিয়ে' গুরুত্বপূর্ণ

ধরুন একটা loop iteration-এ ৩ cycle লাগে, আর DRAM latency ~২০০ cycle। যদি prefetcher শুধু ১ iteration আগে prefetch পাঠায়, latency হাইড হবে মাত্র 3 cycle — বাকি 197 cycle প্রকৃত access-এর সময়ও অপেক্ষা করতেই হবে। DRAM latency পুরোপুরি হাইড করতে prefetcher-কে কমপক্ষে 200 / 3 ≈ 67 iteration আগে prefetch শুরু করতে হবে — এটাই prefetch distance, আর বাস্তব CPU prefetcher এটা runtime-এ dynamically টিউন করার চেষ্টা করে (memory latency আর loop-এর গতি দুটোই বদলাতে পারে)।

কেন pointer chasing prefetcher-কে সম্পূর্ণ অসহায় করে দেয়

এখন আসল প্রশ্ন — mathematics/asymptotic-notation লেসনের সেই ১০-২০ গুণ পার্থক্যের root cause।

Array traversal-এ arr[i], arr[i+1], arr[i+2], ... — প্রতিটা পরের ঠিকানা arithmetically গণনাযোগ্য: base + i × 4। Prefetcher-কে শুধু stride শিখতে হয় (constant, 4 বা যত বাইট), তারপর নিজে থেকেই পরের ঠিকানা compute করে ফেলতে পারে — এই গণনার জন্য কোনো memory access লাগেই না।

Linked list traversal-এ node = node->next — পরের ঠিকানা কোনো সূত্র দিয়ে গণনাযোগ্য না। next পয়েন্টারের মান node-টার ভেতরে, memory-তে, সংরক্ষিত আছে — আর সেই মান জানতে হলে সেই node-টাকেই আগে load করতে হবে। যদি list-টা সময়ের সাথে সাথে বিভিন্ন malloc call-এ scattered হয়ে তৈরি হয়ে থাকে (যা সাধারণত হয়), consecutive node-এর ঠিকানার মধ্যে কোনো arithmetic সম্পর্কই নেই — এলোমেলো।

এটা একটা engineering সীমাবদ্ধতা না — একটা মৌলিক সীমা

এখানে গুরুত্বপূর্ণ পয়েন্টটা এই — এটা “prefetcher যথেষ্ট স্মার্ট না” জাতীয় সমস্যা না, যেটা ভবিষ্যতের আরও ভালো hardware দিয়ে সমাধান করা সম্ভব। এমনকি একটা কাল্পনিক, সম্পূর্ণ নিখুঁত prefetcher-ও node->next-এর মান prefetch করতে পারবে না যতক্ষণ না node নিজে memory থেকে পড়া হয়েছে — কারণ সেই ঠিকানা-টা তথ্যগতভাবেই অস্তিত্বে নেই যতক্ষণ না সেই read সম্পূর্ণ হয়। এটা একটা data dependency, addressing pattern-এর সমস্যা না — কোনো pattern-detection কৌশল একটা তথ্য যা এখনো জানা যায়নি সেটা “অনুমান” করতে পারে না অর্থবহভাবে।

এই কারণেই linked-list traversal-কে বলা হয় serialized load chain — প্রতিটা load তার আগেরটার উপর সরাসরি নির্ভরশীল (RAW dependency, computer-architecture/register-renaming-reorder-buffer লেসনের সেই true dependency ধারণারই একটা data-memory রূপ)। একটা মুহূর্তে CPU-র memory subsystem-এ মাত্র একটা outstanding load থাকতে পারে এই chain-এ — পরেরটা শুরুই করা যায় না আগেরটা শেষ না হওয়া পর্যন্ত।

Memory-Level Parallelism (MLP) — আসল পার্থক্যের নাম

উপরের পর্যবেক্ষণটার একটা নাম আছে — Memory-Level Parallelism (MLP): কতগুলো memory request একসাথে “in flight” (pending, একে অপরের ফলাফলের অপেক্ষায় না থেকে) থাকতে পারে।

Sequential/stride access-এ MLP বেশি। Prefetcher (বা এমনকি শুধু out-of-order execution নিজেই, একাধিক independent load issue করে) একসাথে বহু ভবিষ্যৎ ঠিকানার জন্য request পাঠাতে পারে — সবগুলো DRAM-এ সমান্তরালে চলে, তাদের latency overlap হয়। n টা access-এর মোট সময় প্রায় latency + (n-1) × throughput_per_access — কার্যত একটামাত্র latency-র দাম, বাকি সব pipeline হয়ে যায়।
Pointer chasing-এ MLP = ১। প্রতিটা load তার আগেরটার ফলাফলের উপর নির্ভর করে, তাই কখনো একসাথে একটার বেশি request pending থাকতে পারে না। n টা access-এর মোট সময় প্রায় n × latency — পুরো DRAM latency-টাই প্রতিবার, কোনো overlap ছাড়া।

Sequential (MLP উচ্চ, prefetcher বহু request একসাথে পাঠাতে পারে):
  req1 ──────────────▶ (200 cycle)
  req2   ──────────────▶ (200 cycle, req1-এর সাথে overlap)
  req3     ──────────────▶ (200 cycle, overlap)
  ...
  মোট সময় ≈ 200 + (n-1) × ছোট gap   ≈ প্রায় একটাই latency

Pointer chasing (MLP = 1, পরেরটা শুরুই করা যায় না আগেরটা ছাড়া):
  req1 ──────────────▶ (200 cycle)
                        req2 ──────────────▶ (200 cycle)
                                              req3 ──────────────▶ ...
  মোট সময় ≈ n × 200 cycle   ← কোনো overlap নেই

MLP-এর প্রভাব — একই n access, সম্পূর্ণ ভিন্ন মোট সময়।

এই একটা figure-ই mathematics/asymptotic-notation-এর সেই ১০-২০ গুণ পার্থক্যের সম্পূর্ণ mechanistic ব্যাখ্যা — দুটোই Θ(n), দুটোতেই ঠিক nটা memory access, কিন্তু একটায় latency-গুলো overlap হয়, আরেকটায় হয় না। Big-O এই পার্থক্য দেখাতে পারে না কারণ এটা “কয়টা অপারেশন” গোনে, “কতটা সমান্তরালে চলতে পারে” গোনে না।

Prefetcher-এর সীমা — সবকিছু prefetch করতে পারে না

Stride prefetcher নিখুঁত না — কিছু বাস্তব সীমাবদ্ধতা:

Page boundary। অনেক prefetcher physical page (৪ KB)-এর বাইরে prefetch করে না, কারণ virtual address-এ পাশাপাশি হলেও physical address-এ পাশাপাশি থাকার নিশ্চয়তা নেই (virtual memory-র page mapping arbitrary হতে পারে)। তাই একটা বড় stride যা প্রায়ই page cross করে, prefetcher-এর কার্যকারিতা কমিয়ে দিতে পারে।
Warm-up cost। ছোট loop (n ছোট) prefetcher শেখার আগেই শেষ হয়ে যেতে পারে — কোনো সুবিধাই পাওয়া যায় না।
Multiple concurrent stream। একটা core যদি একসাথে অনেকগুলো ভিন্ন stride pattern (একাধিক array একসাথে traverse) চালায়, stride table-এ সীমিত entry (সাধারণত কয়েক ডজন) থাকায় সব pattern ট্র্যাক করা সম্ভব নাও হতে পারে।
Irregular কিন্তু non-random pattern। কিছু access pattern (যেমন একটা repeating কিন্তু জটিল sequence, +4, +4, +12, +4, +4, +12, ...) সাধারণ stride prefetcher ধরতে পারে না, যদিও এটা সত্যিই predictable — এই ধরনের জটিল pattern ধরার জন্য আরও advanced (“correlation prefetcher”) ডিজাইন থাকে, কিন্তু সেগুলো hardware-এ ব্যয়বহুল, তাই সবখানে নেই।

Software prefetch hint — যখন hardware নিজে থেকে পারে না

যখন access pattern প্রোগ্রামার/compiler জানে কিন্তু hardware prefetcher runtime-এ চিনতে পারবে না (বা দেরিতে চিনবে), একটা escape hatch আছে — software prefetch instruction, explicitly compiler-কে বলা “এই ঠিকানাটা শীঘ্রই লাগবে, এখনই cache-এ আনা শুরু করো”।

#include \<stddef.h>

// GCC/Clang builtin — সরাসরি একটা prefetch instruction-এ compile হয়
// arg1: ঠিকানা, arg2: 0=read/1=write, arg3: locality hint (0-3)
__builtin_prefetch(ptr, 0, 3);

এটা x86-এ prefetcht0/prefetchnta-এর মতো একটা instruction-এ compile হয় — এই instruction-এর একটা বিশেষ বৈশিষ্ট্য: এটা কখনো fault করে না (invalid address দিলেও প্রোগ্রাম crash করে না, শুধু কার্যকর কিছু হয় না) — কারণ এটা নিছক একটা hint, কোনো guarantee বা correctness-প্রভাবিত instruction না। এই “fault-tolerant” প্রকৃতিটাই এটাকে speculative execution-এর সাথে conceptually যুক্ত করে — এটা নিজেই একটা নিরাপদ, controlled ফর্মের speculation, শুধু ডেটার জন্য।

Software prefetch সহজেই ভুল হয় — measure ছাড়া বিশ্বাস না

Manual prefetch hint দুই দিকেই ভুল হতে পারে:

খুব আগে prefetch করলে — ডেটা cache-এ চলে আসে, কিন্তু আসল ব্যবহারের অনেক আগে, ততক্ষণে অন্য কিছু (হয়তো বেশি জরুরি ডেটা) সেই cache line-কে evict করে ফেলে — prefetch-এর পুরো লাভ নষ্ট, উপরন্তু memory bandwidth-ও অপচয় হলো (cache pollution)।
খুব দেরিতে prefetch করলে — DRAM latency হাইড করার মতো যথেষ্ট সময় থাকে না, actual access-এর সময়ও পুরোটা বা আংশিক অপেক্ষা করতে হয় — সুবিধা প্রায় শূন্য।

তাই সঠিক prefetch distance বের করা একটা empirical প্রশ্ন — loop-এর প্রতি-iteration সময় আর memory latency দুটোর অনুপাত জানতে হয়, আর সেটা মেশিন-নির্ভর। এই কারণেই manual prefetch hint যোগ করার পর সবসময় measure করা আবশ্যক, “নিশ্চয়ই সাহায্য করবে” ধরে নিয়ে না — experiment অংশে এটা সরাসরি দেখানো হবে।

উদাহরণ

একটা concrete কেস — hash table bucket চেইন

Hash table-এর collision chain (separate chaining) linked list-এরই একটা রূপ — এখানে prefetching-এর সীমা আর সুযোগ দুটোই স্পষ্ট দেখা যায়।

typedef struct Node {
    int key, value;
    struct Node *next;
} Node;

int lookup(Node **buckets, int idx, int key) {
    Node *n = buckets[idx];
    while (n) {
        if (n->key == key) return n->value;
        n = n->next;             // pointer chase — prefetcher অসহায়
    }
    return -1;
}

buckets[idx] access সরাসরি array indexing — prefetcher-এর জন্য সহজ (যদি lookup বহুবার sequential idx দিয়ে কল হয়)। কিন্তু n = n->next-এর চেইনটা pure pointer chasing — chain-এর দৈর্ঘ্য যত বড়, তত বেশি serialized DRAM latency জমা হবে, কোনো hardware prefetcher-ই এটা এড়াতে পারবে না। এই একই কারণেই ভালো hash table implementation collision chain ছোট রাখার চেষ্টা করে (load factor সীমিত রেখে, বা open addressing ব্যবহার করে যা সম্পূর্ণ array-ভিত্তিক, তাই prefetcher-friendly) — শুধু asymptotic O(1) average lookup-এর জন্য না, বরং এই memory-level parallelism-এর সমস্যা এড়াতেও।

নিজে চালিয়ে দেখুন

EXPERIMENT

Stride বাড়িয়ে prefetcher-কে ভাঙা

Linux/macOS, gcc· ২০ মিনিট

// stride_sweep.c
#include \<stdio.h>
#include \<stdlib.h>
#include \<time.h>

#define TOTAL_BYTES (256 * 1024 * 1024)   // 256 MB buffer, L3-এর চেয়ে বড়

double bench(char *buf, size_t stride, size_t n_access) {
    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    long sum = 0;
    for (size_t i = 0; i \< n_access; i++) {
        sum += buf[(i * stride) % TOTAL_BYTES];
    }
    clock_gettime(CLOCK_MONOTONIC, &t1);
    if (sum == -1) printf("");   // optimize-away ঠেকাতে
    return (t1.tv_sec - t0.tv_sec) + (t1.tv_nsec - t0.tv_nsec) / 1e9;
}

int main(void) {
    char *buf = malloc(TOTAL_BYTES);
    for (size_t i = 0; i \< TOTAL_BYTES; i++) buf[i] = (char)i;

    size_t n_access = 20 * 1000 * 1000;
    size_t strides[] = {64, 256, 4096, 16384, 65536};

    printf("%-12s %-14s %-14s\n", "stride", "time(s)", "ns/access");
    for (size_t s = 0; s \< sizeof(strides)/sizeof(strides[0]); s++) {
        double t = bench(buf, strides[s], n_access);
        printf("%-12zu %-14.4f %-14.2f\n", strides[s], t,
               t * 1e9 / n_access);
    }
    return 0;
}

gcc -O2 -o stride_sweep stride_sweep.c && ./stride_sweep

সাধারণ ফলাফল (প্যাটার্ন consistent, সংখ্যা মেশিনভেদে বদলাবে):

stride       time(s)        ns/access
64           0.041          2.05      ← cache-line stride, prefetcher চমৎকার কাজ করে
256          0.098          4.90      ← এখনও within-page, ধরা যাচ্ছে
4096         0.312          15.60     ← ঠিক এক page — prefetcher-এর সীমায়
16384        0.890          44.50     ← page cross ঘন ঘন — prefetcher কার্যত অকেজো
65536        1.740          87.00     ← প্রায় pure random latency-র কাছাকাছি

stride 64 থেকে 65536-এ প্রায় ৪০ গুণ ধীর — অথচ প্রতিটাই একটা perfectly constant stride, কোনো randomness নেই! পার্থক্যটা আসছে কারণ বড় stride-এ পরপর access প্রায় সবসময় ভিন্ন page-এ পড়ে (আর প্রায়ই ভিন্ন cache line, কম spatial reuse), আর prefetcher-এর tracking সীমার বাইরে চলে যায়।

perf দিয়ে সরাসরি hardware prefetcher-এর কার্যকারিতা যাচাই করা যায়:

perf stat -e L1-dcache-load-misses,LLC-load-misses,cycles ./stride_sweep

ছোট stride-এ miss rate কম থাকবে (prefetcher সফলভাবে আগে থেকে এনে রাখছে); বড় stride-এ miss rate লাফিয়ে বাড়বে।

এটা কী প্রমাণ করে

Constant stride হওয়া সত্ত্বেও, stride যথেষ্ট বড় হলে (page boundary পার হলে) prefetcher কার্যকারিতা হারায় — 'constant stride মানেই prefetch-বান্ধব' এই সরলীকরণ ভুল প্রমাণ করা।

নিজে বানান

BUILD IT

Linked list traversal-এ manual prefetch — কতটা সাহায্য করে, কখন করে না

C · ●●●○○

একটা linked list বানান যার প্রতিটা node malloc দিয়ে আলাদাভাবে, এলোমেলো ক্রমে allocate হয়েছে (আগের লেসনের random-permutation পদ্ধতির মতো)
একটা baseline traversal লিখুন যেখানে প্রতিটা node-এ কিছু dummy কাজ (যেমন একটা ছোট loop) করা হয়, কোনো prefetch hint ছাড়া
একই traversal-এ প্রতিটা iteration-এর শুরুতে __builtin_prefetch(node->next) যোগ করুন, তারপর dummy কাজটা করুন
dummy কাজের পরিমাণ বাড়িয়ে-কমিয়ে (০ থেকে অনেক বেশি) দুইটা সংস্করণ তুলনা করুন — prefetch-এর সুবিধা কখন সবচেয়ে বেশি, কখন প্রায় শূন্য
এখন node->next->next প্রি-ফেচ করে দেখুন (দুই ধাপ আগে) — এটা সাহায্য করে না ক্ষতি করে তা measure করুন

মূল প্রশ্ন: pointer chasing-এ যেহেতু পরের ঠিকানা আগে থেকে জানাই যায় না (এই লেসনের mechanism অংশ), সেখানে prefetch hint কীভাবে কোনো কাজে লাগতে পারে? উত্তর — hint নিজে থেকে dependency chain ভাঙতে পারে না, কিন্তু যদি প্রতিটা node-এ করার মতো অন্য কোনো কাজ থাকে (dummy computation), তাহলে node->next-এর load-টা early শুরু করে দিয়ে সেই latency-কে dummy কাজের সাথে overlap করানো সম্ভব — dependency chain না ভেঙে, শুধু latency hide করে।

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

typedef struct Node {
    struct Node *next;
    long payload;
} Node;

Node *build_scattered_list(int n) {
    Node **nodes = malloc(n * sizeof(Node*));
    for (int i = 0; i \< n; i++) {
        nodes[i] = malloc(sizeof(Node));   // প্রতিটা আলাদা allocation
    }
    // ইচ্ছাকৃতভাবে এলোমেলো ক্রমে link করা, allocator-এর natural
    // locality নষ্ট করতে
    srand(1);
    for (int i = n - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        Node *tmp = nodes[i]; nodes[i] = nodes[j]; nodes[j] = tmp;
    }
    for (int i = 0; i \< n - 1; i++) nodes[i]->next = nodes[i + 1];
    nodes[n - 1]->next = NULL;
    Node *head = nodes[0];
    free(nodes);
    return head;
}

long dummy_work(long seed, int amount) {
    long x = seed;
    for (int i = 0; i \< amount; i++) x = x * 2654435761u + 1;
    return x;
}

double traverse_baseline(Node *head, int work) {
    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    long acc = 0;
    for (Node *n = head; n; n = n->next) {
        acc += dummy_work(n->payload, work);
    }
    clock_gettime(CLOCK_MONOTONIC, &t1);
    if (acc == -1) printf("");
    return (t1.tv_sec - t0.tv_sec) + (t1.tv_nsec - t0.tv_nsec) / 1e9;
}

double traverse_prefetched(Node *head, int work) {
    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    long acc = 0;
    for (Node *n = head; n; n = n->next) {
        if (n->next) __builtin_prefetch(n->next, 0, 3);
        acc += dummy_work(n->payload, work);
    }
    clock_gettime(CLOCK_MONOTONIC, &t1);
    if (acc == -1) printf("");
    return (t1.tv_sec - t0.tv_sec) + (t1.tv_nsec - t0.tv_nsec) / 1e9;
}

int main(void) {
    int n = 2000000;
    printf("%-10s %-14s %-14s %-10s\n", "work", "baseline(s)", "prefetch(s)", "speedup");
    for (int work = 0; work \<= 40; work += 10) {
        Node *h1 = build_scattered_list(n);
        Node *h2 = build_scattered_list(n);
        double t1 = traverse_baseline(h1, work);
        double t2 = traverse_prefetched(h2, work);
        printf("%-10d %-14.4f %-14.4f %-10.2fx\n", work, t1, t2, t1 / t2);
    }
    return 0;
}

gcc -O2 -o list_prefetch list_prefetch.c && ./list_prefetch

প্রত্যাশিত প্যাটার্ন:

work       baseline(s)    prefetch(s)    speedup
0          0.512          0.498          1.03x    ← কাজ নেই, overlap করার কিছুই নেই
10         0.560          0.480          1.17x
20         0.610          0.470          1.30x    ← latency ভালোভাবে hide হচ্ছে
40         0.710          0.465          1.53x    ← যথেষ্ট কাজ থাকলে prefetch latency প্রায় পুরো hide করে দেয়

work = 0-এ প্রায় কোনো সুবিধাই নেই — কারণ overlap করার মতো কোনো স্বাধীন কাজ নেই, dependency chain-টাই একমাত্র কাজ। work বাড়ার সাথে সাথে সুবিধা বাড়ে — কারণ dummy কাজটা DRAM latency-র সাথে সমান্তরালে চলতে পারছে।

দুই ধাপ আগে prefetch (node->next->next) পরীক্ষা করলে সাধারণত দেখা যায় সামান্য বা কোনো অতিরিক্ত সুবিধা নেই (কারণ node->next নিজেই এখনো load হয়নি, তাই node->next->next-এর ঠিকানা জানাই সম্ভব না — এটা করতে হলে প্রথমে node->next load করতে হবে, যা এমনিতেই আগের iteration-এ prefetch হয়ে গেছে) — কখনো কখনো সামান্য ক্ষতিও দেখা যেতে পারে অপ্রয়োজনীয় speculative load-এর জন্য memory bandwidth খরচ হওয়ায়। এটাই এই লেসনের মূল সতর্কতার বাস্তব প্রমাণ — prefetch distance বাড়ালেই ভালো হয় না, measure করে বলতে হয়।

বাস্তব সিস্টেমে

Prefetching যেখানে বাস্তবে সিদ্ধান্ত নেয়

glibc-এর অপ্টিমাইজড memcpy/memmove — বড় buffer কপি করার সময় explicit prefetcht0-জাতীয় instruction ব্যবহার করে destination আর source-এর সামনের অংশ আগেই cache-এ আনে, কারণ compiler/hardware prefetcher নিজে থেকে এতটা আক্রমণাত্মকভাবে নাও করতে পারে যতটা এই নির্দিষ্ট, well-known access pattern-এ নিরাপদে করা সম্ভব।
Database hash join — “software-managed prefetching”। একটা hash join-এ প্রতিটা probe row-এর জন্য hash bucket lookup করতে হয়, যা কার্যত pointer chasing (bucket chain বা open-addressing hash table-এর random slot)। আধুনিক database engine (গবেষণা সাহিত্যে সুপরিচিত কৌশল) একসাথে অনেকগুলো probe row-এর hash আগে থেকে গণনা করে, তাদের প্রত্যেকের জন্য prefetch instruction পাঠিয়ে দেয়, তারপর group করে process করে — একটা row-এর latency-কে অন্য row-গুলোর সাথে overlap করানোর কৌশল, ঠিক এই লেসনের build অংশের নীতির বড় স্কেলে প্রয়োগ।
B-tree/B+-tree node traversal। Database index-এ প্রতিটা node শিশুর pointer রাখে — parent থেকে child-এ যাওয়া এক ধরনের pointer chase। কিছু implementation child pointer পড়ার সাথে সাথেই সেটাকে prefetch করে, parent node-এর বাকি অংশ প্রসেস করার সময়টা ব্যবহার করে latency hide করতে।
Data-Oriented Design (গেম ইঞ্জিন) — এই পুরো সমস্যার একটা ভিন্ন সমাধান: manual prefetch hint দেওয়ার বদলে, ডেটা-স্ট্রাকচারই এমনভাবে ডিজাইন করা (array-ভিত্তিক, pointer-heavy structure এড়িয়ে) যাতে hardware prefetcher স্বাভাবিকভাবেই কার্যকর হয় — পরের লেসনে এই দর্শনটাই “AoS বনাম SoA” নামে বিস্তারিত আসবে।
Graph algorithm-এর কুখ্যাত সমস্যা। বড় graph (adjacency list হিসেবে সংরক্ষিত, node-গুলো scattered memory-তে) traverse করা (BFS/DFS) prefetcher-এর জন্য প্রায় worst-case — এই কারণেই large-scale graph processing framework (GraphChi, Ligra-জাতীয় গবেষণা সিস্টেম) বিশেষ cache-সচেতন graph layout ব্যবহার করে।
perf mem / perf c2c — production performance debugging-এ ব্যবহৃত টুল যা সরাসরি দেখায় কোন load memory-bound (prefetcher ব্যর্থ হচ্ছে), সাহায্য করে বোঝাতে কোথায় manual prefetch hint বা data-layout পরিবর্তন লাভজনক হতে পারে।
Multi-stream L2 “streamer” prefetcher। আধুনিক Intel/AMD core একই সময়ে ডজন-খানেক আলাদা stride pattern ট্র্যাক করতে পারে — multi-threaded workload-এ প্রতিটা thread যদি নিজের array আলাদাভাবে scan করে, প্রতিটার জন্য আলাদা prefetch stream চালু থাকতে পারে একসাথে।

যে ভুলগুলো সবাই করে

“Prefetching সবসময় সাহায্য করে — যত বেশি prefetch, তত ভালো।”

এই লেসনের build অংশেই সরাসরি দেখানো হয়েছে — খুব আগে বা অপ্রয়োজনীয় prefetch cache-এর সীমিত জায়গায় দরকারি ডেটা evict করে দিতে পারে (cache pollution), আর memory bandwidth অপচয় করে (একটা অব্যবহৃত prefetch-ও bus-এ ট্রাফিক তৈরি করে, যা প্রকৃত দরকারি request-কে পিছিয়ে দিতে পারে যদি bandwidth-bound workload হয়)। “নিজে থেকে দ্রুত মনে হচ্ছে” যথেষ্ট না — measure করেই বলা উচিত।

“Software prefetch hint যোগ করলেই compiler/programmer-এর দায়িত্ব শেষ, hardware বাকি সামলাবে।”

Software prefetch hint একটা suggestion, guarantee না — CPU এটা ignore করতে পারে (যদি prefetch queue পূর্ণ থাকে, বা hardware সিদ্ধান্ত নেয় এটা কার্যকর না), আর ভুল জায়গায় বসালে (খুব আগে/দেরি) উপকারের বদলে ক্ষতি করতে পারে। এই লেসনের experiment আর build অংশ দুটোই দেখিয়েছে — সঠিক distance/placement একটা empirical প্রশ্ন, একবার লিখে ভুলে যাওয়ার মতো optimization না।

“Hardware prefetcher থাকলে manual prefetching কখনোই দরকার হয় না।”

Hardware prefetcher শুধু নির্দিষ্ট ধরনের প্যাটার্ন (sequential, constant stride, নির্দিষ্ট সীমার মধ্যে) চেনে। Pointer chasing, জটিল বা data-dependent access pattern, বা prefetcher-এর tracking সীমা ছাড়িয়ে যাওয়া pattern-এ hardware prefetcher একেবারেই সাহায্য করতে পারে না — সেখানে হয় manual prefetch hint (যদি overlap করার মতো অন্য কাজ থাকে), নয়তো ডেটা-স্ট্রাকচার redesign (linked structure-কে array-ভিত্তিক করা) দরকার হয়।

বুঝেছেন কি না দেখুন

একজন developer বলে, “আমাদের hardware prefetcher যথেষ্ট স্মার্ট না — ভবিষ্যতের কোনো CPU generation নিশ্চয়ই এমন prefetcher বানাবে যেটা linked list traversal-ও পুরোপুরি hide করে ফেলবে।” এই দাবিটা কেন মৌলিকভাবে ভুল?

যুক্তি

এটা একটা engineering সীমাবদ্ধতাকে তথ্যতাত্ত্বিক সীমার সাথে গুলিয়ে ফেলা। একটা linked list-এ node->next-এর মান memory-তে সংরক্ষিত, আর সেই মান শুধুমাত্র node-কে সম্পূর্ণভাবে load করেই জানা সম্ভব — এটা কোনো “prefetcher যথেষ্ট চালাক না” এর সমস্যা না, বরং তথ্যটাই এখনো অস্তিত্বে নেই (CPU-র কাছে জানার উপায়ে নেই) যতক্ষণ না সেই load সম্পূর্ণ হয়।

কোনো hardware, তার prediction কৌশল যত জটিলই হোক না কেন, এমন একটা তথ্য “prefetch” করতে পারে না যেটা এখনো কোনো জায়গা থেকে পড়াই হয়নি — এটা branch prediction-এর সেই একই সীমার মতো (সম্পূর্ণ এলোমেলো ৫০-৫০ branch-এ কোনো predictor ৫০%-এর বেশি ভালো করতে পারে না, কারণ predict করার মতো কোনো signal নেই)। এখানেও একই নীতি — signal নেই মানে prediction অসম্ভব, hardware generation যতই উন্নত হোক।

একমাত্র বাস্তব সমাধান ডেটা-স্ট্রাকচার বদলানো (array-ভিত্তিক করা, যেখানে ঠিকানা arithmetically গণনাযোগ্য), prefetcher-কে আরও “স্মার্ট” বানানো না।

একটা loop-এ প্রতিটা iteration গড়ে ৫ cycle সময় নেয়, আর DRAM latency এই মেশিনে ১৮০ cycle। Prefetcher-কে DRAM latency সম্পূর্ণ hide করতে ন্যূনতম কত iteration আগে prefetch শুরু করতে হবে?

প্রয়োগ

হিসাবটা সহজ ভাগ — কতগুলো ৫-cycle iteration মিলে ১৮০ cycle পূরণ হয়:

$\text{prefetch distance} = \left\lceil \frac{180}{5} \right\rceil = 36 \text{ iteration}$

অর্থাৎ prefetcher-কে (বা manual prefetch hint-কে) বর্তমান iteration থেকে অন্তত ৩৬ iteration ভবিষ্যতের ঠিকানার জন্য request পাঠাতে হবে, যাতে সেই ডেটা actual ব্যবহারের সময় ততক্ষণে cache-এ পৌঁছে যায়। যদি prefetch distance এর চেয়ে কম হয় (ধরুন মাত্র ১০ iteration আগে), 180 - 10×5 = 130 cycle latency এখনও hide হয়নি — actual access-এ আংশিক অপেক্ষা করতে হবে। যদি distance অনেক বেশি হয় (ধরুন ১০০ iteration আগে), ডেটা প্রয়োজনের অনেক আগেই cache-এ চলে আসবে — কাজ ঠিকই হবে, কিন্তু cache-এ বেশিক্ষণ “বসে থাকা” মানে অন্য ডেটার জন্য জায়গা কম, যা পরোক্ষ ক্ষতির (cache pollution) ঝুঁকি তৈরি করে যদি cache ছোট হয় বা অনেক পুরনো prefetch-এর ফলাফল জমে যায়।

Spectre-এর probe array উদাহরণে (আগের লেসন) ইচ্ছাকৃতভাবে প্রতিটা entry-কে ৪০৯৬ byte (এক page) দূরত্বে রাখা হয়েছিল, একটা মাত্র cache line (৬৪ byte) দূরত্বে না। এই লেসনের জ্ঞান দিয়ে ব্যাখ্যা করুন কেন।

যুক্তি

যদি probe array entry-গুলো ৬৪ byte (একটা cache line) দূরত্বে রাখা হতো, একটা নির্দিষ্ট entry access করার সাথে সাথে sequential/next-line prefetcher পাশের এক বা একাধিক entry-ও speculatively cache-এ এনে ফেলতে পারত — শুধু “সেই একটা secret-নির্দিষ্ট entry” access হওয়ার কারণে না, বরং locality-based prefetching-এর কারণে। তাহলে timing measurement-এ একাধিক entry দ্রুত দেখাবে (আসল touched entry-টা, আর prefetcher-এর এনে দেওয়া পাশেরগুলোও) — attacker আর নিশ্চিতভাবে বলতে পারবে না কোন entry-টা আসল secret-নির্দেশিত ছিল, কারণ signal-টা “দূষিত” (noisy) হয়ে গেছে।

৪০৯৬ byte (এক পূর্ণ page) দূরত্ব ব্যবহার করলে — এই লেসনে আলোচিত page-boundary সীমাবদ্ধতার কারণে — hardware prefetcher সাধারণত পাশের entry prefetch করবে না (অনেক prefetcher design page cross করে না)। তাই timing measurement-এ শুধু একটাই entry দ্রুত দেখাবে — ঠিক যেটা speculative access দিয়ে touch হয়েছিল, কোনো prefetcher-induced false positive ছাড়া। এটা attack-এর নির্ভুলতা (signal-to-noise ratio) নিশ্চিত করার একটা প্রকৌশলগত সিদ্ধান্ত, এই লেসনের prefetcher আচরণ সরাসরি জানার ফল।

একটা টিম দুটো বিকল্পের মধ্যে বেছে নিতে চায় একটা graph-traversal-heavy workload-এর জন্য: (ক) বিদ্যমান adjacency-list (pointer-heavy) ডেটা-স্ট্রাকচার রেখে সব জায়গায় manual __builtin_prefetch যোগ করা, অথবা (খ) পুরো ডেটা-স্ট্রাকচার adjacency-array (CSR — Compressed Sparse Row, একটা flat array-ভিত্তিক প্রতিনিধিত্ব)-এ রিরাইট করা। Trade-off বিশ্লেষণ করুন।

ডিজাইন

দুটোই বৈধ কৌশল, কিন্তু ভিন্ন মাত্রার লাভ আর দাম নিয়ে আসে।

(ক) Manual prefetch — কম কাজ, সীমিত লাভ। Graph traversal-এ প্রতিটা node-এর neighbor pointer সাধারণত সম্পূর্ণ ভিন্ন ঠিকানায় (scattered allocation) — এই লেসনের build অংশের linked-list উদাহরণের মতোই, একটা node access করে তার প্রথম neighbor-এর pointer prefetch করা সম্ভব, কিন্তু dependency chain-টা এখনও ভাঙা যাচ্ছে না। যদি প্রতিটা node visit-এ যথেষ্ট per-node কাজ থাকে (যেমন কোনো ভারী computation), prefetch কিছুটা latency hide করতে পারবে — কিন্তু graph algorithm প্রায়ই per-node কাজ খুব হালকা (শুধু visited-flag চেক), তাই overlap করার মতো তেমন কিছু নেই, লাভ সীমিত।

(খ) CSR রিরাইট — বেশি কাজ, মৌলিক সমাধান। CSR প্রতিনিধিত্বে সব neighbor একটা একক, বড়, contiguous array-তে থাকে (প্রতিটা node-এর neighbor-list একটা offset+length দিয়ে নির্দেশিত)। এখন neighbor traversal হয়ে যায় sequential array access — ঠিক এই লেসনের stride-prefetcher-friendly প্যাটার্ন, hardware prefetcher নিজে থেকেই কার্যকরভাবে কাজ করবে, কোনো manual hint ছাড়াই, এমনকি এই লেসনের experiment-এর মতোই measurably দ্রুত।

সিদ্ধান্তের মানদণ্ড:

যদি ডেটা-স্ট্রাকচার রিরাইট ব্যয়বহুল হয় (বিশাল codebase, বহু জায়গায় ব্যবহৃত), আর সামান্য উন্নতিই যথেষ্ট — (ক) দিয়ে শুরু করা বাস্তবসম্মত, কিন্তু expectation বাস্তবসম্মত রাখা উচিত (২০-৩০%, বিশাল না)।
যদি এই graph traversal performance-critical hot path হয় (বারবার চলে, বড় স্কেলে) — (খ)-এর upfront খরচ ন্যায্য, কারণ এটা সমস্যার root cause (MLP = 1) সরাসরি সমাধান করে, শুধু symptom কমায় না।

এটাই মূল শিক্ষা: manual prefetch hint একটা patch, ডেটা-লেআউট পরিবর্তন একটা cure — যেখানে সম্ভব, দ্বিতীয়টাই বেশি টেকসই লাভ দেয়, পরের লেসনে (AoS বনাম SoA) এই একই নীতি আরও বিস্তারিত দেখব।

এরপর কী

এই দুই লেসন জুড়ে আমরা দেখলাম CPU দুই ধরনের ভবিষ্যদ্বাণী করে — control flow (branch prediction) আর data address (prefetching) — আর দুটোই “past pattern দিয়ে future অনুমান” নীতির উপর দাঁড়িয়ে, দুটোরই নিজস্ব সীমা আছে।

পরের লেসনে আমরা সম্পূর্ণ ভিন্ন এক ধরনের parallelism দেখব — prediction বা speculation না, বরং একটা instruction দিয়ে সত্যিই একসাথে বহু data element প্রসেস করা। computer-architecture/simd লেসনে আমরা SIMD-র ধারণা আর ইতিহাস দেখেছিলাম; এবার হাতে-কলমে real AVX2 আর ARM NEON intrinsics কোড লিখে দেখব কীভাবে এই “packed register” ধারণাটা বাস্তব, compilable প্রোগ্রামে রূপ নেয় — আর এই লেসনের prefetching আর data-layout আলোচনা (contiguous memory, array-ভিত্তিক স্ট্রাকচার) ঠিক সেই ভিত্তি তৈরি করে দিয়েছে যা SIMD programming-এর প্রথম পূর্বশর্ত।

Prefetching — ডেটা লাগার আগেই নিয়ে আসা

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

মূল ধারণা

Hardware prefetcher — একটা dedicated pattern-detector

ভেতরে কী ঘটছে

Sequential prefetcher — সবচেয়ে সরল রূপ

Stride prefetcher — একটা নির্দিষ্ট mechanism

কেন pointer chasing prefetcher-কে সম্পূর্ণ অসহায় করে দেয়

Memory-Level Parallelism (MLP) — আসল পার্থক্যের নাম

Prefetcher-এর সীমা — সবকিছু prefetch করতে পারে না

Software prefetch hint — যখন hardware নিজে থেকে পারে না

উদাহরণ

একটা concrete কেস — hash table bucket চেইন

নিজে চালিয়ে দেখুন

Stride বাড়িয়ে prefetcher-কে ভাঙা

নিজে বানান

Linked list traversal-এ manual prefetch — কতটা সাহায্য করে, কখন করে না

বাস্তব সিস্টেমে

Prefetching যেখানে বাস্তবে সিদ্ধান্ত নেয়

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী

আরও পড়ুন

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

◔আগে এটা বুঝিWhy this matters

◆মূল ধারণাCore concept

Hardware prefetcher — একটা dedicated pattern-detector

⚙ভেতরে কী ঘটছেUnder the hood

Sequential prefetcher — সবচেয়ে সরল রূপ

Stride prefetcher — একটা নির্দিষ্ট mechanism

কেন pointer chasing prefetcher-কে সম্পূর্ণ অসহায় করে দেয়

Memory-Level Parallelism (MLP) — আসল পার্থক্যের নাম

Prefetcher-এর সীমা — সবকিছু prefetch করতে পারে না

Software prefetch hint — যখন hardware নিজে থেকে পারে না

▶উদাহরণExample

একটা concrete কেস — hash table bucket চেইন

⌘নিজে চালিয়ে দেখুনExperiment

Stride বাড়িয়ে prefetcher-কে ভাঙা

⚒নিজে বানানBuild it yourself

Linked list traversal-এ manual prefetch — কতটা সাহায্য করে, কখন করে না

◉বাস্তব সিস্টেমেReal-world usage

Prefetching যেখানে বাস্তবে সিদ্ধান্ত নেয়

⚠যে ভুলগুলো সবাই করেMisconceptions

?বুঝেছেন কি না দেখুনCheck understanding

→এরপর কীNext step

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

ভেতরে কী ঘটছে

উদাহরণ

নিজে চালিয়ে দেখুন

নিজে বানান

বাস্তব সিস্টেমে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী