Cache-এর মৌলিক কথা — direct-mapped cache আর address-এর ভাগ

১ · Cache কী — ডেস্কের খাতা আর আলমারি

পর্ব ৪৪-এ (মেমরি হায়ারার্কি আর locality) দেখেছেন, কেন মেমরি স্তরে স্তরে সাজানো: register খুব দ্রুত কিন্তু খুব কম, main memory অনেক বড় কিন্তু CPU-র তুলনায় বহু গুণ ধীর। মাঝখানের সেতুটি হলো cache — CPU-র কাছে রাখা ছোট, দ্রুত SRAM, যাতে main memory-র সেই অংশের কপি থাকে, যা এখন কাজে লাগছে। Cache-এ আলাদা কোনো ঠিকানা নেই; প্রোগ্রাম সাধারণ memory address-ই দেয়, আর hardware নিজে খুঁজে দেখে কপিটি কাছে আছে কি না। Programmer-এর চোখে cache অদৃশ্য — শুধু গতিতে তার উপস্থিতি টের পাওয়া যায়।

Block বা line — কপির একক

Cache কখনো একটি বাইট আলাদা করে আনে না। Memory-কে সমান মাপের টুকরোয় ভাগ করা হয় — একেকটি block বা line — আর cache আনে-রাখে পুরো block. আজকের সাধারণ x86-64 আর ARM প্রসেসরে L1-এর line সাধারণত ৬৪ বাইট (কিছু নকশায় ১২৮)। পাঠ্যবইয়ের ছোট উদাহরণে block হতে পারে ১ বা ৪ word. Block ধরে আনার কারণ পর্ব ৪৪-এর spatial locality: একটি ঠিকানা লাগলে পাশের ঠিকানাও শিগগিরই লাগার সম্ভাবনা বেশি (array-র পরের element, পরের instruction). আর একবার আনা block কিছুক্ষণ রেখে দেওয়ার কারণ temporal locality: যা এইমাত্র লেগেছে, তা আবার লাগার সম্ভাবনা বেশি (loop-এর counter, loop-এর instruction নিজেই)।

কয়েকটি শব্দ পুরো Module ৮-এ বারবার আসবে। যা খোঁজা হচ্ছে তা cache-এ থাকলে hit, না থাকলে miss. মোট access-এর মধ্যে hit-এর ভগ্নাংশ hit rate, আর miss rate = ১ − hit rate. Hit হলে উত্তর দিতে যে সময় লাগে, তা hit time; miss হলে পরের স্তর থেকে block এনে বসাতে যে বাড়তি সময় লাগে, তা miss penalty. এগুলো জুড়ে গড় সময়ের সূত্র (AMAT) আর CPI-এর হিসাব পর্ব ৪৭-এ (Cache-এর পারফরম্যান্স)।

যেকোনো cache-এর চারটি প্রশ্ন

যেকোনো cache-এর নকশা আসলে চারটি প্রশ্নের উত্তর। ১. Placement: একটি block cache-এর কোথায় বসতে পারে? ২. Identification: বসার পর তাকে চিনব কীভাবে? ৩. Replacement: জায়গা না থাকলে কাকে সরাব? ৪. Write: লেখা হলে memory-কে কখন জানাব? এই পর্ব প্রথম দুটি প্রশ্নের সবচেয়ে সরল উত্তর দেয় — direct-mapped cache. তৃতীয় প্রশ্ন, আর একাধিক ঘরের সুযোগ, পর্ব ৪৬-এ (Set-associative আর fully associative cache); চতুর্থটি পর্ব ৪৭-এ।

২ · Direct-mapped cache — প্রতিটি block-এর একটিই ঘর

Placement-এর সবচেয়ে সরল নিয়ম: প্রতিটি memory block-এর জন্য cache-এ ঠিক একটি নির্দিষ্ট ঘর। কোন ঘর? Block-এর নম্বরকে cache-এর মোট block-সংখ্যা দিয়ে ভাগ করে ভাগশেষ:

index = (block address) mod (cache-এ block-এর সংখ্যা)

এখানে block address = byte address ÷ block size (ভাগফলের পূর্ণ অংশ) — অর্থাৎ memory-র কত নম্বর block. ধরুন cache-এ ৮টি block আর block size ১ word. Word address ২২-এর block ২২, আর ২২ mod ৮ = ৬, তাই সে বসবে ঘর ৬-এ। Word ১৪, ৩০, ৩৮ — সবারই ভাগশেষ ৬, তাই তারাও ঘর ৬-এর দাবিদার। একসাথে একজনই বসতে পারে।

কেন mod মানে শুধু বিট তুলে নেওয়া

Cache-এর block-সংখ্যা আর block size দুটোই ২-এর ঘাত রাখা হয়। পর্ব ০৪-এর (সংখ্যা পদ্ধতি) একটি সরল সত্য এখানে কাজে লাগে: কোনো binary সংখ্যাকে ২^k দিয়ে ভাগ করলে ভাগশেষ হলো তার নিচের k বিট, আর ভাগফল হলো বাকি ওপরের বিট। যেমন ২২ = 10110; ৮ = ২^৩ দিয়ে ভাগ করলে ভাগশেষ নিচের তিন বিট 110 = ৬, ভাগফল ওপরের দুই বিট 10 = ২। তাই hardware-এ কোনো ভাগের circuit লাগে না — address-এর তার থেকে কয়েকটি তার সরাসরি নিয়ে নিলেই index.

একই যুক্তি দুবার খাটালে পুরো byte address তিন ভাগ হয়ে যায়। ধরুন address n বিটের, block size ২^b বাইট, cache-এ ২ⁱটি block:

• Block offset (নিচের b বিট): address ÷ ২^b-এর ভাগশেষ — block-এর ভেতরে কত নম্বর বাইট। offset = log₂(block size).
• Index (পরের i বিট): block address ÷ ২ⁱ-এর ভাগশেষ — cache-এর কোন ঘর। index = log₂(block-সংখ্যা) = log₂(cache size ÷ block size).
• Tag (ওপরের n − i − b বিট): block address ÷ ২ⁱ-এর ভাগফল। একই ঘরের দাবিদার অনেক block, তাদের আলাদা করে চেনার জন্য এটুকু ঘরের পাশে লিখে রাখা হয় — এটিই tag.

| tag : n − i − b | index : i | block offset : b |

কেন এটুকুই যথেষ্ট (ছোট প্রমাণ): যেকোনো address A-কে অনন্যভাবে লেখা যায় A = (tag × ২ⁱ + index) × ২^b + offset, যেখানে ০ ≤ index < ২ⁱ আর ০ ≤ offset < ২^b — এটি দুবার ভাগ-ভাগশেষের উপপাদ্য। ঘর নম্বর (index) জানা থাকায় সেটি লিখে রাখার দরকার নেই, offset তো block-এর ভেতরের অবস্থান মাত্র। তাই একটি ঘরে কোন block বসে আছে, তা নিশ্চিত বলতে শুধু tag জমা রাখাই যথেষ্ট — দুটি ভিন্ন block একই index-এ এলে তাদের tag অবশ্যই ভিন্ন। আবার এর চেয়ে কম বিটে চলবে না: একই index-এর ২^n−i−bটি সম্ভাব্য block আলাদা করতে অন্তত n − i − b বিট লাগে।

নিচের stepper-এ একটি বাস্তবধর্মী cache-এ একটি hex address খোঁজা হচ্ছে: ৩২-বিট address, ১৬ KiB data, ৬৪ B block. হিসাব: offset = log₂৬৪ = ৬, block-সংখ্যা = ১৬,৩৮৪ ÷ ৬৪ = ২৫৬ = ২^৮, তাই index = ৮, tag = ৩২ − ৮ − ৬ = ১৮ বিট।

৩ · Hardware-এর ভেতরে — valid bit, tag তুলনা আর hit-এর circuit

প্রতিটি cache line আসলে তিনটি জিনিসের একটি সারি: data (পুরো block), tag, আর একটি valid bit. Valid bit কেন লাগে? Computer চালু হওয়ার মুহূর্তে cache-এর SRAM-এ এলোমেলো বিট থাকে; কোনো tag ঘটনাক্রমে মিলে গেলে CPU আবর্জনা পড়ত। তাই চালু হওয়ার সময় (বা OS যখন cache খালি করতে বলে) সব valid bit ০ করা হয়, আর block বসানোর সময় ১। নিচের ছবিটি পাঠ্যবইয়ের ক্লাসিক diagram-এর ধাঁচে: ৩২-বিট address, ১,০২৪টি line, প্রতিটি line-এ ৪ word (১৬ বাইট) — ভাগ ১৮ | ১০ | ৪.

ছবির তিনটি অংশ পর্ব ১২-এর (Multiplexer, decoder আর encoder) পুরোনো বন্ধু। Index একটি ১০-থেকে-১,০২৪ decoder-এর মতো কাজ করে — SRAM-এর ঠিক একটি সারি সক্রিয় হয়। Tag-এর তুলনা একটি equality comparator: ১৮ জোড়া বিটের প্রতিটিতে একটি XNOR (মিললে ১), তারপর সব ফল একটি বড় AND-এ। শেষে:

Hit = V · (stored tag = address tag)

আর data-র পথে একটি ৪-থেকে-১ multiplexer, যার select লাইন word offset-এর দুই বিট। লক্ষ করুন, tag তুলনা আর data পড়া একই সময়ে চলে — direct-mapped নকশায় একটি মাত্র সম্ভাব্য জায়গা, তাই hit হবে ধরে নিয়ে data আগেভাগেই multiplexer দিয়ে বেরিয়ে আসে; Hit = ০ হলে CPU সেটি ফেলে দেয়। এজন্যই direct-mapped cache-এর hit time সবচেয়ে কম। পর্ব ৪৬-এর set-associative cache-এ একাধিক tag-এর তুলনার পর কোন data নেওয়া হবে, সেই বাড়তি multiplexer hit time-এ কিছুটা যোগ করে।

৪ · বিটের হিসাব — tag, index, offset আর “মোট কত bit”

পরীক্ষায় cache-এর সবচেয়ে প্রচলিত numerical দুটি: (১) একটি configuration দেওয়া আছে, tag, index আর offset কত বিট? (২) পুরো cache বানাতে মোট কত bit SRAM লাগবে? দ্বিতীয়টির ফাঁদ হলো, “cache size” শুধু data গোনে (Module ৮-এর নিয়ম), অথচ প্রতিটি line-এ tag আর valid bit-ও জমা রাখতে হয়।

তিন ধাপের নিয়ম

1. offset = log₂(block size বাইটে)
2. line-সংখ্যা = cache size ÷ block size; index = log₂(line-সংখ্যা)
3. tag = address-এর বিট − index − offset

আর মোট bit = line-সংখ্যা × (৮ × block size + tag + ১ valid [+ ১ dirty]).

পূর্ণ সমাধান — পাঠ্যবইয়ের “মোট কত bit” সমস্যা

প্রশ্ন: একটি direct-mapped cache-এ ১৬ KiB data, block ৪ word (১ word = ৪ বাইট), address ৩২ বিট। মোট কত bit লাগবে?

• Block size = ৪ × ৪ = ১৬ বাইট → offset = log₂১৬ = ৪ বিট (২ বিট word বাছাই + ২ বিট বাইট বাছাই)।
• Line-সংখ্যা = ১৬,৩৮৪ ÷ ১৬ = ১,০২৪ = ২^১০ → index = ১০ বিট.
• Tag = ৩২ − ১০ − ৪ = ১৮ বিট.
• প্রতি line: data ৪ × ৩২ = ১২৮ বিট, tag ১৮, valid ১ → ১৪৭ বিট।
• মোট = ১,০২৪ × ১৪৭ = ১,৫০,৫২৮ বিট = ১৪৭ Kibit ≈ ১৮.৪ KiB — অর্থাৎ ১৬ KiB data-র জন্য প্রায় ১.১৫ গুণ SRAM.

টেবিলের শেষ সারিটি লক্ষ করুন: ১ word-এর block-এ প্রতি ৩২ বিট data-র জন্য ২১ বিট বাড়তি — প্রায় ৬৬% overhead. Block বড় হলে প্রতি line-এ tag একটিই থাকে কিন্তু data বাড়ে, তাই overhead দ্রুত কমে: ৬৪ B block-এ মাত্র ৩.৭%. বাস্তব cache-এর block কেন বড়, তার এটি একটি কারণ। নিচের calculator একই নিয়ম পাঁচটি configuration-এ চালায় — শেষ দুটিতে dirty bit, আর শেষটিতে ৬৪-বিট address.

// Direct-mapped cache: address split and total storage bits.
// "Cache size" counts data only; every line also stores a tag, a valid
// bit and (for a write-back cache, see lesson 47) a dirty bit.
const KiB = 1024;
function split(addrBits, cacheBytes, blockBytes, dirty) {
  const lines = cacheBytes / blockBytes;
  const off = Math.log2(blockBytes), idx = Math.log2(lines);
  const tag = addrBits - idx - off;
  const perLine = 8 * blockBytes + tag + 1 + (dirty ? 1 : 0);
  const total = lines * perLine, data = 8 * cacheBytes;
  console.log(`${addrBits}-bit, ${cacheBytes / KiB} KiB, ${blockBytes} B blocks` +
    (dirty ? " (+dirty)" : ""));
  console.log(`   lines = ${lines} = 2^${idx}   tag|index|offset = ${tag}|${idx}|${off}`);
  console.log(`   bits/line = ${8 * blockBytes} data + ${tag} tag + 1 valid` +
    (dirty ? " + 1 dirty" : "") + ` = ${perLine}`);
  console.log(`   total = ${lines} x ${perLine} = ${total} bits = ${total / KiB} Kibit` +
    ` = ${(total / 8 / KiB).toFixed(2)} KiB   (overhead ${(100 * (total - data) / data).toFixed(1)}%)`);
}
split(32, 16 * KiB, 16, false);   // textbook: 16 KiB data, 4-word blocks
split(32, 16 * KiB, 64, false);
split(32, 64 * KiB, 32, false);
split(32, 64 * KiB, 32, true);    // same cache, write-back
split(64, 32 * KiB, 64, true);    // a 64-bit address, typical L1 line size

32-bit, 16 KiB, 16 B blocks
   lines = 1024 = 2^10   tag|index|offset = 18|10|4
   bits/line = 128 data + 18 tag + 1 valid = 147
   total = 1024 x 147 = 150528 bits = 147 Kibit = 18.38 KiB   (overhead 14.8%)
32-bit, 16 KiB, 64 B blocks
   lines = 256 = 2^8   tag|index|offset = 18|8|6
   bits/line = 512 data + 18 tag + 1 valid = 531
   total = 256 x 531 = 135936 bits = 132.75 Kibit = 16.59 KiB   (overhead 3.7%)
32-bit, 64 KiB, 32 B blocks
   lines = 2048 = 2^11   tag|index|offset = 16|11|5
   bits/line = 256 data + 16 tag + 1 valid = 273
   total = 2048 x 273 = 559104 bits = 546 Kibit = 68.25 KiB   (overhead 6.6%)
32-bit, 64 KiB, 32 B blocks (+dirty)
   lines = 2048 = 2^11   tag|index|offset = 16|11|5
   bits/line = 256 data + 16 tag + 1 valid + 1 dirty = 274
   total = 2048 x 274 = 561152 bits = 548 Kibit = 68.50 KiB   (overhead 7.0%)
64-bit, 32 KiB, 64 B blocks (+dirty)
   lines = 512 = 2^9   tag|index|offset = 49|9|6
   bits/line = 512 data + 49 tag + 1 valid + 1 dirty = 563
   total = 512 x 563 = 288256 bits = 281.5 Kibit = 35.19 KiB   (overhead 10.0%)

৫ · একটি পূর্ণ trace — পাঠ্যবইয়ের ৮-block cache

এবার সবচেয়ে পরিচিত হাতে-কলমে উদাহরণ (Patterson–Hennessy-র ধাঁচে)। Cache-এ ৮টি block, প্রতিটি ১ word; address দেওয়া word-এ, ৫ বিটের। তাই offset ০ বিট, index = log₂৮ = ৩ বিট (নিচের তিন), tag = ২ বিট (ওপরের দুই)। প্রোগ্রাম পরপর এই word address-গুলো চায়:

২২, ২৬, ২২, ২৬, ১৬, ৩, ১৬, ১৮

প্রতিটি address binary-তে লিখে নিচের তিন বিট দেখুন — সেটিই ঘর। ২২ = 10 110 → ঘর ১১০ (৬), tag ১০। ২৬ = 11 010 → ঘর ০১০ (২), tag ১১। ১৬ = 10 000 → ঘর ০০০, tag ১০। ৩ = 00 011 → ঘর ০১১, tag ০০। ১৮ = 10 010 → ঘর ০১০, tag ১০ — ২৬-এর ঘরেই! নিচের stepper-এ প্রতিটি access-এর পর পুরো cache-এর ছবি।

এই হিসাব হাতে করতে করতে ভুল হওয়া সহজ, তাই একটি simulator বানানো যাক। নিচের প্রোগ্রাম যেকোনো cache size, block size আর address-এর বিট-সংখ্যা নেয়, trace দশমিক বা hex-এ, আর প্রতিটি access-এর tag, index, offset, hit বা miss, miss-এর তিন C-এর শ্রেণি (অংশ ৭-এর নিয়ম), শেষে cache-এর ভেতরে কী আছে আর hit rate ছাপে। পাঁচটি পরীক্ষা চলে: পাঠ্যবইয়ের trace; একই trace ৪-word block-এ (একই ৮ word ধারণক্ষমতা); ৪-word block-এ টানা একটি scan; একটি ping-pong; আর ১৬ KiB, ৬৪ B block-এর একটি hex trace.

// Direct-mapped cache simulator. Sizes are in addressable units (bytes,
// or words for the textbook trace). Miss class (3 C's): first touch of the
// block = compulsory; else a fully associative LRU cache with the same
// number of blocks would also miss = capacity; else = conflict.
function simulate(title, cacheSize, blockSize, addrBits, trace, hex) {
  const nBlocks = cacheSize / blockSize, offBits = Math.log2(blockSize);
  const idxBits = Math.log2(nBlocks), tagBits = addrBits - idxBits - offBits;
  const line = Array.from({length: nBlocks}, () => ({v: 0, tag: 0, blk: 0}));
  const seen = new Set(), fa = [];        // fa: fully associative LRU list
  let hits = 0;
  const f = (n, w) => (hex ? "0x" + n.toString(16).toUpperCase() : String(n)).padStart(w);
  console.log(`== ${title}: ${nBlocks} blocks x ${blockSize}, tag|index|offset = ${tagBits}|${idxBits}|${offBits} bits`);
  for (const a of trace) {
    const blk = Math.floor(a / blockSize), idx = blk % nBlocks;
    const tag = Math.floor(blk / nBlocks), off = a % blockSize, L = line[idx];
    const hit = L.v === 1 && L.tag === tag, p = fa.indexOf(blk);
    if (p >= 0) fa.splice(p, 1); else if (fa.length === nBlocks) fa.shift();
    fa.push(blk);
    const kind = hit ? "" : !seen.has(blk) ? "compulsory" : p >= 0 ? "conflict" : "capacity";
    seen.add(blk);
    if (hit) hits++; else Object.assign(L, {v: 1, tag, blk});
    console.log(`${f(a, 11)}  tag ${f(tag, 7)}  idx ${f(idx, 5)}  off ${f(off, 4)}  ${hit ? "HIT " : "MISS"} ${kind}`);
  }
  const live = line.map((L, i) => L.v ? `[${f(i, 1)}] tag ${f(L.tag, 1)} = block ${f(L.blk, 1)}` : "").filter(s => s);
  console.log("cache now: " + live.join(", "));
  console.log(`hits ${hits}/${trace.length}  hit rate ${(100 * hits / trace.length).toFixed(1)}%\n`);
}
const book = [22, 26, 22, 26, 16, 3, 16, 18];          // word addresses
simulate("textbook, 1-word blocks", 8, 1, 5, book);
simulate("same 8 words, 4-word blocks", 8, 4, 5, book);
simulate("scan 16..23, 4-word blocks", 8, 4, 5, [16, 17, 18, 19, 20, 21, 22, 23]);
simulate("ping-pong 0,8,0,8", 8, 1, 5, [0, 8, 0, 8, 0, 8]);
simulate("16 KiB, 64 B blocks, 32-bit", 16384, 64, 32,
  [0x00012340, 0x0001237C, 0x00016340, 0x00012344, 0x12345678, 0x12345640], true);

== textbook, 1-word blocks: 8 blocks x 1, tag|index|offset = 2|3|0 bits
         22  tag       2  idx     6  off    0  MISS compulsory
         26  tag       3  idx     2  off    0  MISS compulsory
         22  tag       2  idx     6  off    0  HIT
         26  tag       3  idx     2  off    0  HIT
         16  tag       2  idx     0  off    0  MISS compulsory
          3  tag       0  idx     3  off    0  MISS compulsory
         16  tag       2  idx     0  off    0  HIT
         18  tag       2  idx     2  off    0  MISS compulsory
cache now: [0] tag 2 = block 16, [2] tag 2 = block 18, [3] tag 0 = block 3, [6] tag 2 = block 22
hits 3/8  hit rate 37.5%

== same 8 words, 4-word blocks: 2 blocks x 4, tag|index|offset = 2|1|2 bits
         22  tag       2  idx     1  off    2  MISS compulsory
         26  tag       3  idx     0  off    2  MISS compulsory
         22  tag       2  idx     1  off    2  HIT
         26  tag       3  idx     0  off    2  HIT
         16  tag       2  idx     0  off    0  MISS compulsory
          3  tag       0  idx     0  off    3  MISS compulsory
         16  tag       2  idx     0  off    0  MISS conflict
         18  tag       2  idx     0  off    2  HIT
cache now: [0] tag 2 = block 4, [1] tag 2 = block 5
hits 3/8  hit rate 37.5%

== scan 16..23, 4-word blocks: 2 blocks x 4, tag|index|offset = 2|1|2 bits
         16  tag       2  idx     0  off    0  MISS compulsory
         17  tag       2  idx     0  off    1  HIT
         18  tag       2  idx     0  off    2  HIT
         19  tag       2  idx     0  off    3  HIT
         20  tag       2  idx     1  off    0  MISS compulsory
         21  tag       2  idx     1  off    1  HIT
         22  tag       2  idx     1  off    2  HIT
         23  tag       2  idx     1  off    3  HIT
cache now: [0] tag 2 = block 4, [1] tag 2 = block 5
hits 6/8  hit rate 75.0%

== ping-pong 0,8,0,8: 8 blocks x 1, tag|index|offset = 2|3|0 bits
          0  tag       0  idx     0  off    0  MISS compulsory
          8  tag       1  idx     0  off    0  MISS compulsory
          0  tag       0  idx     0  off    0  MISS conflict
          8  tag       1  idx     0  off    0  MISS conflict
          0  tag       0  idx     0  off    0  MISS conflict
          8  tag       1  idx     0  off    0  MISS conflict
cache now: [0] tag 1 = block 8
hits 0/6  hit rate 0.0%

== 16 KiB, 64 B blocks, 32-bit: 256 blocks x 64, tag|index|offset = 18|8|6 bits
    0x12340  tag     0x4  idx  0x8D  off  0x0  MISS compulsory
    0x1237C  tag     0x4  idx  0x8D  off 0x3C  HIT
    0x16340  tag     0x5  idx  0x8D  off  0x0  MISS compulsory
    0x12344  tag     0x4  idx  0x8D  off  0x4  MISS conflict
 0x12345678  tag  0x48D1  idx  0x59  off 0x38  MISS compulsory
 0x12345640  tag  0x48D1  idx  0x59  off  0x0  HIT
cache now: [0x59] tag 0x48D1 = block 0x48D159, [0x8D] tag 0x4 = block 0x48D
hits 2/6  hit rate 33.3%

৬ · Block কত বড় হবে — লাভ, ক্ষতি আর miss rate-এর বাঁক

ওপরের দুটি পরীক্ষা আসলে পুরো নকশা-প্রশ্নটির ক্ষুদ্র সংস্করণ। Cache-এর মোট আকার স্থির রেখে block বড় করলে তিনটি জিনিস ঘটে:

ফল: একটি নির্দিষ্ট cache size-এ block size বাড়ালে miss rate প্রথমে দ্রুত কমে, তারপর সমতল হয়, আর block যখন cache-এর তুলনায় বড় হয়ে block-এর সংখ্যা খুব কমে যায়, তখন আবার বাড়তে পারে। পাঠ্যবইয়ে benchmark-এর মাপা miss rate-এর যে বক্ররেখা দেখানো হয়, তাতে ছোট cache-এ এই “U” আকার স্পষ্ট, আর বড় cache-এ বাঁকটি অনেক পরে আসে — কারণ বড় cache-এ block বড় করলেও যথেষ্ট ঘর থাকে। সঠিক সংখ্যাগুলো workload আর মাপার পদ্ধতিভেদে বদলায়, তাই এখানে আকারটিই মনে রাখুন। আরও একটি সূক্ষ্মতা: miss rate সর্বনিম্ন যেখানে, গড় সময় সর্বনিম্ন সেখানে না-ও হতে পারে, কারণ বড় block-এ miss penalty-ও বাড়ে; তাই নকশাকাররা গড় memory access time (AMAT, পর্ব ৪৭) দেখে সিদ্ধান্ত নেন। বাস্তবে সাধারণ CPU-র L1-এ ৬৪ বাইট বহুদিন ধরে প্রচলিত।

নিচের C প্রোগ্রাম JS simulator-এর একটি স্বাধীন cross-check: একই direct-mapped নিয়মে একটি ১ KiB cache-এর model, যা একটি ৪ KiB int array-র তিন রকম ব্যবহারে ১৬ B আর ৬৪ B block-এর miss rate ছাপে। দ্বিতীয় আর তৃতীয় trace-এ দুটি array a[] আর b[] পাশাপাশি পড়া হয়; b-এর শুরুর ঠিকানা কেবল ৬৪ বাইট সরানো হয়েছে।

// Direct-mapped cache model (1 KiB data) fed with array-access traces.
// int a[1024] starts at address 0; b[] starts right after it (aliased)
// or one 64-byte line later (padded). Prints miss rate per block size.
#include <stdio.h>
#include <string.h>
#define CACHE 1024u
static unsigned tagv[CACHE / 4];
static unsigned char valid[CACHE / 4];
static unsigned long accesses, misses;
static void access_addr(unsigned addr, unsigned block) {
    unsigned lines = CACHE / block, blk = addr / block;
    unsigned idx = blk % lines, tag = blk / lines;
    accesses++;
    if (!valid[idx] || tagv[idx] != tag) {      /* miss: fetch the block */
        misses++; valid[idx] = 1; tagv[idx] = tag;
    }
}
static double miss_rate(int trace, unsigned block) {
    memset(valid, 0, sizeof valid);
    accesses = misses = 0;
    unsigned b = trace == 1 ? 4096u : 4096u + 64u;   /* address of b[0] */
    for (unsigned i = 0; i < 1024; i++) {
        access_addr(4 * i, block);                    /* read a[i] */
        if (trace) access_addr(b + 4 * i, block);     /* read b[i] */
    }
    return 100.0 * (double)misses / (double)accesses;
}
int main(void) {
    const char *name[] = {"scan a[i]", "a[i]+b[i], b = a+4096", "a[i]+b[i], b = a+4096+64"};
    printf("%-26s %10s %10s\n", "trace (1 KiB cache)", "16 B", "64 B");
    for (int t = 0; t < 3; t++)
        printf("%-26s %9.2f%% %9.2f%%\n", name[t], miss_rate(t, 16), miss_rate(t, 64));
    return 0;
}

trace (1 KiB cache)              16 B       64 B
scan a[i]                      25.00%      6.25%
a[i]+b[i], b = a+4096         100.00%    100.00%
a[i]+b[i], b = a+4096+64       25.00%      6.25%

৭ · তিন C — miss কেন হলো, তার শ্রেণিভাগ

সব miss এক জাতের নয়, আর প্রতিকারও আলাদা। Mark Hill-এর প্রবর্তিত বলে পরিচিত “three C's” মডেল প্রতিটি miss-কে তিনটি শ্রেণির একটিতে ফেলে:

• Compulsory miss (cold-start): block-টি এই প্রথম চাওয়া হলো — যত বড় cache-ই হোক, এটি এড়ানো যেত না (তবে বড় block আর prefetching এর সংখ্যা কমায়)।
• Capacity miss: প্রোগ্রাম এই মুহূর্তে যত block ঘুরিয়ে ফিরিয়ে ব্যবহার করছে, তা cache-এ একসাথে আঁটে না — একই আকারের, যেকোনো ঘরে বসতে পারে এমন cache-ও এখানে miss করত। প্রতিকার: বড় cache.
• Conflict miss (collision): cache-এ জায়গা ছিল, কিন্তু placement-এর নিয়মে দুটি block একই ঘরের দাবিদার হওয়ায় একটি সরে গেছে। প্রতিকার: বেশি associativity (পর্ব ৪৬), বা data-র ঠিকানা সরানো।

এখন trace-গুলোর miss শ্রেণিভাগ করা যাক। পাঠ্যবইয়ের ১-word trace-এ পাঁচটি miss-এর পাঁচটিই compulsory — প্রতিটি miss-এ এমন word এসেছে যা আগে কখনো আসেনি। ৪-word সংস্করণে দ্বিতীয় ১৬-র miss conflict: ৩ আর ১৬-র block একই ঘরে, অথচ ২-block-এর একটি fully associative cache-এ তখন block ৪ (১৬–১৯) আর block ০ (০–৩) দুটোই থাকত। Ping-pong-এর প্রথম দুটি compulsory, বাকি চারটি conflict — ৮টি ঘরের মধ্যে মাত্র দুটি block, কাজেই capacity-র প্রশ্নই নেই।

Capacity miss দেখতে একটু বড় trace লাগে। অনুশীলন ২-এ একটি ৪-block cache-এ পাঁচটি ভিন্ন block ঘুরিয়ে চাওয়ার পর প্রথম block ফিরে এলে simulator যে “capacity” দেখায়, তা হাতে মিলিয়ে নিতে পারবেন। মনে রাখার মতো আরও একটি কথা: এই শ্রেণিভাগ একটি মডেল, প্রকৃতির নিয়ম নয়। Fully associative cache-এর replacement নীতি (LRU, না অন্য কিছু) বদলালে শ্রেণির সংখ্যাও বদলায়, আর মাঝে মাঝে direct-mapped cache এমন জায়গায় hit করে যেখানে fully associative LRU miss করত। Multicore-এ একটি চতুর্থ C-ও আছে — coherence miss — যা পর্ব ৫৩-এ (Multicore আর cache coherence).

বাস্তব যন্ত্রে ping-pong — দেখা যায় কি?

বাস্তব CPU-র L1 data cache direct-mapped নয়; সাধারণত ৮ থেকে ১২-way set-associative (পর্ব ৪৬)। তাই দুটি ঠিকানা একই set-এ পড়লেও তারা পাশাপাশি থাকতে পারে, আর ওপরের দুই-array ping-pong বাস্তবে প্রায় দেখাই যায় না। কিন্তু একই set-এ way-এর চেয়ে বেশি line পড়লে conflict ফিরে আসে। সাধারণ x86-64 L1-এ ৬৪ বাইটের line আর ৬৪টি set থাকলে ৪,০৯৬ বাইট দূরের ঠিকানাগুলো একই set-এ পড়ে। নিচের প্রোগ্রাম ৩২টি এমন ঠিকানা বারবার পড়ে, তারপর একই কাজ করে ৪,০৯৬ + ৬৪ বাইট দূরত্বে, যেখানে ৩২টি line ৩২টি ভিন্ন set-এ ছড়িয়ে পড়ে।

// Real machine: K lines 4096 B apart (all map to the same L1 set) versus
// 4096+64 B apart (spread over K sets). Timings vary per run and machine.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define K 32
#define ROUNDS 200000
static double now_ns(void) {
    struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t);
    return t.tv_sec * 1e9 + t.tv_nsec;
}
static double ns_per_access(const volatile char *base, size_t stride) {
    const volatile char *p[K];
    for (int k = 0; k < K; k++) p[k] = base + (size_t)k * stride;
    unsigned sum = 0; double best = 1e30;
    for (int trial = 0; trial < 3; trial++) {         /* keep the best of 3 */
        double t0 = now_ns();
        for (int r = 0; r < ROUNDS; r++)
            for (int k = 0; k < K; k++) sum += p[k][0];
        double t = (now_ns() - t0) / ((double)ROUNDS * K);
        if (t < best) best = t;
    }
    if (sum == 1) puts("");                           /* keep the loads alive */
    return best;
}
int main(void) {
    char *buf = calloc((size_t)K * (4096 + 64) + 4096, 1);
    if (!buf) return 1;
    double alias = ns_per_access(buf, 4096), pad = ns_per_access(buf, 4096 + 64);
    printf("%d lines, stride 4096    : %.2f ns per access\n", K, alias);
    printf("%d lines, stride 4096+64 : %.2f ns per access\n", K, pad);
    printf("ratio aliased/padded = %.2f\n", alias / pad);
    free(buf);
    return 0;
}

32 lines, stride 4096    : 5.37 ns per access
32 lines, stride 4096+64 : 2.03 ns per access
ratio aliased/padded = 2.64

৮ · Pipeline-এ miss সামলানো — থামা, আনা, আবার চলা

পর্ব ৩৫-এর (Pipelining) পাঁচ ধাপের pipeline ধরে নিয়েছিল, IF আর MEM ধাপে memory এক cycle-এ উত্তর দেয়। Hit হলে তা সত্যি। Miss হলে উত্তর আসতে কয়েক ডজন থেকে শত cycle লাগতে পারে (কোন স্তর থেকে আসছে তার ওপর নির্ভর করে, আর যন্ত্রভেদে বদলায়)। Cache-কে নিয়ন্ত্রণ করে একটি ছোট FSM — cache controller (পর্ব ১৭-এর finite state machine-এর একটি বাস্তব প্রয়োগ)। সরল in-order pipeline-এ miss-এর জবাব হলো পুরো processor-কে stall করা — পর্ব ৩৬-এর (Pipeline hazard) data hazard-এর stall-এর মতো, তবে অনেক লম্বা, আর সব ধাপ একসাথে জমে থাকে (register-এর মান বদলায় না)।

Instruction miss-এর ধাপ (পাঠ্যবইয়ের নিয়মে):

1. যে instruction miss করেছে, তার PC-টি পরের স্তরে পাঠানো। IF ধাপে PC + ৪ ইতিমধ্যে হিসাব হয়ে থাকতে পারে, তাই পাঠ্যবই বলে “current PC − ৪” পাঠাতে — মূল কথা, miss-করা instruction-এর ঠিকানাই চাই।
2. পরের স্তরকে (L2 বা main memory) পুরো block পড়তে বলা, আর উত্তর আসা পর্যন্ত অপেক্ষা।
3. Cache line লেখা: data অংশে block, tag অংশে address-এর ওপরের বিট, valid bit = ১।
4. Instruction-টি আবার শুরু থেকে আনা — এবার সেটি hit.

Data miss একই রকম: lw MEM ধাপে miss করলে processor থেমে থাকে যতক্ষণ না block এসে cache-এ বসে, তারপর load শেষ হয় আর pipeline আবার এগোয়। নিচের stepper-এ একটি instruction miss-এর পুরো যাত্রা — I-cache ১৬ KiB, ১৬ B block (১৮ | ১০ | ৪), PC = 0x00400010.

PC = 0x00400010
   tag    = PC >> 14          = 0x100
   index  = (PC >> 4) & 0x3FF = 0x001
   offset = PC & 0xF          = 0x0
line 1:  V = 1, stored tag = 0x0FF   (some older code)
0x0FF != 0x100  ->  MISS

IF   : the missing instruction, waiting
ID..WB: frozen - no register or memory is written
PC   : held at 0x00400010 (not advanced to the next one)
cost : every stalled cycle adds 1 to the total cycle count

block address = 0x00400010 >> 4 = 0x0040001
request: read 16 bytes, 0x00400010 .. 0x0040001F
         from the next level (L2 or main memory)

cycle   1 .. 100 : waiting for the block   (assumed penalty)
a hit would have taken about 1 cycle in this simple pipeline
-> one miss costs as much time as roughly 100 hits

line 1:  data  = Mem[0x00400010 .. 0x0040001F]
         tag   = 0x100
         V     = 1
(old block with tag 0x0FF is gone; this is a read-only
 I-cache, so nothing has to be written back)

IF again with PC = 0x00400010
line 1: V = 1, tag 0x100 == 0x100  ->  HIT
the pipeline resumes; the next three instructions
(0x00400014, 0x00400018, 0x0040001C) also hit

এই “সব থামিয়ে অপেক্ষা” নকশা সরল, কিন্তু ব্যয়বহুল — পর্ব ৪৭-এ দেখবেন, miss rate সামান্য হলেও memory stall CPI প্রায় দ্বিগুণ করে দিতে পারে। বড় out-of-order প্রসেসর (পর্ব ৪০) একটি load miss করলেও পরের স্বাধীন instruction-গুলো চালিয়ে যায়, আর cache একসাথে একাধিক miss সামলাতে পারে (non-blocking cache) — তবু instruction miss হলে ফ্রন্ট-এন্ড কার্যত শুকিয়ে যায়।

Split বনাম unified cache

Pipeline-এ IF আর MEM একই cycle-এ memory চায় — পর্ব ৩৫-এর structural hazard. তাই প্রায় সব আধুনিক CPU-তে L1 স্তরে দুটি আলাদা cache: instruction cache (I-cache) আর data cache (D-cache) — একে বলে split cache. দুটির নিজস্ব port, নিজস্ব tag আর নিজস্ব index; ওপরের stepper-এর I-cache ঠিক এমন একটি। L2 আর L3 সাধারণত unified — instruction আর data একসাথে। একই মোট আকারে unified cache-এর miss rate সাধারণত একটু কম হতে পারে, কারণ instruction আর data নিজেদের প্রয়োজন অনুযায়ী জায়গা ভাগাভাগি করে নেয়; কিন্তু L1-এ প্রতি cycle-এ দুটি access-এর bandwidth আর ছোট-দ্রুত cache-এর hit time বেশি জরুরি — তাই L1-এ split-ই জেতে।

৯ · পরীক্ষার কৌশল — hex address থেকে দ্রুত tag, index, offset

পরীক্ষায় address প্রায়ই hex-এ দেওয়া থাকে। পুরো ৩২ বিট লিখতে সময় নষ্ট; কয়েকটি কৌশল জানলে কাজ অর্ধেক।

• সীমানা ৪-এর গুণিতকে পড়লে সরাসরি পড়ুন। প্রতিটি hex অঙ্ক ঠিক ৪ বিট। ৩২-বিট, ৬৪ KiB, ৩২ B (১৬ | ১১ | ৫)-এ tag ঠিক ওপরের চারটি অঙ্ক: 0x12345678-এর tag = 0x1234. বাকি 0x5678 = 0101 0110 0111 1000 থেকে নিচের ৫ বিট 11000 = ২৪ (offset), ওপরের ১১ বিট 010 1011 0011 = 0x2B3 = ৬৯১ (index).
• শুধু নিচের অংশ binary করুন। ১৬ KiB, ৬৪ B (১৮ | ৮ | ৬)-এ index + offset = ১৪ বিট, যা নিচের চার hex অঙ্কে (১৬ বিট) আঁটে। 0x5678-এর নিচের ১৪ বিট 01 0110 0111 1000 → offset 111000 = 0x38, index 0101 1001 = 0x59. Tag = (ওপরের অঙ্কগুলো 0x1234) × ৪ + বাদ পড়া দুই বিট (01) = 0x48D0 + ১ = 0x48D1.
• Offset ৪ বিট হলে শেষ অঙ্কটিই offset. ১৬ KiB, ১৬ B (১৮ | ১০ | ৪)-এ 0x12345678-এর offset = 0x8, index = 0x567-এর নিচের ১০ বিট = 0x167 = ৩৫৯, tag = 0x48D1.
• Cache size-এর গুণিতক দূরত্ব = একই index. দুটি address-এর পার্থক্য cache size-এর গুণিতক হলে (direct-mapped-এ) তারা একই ঘরে পড়ে, শুধু tag আলাদা। যেমন ১৬ KiB = 0x4000: 0x12345678 আর 0x12349678 দুটিরই index ৩৫৯ (১৬ B block-এ), tag 0x48D1 বনাম 0x48D2. Conflict-এর প্রশ্নে এটি এক নজরে ধরা যায়।
• উত্তর যাচাই: tag + index + offset = address-এর বিট; index + offset = log₂(cache size); আর tag-কে ২^index+offset দিয়ে গুণ করে বাকি দুই অংশ বসালে মূল address ফিরে আসে।

১০ · AI-এর যুগে cache-এর হিসাব

AI টুল cache-এর ধারণা গুছিয়ে বলতে পারে, কিন্তু বিটের হিসাব আর trace-এ নিয়মিত ভুল করে — বিশেষ করে দীর্ঘ hex-binary রূপান্তরে আর “cache size” কী গোনে তাতে। প্রচলিত ভুল আর ধরার উপায়:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• Index গোনা হয়েছে block দিয়ে, বাইট দিয়ে নয়; tag + index + offset = address-এর বিট
• মোট bit-এ প্রতিটি line-এর tag, valid আর (write-back হলে) dirty ধরা হয়েছে
• অন্তত একটি hex address নিজে binary করে ভাগ মিলিয়েছি, বা এই পর্বের simulator-এ চালিয়েছি
• Cache size-এর গুণিতক দূরত্বের দুটি address একই index পেয়েছে কি না দেখেছি
• Miss-এর শ্রেণিভাগে “আগে এসেছে কি না” আর “fully associative হলে hit হতো কি না” — দুটি প্রশ্নই করা হয়েছে
• বাস্তব chip-এর cache size, way বা latency-র দাবি নির্মাতার তথ্য বা নিজের যন্ত্রে মিলিয়েছি