মেমরি হায়ারার্কি আর locality — কেন cache কাজ করে

১ · প্রসেসর আর মেমরির ফারাক — memory wall

মডিউল ৬ আর ৭-এ আমরা CPU-কে দ্রুত করার অনেক কৌশল দেখেছি: পর্ব ৩৫-এর pipeline, পর্ব ৩৯-এর superscalar, পর্ব ৪০-এর out-of-order execution, পর্ব ৪৩-এর multithreading. প্রতিবারই একটি শত্রু ফিরে এসেছে — ডেটা না পাওয়া load.

প্রতিটি instruction মেমরি ছোঁয়। Instruction নিজেই মেমরিতে থাকে, তাই প্রতিটি instruction-এর জন্য অন্তত একটি instruction fetch. তার ওপর load আর store — সাধারণ প্রোগ্রামে প্রতি তিন-চারটি instruction-এ একটি, মোটামুটি। একটি ৩ GHz CPU-র এক clock cycle মাত্র ০.৩৩ ন্যানোসেকেন্ড (ns). অথচ main memory বা DRAM থেকে একটি ডেটা আনতে মোটামুটি ৫০ থেকে ১০০ ns লাগে — অর্থাৎ ১৫০ থেকে ৩০০ cycle. প্রতিটি access-এ যদি এতক্ষণ অপেক্ষা করতে হতো, পর্ব ৩-এর CPI-র সূত্রে CPI শত শত হয়ে যেত।

ফারাকটা কীভাবে তৈরি হলো

১৯৭০-এর দশকের শেষ আর ১৯৮০-এর দশকের শুরুতে microprocessor-এর clock আর DRAM-এর গতি কাছাকাছি ছিল। তখনকার অনেক ছোট কম্পিউটারে cache ছাড়াই CPU সরাসরি মেমরি পড়ত, আর খুব একটা অপেক্ষা করতে হতো না। তারপর দুটি রেখা আলাদা হয়ে যায়। পর্ব ২-এ দেখেছেন, Moore-এর সূত্র আর Dennard scaling-এর যুগে একটি processor-এর কর্মক্ষমতা ১৯৮০-এর দশকের মাঝামাঝি থেকে ২০০০-এর দশকের শুরু পর্যন্ত বছরে মোটামুটি ৫০%-এর মতো হারে বেড়েছে (Hennessy–Patterson-এর বইয়ের হিসাবে)। DRAM-এর ধারণক্ষমতা দ্রুত বেড়েছে, কিন্তু তার latency কমেছে বছরে মাত্র কয়েক শতাংশ। তাঁদের বইয়ের একটি log-scale ছবিতে ফারাকটা কয়েক দশকে কয়েকশো গুণ ছাড়িয়ে যায় (সংস্করণভেদে সংখ্যা কিছুটা আলাদা)।

১৯৯৫ সালে William Wulf আর Sally McKee একটি ছোট প্রবন্ধে এই অবস্থার নাম দেন memory wall: যদি ফারাক এভাবে বাড়তেই থাকে, তাহলে একদিন CPU-র গতি আর কোনো কাজেই আসবে না — সব সময় যাবে মেমরির অপেক্ষায়। ২০০০-এর দশকের মাঝামাঝি থেকে একটি core-এর clock আর তেমন বাড়েনি (পর্ব ২-এর power wall), তাই ফারাক বাড়ার গতি কমেছে। কিন্তু একই chip-এ অনেক core এসেছে, আর সবাই একই মেমরি ভাগ করে — চাপ কমেনি, শুধু রূপ বদলেছে। আজও একটি DRAM access-এ মোটামুটি কয়েকশো cycle লাগে।

২ · আদর্শ মেমরি কেন অসম্ভব — প্রযুক্তির trade-off

একজন প্রোগ্রামার যা চান: অসীম বড়, CPU-র সমান দ্রুত, আর প্রায় বিনামূল্যে পাওয়া মেমরি। কোনো একটি প্রযুক্তি তিনটি একসাথে দিতে পারে না। কারণগুলো ভৌত:

• বড় মানে দূরে। মেমরি যত বড়, তার wire তত লম্বা, ঠিকানা বাছাইয়ের decoder তত গভীর। পর্ব ১৮-এ দেখেছেন, লম্বা wire-এ সংকেত পৌঁছাতে সময় লাগে। বড় মেমরি তাই chip-এর বাইরে, কয়েক সেন্টিমিটার দূরে বসে।
• দ্রুত cell মানে বড় cell. SRAM-এর একটি bit রাখতে সাধারণত ৬টি transistor লাগে (দুটি inverter-এর loop আর দুটি access transistor — পর্ব ১৫-এর latch-এর আত্মীয়). DRAM-এর একটি bit = ১টি transistor আর ১টি ছোট capacitor. তাই একই জায়গায় DRAM অনেক বেশি bit রাখে, কিন্তু capacitor-এর চার্জ পড়া ধীর, আর চার্জ চুইয়ে যায় বলে বারবার refresh করতে হয় (পর্ব ৪৯).
• স্থায়িত্ব মানে আরও ধীর। Flash-এ (SSD-এর ভেতরে) চার্জ একটি অন্তরিত গেটে আটকে রাখা হয়, তাই বিদ্যুৎ গেলেও ডেটা থাকে; কিন্তু লেখা আর পড়া microsecond-এর মাপে। HDD-তে ঘুরন্ত চাকতি আর নড়াচড়া করা মাথা — milliseconds.

নিচের টেবিলে প্রতিটি স্তরের মোটামুটি মাত্রা দেওয়া হলো, ২০২০-এর দশকের একটি সাধারণ desktop বা server-এর জন্য। এগুলো নির্দিষ্ট chip-এর মাপ নয় — নির্মাতা, প্রজন্ম আর মাপার পদ্ধতিভেদে কয়েক গুণ পর্যন্ত আলাদা হতে পারে। দামও বাজারভেদে ওঠানামা করে। মনে রাখার বিষয় সংখ্যাগুলো নয়, তাদের মাত্রার ফারাক: প্রতিটি ধাপে latency প্রায় ১০ থেকে ১০০ গুণ বাড়ে।

যদি এক cycle হতো এক সেকেন্ড

ন্যানোসেকেন্ড আর মাইক্রোসেকেন্ড মানুষের অনুভূতিতে ধরা পড়ে না। তাই একটি মানব-মাপের তুলনা করা যাক। ধরুন CPU-র clock ৩ GHz, অর্থাৎ এক cycle ≈ ০.৩৩৩ ns. এখন কল্পনা করুন সময় এমনভাবে টেনে লম্বা করা হলো যে এক cycle = এক সেকেন্ড; তাহলে গুণক = ১ s ÷ ০.৩৩৩ ns = ৩ × ১০^৯. প্রতিটি latency-কে এই গুণক দিয়ে গুণ করলে (হিসাবটি একটি ছোট script-এ করা হয়েছে, latency-গুলো উপরের টেবিলের মাঝামাঝি ধরে নেওয়া মান):

L1 থেকে পাওয়া যায় ৪ সেকেন্ডে, DRAM-এ ৫ মিনিট, আর disk-এ মাস। তাই একটি cache miss-কে “মাত্র ১০০ ns” বলে উড়িয়ে দেওয়া যায় না — CPU-র চোখে সেটা পাঁচ মিনিট হাত গুটিয়ে বসে থাকা, যখন প্রতি সেকেন্ডে কয়েকটি instruction শেষ করার ক্ষমতা ছিল।

৩ · হায়ারার্কির পিরামিড — প্রতিটি স্তর পরের স্তরের cache

সমাধান হলো স্তর সাজানো। ওপরে ছোট, দ্রুত, দামি; নিচে বড়, ধীর, সস্তা। CPU সব সময় ওপরের স্তরে খোঁজে। যা দরকার তা ওপরে না পেলে নিচ থেকে আনা হয়, আর আনার সময় সেটির একটি কপি ওপরে রেখে দেওয়া হয় — যাতে পরের বার কাছেই পাওয়া যায়। এই ব্যবস্থার নাম memory hierarchy.

একটি load যখন কোনো স্তরে ডেটা পায় না, কী ঘটে? নিচের stepper-এ একটি RISC-V load ধাপে ধাপে নিচে নামে আর ডেটা নিয়ে ওপরে ওঠে। সময়গুলো ধরে নেওয়া গোল সংখ্যা (L1 ৪, L2 ১২, L3 ৪০, DRAM ২০০ cycle, প্রতিটি স্তর একের পর এক দেখা হয়); বাস্তব chip-এ অনেক কাজ সমান্তরালে হয় আর সংখ্যা আলাদা।

কে কোন স্তর সামলায়, আর সীমানায় কত বড় টুকরো যায়

প্রতিটি সীমানায় ডেটা আসে-যায় একটি নির্দিষ্ট মাপের টুকরোয়। আর সিদ্ধান্ত নেয় আলাদা আলাদা “ব্যবস্থাপক”:

লক্ষ করুন, নিচে নামলে টুকরো বড় হয়। কারণ নিচের স্তরে একটি access শুরু করাই দামি (latency বেশি), কিন্তু শুরু হয়ে গেলে একসাথে অনেক byte আনা তুলনায় সস্তা। তাই বড় টুকরো আনা হয়, এই আশায় যে পাশের ডেটাও কাজে লাগবে — অর্থাৎ spatial locality-র ওপর বাজি।

Volatile আর non-volatile

আরেকটি বড় বিভাজন: বিদ্যুৎ চলে গেলে ডেটা থাকে কি না। Register, SRAM আর DRAM হলো volatile — লোডশেডিংয়ে কম্পিউটার বন্ধ হলে সব মুছে যায়। Flash (SSD, ফোনের storage, pen drive) আর HDD হলো non-volatile. তাই হায়ারার্কির একটি সীমারেখা হলো “কাজের জায়গা” আর “সংরক্ষণের জায়গা”: Word-এ লেখা ফাইল “Save” না করা পর্যন্ত DRAM-এই থাকে। অংশ ৮-এ দেখবেন, persistent memory এই রেখাটি মুছে ফেলার চেষ্টা করেছিল।

৪ · Locality — temporal আর spatial

হায়ারার্কি কাজ করবে কেবল তখনই, যদি বেশিরভাগ access ওপরের ছোট স্তরে মেটে। এটা কেন হয়? কারণ প্রোগ্রাম এলোমেলোভাবে মেমরি ছোঁয় না। প্রোগ্রামের এই স্বভাবের নাম locality of reference, আর এর দুটি রূপ:

সাধারণ কোডে locality কোথায় লুকিয়ে থাকে

int sum = 0;
for (int i = 0; i < n; i++)     /* i, n, sum: প্রতি পাকে ব্যবহার -> temporal       */
    sum += a[i];                /* a[0], a[1], ... পরপর ঠিকানা -> spatial          */
                                /* loop-এর ৪-৫টি instruction বারবার -> temporal    */
                                /* instruction-গুলো পরপর ঠিকানায় -> spatial         */

• Loop counter আর accumulator (i, sum): প্রতি পাকে পড়া আর লেখা — সবচেয়ে শক্তিশালী temporal locality. Compiler সাধারণত এগুলো register-এই রাখে।
• Array পরপর পড়া (a[i]): ৪ byte-এর int হলে একটি ৬৪ B block-এ ১৬টি উপাদান। প্রথমটিতে miss, পরের ১৫টিতে hit — miss rate ১ ÷ ১৬ = ৬.২৫%.
• Instruction fetch: loop-এর শরীর কয়েকটি instruction, প্রতি পাকে একই ঠিকানা থেকে আনা হয় (temporal), আর loop-এর বাইরেও instruction সাধারণত পরপর ঠিকানায় চলে, branch ছাড়া (spatial).
• Stack: পর্ব ৩০-এ দেখেছেন, function call-এ stack-এর শীর্ষে frame তৈরি হয় আর ফেরার সময় মোছে। পরপর call একই কয়েকশো byte বারবার ব্যবহার করে — temporal আর spatial দুটোই।

এবার একটি ছোট loop-কে cache-এর চোখে দেখা যাক। বোঝার সুবিধার জন্য এখানে block-কে ছোট ধরা হলো — ১৬ byte, অর্থাৎ ৪টি int (বাস্তবে সাধারণত ৬৪ B). Array a শুরু হয় ঠিকানা 0x1000-এ, আর শুরুতে cache খালি।

1int sum = 0;2for (int i = 0; i < 8; i++)3    sum += a[i];

কোডে locality চেনার উপায়

• ঠিকানা কীভাবে বদলায় দেখুন। a[i], i++ — stride ১ উপাদান: ভালো spatial. a[i * 16] (৪ B int-এ ৬৪ B লাফ) — প্রতি access নতুন block: spatial প্রায় শূন্য। a[rand()] — কোনো ধারা নেই।
• 2D array-র loop-এর ক্রম দেখুন। C-তে m[i][j] সারি ধরে (row-major) পাশাপাশি থাকে। ভেতরের loop যদি j হয়, পরপর ঠিকানা; যদি i হয়, প্রতিবার এক সারি সমান লাফ (পর্ব ৪৮-এ বিস্তারিত; C কোর্সের performance আর cache পর্বে হাতে-কলমে)।
• পুনর্ব্যবহারের দূরত্ব ভাবুন। একটি মান দুবার ব্যবহারের মাঝে আর কতগুলো আলাদা ডেটা ছোঁয়া হয়? দূরত্ব কম হলে temporal লাভ, বেশি হলে মাঝখানে ডেটা cache থেকে বেরিয়ে যায়। অংশ ৫-এ এটা মাপব।
• Pointer-এর পেছনে দৌড় সন্দেহ করুন। Linked list, tree, hash table-এ পরের ঠিকানা আগের ডেটার ভেতরে লেখা থাকে, আর node-গুলো মেমরির যেখানে-সেখানে — spatial locality দুর্বল।

৫ · Locality মাপা — reuse distance আর LRU stack

“এই কোডে locality ভালো” বলা সহজ, কিন্তু সংখ্যায় মাপা যায় কীভাবে? একটি সুন্দর মাপ হলো reuse distance (stack distance-ও বলা হয়): একটি block দ্বিতীয়বার চাওয়ার সময়, মাঝখানে আর কতগুলো আলাদা block ছোঁয়া হয়েছে। একই block পরপর দুবার চাইলে দূরত্ব ০; কখনো আগে না চাওয়া হলে দূরত্ব অসীম (cold).

যুক্তি। সব block-কে শেষ ব্যবহারের ক্রমে একটি তালিকায় (stack) সাজান — সবচেয়ে সাম্প্রতিকটি ওপরে, অবস্থান ০। প্রতিটি access-এ block-টি ওপরে উঠে আসে, আর তার ওপরে যারা ছিল তারা এক ধাপ নামে। LRU cache সব সময় ঠিক এই তালিকার ওপরের C-টি block ধরে রাখে। আরোহ পদ্ধতিতে এটি দেখানো যায়: শুরুতে দুটোই খালি; প্রতি access-এ ব্যবহৃত block দুই জায়গাতেই সবার ওপরে ওঠে, আর জায়গা লাগলে cache থেকে যে block বাদ পড়ে (সবচেয়ে আগে ব্যবহৃত), সেটিই তালিকার ওপরের C-টির ভেতর থেকে নিচে নেমে যায়। এখন block X-এর আগের access-এর পরে d-টি আলাদা block ছোঁয়া হলে X ঠিক অবস্থান d-তে থাকবে, কারণ শুধু ওই d-টি block তার ওপরে উঠেছে। অবস্থান d < C মানে X ওপরের C-টির মধ্যে, অর্থাৎ cache-এ: hit. d ≥ C হলে নেই: miss. একটি মজার ফল: একটি trace-এর reuse distance-এর histogram একবার বের করলেই সব মাপের LRU cache-এর hit rate একসাথে জানা যায়।

নিচের simulator পাঁচটি address trace তৈরি করে — প্রতিটি ৪ byte-এর int-এর ৬৪ KiB array (১০২৪টি block) নিয়ে — আর প্রতিটি access-এর reuse distance মেপে histogram ছাপে। শেষে তিন মাপের fully associative LRU cache-এ hit rate: ৮টি block (৫১২ B), ৬৪টি (৪ KiB) আর ৫১২টি (৩২ KiB).

// Locality analyser: reuse distance of 64-byte blocks in five address traces (4-byte ints)
const B = 64, N = 16384;                        // array of 16384 ints = 64 KiB = 1024 blocks
let seed = 12345; const rnd = n => Math.floor((seed = (Math.imul(seed, 1664525) + 1013904223) >>> 0) / 2 ** 32 * n);
const traces = {
  "sequential x2": [...Array(2 * N).keys()].map(i => (i % N) * 4),
  "stride 64 B x2": [...Array(2 * N / 16).keys()].map(i => (i * 16 % N) * 4),
  "random":        Array.from({ length: N }, () => rnd(N) * 4),
  "matrix rows":   [...Array(N).keys()].map(k => k * 4),                          // a[128][128], i outer
  "matrix cols":   [...Array(N).keys()].map(k => ((k % 128) * 128 + (k >> 7)) * 4) // j outer
};
const buckets = ["0", "1-7", "8-63", "64-511", "512+", "cold"];
const bucket = d => d < 0 ? 5 : d === 0 ? 0 : d < 8 ? 1 : d < 64 ? 2 : d < 512 ? 3 : 4;
console.log("trace           " + buckets.map(b => b.padStart(7)).join("") + "   hit% if LRU holds 8 / 64 / 512 blocks");
for (const [name, addrs] of Object.entries(traces)) {
  const stack = [], hist = [0, 0, 0, 0, 0, 0], hits = [0, 0, 0];   // stack[0] = most recently used block
  for (const a of addrs) {
    const blk = Math.floor(a / B), d = stack.indexOf(blk);       // d = distinct blocks used since last use
    hist[bucket(d)]++;
    [8, 64, 512].forEach((c, i) => { if (d >= 0 && d < c) hits[i]++; });
    if (d >= 0) stack.splice(d, 1);
    stack.unshift(blk);
  }
  const pct = x => (100 * x / addrs.length).toFixed(1);
  console.log(name.padEnd(16) + hist.map(h => String(h).padStart(7)).join("") + "   " + hits.map(pct).join(" / "));
}

trace                 0    1-7   8-63 64-511   512+   cold   hit% if LRU holds 8 / 64 / 512 blocks
sequential x2     30720      0      0      0   1024   1024   93.8 / 93.8 / 93.8
stride 64 B x2        0      0      0      0   1024   1024   0.0 / 0.0 / 0.0
random               14    112    878   7011   7345   1024   0.8 / 6.1 / 48.9
matrix rows       15360      0      0      0      0   1024   93.8 / 93.8 / 93.8
matrix cols           0      0      0  15360      0   1024   0.0 / 0.0 / 93.8

৬ · Hit, miss আর প্রত্যাশিত সময় — AMAT-এর প্রথম স্বাদ

এবার শব্দগুলো ঠিকঠাক সংজ্ঞায়িত করা যাক। পর্ব ৪৫ থেকে ৪৭ পর্যন্ত এই শব্দগুলোই বারবার আসবে।

দুই স্তরের প্রথম হিসাব

ধরুন একটি cache-এর hit time ৪ cycle, miss rate ৫%, আর miss হলে main memory থেকে block আনতে বাড়তি ১০০ cycle. প্রতি ১০০টি access-এর ৯৫টি ৪ cycle-এ শেষ। বাকি ৫টি-তে ৪ cycle খোঁজা (miss), তারপর ১০০ cycle — মোট ১০৪. গড় = (৯৫ × ৪ + ৫ × ১০৪) ÷ ১০০ = (৩৮০ + ৫২০) ÷ ১০০ = ৯ cycle. সংক্ষেপে:

Cache না থাকলে প্রতিটি access-এ ১০০ cycle-এর বেশি; cache থাকায় গড় ৯ — দশ গুণের বেশি লাভ। লক্ষ করুন, ৯ cycle-এর মধ্যে ৫ cycle এসেছে মাত্র ৫% miss থেকে। Miss rate ৫% থেকে ২% হলে AMAT = ৪ + ২ = ৬; অর্থাৎ hit rate-এ সামান্য উন্নতিও গড় সময়ে বড় পার্থক্য আনে।

অনেক স্তরের প্রত্যাশিত সময় — সূত্র আর প্রমাণ

এখন k-টি স্তর ধরুন: স্তর i-এর hit time t_i, আর local hit rate h_i (যত access স্তর i পর্যন্ত পৌঁছায়, তার মধ্যে কতগুলো সেখানে মেটে); শেষ স্তরে h_k = ১ — সব কিছু সেখানে আছে। ধরা যাক স্তরগুলো একের পর এক দেখা হয়।

প্রমাণ। প্রথম রূপটি প্রত্যাশিত মানের সংজ্ঞা: access-টি ঠিক একটি স্তরে মেটে, স্তর i-তে মেটার সম্ভাবনা f_i, আর তখন সে t_১ থেকে t_i সব খোঁজার সময় দিয়েছে। দ্বিতীয় রূপের জন্য যোগফলটি অন্যভাবে সাজান: t_j খরচটি দিতে হয় ঠিক তখনই, যখন access স্তর j পর্যন্ত পৌঁছায় — যার সম্ভাবনা r_j. তাই E[T] = Σ_j r_j t_j = t_১ + m_১t_২ + m_১m_২t_৩ + …, আর m_১, তারপর m_২ ইত্যাদি সাধারণ গুণনীয়ক হিসেবে বাইরে আনলেই nested রূপ। দুই স্তরে এটি t_১ + m_১t_২ — ঠিক AMAT, যেখানে miss penalty = t_২. তিন স্তরে AMAT = HT_L1 + MR_L1 × (HT_L2 + MR_L2 × MP_L2) — পর্ব ৪৭-এর multi-level সূত্র।

নিচের calculator তিনটি পরিস্থিতিতে এই হিসাব করে, স্তর ধরে ধরে: কোন স্তরে কত ভগ্নাংশ access মেটে, আর গড়ে কতটা সময় যোগ করে। সব সংখ্যা ধরে নেওয়া গোল মান (৩ GHz-এর cycle); বাস্তব chip-এ L2 আর L3-এর খোঁজা আংশিক সমান্তরাল হয়, আর DRAM-এর সময় অবস্থাভেদে বদলায়।

// Expected access time of a memory hierarchy (ASSUMED round numbers, cycles at 3 GHz; real chips differ)
function expected(name, levels) {
  console.log(`== ${name}`);
  console.log("level  hit time  local hit   served here   time to here   contribution");
  let reach = 1, path = 0, total = 0;            // reach = fraction of accesses that get this far
  for (const [lv, ht, hit] of levels) {
    path += ht;                                  // lookups are tried one after another
    const served = reach * hit, part = served * path;
    total += part;
    console.log(lv.padEnd(6) + String(ht).padStart(9) + (+(100 * hit).toFixed(4) + "%").padStart(11) +
      ((100 * served).toPrecision(4) + "%").padStart(14) + String(path).padStart(15) + part.toFixed(3).padStart(15));
    reach *= 1 - hit;
  }
  // the same answer written as nested AMAT: HT1 + MR1 x (HT2 + MR2 x (...))
  const nested = levels.reduceRight((acc, [, ht, hit]) => ht + (1 - hit) * acc, 0);
  console.log(`expected time = ${total.toFixed(3)} cycles (nested AMAT ${nested.toFixed(3)}) = ${(total / 3).toFixed(2)} ns`);
}
const base = [["L1", 4, 0.95], ["L2", 12, 0.6], ["L3", 40, 0.5], ["DRAM", 200, 1]];
expected("A: typical-looking program", base);
expected("B: L1 hit rate 98% instead of 95%", [["L1", 4, 0.98], ...base.slice(1)]);
expected("C: like A, but 1 access in 100,000 needs a page from SSD (50 us)",
  [...base.slice(0, 3), ["DRAM", 200, 1 - 1e-5 / 0.01], ["SSD", 150000, 1]]);

== A: typical-looking program
level  hit time  local hit   served here   time to here   contribution
L1            4        95%        95.00%              4          3.800
L2           12        60%        3.000%             16          0.480
L3           40        50%        1.000%             56          0.560
DRAM        200       100%        1.000%            256          2.560
expected time = 7.400 cycles (nested AMAT 7.400) = 2.47 ns
== B: L1 hit rate 98% instead of 95%
level  hit time  local hit   served here   time to here   contribution
L1            4        98%        98.00%              4          3.920
L2           12        60%        1.200%             16          0.192
L3           40        50%       0.4000%             56          0.224
DRAM        200       100%       0.4000%            256          1.024
expected time = 5.360 cycles (nested AMAT 5.360) = 1.79 ns
== C: like A, but 1 access in 100,000 needs a page from SSD (50 us)
level  hit time  local hit   served here   time to here   contribution
L1            4        95%        95.00%              4          3.800
L2           12        60%        3.000%             16          0.480
L3           40        50%        1.000%             56          0.560
DRAM        200      99.9%       0.9990%            256          2.557
SSD      150000       100%     0.001000%         150256          1.503
expected time = 8.900 cycles (nested AMAT 8.900) = 2.97 ns

Inclusion — ওপরের স্তরের সব কিছু কি নিচেও থাকে?

“প্রতিটি স্তর পরের স্তরের cache” কথাটি শুনে মনে হতে পারে, L1-এর প্রতিটি block L2-তেও আছে। এটি নকশার একটি সিদ্ধান্ত, প্রাকৃতিক নিয়ম নয়। Inclusive নীতিতে নিচের cache ওপরের সবের কপি রাখতে বাধ্য: L3 থেকে কিছু বাদ দিলে L1/L2 থেকেও বাদ দিতে হয়। সুবিধা — অন্য core জানতে চাইলে শুধু L3 দেখলেই চলে (পর্ব ৫৩-এর coherence-এ কাজে লাগে); অসুবিধা — একই ডেটা দুই জায়গায়, কার্যকর ধারণক্ষমতা কমে। Exclusive নীতিতে একটি block একসময়ে একটিই স্তরে; L1 থেকে বাদ পড়া block নিচে নামে (victim cache ধরনের), ধারণক্ষমতা পুরোটা কাজে লাগে, কিন্তু ব্যবস্থাপনা জটিল। মাঝামাঝি non-inclusive নীতিতে কোনো বাধ্যবাধকতা নেই। বিভিন্ন নির্মাতা আর প্রজন্ম ভিন্ন পথ নিয়েছে — যেমন Intel-এর অনেক পুরোনো desktop chip-এর L3 inclusive ছিল বলে জানা যায়, আর পরের কিছু server chip ও AMD-এর Zen-এর L3 non-inclusive বা victim-ধরনের; নির্দিষ্ট chip-এর জন্য নির্মাতার optimization manual দেখাই নিরাপদ।

৭ · নিজের চোখে দেখা — runner-এর cache আর staircase

এই কোর্সের C আর bash কোড চলে একটি shared virtual machine-এ। তার cache কত বড়? নিচের script শুধু cache-এর স্তর, ধরন, মাপ, line-এর মাপ আর associativity ছাপে — Linux-এর /sys থেকে আর getconf থেকে। CPU-র নাম, নির্মাতা বা যন্ত্রের পরিচয় ছাপা হয় না (মানগুলো থেকে অক্ষর-সংখ্যা ছাড়া সব বাদ দেওয়া হয়)।

# Cache levels, sizes and line size ONLY -- no CPU name, vendor, flags or host info
d=/sys/devices/system/cpu/cpu0/cache
if [ -d "$d" ]; then
    printf '%-7s %-12s %-6s %-9s %-5s\n' level type size line_B ways
    for i in "$d"/index*; do
        [ -r "$i/level" ] || continue
        v() { tr -cd 'A-Za-z0-9' < "$i/$1" 2>/dev/null || echo '?'; }
        printf 'L%-6s %-12s %-6s %-9s %-5s\n' "$(v level)" "$(v type)" "$(v size)" \
            "$(v coherency_line_size)" "$(v ways_of_associativity)"
    done
else
    echo "sysfs cache তথ্য নেই"
fi
echo "--- getconf ---"
if command -v getconf >/dev/null; then
    getconf -a 2>/dev/null | grep -E '^LEVEL[1-4]_(I|D)?CACHE_(SIZE|LINESIZE|ASSOC) ' \
        | awk '{ printf "%-24s %s\n", $1, ($2 == "" ? "?" : $2) }'
else
    echo "getconf নেই"
fi

level   type         size   line_B    ways 
L1      Data         32K    64        8    
L1      Instruction  32K    64        8    
L2      Unified      512K   64        8    
L3      Unified      16384K 64        16   
--- getconf ---
LEVEL1_ICACHE_SIZE       32768
LEVEL1_ICACHE_ASSOC      ?
LEVEL1_ICACHE_LINESIZE   64
LEVEL1_DCACHE_SIZE       32768
LEVEL1_DCACHE_ASSOC      8
LEVEL1_DCACHE_LINESIZE   64
LEVEL2_CACHE_SIZE        524288
LEVEL2_CACHE_ASSOC       8
LEVEL2_CACHE_LINESIZE    64
LEVEL3_CACHE_SIZE        16777216
LEVEL3_CACHE_ASSOC       16
LEVEL3_CACHE_LINESIZE    64
LEVEL4_CACHE_SIZE        0
LEVEL4_CACHE_ASSOC       ?
LEVEL4_CACHE_LINESIZE    ?

এবার মাপা যাক, array-র মাপ বাড়লে একটি access-এর সময় কীভাবে বদলায়। নিচের প্রোগ্রাম ১৬ KiB থেকে ৬৪ MiB পর্যন্ত array-তে একটি pointer chase চালায়: প্রতিটি ৬৪ B line-এ পরের line-এর ঠিকানা লেখা, তাই প্রতিটি load আগেরটির ফলের ওপর নির্ভরশীল — CPU একসাথে অনেকগুলো load পাঠিয়ে latency লুকাতে পারে না, আর আমরা সত্যিকারের latency দেখি। তিনটি ক্রম: seq — line-এর পর line; stride4K — প্রতিবার ৪ KiB লাফ (প্রতি access নতুন page); random — এলোমেলো একটি চক্র। Wandbox-এ প্রোগ্রাম -O0-তে compile হয়, তাই প্রতিটি পাকে loop-এর নিজের কয়েক ns খরচ যোগ হয়। সময় প্রতি run-এ আর যন্ত্রভেদে বদলায়।

// Pointer chase over arrays of growing size: ns per access (varies per run and machine)
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
#define LINE 16                       /* uint32_t per 64-byte line */
static double now(void) { struct timespec t; timespec_get(&t, TIME_UTC); return t.tv_sec * 1e9 + t.tv_nsec; }
static uint64_t rng = 88172645463325252u;
static uint32_t rnd(uint32_t n) { rng ^= rng << 13; rng ^= rng >> 7; rng ^= rng << 17; return (uint32_t)(rng % n); }
static double chase(uint32_t *a, uint32_t *ord, uint32_t n, long steps) {
    for (uint32_t k = 0; k < n; k++) a[ord[k] * LINE] = ord[(k + 1) % n] * LINE;   /* build the cycle */
    uint32_t p = 0;
    for (uint32_t k = 0; k < n; k++) p = a[p];                                    /* warm-up lap */
    double t0 = now();
    for (long s = 0; s < steps; s++) p = a[p];               /* each load needs the previous one */
    double t = now() - t0;
    return p == 1 ? -1 : t / steps;                          /* use p so it is not dropped */
}
int main(void) {
    uint32_t maxn = (64u << 20) / 64;                        /* lines in 64 MiB */
    uint32_t *a = malloc((size_t)maxn * 64), *ord = malloc(maxn * sizeof *ord);
    if (!a || !ord) { puts("out of memory"); return 1; }
    printf("%9s %8s %8s %8s   (ns per access)\n", "size", "seq", "stride4K", "random");
    for (uint32_t kib = 16; kib <= 65536; kib *= 4) {
        uint32_t n = kib * 1024 / 64, cols = n / 64; double r[3];
        for (int pat = 0; pat < 3; pat++) {
            for (uint32_t k = 0; k < n; k++)                 /* order in which lines are visited */
                ord[k] = pat == 0 ? k : pat == 1 ? (k % cols) * 64 + k / cols : k;
            if (pat == 2) for (uint32_t k = n - 1; k > 0; k--) { uint32_t j = rnd(k), t = ord[k]; ord[k] = ord[j]; ord[j] = t; }
            r[pat] = chase(a, ord, n, 3000000);
        }
        printf("%6u KiB %8.2f %8.2f %8.2f\n", kib, r[0], r[1], r[2]);
    }
    free(a); free(ord); return 0;
}

     size      seq stride4K   random   (ns per access)
    16 KiB     3.11     3.14     3.17
    64 KiB     3.46     6.25     6.08
   256 KiB     3.23     7.73     6.62
  1024 KiB     3.17     9.96    21.14
  4096 KiB     3.07    17.18    34.96
 16384 KiB     5.21    41.22   183.09
 65536 KiB     6.13    42.65   204.16

৮ · আধুনিক মোড় — scratchpad, HBM, CXL আর persistent memory

ক্লাসিক পিরামিড এখনো সত্য, কিন্তু কয়েকটি নতুন স্তর আর নতুন ধরনের ব্যবস্থাপনা যোগ হয়েছে:

• Scratchpad memory: chip-এর ভেতরের SRAM, কিন্তু cache নয় — hardware নিজে কিছু রাখে না বা বাদ দেয় না; প্রোগ্রাম (বা compiler) স্পষ্টভাবে ডেটা কপি করে আনে-নেয়। সুবিধা: সময় সম্পূর্ণ অনুমানযোগ্য (hit-miss-এর অনিশ্চয়তা নেই), tag রাখার জায়গা ও শক্তি লাগে না। তাই অনেক microcontroller, DSP আর real-time সিস্টেমে (পর্ব ৫৬) এটি প্রচলিত। GPU-তেও একই ভাবনা: NVIDIA-র CUDA-তে “shared memory” হলো প্রতি multiprocessor-এ প্রোগ্রামার-নিয়ন্ত্রিত দ্রুত মেমরি (পর্ব ৫৫).
• HBM (High Bandwidth Memory): কয়েকটি DRAM die একটির ওপর আরেকটি সাজিয়ে (stacked) processor-এর ঠিক পাশে, একটি silicon interposer-এ বসানো, হাজারের বেশি bit চওড়া সংযোগে। Latency খুব বেশি কমে না, কিন্তু bandwidth বিশাল — তাই আধুনিক GPU আর AI accelerator-এ প্রচলিত।
• CXL (Compute Express Link): PCIe-এর ভৌত সংযোগের ওপর চলা একটি মান (পর্ব ৫১), যার মাধ্যমে CPU বাইরের একটি card বা বাক্সের মেমরিকে প্রায় নিজের মেমরির মতো load/store দিয়ে ব্যবহার করতে পারে। এটি DRAM-এর নিচে একটি নতুন স্তর তৈরি করে — স্থানীয় DRAM-এর চেয়ে ধীর (অতিরিক্ত latency, নকশাভেদে মোটামুটি কয়েকশো ns-এর মাত্রায় বলে উল্লেখ পাওয়া যায়), কিন্তু অনেক বড় আর কয়েকটি server ভাগ করে নিতে পারে। প্রযুক্তিটি তুলনামূলক নতুন, ব্যবহার এখনো ছড়াচ্ছে।
• Persistent memory: এমন মেমরি যা DRAM-এর মতো byte ধরে load/store করা যায়, কিন্তু বিদ্যুৎ গেলেও ডেটা থাকে। সবচেয়ে পরিচিত উদাহরণ Intel Optane persistent memory (3D XPoint প্রযুক্তি), যা DRAM-এর slot-এ বসত; latency DRAM-এর চেয়ে বেশি, flash-এর চেয়ে অনেক কম। ২০২২ সালে Intel Optane ব্যবসা গুটিয়ে নেওয়ার ঘোষণা দেয়। ধারণাটি অবশ্য বেঁচে আছে — CXL-এর ওপর বা নতুন ধরনের মেমরি-প্রযুক্তিতে।

শেষে একটি সতর্কতা। Cache সাধারণত “অদৃশ্য” — প্রোগ্রাম ঠিক থাকে, শুধু গতি বদলায়। কিন্তু সময়ের পার্থক্য দেখা যায়, আর ঠিক এই পার্থক্যই side channel হতে পারে: একটি প্রোগ্রাম মেপে বুঝতে পারে অন্যটি কোন ডেটা ছুঁয়েছে। প্রতিরক্ষার কথা পর্ব ৪১-এ (Spectre, Meltdown) দেখেছেন।

৯ · AI-এর যুগে — মেমরি হায়ারার্কির প্রশ্নে AI, আর যাচাইয়ের অভ্যাস

মেমরি নিয়ে AI-এর উত্তর প্রায়ই আত্মবিশ্বাসী আর সংখ্যায় ভরা। সমস্যা হলো, সেই সংখ্যাগুলো প্রায়ই নির্দিষ্ট কোনো যন্ত্রের নয়, আর কখনো একেবারে বানানো:

AI-এর দেওয়া মেমরি-ব্যাখ্যা হাতে পেলে — চেকলিস্ট

• AMAT বা প্রত্যাশিত সময় হাতে বা একটি ছোট script-এ দুই পদ্ধতিতে আবার হিসাব করেছি
• Miss rate local না global, আর miss penalty-তে কী কী ধরা হয়েছে, তা পরিষ্কার করেছি
• Temporal আর spatial-এর উদাহরণ সংজ্ঞার সাথে মিলিয়েছি (একই ঠিকানা বনাম পাশের ঠিকানা)
• Latency আর cache-মাপের দাবি নিজের যন্ত্রের sysfs/lscpu বা নির্মাতার ডকুমেন্টেশনে যাচাই করেছি
• AI-এর benchmark কোডে নির্ভরশীল load আছে কি না, আর compiler loop মুছে দেয় কি না, দেখেছি; কয়েকবার চালিয়ে ফল তুলনা করেছি