Set-associative আর fully associative cache — replacement policy

১ · Conflict miss — direct-mapped cache-এর দুর্বলতা

পর্ব ৪৫-এ (Cache-এর মৌলিক কথা) দেখেছেন, একটি direct-mapped cache-এ মেমরির প্রতিটি block-এর জন্য ঘর মাত্র একটি: ঘর = block address mod (ঘরের সংখ্যা)। Byte address তিন ভাগে ভাঙে — | tag | index | block offset | — index ঘর বাছে, ঘরে রাখা tag মিললে আর valid bit ১ হলে hit. Miss তিন রকম (3 C's): compulsory (প্রথমবার ছোঁয়া), capacity (cache-এ এত ডেটা ধরেই না) আর conflict (জায়গা ছিল, কিন্তু ভুল ঘরে ভিড়)। এই পর্ব তৃতীয়টি নিয়ে — আর তার সমাধান থেকে জন্ম নেওয়া প্রশ্ন: ঘর ভরা থাকলে কাকে বাদ দেবেন?

একটি ছোট উদাহরণ ভাবুন। ৪টি ঘরের direct-mapped cache, আর একটি লুপ পালা করে block 0 আর block 8 পড়ছে (যেমন দুটি array-র একই অবস্থানের উপাদান, যাদের দূরত্ব cache-এর আকারের গুণিতক)। 0 mod 4 = 0, 8 mod 4 = 0 — দুজনেরই ঘর ০. প্রতিবার একজন অন্যজনকে বের করে দেয়, প্রতিটি প্রবেশ miss, অথচ ঘর ১, ২, ৩ খালি পড়ে আছে। Cache-এর আকার দোষী নয় — দোষী নিয়মটি, যা প্রতিটি block-কে একটিমাত্র ঘরে বেঁধে রেখেছে। একে বলে thrashing (দুই বা ততোধিক block-এর পালা করে একে অপরকে তাড়ানো)।

২ · Placement-এর বর্ণালি — direct-mapped, n-way আর fully associative

একটি cache-এ মোট B টি block-এর ঘর (cache line). এগুলোকে S টি set-এ ভাগ করা হয়, প্রতিটি set-এ n টি ঘর — প্রতিটি ঘরকে বলে একটি way. তাই B = S × n. নিয়ম:

Block address মানে byte address ÷ block size (offset বাদ দেওয়া অংশ)। Block টি সেই set-এর যেকোনো way-তে বসতে পারে। এই এক সূত্রেই পুরো বর্ণালি আসে — এমন cache-কে বলে n-way set-associative cache, আর n-কে বলে associativity:

অর্থাৎ direct-mapped হলো “১-way set-associative” আর fully associative cache হলো “B-way, ১টি set”. বাস্তবের প্রায় সব cache মাঝখানে — 2, 4, 8, 12 বা 16-way.

পাঠ্যবইয়ের তুলনা: 0, 8, 0, 6, 8

Patterson–Hennessy-র বইয়ের বিখ্যাত উদাহরণটি এখানে হাতে করা যাক। ৪টি block-এর cache, শুরুতে খালি, block address-এর ক্রম 0, 8, 0, 6, 8; set-associative অংশে replacement LRU (যে block সবচেয়ে বেশি সময় অব্যবহৃত, তাকে বাদ)। Set নির্ণয়: direct-mapped-এ mod 4 — 0 → 0, 8 → 0, 6 → 2; 2-way-তে mod 2 — তিনটিই set 0; fully associative-এ set একটিই। “পরে” চেপে তিনটি cache পাশাপাশি দেখুন:

1# 4-block cache, empty at start, LRU2read block 03read block 84read block 05read block 66read block 87# misses: 5 / 4 / 3

লক্ষ করুন, 2-way-এর ৫ নম্বর প্রবেশে miss হলো কারণ তিনটি block-ই একই set-এ পড়েছে — set-এ ঘর মাত্র ২টি। Associativity বাড়ালে conflict কমে, কিন্তু set-এর ভেতরে ঘর ভরা থাকলে কাকে বাদ দেওয়া হবে, তা-ও ফলকে বদলে দেয়। এই দুটি প্রশ্নই বাকি পর্বের বিষয়।

৩ · Associativity বাড়লে address-এর ভাগ কীভাবে বদলায়

Byte-addressed মেমরি, ৩২-বিট address (Module 8-এর সব উদাহরণের নিয়ম)। Block size 2^b byte হলে offset = b বিট। Set-এর সংখ্যা S = 2^s হলে index = s বিট। বাকি সব tag:

যুক্তি: একই set-এ যে block-গুলো পড়ে, তাদের block address-এর নিচের s বিট এক (কারণ mod 2^s মানে নিচের s বিট)। তাই set-এর ভেতরে আলাদা করে চেনার জন্য বাকি উঁচু বিটগুলো রাখতে হয় — সেটাই tag. মোট আকার আর block size স্থির রেখে n দ্বিগুণ করলে S অর্ধেক, s এক কমে; যে বিটটি index থেকে বেরোল, সেটি এখন set চেনাতে পারে না — তাই tag-এ যোগ হয়। Fully associative-এ S = 1, index = 0 — offset ছাড়া পুরো address-ই tag.

একটি সাধারণ মাপ ধরুন: ৩২ KiB data, ৬৪ B block — মোট ৩২৭৬৮ ÷ ৬৪ = ৫১২টি ঘর, offset = ৬ বিট। পাঁচটি সংগঠনে (সংখ্যাগুলো scratch script-এ মেলানো):

তিনটি জিনিস লক্ষ করার মতো। এক, way দ্বিগুণ হলে প্রতিটি tag ১ বিট লম্বা, তাই মোট tag storage প্রতি ধাপে ৫১২ বিট বাড়ে। দুই, comparator-এর সংখ্যা n-এর সমান, আর প্রতিটি আরও চওড়া। তিন, 8-way-এর ঘরে index + offset = ৬ + ৬ = ১২ বিট — ঠিক একটি ৪ KiB page-এর offset-এর সমান। এই কাকতালীয়-মনে-হওয়া মিলটি আসলে নকশার ইচ্ছাকৃত সিদ্ধান্ত; অংশ ৮-এ কারণ দেখবেন।

৪ · Hardware — n টি tag একসাথে তুলনা, n:1 mux আর CAM

Direct-mapped cache-এ index দিয়ে একটি ঘর পড়া হয়, একটি tag comparator বলে মিলল কি না। n-way-তে index দিয়ে একটি পুরো set পড়া হয় — n টি tag, n টি valid বিট আর (দ্রুত নকশায়) n টি data block, সবগুলো একই সময়ে। তারপর n টি comparator একসাথে কাজ করে। প্রতিটি comparator আসলে বিট ধরে ধরে XNOR আর সবগুলোর AND — অর্থাৎ ৩২-বিটের তুলনা নয়, শুধু tag-এর বিটগুলো। মিল আর valid-এর AND প্রতিটি way-এর জন্য একটি বিট দেয়; সঠিক নকশায় বড়জোর একটি ১ হয় (one-hot). এই n বিটের OR = hit, আর এরাই n:1 multiplexer-এর select — কোন way-এর data বেরোবে।

নিচের stepper-এ একটি সুনির্দিষ্ট উদাহরণ: ৩২ KiB, 4-way, ৬৪ B block (ভাগ ১৯ │ ৭ │ ৬). প্রথম load-এর address 0x00402A48: 0x00402A48 = 0x201 × 2¹³ + 41 × 2⁶ + 8, তাই tag 0x201, set 41, offset 8. দ্বিতীয় load 0x00752A70 একই set-এ পড়ে কিন্তু tag ভিন্ন:

1# 32 KiB, 4-way, 64 B: tag 19 │ index 7 │ offset 62lw x5, 0(x10)    # x10 = 0x00402A483set 41  way0: V=1 tag 0x1F34        way1: V=0 tag 0x201  (stale)5        way2: V=1 tag 0x2016        way3: V=1 tag 0x0C47lw x6, 0(x11)    # x11 = 0x00752A70

দামের হিসাব — hit time, জায়গা আর শক্তি

• Hit time: direct-mapped-এ data পড়া আর tag তুলনা সমান্তরালে চলে, ফলের data সরাসরি বেরোয় (ভুল হলে পরে ফেলে দেওয়া হয়)। n-way-তে data বেরোনোর আগে তুলনা শেষ হয়ে mux-এর select তৈরি হতে হয় — critical path-এ একটি comparator আর একটি n:1 mux যোগ হয়। n বাড়লে mux-এর স্তরও বাড়ে (মোটামুটি log₂n স্তর)।
• জায়গা: n টি comparator, আরও লম্বা tag (অংশ ৩-এর টেবিল), replacement-এর বিট, আর চওড়া mux.
• শক্তি: প্রতিটি প্রবেশে n টি tag আর (দ্রুত নকশায়) n টি data block পড়া হয়, অথচ কাজে লাগে একটি। এই কারণে বড়, ধীর cache (L2, L3) প্রায়ই আগে শুধু tag পড়ে, মিল জানার পরে একটিমাত্র way-এর data পড়ে — এক cycle বেশি লাগে, কিন্তু শক্তি অনেক কম। L1 সময় বাঁচাতে দুটি একসাথে পড়ে।

Fully associative আর CAM

Fully associative-এ index নেই — প্রতিটি ঘরের tag-কে খোঁজা tag-এর সাথে তুলনা করতে হয়, অর্থাৎ প্রতিটি ঘরে একটি comparator. এটি বানানো হয় CAM (content-addressable memory) দিয়ে: সাধারণ SRAM-এ ঠিকানা দিলে data আসে; CAM-এ data (tag) দিলে বলে কোন সারিতে সেটি আছে। প্রতিটি CAM cell-এ রাখার বিটের পাশে তুলনার transistor থাকে, তাই সাধারণ ৬-transistor SRAM cell-এর চেয়ে বড় (প্রায় ৯–১০ transistor-এর নকশা প্রচলিত), আর প্রতিটি খোঁজে সব সারির match line একসাথে চার্জ-ডিসচার্জ হয় — শক্তিখেকো। তাই CAM শুধু ছোট কাঠামোয়: TLB (L1 TLB প্রায়ই কয়েক ডজন entry-র, অনেক নকশায় fully associative — পর্ব ৫০), victim cache (অংশ ৭), branch target buffer-এর কিছু রূপ, আর নেটওয়ার্ক router-এর lookup table. ৫১২ ঘরের fully associative L1 data cache প্রায় দেখা যায় না।

৫ · Replacement policy — ঘর ভরা থাকলে কাকে বাদ দেবেন

Direct-mapped-এ প্রশ্নটিই ওঠে না — ঘর একটিই। n-way-তে miss হলে, আর set-এর সব way valid থাকলে, একজনকে বের করতে হয় — যাকে বের করা হয় সে victim. এই নিয়মই replacement policy. আদর্শ নিয়ম জানা: যে block সবচেয়ে দেরিতে আবার লাগবে, তাকে বাদ দেওয়া। কিন্তু hardware ভবিষ্যৎ জানে না, তাই অতীত দেখে অনুমান করে।

LRU — সবচেয়ে বেশি সময় অব্যবহৃতকে বাদ

LRU (least recently used) temporal locality-র ওপর বাজি ধরে: যা অনেকক্ষণ ছোঁয়া হয়নি, তা সম্ভবত শিগগির লাগবে না। নিখুঁত LRU-র জন্য set-এর n টি block-এর পুরো “সাম্প্রতিকতার ক্রম” মনে রাখতে হয়। n টি block-এর সম্ভাব্য ক্রম n! টি, তাই অন্তত ⌈log₂(n!)⌉ বিট লাগে — এর কমে সব ক্রম আলাদা করা অসম্ভব (pigeonhole নীতি)।

বিটের সংখ্যাই একমাত্র সমস্যা নয়। প্রতিটি hit-এও অবস্থা বদলাতে হয় (ক্রম নতুন করে সাজানো), আর ৫ বিটের ঘন encoding থেকে “কে সবচেয়ে পুরোনো” বের করার logic জটিল। তাই 2-way-তে নিখুঁত LRU সস্তা (১ বিট: “কোন way শেষে ছোঁয়া”), 4-way পর্যন্ত চলে, কিন্তু 8-way বা বেশিতে প্রায় সবাই অনুমিত LRU ব্যবহার করে।

Pseudo-LRU tree — n − 1 বিটে প্রায় LRU

Tree pseudo-LRU (PLRU) way-গুলোকে একটি binary tree-এর পাতা হিসেবে সাজায়। 4-way-তে ৩টি বিট: b1 (root: বাঁ জোড়া way0–1 নাকি ডান জোড়া way2–3), b2 (way0 নাকি way1), b3 (way2 নাকি way3). এই পর্বের নিয়ম: বিট ০ মানে victim বাঁ দিকে, ১ মানে ডানে। দুটি কাজ:

• Victim খোঁজা: root থেকে বিট অনুযায়ী নিচে নামা। যেমন b1 b2 b3 = 1 0 0: root 1 → ডান জোড়া, b3 = 0 → বাঁ — victim way2.
• প্রবেশে হালনাগাদ (hit বা নতুন block বসানো): ছোঁয়া way-এর পথের প্রতিটি বিটকে সেই way থেকে উল্টো দিকে ঘোরানো। way1 ছোঁয়া হলে: সে বাঁ জোড়ায়, তাই b1 = 1 (ডান দিক নির্দেশ); জোড়ার ভেতরে সে ডানে, তাই b2 = 0. b3 অপরিবর্তিত।

প্রতিটি প্রবেশে শুধু log₂n টি বিট বদলায় — সরল, দ্রুত। কিন্তু এটি নিখুঁত LRU নয়: tree শুধু বলে “কোন অর্ধেক কম সাম্প্রতিক”, পুরো ক্রম নয়। নিচের stepper-এ একটি set-এ A B C D B E A F ক্রম (শুরুতে সব বিট ০, খালি way আগে ক্রমানুসারে ভরা হয়) — আর কোথায় PLRU নিখুঁত LRU-র থেকে আলাদা সিদ্ধান্ত নেয়:

1# one 4-way set; b1 = root, b2 = ways 0/1, b3 = ways 2/32A B C D   # fill ways 0, 1, 2, 33B         # hit in way 14E         # miss: PLRU victim?5A         # hit?6F         # miss: PLRU victim?

FIFO, random আর NRU

• FIFO (first in, first out): যে সবচেয়ে আগে ঢুকেছে সে যাবে — hit-এ কিছু বদলায় না, তাই একটি ঘুরন্ত pointer-ই যথেষ্ট (log₂n বিট)। দুর্বলতা: খুব ব্যস্ত block-ও তার পালা এলে বের হয়।
• Random: একটি সস্তা pseudo-random generator (যেমন LFSR — কয়েকটি flip-flop আর XOR) দিয়ে victim বাছাই। কোনো অবস্থা মনে রাখতে হয় না। বড় cache-এ LRU-র সাথে পার্থক্য প্রায়ই ছোট বলে পাঠ্যবইয়ের মাপে দেখা যায়; কিছু ARM core-এর cache-এ pseudo-random replacement একটি বিকল্প হিসেবে ছিল বলে জানা যায়।
• NRU (not recently used) বা clock-ধাঁচ: প্রতিটি way-এ একটি “ব্যবহৃত” বিট; ছোঁয়া হলে ১. Victim = প্রথম যে way-এর বিট ০; সবগুলো ১ হলে বাকিদের বিট মুছে আবার শুরু। n বিটে মোটা দাগের LRU — OS-এর page replacement-এর clock algorithm-এর হুবহু আত্মীয় (অপারেটিং সিস্টেম কোর্সের page replacement).

Belady-র OPT — যা কেউ বানাতে পারে না, কিন্তু সবাই মাপে

১৯৬৬ সালে IBM-এর Laszlo Belady virtual memory-র জন্য replacement নিয়ে একটি বিখ্যাত গবেষণা প্রকাশ করেন; সেখান থেকে পরিচিত নিয়মটি OPT বা MIN: যে block-এর পরের ব্যবহার সবচেয়ে দূরে (বা কখনো না), তাকে বাদ দেওয়া। এটি প্রমাণিতভাবে সর্বনিম্ন miss দেয়। যুক্তির সারকথা (exchange argument): ধরুন কোনো নিয়ম P প্রথমবার OPT-এর থেকে আলাদা সিদ্ধান্ত নেয় — Y-এর বদলে X-কে বাদ দেয়, যদিও X আবার লাগবে Y-এর আগে। এখন P′ নামের একটি নিয়ম কল্পনা করুন, যা এই মুহূর্তে OPT-এর মতো Y-কে বাদ দেয় আর তারপর P-কে নকল করে, শুধু X আর Y-এর ভূমিকা অদলবদল করে। X-এর পরের ব্যবহারে P miss করে কিন্তু P′ hit পায়; আর Y আবার লাগার আগেই P′ নিজের cache-কে P-এর cache-এর সাথে মিলিয়ে নিতে পারে, কখনো P-এর চেয়ে বেশি miss না করে। তাই প্রতিটি পার্থক্য OPT-এর দিকে বদলালে miss বাড়ে না — বারবার এই বদল করলে OPT-এ পৌঁছানো যায়, তাই OPT-ই সর্বনিম্ন। OPT-এর জন্য পুরো ভবিষ্যৎ লাগে, তাই hardware-এ অসম্ভব; কিন্তু একটি trace রেকর্ড করে offline চালালে জানা যায় “কোনো নিয়ম এর চেয়ে ভালো পারবে না” — নতুন policy-র মাপকাঠি।

নিচের simulator চারটি policy একই কোডে চালায়: set = block mod sets, খালি way আগে ভরা, LRU আর FIFO একটি “বয়স” দিয়ে (LRU প্রতিটি hit-এ বয়স নতুন করে, FIFO শুধু ঢোকার সময়), PLRU উপরের tree-নিয়মে, আর RAND একটি নির্দিষ্ট seed-এর generator-এ — তাই প্রতিবার একই ফল। প্রথম অংশ 0, 8, 0, 6, 8 ক্রম তিন সংগঠনে চালিয়ে miss-গুলোকে 3 C's-এ ভাগ করে; দ্বিতীয় অংশ একটি চক্রাকার ক্রম:

// Set-associative cache simulator. Input: block addresses. set = block mod sets. Policies: LRU, FIFO, RAND, PLRU.
function sim(trace, sets, ways, policy, show) {
  const S = Array.from({ length: sets }, () => ({ blk: [], age: [], bits: [] }));
  let seed = 7, t = 0, miss = 0;
  const rnd = n => (seed = (seed * 1103515245 + 12345) % 2147483648) % n;       // seeded: same "random" every run
  const victimPLRU = b => { let n = 1; while (n < ways) n = 2 * n + (b[n] || 0); return n - ways; };
  const touchPLRU = (b, w) => { for (let n = w + ways; n > 1; n >>= 1) b[n >> 1] = n & 1 ? 0 : 1; }; // point away from w
  for (const blk of trace) {
    const set = blk % sets, s = S[set]; t++;
    let w = s.blk.indexOf(blk); const hit = w >= 0;
    if (!hit) {
      miss++;
      if (s.blk.length < ways) w = s.blk.length;                                 // an empty way: just fill it
      else if (policy === "RAND") w = rnd(ways);
      else if (policy === "PLRU") w = victimPLRU(s.bits);
      else w = s.age.indexOf(Math.min(...s.age));                                // LRU and FIFO: smallest age
      s.blk[w] = blk; s.age[w] = t;                                              // FIFO keeps the fill time
    } else if (policy === "LRU") s.age[w] = t;                                   // LRU refreshes on every hit
    if (policy === "PLRU") touchPLRU(s.bits, w);
    if (show) console.log(`  block ${String(blk).padStart(2)} -> set ${set}  ${hit ? "hit " : "MISS"}  set ${set} = [${s.blk.join(", ")}]`);
  }
  return miss;
}
const classic = [0, 8, 0, 6, 8], compulsory = new Set(classic).size;
const fa = sim(classic, 1, 4, "LRU", false);
for (const [name, sets, ways] of [["direct-mapped (4 sets x 1 way)", 4, 1], ["2-way (2 sets x 2 ways)", 2, 2], ["fully associative (1 set x 4 ways)", 1, 4]]) {
  console.log(name);
  const m = sim(classic, sets, ways, "LRU", true);
  console.log(`  misses = ${m}: compulsory ${compulsory}, capacity ${fa - compulsory}, conflict ${m - fa}`);
}
const cyclic = []; for (let r = 0; r < 4; r++) cyclic.push(0, 1, 2, 3, 4);      // 5 blocks cycling through 4 ways
console.log("cyclic 0..4 x 4 (20 accesses), fully associative, 4 ways:");
console.log("  " + ["LRU", "FIFO", "PLRU", "RAND"].map(p => `${p} ${sim(cyclic, 1, 4, p, false)} misses`).join(" | "));

direct-mapped (4 sets x 1 way)
  block  0 -> set 0  MISS  set 0 = [0]
  block  8 -> set 0  MISS  set 0 = [8]
  block  0 -> set 0  MISS  set 0 = [0]
  block  6 -> set 2  MISS  set 2 = [6]
  block  8 -> set 0  MISS  set 0 = [8]
  misses = 5: compulsory 3, capacity 0, conflict 2
2-way (2 sets x 2 ways)
  block  0 -> set 0  MISS  set 0 = [0]
  block  8 -> set 0  MISS  set 0 = [0, 8]
  block  0 -> set 0  hit   set 0 = [0, 8]
  block  6 -> set 0  MISS  set 0 = [0, 6]
  block  8 -> set 0  MISS  set 0 = [8, 6]
  misses = 4: compulsory 3, capacity 0, conflict 1
fully associative (1 set x 4 ways)
  block  0 -> set 0  MISS  set 0 = [0]
  block  8 -> set 0  MISS  set 0 = [0, 8]
  block  0 -> set 0  hit   set 0 = [0, 8]
  block  6 -> set 0  MISS  set 0 = [0, 8, 6]
  block  8 -> set 0  hit   set 0 = [0, 8, 6]
  misses = 3: compulsory 3, capacity 0, conflict 0
cyclic 0..4 x 4 (20 accesses), fully associative, 4 ways:
  LRU 20 misses | FIFO 20 misses | PLRU 19 misses | RAND 11 misses

OPT-কে আলাদা করে দেখা যাক। নিচের simulator প্রতিটি miss-এ ভবিষ্যতের trace দেখে সবচেয়ে দূরের পরের-ব্যবহারওয়ালা block বাদ দেয়, আর কারণ ছাপে। ক্রমটি virtual memory-র বইয়ের পরিচিত 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 — ৩টি ঘরের fully associative cache-এ (বা ৩-way-এর একটি set-এ):

// Belady's OPT (MIN): on a miss, evict the block whose next use is farthest in the future (or never).
// Needs the whole future trace, so real hardware cannot build it; it is the lower bound for any policy.
function run(trace, cap, policy, show) {
  let cache = [], miss = 0;
  trace.forEach((b, i) => {
    const hit = cache.includes(b);
    let note = "";
    if (hit) { if (policy === "LRU") cache = cache.filter(x => x !== b).concat(b); }   // LRU order: oldest first
    else {
      miss++;
      if (cache.length === cap) {
        let v;
        if (policy === "LRU") v = cache[0];
        else {
          const next = x => { const j = trace.indexOf(x, i + 1); return j < 0 ? Infinity : j; };
          v = cache.reduce((a, x) => (next(x) > next(a) ? x : a));
          note = `evict ${v} (next use ${next(v) === Infinity ? "never" : "at #" + next(v)})`;
        }
        if (policy === "LRU") note = `evict ${v} (least recently used)`;
        cache = cache.filter(x => x !== v);
      }
      cache.push(b);
    }
    if (show) console.log(`#${String(i).padStart(2)} ${b}: ${hit ? "hit " : "MISS"} [${[...cache].sort().join(" ")}] ${note}`);
  });
  return miss;
}
const T = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5];
console.log("trace " + T.join(",") + ", 3 blocks, OPT:");
run(T, 3, "OPT", true);
console.log(`3 blocks: OPT ${run(T, 3, "OPT")} misses, LRU ${run(T, 3, "LRU")} misses`);
const cyc = []; for (let r = 0; r < 4; r++) cyc.push(0, 1, 2, 3, 4);
console.log(`cyclic 0..4 x 4, 4 blocks: OPT ${run(cyc, 4, "OPT")} misses, LRU ${run(cyc, 4, "LRU")} misses`);

trace 1,2,3,4,1,2,5,1,2,3,4,5, 3 blocks, OPT:
# 0 1: MISS [1] 
# 1 2: MISS [1 2] 
# 2 3: MISS [1 2 3] 
# 3 4: MISS [1 2 4] evict 3 (next use at #9)
# 4 1: hit  [1 2 4] 
# 5 2: hit  [1 2 4] 
# 6 5: MISS [1 2 5] evict 4 (next use at #10)
# 7 1: hit  [1 2 5] 
# 8 2: hit  [1 2 5] 
# 9 3: MISS [2 3 5] evict 1 (next use never)
#10 4: MISS [3 4 5] evict 2 (next use never)
#11 5: hit  [3 4 5] 
3 blocks: OPT 7 misses, LRU 10 misses
cyclic 0..4 x 4, 4 blocks: OPT 8 misses, LRU 20 misses

৬ · LRU-র ফাঁদ — চক্রাকার প্রবেশ, আর আধুনিক policy

কেন চক্রাকার ক্রমে LRU প্রতিবার miss করে, তা হাতে দেখা সহজ। ৪টি way, ক্রম 0 1 2 3 4 0 1 2 3 4 … প্রথম চারটি ঢুকল। 4 এল — LRU সবচেয়ে পুরোনো 0-কে বাদ দিল। পরের প্রবেশ ঠিক 0! সে miss করে 1-কে বাদ দেয় — আর পরের প্রবেশ 1. প্রতিবার যাকে বাদ দেওয়া হয়, ঠিক তাকেই পরের মুহূর্তে লাগে। LRU-র যুক্তি (“পুরোনো জিনিস আর লাগবে না”) চক্রাকার প্রবেশে ঠিক উল্টো সত্য: সবচেয়ে পুরোনোটিই সবচেয়ে আগে আবার লাগবে। সাধারণভাবে, কাজের ডেটা (working set) চক্রাকারে k টি block আর set-এ n টি way হলে, k ≤ n-এ প্রথম ঘুরের পরে সব hit, কিন্তু k = n + 1 হলেই hit শূন্য — একটি block বেশি হলেই খাড়া পাহাড় থেকে পতন।

Random এখানে ভালো কারণ সে মাঝে মাঝে “ভুল” (সাম্প্রতিক) block-কে বাদ দেয়, আর পুরোনোগুলোর কিছু টিকে যায় — সেগুলো hit দেয়। OPT ভালোভাবে করে একই কাজ: কয়েকটি block স্থায়ীভাবে রেখে বাকিদের মধ্যে ঘোরানো। এই ধরনের প্রবেশ বাস্তবে খুব সাধারণ — একটি বড় array-র ওপর বারবার লুপ, যার আকার cache-এর চেয়ে একটু বড়; বা একবার পড়া “streaming” ডেটা (video frame, বড় ফাইল scan) যা দরকারি ছোট working set-কে ঠেলে বের করে দেয়।

আধুনিক ধারণা — কোথায় বসাবেন, শুধু কাকে বাদ দেবেন তা নয়

২০০০-এর দশকের শেষভাগ থেকে গবেষণায় একটি নতুন দৃষ্টিভঙ্গি জনপ্রিয় হয়: নতুন block-কে সবসময় “সবচেয়ে সাম্প্রতিক” অবস্থানে না বসিয়ে, কখনো “শিগগির বাদ যাবে” অবস্থানে বসানো। তাহলে একবার ব্যবহারের streaming ডেটা দ্রুত বেরিয়ে যায়, আর বারবার-লাগা block-গুলো টিকে থাকে। Adaptive insertion-এর ধারণা (Qureshi ও সহকর্মীদের ২০০৭-এর দিকের গবেষণায় পরিচিত, DIP নামে) কয়েকটি নমুনা set-এ দুই নিয়ম চালিয়ে দেখে কোনটি ভালো, আর বাকি set-এ সেটি প্রয়োগ করে (set dueling). RRIP (re-reference interval prediction; Jaleel ও সহকর্মীদের ২০১০-এর দিকের গবেষণা) প্রতিটি block-এ ২–৩ বিটের একটি “আবার কত দেরিতে লাগবে” অনুমান রাখে — NRU-র একটি বহু-বিট রূপ। কিছু নতুন Intel CPU-র শেষ স্তরের cache-এ এ ধরনের adaptive আচরণ দেখা যায় বলে স্বাধীন পরিমাপ-ভিত্তিক গবেষণা বলেছে; নির্মাতারা সাধারণত সঠিক policy প্রকাশ করে না। আরও সাম্প্রতিক গবেষণা (যেমন Hawkeye) অতীতের trace-এ OPT কী করত, তা থেকে শিখে অনুমান করার চেষ্টা করে।

৭ · Miss rate বনাম associativity, way prediction আর victim cache

Associativity বাড়ালে conflict miss কমে, কিন্তু লাভ দ্রুত ফুরায়: 1 থেকে 2-way-তে লাফটি সাধারণত বড়, 2 থেকে 4-way-তে ছোট, তারপর আরও ছোট। Hennessy–Patterson-এর বইয়ে SPEC benchmark-এর মাপ থেকে দুটি rule of thumb প্রচলিত — নিয়ম নয়, অনেক কাজের চাপে দেখা প্রবণতা:

• “2:1 cache rule” — N আকারের direct-mapped cache-এর miss rate মোটামুটি N/2 আকারের 2-way cache-এর সমান।
• 8-way প্রায় fully associative-এর কাছাকাছি — বেশিরভাগ কাজে 8-way-এর পরে conflict miss প্রায় নগণ্য; বাকি miss-এর বেশিরভাগ capacity আর compulsory.

এর সাথে hit time-এর দাম যোগ করলে ছবি পূর্ণ হয়: miss rate-এ সামান্য লাভের জন্য যদি প্রতিটি hit-এ একটি বাড়তি cycle লাগে, তবে মোট গড় সময় বেড়েও যেতে পারে। কতটা, তার হিসাব (AMAT = hit time + miss rate × miss penalty) পরের পর্বে — পর্ব ৪৭ (Cache-এর পারফরম্যান্স)।

Miss-এর শ্রেণিভাগ আবার — fully associative-কে মাপকাঠি ধরে

3 C's একটি নির্দিষ্ট পদ্ধতিতে মাপা হয় (পর্ব ৪৫-এর সংজ্ঞার পরিমাপযোগ্য রূপ): একই trace তিনটি cache-এ চালানো —

• Compulsory = অসীম বড় cache-এর miss (প্রতিটি আলাদা block-এর প্রথম ছোঁয়া)।
• Capacity = একই আকারের fully associative (LRU) cache-এর miss − compulsory.
• Conflict = আসল cache-এর miss − একই আকারের fully associative-এর miss.

অর্থাৎ conflict miss হলো সেগুলো, যা শুধু placement-এর বাঁধনের জন্য হয় — একই আকারে বাঁধন তুলে দিলে থাকত না। উপরের simulator ঠিক এভাবেই ৫ = ৩ + ০ + ২ ভাগ করেছে। একটি সূক্ষ্মতা: fully associative LRU নিজেই নিখুঁত নয় (চক্রাকার ক্রমে সে খুব খারাপ), তাই কখনো কোনো set-associative cache তার চেয়ে কম miss করে — তখন “conflict” সংখ্যা ঋণাত্মক আসে। এটি পদ্ধতির সীমাবদ্ধতা, ভুল নয়।

Way prediction — n-way-এর miss rate, direct-mapped-এর গতি

Way prediction-এ প্রতিটি set-এর সাথে কয়েকটি বিট অনুমান রাখে “পরের প্রবেশ সম্ভবত কোন way-তে”। শুধু সেই way-এর data আর tag আগে পড়া হয় — অনুমান ঠিক হলে direct-mapped-এর মতো দ্রুত আর কম শক্তির hit; ভুল হলে বাকি way দেখতে এক বা কয়েক cycle বেশি। পুরোনো Alpha 21264-এর instruction cache-এ এ ধরনের অনুমানের কথা পাঠ্যবইয়ে আসে; AMD-র কিছু নতুন core-এর L1 data cache-এ virtual address-এর একটি ছোট hash (μtag) দিয়ে way অনুমানের বর্ণনাও নির্মাতার নথিতে পাওয়া যায়। ভাবনাটি পর্ব ৩৭-এর branch prediction-এর আত্মীয় (Branch prediction).

Victim cache — বের হওয়া block-এর জন্য ছোট একটি আশ্রয়

Norman Jouppi ১৯৯০ সালের একটি পরিচিত গবেষণাপত্রে direct-mapped cache-এর পাশে মাত্র কয়েকটি (১ থেকে ৫টির মতো) ঘরের একটি ছোট fully associative victim cache-এর প্রস্তাব দেন: মূল cache থেকে বের হওয়া প্রতিটি block এখানে আসে। মূল cache-এ miss কিন্তু victim cache-এ hit হলে দুটি block অদলবদল — মেমরিতে যেতে হয় না। 0, 8, 0, 8 ধরনের thrashing-এ এটি প্রায় 2-way-এর কাজ করে, অথচ মূল cache direct-mapped-এর দ্রুততা রাখে। গবেষণাপত্রটিতে মাত্র কয়েকটি ঘরেই direct-mapped cache-এর conflict miss-এর বড় অংশ সরিয়ে দেওয়ার ফল দেখানো হয়েছিল। ধারণাটি পরে বহু রূপে বেঁচে আছে — যেমন কিছু নকশায় শেষ স্তরের cache-কে ওপরের স্তরের “victim” হিসেবে চালানো (L2 থেকে বের হওয়া block L3-এ যায়), যার আলোচনা পর্ব ৪৭-এ।

৮ · বাস্তবের L1 — কেন 8–12-way, VIPT আর একটি সত্যিকার cache-এর way গোনা

আজকের desktop আর server CPU-র L1 data cache সাধারণত ৩২–৪৮ KiB, 8 থেকে 12-way set-associative, ৬৪ B line বলে নির্মাতাদের প্রকাশিত বিবরণে পাওয়া যায় (নির্দিষ্ট মান প্রজন্ম আর core-ভেদে বদলায়)। L2 আর L3-এ way সাধারণত L1-এর সমান বা বেশি (প্রায়ই ৮–১৬ বা তার বেশি)। L1 কেন আরও বড় বা fully associative নয়? একটি বড় কারণ hit time আর শক্তি (অংশ ৪); আরেকটি কারণ virtual memory.

VIPT — virtual index, physical tag

প্রোগ্রাম virtual address দেয়; tag তুলনার জন্য physical address লাগে, যা TLB থেকে আসে (পর্ব ৫০, Virtual memory-র hardware). TLB শেষ হওয়া পর্যন্ত অপেক্ষা করলে L1-এর সময় বাড়ে। কৌশল: VIPT (virtually indexed, physically tagged) — set বাছাইয়ের index নেওয়া হয় virtual address থেকে, আর একই সময়ে TLB physical page number বের করে; set-এর tag-গুলো পড়া শেষ হতেই physical tag তুলনা। এটি নিরাপদ হয় একটি শর্তে: index আর offset-এর সব বিট page offset-এর ভেতরে পড়তে হবে, কারণ page offset-এর বিট virtual আর physical-এ একই। ৪ KiB page-এ page offset ১২ বিট, তাই index + offset ≤ ১২ —

8-way × ৪ KiB = ৩২ KiB; 12-way × ৪ KiB = ৪৮ KiB. তাই L1 বড় করতে হলে way বাড়াতে হয় — set বাড়ানো যায় না। এটিই ব্যাখ্যা করে কেন x86 L1 data cache বহু বছর ৩২ KiB 8-way-এ ছিল, আর বড় হতে গিয়ে 12-way হয়েছে। Apple-এর কিছু ARM chip ১৬ KiB page ব্যবহার করে, আর তাদের L1 data cache অনেক বড় (১২৮ KiB পর্যন্ত বলে বর্ণনা পাওয়া যায়) — একই সূত্রে ১৬ KiB × ৮ = ১২৮ KiB. শর্ত ভাঙলে একই physical block দুটি ভিন্ন set-এ বসতে পারে (synonym বা alias সমস্যা), যা সামলাতে বাড়তি hardware লাগে।

নিজের হাতে মাপা — একই set-এ K টি block

প্রথমে runner-এর (একটি shared virtual machine) Linux sysfs থেকে cache-এর সংগঠন — শুধু level, type, size, way, line আর set; অন্য কোনো তথ্য ছাপা হয় না:

# Cache organisation of CPU 0, read from Linux sysfs (only these fields are printed)
d=/sys/devices/system/cpu/cpu0/cache
if [ ! -d "$d" ]; then echo "sysfs cache info নেই"; exit 0; fi
printf "%-6s %-12s %8s %5s %5s %6s %10s\n" level type size ways line sets "way size"
for c in "$d"/index*; do
  lv=$(cat "$c/level" 2>/dev/null || echo "?")
  ty=$(cat "$c/type" 2>/dev/null || echo "?")
  sz=$(cat "$c/size" 2>/dev/null || echo "?")
  wy=$(cat "$c/ways_of_associativity" 2>/dev/null || echo "?")
  ln=$(cat "$c/coherency_line_size" 2>/dev/null || echo "?")
  st=$(cat "$c/number_of_sets" 2>/dev/null || echo "?")
  ws="?"
  if [[ "$st" =~ ^[0-9]+$ && "$ln" =~ ^[0-9]+$ ]]; then ws="$(( st * ln / 1024 ))K"; fi
  printf "L%-5s %-12s %8s %5s %5s %6s %10s\n" "$lv" "$ty" "$sz" "$wy" "$ln" "$st" "$ws"
done
command -v getconf >/dev/null && getconf -a 2>/dev/null | grep -E '^LEVEL1_DCACHE_(SIZE|ASSOC|LINESIZE)' || echo "getconf নেই"

level  type             size  ways  line   sets   way size
L1     Data              32K     8    64     64         4K
L1     Instruction       32K     8    64     64         4K
L2     Unified          512K     8    64   1024        64K
L3     Unified        16384K    16    64  16384      1024K
LEVEL1_DCACHE_SIZE                 32768
LEVEL1_DCACHE_ASSOC                8
LEVEL1_DCACHE_LINESIZE             64

এবার মেপে দেখা যাক। ৪০৯৬ byte দূরে দূরে রাখা address-এর index-এর বিট (৬–১১) একই, তাই তারা সবাই L1-এর একই set-এ পড়ে। প্রোগ্রামটি K টি এমন block একটি বৃত্তে জোড়ে (প্রতিটি পরেরটির address রাখে — pointer chasing, যাতে প্রতিটি load আগেরটির ফলের জন্য অপেক্ষা করে আর CPU একসাথে অনেক load চালিয়ে সময় লুকাতে না পারে), তারপর বৃত্তে ঘোরে। K ≤ way হলে সব block set-এ ধরে; K = way + 1 হলেই অংশ ৬-এর চক্রাকার ফাঁদ:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define STRIDE 4096                 /* 4 KiB apart: same L1 set if L1 has 64 sets of 64-byte lines */
#define MAXK 32
#define STEPS 10000000L
static double now(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t); return t.tv_sec + t.tv_nsec * 1e-9; }
int main(void) {
    char *buf = aligned_alloc(4096, (size_t)MAXK * STRIDE);
    if (!buf) return 1;
    const int ks[] = {2, 4, 6, 7, 8, 9, 10, 12, 16, 24, 32};
    double base = 0;
    void *sink = 0;
    for (int n = 0; n < (int)(sizeof ks / sizeof ks[0]); n++) {
        int K = ks[n];
        for (int i = 0; i < K; i++)            /* K blocks in a ring: block i points to block i+1 */
            *(char **)(buf + (size_t)i * STRIDE) = buf + (size_t)((i + 1) % K) * STRIDE;
        double best = 1e9;
        for (int r = 0; r < 5; r++) {          /* best of 5 runs: less noise from the shared machine */
            register char **p = (char **)buf;
            double t = now();
            for (register long s = 0; s < STEPS; s++) p = (char **)*p;   /* each load needs the previous one */
            t = now() - t;
            if (t < best) best = t;
            sink = p;
        }
        double ns = best / STEPS * 1e9;
        if (n == 0) base = ns;
        printf("K = %2d blocks in one set: %5.2f ns/access  (x%.1f)\n", K, ns, ns / base);
    }
    printf("%s\n", sink ? "done" : "?");
    free(buf);
    return 0;
}

K =  2 blocks in one set:  1.64 ns/access  (x1.0)
K =  4 blocks in one set:  1.67 ns/access  (x1.0)
K =  6 blocks in one set:  1.60 ns/access  (x1.0)
K =  7 blocks in one set:  1.60 ns/access  (x1.0)
K =  8 blocks in one set:  1.60 ns/access  (x1.0)
K =  9 blocks in one set:  4.52 ns/access  (x2.8)
K = 10 blocks in one set:  5.21 ns/access  (x3.2)
K = 12 blocks in one set:  4.89 ns/access  (x3.0)
K = 16 blocks in one set:  4.78 ns/access  (x2.9)
K = 24 blocks in one set:  4.88 ns/access  (x3.0)
K = 32 blocks in one set:  5.14 ns/access  (x3.1)
done

৯ · AI-এর যুগে cache associativity

AI টুল cache-এর ধারণা ভালো বোঝায়, কিন্তু এই বিষয়ের প্রায় সব পরীক্ষার প্রশ্ন বিট গোনা আর trace চালানো — আর সেখানেই সবচেয়ে বেশি ভুল হয়। প্রচলিত ভুলগুলো:

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

• tag + index + offset যোগ করে address-এর মোট বিট পেয়েছি, আর index কমেছে log₂(way) বিট
• Set বের করতে set-এর সংখ্যা দিয়ে mod করা হয়েছে, way দিয়ে নয়
• Trace-টি এই পর্বের simulator-এ (বা নিজের ছোট স্ক্রিপ্টে) চালিয়ে miss-এর সংখ্যা মিলিয়েছি
• LRU-তে প্রতিটি hit-এ ক্রম বদলেছে, FIFO-তে বদলায়নি — দুটো আলাদা করে দেখেছি
• PLRU-র বিটের নিয়ম (০ = কোন দিক) প্রশ্নের নিয়মের সাথে মিলিয়েছি
• কোনো chip-এর cache-এর মাপ থাকলে নির্মাতার নথিতে বা নিজের machine-এ sysfs/lscpu দিয়ে মিলিয়েছি