Single-cycle datapath — একটি instruction-এর পুরো পথ

১ · Instruction থেকে hardware — datapath আর control

এতদিন আমরা instruction দেখেছি software-এর চোখে। পর্ব ২৬-এ শিখেছেন lw x5, 8(x10) মানে “x10-এর ঠিকানার ৮ byte পরের word এনে x5-এ রাখা”। পর্ব ২৭-এ দেখেছেন সেই instruction আসলে ৩২টি বিট, 0x00852283. কিন্তু প্রশ্নটা রয়ে গেছে: chip-এর ভেতরে কোন তার দিয়ে কোন মান কোথায় যায়, যাতে ঠিক এই কাজটি হয়? এই পর্বে আমরা প্রথমবার একটি আসল CPU-র ভেতরটা নিজের হাতে বানাব।

একটি CPU-র hardware-কে দুই ভাগে দেখা হয়। প্রথম ভাগ datapath — যেখানে ডেটা চলে আর হিসাব হয়: register, ALU, মেমরি, adder, mux আর তাদের মধ্যের তার। দ্বিতীয় ভাগ control unit — যে instruction-এর opcode দেখে datapath-কে বলে দেয় কোন mux কোন ইনপুট নেবে, কোন register-এ লেখা হবে, মেমরি পড়বে না লিখবে। এই নির্দেশগুলোকে বলে control signal.

এই পর্বে আমরা Patterson–Hennessy-এর বই Computer Organization and Design, RISC-V Edition-এর ধাঁচে একটি ছোট CPU বানাব, যা RV32I-এর আটটি instruction চালায়:

ছোট তালিকা, কিন্তু এখানে CPU-র সব মৌলিক কাজ আছে: হিসাব, মেমরি থেকে আনা, মেমরিতে রাখা আর সিদ্ধান্ত নিয়ে লাফ দেওয়া। এই আটটি দিয়েই লুপ, array-র যোগফল বা খোঁজার প্রোগ্রাম লেখা যায়। অন্য instruction যোগ করার উপায় অংশ ৮-এ দেখব।

২ · উপাদানগুলো — state element আর combinational unit

Datapath-এর প্রতিটি উপাদান দুই জাতের একটি। Combinational unit-এর আউটপুট শুধু এই মুহূর্তের ইনপুটের ওপর নির্ভর করে — ALU, adder, mux, ImmGen. এরা কিছু মনে রাখে না। আর state element মান ধরে রাখে, আর শুধু clock-এর ধারে নতুন মান নেয় — PC, register file, data memory. (Instruction memory-কে এই মডেলে শুধু পড়া হয়, তাই সেটি combinational-এর মতো আচরণ করে: ঠিকানা দিলে কিছুক্ষণ পরে instruction আসে।) পর্ব ১৫-১৬-এ (flip-flop, register) যে edge-triggered flip-flop দেখেছেন, state element তারই বড় রূপ।

Register file — দুইটি পড়া, একটি লেখা

R-type instruction একবারে দুটি register পড়ে আর একটিতে লেখে, তাই register file-এ দুটি read port আর একটি write port. পর্ব ১২-তে (mux আর decoder) দেখেছেন: প্রতিটি read port আসলে ৩২টি register-এর মধ্যে একটি বাছাইয়ের একটি চওড়া mux — পড়া combinational, ঠিকানা দিলেই কিছুক্ষণ পরে মান। লেখা হয় শুধু clock-এর উঠন্ত ধারে, আর শুধু যখন RegWrite = 1; কোন register-এ লেখা হবে তা ঠিক করে একটি ৫-থেকে-৩২ decoder. আর x0 একটি বিশেষ ঘর: পড়লে সবসময় 0, লেখার চেষ্টা উপেক্ষা হয়।

// উদাহরণ — synthesizable Verilog (পর্ব ১৪-এর ধাঁচে), ৩২ × ৩২-বিট register file
module regfile (
  input  wire        clk, we,           // we = RegWrite
  input  wire [4:0]  ra1, ra2, wa,      // rs1, rs2, rd
  input  wire [31:0] wd,                // write data
  output wire [31:0] rd1, rd2           // ReadData1, ReadData2
);
  reg [31:0] r [0:31];
  assign rd1 = (ra1 == 5'd0) ? 32'd0 : r[ra1];   // combinational read
  assign rd2 = (ra2 == 5'd0) ? 32'd0 : r[ra2];   // x0 always reads 0
  always @(posedge clk)
    if (we && wa != 5'd0) r[wa] <= wd;          // write only at the edge
endmodule

এই নকশার একটি চমৎকার ফল: add x5, x5, x6-এর মতো instruction একই cycle-এ x5 পড়ে আর x5-এ লেখে, তবু গোলমাল হয় না। পুরো cycle ধরে পড়া হয় পুরোনো মান; নতুন মান ঢোকে cycle-এর শেষের ধারে। পরের cycle-এর instruction নতুনটি দেখে। এই নিয়মকে বলে clocking methodology: সব state element একই ধারে লেখে, আর দুই ধারের মাঝে combinational logic-এর মান স্থির হওয়ার সময় পায়।

ALU আর ImmGen

পর্ব ১৩-এর ALU এখানে চারটি কাজ করবে: AND, OR, যোগ, বিয়োগ। কোনটি করবে তা বলে ৪-বিটের ALU control: Patterson–Hennessy-এর কোডে 0000 = AND, 0001 = OR, 0010 = যোগ, 0110 = বিয়োগ। ALU-র একটি বাড়তি আউটপুট Zero — ফল 0 হলে 1. beq ঠিক এটাই ব্যবহার করবে: rs1 − rs2 = 0 মানে দুটি সমান।

ImmGen (immediate generator) instruction-এর বিট থেকে immediate বের করে ৩২ বিটে sign extend করে। কোন বিট কোথা থেকে আসবে তা format-ভেদে আলাদা — I-তে inst[31:20], S-এ inst[31:25] আর inst[11:7], B-তে চার টুকরো। পুরো টেবিল পর্ব ২৭-এ; এখানে মনে রাখুন ImmGen opcode দেখে format বোঝে, আর sign bit সবসময় inst[31].

৩ · প্রথম দুই টুকরো — instruction fetch আর R-type

Fetch: PC → instruction memory, আর PC + 4

প্রতিটি instruction-এর কাজ শুরু একইভাবে। PC-র মান যায় instruction memory-র ঠিকানায়, আর কিছুক্ষণ পরে বেরিয়ে আসে ৩২-বিটের instruction. একই সময়ে PC-র মান যায় একটি আলাদা adder-এ, যেখানে ৪ যোগ হয় — কারণ RV32I-এর প্রতিটি instruction ৪ byte, আর মেমরি byte-ঠিকানার। Branch না থাকলে পরের clock-এর ধারে PC-তে বসবে PC + 4. এই অংশটিকে বলে instruction fetch.

প্রশ্ন জাগতে পারে, ALU তো যোগ করতে পারে — PC + 4-এর জন্য আলাদা adder কেন? কারণ single-cycle-এ প্রতিটি unit এক cycle-এ শুধু একবার ব্যবহার করা যায়। add-এর cycle-এ ALU ব্যস্ত rs1 + rs2 নিয়ে; একই সময়ে PC + 4-ও দরকার। তাই আলাদা adder. একই কারণে instruction আর ডেটার মেমরিও আলাদা: lw-এর একটি cycle-এ দুবার মেমরি লাগে — একবার instruction আনতে, একবার ডেটা আনতে। এটি Harvard-ধাঁচের নকশা।

R-type: দুই register পড়া, ALU, এক register-এ লেখা

add x7, x5, x6 নিন। Instruction-এর বিট ১৯..১৫ (rs1 = 5) যায় register file-এর প্রথম read port-এ, বিট ২৪..২০ (rs2 = 6) দ্বিতীয়টিতে, বিট ১১..৭ (rd = 7) যায় write-এর ঠিকানায়। RD1 আর RD2 সরাসরি ALU-র দুই ইনপুটে; ALU-র ফল ফিরে আসে register file-এর write data (WD)-তে। RegWrite = 1, তাই cycle-এর শেষের ধারে x7-এ ফল লেখা হয়। কোন কাজ (যোগ, বিয়োগ, AND, OR) — তা ঠিক করে funct3 আর funct7-এর বিট ৩০, ALU control-এর মাধ্যমে।

পর্ব ২৭-এ দেখেছিলেন rs1, rs2, rd যে format-এ আছে, সবখানে একই বিট-জায়গায় থাকে। এখানে তার লাভটা চোখে দেখা যায়: instruction-এর বিটগুলো সরাসরি তার দিয়ে register file-এ যায়, কোনো বাছাই ছাড়াই — control unit opcode বোঝার আগেই register পড়া শুরু হয়ে যায়।

৪ · আরও দুই টুকরো — load/store আর branch

Load আর store: ঠিকানা = rs1 + imm

lw x5, 8(x10)-এ ঠিকানা = x10 + ৮. ঠিকানার যোগটি ALU-ই করে, কিন্তু এবার দ্বিতীয় ইনপুট register নয়, ImmGen-এর আউটপুট। ALU-র ফল যায় data memory-র ঠিকানায়; MemRead = 1, তাই মেমরি সেই word ফেরত দেয়; আর সেই মান যায় register file-এর WD-তে, rd = x5-এ লেখার জন্য।

sw x7, 16(x10)-এ ঠিকানার হিসাব হুবহু এক (rs1 + imm), কিন্তু rs2-এর মান (RD2) যায় data memory-র write data-তে, MemWrite = 1, আর register file-এ কিছু লেখা হয় না (RegWrite = 0). এখানে ImmGen-কে S-format-এর দুই টুকরো জুড়তে হয়। Load-store ছাড়া আর কোনো instruction মেমরি ছোঁয় না — এটাই load-store architecture, আর তাই datapath-এ data memory মাত্র একটি জায়গায় বসে।

Branch: target = PC + imm, সিদ্ধান্ত Zero থেকে

beq x7, x8, 8-এর দুটি কাজ। প্রথমত তুলনা: RD1 আর RD2 ALU-তে যায়, ALU বিয়োগ করে, আর Zero = 1 মানে দুটি সমান। দ্বিতীয়ত লক্ষ্য-ঠিকানা: আরেকটি adder PC আর ImmGen-এর offset (Shift left 1-এর পরে) যোগ করে branch target বানায়। ALU তুলনায় ব্যস্ত, তাই এই যোগের জন্যও আলাদা adder. শেষে একটি সিদ্ধান্ত: Branch control signal = 1 আর Zero = 1 হলে PC-তে যাবে target, নইলে PC + 4.

খেয়াল করুন, offset যোগ হয় এই instruction-এর নিজের PC-র সাথে, PC + 4-এর সাথে নয় — RISC-V-এর নিয়ম এটাই (পর্ব ২৯)। MIPS-এ ছিল উল্টো, PC + 4-এর সাথে; পুরোনো বই থেকে শিখলে এখানে ভুল হয়।

৫ · সব জোড়া লাগানো — তিনটি mux আর পূর্ণ datapath

এবার চারটি টুকরো একটি circuit-এ জুড়তে হবে, যাতে একই hardware আটটি instruction-ই চালায়। যেখানেই একটি ইনপুটে দুই জায়গা থেকে মান আসতে চায়, সেখানে একটি mux বসে। তিনটি এমন জায়গা আছে:

• ALUSrc mux — ALU-র দ্বিতীয় ইনপুট: R-type আর beq চায় RD2 (0), lw, sw, addi চায় immediate (1).
• MemtoReg mux — register file-এ কী লেখা হবে: R-type আর addi চায় ALU-র ফল (0), lw চায় মেমরি থেকে আসা মান (1).
• PCSrc mux — PC-র পরের মান: সাধারণত PC + 4 (0), branch নেওয়া হলে target (1). PCSrc = Branch AND Zero.

নিচের stepper-এ দেখুন datapath কীভাবে একটি একটি উপাদান আর mux যোগ করে বড় হয়:

PC ──► Instruction memory ──► instruction
PC ──► [ + 4 ] ──► PC   (পরের clock-এর ধারে)

উপাদান: PC, IMem, adder
চলে: কিছুই না — শুধু instruction আসে

inst[19:15] ──► RF rs1 ──► RD1 ──► ALU A
inst[24:20] ──► RF rs2 ──► RD2 ──► ALU B
ALU result  ──► RF WD   (rd = inst[11:7])
control: RegWrite, ALU control

চলে: add, sub, and, or

ALU B   ◄── ALUSrc mux  (0: RD2 │ 1: imm)
RF WD   ◄── MemtoReg mux (0: ALU │ 1: Mem)
ALU result ──► DMem address
RD2        ──► DMem write data
control: + ALUSrc, MemtoReg, MemRead, MemWrite

চলে: + lw, sw, addi

imm ──► [<<1] ──► [ Add ] ◄── PC   = target
PC  ◄── PCSrc mux (0: PC+4 │ 1: target)
PCSrc = Branch AND Zero
control: + Branch, ALUOp = 01 (বিয়োগ)

চলে: + beq

inst[6:0] ──► Control ──► ALUSrc, MemtoReg,
                         RegWrite, MemRead,
                         MemWrite, Branch, ALUOp
ALUOp + inst[30,14:12] ──► ALU control

মোট: ৩টি mux, ২টি adder, ২টি মেমরি,
১টি register file, ১টি ALU, ১টি ImmGen

এবার পুরো ছবিটি একসাথে। কালো তার ডেটা বহন করে, কমলা ড্যাশ-দাগ control সংকেত। ছবিটি বড়; ফোনে আঙুল দিয়ে zoom করে দেখতে পারেন।

Control signal-এর এক ঝলক

প্রতিটি instruction শ্রেণির জন্য control unit কোন মান দেয়, তার সংক্ষিপ্ত টেবিল নিচে। এই টেবিল কীভাবে truth table থেকে gate-এ বানানো হয়, আর ALU control-এর পুরো নকশা — সেটি পর্ব ৩৩-এর বিষয়। এখানে শুধু মানগুলো পড়তে শিখুন; X মানে don't care — যেটিই হোক ফল বদলায় না।

ALUOp = 00 মানে যোগ (ঠিকানার হিসাব), 01 মানে বিয়োগ (beq-এর তুলনা), 10 মানে funct3/funct7 দেখে কাজ বাছাই (R-type). *addi Patterson–Hennessy-এর মূল টেবিলে নেই; এখানে তাকে ALUOp = 00 (যোগ) দেওয়া হলো, 10 নয় — কারণ addi-এর inst[30] immediate-এর একটি বিট; ALUOp = 10 দিলে ALU control সেটিকে funct7-এর বিট ভেবে ঋণাত্মক immediate-এ যোগের বদলে বিয়োগ করে ফেলত। andi, ori, slti যোগ করলে ALU control-কে funct3 দেখতে হবে, তখন আলাদা ALUOp লাগে — পর্ব ৩৩-এ।

৬ · মান ধরে trace — প্রতিটি তারে কী আছে

ছবি মুখস্থ করে লাভ কম; আসল বোঝা আসে একটি instruction-কে সংখ্যা ধরে এক unit থেকে আরেক unit-এ নিয়ে গেলে। ধরুন শুরুতে x10 = 0x1000, মেমরির 0x1008 ঠিকানায় ৪২ আর 0x100C-তে ৮, PC = 0x00. প্রথম instruction lw x5, 8(x10), যার word 0x00852283. নিচে প্রতিটি ধাপে কোন তারে কোন মান, আর সেই মান কখন স্থির হয় (অংশ ৭-এর পাঠ্যবই-সংখ্যায়: I-mem ২০০, register পড়া ৫০, ALU ১০০, D-mem ২০০, register-এ লেখার setup ৫০ ps), দেখুন।

R-type-এর পথ এর চেয়ে ছোট: add x7, x5, x6-এ RD1 = ৪২, RD2 = ৮, ALUSrc = 0 বলে B = ৮, ALU ফল ৫০, MemtoReg = 0 বলে WD = ৫০. Data memory চুপচাপ বসে থাকে (MemRead = MemWrite = 0). sw x7, 16(x10)-এ ঠিকানা 0x1010, write data = RD2 = ৫০, MemWrite = 1, আর ধারে মেমরিতে ৫০ লেখা হয়; register file-এ কিছু নয়। কোন instruction কোন unit ব্যবহার করে, এক টেবিলে:

“—” মানে unit-টি সেই cycle-এ কোনো কাজে লাগে না, কিন্তু hardware তো আছে, তার মধ্যে বিদ্যুৎও যায়। Single-cycle-এ কোনো unit অন্য instruction-কে ধার দেওয়া যায় না — সবাই একই cycle-এ একটি instruction-এর জন্য বসে থাকে।

beq — নেওয়া আর না-নেওয়া

একই beq x7, x8, 8 word (0x00838463) প্রোগ্রামে দুবার আছে: 0x14-এ, যখন x7 = ৫০ আর x8 = ৩৪, আর 0x1C-তে, যখন মাঝের addi x8, x8, 16 x8-কে ৫০ বানিয়েছে। Branch নেওয়া হবে কি না, তা পুরোপুরি ALU-র Zero আর PCSrc mux-এর ওপর নির্ভর করে:

নিজে চালিয়ে দেখুন — একটি single-cycle simulator

নিচের প্রোগ্রাম এই পর্বের CPU-কে সফটওয়্যারে নকল করে। প্রতিটি instruction-এর জন্য এটি word থেকে field বের করে (পর্ব ২৭-এর decode), opcode দিয়ে control টেবিল দেখে, ImmGen চালায়, তারপর তিনটি mux-এর বাছাই মেনে প্রতিটি তারের মান হিসাব করে। লক্ষ্য করুন, register, মেমরি আর PC-তে লেখা হয় লুপের একদম শেষে — সেটিই clock-এর ধার। প্রোগ্রামের দশটি word পর্ব ২৭-এর নিয়মে আলাদা একটি Python encoder দিয়ে বানানো।

// Single-cycle RV32I subset: one instruction per clock -> fields, control, datapath wires.
const prog = [0x00852283, 0x00C52303, 0x006283B3, 0x00752823, 0x40628433,
  0x00838463, 0x01040413, 0x00838463, 0x0062E4B3, 0x0062F4B3];
const x = new Array(32).fill(0); x[10] = 0x1000;              // x0 stays 0
const mem = { 0x1008: 42, 0x100C: 8 };                         // data memory (words)
const bit = (w, hi, lo) => (w >>> lo) & ((1 << (hi - lo + 1)) - 1);
const sx = (v, n) => (v << (32 - n)) >> (32 - n);              // sign-extend n bits
const hex = (v, n = 2) => "0x" + (v >>> 0).toString(16).toUpperCase().padStart(n, "0");
const CTRL = { // ALUSrc MemtoReg RegWrite MemRead MemWrite Branch ALUOp
  0x33: ["R", "0 0 1 0 0 0 10"], 0x13: ["I", "1 0 1 0 0 0 00"], 0x03: ["I", "1 1 1 1 0 0 00"],
  0x23: ["S", "1 x 0 0 1 0 00"], 0x63: ["B", "0 x 0 0 0 1 01"] };
const immGen = (w, f) => f === "I" ? sx(bit(w, 31, 20), 12)
  : f === "S" ? sx(bit(w, 31, 25) << 5 | bit(w, 11, 7), 12)
  : f === "B" ? sx(bit(w, 31, 31) << 12 | bit(w, 7, 7) << 11 | bit(w, 30, 25) << 5 | bit(w, 11, 8) << 1, 13) : 0;
let pc = 0;
while (pc / 4 < prog.length) {
  const w = prog[pc / 4], op = bit(w, 6, 0), rd = bit(w, 11, 7), f3 = bit(w, 14, 12);
  const rs1 = bit(w, 19, 15), rs2 = bit(w, 24, 20), f7 = bit(w, 31, 25), [fmt, c] = CTRL[op], s = c.split(" ");
  const rd1 = x[rs1], rd2 = x[rs2], imm = immGen(w, fmt), b = s[0] === "1" ? imm : rd2;   // ALUSrc mux
  const opn = s[6] === "00" ? "add" : s[6] === "01" ? "sub"                              // ALU control
    : { "0,0": "add", "0,32": "sub", "7,0": "and", "6,0": "or" }[f3 + "," + f7];
  const alu = { add: rd1 + b, sub: rd1 - b, and: rd1 & b, or: rd1 | b }[opn] | 0, zero = alu === 0 ? 1 : 0;
  const rdata = s[3] === "1" ? (mem[alu] ?? 0) : "-", wb = s[1] === "1" ? rdata : alu;  // MemtoReg mux
  const next = s[5] === "1" && zero ? pc + imm : pc + 4;                                  // PCSrc mux
  const fld = (fmt === "R" || fmt === "I" ? `rd=x${rd} ` : "") + `rs1=x${rs1} ` +
    (fmt === "I" ? "" : `rs2=x${rs2} `) + `f3=${f3}` + (fmt === "R" ? ` f7=${hex(f7)}` : "");
  console.log(`PC=${hex(pc)} ${hex(w, 8)} ${fmt}  ${fld}  ctrl=${c}`);
  console.log(`   RD1=${rd1} RD2=${rd2} imm=${imm} ALU(${opn})=${op === 0x03 || op === 0x23 ? hex(alu, 4) : alu}` +
    ` Zero=${zero} MemData=${rdata} WB=${s[2] === "1" ? wb : "-"} nextPC=${hex(next)}`);
  if (s[4] === "1") mem[alu] = rd2;                              // clock edge: memory write
  if (s[2] === "1" && rd !== 0) x[rd] = wb;                      // clock edge: register write
  pc = next;                                                     // clock edge: PC update
}
console.log(`after the run: x5..x9 = ${x.slice(5, 10).join(", ")}, mem[0x1010] = ${mem[0x1010]}`);

PC=0x00 0x00852283 I  rd=x5 rs1=x10 f3=2  ctrl=1 1 1 1 0 0 00
   RD1=4096 RD2=0 imm=8 ALU(add)=0x1008 Zero=0 MemData=42 WB=42 nextPC=0x04
PC=0x04 0x00C52303 I  rd=x6 rs1=x10 f3=2  ctrl=1 1 1 1 0 0 00
   RD1=4096 RD2=0 imm=12 ALU(add)=0x100C Zero=0 MemData=8 WB=8 nextPC=0x08
PC=0x08 0x006283B3 R  rd=x7 rs1=x5 rs2=x6 f3=0 f7=0x00  ctrl=0 0 1 0 0 0 10
   RD1=42 RD2=8 imm=0 ALU(add)=50 Zero=0 MemData=- WB=50 nextPC=0x0C
PC=0x0C 0x00752823 S  rs1=x10 rs2=x7 f3=2  ctrl=1 x 0 0 1 0 00
   RD1=4096 RD2=50 imm=16 ALU(add)=0x1010 Zero=0 MemData=- WB=- nextPC=0x10
PC=0x10 0x40628433 R  rd=x8 rs1=x5 rs2=x6 f3=0 f7=0x20  ctrl=0 0 1 0 0 0 10
   RD1=42 RD2=8 imm=0 ALU(sub)=34 Zero=0 MemData=- WB=34 nextPC=0x14
PC=0x14 0x00838463 B  rs1=x7 rs2=x8 f3=0  ctrl=0 x 0 0 0 1 01
   RD1=50 RD2=34 imm=8 ALU(sub)=16 Zero=0 MemData=- WB=- nextPC=0x18
PC=0x18 0x01040413 I  rd=x8 rs1=x8 f3=0  ctrl=1 0 1 0 0 0 00
   RD1=34 RD2=0 imm=16 ALU(add)=50 Zero=0 MemData=- WB=50 nextPC=0x1C
PC=0x1C 0x00838463 B  rs1=x7 rs2=x8 f3=0  ctrl=0 x 0 0 0 1 01
   RD1=50 RD2=50 imm=8 ALU(sub)=0 Zero=1 MemData=- WB=- nextPC=0x24
PC=0x24 0x0062F4B3 R  rd=x9 rs1=x5 rs2=x6 f3=7 f7=0x00  ctrl=0 0 1 0 0 0 10
   RD1=42 RD2=8 imm=0 ALU(and)=8 Zero=0 MemData=- WB=8 nextPC=0x28
after the run: x5..x9 = 42, 8, 50, 50, 8, mem[0x1010] = 50

৭ · এক লম্বা clock — critical path আর cycle time-এর হিসাব

Single-cycle CPU-তে clock-এর কাজ সহজ: প্রতিটি উঠন্ত ধারে (rising edge) PC, register file আর data memory নতুন মান নেয়; দুই ধারের মাঝে বাকি সব combinational. তাই পর্ব ১৮-এর নিয়ম সরাসরি খাটে: cycle time হতে হবে সবচেয়ে দীর্ঘ state-থেকে-state পথের সমান বা বেশি — সেই পথই critical path.

T_c ≥ t_pcq + (পথের সব combinational delay) + t_setup,   সব instruction-এর পথের মধ্যে সর্বোচ্চটি

পাঠ্যবইয়ের হিসাব

পরীক্ষার সবচেয়ে প্রচলিত সংখ্যা: instruction memory ২০০ ps, register file পড়া ৫০ ps, ALU ১০০ ps, data memory ২০০ ps, register file-এ লেখার setup ৫০ ps; mux, ImmGen, control, PC-র clock-to-Q আর তারের delay শূন্য ধরা; adder ১০০ ps. প্রতিটি শ্রেণির পথ:

beq-এ target adder-এর পথও আছে: ২০০ (I-mem) + ০ (ImmGen) + ১০০ (adder) = ৩০০ ps, যা তুলনার পথের (৩৫০) চেয়ে ছোট, তাই ৩৫০-ই থাকে। PC + 4-এর পথ মাত্র ১০০ ps. সুতরাং critical path হলো lw: instruction memory → register পড়া → ALU → data memory → MemtoReg mux → register file-এর setup. T_c = ৬০০ ps, f = ১ / ৬০০ ps ≈ ১.৬৬৭ GHz. কিন্তু প্রতিটি instruction — এমনকি ৩৫০ ps-এর beq — পায় সেই একই ৬০০ ps.

Instruction mix আর “পরিবর্তনশীল clock”-এর কল্পনা

একটি প্রোগ্রামে ধরুন ২৫% lw, ১০% sw, ৪৫% R-type, ২০% beq (instruction mix). গড় দরকার = ০.২৫ × ৬০০ + ০.১০ × ৫৫০ + ০.৪৫ × ৪০০ + ০.২০ × ৩৫০ = ১৫০ + ৫৫ + ১৮০ + ৭০ = ৪৫৫ ps. অর্থাৎ গড়ে প্রতিটি cycle-এর ১৪৫ ps (২৪.২%) অপেক্ষায় যায়। যদি কোনোভাবে প্রতিটি instruction-কে ঠিক তার দরকারি সময় দেওয়া যেত (পরিবর্তনশীল দৈর্ঘ্যের clock), speedup হতো ৬০০ / ৪৫৫ ≈ ১.৩২ গুণ। বাস্তবে এমন clock বানানো কঠিন (ভাবনার প্রশ্ন ৩), কিন্তু হিসাবটি বলে দেয় কোথায় লাভ লুকিয়ে আছে।

Iron law দিয়ে পুরো ছবি: CPU time = instruction count × CPI × T_c. Single-cycle-এ CPI = ১ (সবচেয়ে কম সম্ভব), কিন্তু T_c = ৬০০ ps (সবচেয়ে বেশি)। ১০০ কোটি instruction-এ সময় ১০^৯ × ১ × ৬০০ ps = ০.৬ সেকেন্ড। CPI কম দেখে বিভ্রান্ত হওয়া চলবে না।

নিচের calculator যেকোনো delay-এর সেট থেকে এই হিসাব করে। দ্বিতীয় সেটে বাস্তবের মতো কিছু খরচ যোগ করা হয়েছে — PC-র clock-to-Q ৩০, ImmGen ৩০, প্রতিটি mux ২০, register setup ২০ ps — দেখুন critical path কীভাবে mux-এর পথ ধরে:

// Single-cycle timing: time each instruction class needs; clock period = the slowest one.
function classTimes(d) {
  const front = d.pcq + d.imem;                       // PC -> instruction bits ready
  const bViaMux = d.rf + d.mux;                        // ReadData2 -> ALUSrc mux -> ALU
  const immPath = Math.max(d.rf, d.imm + d.mux);       // rs1 read vs ImmGen -> mux
  return {
    "R-type": front + bViaMux + d.alu + d.mux + d.rfSetup,
    "lw":     front + immPath + d.alu + d.dmem + d.mux + d.rfSetup,
    "sw":     front + immPath + d.alu + d.dmem,
    "beq":    front + Math.max(bViaMux + d.alu, d.imm + d.add) + d.mux + d.pcSetup };
}
const mix = { "R-type": 0.45, lw: 0.25, sw: 0.10, beq: 0.20 };   // instruction mix
function report(name, d) {
  const t = classTimes(d), Tc = Math.max(...Object.values(t));
  const pc4 = d.pcq + d.add + d.mux + d.pcSetup;
  console.log(`${name}: Tc = ${Tc} ps, f = ${(1000 / Tc).toFixed(3)} GHz (PC+4 path ${pc4} ps)`);
  for (const [k, v] of Object.entries(t))
    console.log(`  ${k.padEnd(6)} needs ${String(v).padStart(3)} ps, wasted ${String(Tc - v).padStart(3)} ps` +
      ` (${(100 * (Tc - v) / Tc).toFixed(1)}% of the cycle)`);
  const avg = Object.entries(mix).reduce((s, [k, p]) => s + p * t[k], 0);
  console.log(`  mix: average need ${avg.toFixed(1)} ps, average waste ${(Tc - avg).toFixed(1)} ps` +
    ` (${(100 * (Tc - avg) / Tc).toFixed(1)}%)`);
  console.log(`  ideal variable-length clock: speedup = ${Tc} / ${avg.toFixed(1)} = ${(Tc / avg).toFixed(3)}x`);
}
report("A (textbook units)", { pcq: 0, imem: 200, rf: 50, imm: 0, mux: 0, alu: 100,
  dmem: 200, rfSetup: 50, add: 100, pcSetup: 0 });
report("B (with register and mux overheads)", { pcq: 30, imem: 200, rf: 50, imm: 30, mux: 20, alu: 100,
  dmem: 200, rfSetup: 20, add: 100, pcSetup: 20 });

A (textbook units): Tc = 600 ps, f = 1.667 GHz (PC+4 path 100 ps)
  R-type needs 400 ps, wasted 200 ps (33.3% of the cycle)
  lw     needs 600 ps, wasted   0 ps (0.0% of the cycle)
  sw     needs 550 ps, wasted  50 ps (8.3% of the cycle)
  beq    needs 350 ps, wasted 250 ps (41.7% of the cycle)
  mix: average need 455.0 ps, average waste 145.0 ps (24.2%)
  ideal variable-length clock: speedup = 600 / 455.0 = 1.319x
B (with register and mux overheads): Tc = 620 ps, f = 1.613 GHz (PC+4 path 170 ps)
  R-type needs 440 ps, wasted 180 ps (29.0% of the cycle)
  lw     needs 620 ps, wasted   0 ps (0.0% of the cycle)
  sw     needs 580 ps, wasted  40 ps (6.5% of the cycle)
  beq    needs 440 ps, wasted 180 ps (29.0% of the cycle)
  mix: average need 499.0 ps, average waste 121.0 ps (19.5%)
  ideal variable-length clock: speedup = 620 / 499.0 = 1.242x

এই অপচয়ের দুটি জবাব আছে, আর দুটিই এই মডিউলের পরের পর্ব। পর্ব ৩৪-এর multi-cycle নকশা instruction-কে কয়েকটি ছোট clock-এ ভাগ করে, যাতে beq কম cycle আর lw বেশি cycle নেয়, আর একটি ALU বা একটি মেমরি একাধিক ধাপে ভাগাভাগি করা যায়। পর্ব ৩৫-এর pipelining একই ছোট ধাপগুলোতে একসাথে কয়েকটি instruction চালায় — গার্মেন্টস কারখানার assembly line-এর মতো। দুটিরই শুরু এই হিসাব থেকে: single-cycle-এর ৬০০ ps-কে ভাঙতে হবে।

৮ · নতুন instruction যোগ — addi, jal আর ImmGen-এর ভূমিকা

একটি datapath-এর গুণ বোঝা যায় নতুন instruction যোগ করতে কত কম বদল লাগে তা দেখে। পদ্ধতি সবসময় একই: (১) instruction-টির কাজ register transfer-এ লিখুন, (২) দেখুন কোন মান কোন unit-এর ইনপুটে নতুন উৎস থেকে আসছে, (৩) সেখানে mux-এর নতুন ইনপুট বা নতুন mux বসান, (৪) control টেবিলে নতুন সারি আর দরকারে নতুন সংকেত যোগ করুন।

addi — কোনো নতুন hardware নয়

addi rd, rs1, imm: rd ← rs1 + imm. ALU-র B-তে immediate (lw-এর মতো, ALUSrc = 1), কিন্তু লেখা হয় ALU-র ফল (R-type-এর মতো, MemtoReg = 0). দুটি পথই আগে থেকে আছে; শুধু control-এ একটি নতুন সারি: ALUSrc = 1, MemtoReg = 0, RegWrite = 1, MemRead = 0, MemWrite = 0, Branch = 0, ALUOp = 00. ImmGen I-format আগেই জানে (lw-এর জন্য)। সময়: ২০০ + ৫০ + ১০০ + ৫০ = ৪০০ ps, R-type-এর সমান।

jal — তিনটি ছোট বদল

jal rd, offset: rd ← PC + 4, আর PC ← PC + offset (J-format, ±১ MiB). তিনটি জিনিস নতুন:

1. ImmGen-এ J-format: inst[31], inst[19:12], inst[20], inst[30:21] জুড়ে ২১-বিট offset (পর্ব ২৭-এর টেবিল)। ImmGen-এর ভেতরের mux-এ আরেকটি পছন্দ।
2. লেখার মানের নতুন উৎস: register file-এ যাবে PC + 4, যা ALU বা মেমরি থেকে আসে না। তাই MemtoReg mux-কে ৩-ইনপুটের করতে হয় (ALU, Mem, PC + 4), select ২ বিটের। Harris & Harris-এর বই এই চওড়া সংকেতকে ResultSrc বলে।
3. PC-র সিদ্ধান্ত: jal সবসময় লাফায়। target adder (PC + imm) আগে থেকেই আছে, শুধু সিদ্ধান্তের logic বদলায়: PCSrc = (Branch AND Zero) OR Jump. নতুন control সংকেত Jump.

উদাহরণ: PC = 0x30-এ jal x1, 2048 (0x001000EF) — x1 ← 0x34, PC ← 0x30 + 0x800 = 0x830. সময়: target = ২০০ + ১০০ = ৩০০ ps, PC + 4 → register = ১০০ + mux + setup ৫০ = ১৫০ ps — critical path বাড়ে না। jalr যোগ করলে PC-র তৃতীয় উৎস লাগে — rs1 + imm, যা ALU-র ফল — তাই PCSrc mux-ও তিন-ইনপুটের হয়; lui-এর জন্য ImmGen-এ U-format আর ALU-কে immediate “পার করে দেওয়া”-র ব্যবস্থা; auipc-এর জন্য ALU-র A ইনপুটে PC আনার mux. প্রতিটি নতুন instruction মানে একটু বেশি mux, একটু চওড়া control — কিন্তু datapath-এর মূল কাঠামো একই থাকে।

ImmGen-কে কাজে দেখুন

Datapath-এর তিনটি mux-ই সহজ; সবচেয়ে বেশি বিট-জোড়ার কাজ ImmGen-এ। নিচের প্রোগ্রাম ছয়টি জানা word থেকে immediate বের করে sign extend করে, Patterson–Hennessy-এর ধাঁচে — B-format-এ ImmGen দেয় imm[12:1], তারপর Shift left 1:

// ImmGen: pull the immediate out of an I, S or B word and sign-extend it to 32 bits.
const bit = (w, hi, lo) => (w >>> lo) & ((1 << (hi - lo + 1)) - 1);
const sx = (v, n) => (v << (32 - n)) >> (32 - n);                  // copy bit n-1 upward
const hex8 = v => "0x" + (v >>> 0).toString(16).toUpperCase().padStart(8, "0");
const grp = (v, n) => v.toString(2).padStart(n, "0").replace(/(?=(\d{4})+$)/g, " ").trim();
function immGen(w) {                  // returns [format, 12 raw bits, where they came from]
  const op = bit(w, 6, 0);
  if (op === 0x03 || op === 0x13) return ["I", bit(w, 31, 20), "inst[31:20]"];
  if (op === 0x23) return ["S", bit(w, 31, 25) << 5 | bit(w, 11, 7), "inst[31:25] + inst[11:7]"];
  if (op === 0x63) return ["B", bit(w, 31, 31) << 11 | bit(w, 7, 7) << 10 | bit(w, 30, 25) << 4 |
    bit(w, 11, 8), "inst[31] + inst[7] + inst[30:25] + inst[11:8]"];
  return ["?", 0, "no immediate"];
}
const words = [[0x00852283, "lw   x5, 8(x10)"], [0xFFF00293, "addi x5, x0, -1"],
  [0x00752823, "sw   x7, 16(x10)"], [0xFE992E23, "sw   x9, -4(x18)"],
  [0x00838463, "beq  x7, x8, 8"], [0xFEB50CE3, "beq  x10, x11, -8"]];
for (const [w, asm] of words) {
  const [f, raw, from] = immGen(w), ext = sx(raw, 12);
  console.log(`${hex8(w)}  ${asm.padEnd(17)} ${f}: ${from}`);
  let line = `    12 bits ${grp(raw, 12)} -> sign-extended ${hex8(ext)} = ${ext}`;
  if (f === "B") line += ` (imm[12:1]); <<1 -> byte offset ${ext * 2}`;
  console.log(line);
}

0x00852283  lw   x5, 8(x10)   I: inst[31:20]
    12 bits 0000 0000 1000 -> sign-extended 0x00000008 = 8
0xFFF00293  addi x5, x0, -1   I: inst[31:20]
    12 bits 1111 1111 1111 -> sign-extended 0xFFFFFFFF = -1
0x00752823  sw   x7, 16(x10)  S: inst[31:25] + inst[11:7]
    12 bits 0000 0001 0000 -> sign-extended 0x00000010 = 16
0xFE992E23  sw   x9, -4(x18)  S: inst[31:25] + inst[11:7]
    12 bits 1111 1111 1100 -> sign-extended 0xFFFFFFFC = -4
0x00838463  beq  x7, x8, 8    B: inst[31] + inst[7] + inst[30:25] + inst[11:8]
    12 bits 0000 0000 0100 -> sign-extended 0x00000004 = 4 (imm[12:1]); <<1 -> byte offset 8
0xFEB50CE3  beq  x10, x11, -8 B: inst[31] + inst[7] + inst[30:25] + inst[11:8]
    12 bits 1111 1111 1100 -> sign-extended 0xFFFFFFFC = -4 (imm[12:1]); <<1 -> byte offset -8

৯ · AI-এর যুগে — datapath-এর উত্তর যাচাই

Datapath-এর প্রশ্নে AI সাধারণত আত্মবিশ্বাসী আর সুন্দর উত্তর দেয় — একটি টেবিল, একটি ছবির বর্ণনা, একটি সংখ্যা। কিন্তু এই বিষয়ে পাঠ্যবইয়ের দুই প্রজন্ম (MIPS আর RISC-V) আর অনেক রকম নকশা-রীতি মিশে আছে, তাই ভুলও সূক্ষ্ম। সুখবর: প্রায় সবকিছু হাতে বা ছোট একটি simulator-এ যাচাই করা যায়।

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

• উত্তরে RegDst, Shift left 2, branch delay slot-এর মতো MIPS-এর জিনিস নেই — থাকলে কেন, তা জিজ্ঞেস করেছি
• প্রতিটি শ্রেণির পথ নিজে লিখে যোগ করেছি; সমান্তরাল পথে max নেওয়া হয়েছে কি না দেখেছি
• control টেবিলের প্রতিটি X যুক্তিতে মিলিয়েছি: সংকেতটি ভুল মান নিলেও ফল বদলায় না তো?
• একটি lw আর একটি beq (নেওয়া ও না-নেওয়া) সংখ্যা ধরে simulator-এ চালিয়ে মিলিয়েছি
• সম্ভব হলে নকশাটি Verilog-এ লিখে simulate করেছি (পর্ব ১৪), বা একটি পরিচিত শিক্ষামূলক RISC-V simulator-এ একই প্রোগ্রাম চালিয়ে register-এর মান মিলিয়েছি