Pipeline hazard — structural, data hazard, forwarding আর stall

১ · Hazard কী — assembly line যখন থমকে যায়

একটি গার্মেন্টস কারখানার assembly line কল্পনা করুন। পাঁচটি টেবিল: কাপড় কাটা, সেলাই, বোতাম লাগানো, ইস্ত্রি, প্যাকিং। প্রতি মিনিটে প্রতিটি শার্ট এক টেবিল সামনে এগোয়, তাই একসাথে পাঁচটি শার্টে কাজ চলে, আর প্রতি মিনিটে একটি শার্ট বের হয়। পর্ব ৩৫-এ ঠিক এই ছবিটিই দেখেছেন — RISC-V-এর পাঁচটি stage: IF (instruction আনা), ID (decode আর register পড়া), EX (ALU-তে হিসাব), MEM (data memory পড়া বা লেখা), WB (ফল register-এ লেখা)। আদর্শ অবস্থায় প্রতি cycle-এ একটি instruction শেষ হয়, অর্থাৎ ideal CPI = ১.

কিন্তু কারখানায় মাঝে মাঝে লাইন থামে। হয়তো ইস্ত্রির টেবিল আর সেলাইয়ের টেবিল একই মেশিন ভাগ করে ব্যবহার করে। হয়তো বোতাম লাগানোর লোক এমন একটি শার্ট পেলেন, যার কাপড় এখনো রং-এর ঘর থেকে ফেরেনি। এমন যেকোনো পরিস্থিতি, যেখানে পরের instruction তার নির্ধারিত cycle-এ চলতে পারে না, তাকে বলে pipeline hazard. তিন রকম hazard আছে:

Hazard সামলানোর তিনটি মূল উপায় এই পর্বে দেখবেন: (১) stall — নির্ভরশীল instruction-কে অপেক্ষা করানো; (২) forwarding — ফল register-এ পৌঁছানোর আগেই তাকে সরাসরি দরকারের জায়গায় পাঠানো; (৩) instruction scheduling — compiler-কে দিয়ে instruction-এর ক্রম এমনভাবে সাজানো, যাতে অপেক্ষা কম লাগে।

এই পর্বজুড়ে আমরা Patterson–Hennessy-র RISC-V ৫-stage pipeline-এর নিয়ম মেনে চলব। দুটি নিয়ম মনে রাখুন: register file cycle-এর প্রথম অর্ধেকে লেখে আর দ্বিতীয় অর্ধেকে পড়ে; আর forwarding আসে EX/MEM ও MEM/WB pipeline register থেকে EX stage-এর ALU-তে। Single-cycle datapath (পর্ব ৩২) আর control signal-এর টেবিল (পর্ব ৩৩) মনে থাকলে বুঝতে আরও সহজ হবে।

২ · Structural hazard — একটি সম্পদ, দুই দাবিদার

Structural hazard হয় যখন hardware-এ যথেষ্ট সম্পদ নেই। Pipeline-এর নকশাকারীর কাজ হলো সম্পদ এমনভাবে বসানো, যাতে প্রতিটি stage প্রতি cycle-এ নিজের অংশ নিজেই ব্যবহার করতে পারে। তিনটি ক্লাসিক উদাহরণ দেখি।

উদাহরণ ১: একটিমাত্র memory port

ধরুন প্রসেসরের কাছে একটিই memory, আর প্রতি cycle-এ সেখানে একটিই কাজ করা যায় (একটি port). এখন নিচের ক্রমে cycle ৪-এ কী হয় দেখুন:

cycle            1    2    3    4    5    6    7    8
lw  x5, 0(x10)   IF   ID   EX   MEM  WB
add x6, x7, x8        IF   ID   EX   MEM  WB
sub x9, x7, x8             IF   ID   EX   MEM  WB
or  x11, x7, x8                 IF   ID   EX   MEM  WB

Cycle ৪-এ lw data memory থেকে পড়তে চায়, আর একই cycle-এ or-কে memory থেকে আনতে (fetch) হবে। Port একটি হলে একজনকে অপেক্ষা করতেই হবে — সাধারণত fetch এক cycle পিছিয়ে যায়। প্রতিটি load আর store-এ এমন একটি stall হলে CPI অনেক বেড়ে যাবে।

সমাধান: instruction আর ডেটার জন্য আলাদা memory, বাস্তবে আলাদা L1 cache — split cache: একটি L1 instruction cache (I-cache), একটি L1 data cache (D-cache). এটি Harvard architecture-এর ধারণা, তবে শুধু সবচেয়ে কাছের স্তরে; L2 আর main memory সাধারণত দুইয়ের জন্য একটিই (unified). প্রায় সব আধুনিক x86-64, ARM আর RISC-V core-এ L1 এভাবে ভাগ করা থাকে। মেমরির পুরো hierarchy দেখবেন পর্ব ৪৪-এ।

উদাহরণ ২: register file — একই cycle-এ লেখা আর পড়া

উপরের ছবিতে cycle ৫-এ lw WB-তে register-এ লেখে, আর একই cycle-এ or ID-তে register পড়ে। এটিও একটি সম্পদ-দ্বন্দ্ব হতে পারত। দুটি কৌশলে এটি মেটানো হয়:

• আলাদা port: register file-এ দুটি read port (rs1, rs2 একসাথে পড়ার জন্য) আর একটি write port থাকে, তাই ID-এর দুটি পড়া আর WB-এর একটি লেখা একই cycle-এ চলতে পারে।
• অর্ধ-cycle কৌশল: লেখা হয় cycle-এর প্রথম অর্ধেকে, পড়া দ্বিতীয় অর্ধেকে। ফলে একই register যদি একই cycle-এ লেখা ও পড়া হয়, পাঠক নতুন মানটিই পায়। এই নিয়মের কারণেই পরের অংশে stall-এর হিসাব একটি cycle কম আসবে।

বোর্ডের উদাহরণে ভাবুন: ক্লাসের প্রথম অর্ধেকে শিক্ষক বোর্ডে নতুন সংখ্যা লেখেন, দ্বিতীয় অর্ধেকে ছাত্ররা বোর্ড থেকে টুকে নেন — একই ক্লাসে লেখা আর পড়া দুটোই হলো, আর ছাত্ররা নতুন সংখ্যাটিই পেলেন।

উদাহরণ ৩: pipeline-হীন ধীর unit

ধরুন একটি integer divider ২০ cycle নেয়, আর তার ভেতরে pipeline নেই — একটি ভাগ শেষ না হওয়া পর্যন্ত আরেকটি শুরু করা যায় না। তাহলে পরপর দুটি div এলে দ্বিতীয়টি কয়েক cycle অপেক্ষা করবে, যদিও দুটির মধ্যে কোনো ডেটা-সম্পর্ক নেই। এটিও structural hazard. সমাধান দুই রকম: divider-কে pipelined করা (বেশি transistor), অথবা মেনে নেওয়া — কারণ ভাগ খুব কম আসে, তাই গড় CPI-তে প্রভাব সামান্য। অংশ ৮-এর হিসাবে এর একটি সংখ্যাগত উদাহরণ পাবেন।

৩ · Data dependence — RAW, WAR, WAW আর কেন শুধু RAW বিপদ

দুটি instruction একই register ছুঁলে তাদের মধ্যে একটি data dependence তৈরি হয়। আগের instruction-কে বলি i, পরেরটিকে j (প্রোগ্রামের ক্রমে i আগে)। একই register-এ “পড়া” আর “লেখা”-র তিনটি সমন্বয়:

RAW হলো আসল ডেটা-প্রবাহ — মানটি সত্যিই i থেকে j-তে যায়। WAR আর WAW-কে বলা হয় “name dependence”: কোনো মান আদান-প্রদান হয় না, শুধু দুজনে একই register-এর নাম ব্যবহার করছে। আলাদা register নিলেই এরা মিলিয়ে যায় — এই ধারণাই পর্ব ৪০-এর register renaming-এর ভিত্তি।

Dependence হলো প্রোগ্রামের ধর্ম; hazard হলো pipeline-এর ধর্ম। একটি dependence তখনই hazard, যখন pipeline-এর কাঠামোর কারণে পড়া-লেখার ক্রম উল্টে যেতে পারে। এখন প্রমাণ করি কেন ক্লাসিক in-order ৫-stage pipeline-এ শুধু RAW hazard হয়:

1. সব instruction register পড়ে একই stage-এ (ID, stage ২) আর লেখে একই stage-এ (WB, stage ৫)। Instruction-গুলো প্রোগ্রামের ক্রমে, প্রতি cycle-এ সর্বোচ্চ একটি করে ঢোকে, আর কেউ কাউকে টপকে যায় না (in-order).
2. WAW অসম্ভব: i আগে ঢুকেছে, তাই i-এর WB আগে হবে, j-এর WB পরে। সবার WB একই stage-এ বলে লেখার ক্রম প্রোগ্রামের ক্রমের সমান — শেষ মান j-এরই থাকে।
3. WAR অসম্ভব: i পড়ে নিজের stage ২-এ, j লেখে নিজের stage ৫-এ। j অন্তত এক cycle পরে ঢুকেছে, তাই j-এর লেখা i-এর পড়ার অন্তত ৩ + ১ = ৪ cycle পরে। পুরোনো মান পড়ার আগে মুছে যাওয়ার কোনো সুযোগ নেই।
4. RAW সম্ভব: i লেখে stage ৫-এ, অথচ j পড়ে stage ২-এ। j যদি i-এর মাত্র ১ বা ২ cycle পরে ঢোকে, j-এর পড়া i-এর লেখার আগেই ঘটে যাবে — j পুরোনো মান পাবে। এখানেই বিপদ।

পরীক্ষার ক্লাসিক: সব dependence চিহ্নিত করা

প্রশ্নে সাধারণত instruction-এর একটি ক্রম দিয়ে বলা হয়: সব dependence চিহ্নিত করুন, কোনগুলো hazard, forwarding থাকলে আর না থাকলে। পদ্ধতিটি যান্ত্রিক — প্রতিটি জোড়া (i, j)-এর জন্য দেখুন i-এর destination register (rd) j-এর source (rs1/rs2)-এ আছে কি না (RAW), i-এর source j-এর rd কি না (WAR), দুজনের rd এক কি না (WAW). একটি সূক্ষ্ম বিষয়: মাঝখানে অন্য কেউ একই register-এ লিখলে দূরের জোড়াটি আর dependence নয় — j তখন মাঝের লেখকের মান পড়ে। আর x0-কে বাদ দিন — সে সবসময় ০, তার সাথে কোনো dependence হয় না।

নিচের analyser ঠিক এই কাজটি করে। দূরত্ব d = j − i (পরপর হলে d = ১)। Stall-এর সংখ্যা প্রতিটি জোড়ার জন্য আলাদাভাবে হিসাব করা (কেন ৩ − d, তা পরের অংশে প্রমাণ করব)। Run চাপুন, তারপর নিজের ক্রম বসিয়ে দেখুন:

// Dependence analyser: RAW / WAR / WAW between instruction pairs, 5-stage RISC-V pipeline
const prog = ["lw  x5, 0(x10)", "add x6, x5, x7", "sub x5, x8, x9",
              "and x7, x6, x5", "sw  x7, 4(x10)"];
function parse(s) {                                   // -> {op, rd, src[]}, x0 ignored
  const [op, ...a] = s.replace(/[(),]/g, " ").trim().split(/\s+/);
  const r = a.map(t => t.startsWith("x") ? +t.slice(1) : null);
  let rd = null, src = [];
  if (op === "sw") src = [r[2], r[0]];                // sw rs2, imm(rs1)
  else if (op === "lw") { rd = r[0]; src = [r[2]]; }  // lw rd, imm(rs1)
  else if (op === "addi") { rd = r[0]; src = [r[1]]; }
  else { rd = r[0]; src = [r[1], r[2]]; }             // R-type
  return { op, rd: rd || null, src: src.filter(x => x) };
}
const I = prog.map(parse);
const writes = (k, r) => I[k].rd === r;
const clean = (i, j, r) => { for (let k = i + 1; k < j; k++) if (writes(k, r)) return false; return true; };
console.log("pair    type  reg  dist  no forwarding       with forwarding");
for (let j = 1; j < I.length; j++) for (let i = 0; i < j; i++) {
  const d = j - i, out = [];
  const rd = I[i].rd;
  if (rd && I[j].src.includes(rd) && clean(i, j, rd)) {
    const nf = d <= 2 ? `HAZARD, ${3 - d} stall(s)` : "ok (reg file)";
    const fw = I[i].op === "lw" && d === 1 ? "HAZARD, 1 stall" : d <= 2 ? "ok (forwarded)" : "ok";
    out.push(["RAW", rd, nf, fw]);
  }
  for (const r of new Set(I[i].src)) if (writes(j, r) && clean(i, j, r)) out.push(["WAR", r, "no hazard", "no hazard"]);
  if (rd && writes(j, rd) && clean(i, j, rd)) out.push(["WAW", rd, "no hazard", "no hazard"]);
  for (const [t, r, nf, fw] of out)
    console.log(`I${i + 1}->I${j + 1}  ${t}   x${String(r).padEnd(3)}  ${d}    ${nf.padEnd(20)}${fw}`);
}

pair    type  reg  dist  no forwarding       with forwarding
I1->I2  RAW   x5    1    HAZARD, 2 stall(s)  HAZARD, 1 stall
I1->I3  WAW   x5    2    no hazard           no hazard
I2->I3  WAR   x5    1    no hazard           no hazard
I2->I4  RAW   x6    2    HAZARD, 1 stall(s)  ok (forwarded)
I2->I4  WAR   x7    2    no hazard           no hazard
I3->I4  RAW   x5    1    HAZARD, 2 stall(s)  ok (forwarded)
I4->I5  RAW   x7    1    HAZARD, 2 stall(s)  ok (forwarded)

৪ · Stall — hardware যখন bubble ঢোকায়

RAW hazard সামলানোর সবচেয়ে সরল উপায়: নির্ভরশীল instruction-কে ID stage-এ আটকে রাখা, যতক্ষণ না তার দরকারি মান register file-এ পৌঁছায়। আটকে থাকার প্রতিটি cycle হলো একটি stall. যে cycle-গুলোতে পেছনের instruction সামনে এগোয় না, সেখানে সামনের stage-গুলোতে একটি “ফাঁকা” instruction চলে যায় — একে বলে bubble. Bubble দেখতে একটি nop-এর মতো: সে কিছু লেখে না, memory ছোঁয় না, শুধু pipeline-এর একটি ঘর দখল করে এগিয়ে যায়।

গুরুত্বপূর্ণ: এই bubble hardware নিজে ঢোকায়, প্রোগ্রামে কোনো nop লেখা থাকে না। যে hardware dependence চিনে stall করায়, তাকে বলে hazard detection unit; এই আটকে রাখার ব্যবস্থাকে interlock-ও বলা হয়। প্রথম দিকের কিছু প্রসেসরে এই দায়িত্ব দেওয়া হয়েছিল compiler-কে — সে নিজেই nop বসাত (ভাবনার প্রশ্ন ১ দেখুন)।

কয়টি stall? — প্রমাণ

ধরুন producer instruction i cycle ১-এ fetch হয়। তাহলে i-এর WB cycle ৫-এ। Consumer j = i + d, stall না থাকলে fetch হয় cycle ১ + d-তে, আর register পড়ে (ID) cycle ২ + d-তে। s টি stall দিলে j-এর ID হয় cycle ২ + d + s-এ।

1. Register file প্রথম অর্ধেকে লেখে, দ্বিতীয় অর্ধেকে পড়ে — তাই j-এর পড়া i-এর লেখার cycle-এ হলেও চলবে: শর্ত 2 + d + s ≥ 5.
2. অর্থাৎ s ≥ 3 − d, আর s ঋণাত্মক হতে পারে না: s = max(0, 3 − d).
3. d = ১ (ঠিক পরের instruction) → ২ stall; d = ২ → ১ stall; d ≥ ৩ → কোনো stall নেই।
4. অর্ধ-cycle কৌশল না থাকলে পড়া লেখার পরের cycle-এ হতে হতো: 2 + d + s ≥ 6, তাই s = max(০, ৪ − d) — পরপর instruction-এ ৩টি stall.

শেষ সূত্রটি পর্ব ৩৫-এর: প্রথম instruction শেষ হতে ৫ cycle, তারপর প্রতিটি নতুন instruction এক cycle করে যোগ করে, আর প্রতিটি stall আরও একটি। উদাহরণ: add x1, x2, x3 আর ঠিক পরেই sub x4, x1, x5 — forwarding ছাড়া ২ + ৪ + ২ = ৮ cycle; forwarding থাকলে ৬ cycle.

৫ · Forwarding (bypassing) — ফল register-এ পৌঁছানোর আগেই পাঠিয়ে দেওয়া

একটু ভাবুন: add x1, x2, x3-এর ফল কখন তৈরি হয়? EX stage-এর শেষে, cycle ৩-এ। অথচ register file-এ লেখা হয় cycle ৫-এ। আর sub x4, x1, x5-এর মানটি আসলে লাগে কখন? তার নিজের EX-এর শুরুতে, cycle ৪-এ। অর্থাৎ ফলটি দরকারের আগেই তৈরি — শুধু ভুল জায়গায় বসে আছে (EX/MEM pipeline register-এ)। তাহলে সেখান থেকে একটি তার টেনে সরাসরি ALU-র ইনপুটে দিলেই হয়! এটাই forwarding, অন্য নাম bypassing.

RISC-V-এর ৫-stage pipeline-এ দুটি forwarding পথ যথেষ্ট:

• EX/MEM → EX: ঠিক আগের instruction-এর ALU ফল (d = ১)।
• MEM/WB → EX: দুই আগের instruction-এর ফল, অথবা ঠিক আগের load-এর memory থেকে পড়া মান (d = ২, বা load-এর ক্ষেত্রে stall-এর পরে)।
• d = ৩ হলে কোনো forwarding লাগে না — অর্ধ-cycle কৌশলে register file থেকেই নতুন মান পাওয়া যায়।

নিচের stepper-এ তিনটি instruction দেখুন। শুরুর মান: x1 = ৯৯ (পুরোনো), x2 = ১০, x3 = ২০, x5 = ৭, x7 = ১২. প্রতিটি সারি একটি stage, প্রতিটি ধাপ একটি cycle:

Forwarding unit-এর শর্ত — ধাপে ধাপে গড়ে তোলা

EX stage-এ ALU-র প্রতিটি ইনপুটের আগে একটি তিন-ইনপুটের multiplexer বসানো হয়। যে hardware ঠিক করে mux কোন ইনপুট নেবে, তাকে বলে forwarding unit. Encoding (Patterson–Hennessy-র RISC-V বইয়ের রীতি):

এখন শর্তটি নিজে গড়ে তুলি। “EX/MEM থেকে forward করব” কখন সঠিক?

1. আগের instruction আসলেই register-এ লিখবে: EX/MEM.RegWrite = 1. sw বা branch-এর rd ঘরে কিছু bit থাকে, কিন্তু তারা register লেখে না — এই শর্ত ছাড়া তাদের “ফল” ভুল করে forward হতো।
2. Destination x0 নয়: EX/MEM.rd ≠ 0. RISC-V-এ addi x0, x1, 5 বৈধ instruction (ফল ফেলে দেওয়া হয়) — x0 সবসময় ০ থাকবে। এই শর্ত না থাকলে পরের add x2, x0, x0 forward করা মান পেয়ে x2 = ০-এর বদলে (x1 + ৫)-এর দ্বিগুণ পেত।
3. Register মিলে যায়: EX/MEM.rd = ID/EX.rs1.

// EX hazard (Patterson–Hennessy, RISC-V সংস্করণের রীতি)
if (EX/MEM.RegWrite and (EX/MEM.RegisterRd ≠ 0)
    and (EX/MEM.RegisterRd = ID/EX.RegisterRs1))  ForwardA = 10
if (EX/MEM.RegWrite and (EX/MEM.RegisterRd ≠ 0)
    and (EX/MEM.RegisterRd = ID/EX.RegisterRs2))  ForwardB = 10

// MEM hazard — শুধু তখনই, যখন EX hazard নেই
if (MEM/WB.RegWrite and (MEM/WB.RegisterRd ≠ 0)
    and not (EX/MEM.RegWrite and (EX/MEM.RegisterRd ≠ 0)
             and (EX/MEM.RegisterRd = ID/EX.RegisterRs1))
    and (MEM/WB.RegisterRd = ID/EX.RegisterRs1))  ForwardA = 01
// ForwardB-এর জন্য একই, Rs1-এর জায়গায় Rs2

অগ্রাধিকারের নিয়ম — double data hazard

MEM hazard-এর শর্তে ওই লম্বা “not (…)” অংশটি কেন? ধরুন একই register পরপর কয়েকবার বদলানো হচ্ছে — যেমন একটি loop-এ যোগফল জমানো: add x1, x1, x2, add x1, x1, x3, add x1, x1, x4. তৃতীয় instruction যখন EX-এ, তখন EX/MEM আর MEM/WB — দুটিতেই rd = x1! কোনটি নেব? প্রোগ্রামের অর্থ অনুযায়ী সবচেয়ে সাম্প্রতিক মানটি, অর্থাৎ EX/MEM-এরটি। নিচের stepper-এ forwarding unit-এর সিদ্ধান্তটি ধাপে ধাপে দেখুন (শুরুতে x1 = ৫, x2 = ১, x3 = ২, x4 = ৩):

Hardware-এ এই অগ্রাধিকার আসলে একটি সরল if–else শৃঙ্খল। নিচে SystemVerilog-এ একটি forwarding unit (উদাহরণ, synthesizable combinational লজিক — Verilog-এর পরিচয় আছে পর্ব ১৪-এ):

// উদাহরণ — forwarding unit (SystemVerilog, combinational)
module forwarding_unit (
    input  logic [4:0] id_ex_rs1, id_ex_rs2, ex_mem_rd, mem_wb_rd,
    input  logic       ex_mem_regwrite, mem_wb_regwrite,
    output logic [1:0] forward_a, forward_b
);
    always_comb begin
        forward_a = 2'b00;                                   // register file
        if (ex_mem_regwrite && ex_mem_rd != 5'd0 && ex_mem_rd == id_ex_rs1)
            forward_a = 2'b10;                               // EX/MEM wins
        else if (mem_wb_regwrite && mem_wb_rd != 5'd0 && mem_wb_rd == id_ex_rs1)
            forward_a = 2'b01;                               // MEM/WB

        forward_b = 2'b00;
        if (ex_mem_regwrite && ex_mem_rd != 5'd0 && ex_mem_rd == id_ex_rs2)
            forward_b = 2'b10;
        else if (mem_wb_regwrite && mem_wb_rd != 5'd0 && mem_wb_rd == id_ex_rs2)
            forward_b = 2'b01;
    end
endmodule

else if-ই সেই “not already forwarded from EX/MEM” শর্ত — প্রথম শর্ত সত্য হলে দ্বিতীয়টি দেখাই হয় না। প্রতিটি ইনপুটে মাত্র দুটি ৫-bit comparator আর কয়েকটি gate — খুব ছোট hardware, কিন্তু CPI-তে বিশাল প্রভাব।

৬ · Load-use hazard — forwarding-ও যেখানে হার মানে

এবার producer যদি একটি load হয়? lw x5, 0(x10)-এর মান memory থেকে আসে MEM stage-এর শেষে। ঠিক পরের add x6, x5, x7-এর মান লাগে তার EX-এর শুরুতে — যা একই cycle! সময়ে পেছনে তো কিছু পাঠানো যায় না। তাই forwarding থাকলেও একটি stall লাগবেই। একে বলে load-use hazard.

প্রমাণ আগের মতো: lw cycle ১-এ fetch হলে তার মান তৈরি হয় cycle ৪-এর শেষে (MEM). Consumer j = i + d-এর EX (s stall সহ) cycle ৩ + d + s-এ, আর তাকে অন্তত cycle ৫ হতে হবে (MEM/WB → EX forwarding): 3 + d + s ≥ 5, তাই s = max(0, 2 − d) — d = ১-এ ১টি stall, d ≥ ২-এ শূন্য। একই হিসাবে ALU producer-এর জন্য: মান তৈরি cycle ৩-এর শেষে, শর্ত 3 + d + s ≥ 4, তাই s = max(০, ১ − d) = ০ সবসময়।

Hazard detection unit — কখন, আর কীভাবে bubble ঢোকায়

Load-use চেনার সবচেয়ে ভালো সময় হলো consumer যখন ID-তে আর load যখন EX-এ। Patterson–Hennessy-র শর্ত:

if (ID/EX.MemRead and
    ((ID/EX.RegisterRd = IF/ID.RegisterRs1) or
     (ID/EX.RegisterRd = IF/ID.RegisterRs2)))
    stall the pipeline (১ cycle)

ID/EX.MemRead একমাত্র load-এর জন্যই ১ — তাই এটিই বলে “EX-এ যে আছে সে একটি load”. বাকি অংশ দেখে, ID-তে থাকা instruction তার rd পড়বে কি না। Stall হলে তিনটি কাজ একসাথে হয়:

1. PC আটকে রাখা (PCWrite = ০): একই instruction আবার fetch হয়, নতুন কিছু ঢোকে না।
2. IF/ID register আটকে রাখা (IF/IDWrite = ০): ID-তে থাকা consumer পরের cycle-এ আবার decode হয়।
3. ID/EX-এ সব control signal ০ (একটি mux দিয়ে): EX-এ যা ঢোকে তা RegWrite = ০, MemRead = ০, MemWrite = ০ — কিছুই বদলায় না। এটিই bubble.

পাঠ্যবইয়ের এই সরল শর্ত দেখে না consumer আসলেই rs2 ব্যবহার করে কি না (যেমন addi-এর rs2 ঘরে immediate-এর bit থাকে), তাই কখনো কখনো অকারণ stall হয় — নিরাপদ দিকে ভুল। বাস্তব নকশা decoder থেকে জেনে নেয় কোন source আসলে ব্যবহৃত হচ্ছে; এই পর্বের simulator-ও তাই করে। নিচের stepper-এ পুরো ঘটনাটি দেখুন (Mem[x10] = ৪০, x7 = ২, x9 = ০):

পুরো simulator: forwarding ছাড়া বনাম forwarding সহ

নিচের simulator একটি পাঁচ-instruction প্রোগ্রামের cycle-by-cycle diagram আঁকে। নিয়মগুলো ঠিক উপরের প্রমাণের: forwarding ছাড়া consumer-কে producer-এর WB-এর cycle পর্যন্ত ID-তে অপেক্ষা করতে হয়; forwarding থাকলে ALU-র ফলের জন্য অপেক্ষা নেই, load-এর ঠিক পরে ১ cycle. ** মানে instruction আগের stage-এই আটকে আছে (stall), আর ডান পাশে লেখা থাকে EX-এর সময় প্রতিটি operand কোথা থেকে এল:

// 5-stage pipeline timing with hazard detection; forwarding EX/MEM->EX and MEM/WB->EX
// each entry: [text, rd (0 = none), source registers, isLoad]
const prog = [["lw  x5, 0(x10)", 5, [10], 1], ["add x6, x5, x7", 6, [5, 7]],
  ["sub x8, x6, x5", 8, [6, 5]], ["and x9, x8, x6", 9, [8, 6]], ["sw  x9, 8(x10)", 0, [10, 9]]];
const writer = (r, i) => prog.map(q => q[1]).lastIndexOf(r, i - 1);  // nearest earlier writer
function simulate(fwd) {
  const D = [], notes = [];                // D[i] = last cycle instruction i spends in ID
  prog.forEach(([, , src], i) => {
    let d = i === 0 ? 2 : D[i - 1] + 1;    // earliest: one cycle after the previous one
    for (const r of src) {
      const p = writer(r, i); if (p < 0 || r === 0) continue;
      d = Math.max(d, D[p] + (!fwd ? 3 : prog[p][3] ? 2 : 1));    // WB / load-use / ALU
    }
    const why = src.map(r => {             // where the operand comes from when i is in EX
      const p = writer(r, i), gap = p < 0 ? 9 : d - D[p];
      return gap === 1 ? `x${r} EX/MEM->EX` : gap === 2 ? `x${r} MEM/WB->EX` :
             gap === 3 ? `x${r} regfile(WB same cycle)` : "";
    }).filter(s => s);
    D.push(d); notes.push(why.join(", "));
  });
  const total = D[D.length - 1] + 3, cell = s => s.padEnd(4);
  console.log(`${fwd ? "WITH" : "NO"} forwarding: ${total} cycles, ` +
              `${total - prog.length - 4} stall cycles\n${"cycle".padEnd(16)}` +
              [...Array(total)].map((_, c) => cell(String(c + 1))).join(""));
  prog.forEach(([txt], i) => {
    const row = Array(total).fill(cell("")), first = i === 0 ? 2 : D[i - 1] + 1;
    const F = i === 0 ? 1 : (i === 1 ? 2 : D[i - 2] + 1);         // fetched when i-1 enters ID
    for (let c = F; c <= D[i] + 3; c++) row[c - 1] = cell("**");   // ** = held (stall)
    row[F - 1] = cell("IF"); row[first - 1] = cell("ID");
    ["EX", "MEM", "WB"].forEach((s, k) => row[D[i] + k] = cell(s));
    console.log(txt.padEnd(16) + row.join("") + (notes[i] ? " " + notes[i] : ""));
  });
}
simulate(false); console.log(); simulate(true);

NO forwarding: 17 cycles, 8 stall cycles
cycle           1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17
lw  x5, 0(x10)  IF  ID  EX  MEM WB
add x6, x5, x7      IF  ID  **  **  EX  MEM WB                                       x5 regfile(WB same cycle)
sub x8, x6, x5          IF  **  **  ID  **  **  EX  MEM WB                           x6 regfile(WB same cycle)
and x9, x8, x6                      IF  **  **  ID  **  **  EX  MEM WB               x8 regfile(WB same cycle)
sw  x9, 8(x10)                                  IF  **  **  ID  **  **  EX  MEM WB   x9 regfile(WB same cycle)

WITH forwarding: 10 cycles, 1 stall cycles
cycle           1   2   3   4   5   6   7   8   9   10
lw  x5, 0(x10)  IF  ID  EX  MEM WB
add x6, x5, x7      IF  ID  **  EX  MEM WB               x5 MEM/WB->EX
sub x8, x6, x5          IF  **  ID  EX  MEM WB           x6 EX/MEM->EX, x5 regfile(WB same cycle)
and x9, x8, x6                  IF  ID  EX  MEM WB       x8 EX/MEM->EX, x6 MEM/WB->EX
sw  x9, 8(x10)                      IF  ID  EX  MEM WB   x9 EX/MEM->EX

৭ · Compiler scheduling — ক্রম বদলে stall এড়ানো

Load-use stall hardware দিয়ে সরানো যায় না, কিন্তু software দিয়ে লুকানো যায়। কৌশল সহজ: load আর তার ব্যবহারকারীর মাঝে এমন একটি instruction বসান, যার ওই load-এর সাথে কোনো সম্পর্ক নেই। একে বলে instruction scheduling (বা code scheduling); compiler এটি স্বয়ংক্রিয়ভাবে করে, যদি নতুন ক্রমে প্রোগ্রামের অর্থ না বদলায়।

Patterson–Hennessy-র বইয়ে একটি বিখ্যাত উদাহরণ আছে (a = b + e; c = b + f;), যেখানে ক্রম বদলে ১৩ cycle থেকে ১১ cycle হয়। আমরা একটু বড় নিজস্ব উদাহরণ নিই:

d = a + b;
e = a - c;
f = d + e;      // a, b, c, d, e, f মেমরিতে, ঠিকানা x10 + 0, 4, 8, 12, 16, 20

সরল অনুবাদে (প্রতিটি statement নিজের ক্রমে) ৯টি instruction, যেখানে দুটি load-use জোড়া আছে: lw x6 → add x7, আর lw x28 → sub x29. তাই forwarding সহ ৯ + ৪ + ২ = ১৫ cycle. সমাধান: তৃতীয় load (lw x28, যা c আনে) উপরে তুলে আনা — সে কারও ওপর নির্ভর করে না, আর যে দুটি instruction-কে সে টপকে যাবে (add x7, sw x7), তারা কেউ x28 পড়ে বা লেখে না।

কিন্তু “উপরে তোলা” কখন বৈধ? Compiler একটি dependence graph বানায় — প্রতিটি RAW, WAR, WAW, আর মেমরির ক্ষেত্রে একই ঠিকানার store-load, load-store বা store-store জোড়া — তারপর শুধু সেই ক্রমগুলো বদলায় যাদের মধ্যে কোনো তীর নেই। এই উদাহরণে সব ঠিকানা একই base register (x10) থেকে ভিন্ন offset-এ, আর x10 কোথাও বদলায় না, তাই lw x28, 8(x10) নিশ্চিতভাবে sw x7, 12(x10)-এর সাথে ভিন্ন ঠিকানা ছোঁয়। (ভিন্ন base register হলে compiler সাধারণত ধরে নেয় একই ঠিকানা হতে পারে — aliasing — আর ক্রম বদলায় না।)

নিচের প্রোগ্রাম একটি সরল greedy list scheduling চালায়: প্রতিবার “প্রস্তুত” (সব পূর্বসূরি বসে গেছে এমন) instruction-গুলোর মধ্যে প্রথমটি নেয়, যেটি ঠিক আগের load-এর ফল ব্যবহার করে না; এমন কেউ না থাকলে প্রথম প্রস্তুতটিকেই নেয়:

// Greedy list scheduling to remove load-use stalls. C: d = a + b; e = a - c; f = d + e;
// a,b,c,d,e,f live at 0,4,8,12,16,20(x10). Entry: [text, op, rd, [sources], memory offset]
const P = [["lw  x5, 0(x10)", "lw", 5, [10], 0], ["lw  x6, 4(x10)", "lw", 6, [10], 4],
  ["add x7, x5, x6", "add", 7, [5, 6]], ["sw  x7, 12(x10)", "sw", 0, [10, 7], 12],
  ["lw  x28, 8(x10)", "lw", 28, [10], 8], ["sub x29, x5, x28", "sub", 29, [5, 28]],
  ["sw  x29, 16(x10)", "sw", 0, [10, 29], 16], ["add x30, x7, x29", "add", 30, [7, 29]],
  ["sw  x30, 20(x10)", "sw", 0, [10, 30], 20]];
const isMem = q => q[1] === "lw" || q[1] === "sw";
function mustStayAfter(j, i) {           // must P[j] stay after P[i] (i < j)?
  const a = P[i], b = P[j];
  if (a[2] && b[3].includes(a[2])) return true;                 // RAW
  if (b[2] && a[3].includes(b[2])) return true;                 // WAR
  if (a[2] && a[2] === b[2]) return true;                       // WAW
  return isMem(a) && isMem(b) && (a[1] === "sw" || b[1] === "sw") && a[4] === b[4]; // same address
}
const loadUse = (prev, q) => prev && prev[1] === "lw" && q[3].includes(prev[2]);
const cycles = seq => seq.length + 4 + seq.filter((q, k) => loadUse(seq[k - 1], q)).length;
function schedule() {
  const done = new Set(), out = [];
  while (out.length < P.length) {
    const ready = P.map((_, j) => j).filter(j => !done.has(j) &&
      P.every((_, i) => i >= j || done.has(i) || !mustStayAfter(j, i)));
    const pick = ready.find(j => !loadUse(out[out.length - 1], P[j])) ?? ready[0];
    done.add(pick); out.push(P[pick]);
  }
  return out;
}
const S = schedule();
for (const [name, seq] of [["original", P], ["scheduled", S]]) {
  console.log(`${name}: ${cycles(seq)} cycles (with forwarding)`);
  seq.forEach((q, k) => console.log("   " + q[0].padEnd(18) + (loadUse(seq[k - 1], q) ? "<- 1 stall (load-use)" : "")));
}

original: 15 cycles (with forwarding)
   lw  x5, 0(x10)
   lw  x6, 4(x10)
   add x7, x5, x6    <- 1 stall (load-use)
   sw  x7, 12(x10)
   lw  x28, 8(x10)
   sub x29, x5, x28  <- 1 stall (load-use)
   sw  x29, 16(x10)
   add x30, x7, x29
   sw  x30, 20(x10)
scheduled: 13 cycles (with forwarding)
   lw  x5, 0(x10)
   lw  x6, 4(x10)
   lw  x28, 8(x10)
   add x7, x5, x6
   sw  x7, 12(x10)
   sub x29, x5, x28
   sw  x29, 16(x10)
   add x30, x7, x29
   sw  x30, 20(x10)

বাস্তবে compiler-এর scheduler অনেক বেশি তথ্য ব্যবহার করে: প্রতিটি instruction-এর আসল latency (একটি গুণ হয়তো ৩ cycle, L1 cache থেকে load হয়তো ৪–৫ cycle), কতগুলো functional unit আছে, আর register কম পড়ে যাচ্ছে কি না — কারণ load আগে তুলে আনলে একসাথে বেশি মান “জীবিত” থাকে, ফলে বেশি register লাগে (register allocation-এর সাথে টানাটানি)। Loop unrolling scheduling-কে আরও বেশি স্বাধীন instruction দেয়। GCC-তে -O2 থেকে scheduling চালু থাকে, আর -mtune= দিয়ে নির্দিষ্ট CPU-র latency টেবিল বেছে নেওয়া যায়।

৮ · Stall সহ CPI — হিসাব আর পরীক্ষার numerical

বড় প্রোগ্রামে প্রতিটি cycle গোনা সম্ভব নয়; তখন আমরা গড় হিসাব করি। ৫-stage pipeline-এ প্রতিটি instruction আদর্শভাবে ১ cycle নেয়, আর প্রতিটি stall একটি বাড়তি cycle যোগ করে। তাই পর্ব ০৩-এর CPI-র সংজ্ঞা থেকে সরাসরি:

কেন ঠিক? মোট cycle = n + ৪ + মোট stall. n বড় হলে ৪-এর ভাগ (৪ / n) শূন্যের দিকে যায়, তাই CPI = মোট cycle / n ≈ ১ + (মোট stall / n). আর মোট stall / n = Σ (ঘটনার সংখ্যা / n) × প্রতিবারের stall = Σ f × s. শর্ত একটিই: ঘটনাগুলোর stall যেন একে অপরের সাথে না মেশে (overlap না করে) — সাধারণ পরীক্ষার প্রশ্নে এটি ধরে নেওয়া হয়।

ক্লাসিক উদাহরণ: forwarding আছে; ২৫% instruction load; তাদের ৪০%-এর ঠিক পরের instruction ফলটি ব্যবহার করে। Load-use ঘটনার হার = ০.২৫ × ০.৪০ = ০.১০ (প্রতি ১০টি instruction-এ একটি), তাই CPI = ১ + ০.১০ × ১ = ১.১০. ভগ্নাংশের ভগ্নাংশ গুণ করতে ভুলবেন না — “৪০% load-use” মানে সব instruction-এর ৪০% নয়, load-গুলোর ৪০%.

এখন forwarding-এর দাম। Forwarding mux ALU-র সামনে বসে, তাই EX stage-এর পথ একটু লম্বা হয় — clock cycle সামান্য বাড়তে পারে (critical path, পর্ব ১৮)। তাই সঠিক তুলনা CPI দিয়ে নয়, CPI × clock cycle time দিয়ে। নিচের calculator চারটি পরিস্থিতি হিসাব করে:

// CPI with stalls: CPI = ideal CPI (1) + sum over causes of (frequency x stall cycles)
function cpi(name, causes, clockPs) {
  let c = 1;
  const parts = causes.map(([what, freq, stalls]) => {
    c += freq * stalls;
    return `${freq.toFixed(3)} x ${stalls} [${what}]`;
  });
  const tPerInstr = c * clockPs;                       // average time per instruction
  console.log(`${name}\n   CPI = 1 + ${parts.join(" + ")} = ${c.toFixed(3)}` +
              `  -> ${clockPs} ps clock, ${tPerInstr.toFixed(1)} ps per instruction`);
  return tPerInstr;
}
// A) forwarding: 25% loads, 40% of them followed immediately by a user of the result
const A = cpi("A) forwarding, load-use only", [["load-use", 0.25 * 0.40, 1]], 250);
// B) same program after compiler scheduling removes 3/4 of the load-use pairs
const B = cpi("B) forwarding + scheduling", [["load-use", 0.25 * 0.40 * 0.25, 1]], 250);
// C) no forwarding: 30% of instructions have a user at distance 1 (2 stalls),
//    another 10% only at distance 2 (1 stall); no forwarding muxes -> 240 ps clock
const C = cpi("C) no forwarding", [["dist-1", 0.30, 2], ["dist-2", 0.10, 1]], 240);
// D) A plus a non-pipelined divider: 0.5% of instructions are a divide that
//    finds the divider still busy and waits 12 cycles on average
const D = cpi("D) A + busy divider", [["load-use", 0.10, 1], ["div-busy", 0.005, 12]], 250);
console.log(`\nA vs C: forwarding is ${(C / A).toFixed(3)} times faster (even with a slower clock)`);
console.log(`B vs A: scheduling gives ${(A / B).toFixed(3)} times;  D vs A: ${(D / A).toFixed(3)} times slower`);

A) forwarding, load-use only
   CPI = 1 + 0.100 x 1 [load-use] = 1.100  -> 250 ps clock, 275.0 ps per instruction
B) forwarding + scheduling
   CPI = 1 + 0.025 x 1 [load-use] = 1.025  -> 250 ps clock, 256.3 ps per instruction
C) no forwarding
   CPI = 1 + 0.300 x 2 [dist-1] + 0.100 x 1 [dist-2] = 1.700  -> 240 ps clock, 408.0 ps per instruction
D) A + busy divider
   CPI = 1 + 0.100 x 1 [load-use] + 0.005 x 12 [div-busy] = 1.160  -> 250 ps clock, 290.0 ps per instruction

A vs C: forwarding is 1.484 times faster (even with a slower clock)
B vs A: scheduling gives 1.073 times;  D vs A: 1.055 times slower

পরীক্ষার numerical: pipeline বনাম single-cycle

একটি single-cycle প্রসেসরের clock ৮০০ ps (পর্ব ৩২-এর ধাঁচে, সবচেয়ে ধীর instruction-এর পথ ধরে)। একই ISA-র ৫-stage pipelined সংস্করণে clock ২৫০ ps (সবচেয়ে ধীর stage আর pipeline register-এর overhead মিলিয়ে), forwarding আছে, আর load-use পরিস্থিতি উপরের A-র মতো। Speedup কত?

1. Single-cycle: CPI = ১, প্রতি instruction-এ ৮০০ ps.
2. Pipeline: CPI = ১.১, প্রতি instruction-এ ১.১ × ২৫০ = ২৭৫ ps.
3. Speedup = ৮০০ / ২৭৫ ≈ ২.৯১ — আদর্শ ৫ নয়, কারণ (ক) stage-গুলো সমান ভাগ হয়নি (৮০০ / ৫ = ১৬০ ps-এর বদলে ২৫০ ps), আর (খ) stall-এর কারণে CPI ১-এর বেশি।

এই দুটি কারণ মনে রাখুন — pipeline-এর speedup নিয়ে যেকোনো প্রশ্নে উত্তর এখান থেকেই আসে।

৯ · লম্বা pipeline, multi-cycle unit আর বাস্তব core

আমাদের ৫-stage pipeline-এ সব instruction একই দৈর্ঘ্যের। বাস্তবে floating-point যোগ, গুণ বা ভাগ এক cycle-এ শেষ হয় না। Hennessy–Patterson-এর একটি পাঠ্যবই-উদাহরণে FP যোগের unit ৪ stage-এর, গুণের unit ৭ stage-এর, আর ভাগের unit pipeline-হীন, প্রায় দুই ডজন cycle নেয়। এমন multi-cycle functional unit এলে তিনটি নতুন সমস্যা দেখা দেয়:

• RAW stall লম্বা হয়: একটি গুণের ফল ৭ cycle পরে আসে, তাই তার ব্যবহারকারী forwarding সহও কয়েক cycle অপেক্ষা করে। Compiler scheduling তখন আরও জরুরি।
• WAW hazard ফিরে আসে: fmul.d f0, f2, f4-এর পরে fadd.d f0, f6, f8 এলে যোগটি আগে শেষ হতে পারে — তারপর ধীর গুণটি f0-এ লিখে ঠিক মানটি মুছে দেবে। Hardware-কে তখন দ্বিতীয় লেখাটি আটকাতে বা প্রথমটি বাতিল করতে হয়।
• Register write port-এর structural hazard আর ক্রমভাঙা শেষ: ভিন্ন দৈর্ঘ্যের instruction একই cycle-এ WB-তে পৌঁছাতে পারে, আর পরের instruction আগে শেষ হতে পারে — তখন কোনো exception হলে “কোন পর্যন্ত কাজ হয়েছে” বলা কঠিন (precise exception, পর্ব ৩৮)।

লম্বা (গভীর) pipeline-এ — যেখানে memory পড়া কয়েকটি stage নেয় — load-use-এর দূরত্বও বাড়ে। আধুনিক অনেক x86-64 আর ARM core-এ L1 data cache থেকে load-to-use latency প্রায় ৪–৫ cycle বলে প্রকাশিত তথ্যে দেখা যায়, তাই ঠিক পরের instruction-কে সেই ক’টি cycle অপেক্ষা করতে হয় (যদি না অন্য স্বাধীন কাজ পাওয়া যায়)।

ইতিহাস: scoreboard থেকে renaming

১৯৬৪ সালে Control Data Corporation-এর CDC 6600 (নকশায় Seymour Cray আর James Thornton) কয়েকটি স্বাধীন functional unit-এ instruction পাঠাত আর একটি কেন্দ্রীয় টেবিল — scoreboard — দিয়ে হিসাব রাখত কোন unit ব্যস্ত, কোন register-এর মান কে লিখবে। RAW-এ সে অপেক্ষা করাত, WAW-এ নতুন instruction পাঠানো থামাত, আর WAR-এ লেখা পিছিয়ে দিত। এর কয়েক বছর পর IBM System/360 Model 91-এ Robert Tomasulo-র পদ্ধতি register-এর নাম বদলে (register renaming) WAR আর WAW-কে পুরোপুরি মুছে দেয় — আজকের out-of-order core-এর ভিত্তি এটিই, বিস্তারিত পর্ব ৪০-এ।

১০ · AI-এর যুগে — pipeline-এর হিসাব AI দিয়ে, যাচাই নিজে

Pipeline diagram আঁকা আর cycle গোনা ঠিক সেই ধরনের কাজ, যেখানে AI আত্মবিশ্বাসের সাথে ভুল করে। এই বিষয়ে AI-এর সাধারণ ভুলগুলো:

• MIPS আর RISC-V-এর রীতি মিশিয়ে ফেলা — যেমন পুরোনো MIPS-এর load delay slot বা $t0-ধাঁচের register, অথবা ForwardA-র encoding উল্টে বলা (01 আর 10 অদলবদল)।
• Register file-এর অর্ধ-cycle কৌশল ভুলে গিয়ে forwarding ছাড়া পরপর instruction-এ ৩টি stall বলা — অথবা উল্টোটা, কোন রীতি ধরছে তা না বলেই।
• Forwarding থাকলেও load-use stall বাদ দেওয়া, বা ALU-র ফলের জন্যও stall বসানো।
• WAR/WAW-কে in-order ৫-stage pipeline-এ hazard বলা, বা মাঝখানে অন্য লেখক থাকলেও দূরের জোড়াকে RAW গোনা।
• মোট cycle-এ pipeline ভরার ৪ cycle যোগ না করা, বা “৪০% load-use” কে সব instruction-এর ৪০% ধরে CPI হিসাব করা।

AI-এর দেওয়া pipeline-উত্তর যাচাইয়ের চেকলিস্ট

• রীতি স্পষ্ট — RISC-V না MIPS, অর্ধ-cycle register file আছে কি না, কোন forwarding পথ ধরা হয়েছে
• প্রতিটি RAW-এর দূরত্ব নিজে গুনেছি আর নিয়ম মিলিয়েছি: forwarding ছাড়া max(০, ৩ − d), load-use-এ ১
• মোট cycle = n + ৪ + stall — diagram-এর শেষ WB-এর cycle নম্বরের সাথে মেলে
• ForwardA/ForwardB-এর encoding আর অগ্রাধিকার (EX/MEM আগে) পাঠ্যবইয়ের সাথে মিলিয়েছি, x0-এর ক্ষেত্র আলাদা পরীক্ষা করেছি
• উত্তরটি উপরের simulator-এ (বা নিজের লেখা স্ক্রিপ্টে) একই কোড বসিয়ে আবার চালিয়েছি; বাস্তব CPU-র latency দাবি করলে নির্মাতার optimization manual দেখেছি