Cache-এর পারফরম্যান্স — write policy, AMAT আর multi-level cache

১ · Store এলে কী হবে — write-through, write buffer আর write-back

পর্ব ৪৫-এ direct-mapped cache আর পর্ব ৪৬-এ set-associative cache ও replacement দেখেছেন। সেখানে মূলত পড়ার (load) গল্প ছিল: address-কে | tag | index | block offset | ভাগে ভেঙে খোঁজা, hit হলে ডেটা, miss হলে নিচের স্তর থেকে পুরো block আনা। এই পর্বে দুটি নতুন প্রশ্ন। এক, লেখার (store) সময় কী হবে? দুই, এই সব hit আর miss মিলে প্রোগ্রাম আসলে কতটা ধীর হয় — সংখ্যায়?

পড়ার সময় cache আর মেমরিতে একই মান থাকে, তাই সমস্যা নেই। কিন্তু cache-এ থাকা কোনো block-এ store লিখলে cache-এর কপি নতুন, আর মেমরির কপি পুরোনো হয়ে যায়। দুই কপি কখন আর কীভাবে আবার মেলানো হবে — এই সিদ্ধান্তই write policy.

Write-through — প্রতিটি store নিচেও যায়

Write-through নীতিতে store hit হলে cache-এর word বদলায়, আর একই সাথে লেখাটি নিচের স্তরেও (L2 বা মেমরি) পাঠানো হয়। সুবিধা: cache আর নিচের স্তর সবসময় মেলে, তাই কোনো block বের করে দিলে কিছু লিখতে হয় না, আর নকশা সরল। অসুবিধা: প্রতিটি store নিচে যায়। প্রোগ্রামে প্রায় ১০% instruction store হলে আর মেমরিতে একটি লেখা ১০০ cycle নিলে, প্রতিটি store-এ অপেক্ষা করলে CPI-তে যোগ হতো ০.১ × ১০০ = ১০ cycle — অসম্ভব রকম ধীর।

তাই write-through প্রায় সবসময় একটি write buffer-এর সাথে আসে: কয়েকটি entry-র ছোট একটি সারি, যেখানে store-এর ঠিকানা আর ডেটা রেখে দিয়ে CPU সাথে সাথে এগিয়ে যায়। Buffer নিজে ধীরে ধীরে নিচের স্তরে লিখতে থাকে। CPU থামে কেবল তখন, যখন buffer পুরো ভরা। এখানে একটি সহজ হিসাব খুব কাজের:

অনেক write buffer আরেকটি কৌশল নেয় — write merging: একই block-এর পরপর কয়েকটি store একটি entry-তে জুড়ে দেয়, যাতে নিচে একটি বড় লেখা যায়, অনেক ছোট লেখার বদলে।

Write-back আর dirty bit — শুধু cache-এ লেখা, পরে একবারে

Write-back নীতিতে store hit হলে শুধু cache-এর word বদলায়; নিচের স্তর ছোঁয়া হয় না। প্রতিটি line-এ valid bit-এর পাশে একটি বাড়তি bit থাকে — dirty bit. Store এলে dirty = 1. পরে কোনো miss-এর কারণে এই line সরাতে (evict) হলে দেখা হয়: dirty = 0 হলে line-টি নিচের স্তরের সাথে হুবহু মেলে, শুধু ফেলে দিলেই চলে; dirty = 1 হলে পুরো block নিচে লিখে (write back) তারপর নতুন block আনা হয়।

লাভটা আসে বারবার লেখা থেকে। একটি লুপে একটি যোগফলের চলক ৬৪ বার লেখা হলে write-through নিচে ৬৪টি লেখা পাঠায়, write-back পাঠায় শেষে একটি block. অংশ ২-এর simulator ঠিক এই তুলনাটি গুনে দেখাবে। দাম: প্রতি line-এ একটি বাড়তি bit, miss-এর সময় বাড়তি একটি block-লেখার সম্ভাবনা (অংশ ২-এর শেষে হিসাব), আর এক মুহূর্তে মেমরির কপি পুরোনো থাকা — যা একাধিক core বা DMA থাকলে coherence-এর প্রশ্ন তোলে (পর্ব ৫২ আর ৫৩).

২ · Write miss — block আনবেন, নাকি না? আর dirty eviction-এর দাম

এবার store এমন ঠিকানায়, যার block cache-এ নেই — write miss. দুটি পথ:

যেকোনো জুটি সম্ভব, কিন্তু দুটি জুটি স্বাভাবিকভাবে মেলে, আর পাঠ্যবইও এই দুটিই ধরে (এই কোর্সের Module 8-এর সব পর্বেও তাই):

• Write-back + write-allocate: block একবার এনে রাখলে পরের সব store cache-এই জমে, dirty bit শেষে একবার লেখায়। লেখা বারবার একই block-এ হলে এটাই সবচেয়ে সাশ্রয়ী। আজকের বেশিরভাগ L1 data cache, L2 আর L3 এই ধাঁচের বলে সাধারণভাবে বর্ণিত।
• Write-through + no-write-allocate: store তো এমনিই নিচে যাবে; block এনে লাভ কেবল যদি পরে পড়া হয়। তাই block না এনে শুধু নিচে লেখা।

Write-back + write-allocate-এ একটি write miss-এর পুরো ধাপগুলো হলো: tag মেলানো, মিলল না; সরানোর জন্য বাছা line (victim) dirty হলে তাকে নিচে লেখা; নতুন block নিচ থেকে আনা, tag আর valid বসানো; তারপর store-এর word মিশিয়ে dirty = 1. নিচের stepper-এ একটি ছোট direct-mapped cache-এ এটি ধাপে ধাপে দেখুন।

32-bit address:  │ tag: 26 bit │ index: 2 bit │ offset: 4 bit │

0x200 = ...0010 0000 0000  →  tag 0x8, index 0, offset 0
0x204                      →  tag 0x8, index 0, offset 4
0x300 = ...0011 0000 0000  →  tag 0xC, index 0, offset 0

line  V  D  tag
 0    0  0  —
 1    0  0  —
 2    0  0  —
 3    0  0  —        মেমরি-লেখা: 0   block-পড়া: 0

index 0 → V = 0  →  MISS
victim dirty? না (খালি line)
মেমরি থেকে block 0x200–0x20F আনা হলো

line  V  D  tag
 0    1  0  0x8     ← block 0x200
 1    0  0  —
 2    0  0  —
 3    0  0  —        মেমরি-লেখা: 0   block-পড়া: 1

store 0x204: index 0, tag 0x8 = 0x8  →  HIT
   word বদলাল শুধু cache-এ, D = 1
store 0x208: index 0, tag 0x8        →  HIT
   আবার শুধু cache-এ, D আগেই 1

line  V  D  tag
 0    1  1  0x8     ← dirty: মেমরির কপি পুরোনো
 1    0  0  —
 2    0  0  —
 3    0  0  —        মেমরি-লেখা: 0   block-পড়া: 1

index 0, tag 0xC ≠ 0x8  →  MISS
victim (block 0x200) dirty = 1
   ① block 0x200–0x20F মেমরিতে লেখা   (write back)
   ② block 0x300–0x30F মেমরি থেকে আনা (write-allocate)
   ③ store-এর word মেশানো, D = 1

line  V  D  tag
 0    1  1  0xC     ← block 0x300
 1    0  0  —
 2    0  0  —
 3    0  0  —        মেমরি-লেখা: 1 block   block-পড়া: 2

index 0, tag 0x8 ≠ 0xC  →  MISS
victim (block 0x300) dirty = 1
   ① block 0x300–0x30F মেমরিতে লেখা
   ② block 0x200–0x20F আনা — access ২–৩-এর নতুন মানসহ,
      কারণ access ৪-এ সেগুলো মেমরিতে লেখা হয়ে গেছে

line  V  D  tag
 0    1  0  0x8     ← clean
 1    0  0  —
 2    0  0  —
 3    0  0  —        মেমরি-লেখা: 2 block   block-পড়া: 3

                     WB + WA        WT + NWA
hit                  2              3
block-পড়া            3              1
মেমরি-লেখা           2 block        3 word
                     (32 byte)      (12 byte)

WT + NWA-তে: store 0x204, 0x208 hit (cache আর মেমরি
দুটোতেই লেখা), store 0x300 miss → শুধু মেমরিতে, cache-এ
কিছু বসে না; তাই শেষের load 0x204 HIT.

Simulator — দুই নীতি, দুই ধরনের লুপ

এবার একটি ছোট 2-way set-associative cache (২টি set × ২টি way, ১৬ byte block, LRU) নিয়ে দুটি লুপের মেমরি-ট্রাফিক গুনে দেখি। প্রথম লুপ sum += a[i]: array পড়া হয়, আর sum চলকটি মেমরিতে (ঠিকানা 0x130) প্রতিবার লেখা হয় — optimization ছাড়া compile করা কোডে এমনটাই হয়। দ্বিতীয় লুপ b[i] = a[i]: একটি array থেকে আরেকটিতে কপি। দুটিতেই ৬৪টি iteration. শেষে cache-এ যে dirty line থেকে যায়, সেগুলোও একসময় লিখতেই হবে, তাই তাদের “flush” হিসেবে লেখার byte-এ যোগ করা হয়েছে।

// Write policies on two traces: 2-way set-associative, 2 sets, 16-byte blocks, LRU, 4-byte words
const SETS = 2, WAYS = 2, BLOCK = 16, WORD = 4, N = 64;
const sumLoop = [], copyLoop = [];               // sum += a[i]  and  b[i] = a[i]
for (let i = 0; i < N; i++) {
  sumLoop.push(["R", 0x200 + 4 * i], ["W", 0x130]);
  copyLoop.push(["R", 0x200 + 4 * i], ["W", 0x800 + 4 * i]);
}
function run(trace, wb) {                       // wb=true: WB+WA, wb=false: WT+NWA
  const sets = Array.from({ length: SETS }, () => []);   // each set: [{blk, dirty}], MRU last
  const c = { hit: 0, rd: 0, ww: 0, wbk: 0 };
  for (const [op, a] of trace) {
    const blk = Math.floor(a / BLOCK), s = sets[blk % SETS];
    const k = s.findIndex(l => l.blk === blk);
    let line = k >= 0 ? s.splice(k, 1)[0] : null; // remove, re-insert as MRU
    if (line) c.hit++;
    if (op === "W" && !wb) { c.ww++; if (line) s.push(line); continue; } // WT: store goes to memory
    if (!line) {                                   // miss: allocate (read miss, or WB write miss)
      if (s.length === WAYS && s.shift().dirty) c.wbk++;  // evict LRU, write back if dirty
      line = { blk, dirty: false }; c.rd++;
    }
    if (op === "W") line.dirty = true;             // WB: write stays in cache
    s.push(line);
  }
  const left = sets.flat().filter(l => l.dirty).length;    // must be written back later
  return { ...c, left, readB: c.rd * BLOCK, writeB: c.ww * WORD + (c.wbk + left) * BLOCK };
}
console.log(`N = ${N} iterations; bytes-written includes the final flush of dirty lines`);
console.log("trace  policy   hits  block-reads  word-writes  writebacks+flush  bytes-read  bytes-written");
for (const [name, t] of [["sum", sumLoop], ["copy", copyLoop]]) for (const wb of [false, true]) {
  const s = run(t, wb);
  console.log(`${name.padEnd(6)} ${wb ? "WB+WA " : "WT+NWA"} ${String(s.hit).padStart(5)} ${String(s.rd).padStart(12)}` +
    ` ${String(s.ww).padStart(12)} ${(s.wbk + "+" + s.left).padStart(17)} ${String(s.readB).padStart(11)} ${String(s.writeB).padStart(14)}`);
}

N = 64 iterations; bytes-written includes the final flush of dirty lines
trace  policy   hits  block-reads  word-writes  writebacks+flush  bytes-read  bytes-written
sum    WT+NWA    48           16           64               0+0         256            256
sum    WB+WA    111           17            0               0+1         272             16
copy   WT+NWA    48           16           64               0+0         256            256
copy   WB+WA     96           32            0              14+2         512            256

Dirty eviction-এর দাম miss penalty-তে

Write-back-এ একটি miss যদি dirty line সরায়, তাহলে নতুন block আনার আগে পুরোনোটি লিখতে হয়। ধরুন একটি clean miss-এর miss penalty ১০০ cycle, আর পুরো block লেখাও ১০০ cycle. যদি সরানো line-গুলোর ৩০% dirty হয়, আর লেখা আর পড়া একটির পর একটি হয়, তাহলে গড় miss penalty = ১০০ + ০.৩ × ১০০ = ১৩০ cycle. ১ cycle-এর hit আর ৫% miss rate ধরলে AMAT (অংশ ৩-এ সংজ্ঞা) ১ + ০.০৫ × ১০০ = ৬ cycle থেকে বেড়ে ১ + ০.০৫ × ১৩০ = ৭.৫ cycle.

সমাধান: write-back buffer (victim buffer) — dirty victim-কে প্রথমে একটি ছোট buffer-এ সরিয়ে রেখে নতুন block-এর পড়া আগে শুরু করা, আর buffer-টি পরে ফাঁকা সময়ে লেখা। তখন miss penalty আবার প্রায় ১০০ cycle-এ নামে — যতক্ষণ buffer ভরে না যায়। Write-through-এর write buffer-এর মতোই নিয়ম: buffer ক্ষণিকের চাপ লুকায়, গড় হার লুকাতে পারে না।

৩ · পারফরম্যান্সের সমীকরণ — memory stall cycle, CPI আর AMAT

পর্ব ০৩-এ CPU time-এর মূল সূত্র দেখেছেন: CPU time = instruction count × CPI × clock cycle time. সেখানে CPI ধরা হয়েছিল একটি সংখ্যা। কিন্তু সেই CPI-এর ভেতরে দুটি অংশ লুকিয়ে আছে — CPU-র নিজের কাজের cycle, আর মেমরির জন্য দাঁড়িয়ে থাকার cycle. প্রথমটিকে বলি CPI_base (সব access cache-এ hit হলে যা হতো; hit time এর ভেতরেই ধরা), দ্বিতীয়টি memory stall cycle.

সূত্রটি কোথা থেকে আসে — একটি ছোট প্রমাণ

একটি প্রোগ্রামে IC সংখ্যক instruction. প্রতিটি instruction গড়ে A বার মেমরিতে যায় (instruction fetch আর load/store মিলিয়ে)। তাহলে মোট access = IC × A. এদের মধ্যে miss rate অনুপাতে miss — মোট miss = IC × A × miss rate. ধরে নিই (সরল in-order মডেলে) প্রতিটি miss-এ CPU পুরো miss penalty সময় দাঁড়িয়ে থাকে, আর miss-গুলো একটির ওপর আরেকটি পড়ে না। তাহলে:

দুই দিককে IC দিয়ে ভাগ করলে পাই প্রতি instruction-এ stall, আর CPU-র cycle-এর সাথে যোগ করলে:

Instruction cache আর data cache আলাদা হলে (split cache — পর্ব ৩৬-এ structural hazard এড়ানোর প্রসঙ্গে দেখেছেন) দুটি পদ আলাদা লেখা হয়: প্রতিটি instruction ঠিক একবার fetch হয়, তাই I-cache-এর A = ১; আর D-cache-এ A = load/store-এর অনুপাত। দুটি অনুমান মনে রাখবেন: miss penalty সব miss-এ সমান, আর miss চলাকালীন CPU কিছুই করে না। দ্বিতীয় অনুমানটি অংশ ৬-এ ভাঙব।

ক্লাসিক numerical (ক) — perfect cache কত দ্রুত?

প্রশ্ন: I-cache miss rate ২%, D-cache miss rate ৪%, miss penalty ১০০ cycle, CPI_base ২, আর ৩৬% instruction load বা store. Stall-সহ CPI কত, আর সব hit হলে (perfect cache) প্রসেসর কত গুণ দ্রুত হতো? নিচের stepper-এ হিসাবটি ধাপে ধাপে।

CPI_base          = 2
I-cache miss rate = 2%   = 0.02
D-cache miss rate = 4%   = 0.04
miss penalty      = 100 cycle
load/store        = 36%  = 0.36 per instruction
I-fetch           = 1    per instruction (সবসময়)

I-stall / instr = (I-access / instr) × miss rate × penalty
                = 1 × 0.02 × 100
                = 2.00 cycle

D-stall / instr = (D-access / instr) × miss rate × penalty
                = 0.36 × 0.04 × 100
                = 1.44 cycle

CPI = CPI_base + I-stall + D-stall
    = 2 + 2.00 + 1.44
    = 5.44

মোট সময়ের 3.44 / 5.44 ≈ 63% শুধু মেমরির অপেক্ষা

একই IC, একই clock — তাই সময়ের অনুপাত = CPI-এর অনুপাত

speedup = CPI_stall / CPI_perfect
        = 5.44 / 2
        = 2.72 গুণ

ক্লাসিক numerical (খ) — clock দ্বিগুণ করলে কী হয়?

এবার একই প্রসেসরের clock rate দ্বিগুণ করা হলো, কিন্তু মেমরি একই। মেমরির latency ন্যানোসেকেন্ডে অপরিবর্তিত, কিন্তু cycle এখন অর্ধেক লম্বা, তাই একই সময়ে দ্বিগুণ cycle — miss penalty ২০০ cycle. নতুন CPI = ২ + ১ × ০.০২ × ২০০ + ০.৩৬ × ০.০৪ × ২০০ = ২ + ৪ + ২.৮৮ = ৮.৮৮. CPU time-এর অনুপাত:

Clock দ্বিগুণ, অথচ CPU মাত্র প্রায় ১.২৩ গুণ দ্রুত। কারণ সময়ের যে অংশ মেমরির অপেক্ষা, সেটি clock-এর সাথে একটুও কমেনি — এটা পর্ব ০৩-এর Amdahl-এর সূত্র, শুধু মেমরির রূপে। এই প্রবণতারই নাম memory wall (পর্ব ৪৪).

AMAT — গড়ে একটি মেমরি access কত সময় নেয়

শুধু cache-এর নকশা তুলনা করতে চাইলে পুরো CPI লাগে না; একটি সরল মাপকাঠি যথেষ্ট — AMAT (average memory access time):

যুক্তি: প্রতিটি access-এ আগে cache দেখতেই হয় (hit time, hit হোক বা miss); তারপর miss rate অনুপাতে access-কে বাড়তি miss penalty দিতে হয়। উদাহরণ: hit time ১ cycle, miss rate ৫%, miss penalty ২০ cycle → AMAT = ১ + ০.০৫ × ২০ = ২ cycle. AMAT cycle-এ বা ন্যানোসেকেন্ডে — যেকোনো এককে লেখা যায়, শুধু তিনটি পদ একই এককে থাকতে হয়। আর মনে রাখবেন: একটি cache-এর miss rate কম কিন্তু hit time বেশি হলে AMAT খারাপও হতে পারে — তুলনা সবসময় পুরো সূত্রে।

নিচের calculator ঠিক এই হিসাবগুলো — (ক), (খ), AMAT আর পরের অংশের L2-এর উদাহরণ — প্রতিটি মধ্যবর্তী সংখ্যাসহ ছাপায়:

// CPI with memory stalls + AMAT: the classic textbook numericals, every step printed
const r = (x, d = 4) => +x.toFixed(d);
function cpiWithStalls(name, base, pen, iMiss, dMiss, ldst) {
  const iSt = 1 * iMiss * pen;            // every instruction is fetched: 1 I-access / instr
  const dSt = ldst * dMiss * pen;         // only loads/stores access the D-cache
  const cpi = base + iSt + dSt;
  console.log(`${name}: I-stall = 1 x ${iMiss} x ${pen} = ${r(iSt)}, D-stall = ${ldst} x ${dMiss} x ${pen} = ${r(dSt)}`);
  console.log(`   CPI = ${base} + ${r(iSt)} + ${r(dSt)} = ${r(cpi)};  perfect cache is ${r(cpi / base)}x faster`);
  return cpi;
}
const A = cpiWithStalls("(a) penalty 100", 2, 100, 0.02, 0.04, 0.36);
const B = cpiWithStalls("(b) penalty 200", 2, 200, 0.02, 0.04, 0.36);
// time = IC x CPI x cycle time; (b) has half the cycle time
console.log(`(b) vs (a): time ratio = (${r(A)} x 1) / (${r(B)} x 0.5) = ${r(A / (B * 0.5), 3)}x  (not 2x)`);

const amat = (ht, mr, mp) => ht + mr * mp;
console.log(`AMAT = 1 + 0.05 x 20 = ${amat(1, 0.05, 20)} cycles`);

// Two levels: base CPI 1, 4 GHz, L1 misses/instr 2%, memory 100 ns, L2 5 ns, global L2 miss 0.5%
const ghz = 4, cyc = ns => ns * ghz;     // ns -> cycles
const mem = cyc(100), l2 = cyc(5);
const cpi1 = 1 + 0.02 * mem;
const cpi2 = 1 + 0.02 * l2 + 0.005 * mem;
console.log(`memory = 100 ns x ${ghz} GHz = ${mem} cycles, L2 = 5 ns = ${l2} cycles`);
console.log(`L1 only : CPI = 1 + 0.02 x ${mem} = ${r(cpi1)}`);
console.log(`L1 + L2 : CPI = 1 + 0.02 x ${l2} + 0.005 x ${mem} = ${r(cpi2)}`);
const local = 0.005 / 0.02;
console.log(`L2 local miss rate = 0.005 / 0.02 = ${local}; check: 0.02 x (${l2} + ${local} x ${mem}) = ${r(0.02 * (l2 + local * mem))} stall cycles`);
console.log(`speedup from L2 = ${r(cpi1)} / ${r(cpi2)} = ${r(cpi1 / cpi2, 3)}x`);

(a) penalty 100: I-stall = 1 x 0.02 x 100 = 2, D-stall = 0.36 x 0.04 x 100 = 1.44
   CPI = 2 + 2 + 1.44 = 5.44;  perfect cache is 2.72x faster
(b) penalty 200: I-stall = 1 x 0.02 x 200 = 4, D-stall = 0.36 x 0.04 x 200 = 2.88
   CPI = 2 + 4 + 2.88 = 8.88;  perfect cache is 4.44x faster
(b) vs (a): time ratio = (5.44 x 1) / (8.88 x 0.5) = 1.225x  (not 2x)
AMAT = 1 + 0.05 x 20 = 2 cycles
memory = 100 ns x 4 GHz = 400 cycles, L2 = 5 ns = 20 cycles
L1 only : CPI = 1 + 0.02 x 400 = 9
L1 + L2 : CPI = 1 + 0.02 x 20 + 0.005 x 400 = 3.4
L2 local miss rate = 0.005 / 0.02 = 0.25; check: 0.02 x (20 + 0.25 x 400) = 2.4 stall cycles
speedup from L2 = 9 / 3.4 = 2.647x

৪ · Multi-level cache — L2, L3, local আর global miss rate

(খ)-এর শিক্ষা: CPU আর মেমরির ফারাক যত বাড়ে, miss penalty তত বড়। L1-কে আরও বড় করলে miss কমে, কিন্তু বড় cache ধীর — L1-এর hit time প্রতিটি load-এর গতি ঠিক করে, তাই সেটি বাড়ানো যায় না। সমাধান: L1 ছোট আর দ্রুত রেখে তার পেছনে আরেকটি বড়, একটু ধীর cache বসানো — L2 cache. L1-এর miss এখন মেমরিতে না গিয়ে প্রথমে L2-তে যায়; অর্থাৎ L2-র কাজ হলো L1-এর miss penalty কমানো. তার পেছনে প্রায়ই সব core-এর ভাগাভাগি করা L3 (last-level cache) — এটাই multi-level cache.

দুই স্তরের AMAT আর local বনাম global miss rate

L1-এর miss penalty এখন নিজেই একটি ছোট AMAT — L2-এর hit time আর L2-এর miss-এর দাম মিলিয়ে:

এখানে MR_L2 একটি local miss rate: L2-তে যত access পৌঁছায়, তার কত অংশ miss. আর global miss rate হলো CPU-র মোট access-এর কত অংশ L2-তেও miss করে মেমরিতে যায় = MR_L1 × MR_L2(local). L2-এর local miss rate প্রায়ই চোখে “খারাপ” দেখায় (২৫–৫০% হতেই পারে), কারণ সহজ access-গুলো L1-ই ছেঁকে নিয়েছে, L2-এর ভাগে শুধু কঠিনগুলো। তাই L2-এর মান বিচার করতে global miss rate-ই বেশি অর্থবহ।

পাঠ্যবইয়ের উদাহরণ — L2 যোগ করলে কত লাভ

একটি প্রসেসর: CPI_base ১, clock ৪ GHz, প্রতি instruction-এ L1 miss ২% (miss rate এখানে instruction প্রতি দেওয়া), main memory-র access time ১০০ ns (সব miss-এ সমান)। এবার একটি L2 যোগ: hit time ৫ ns, আর L2 যোগের পর মেমরিতে যাওয়ার global miss rate ০.৫%. প্রথমে ns-কে cycle-এ: ৪ GHz মানে এক cycle ০.২৫ ns, তাই ১০০ ns = ৪০০ cycle, ৫ ns = ২০ cycle.

• শুধু L1: CPI = ১ + ০.০২ × ৪০০ = ৯.
• L1 + L2: প্রতিটি L1 miss ২০ cycle-এ L2 দেখে; global ০.৫% access আরও ৪০০ cycle নেয়। CPI = ১ + ০.০২ × ২০ + ০.০০৫ × ৪০০ = ১ + ০.৪ + ২.০ = ৩.৪.
• Local miss rate দিয়ে যাচাই: L2-এর local miss rate = ০.০০৫ / ০.০২ = ২৫%. প্রতি L1 miss-এর গড় দাম = ২০ + ০.২৫ × ৪০০ = ১২০ cycle; প্রতি instruction-এ ০.০২ × ১২০ = ২.৪ — একই ফল, কারণ ১ + ২.৪ = ৩.৪.
• Speedup: ৯ / ৩.৪ ≈ ২.৬ গুণ (calculator-এ ২.৬৪৭)।

নিচের stepper-এ এই উদাহরণের একটি load দেখুন যেটি L1-এ আর L2-তেও miss করে।

তিন স্তর আর একটি explorer

তিন স্তরে সূত্রটি আরেক ধাপ ভেতরে যায়: AMAT = HT_L1 + MR_L1 × (HT_L2 + MR_L2 × (HT_L3 + MR_L3 × MP_mem)), প্রতিটি MR local. নিচের explorer-এ L2-এর আকার বদলালে কী হয় তা দেখুন। সব সংখ্যা শেখানোর জন্য ধরে নেওয়া — কোনো নির্দিষ্ট chip-এর নয়; ধারা বোঝানোই উদ্দেশ্য: বড় L2-এর miss কম কিন্তু hit একটু ধীর।

// Multi-level AMAT explorer. ALL numbers below are ASSUMED teaching values, not a real chip.
const L1 = { ht: 4, mr: 0.05 };             // L1: hit time 4 cycles, miss rate 5%
const MEM = 200;                            // main memory: 200 cycles
const L2 = [                                // assumed: bigger L2 -> lower local miss rate, slower hit
  { size: "256 KiB", ht: 10, mr: 0.50 }, { size: "512 KiB", ht: 11, mr: 0.40 },
  { size: "1 MiB", ht: 12, mr: 0.30 }, { size: "2 MiB", ht: 14, mr: 0.25 }, { size: "4 MiB", ht: 16, mr: 0.20 }];
const f = x => x.toFixed(2).padStart(6);
const noL2 = L1.ht + L1.mr * MEM;
console.log(`L1 only: AMAT = ${L1.ht} + ${L1.mr} x ${MEM} = ${noL2.toFixed(2)} cycles`);
console.log("L2 size   HT  local MR  global MR  L1 miss penalty   AMAT  speedup vs L1-only");
for (const c of L2) {
  const pen = c.ht + c.mr * MEM;             // what an L1 miss now costs
  const amat = L1.ht + L1.mr * pen;
  console.log(`${c.size.padEnd(8)} ${String(c.ht).padStart(3)} ${f(c.mr * 100)}%   ${f(L1.mr * c.mr * 100)}%` +
    `   ${f(pen).padStart(14)}   ${f(amat)}   ${(noL2 / amat).toFixed(2)}x`);
}
// add an L3 behind the 1 MiB L2 (assumed: 40-cycle hit, 20% local miss rate)
const L3 = { ht: 40, mr: 0.20 }, m = L2[2];
const l3pen = L3.ht + L3.mr * MEM, l2pen = m.ht + m.mr * l3pen, amat3 = L1.ht + L1.mr * l2pen;
console.log(`3 levels: AMAT = ${L1.ht} + ${L1.mr} x (${m.ht} + ${m.mr} x (${L3.ht} + ${L3.mr} x ${MEM}))`);
console.log(`        = ${L1.ht} + ${L1.mr} x (${m.ht} + ${m.mr} x ${l3pen}) = ${L1.ht} + ${L1.mr} x ${l2pen.toFixed(1)} = ${amat3.toFixed(2)} cycles`);
console.log(`global miss rates: L1 ${(L1.mr * 100).toFixed(1)}%, L2 ${(L1.mr * m.mr * 100).toFixed(1)}%, L3 ${(L1.mr * m.mr * L3.mr * 100).toFixed(2)}%`);

L1 only: AMAT = 4 + 0.05 x 200 = 14.00 cycles
L2 size   HT  local MR  global MR  L1 miss penalty   AMAT  speedup vs L1-only
256 KiB   10  50.00%     2.50%           110.00     9.50   1.47x
512 KiB   11  40.00%     2.00%            91.00     8.55   1.64x
1 MiB     12  30.00%     1.50%            72.00     7.60   1.84x
2 MiB     14  25.00%     1.25%            64.00     7.20   1.94x
4 MiB     16  20.00%     1.00%            56.00     6.80   2.06x
3 levels: AMAT = 4 + 0.05 x (12 + 0.3 x (40 + 0.2 x 200))
        = 4 + 0.05 x (12 + 0.3 x 80) = 4 + 0.05 x 36.0 = 5.80 cycles
global miss rates: L1 5.0%, L2 1.5%, L3 0.30%

প্রতিটি স্তরের নকশার লক্ষ্য আলাদা

এ কারণেই L1-এ hit time বাঁচাতে কখনো কম associativity মেনে নেওয়া হয়, অথচ L2-তে miss কমাতে বেশি associativity আর বড় আকার — কারণ L2-এর hit time প্রতিটি access-এ নয়, শুধু L1 miss-এ লাগে।

Inclusive, exclusive আর NINE

বাইরের স্তরে কী থাকবে, সেটিও একটি নকশা-সিদ্ধান্ত:

• Inclusive: ভেতরের স্তরের (L1, L2) সব block বাইরের স্তরেও (L3) থাকবেই। সুবিধা: অন্য core-এর coherence-প্রশ্নের উত্তর L3 দেখেই দেওয়া যায় — L3-এ না থাকলে কোনো L1-এও নেই (পর্ব ৫৩). দাম: একই ডেটা দুই জায়গায়, তাই কার্যকর ধারণক্ষমতা কম; আর L3 থেকে কোনো block সরালে ভেতরের কপিও বাতিল করতে হয় (back-invalidation).
• Exclusive: একটি block একসাথে L2 বা L3 — যেকোনো একটিতে। L2 থেকে সরানো block L3-এ যায় (L3 যেন একটি victim cache). মোট ধারণক্ষমতা L2 + L3-এর যোগফল, কিন্তু block দুই স্তরে আদান-প্রদানের ট্রাফিক বেশি।
• NINE (non-inclusive non-exclusive): কোনো নিয়মই জোর করা হয় না — block থাকতেও পারে, না-ও পারে।

বাস্তব chip-এ কোনটি, তা প্রজন্মভেদে বদলেছে। Intel-এর অনেক পুরোনো desktop প্রজন্মের L3 inclusive বলে ব্যাপকভাবে বর্ণিত, আর পরের কিছু server প্রজন্মে non-inclusive-এ সরে যাওয়ার কথা জানা যায়; AMD-এর Zen-ধাঁচের core-এ L3 মূলত L2-এর victim cache হিসেবে কাজ করে বলে বর্ণিত। নির্দিষ্ট প্রজন্মের জন্য নির্মাতার optimization manual দেখে নেবেন — এগুলো সময়ের সাথে বদলায়।

৫ · Cache optimization-এর তালিকা — কোন কৌশল কোন পদ কমায়

AMAT-এর তিনটি পদ — hit time, miss rate, miss penalty — প্রতিটি কমানোর আলাদা কৌশল আছে; সাথে আছে bandwidth বাড়ানো আর miss-এর সময় অন্য কাজ চালিয়ে যাওয়া। Hennessy আর Patterson-এর বইয়ে যে ধাঁচে সাজানো থাকে, তার কাছাকাছি একটি তালিকা নিচে। প্রতিটি কৌশলের কোনো না কোনো দাম আছে; কোন chip কোনটি কতটা নেয়, তা নকশাভেদে আলাদা।

কয়েকটি কৌশল একটু খুলে বলি। Critical word first: ৬৪ byte-এর block আনতে কয়েকটি ধাপে ডেটা আসে; CPU চেয়েছে হয়তো মাঝের একটি ৮ byte. মেমরিকে বলা হয় সেই word দিয়েই শুরু করতে, আর আসামাত্র register-এ পাঠানো হয় — বাকি block পেছনে ভরে। Non-blocking cache: সাধারণ (blocking) cache একটি miss চলাকালীন সব access আটকে রাখে। Non-blocking cache প্রতিটি অসমাপ্ত miss-এর ঠিকানা আর কে অপেক্ষা করছে, তা একটি Miss Status Holding Register (MSHR)-এ লিখে রাখে, আর এর মধ্যে অন্য hit, এমনকি আরও miss, চালিয়ে যায়। একই block-এ দ্বিতীয় miss এলে নতুন অনুরোধ না পাঠিয়ে আগের MSHR-এর সাথে জুড়ে দেওয়া হয়। MSHR-এর সংখ্যা (আধুনিক core-এ কয়েকটি থেকে কয়েক ডজনের মতো বলে বর্ণিত) ঠিক করে একসাথে কতগুলো miss উড়তে পারে।

Prefetcher: সবচেয়ে সরলটি next-line — block B-তে miss হলে B + 1-ও এনে রাখা। Stride prefetcher একটি নির্দিষ্ট load instruction-এর (PC ধরে) পরপর ঠিকানার পার্থক্য দেখে; পার্থক্য স্থির হলে (যেমন প্রতিবার +২৫৬ byte) সামনের কয়েকটি ঠিকানা আগেভাগে আনে। আধুনিক chip-এ এর চেয়ে অনেক জটিল prefetcher থাকে বলে জানা যায়, কিন্তু তাদের খুঁটিনাটি সাধারণত প্রকাশিত নয়। একটি prefetch-এর মান তিনটি জিনিসে: accuracy (আনা block কি কাজে লাগল), coverage (কত miss এড়ানো গেল), আর timeliness (দরকারের আগে পৌঁছাল কি না)।

৬ · Memory-level parallelism — কেন stall-এর সূত্র একটি ঊর্ধ্বসীমা

অংশ ৩-এর প্রমাণে একটি অনুমান ছিল: প্রতিটি miss-এ CPU পুরো penalty দাঁড়িয়ে থাকে, আর miss-গুলো একটির পর একটি। সরল in-order core-এ এটি প্রায় সত্য। কিন্তু পর্ব ৪০-এর out-of-order core একটি load-এর miss চলাকালীন instruction window-এর পরের স্বাধীন কাজ চালিয়ে যায় — আর সেই কাজে যদি আরও load থাকে, তাদের miss-ও একই সময়ে শুরু হয়। Non-blocking cache আর MSHR এটি সম্ভব করে। একসাথে একাধিক miss উড়ন্ত রাখার এই ক্ষমতাই memory-level parallelism (MLP).

ধরুন ৪টি miss একসাথে উড়ছে, প্রতিটি ১০০ cycle. Stall-এর সূত্র বলবে ৪০০ cycle; বাস্তবে প্রায় ১০০-র কিছু বেশি। তাই আধুনিক core-এ সূত্রটি একটি ঊর্ধ্বসীমা (worst case) — পরীক্ষার numerical-এ এটাই ব্যবহার করবেন, কিন্তু মাপা সময় এর চেয়ে কম হলে অবাক হবেন না। উল্টো দিকে, যে কোডে পরের ঠিকানা আগের load-এর ফল থেকে আসে (pointer chasing: linked list, tree), সেখানে MLP শূন্য, আর prefetcher-ও পরের ঠিকানা অনুমান করতে পারে না — সূত্রটি সেখানে প্রায় হুবহু খাটে।

নিচের প্রোগ্রাম একই ১৬ MiB-এর array (cache-এর চেয়ে বড়) দুইভাবে পড়ে। প্রথমবার ক্রমানুসারে — প্রতিটি load স্বাধীন, ঠিকানা আগে থেকে জানা, prefetcher-এর জন্য আদর্শ। দ্বিতীয়বার pointer chase: array-টিতে আগে থেকে একটি এলোমেলো চক্র (Sattolo-র পদ্ধতিতে, একটি নির্দিষ্ট seed দিয়ে — তাই প্রতিবার একই array) বসানো, আর প্রতিটি load-এর ফলই পরের ঠিকানা। দুটিতেই ঠিক ৪১,৯৪,৩০৪টি load.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
#define N (1u << 22)                     /* 4M entries x 4 bytes = 16 MiB, bigger than the caches */

static double now_ns(void) {
    struct timespec t;
    clock_gettime(CLOCK_MONOTONIC, &t);
    return (double)t.tv_sec * 1e9 + (double)t.tv_nsec;
}

int main(void) {
    uint32_t *nx = malloc(N * sizeof *nx);
    if (!nx) return 1;
    uint64_t r = 88172645463325252u, sum = 0;      /* fixed xorshift seed: same array every run */
    for (uint32_t i = 0; i < N; i++) nx[i] = i;
    for (uint32_t i = N - 1; i > 0; i--) {         /* Sattolo: ONE random cycle through all entries */
        r ^= r << 13; r ^= r >> 7; r ^= r << 17;
        uint32_t j = (uint32_t)(r % i), t = nx[i]; nx[i] = nx[j]; nx[j] = t;
    }
    double t0 = now_ns();
    for (uint32_t i = 0; i < N; i++) sum += nx[i];   /* independent loads, addresses in order */
    double t1 = now_ns();
    uint32_t p = 0;
    for (uint32_t i = 0; i < N; i++) p = nx[p];      /* next address = result of this load */
    double t2 = now_ns();
    double seq = (t1 - t0) / N, chase = (t2 - t1) / N;
    printf("sequential scan : %6.2f ns per access (sum %llu)\n", seq, (unsigned long long)sum);
    printf("pointer chase   : %6.2f ns per access (end at %u)\n", chase, p);
    printf("chase / scan    : about %.0fx slower\n", chase / seq);
    free(nx);
    return 0;
}

sequential scan :   1.61 ns per access (sum 8796090925056)
pointer chase   : 179.60 ns per access (end at 0)
chase / scan    : about 112x slower

মেপে দেখা — performance counter

অনুমানের বদলে মাপতে চাইলে আধুনিক CPU-র performance counter আছে — hardware-এর ভেতরের গণক, যারা cache miss, cycle, instruction ইত্যাদি গোনে। Linux-এ perf টুল দিয়ে এগুলো পড়া যায়। নিচের কমান্ডগুলো শুধু উদাহরণ — এখানে চালানো হয়নি, কারণ অনেক virtual machine আর container-এ counter পাওয়া যায় না বা অনুমতি (perf_event_paranoid) বন্ধ থাকে:

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

ফলাফলে প্রতিটি event-এর গণনা আর কিছু অনুপাত (যেমন instruction per cycle, cache-references-এর কত শতাংশ miss) আসে। সতর্কতা: cache-misses-এর মতো “generic” event কোন hardware event-এ যায়, তা CPU-ভেদে আলাদা — অনেক x86 মেশিনে এটি মূলত last-level cache-এর miss বোঝায় বলে বর্ণিত, L1-এর নয়। কোনো event কোনো মেশিনে না-ও থাকতে পারে। তাই সংখ্যা পড়ার আগে perf list দেখে নিন, আর একই মেশিনে দুটি সংস্করণের তুলনাই সবচেয়ে নির্ভরযোগ্য। OS-এর দিক থেকে মাপার আরও কৌশল Operating Systems কোর্সের পারফরম্যান্স পর্বে, আর C-এর দিক থেকে C প্রোগ্রামিং কোর্সের cache পর্বে.

৭ · AI-এর যুগে — cache-এর হিসাবে AI, আর যাচাইয়ের অভ্যাস

AMAT আর CPI-এর প্রশ্নে AI-এর উত্তর সাধারণত গুছানো দেখায়, কিন্তু সংখ্যায় আর সংজ্ঞায় ভুল প্রায়ই চোখে পড়ে:

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

• প্রতিটি stall-পদের তিনটি গুণক (access/instruction, miss rate, penalty) আলাদা করে মিলিয়েছি
• সব সময় একই এককে (cycle বা ns) আছে কি না দেখেছি, আর ns থেকে cycle-এ বদল নিজে করেছি
• Local আর global miss rate গুলিয়ে যায়নি: global = MR_L1 × local
• দুই পথে (global দিয়ে আর local দিয়ে) হিসাব করে একই CPI পেয়েছি
• Write policy-র ট্রাফিক একটি ছোট trace-এ হাতে বা simulator-এ গুনে মিলিয়েছি
• কোনো chip-এর cache-এর তথ্য নির্মাতার নথি বা নিজের মেশিনে যাচাই করেছি