Pipelining — পাঁচ ধাপের pipeline আর speedup-এর হিসাব

১ · Pipelining-এর মূল ভাবনা — লন্ড্রির দোকান আর গার্মেন্টসের লাইন

পর্ব ৩২-এ (Single-cycle datapath) একটি প্রসেসর বানানো হয়েছে, যেখানে প্রতিটি instruction এক লম্বা clock cycle-এ শুরু থেকে শেষ হয়। পর্ব ৩৪-এ (Multi-cycle datapath) একই কাজ কয়েকটি ছোট cycle-এ ভাগ করা হয়েছে। দুই নকশাতেই একটি মিল আছে: এক সময়ে মাত্র একটি instruction. Instruction যখন ALU-তে, তখন instruction memory বসে থাকে; যখন memory-তে, তখন ALU বসে থাকে। এই পর্বের প্রশ্ন: সব অংশকে একসাথে ব্যস্ত রাখা যায় কীভাবে?

এটিই pipelining: কাজকে কয়েকটি ধাপে (stage) ভাগ করা, আর ভিন্ন ভিন্ন কাজের ভিন্ন ধাপ একই সময়ে চালানো। নিচের stepper-এ চারটি বস্তা (A, B, C, D) আর চার ধাপ — W = ধোয়া, D = শুকানো, I = ইস্ত্রি, F = ভাঁজ; প্রতিটি ঘর ৩০ মিনিটের একটি সময়-খণ্ড।

load    1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
A       W  D  I  F  .  .  .  .  .  .  .  .  .  .  .  .

one load: 4 slots x 30 min = 2 hours (latency)

load    1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
A       W  D  I  F  .  .  .  .  .  .  .  .  .  .  .  .
B       .  .  .  .  W  D  I  F  .  .  .  .  .  .  .  .
C       .  .  .  .  .  .  .  .  W  D  I  F  .  .  .  .
D       .  .  .  .  .  .  .  .  .  .  .  .  W  D  I  F

4 loads x 2 hours = 16 slots = 8 hours
each machine is idle 3 slots out of every 4

load    1  2  3
A       W  D  I
B       .  W  D
C       .  .  W
D       .  .  .

slot 2: A in dryer, B in washer   (2 machines busy)
slot 3: A, B, C all moving        (3 machines busy)

load    1  2  3  4
A       W  D  I  F
B       .  W  D  I
C       .  .  W  D
D       .  .  .  W

slot 4: all 4 machines busy, A finishes at the end of slot 4

load    1  2  3  4  5  6  7
A       W  D  I  F  .  .  .
B       .  W  D  I  F  .  .
C       .  .  W  D  I  F  .
D       .  .  .  W  D  I  F

total = 4 + 4 - 1 = 7 slots = 3.5 hours
speedup = 8 / 3.5 = 2.29   (not 4!)
each load still takes 2 hours; one load leaves every 30 min

Latency বনাম throughput

পর্ব ০৩-এ (পারফরম্যান্স মাপা) দুটি মাপ দেখেছেন। Latency — একটি কাজ শুরু থেকে শেষ হতে কত সময়। Throughput — প্রতি একক সময়ে কয়টি কাজ শেষ হয়। লন্ড্রিতে latency ২ ঘণ্টাই থেকে গেছে, কিন্তু throughput ২ ঘণ্টায় ১টি বস্তা থেকে বেড়ে ৩০ মিনিটে ১টি — অর্থাৎ ৪ গুণ (দীর্ঘ সময়ের হিসাবে)। প্রোগ্রাম কোটি কোটি instruction চালায়, আর প্রোগ্রামের মোট সময় ঠিক করে throughput, একটি instruction-এর latency নয়। তাই pipelining একটি instruction-কে দ্রুত না করেও পুরো প্রোগ্রামকে দ্রুত করে।

২ · পাঁচ ধাপের RISC-V pipeline — IF, ID, EX, MEM, WB

পর্ব ৩২-এর single-cycle datapath-কে স্বাভাবিকভাবেই পাঁচ টুকরো করা যায়, কারণ প্রতিটি instruction মোটামুটি একই পথে চলে: instruction আনা, বোঝা, হিসাব, memory, ফল লেখা। এই পাঁচ ধাপ (Patterson–Hennessy-র RISC-V সংস্করণের নিয়মে, যা এই কোর্সের মূল ধারা) হলো:

লক্ষ করুন দুটি বিষয়। প্রথমত, register file দুই ধাপে ব্যবহার হয় — ID-তে পড়া, WB-তে লেখা। এজন্য pipeline-এর ছবিতে register file-কে প্রায়ই ID-তে আঁকা হয়, আর WB থেকে একটি তার পেছনে ফিরে আসে। দ্বিতীয়ত, memory-ও দুই ধাপে লাগে — IF-এ instruction, MEM-এ data. একই cycle-এ একটি instruction IF-এ আর আরেকটি MEM-এ থাকতে পারে, তাই দুটি আলাদা memory পথ লাগে: আলাদা instruction cache আর data cache (অংশ ৮-এ এর কারণ, structural hazard).

কেন প্রতিটি instruction পাঁচ ধাপই পার হয়? add-এর MEM-এ কোনো কাজ নেই — তবু সে MEM ধাপে এক cycle কাটায়, তারপর WB-তে লেখে। কারণ নিয়ম সরল রাখা: প্রতিটি ধাপ প্রতি cycle-এ ঠিক একটি instruction নেয়। add যদি MEM বাদ দিয়ে চতুর্থ cycle-এই WB করত, আর তার আগের lw একই cycle-এ তার পঞ্চম cycle-এ WB করত, তবে দুজনে একই সাথে register file-এর একটিমাত্র write port চাইত — একটি সংঘাত। সবাইকে একই পাঁচ ধাপের ছন্দে রাখলে এমন সংঘাতই তৈরি হয় না।

৩ · Pipeline register — ধাপগুলোর মাঝের হাতবদল

লন্ড্রিতে বস্তা নিজেই পরের যন্ত্রে চলে যায়। Circuit-এ একটি instruction-এর “বস্তা” হলো তার সব তথ্য — instruction-এর বিট, register থেকে পড়া মান, immediate, ALU-র ফল, destination register-এর নম্বর আর control signal. দুই ধাপের মাঝে এগুলো ধরে রাখতে বসানো হয় pipeline register — পর্ব ১৮-এর (Timing আর clock) সাধারণ edge-triggered register-এর একটি চওড়া সারি। প্রতিটি clock edge-এ সব pipeline register একসাথে আগের ধাপের ফল তুলে নেয় আর পরের ধাপকে দেয়। নাম দেওয়া হয় দুই পাশের ধাপ দিয়ে: IF/ID, ID/EX, EX/MEM, MEM/WB. PC নিজেও একটি register, যা IF ধাপকে খাওয়ায়; WB-র পরে আলাদা কোনো pipeline register লাগে না, কারণ ফল সরাসরি register file-এ যায়।

Control signal তৈরি হয় ID-তে, চলে instruction-এর সাথে

পর্ব ৩৩-এ (Control unit) একটি টেবিল দেখেছেন: opcode দেখে control unit বলে দেয় ALUSrc, MemtoReg, RegWrite, MemRead, MemWrite, Branch আর ALUOp কোনটি কী হবে। Single-cycle নকশায় এই control signal-গুলো পুরো cycle ধরে স্থির থাকে, কারণ datapath-এ একটিই instruction. Pipeline-এ পাঁচটি instruction একসাথে — EX ধাপের ALU-কে তার নিজের instruction-এর ALUOp মানতে হবে, ID-তে যে নতুন instruction decode হচ্ছে তারটা নয়।

সমাধান সহজ আর সুন্দর: control unit ID ধাপে একবারই সব signal বানায়, তারপর সেগুলো instruction-এর ডেটার সাথে pipeline register-এ চড়ে এগোয়। তিন দলে ভাগ করা হয়: EX বিট (ALUOp, ALUSrc) — EX-এ ব্যবহার শেষ, তাই EX/MEM-এ আর যায় না; M বিট (MemRead, MemWrite, Branch) — MEM-এ শেষ; WB বিট (RegWrite, MemtoReg) — একেবারে শেষ পর্যন্ত যায়। তাই ছবিতে ID/EX-এ তিন দল, EX/MEM-এ দুই দল, MEM/WB-এ এক দল। একই যুক্তিতে rd-এর নম্বরও শেষ পর্যন্ত বয়ে নিতে হয় — WB ধাপে লেখার সময় IF/ID-তে ততক্ষণে অন্য instruction, তার rd ভিন্ন।

নিচের stepper-এ lw x5, 0(x10) পাঁচ cycle-এ চারটি pipeline register পেরিয়ে যায় (x10 = 100, memory[100] = 42). লক্ষ করুন, প্রতিটি register-এর পুরোনো জায়গায় সাথে সাথে পরের instruction বসে পড়ে — পাঁচটি instruction-এর প্রোগ্রামটি অংশ ৪-এর।

৪ · Pipeline diagram — instruction বনাম clock cycle

পরীক্ষায় আর নকশার আলোচনায় pipeline বোঝানোর সবচেয়ে প্রচলিত ছবি হলো pipeline diagram: সারিতে instruction, কলামে clock cycle, ঘরে ধাপের নাম। নিচের পাঁচটি RV32I instruction-এর মধ্যে কোনো নির্ভরতা নেই — কেউ আগের কারো লেখা register পড়ে না — তাই কোনো hazard নেই (hazard-এর কথা অংশ ৮-এ)।

টেবিলটি একটি সিঁড়ির মতো। প্রতিটি সারি আগেরটির চেয়ে এক ঘর ডানে সরে যায়, কারণ প্রতি cycle-এ একটি নতুন instruction IF-এ ঢোকে। কোনো কলাম ধরে নিচে পড়লে সেই cycle-এ pipeline-এর অবস্থা পাওয়া যায় — যেমন c5-এ পাঁচটি ধাপেই একজন করে: sub IF-এ, sw ID-তে, add EX-এ, addi MEM-এ, lw WB-তে। এটিই একমাত্র cycle, যখন pipeline সম্পূর্ণ পূর্ণ। নিচের stepper-এ একই জিনিস cycle ধরে ধরে দেখুন — এবার প্রতিটি সারি একটি ধাপ।

এই diagram যেকোনো instruction-তালিকার জন্য বানানো যায়। নিচের generator নিয়মটি সরাসরি কাজে লাগায়: instruction i (০ থেকে গোনা) cycle i + ১-এ IF-এ ঢোকে, তাই cycle c-তে সে আছে ধাপ নম্বর c − ১ − i-তে। তালিকায় instruction যোগ বা বাদ দিয়ে Run চাপুন — মোট cycle কীভাবে বদলায় দেখুন।

// Pipeline diagram for a hazard-free instruction list (5 stages).
// Instruction i (0-based) enters IF in cycle i+1 and is in stage s
// during cycle i+1+s.  Total cycles = k + n - 1.
const STAGES = ["IF", "ID", "EX", "MEM", "WB"];
const prog = [
  "lw   x5, 0(x10)",
  "addi x6, x0, 3",
  "add  x7, x1, x2",
  "sw   x8, 4(x10)",
  "sub  x9, x3, x4",
];
const k = STAGES.length, n = prog.length, total = k + n - 1;
let head = "instruction".padEnd(17);
for (let c = 1; c <= total; c++) head += ("c" + c).padStart(5);
console.log(head);
prog.forEach((ins, i) => {
  let row = ins.padEnd(17);
  for (let c = 1; c <= total; c++) {
    const s = c - 1 - i;                      // stage index in cycle c
    row += (s >= 0 && s < k ? STAGES[s] : ".").padStart(5);
  }
  console.log(row);
});
// Which cycles is the pipeline completely full?
const full = [];
for (let c = 1; c <= total; c++) if (c >= k && c <= n) full.push(c);
console.log("\nk = " + k + ", n = " + n + "  ->  total cycles = k + n - 1 = " + total);
console.log("pipeline full (all 5 stages busy) in cycle(s): " + full.join(", "));
console.log("unpipelined would need n * k = " + n * k + " cycles");
console.log("cycles per finished instruction = " + (total / n).toFixed(2));

instruction         c1   c2   c3   c4   c5   c6   c7   c8   c9
lw   x5, 0(x10)     IF   ID   EX  MEM   WB    .    .    .    .
addi x6, x0, 3       .   IF   ID   EX  MEM   WB    .    .    .
add  x7, x1, x2      .    .   IF   ID   EX  MEM   WB    .    .
sw   x8, 4(x10)      .    .    .   IF   ID   EX  MEM   WB    .
sub  x9, x3, x4      .    .    .    .   IF   ID   EX  MEM   WB

k = 5, n = 5  ->  total cycles = k + n - 1 = 9
pipeline full (all 5 stages busy) in cycle(s): 5
unpipelined would need n * k = 25 cycles
cycles per finished instruction = 1.80

একটি ছোট pipelined machine — প্রতিটি register-এর ভেতরে উঁকি

Diagram বলে কে কোথায়; কিন্তু প্রতিটি pipeline register-এ আসলে কোন মান আছে? নিচের ছোট simulator একই পাঁচটি instruction আসলে চালায় (x1 = 10, x2 = 20, x3 = 50, x4 = 7, x8 = 99, x10 = 100, memory[100] = 42). এর মূল কৌশলটি hardware-এর মতোই: প্রতিটি cycle-এ প্রথমে WB, তারপর MEM, EX, ID, IF হিসাব হয় — প্রতিটি ধাপ আগের cycle-এর pipeline register পড়ে — আর শেষে চারটি register একসাথে বদলায়, ঠিক যেমন clock edge-এ সব flip-flop একসাথে মান নেয়।

// Tiny 5-stage RV32I pipeline (no hazards in this program, so no
// forwarding or stalls). Each cycle we update the stages from WB back
// to IF, so every stage reads the pipeline register of the LAST cycle.
const x = new Array(32).fill(0); Object.assign(x, {1: 10, 2: 20, 3: 50, 4: 7, 8: 99, 10: 100});
const mem = {100: 42};
const P = [ {t: "lw x5,0(x10)", op: "lw", rd: 5, a: 10, imm: 0},
  {t: "addi x6,x0,3", op: "addi", rd: 6, a: 0, imm: 3},
  {t: "add x7,x1,x2", op: "add", rd: 7, a: 1, b: 2},
  {t: "sw x8,4(x10)", op: "sw", a: 10, b: 8, imm: 4},
  {t: "sub x9,x3,x4", op: "sub", rd: 9, a: 3, b: 4} ];
let IFID = null, IDEX = null, EXMEM = null, MEMWB = null, pc = 0;
const name = r => (r ? r.i.t.split(" ")[0] : "-");
for (let c = 1; c <= P.length + 4; c++) {
  let wb = "-";                                                 // WB
  if (MEMWB && MEMWB.i.rd) { x[MEMWB.i.rd] = MEMWB.v; wb = `x${MEMWB.i.rd}=${MEMWB.v}`; }
  let nMW = null;                                               // MEM
  if (EXMEM) { const e = EXMEM;
    if (e.i.op === "sw") mem[e.alu] = e.B;
    nMW = {i: e.i, v: e.i.op === "lw" ? mem[e.alu] : e.alu}; }
  let nEM = null;                                               // EX
  if (IDEX) { const d = IDEX, op = d.i.op;
    const alu = op === "add" ? d.A + d.B : op === "sub" ? d.A - d.B : d.A + d.i.imm;
    nEM = {i: d.i, alu, B: d.B}; }
  const nIE = IFID ? {i: IFID.i, A: x[IFID.i.a], B: x[IFID.i.b ?? 0]} : null;   // ID
  const nIF = pc / 4 < P.length ? {i: P[pc / 4], pc} : null;    // IF
  if (nIF) pc += 4;
  [IFID, IDEX, EXMEM, MEMWB] = [nIF, nIE, nEM, nMW];
  console.log(`c${c} IF/ID[${IFID ? name(IFID) + " pc=" + IFID.pc : "-"}]`.padEnd(23) +
    `ID/EX[${IDEX ? name(IDEX) + " A=" + IDEX.A + " B=" + IDEX.B : "-"}]`.padEnd(21) +
    `EX/MEM[${EXMEM ? name(EXMEM) + " alu=" + EXMEM.alu : "-"}]`.padEnd(19) +
    `MEM/WB[${MEMWB ? name(MEMWB) + " v=" + MEMWB.v : "-"}]`.padEnd(17) + "WB: " + wb);
}
console.log(`final: x5=${x[5]} x6=${x[6]} x7=${x[7]} x9=${x[9]} mem[104]=${mem[104]}`);

c1 IF/ID[lw pc=0]      ID/EX[-]             EX/MEM[-]          MEM/WB[-]        WB: -
c2 IF/ID[addi pc=4]    ID/EX[lw A=100 B=0]  EX/MEM[-]          MEM/WB[-]        WB: -
c3 IF/ID[add pc=8]     ID/EX[addi A=0 B=0]  EX/MEM[lw alu=100] MEM/WB[-]        WB: -
c4 IF/ID[sw pc=12]     ID/EX[add A=10 B=20] EX/MEM[addi alu=3] MEM/WB[lw v=42]  WB: -
c5 IF/ID[sub pc=16]    ID/EX[sw A=100 B=99] EX/MEM[add alu=30] MEM/WB[addi v=3] WB: x5=42
c6 IF/ID[-]            ID/EX[sub A=50 B=7]  EX/MEM[sw alu=104] MEM/WB[add v=30] WB: x6=3
c7 IF/ID[-]            ID/EX[-]             EX/MEM[sub alu=43] MEM/WB[sw v=104] WB: x7=30
c8 IF/ID[-]            ID/EX[-]             EX/MEM[-]          MEM/WB[sub v=43] WB: -
c9 IF/ID[-]            ID/EX[-]             EX/MEM[-]          MEM/WB[-]        WB: x9=43
final: x5=42 x6=3 x7=30 x9=43 mem[104]=99

৫ · Speedup-এর হিসাব — k + n − ১ থেকে k পর্যন্ত

এবার সাধারণ সূত্র। ধরুন pipeline-এ k-টি ধাপ, প্রতিটির সময় সমান τ, আর n-টি instruction, কোনো hazard নেই।

মোট সময়ের প্রমাণ। প্রথম instruction সব k ধাপ পেরোতে k cycle নেয় — সেটি শেষ হয় cycle k-এর শেষে। এরপর প্রতি cycle-এ একটি করে instruction শেষ হয়, কারণ instruction i + ১ ঠিক এক cycle পরে instruction i-এর পেছনে পেছনে চলে। বাকি n − ১টি instruction তাই আরও n − ১ cycle নেয়। মোট:

মোট cycle = k + (n − ১)  ⇒  T_pipe = (k + n − ১) · τ

বাড়তি k − ১ cycle হলো শুরুতে pipeline ভরা আর শেষে খালি হওয়ার খরচ — fill and drain; এই সময়ে সব ধাপ একসাথে কাজ করে না।

Pipeline ছাড়া — একই ধাপগুলো, কিন্তু এক instruction শেষ হলে তবেই পরেরটি — প্রতিটি instruction নেয় k·τ, তাই T_seq = n · k · τ. অতএব

Speedup S(n) = n · k / (k + n − ১)

সীমা। লব আর হরকে n দিয়ে ভাগ করুন: S(n) = k / (১ + (k − ১)/n). n → ∞ হলে (k − ১)/n → ০, তাই S → k. আর যেহেতু (k − ১)/n > ০ যেকোনো সসীম n আর k > ১-এর জন্য, S(n) সবসময় k-এর চেয়ে কম — k কখনো ছোঁয়া যায় না, শুধু কাছে যাওয়া যায়। আদর্শ speedup = ধাপের সংখ্যা, শর্ত তিনটি: (১) সব ধাপ সমান, (২) pipeline register-এর কোনো সময়-খরচ নেই, (৩) কোনো stall নেই। বাস্তবে তিনটিই ভাঙে — অংশ ৬ আর ৮-এ।

আদর্শ CPI = ১, আর বাস্তবের CPI

পর্ব ০৩-এর ভাষায় CPI (cycles per instruction) দেখুন। n-টি instruction-এ (k + n − ১) cycle, তাই CPI = (k + n − ১) / n, যা n বড় হলে ১-এ নামে। অর্থাৎ আদর্শ pipeline-এর CPI = ১ — প্রতি cycle-এ একটি instruction শেষ। (Single-cycle-এর CPI-ও ১, কিন্তু তার cycle অনেক লম্বা; multi-cycle-এর cycle ছোট, কিন্তু CPI ৩–৫. Pipeline দুইয়ের ভালোটা একসাথে নেয়: ছোট cycle এবং CPI ≈ ১.)

Hazard থাকলে কিছু instruction-কে অপেক্ষা করতে হয় — stall, আর pipeline-এ ঢোকে একটি খালি ধাপ, bubble. তখন:

CPI_pipeline = ১ + (প্রতি instruction-এ গড় stall cycle)

উদাহরণ। একটি প্রোগ্রামে ২৫% instruction lw, যার ৪০%-এর ঠিক পরেই একটি instruction তার ফল চায় আর ১ cycle stall হয়; ১৫% branch, যার ২০% ভুল অনুমান হয় আর প্রতিটিতে ২ cycle নষ্ট হয়। Stall = ০.২৫ × ০.৪ × ১ + ০.১৫ × ০.২ × ২ = ০.১০ + ০.০৬ = ০.১৬, তাই CPI = ১.১৬. অংশ ৬-এর T_stage = ২২০ ps নিলে প্রতি instruction-এ গড় সময় ১.১৬ × ২২০ = ২৫৫.২ ps, আর ৮২০ ps-এর single-cycle-এর তুলনায় speedup ৮২০ / ২৫৫.২ ≈ ৩.২১ (stall ছাড়া হতো ৩.৭৩)। এই stall কোথা থেকে আসে আর কীভাবে কমে — forwarding, load-use stall — পর্ব ৩৬-এ (Pipeline hazard), আর branch-এর অংশ পর্ব ৩৭-এ (Branch prediction).

৬ · অসম ধাপ আর register overhead — পরীক্ষার পূর্ণ numerical

বাস্তব ধাপগুলো সমান নয়। Memory পড়া আর ALU সাধারণত ধীর, register পড়া বা লেখা দ্রুত। কিন্তু pipeline-এর সব ধাপ একই clock শোনে — clock-কে সবচেয়ে ধীর ধাপের জন্য অপেক্ষা করতেই হবে। তার ওপর প্রতিটি pipeline register নিজেই সময় খায়: পর্ব ১৮-এর sequencing overhead, t_pcq + t_setup (আর skew). তাই:

T_stage = max(ধাপের delay) + t_reg,   যেখানে t_reg = t_pcq + t_setup

ধীরতম ধাপটি pipeline-এর critical path — পর্ব ১৮-এর ভাষায়, যে দুই register-এর মাঝে সবচেয়ে বেশি logic.

উদাহরণ: ২০০/১০০/২০০/২০০/১০০ ps, register overhead ২০ ps

একটি প্রসেসরে IF = ২০০, ID = ১০০, EX = ২০০, MEM = ২০০, WB = ১০০ ps; প্রতিটি register-এর overhead ২০ ps. (ক) single-cycle আর pipelined নকশার clock, (খ) একটি instruction-এর latency, (গ) ১, ৫ আর ১০,০০,০০০ (১০^৬) instruction-এর মোট সময়, throughput আর speedup বের করুন।

ধরে নেওয়া: single-cycle নকশাতেও cycle-এর শেষে একটি register (PC আর register file) আছে, তাই তারও একবার ২০ ps overhead লাগে। কিছু বইয়ের প্রশ্নে non-pipelined নকশার overhead ধরা হয় না — সেই হিসাব নিচে আলাদা দেখানো হলো। পরীক্ষায় প্রশ্নে যা বলা আছে, সেটিই মানবেন, আর নিজের ধারণাটি লিখে দেবেন।

• Single-cycle clock: সব ধাপের যোগফল + একবার overhead = ২০০ + ১০০ + ২০০ + ২০০ + ১০০ + ২০ = ৮২০ ps (≈ ১.২২ GHz).
• Pipelined clock: T_stage = max(২০০, ১০০, ২০০, ২০০, ১০০) + ২০ = ২২০ ps (≈ ৪.৫৫ GHz).
• Latency: single-cycle-এ ৮২০ ps; pipelined-এ ৫ × ২২০ = ১,১০০ ps — ২৮০ ps বেশি! কারণ ১০০ ps-এর ধাপগুলোকেও ২২০ ps দিতে হচ্ছে, আর overhead ১ বারের বদলে ৫ বার।

Single-cycle-এর throughput সব n-এ একই: ১ / ৮২০ ps ≈ ১.২২ instr/ns. সংখ্যাগুলো থেকে তিনটি শিক্ষা। এক, একটি instruction-এর জন্য pipeline ধীর (speedup ০.৭৪৫ < ১)। দুই, n বড় হলে speedup সীমায় পৌঁছায়, কিন্তু সেই সীমা ৫ নয়, ৩.৭৩ — কারণ সীমাটি আসলে T_single / T_stage, k নয়। তিন, ৫ থেকে ৩.৭৩-এ নামার দুই কারণ আলাদা করে মাপা যায়: সমান ধাপ হলে (৮০০ / ৫ = ১৬০ ps প্রতিটি) T_stage হতো ১৮০ ps আর সীমা ৮২০ / ১৮০ ≈ ৪.৫৬ — অসমতার দাম; overhead শূন্য হলে আর সমান ধাপে সীমা হতো ৮০০ / ১৬০ = ঠিক ৫.

যদি single-cycle-এ overhead না ধরা হয় (T = ৮০০ ps): speedup n = ১-এ ০.৭২৭, n = ৫-এ ২.০২০, n = ১০^৬-এ ৩.৬৩৬, আর সীমা ৮০০ / ২২০ ≈ ৩.৬৪.

কোন ধাপ ভাগ করলে লাভ?

T_stage ঠিক করে ধীরতম ধাপ। তাই স্বাভাবিক প্রশ্ন: ২০০ ps-এর একটি ধাপকে দুটি ১০০ ps-এর ধাপে ভাগ করলে? ফাঁদটি হলো, এখানে তিনটি ধাপ ২০০ ps (IF, EX, MEM). শুধু IF ভাগ করলে ধাপ ৬টি হয়, কিন্তু সবচেয়ে ধীর ধাপ এখনো ২০০ — T_stage ২২০-ই থাকে, আর latency বেড়ে ৬ × ২২০ = ১,৩২০ ps. লাভ শূন্য, ক্ষতি আছে। তিনটিকেই ভাগ করলে ৮টি ১০০ ps-এর ধাপ: T_stage = ১২০ ps, সীমা ৮২০ / ১২০ ≈ ৬.৮৩. আর ক্রমাগত ভাগ করলে? নিচের calculator দুটোই দেখায়।

// Pipeline timing: Tstage = max(stage delay) + register overhead.
// Single-cycle machine: Tc = sum(stage delays) + one register overhead.
const REG = 20;                                  // ps (tpcq + tsetup)
function analyse(name, stages, ns) {
  const k = stages.length;
  const T = Math.max(...stages) + REG;
  const single = stages.reduce((a, b) => a + b, 0) + REG;
  console.log(`${name}: k=${k}  Tstage=${T} ps  latency=${k * T} ps  single-cycle Tc=${single} ps`);
  for (const n of ns) {
    const tp = (k + n - 1) * T, ts = n * single;
    console.log("   n=" + String(n).padEnd(8) + "pipelined " + String(tp).padStart(10) +
      " ps  single " + String(ts).padStart(10) + " ps  speedup " + (ts / tp).toFixed(3) +
      "  throughput " + (n / tp * 1000).toFixed(3) + " instr/ns");
  }
}
analyse("5-stage RISC-V", [200, 100, 200, 200, 100], [1, 5, 100, 1e6]);
analyse("split IF only  ", [100, 100, 100, 200, 200, 100], [1e6]);
analyse("split IF,EX,MEM", [100, 100, 100, 100, 100, 100, 100, 100], [1e6]);

// Deeper and deeper: 800 ps of logic cut into k perfectly equal pieces.
console.log("\n  k   Tstage   limit speedup   speedup / k   (overhead share)");
for (const k of [1, 2, 4, 8, 16, 32, 64]) {
  const T = 800 / k + REG, sp = 820 / T;
  console.log(String(k).padStart(3) + String(T).padStart(9) + sp.toFixed(2).padStart(16) +
    (sp / k).toFixed(2).padStart(14) + ((REG / T) * 100).toFixed(0).padStart(12) + "%");
}

5-stage RISC-V: k=5  Tstage=220 ps  latency=1100 ps  single-cycle Tc=820 ps
   n=1       pipelined       1100 ps  single        820 ps  speedup 0.745  throughput 0.909 instr/ns
   n=5       pipelined       1980 ps  single       4100 ps  speedup 2.071  throughput 2.525 instr/ns
   n=100     pipelined      22880 ps  single      82000 ps  speedup 3.584  throughput 4.371 instr/ns
   n=1000000 pipelined  220000880 ps  single  820000000 ps  speedup 3.727  throughput 4.545 instr/ns
split IF only  : k=6  Tstage=220 ps  latency=1320 ps  single-cycle Tc=820 ps
   n=1000000 pipelined  220001100 ps  single  820000000 ps  speedup 3.727  throughput 4.545 instr/ns
split IF,EX,MEM: k=8  Tstage=120 ps  latency=960 ps  single-cycle Tc=820 ps
   n=1000000 pipelined  120000840 ps  single  820000000 ps  speedup 6.833  throughput 8.333 instr/ns

  k   Tstage   limit speedup   speedup / k   (overhead share)
  1      820            1.00          1.00           2%
  2      420            1.95          0.98           5%
  4      220            3.73          0.93           9%
  8      120            6.83          0.85          17%
 16       70           11.71          0.73          29%
 32       45           18.22          0.57          44%
 64     32.5           25.23          0.39          62%

৭ · কেন RISC ISA pipeline-বান্ধব — আর x86-এর চ্যালেঞ্জ

পর্ব ২৫-এ (ISA কী) RISC বনাম CISC-এর তর্ক দেখেছেন, আর পর্ব ২৭-এ (Instruction format আর encoding) RISC-V-এর বিট-বিন্যাস। এখন বোঝা যাবে কেন RISC-এর নকশাকারীরা এত সরলতার ওপর জোর দিয়েছিলেন — উদ্দেশ্য অনেকটাই pipeline. চারটি বৈশিষ্ট্য সরাসরি pipeline-কে সাহায্য করে:

এবার x86-এর কথা ভাবুন। Instruction ১ থেকে ১৫ বাইট পর্যন্ত (variable length), prefix থাকতে পারে, আর একটি instruction-এর দৈর্ঘ্য জানতে তার বেশ কয়েকটি বাইট পড়তে হয় — তাই পরের instruction কোথায় শুরু, তা জানার আগেই IF আটকে যায়। add [rbx+8], eax-এর মতো একটি instruction memory পড়ে, যোগ করে, আবার memory-তে লেখে — পাঁচ ধাপের এক ছন্দে বসে না। কিছু instruction (যেমন string copy) অনেক cycle নেয়।

আধুনিক x86 প্রসেসর এটি সমাধান করে একটি চতুর অনুবাদ দিয়ে: ফ্রন্ট-এন্ডে decoder প্রতিটি x86 instruction-কে এক বা একাধিক RISC-ধাঁচের ছোট micro-op-এ ভাঙে, আর ভেতরের pipeline সেই micro-op-গুলো চালায়। Intel-এর Pentium Pro (১৯৯৫) এই পদ্ধতির পরিচিত শুরু, আর আজকের Intel ও AMD core-এ এটিই ভিত্তি; ঘন ঘন চলা অংশের decode-এর খরচ বাঁচাতে decode করা micro-op একটি ছোট cache-এ রাখা হয়। মূল্য: বড় ও শক্তিখেকো decoder, আর বাড়তি কয়েকটি pipeline ধাপ। অর্থাৎ শেষ পর্যন্ত x86-ও ভেতরে RISC-ধাঁচের pipeline চালায় — ISA-র জটিলতা গিলে ফেলা হয় ফ্রন্ট-এন্ডে (ভাবনার প্রশ্ন ০২)।

৮ · Hazard — যেখানে pipeline হোঁচট খায় (পরিচয়)

এতক্ষণ ধরে নেওয়া হয়েছে প্রতিটি instruction তার নির্ধারিত cycle-এ নিশ্চিন্তে চলতে পারে। যে পরিস্থিতিতে তা পারে না, তাকে বলে pipeline hazard. তিন ধরনের hazard আছে — এই পর্বে শুধু সংজ্ঞা আর একটি করে ছোট উদাহরণ; সমাধানের বিস্তারিত পরের দুই পর্বে।

১. Structural hazard — একই যন্ত্র, দুজন দাবিদার

Structural hazard হয়, যখন একই cycle-এ দুটি instruction একই hardware চায়। ক্লাসিক উদাহরণ: memory যদি একটিই হয় (instruction আর data একসাথে, von Neumann ধাঁচে), তবে অংশ ৪-এর c4-এ lw MEM-এ data পড়তে চায় আর sw IF-এ instruction আনতে চায় — একটি memory port দুটি কাজ একসাথে পারে না, তাই একজনকে অপেক্ষা করতে হয়। লন্ড্রিতে একটিই যন্ত্র যদি washer আর dryer দুটোই হয়, একই অবস্থা। সমাধান: বাড়তি hardware — আলাদা instruction cache আর data cache (Harvard ধাঁচ, অন্তত L1-এ), আর register file-এ আলাদা read ও write port. RISC-V-এর পাঁচ ধাপের নকশা এমনভাবে বানানো যাতে এই সমাধানগুলো থাকলে structural hazard না থাকে।

২. Data hazard — মান এখনো তৈরি হয়নি

Data hazard হয়, যখন একটি instruction এমন register পড়তে চায়, যা আগের instruction এখনো লেখেনি। সবচেয়ে সাধারণ ধরন RAW (read after write):

add x1, x2, x3     # x1 is written in WB (cycle 5)
sub x4, x1, x5     # but sub reads x1 in ID (cycle 3) -> old value!

add ফল হিসাব করে EX-এ (cycle ৩), কিন্তু register file-এ লেখে WB-তে (cycle ৫)। sub cycle ৩-এ ID-তে x1 পড়ে ফেলে — পুরোনো মান। দুই সমাধান: অপেক্ষা (stall, bubble ঢুকিয়ে), অথবা forwarding — EX/MEM register থেকে ফলটি সরাসরি পরের instruction-এর ALU-তে পৌঁছে দেওয়া। Forwarding-এর তার, load-এর পরে কেন তবু এক cycle stall লাগে (load-use), আর compiler কীভাবে instruction-এর ক্রম বদলে সাহায্য করে — সব পর্ব ৩৬-এ (Pipeline hazard — structural, data hazard, forwarding আর stall).

৩. Control hazard — কোন পথে যাব, এখনো অজানা

Control hazard হয় branch-এ। beq x1, x2, L নেওয়া হবে কি না, তা জানা যায় EX-এ তুলনার পর — কিন্তু ততক্ষণে IF আরও দুটি instruction এনে ফেলেছে, PC + 4-এর পথ ধরে। Branch নেওয়া হলে সেই দুটি ভুল, ফেলে দিতে হয়:

beq  x1, x2, L     # outcome known in EX (cycle 3)
addi x3, x0, 1     # already fetched in cycle 2 -> flush if taken
addi x4, x0, 2     # already fetched in cycle 3 -> flush if taken
L: sub x5, x6, x7

প্রতিটি নেওয়া branch-এ এভাবে কয়েকটি cycle নষ্ট হলে খরচ বিশাল, কারণ সাধারণ প্রোগ্রামে branch প্রায় প্রতি পাঁচ-ছয়টি instruction-এ একটি। সমাধান: branch-এর ফল আগে (ID-তে) বের করা, আর branch prediction — ফলটি অনুমান করে সেই পথে এগিয়ে যাওয়া, ভুল হলে ফিরে আসা (branch penalty). পুরোনো MIPS-এ একটি ভিন্ন কৌশল ছিল, branch delay slot; RISC-V সেটি নেয়নি। বিস্তারিত পর্ব ৩৭-এ (Control hazard আর branch prediction).

৯ · Pipeline কত গভীর হবে — Pentium 4 থেকে আজকের core

অংশ ৬-এর শেষ টেবিল বলে, বেশি ধাপ মানে ছোট T_stage আর বেশি clock rate — যদিও ক্রমে কম লাভ। ধাপের সংখ্যাকে বলে pipeline depth, আর খুব বেশি ধাপের নকশাকে কখনো superpipelining বলা হয়। কিন্তু গভীরতার তিনটি দাম আছে:

• Register overhead জমে: প্রতিটি ধাপে ২০ ps-এর মতো স্থির খরচ, আর latency = k × T_stage বাড়তে থাকে।
• Hazard-এর খরচ বাড়ে: branch-এর ফল যত পরের ধাপে জানা যায়, ভুল অনুমানে তত বেশি ধাপের কাজ ফেলতে হয়; load-এর ফল আসতেও বেশি cycle লাগে।
• Power বাড়ে: বেশি register, বেশি clock load, আর উচ্চ frequency (পর্ব ০২-এর power wall).

ইতিহাসের সবচেয়ে বিখ্যাত পরীক্ষা। Intel-এর Pentium 4 (NetBurst, ২০০০) উচ্চ clock-এর জন্য প্রায় ২০ ধাপের pipeline নিয়ে আসে; ২০০৪ সালের Prescott সংস্করণে তা প্রায় ৩১ ধাপ বলে জানা যায়। Clock সত্যিই উঠেছিল — প্রায় ৩.৮ GHz পর্যন্ত — কিন্তু branch-এর ভুল অনুমানের খরচ আর তাপ এত বাড়ে যে পরের Core microarchitecture (২০০৬) প্রায় ১৪ ধাপের তুলনামূলক ছোট pipeline আর কম clock নিয়ে বেশি কাজ-প্রতি-cycle (IPC) দিয়ে তাকে ছাড়িয়ে যায় (পর্ব ০২-এ ইতিহাস আর প্রবণতা)। ধাপ-সংখ্যা গোনার পদ্ধতি নির্মাতা আর উৎসভেদে আলাদা, তাই এই সংখ্যাগুলো আনুমানিক।

সর্বোত্তম গভীরতা — একটি খেলনা মডেল

সহজ একটি মডেল বানানো যায়। মোট logic T, প্রতি ধাপে overhead d, ধাপ k. প্রতি instruction-এর মৌলিক সময় T/k + d. ধরুন h ভাগ instruction (যেমন ভুল অনুমান করা branch) pipeline খালি করে দেয় আর প্রায় k − ১ cycle নষ্ট করে। তাহলে

প্রতি instruction-এর সময় = (T/k + d) · (১ + h·(k − ১))

গুণ করে সাজালে: T(১ − h)/k + d·h·k + (ধ্রুবক)। প্রথম পদ k বাড়লে কমে (ছোট ধাপ), দ্বিতীয় পদ k বাড়লে বাড়ে (hazard আর overhead). k-এর সাপেক্ষে অন্তরকলন শূন্য ধরলে −T(১ − h)/k^২ + d·h = ০, অর্থাৎ

k_opt = √( T(১ − h) / (d·h) )

অর্থ পরিষ্কার: logic বেশি বা overhead কম হলে গভীর pipeline লাভজনক; hazard বেশি হলে অগভীর। ২০০২ সালের কাছাকাছি প্রকাশিত কয়েকটি গবেষণা (Intel আর IBM-এর গবেষকদের) আরও বিশদ মডেলে একই ধরনের যুক্তি দিয়েছিল, আর সাধারণভাবে বোঝা যায় যে সর্বোত্তম গভীরতা workload-নির্ভর। নিচের script এই খেলনা মডেলেই সব k চেষ্টা করে — এটি কোনো আসল CPU-র পরিমাপ নয়।

// TOY MODEL (not a real CPU): how deep should a pipeline be?
//   T = 800 ps of logic, d = 20 ps register overhead per stage.
//   A fraction h of instructions (e.g. mispredicted branches) flushes
//   the pipeline and wastes (k - 1) extra cycles.
//   time per instruction = (T/k + d) * (1 + h*(k - 1))
const T = 800, d = 20;
const tpi = (k, h) => (T / k + d) * (1 + h * (k - 1));
for (const h of [0, 0.02, 0.05, 0.1, 0.2]) {
  let best = 1;
  for (let k = 2; k <= 100; k++) if (tpi(k, h) < tpi(best, h)) best = k;
  const formula = h > 0 ? Math.sqrt(T * (1 - h) / (d * h)).toFixed(1) : "inf";
  console.log(`h=${h.toFixed(2)}  best k=${String(best).padStart(3)}` +
    `  formula sqrt(T(1-h)/(d*h))=${formula.padStart(5)}` +
    `  time/instr=${tpi(best, h).toFixed(1).padStart(6)} ps` +
    `  (k=5: ${tpi(5, h).toFixed(1)} ps)`);
}
console.log("\nh = 0.10, time per instruction (ps) for some depths:");
console.log([1, 5, 10, 19, 30, 50].map(k => `k=${k}: ${tpi(k, 0.1).toFixed(1)}`).join("   "));

h=0.00  best k=100  formula sqrt(T(1-h)/(d*h))=  inf  time/instr=  28.0 ps  (k=5: 180.0 ps)
h=0.02  best k= 44  formula sqrt(T(1-h)/(d*h))= 44.3  time/instr=  71.0 ps  (k=5: 194.4 ps)
h=0.05  best k= 28  formula sqrt(T(1-h)/(d*h))= 27.6  time/instr= 114.1 ps  (k=5: 216.0 ps)
h=0.10  best k= 19  formula sqrt(T(1-h)/(d*h))= 19.0  time/instr= 173.9 ps  (k=5: 252.0 ps)
h=0.20  best k= 13  formula sqrt(T(1-h)/(d*h))= 12.6  time/instr= 277.2 ps  (k=5: 324.0 ps)

h = 0.10, time per instruction (ps) for some depths:
k=1: 820.0   k=5: 252.0   k=10: 190.0   k=19: 173.9   k=30: 182.0   k=50: 212.4

বাস্তব pipeline — আনুমানিক চিত্র

শেখার জন্য পাঁচ ধাপ, কিন্তু বাস্তব core-এ ধাপ সাধারণত বেশি, কারণ cache বড় আর ধীর, decode জটিল, আর clock উঁচু। সংখ্যাগুলো প্রকাশিত বিবরণ থেকে আনুমানিক, আর নির্মাতাভেদে গোনার নিয়ম আলাদা:

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

AI টুল pipelining-এর ধারণা সুন্দর করে বোঝাতে পারে, কিন্তু numerical-এ চোখে পড়ার মতো ভুল করে। নিচের ভুলগুলো প্রায়ই দেখা যায়:

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

• T_stage-এ সবচেয়ে ধীর ধাপ নেওয়া হয়েছে, গড় নয়, আর overhead যোগ হয়েছে
• মোট cycle k + n − ১; n = ১ বসালে k আসে
• Single-cycle-এ overhead ধরা হয়েছে কি না, স্পষ্ট লেখা আছে, আর সেই অনুযায়ী speedup বদলেছে
• Speedup-এর সীমা T_single / T_stage, k নয় — অসম ধাপ হলে
• Pipeline diagram নিজে এঁকে বা এই পর্বের generator চালিয়ে cycle-সংখ্যা মিলিয়েছি
• MIPS আর RISC-V-এর নিয়ম (delay slot, register-এর নাম) মিশে যায়নি