ক্যাপস্টোন — একটি RISC-V CPU simulator বানানো

১ · ক্যাপস্টোনের মানচিত্র — কী বানাবেন, কোন পর্ব কোথায় লাগবে

এই কোর্সে আপনি একটি CPU-কে টুকরো টুকরো করে দেখেছেন: instruction কীভাবে bit-এ লেখা হয়, datapath-এ কীভাবে চলে, pipeline-এ কোথায় আটকায়, আর মেমরি কেন ধীর। এই ক্যাপস্টোনে সেই সব টুকরো জুড়ে একটি কাজ করা যন্ত্র বানাবেন — software-এ। জিনিসটির নাম instruction set simulator (ISS): একটি প্রোগ্রাম, যা RISC-V-এর machine code পড়ে ঠিক সেই কাজ করে, যা একটি আসল RV32I CPU করত। তারপর তার পাশে দুটি মাপার যন্ত্র বসাবেন — একটি pipeline-এর সময় মাপবে, আরেকটি cache-এর।

1. 🔍M1 · Decoderword → fieldsপর্ব ২৭
3. ⚙️M2 · ISSregs, mem, PCপর্ব ২৬, ৩০, ৩২
5. 📜TracePC, ঠিকানাখাতা
7. ⏱️M3 · Pipelinecycles, CPIপর্ব ৩৫–৩৭
9. 🗄️M4 · CacheAMAT, মোট সময়পর্ব ৪৫–৪৭

প্রতিটি milestone কোন পর্বের ওপর দাঁড়িয়ে, নিচের টেবিলে দেখুন। কোনো জায়গায় আটকালে সেই পর্বে ফিরে যান — এই পর্বে নতুন তত্ত্ব প্রায় নেই, আছে জোড়া লাগানো আর যাচাই।

২ · নকশার সিদ্ধান্ত — data structure, পরীক্ষার প্রোগ্রাম আর golden model

ISS-এর ভেতরে কী থাকবে

একটি CPU-র architectural state — অর্থাৎ যা প্রোগ্রাম দেখতে পায় — RV32I-এ খুব ছোট: ৩২টি ৩২-বিটের register, একটি program counter (PC), আর মেমরি। তাই data structure-ও সরল:

• Register: Int32Array(32) — প্রতিটি ঘর ঠিক ৩২ বিট, আর JavaScript নিজেই প্রতিটি লেখায় মানকে ৩২ বিটে কেটে নেয় (যোগে overflow হলে wrap-around, পর্ব ০৫-এর মতো)। x0 আলাদা করে রক্ষা করতে হয়: লেখার সময় rd = 0 হলে লেখাই বাদ।
• মেমরি: Uint8Array(8192) — ৮ KiB, byte-ভিত্তিক, কারণ RISC-V-এর ঠিকানা byte-এর। একটি word পড়া মানে চারটি byte জোড়া লাগানো, ছোট ঠিকানার byte সবচেয়ে কম গুরুত্বের (little-endian, পর্ব ০৬)।
• PC: একটি সাধারণ সংখ্যা। প্রতিটি instruction-এর শেষে pc = next, যেখানে next সাধারণত pc + 4, আর শাখা বা লাফে অন্য কিছু।
• Trace: দুটি তালিকা — চলা প্রতিটি instruction-এর PC, আর প্রতিটি load/store-এর ঠিকানা। এগুলোই পরের milestone-গুলোর input.

একটি গুরুত্বপূর্ণ সিদ্ধান্ত: ISS-এ কোনো সময়ের ধারণা নেই। এটি একটি functional simulator — প্রতিটি instruction একবারে, পুরোপুরি চলে। Pipeline বা cache-এর হিসাব এর ভেতরে না ঢুকিয়ে আলাদা model-এ রাখা হয়, যা trace পড়ে। এই পদ্ধতিকে বলে trace-driven simulation. সুবিধা: ISS ছোট আর নির্ভুল রাখা সহজ, আর একই trace দিয়ে দশ রকম cache নকশা তুলনা করা যায়। সীমাবদ্ধতা: আসল CPU ভুল অনুমানের পথে (wrong path) কিছু instruction আংশিক চালায়, যা trace-এ নেই — এ নিয়ে ভাবনার প্রশ্ন ০২-এ।

পরীক্ষার প্রোগ্রাম — উত্তর আগে থেকে জানা

Simulator-এর প্রথম পরীক্ষা এমন একটি প্রোগ্রাম, যার উত্তর হাতে বের করা যায়। আমাদের প্রোগ্রাম C-তে এরকম:

int prefix(const int *a, int *c, int n) {   // n >= 1
    int s = 0;
    do { s += *a++; *c++ = s; } while (--n);   // c[i] = a[0] + ... + a[i]
    return s;
}
// main: a[i] = i + 1 (i = 0..9) at 0x100, c[] at 0x200;  a0 = prefix(a, c, 10) -> 55

a[] = 1, 2, …, 10 হলে c[] হবে 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, আর ফেরত মান ১ + ২ + … + ১০ = ১০ × ১১ ÷ ২ = ৫৫. প্রোগ্রামে আছে লুপ, load-store, একটি function call, stack pointer দিয়ে একটি callee-saved register (s0) রক্ষা, আর ra দিয়ে ফেরা — পর্ব ২৯ আর ৩০-এর প্রায় সবকিছু। Assembly রূপটি (যেভাবে একটি assembler পেলে লিখতেন):

00  lui   sp, 2            # sp = 0x2000, top of the 8 KiB memory
04  auipc a0, 0            # \  la a0, a    : a0 = pc + 0      = 0x4
08  addi  a0, a0, 252      # /               a0 = 0x4 + 252   = 0x100
0c  addi  a1, a0, 256      # a1 = &c = 0x200
10  addi  a2, zero, 10     # n = 10
14  jal   ra, prefix       # ra = 0x18, jump to 0x1c
18  ecall                  # our convention: stop here, result in a0
prefix:                    # a0 = a, a1 = c, a2 = n  ->  a0 = sum
1c  addi  sp, sp, -4
20  sw    s0, 0(sp)        # s0 is callee-saved: keep the caller's value
24  addi  s0, zero, 0      # s = 0
loop:
28  lw    t0, 0(a0)        # t0 = *a
2c  add   s0, s0, t0       # s += t0
30  sw    s0, 0(a1)        # *c = s
34  addi  a0, a0, 4        # a++
38  addi  a1, a1, 4        # c++
3c  addi  a2, a2, -1       # --n
40  bne   a2, zero, loop   # back to 0x28 while n != 0
44  addi  a0, s0, 0        # mv a0, s0 : return value
48  lw    s0, 0(sp)        # restore s0
4c  addi  sp, sp, 4
50  jalr  zero, 0(ra)      # ret

লক্ষ করুন la (load address) একটি pseudo-instruction: assembler এটিকে auipc + addi জোড়ায় ভাঙে — PC-relative ঠিকানা (পর্ব ২৮), যাতে প্রোগ্রাম যেকোনো ঠিকানায় বসানো যায়। হাতে যাচাই: dynamic instruction সংখ্যা = main-এর ৬ (jal পর্যন্ত) + prologue ৩ + লুপ ৭ × ১০ + epilogue ৪ + ecall ১ = ৮৪.

Golden model আর স্বাধীন যাচাই

পর্ব ১৯-এর প্রজেক্টে golden model দেখেছেন: একটি সরল, নির্ভরযোগ্য reference, যার সাথে বাকি সব মেলানো হয়। এখানে দুই স্তরে এর ব্যবহার:

1. Encoding-এর জন্য: প্রোগ্রামের hex word এই পর্বের decoder দিয়ে বানানো হয়নি; একটি আলাদা, স্বাধীন encoder script (Python-এ লেখা, field বসিয়ে বসিয়ে) দিয়ে বানানো। দুই দিক থেকে একই উত্তর এলে দুটির একসাথে একই ভুল করার সম্ভাবনা কম। নিজের প্রজেক্টে এই কাজটি করবে একটি আসল RISC-V assembler — যেমন GNU toolchain-এর as (সাধারণত -march=rv32i দিয়ে), আর objdump -d-এর disassembly আপনার decoder-এর আউটপুটের সাথে মেলাবেন।
2. আচরণের জন্য: আপনার ISS পরে নিজেই golden model হয় — পর্ব ১৪-এর Verilog-এ একটি CPU বানালে, প্রতিটি instruction-এর পরে Verilog CPU-র register আর ISS-এর register মেলানো যায়। এটিই co-simulation. আর আপনার ISS-কে যাচাই করার জন্য আছে বাইরের reference — অংশ ৭-এ।

৩ · Milestone ১ — decoder: bit কেটে field আর immediate

Decoder-এর কাজ পর্ব ২৭-এর encoding-এর ঠিক উল্টো। RISC-V-এর সুবিধা হলো register field-গুলো সব format-এ একই জায়গায়: opcode বিট ৬–০, rd ১১–৭, funct3 ১৪–১২, rs1 ১৯–১৫, rs2 ২৪–২০, funct7 ৩১–২৫. তাই decoder প্রথমেই সব field কেটে নিতে পারে — কোন format, সেটা না জেনেই। কোন field-এর অর্থ আছে, তা পরে opcode বলে দেয়। Bit কাটার কৌশল একটাই — ডানে সরানো, তারপর mask (C-তে একই কাজ: bitwise operation):

কঠিন অংশ immediate. পাঁচ রকম format-এ immediate-এর বিট পাঁচ রকমভাবে ছড়ানো, যাতে hardware-এ rs1, rs2, rd-এর তার কখনো সরাতে না হয় আর sign bit সবসময় বিট ৩১-এ থাকে:

জোড়া লাগানোর পরে n বিটের মানটিকে ৩২ বিটে sign-extend করতে হয় (পর্ব ০৫): সবচেয়ে উঁচু বিট ১ হলে বাকি সব উঁচু বিট ১. JavaScript-এ এক লাইনের কৌশল: (v << (32 − n)) >> (32 − n) — বাঁয়ে সরিয়ে sign bit-কে বিট ৩১-এ তোলা, তারপর arithmetic ডান-সরানো (>>), যা sign bit কপি করে ভরে। >>> ব্যবহার করলে ০ ভরত — এটিই সবচেয়ে প্রচলিত bug-গুলোর একটি।

নিচের decoder প্রোগ্রামের ২১টি word নেয়, সব field কাটে, opcode থেকে format ঠিক করে সেই format-এর immediate বের করে, আর disassembly ছাপায়। Branch আর jal-এর লক্ষ্য ছাপা হয় পুরো ঠিকানা হিসেবে (pc + imm), যাতে assembly listing-এর সাথে সরাসরি মেলানো যায়:

// Milestone 1: RV32I decoder + disassembler. Words = the capstone program (hex from an independent encoder).
const words = `00002137 00000517 0fc50513 10050593 00a00613 008000ef 00000073 ffc10113 00812023 00000413 00052283
  00540433 0085a023 00450513 00458593 fff60613 fe0614e3 00040513 00012403 00410113 00008067`.trim().split(/\s+/).map(h => parseInt(h, 16) >>> 0);
const ABI = "zero ra sp gp tp t0 t1 t2 s0 s1 a0 a1 a2 a3 a4 a5 a6 a7".split(" "), R = n => ABI[n] || "x" + n, hex = v => "0x" + (v >>> 0).toString(16);
const bits = (w, hi, lo) => (w >>> lo) & ((1 << (hi - lo + 1)) - 1), sext = (v, n) => (v << (32 - n)) >> (32 - n); // n-bit sign-extend
const TYPE = { 0x33: "R", 0x13: "I", 0x03: "I", 0x67: "I", 0x73: "I", 0x23: "S", 0x63: "B", 0x37: "U", 0x17: "U", 0x6f: "J" };
function decode(w) {
  const f = { op: bits(w, 6, 0), rd: bits(w, 11, 7), f3: bits(w, 14, 12),
              rs1: bits(w, 19, 15), rs2: bits(w, 24, 20), f7: bits(w, 31, 25) };
  f.type = TYPE[f.op] || "?";
  f.imm = { R: 0, "?": 0,
    I: sext(bits(w, 31, 20), 12),
    S: sext((f.f7 << 5) | f.rd, 12),
    B: sext((bits(w, 31, 31) << 12) | (bits(w, 7, 7) << 11) | (bits(w, 30, 25) << 5) | (bits(w, 11, 8) << 1), 13),
    U: (w & 0xfffff000) | 0,                                     // upper 20 bits, low 12 bits = 0
    J: sext((bits(w, 31, 31) << 20) | (bits(w, 19, 12) << 12) | (bits(w, 20, 20) << 11) | (bits(w, 30, 21) << 1), 21),
  }[f.type];
  return f;
}
function disasm(w, pc) {
  const { op, rd, rs1, rs2, f3, f7, imm } = decode(w);
  if (op === 0x33) return [f7 === 0x20 ? "sub" : "add", "sll", "slt", "sltu", "xor", f7 === 0x20 ? "sra" : "srl", "or", "and"][f3] + ` ${R(rd)}, ${R(rs1)}, ${R(rs2)}`;
  if (op === 0x13) return ["addi", "slli", "slti", "sltiu", "xori", f7 === 0x20 ? "srai" : "srli", "ori", "andi"][f3] + ` ${R(rd)}, ${R(rs1)}, ${f3 % 4 === 1 ? rs2 : imm}`;
  if (op === 0x03) return ["lb", "lh", "lw", "?", "lbu", "lhu"][f3] + ` ${R(rd)}, ${imm}(${R(rs1)})`;
  if (op === 0x23) return ["sb", "sh", "sw"][f3] + ` ${R(rs2)}, ${imm}(${R(rs1)})`;
  if (op === 0x63) return ["beq", "bne", "?", "?", "blt", "bge", "bltu", "bgeu"][f3] + ` ${R(rs1)}, ${R(rs2)}, ${hex(pc + imm)}`;
  if (op === 0x37 || op === 0x17) return `${op === 0x37 ? "lui" : "auipc"} ${R(rd)}, ${hex(imm >>> 12)}`;
  if (op === 0x6f) return `jal ${R(rd)}, ${hex(pc + imm)}`;
  if (op === 0x67) return `jalr ${R(rd)}, ${imm}(${R(rs1)})`;
  return w === 0x73 ? "ecall" : "illegal";
}
console.log("pc  word      op type rd f3 rs1 rs2 f7    imm   disassembly");
words.forEach((w, k) => { const f = decode(w), p = (v, n) => String(v).padStart(n);
  console.log(`${(4 * k).toString(16).padStart(2, "0")}  ${w.toString(16).padStart(8, "0")}  ${f.op.toString(16).padStart(2, "0")}` +
    `  ${f.type} ${p(f.rd, 4)}${p(f.f3, 3)}${p(f.rs1, 4)}${p(f.rs2, 4)}${p(f.f7, 4)}${p(f.imm, 7)}   ${disasm(w, 4 * k)}`); });

pc  word      op type rd f3 rs1 rs2 f7    imm   disassembly
00  00002137  37  U    2  2   0   0   0   8192   lui sp, 0x2
04  00000517  17  U   10  0   0   0   0      0   auipc a0, 0x0
08  0fc50513  13  I   10  0  10  28   7    252   addi a0, a0, 252
0c  10050593  13  I   11  0  10   0   8    256   addi a1, a0, 256
10  00a00613  13  I   12  0   0  10   0     10   addi a2, zero, 10
14  008000ef  6f  J    1  0   0   8   0      8   jal ra, 0x1c
18  00000073  73  I    0  0   0   0   0      0   ecall
1c  ffc10113  13  I    2  0   2  28 127     -4   addi sp, sp, -4
20  00812023  23  S    0  2   2   8   0      0   sw s0, 0(sp)
24  00000413  13  I    8  0   0   0   0      0   addi s0, zero, 0
28  00052283  03  I    5  2  10   0   0      0   lw t0, 0(a0)
2c  00540433  33  R    8  0   8   5   0      0   add s0, s0, t0
30  0085a023  23  S    0  2  11   8   0      0   sw s0, 0(a1)
34  00450513  13  I   10  0  10   4   0      4   addi a0, a0, 4
38  00458593  13  I   11  0  11   4   0      4   addi a1, a1, 4
3c  fff60613  13  I   12  0  12  31 127     -1   addi a2, a2, -1
40  fe0614e3  63  B    9  1  12   0 127    -24   bne a2, zero, 0x28
44  00040513  13  I   10  0   8   0   0      0   addi a0, s0, 0
48  00012403  03  I    8  2   2   0   0      0   lw s0, 0(sp)
4c  00410113  13  I    2  0   2   4   0      4   addi sp, sp, 4
50  00008067  67  I    0  0   1   0   0      0   jalr zero, 0(ra)

৪ · Milestone ২ — execute লুপ: register, মেমরি আর একটি function call

ISS-এর হৃৎপিণ্ড একটি অসীম লুপ, যা পর্ব ৩২-এর single-cycle datapath-এর software রূপ: PC থেকে word আনা (fetch), field আর immediate কাটা (decode), ALU-র কাজ বা ঠিকানা হিসাব (execute), দরকার হলে মেমরি পড়া-লেখা (memory), ফল register-এ লেখা (write-back), তারপর PC বদলানো। প্রতিটি instruction-এর জন্য মূল প্রশ্ন দুটি: rd-তে কী লিখব (v), আর পরের PC কী (next). নিচে একটি instruction — লুপের প্রথম lw t0, 0(a0) — ISS-এর ভেতর দিয়ে ধাপে ধাপে:

এবার পুরো ISS. সাবসেটে আছে ১৮টি instruction: add sub and or xor slt addi slli slti lw sw beq bne blt jal jalr lui auipc, আর ecall-কে আমরা থামার সংকেত ধরেছি। প্রতিটি অজানা encoding-এ ISS চুপচাপ এগিয়ে না গিয়ে error দেয় — golden model-এর প্রথম শর্ত: যা জানি না, সেটা জানি না বলা। শেষে ছাপায় শূন্য নয় এমন register, c[], stack-এর word, আর দুটি trace:

// Milestone 2: RV32I instruction-set simulator (subset). 8 KiB little-endian memory, x0 hard-wired to 0.
const prog = `00002137 00000517 0fc50513 10050593 00a00613 008000ef 00000073 ffc10113 00812023 00000413 00052283
  00540433 0085a023 00450513 00458593 fff60613 fe0614e3 00040513 00012403 00410113 00008067`.trim().split(/\s+/);
const mem = new Uint8Array(8192), x = new Int32Array(32);
const ld = a => (mem[a] | mem[a + 1] << 8 | mem[a + 2] << 16 | mem[a + 3] << 24);       // little-endian load
const st = (a, v) => { for (let k = 0; k < 4; k++) mem[a + k] = (v >>> (8 * k)) & 255; };
prog.forEach((h, k) => st(4 * k, parseInt(h, 16)));                // program at address 0
for (let i = 0; i < 10; i++) st(0x100 + 4 * i, i + 1);              // data: a[i] = i + 1 at 0x100
const B = (w, hi, lo) => (w >>> lo) & ((1 << (hi - lo + 1)) - 1), sx = (v, n) => (v << (32 - n)) >> (32 - n);
let pc = 0, count = 0, pcTrace = "", dataTrace = []; x[8] = 7;     // x8 = s0 = 7: the caller's value must survive
for (;;) {
  const w = ld(pc), op = B(w, 6, 0), rd = B(w, 11, 7), f3 = B(w, 14, 12), f7 = B(w, 31, 25);
  const a = x[B(w, 19, 15)], b = x[B(w, 24, 20)], iI = sx(w >>> 20, 12), iS = sx((f7 << 5) | rd, 12), iU = w & 0xfffff000;
  const iB = sx(B(w, 31, 31) << 12 | B(w, 7, 7) << 11 | B(w, 30, 25) << 5 | B(w, 11, 8) << 1, 13);
  const iJ = sx(B(w, 31, 31) << 20 | B(w, 19, 12) << 12 | B(w, 20, 20) << 11 | B(w, 30, 21) << 1, 21);
  let next = pc + 4, v = null;                                       // v = value to write to rd
  count++; pcTrace += (pc / 4).toString(36);
  if (op === 0x33) v = [f7 === 0x20 ? a - b : a + b, NaN, +(a < b), NaN, a ^ b, NaN, a | b, a & b][f3];  // add sub slt xor or and
  else if (op === 0x13) v = [a + iI, a << (iI & 31), +(a < iI)][f3] ?? NaN;                          // addi slli slti
  else if (op === 0x03) { v = ld(a + iI); dataTrace.push("R" + (a + iI).toString(16)); }   // lw
  else if (op === 0x23) { st(a + iS, b); dataTrace.push("W" + (a + iS).toString(16)); }     // sw
  else if (op === 0x63) { const t = [a === b, a !== b, , , a < b][f3]; if (t === undefined) v = NaN; else if (t) next = pc + iB; }
  else if (op === 0x37) v = iU;                                       // lui
  else if (op === 0x17) v = pc + iU;                                  // auipc
  else if (op === 0x6f) { v = pc + 4; next = pc + iJ; }               // jal
  else if (op === 0x67) { v = pc + 4; next = (a + iI) & ~1; }         // jalr: clear bit 0
  else if (w === 0x73) break; else v = NaN;                          // ecall = halt; anything else = unsupported
  if (Number.isNaN(v)) throw new Error(`unsupported instruction at pc ${pc}`);
  if (v !== null && rd !== 0) x[rd] = v;                              // writes to x0 are dropped
  pc = next;
}
const names = "zero ra sp gp tp t0 t1 t2 s0 s1 a0 a1 a2".split(" "); console.log(`halted at pc 0x${pc.toString(16)} after ${count} instructions`);
console.log(x.reduce((s, v, r) => v ? s + `${names[r]}=${v < 0 || v > 255 ? "0x" + (v >>> 0).toString(16) : v} ` : s, "regs: "));
console.log("c[] =", [...Array(10)].map((_, i) => ld(0x200 + 4 * i)).join(" "), "| stack word", ld(0x1ffc));
console.log("pc trace (pc/4, base 36):", pcTrace, "\ndata trace:", dataTrace.join(" "));

halted at pc 0x18 after 84 instructions
regs: ra=24 sp=0x2000 t0=10 s0=7 a0=55 a1=0x228
c[] = 1 3 6 10 15 21 28 36 45 55 | stack word 7
pc trace (pc/4, base 36): 012345789abcdefgabcdefgabcdefgabcdefgabcdefgabcdefgabcdefgabcdefgabcdefgabcdefghijk6
data trace: W1ffc R100 W200 R104 W204 R108 W208 R10c W20c R110 W210 R114 W214 R118 W218 R11c W21c R120 W220 R124 W224 R1ffc

৫ · Milestone ৩ — trace থেকে pipeline-এর সময়

ISS বলেছে কী চলেছে: ৮৪টি instruction, কোন ক্রমে। এবার প্রশ্ন: পর্ব ৩৫-এর পাঁচ ধাপের pipeline-এ (IF, ID, EX, MEM, WB) এতে কত cycle লাগবে? আদর্শ pipeline-এ n টি instruction-এ n + ৪ cycle. বাস্তবে দুই কারণে বাড়ে, আর নিয়মগুলো পর্ব ৩৬ ও ৩৭-এর হুবহু:

• Data hazard (পর্ব ৩৬): Forwarding থাকলে ALU-র ফলের জন্য অপেক্ষা নেই; load-use হলে ১ cycle stall. Forwarding না থাকলে consumer-কে producer-এর WB-এর cycle পর্যন্ত ID-তে থাকতে হয় (অর্ধ-cycle কৌশলে সেই cycle-এই পড়া যায়)।
• Control hazard (পর্ব ৩৭): শাখার ফল জানা যায় EX-এ। ভুল অনুমান হলে পেছনের দুটি instruction (IF আর ID-তে) মুছে ফেলতে হয় — penalty ২ cycle. Predict-not-taken-এ প্রতিটি নেওয়া শাখা আর প্রতিটি লাফ (jal, jalr) ২ cycle দেয়।
• ২-বিট predictor: প্রতিটি শাখার নিজের 2-bit saturating counter, শুরু 01 (weakly not-taken). Taken অনুমান করতে লক্ষ্য ঠিকানাও লাগে — সেটি দেয় একটি BTB, যেখানে একটি শাখা প্রথমবার নেওয়ার পরেই তার লক্ষ্য জমা হয়। তাই প্রথম দেখায় যেকোনো নেওয়া শাখা বা লাফ ২ cycle দেয়।

মডেলটি পর্ব ৩৬-এর simulator-এর একই কৌশল ব্যবহার করে: প্রতিটি instruction-এর জন্য D[i] = যে শেষ cycle-এ সে ID-তে থাকে। স্বাভাবিকভাবে D[i] = D[i−1] + 1; একটি producer p-এর ফল লাগলে D[i] ≥ D[p] + ১ (ALU, forwarding), D[p] + ২ (load, forwarding), বা D[p] + ৩ (forwarding নেই); আগের instruction-টি ভুল অনুমানের শাখা হলে +২. শেষ instruction-এর WB = D + ৩, সেটিই মোট cycle. নিচে লুপের প্রথম ঘুরতি, forwarding আর predict-not-taken সহ:

এবার হাতে পুরো হিসাব, forwarding + predict-not-taken: মোট cycle = n + ৪ + data stall + control stall. Load-use প্রতি ঘুরতিতে ১টি → ১০; নেওয়া শাখা ৯টি, আর jal ও jalr ১টি করে → ১১টি redirect × ২ = ২২. তাই ৮৪ + ৪ + ১০ + ২২ = ১২০ cycle. ২-বিট predictor-এ bne-এর counter 01 থেকে শুরু: প্রথম taken ভুল (01 → 10), পরের আটটি ঠিক, শেষের not-taken ভুল — ২টি ভুল; সাথে jal আর jalr প্রথম দেখায় BTB-তে নেই → মোট ৪টি redirect × ২ = ৮. প্রোগ্রাম:

// Milestone 3: trace-driven timing model of a 5-stage pipeline (IF ID EX MEM WB), branches resolved in EX.
// Input = the program words + the pc trace printed by Milestone 2 (pasted here as data).
const prog = `00002137 00000517 0fc50513 10050593 00a00613 008000ef 00000073 ffc10113 00812023 00000413 00052283
  00540433 0085a023 00450513 00458593 fff60613 fe0614e3 00040513 00012403 00410113 00008067`.trim().split(/\s+/);
const trace = "012345789" + "abcdefg".repeat(10) + "hijk6";       // = the 84-character pc trace of Milestone 2
const info = prog.map(h => { const w = parseInt(h, 16), op = w & 127, f = (lo, n) => (w >>> lo) & ((1 << n) - 1);
  const src = [0x37, 0x17, 0x6f].includes(op) ? [] : [0x33, 0x23, 0x63].includes(op) ? [f(15, 5), f(20, 5)] : [f(15, 5)];
  return { rd: [0x23, 0x63, 0x73].includes(op) ? 0 : f(7, 5), src: src.filter(r => r), load: op === 3,
           branch: op === 0x63, ctrl: [0x63, 0x6f, 0x67].includes(op) }; });
const dyn = [...trace].map(c => parseInt(c, 36));                    // dynamic list of static indices
function run(fwd, predictor) {
  const D = [], ctr = {}, btb = new Set(), last = {};                // D[i] = last cycle i spends in ID
  let dataSt = 0, ctrlSt = 0, redirect = false;                      // last[r] = latest producer of r
  dyn.forEach((s, i) => {
    const I = info[s], taken = I.ctrl && dyn[i + 1] !== s + 1 && i + 1 < dyn.length;
    let d = i === 0 ? 2 : D[i - 1] + 1;
    if (redirect) { d += 2; ctrlSt += 2; redirect = false; }        // 2 wrong-path instructions flushed
    const early = d;
    for (const r of I.src) if (r in last)                            // RAW: wait for the producer's value
      d = Math.max(d, D[last[r]] + (!fwd ? 3 : info[dyn[last[r]]].load ? 2 : 1));
    dataSt += d - early; D.push(d);
    if (I.rd) last[I.rd] = i;
    if (!I.ctrl) return;
    const predT = predictor === "2-bit" && btb.has(s) && (ctr[s] ?? 1) >= 2;   // counters start at 01
    if (predT !== taken) redirect = true;                            // discovered in EX: wrong path
    if (I.branch) ctr[s] = Math.max(0, Math.min(3, (ctr[s] ?? 1) + (taken ? 1 : -1)));
    else ctr[s] = 3;                                                 // jal/jalr: always taken
    if (taken) btb.add(s);                                           // BTB learns the target
  });
  const cycles = D[D.length - 1] + 3, n = dyn.length;
  console.log(`${(fwd ? "forwarding" : "no forwarding").padEnd(14)} ${predictor.padEnd(11)} cycles ${cycles}` +
    ` = ${n} + 4 + ${dataSt} data + ${ctrlSt} control stalls   CPI ${(cycles / n).toFixed(3)}`);
}
const n = dyn.length; console.log(`instructions ${n}, no hazards: ${n + 4} cycles, CPI ${((n + 4) / n).toFixed(3)}`);
run(false, "predict-NT"); run(true, "predict-NT"); run(true, "2-bit");

instructions 84, no hazards: 88 cycles, CPI 1.048
no forwarding  predict-NT  cycles 176 = 84 + 4 + 66 data + 22 control stalls   CPI 2.095
forwarding     predict-NT  cycles 120 = 84 + 4 + 10 data + 22 control stalls   CPI 1.429
forwarding     2-bit       cycles 106 = 84 + 4 + 10 data + 8 control stalls   CPI 1.262

৬ · Milestone ৪ — cache model, AMAT আর মোট সময়

M3-এ data মেমরি ছিল এক cycle-এর। এবার তার জায়গায় বসাই একটি ছোট data cache: মোট ৬৪ বাইট, ব্লক ১৬ বাইট, write-allocate (store miss হলেও ব্লক আনা হয়)। দুটি নকশা তুলনা করব: direct-mapped (৪টি line) আর ২-way set-associative (২টি set × ২ way, LRU). ঠিকানা ভাগ হয় পর্ব ৪৫-এর নিয়মে: ১৬ বাইট ব্লক → offset ৪ বিট; direct-mapped-এ ৪টি line → index ২ বিট, বাকিটা tag; ২-way-এ ২টি set → index ১ বিট।

সমস্যাটি এখানেই দেখা যাচ্ছে: a[] শুরু 0x100-তে, c[] 0x200-তে — ঠিক ২৫৬ বাইট দূরে, আর ২৫৬ cache-এর মাপ ৬৪-এর গুণিতক। তাই a[i] আর c[i] সবসময় একই direct-mapped line-এ পড়ে, আর লুপ তাদের পালা করে ছোঁয়: পড়ি a[i], লিখি c[i], পড়ি a[i+1] … প্রতিবার একজন আরেকজনকে বের করে দেয় — পর্ব ৪৬-এর conflict miss. ২-way cache-এ একই set-এ দুটি ব্লক একসাথে থাকতে পারে। নিচের stepper-এ ২-way LRU-র প্রতিটি set-এর অবস্থা, পাশে direct-mapped-এর মোট miss:

এবার সময়। পর্ব ৪৭-এর সূত্রগুলো হুবহু: AMAT = hit time + miss rate × miss penalty; memory stall cycle = miss-এর সংখ্যা × miss penalty; আর CPI = CPI_base + (মেমরি access / instruction) × miss rate × miss penalty. এখানে CPI_base হলো M3-এর ১২০ / ৮৪ (forwarding, predict-not-taken), কারণ M3 ইতিমধ্যে প্রতিটি data access-কে ১ cycle-এর hit ধরে নিয়েছে। Hit time ১ cycle আর miss penalty ২০ cycle — শেখার জন্য ধরে নেওয়া মান, কোনো নির্দিষ্ট chip-এর নয়:

// Milestone 4: data-cache model driven by the data trace of Milestone 2 (pasted here as data).
// Cache: 64 bytes of data, 16-byte blocks, write-allocate (a store miss also fetches the block).
const trace = `W1ffc R100 W200 R104 W204 R108 W208 R10c W20c R110 W210 R114 W214 R118 W218 R11c W21c
  R120 W220 R124 W224 R1ffc`.trim().split(/\s+/).map(t => parseInt(t.slice(1), 16));
const HIT = 1, PENALTY = 20, CYCLES = 120, IC = 84;     // assumed latencies; 120 cycles = Milestone 3 (forwarding, predict-NT)
function simulate(ways, size = 64, block = 16) {
  const sets = size / block / ways, cache = [...Array(sets)].map(() => []);   // each set: tags, LRU first
  let misses = 0, seq = "";
  for (const addr of trace) {
    const blk = Math.floor(addr / block), set = blk % sets, tag = Math.floor(blk / sets), s = cache[set];
    const k = s.indexOf(tag);
    if (k >= 0) { s.splice(k, 1); seq += "H"; }                     // hit: move to the MRU end
    else { misses++; seq += "M"; if (s.length === ways) s.shift(); }   // miss: evict the LRU tag
    s.push(tag);
  }
  const mr = misses / trace.length, amat = HIT + mr * PENALTY, stall = misses * PENALTY;
  console.log(`${size} B ${ways === 1 ? "direct-mapped" : ways + "-way LRU"} (${sets} sets x ${ways} way): ${seq}`);
  console.log(`  ${trace.length} accesses, ${misses} misses, hit rate ${(100 * (1 - mr)).toFixed(1)}%,` +
    ` AMAT = ${HIT} + ${mr.toFixed(4)} x ${PENALTY} = ${amat.toFixed(2)} cycles`);
  console.log(`  total = ${CYCLES} + ${misses} x ${PENALTY} = ${CYCLES + stall} cycles,` +
    ` CPI = ${(CYCLES / IC).toFixed(3)} + ${(trace.length / IC).toFixed(4)} x ${mr.toFixed(4)} x ${PENALTY} = ${((CYCLES + stall) / IC).toFixed(3)}`);
}
for (const a of [0x104, 0x204, 0x1ffc])                     // direct-mapped 64 B: 4 offset bits, 2 index bits
  console.log(`0x${a.toString(16)}: tag ${a >> 6}, index ${(a >> 4) & 3}, offset ${a & 15}`);
simulate(1); simulate(1, 128); simulate(2);

0x104: tag 4, index 0, offset 4
0x204: tag 8, index 0, offset 4
0x1ffc: tag 127, index 3, offset 12
64 B direct-mapped (4 sets x 1 way): MMMMMMMMMMMMMMMMMMMMMH
  22 accesses, 21 misses, hit rate 4.5%, AMAT = 1 + 0.9545 x 20 = 20.09 cycles
  total = 120 + 21 x 20 = 540 cycles, CPI = 1.429 + 0.2619 x 0.9545 x 20 = 6.429
128 B direct-mapped (8 sets x 1 way): MMMMMMMMMMMMMMMMMMMMMH
  22 accesses, 21 misses, hit rate 4.5%, AMAT = 1 + 0.9545 x 20 = 20.09 cycles
  total = 120 + 21 x 20 = 540 cycles, CPI = 1.429 + 0.2619 x 0.9545 x 20 = 6.429
64 B 2-way LRU (2 sets x 2 way): MMMHHHHHHMMHHHHHHMMHHM
  22 accesses, 8 misses, hit rate 63.6%, AMAT = 1 + 0.3636 x 20 = 8.27 cycles
  total = 120 + 8 x 20 = 280 cycles, CPI = 1.429 + 0.2619 x 0.3636 x 20 = 3.333

৭ · সাধারণ bug, পরীক্ষার কৌশল আর reference simulator

Simulator লেখা শেষ হলে আসল কাজ শুরু — প্রমাণ করা যে এটি ঠিক। প্রায় সব ISS-এ প্রথম দিকে একই পাঁচ-ছয় রকম bug দেখা যায়। প্রতিটির একটি “আঙুলের ছাপ” আছে, যা চিনলে খোঁজা সহজ:

শেষ সারির jalr-এর ক্রম-সমস্যা আমাদের ISS-এ আপনাআপনি এড়ানো হয়েছে: a (rs1-এর মান) instruction-এর শুরুতেই পড়ে রাখা, আর rd-তে লেখা হয় সবার শেষে। এই ছোট নকশা-সিদ্ধান্ত — “আগে সব source পড়া, পরে সব destination-এ লেখা” — hardware-এর মতোই, আর একটি পুরো শ্রেণির bug মুছে দেয়।

পরীক্ষার কৌশল — স্তরে স্তরে

1. প্রতিটি instruction-এর unit test: একটি instruction, জানা register মান, প্রত্যাশিত ফল। বিশেষ মানগুলো ভুলবেন না: 0, −1, সবচেয়ে বড় ধনাত্মক (0x7fffffff), সবচেয়ে ছোট ঋণাত্মক (0x80000000), আর immediate-এর দুই প্রান্ত (−2048, 2047).
2. জানা উত্তরের প্রোগ্রাম: এই পর্বের prefix sum, একটি recursive factorial (পর্ব ৩০), একটি bubble sort. প্রতিটি নিজেকে যাচাই করে — শেষে ফল মিলিয়ে একটি নির্দিষ্ট register-এ ১ বা ০ রাখে।
3. Differential testing: একই ELF ফাইল আপনার ISS আর একটি reference simulator-এ চালিয়ে প্রতিটি instruction-এর পরের register মিলিয়ে দেখা। RISC-V-এর প্রচলিত reference হলো Spike — RISC-V-এর “golden” ISA simulator হিসেবে পরিচিত, যা মূলত UC Berkeley থেকে এসেছে, আর এর একটি instruction-by-instruction log দেওয়ার option আছে। দ্রুত, পূর্ণ সিস্টেম চালানোর জন্য QEMU (একটি emulator, যা অনুবাদ করে চালায় — ভাবনার প্রশ্ন ০৪)। দুটির সঠিক command-line option তাদের নিজস্ব documentation দেখে নিন।
4. Official test suite: RISC-V project-এর riscv-tests সংগ্রহে প্রতিটি instruction-এর ছোট assembly পরীক্ষা আছে, যেগুলো নিজেরাই pass/fail জানায়। আরও আনুষ্ঠানিক compliance test-এর জন্য আছে architecture test suite (riscv-arch-test) আর তা চালানোর framework RISCOF: প্রতিটি পরীক্ষা মেমরির একটি অংশে একটি “signature” লেখে, আর framework সেটি একটি reference model-এর signature-এর সাথে মেলায়। এই tool-গুলোর নাম আর গঠন সময়ের সাথে বদলায় — শুরু করার আগে RISC-V International-এর বর্তমান documentation দেখে নিন।
5. Regression: একটি bug ঠিক করার পরে সেই bug-এর জন্য একটি পরীক্ষা যোগ করুন, আর প্রতিটি পরিবর্তনের পরে সব পরীক্ষা এক কমান্ডে চালান।

৮ · সম্প্রসারণ, রুব্রিক আর portfolio

যেখান থেকে প্রজেক্ট আলাদা হয়ে ওঠে

সম্প্রসারণের আগে M2-র ISS-কে “জমিয়ে” রাখুন — তার আউটপুট golden ফাইলে লিখে রাখুন। প্রতিটি নতুন ফিচারের পরে পুরোনো সব পরীক্ষা হুবহু একই ফল দেয় কি না দেখুন। Simulator বাড়ে, কিন্তু পুরোনো সত্য বদলায় না।

নিজেকে মূল্যায়নের রুব্রিক

পুরো প্রজেক্ট ১০০ নম্বরে। ৭০-এর নিচে হলে আগে “ঠিকতা” আর “পরীক্ষা” সারি পূর্ণ করুন — নতুন ফিচার পরে।

• আমার decoder-এর disassembly একটি assembler-এর objdump -d আউটপুটের সাথে অন্তত একটি পূর্ণ প্রোগ্রামে হুবহু মিলিয়েছি
• ঋণাত্মক immediate-এর প্রতিটি format (I, S, B, J) আলাদা পরীক্ষায় দেখেছি, আর lui-এর পরে ঋণাত্মক addi দিয়ে একটি ৩২-বিট ধ্রুবক বানিয়ে মিলিয়েছি
• addi zero, zero, 5-এর পরে x0 = 0, আর jalr ra, 1(ra)-এ বিট ০ মোছা হয় — দুটিই পরীক্ষায় আছে
• Pipeline model-এর একটি ছোট প্রোগ্রামের cycle সংখ্যা হাতে আঁকা pipeline diagram-এর সাথে মিলিয়েছি
• Cache model-এর একটি trace-এর প্রতিটি set-এর অবস্থা হাতে লিখে মিলিয়েছি, আর AMAT-এর সব সংখ্যা একই এককে (cycle) রেখেছি

Portfolio আর ইন্টারভিউতে উপস্থাপন

একটি ছোট CPU simulator চাকরির আবেদনে বা উচ্চশিক্ষার আবেদনে খুব কাজের একটি নমুনা, কারণ এতে একসাথে দেখা যায় bit-স্তরের সতর্কতা, নকশার সিদ্ধান্ত আর যাচাইয়ের অভ্যাস। Embedded, firmware, verification বা systems ধরনের পদে, আর বিশ্ববিদ্যালয়ের থিসিস বা ল্যাব প্রজেক্টে, প্রায়ই প্রশ্ন আসে “আপনি কী বানিয়েছেন, আর কীভাবে জানলেন যে এটি ঠিক?” README-তে রাখুন: কোন ISA সাবসেট, কীভাবে চালাবেন, পরীক্ষার ফলের একটি টেবিল, আর একটি “নকশার সিদ্ধান্ত” অংশ।

ইন্টারভিউতে trade-off ব্যাখ্যা করতে প্রস্তুত থাকুন — যেমন: কেন trace-driven? (সরল, দ্রুত, একই trace-এ অনেক নকশা; কিন্তু ভুল পথ আর মেমরির সমান্তরাল অনুরোধ ধরা পড়ে না)। কেন cache দ্বিগুণ করায় লাভ হলো না? (miss-গুলো conflict, capacity নয় — ২৫৬ বাইট ব্যবধান)। ২-বিট predictor কেন ৯টি taken-এর লুপে ২টি ভুল করে? (counter 01 থেকে শুরু, আর শেষের not-taken). নিজের সংখ্যা দিয়ে উত্তর দিতে পারা — “১২০ থেকে ১০৬ cycle” — মুখস্থ সংজ্ঞার চেয়ে অনেক বেশি বিশ্বাসযোগ্য।

৯ · AI-এর যুগে — simulator-এ AI সহকারী, যাচাইকারী আপনি

একটি AI চ্যাটবট কয়েক সেকেন্ডে একটি “RISC-V emulator in JavaScript” লিখে দেবে, আর সেটি সম্ভবত একটি সরল প্রোগ্রাম চালাবেও। বিপদ ঠিক সেখানেই — ভুলগুলো থাকে কিনারায়, যা সরল প্রোগ্রাম ছোঁয় না। এই বিষয়ে AI-এর সাধারণ ভুল:

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

• AI-এর দেওয়া প্রতিটি hex word একটি আসল assembler বা আমার স্বাধীন encoder দিয়ে আবার বানিয়ে মিলিয়েছি
• AI-এর বলা প্রত্যাশিত মান নিজের ISS-এ চালিয়ে দেখেছি; অমিল হলে spec পড়ে ঠিক করেছি কে ভুল
• Pipeline বা cache-এর কোনো সংখ্যা AI দিলে, ছোট একটি উদাহরণ হাতে হিসাব করে তার পদ্ধতি পরীক্ষা করেছি
• AI-এর লেখা কোডে অজানা opcode বা funct-এর জন্য error আছে কি না দেখেছি
• Tool-এর option আর test suite-এর নাম তাদের documentation থেকে মিলিয়েছি