Forwarding ও Stalling — Data Hazard-এর দুইটা সমাধান
Forwarding and Stalling
একই data hazard-এর দুইটা সমাধান — stalling (নিরাপদ, ধীর) আর forwarding (দ্রুত, কিন্তু load-use hazard-এ এক cycle stall এখনো অনিবার্য)।
আগে এটা বুঝি
গত লেসনের শেষ দৃশ্যটা মনে করুন:
ADD R1, R2, R3 ; R1 ← R2 + R3
SUB R4, R1, R5 ; R4 ← R1 − R5SUB তার ID স্টেজে (cycle ৩) R1 পড়তে চায়, কিন্তু ADD
তখনো EX-এ, ফলাফল register file-এ পৌঁছাবে অনেক পরে। কোনো fix
ছাড়া SUB একটা পুরনো, ভুল মান পড়ে ফেলবে।
এই একটা সমস্যার দুইটা সম্পূর্ণ ভিন্ন সমাধান আছে — আর দুটোই বাস্তব CPU-তে ব্যবহৃত হয়, একসাথে, একে অপরের পরিপূরক হিসেবে।
প্রথম সমাধান — Stalling। সবচেয়ে সহজ চিন্তা: SUB-কে
যথেষ্ট দেরি করাও, যাতে ADD-এর ফলাফল register file-এ পৌঁছানোর
পরেই SUB সেটা পড়ে। নিরাপদ, সরল, প্রমাণ করা সহজ — কিন্তু
প্রতিটা অপেক্ষার cycle মানেই হারানো throughput।
দ্বিতীয় সমাধান — Forwarding। একটু চতুর চিন্তা: ADD-এর
ফলাফল register file-এ লেখা পর্যন্ত অপেক্ষা করারই বা দরকার কী?
ADD-এর ALU যখন ফলাফল গণনা করে ফেলে (তার EX স্টেজেই), সেই
মুহূর্তেই সেটা একটা সরাসরি তার দিয়ে SUB-এর ALU input-এ পাঠিয়ে
দাও — register file-কে সম্পূর্ণ বাইপাস করে। এটাই forwarding,
আর এই লেসনের মূল আবিষ্কার এটাই যে এই একটা বাড়তি তার (আক্ষরিক
অর্থেই একটা wire, কোনো জটিল লজিক না) বেশিরভাগ data hazard-এর
পুরো খরচ শূন্যে নামিয়ে দেয়।
কিন্তু forwarding-ও সর্বশক্তিমান না। একটা নির্দিষ্ট, অত্যন্ত সাধারণ প্যাটার্নে — যাকে বলে load-use hazard — এমনকি সবচেয়ে ভালো forwarding hardware দিয়েও কমপক্ষে এক cycle stall অনিবার্য। এই লেসনের শেষ ভাগে আমরা দেখব কেন, আর কীভাবে একজন compiler সেই একটা stall cycle-কেও কাজে লাগিয়ে ফেলতে পারে।
মূল ধারণা
Stalling — সবচেয়ে নিরাপদ সমাধান
নিয়ম: যদি একটা instruction-এর ID স্টেজে দরকারি operand
এখনো register file-এ না পৌঁছায়, তাহলে সেই instruction-কে (আর
তার পরে আসা সবাইকে) freeze করো — একই স্টেজে আটকে রাখো,
আর তার জায়গায় pipeline-এ একটা bubble (কার্যত একটা NOP)
পাঠিয়ে দাও পরের স্টেজে।
গত লেসনের timing model অনুযায়ী (register write সম্পূর্ণ হয়
WB cycle-এর শেষে, মান পড়ার জন্য উপলব্ধ হয় তার পরের cycle
থেকে): ADD-এর WB cycle ৫-এ, তাই R1 নির্ভরযোগ্যভাবে
পড়া যায় শুধু cycle ৬ থেকে। SUB-কে তার ID স্টেজ cycle ৬-এ
নিতে হবে — মূল অবস্থান (cycle ৩) থেকে ৩ cycle পিছিয়ে।
Cycle: 1 2 3 4 5 6 7 8 9
ADD R1,R2,R3: IF ID EX MEM WB
SUB R4,R1,R5: IF ID ID ID ID EX MEM WB
└──── stall × 3 ────┘SUB-এর ID চারবার দেখানো হয়েছে — প্রথমবার (cycle ৩) hazard
ধরা পড়ে, পরের তিনবার (cycle ৪, ৫, ৬) সেই একই instruction
register file-এর দিকে “আবার চেষ্টা করছে,” যতক্ষণ না মান সত্যিই
উপলব্ধ হয়। এই তিনটা অতিরিক্ত cycle-এ SUB-এর জায়গায় pipeline-এর
EX স্টেজে bubble (NOP) ঢুকছে — datapath-এর সেই অংশ কোনো
প্রকৃত কাজ করছে না।
Cycle: 1 2 3 4 5 6 7 8 9
ADD R1,R2,R3: IF ID EX MEM WB
SUB (stalled): IF ID -- -- -- EX MEM WB
Bubble: EX MEM WBখরচ: ৩টা stall cycle মানেই SUB-এর জন্য ৩টা bubble —
datapath-এর তিনটা স্টেজ তিন cycle ধরে কোনো real কাজ করেনি। CPI
হিসেবে: গত লেসনের সূত্র অনুযায়ী CPI = 1 + stalls per instruction। যদি প্রতিটা ADD→SUB-এর মতো back-to-back
নির্ভরতায় ৩ cycle stall লাগে, আর একটা প্রোগ্রামে এমন হাজার্ড
ঘন ঘন ঘটে, CPI দ্রুত 1-এর অনেক উপরে উঠে যায় — গত লেসনের
4× ideal speedup বাস্তবে 2×, এমনকি 1.5×-এ নেমে আসতে
পারে।
Forwarding — সরাসরি তার দিয়ে বাইপাস
লক্ষ্য করুন: ADD-এর ALU তার EX স্টেজেই (cycle ৩) ফলাফল
গণনা করে ফেলে। সেই ফলাফলটা EX/MEM pipeline register-এ জমা
হয়, cycle ৪-এর শুরুতে উপলব্ধ। ঠিক সেই একই মুহূর্তে, যদি
SUB স্বাভাবিকভাবে (কোনো stall ছাড়া) এগোতে দেওয়া হয়, তার
EX স্টেজও ঠিক cycle ৪-এই ঘটবে!
Cycle: 1 2 3 4 5 6
ADD R1,R2,R3: IF ID EX MEM WB
SUB R4,R1,R5: IF ID EX MEM WB
↑ ↑
ADD-এর ফলাফল SUB-এর EX — এখানেই
EX/MEM latch-এ দরকার R1
উপলব্ধ (cycle 4) (cycle 4)দুইটা ঘটনা একই cycle-এ ঘটছে — যদি একটা তার দিয়ে ADD-এর
EX/MEM pipeline register-এর মান সরাসরি SUB-এর ALU input-এ
পাঠানো যায়, তাহলে কোনো stall-ই লাগে না! এটাই EX-to-EX
forwarding (একে “EX hazard forwarding”-ও বলা হয়) — সবচেয়ে
সাধারণ, সবচেয়ে গুরুত্বপূর্ণ forwarding path।
Cycle: 1 2 3 4 5 6
ADD R1,R2,R3: IF ID EX MEM WB
SUB R4,R1,R5: IF ID EX MEM WB ← কোনো stall নেই!৩ cycle stall থেকে ০ cycle — একটা মাত্র বাড়তি তার দিয়ে।
Forwarding path-এর পূর্ণ চিত্র
একই ধরনের যুক্তি আরেকটা পরিস্থিতিতেও কাজে লাগে: producer আর consumer-এর মাঝে যদি একটা instruction থাকে (back-to-back না, এক ধাপ দূরে):
ADD R1, R2, R3
NOP-এর মতো কিছু (অসংশ্লিষ্ট instruction)
SUB R4, R1, R5Cycle: 1 2 3 4 5 6
ADD R1,R2,R3: IF ID EX MEM WB
(অসংশ্লিষ্ট): IF ID EX MEM WB
SUB R4,R1,R5: IF ID EX MEM WB
↑ ↑
ADD-এর ফলাফল SUB-এর EX
এখন MEM/WB (cycle 5)
latch-এএখানে ADD-এর ফলাফল cycle ৫-এ SUB-এর EX স্টেজে দরকার,
কিন্তু ততক্ষণে সেটা EX/MEM register ছেড়ে MEM/WB register-এ
চলে গেছে (কারণ ADD নিজে এক cycle এগিয়ে গেছে)। তাই দ্বিতীয়
একটা forwarding path দরকার: MEM/WB-to-EX forwarding।
┌─────────────────────────────┐
│ │
┌────┐ ┌────┐ │ ┌────┐ ┌─────┐ ┌────┐ │
│ IF │──▶│ ID │──┴─▶│ EX │──▶│ MEM │──▶│ WB │──┘
└────┘ └────┘ └────┘ └─────┘ └────┘
▲ │ │
│ │ EX/MEM │ MEM/WB
│ │ forward │ forward
└──────────┴─────────┘
(ALU input mux — register file
output অথবা forwarded value বেছে নেয়)Forwarding unit নামের একটা ছোট combinational লজিক প্রতি
cycle-এ চেক করে: EX স্টেজে থাকা instruction-এর source
register কি EX/MEM বা MEM/WB pipeline register-এ থাকা কোনো
destination register-এর সাথে মেলে? মিললে, register file-এর
সাধারণ output-এর বদলে forwarded value বেছে নেওয়া হয় — একটা
সাধারণ MUX-select সিদ্ধান্ত, ঠিক ALU-design লেসনের output MUX-এর
মতো নীতিতে।
ভেতরে কী ঘটছে
Load-use hazard — forwarding যেখানে হার মানে
এবার একটা ভিন্ন sequence দেখুন:
LOAD R1, 0(R2) ; R1 ← Memory[R2]
ADD R3, R1, R4 ; R3 ← R1 + R4LOAD-এর ডেটা memory থেকে আসে তার MEM স্টেজে — EX স্টেজে
না, যেখানে ADD-এর ফলাফল তৈরি হতো। এটাই মূল পার্থক্য: ADD
তার ফলাফল EX-এর শেষে পায়; LOAD তার ফলাফল পায় MEM-এর
শেষে — এক স্টেজ পরে।
Cycle: 1 2 3 4 5 6
LOAD R1,0(R2): IF ID EX MEM WB
ADD R3,R1,R4: IF ID EX MEM WB
↑ ↑
ADD-এর EX LOAD-এর ফলাফল
(cycle 4, MEM-এ তৈরি
R1 দরকার) (cycle 4-এর শেষে)Cycle ৪-এ ADD-এর EX স্টেজে R1 দরকার — কিন্তু ঠিক সেই
cycle-এই LOAD তার MEM স্টেজে আছে, ডেটা তখনো memory থেকে
আসছে, cycle ৪-এর শেষেই পাওয়া যাবে। ADD-এর EX-এর
শুরুতে সেই মান লাগবে — যা এখনো তৈরিই হয়নি।
এখানে forwarding থাকলেও এক cycle দেরি অনিবার্য — কারণ তথ্যটা এখনো অস্তিত্বেই নেই সেই মুহূর্তে, শুধু ভুল জায়গায় থাকা না। কোনো তার, যত দ্রুতই হোক, এমন কিছু পাঠাতে পারে না যা এখনো তৈরিই হয়নি।
Cycle: 1 2 3 4 5 6 7
LOAD R1,0(R2): IF ID EX MEM WB
ADD R3,R1,R4: IF ID ID* EX MEM WB
└── stall × 1 ──┘ADD-এর ID cycle ৩-এ শুরু হয়, cycle ৪-এ একবার আবার
(stall), তারপর cycle ৫-এ তার EX, যেখানে LOAD-এর MEM
output সরাসরি forward হয়ে আসে। নিট ফলাফল: ১টা মাত্র stall
cycle, ADD/SUB-এর ৩টার তুলনায় অনেক কম, কিন্তু ০ না।
Compiler instruction scheduling — stall cycle-টাকে কাজে লাগানো
hardware যদি একটা bubble ঢোকায়, সেই cycle-এ datapath কিছুই
করে না — একটা সম্পূর্ণ নষ্ট cycle। কিন্তু যদি LOAD আর
নির্ভরশীল ADD-এর মাঝে একটা স্বাধীন instruction থাকে,
সেই instruction-টাই সেই ফাঁকা cycle-এ কাজ করতে পারে — বিনামূল্যে!
LOAD R1, 0(R2)
ADD R6, R7, R8 ; সম্পূর্ণ স্বাধীন — R1 বা R2 কারো সাথে সম্পর্ক নেই
ADD R3, R1, R4 ; আসল নির্ভরশীল instructionCycle: 1 2 3 4 5 6 7
LOAD R1,0(R2): IF ID EX MEM WB
ADD R6,R7,R8: IF ID EX MEM WB
ADD R3,R1,R4: IF ID EX MEM WB
↑ ↑
EX (cycle 5) LOAD-এর ফলাফল
forward হয়ে MEM-এ (cycle 4)
R1 পায়লক্ষ্য করুন ADD R3,R1,R4-এর ID এখন cycle ৪-এ (আগের মতো
৩-এ না, কারণ মাঝে একটা instruction ঢুকেছে), আর তার EX cycle
৫-এ — ঠিক তখনই যখন LOAD-এর ফলাফল (MEM/WB-এ, cycle ৪-এর
শেষে তৈরি) forward করে পাঠানো যায়। কোনো stall লাগেনি — কারণ
compiler ইচ্ছাকৃতভাবে ADD R6,R7,R8-কে সেই “গ্যাপ”-এ বসিয়ে
দিয়েছে, hardware-এর bubble-এর বদলে আসল কাজ।
এই কৌশলের নাম instruction scheduling — এটা কম্পাইলার optimization-এর একটা মৌলিক অংশ (Level ৫-এ compiler-এর optimization pass হিসেবে বিস্তারিত দেখবেন)। compiler-এর কাছে hardware-এর মতো “রিয়েল-টাইম” তথ্য নেই, কিন্তু compiler-এর একটা বড় সুবিধা আছে: এটা পুরো প্রোগ্রাম একবারে দেখতে পারে, আর আগে থেকেই জানে কোন instruction-এর মাঝে dependency আছে — তাই এটা এমন independent instruction খুঁজে বের করে reorder করতে পারে, যেটা hardware রানটাইমে করতে পারবে না (অন্তত in-order pipeline-এ না — লেসন ১৩-এ দেখবেন out-of-order hardware আসলে ঠিক এই কাজটাই রানটাইমে করে)।
উদাহরণ
একটা পূর্ণ trace — গত লেসনের চার-instruction sequence, এবার forwarding সহ
গত লেসনের সেই sequence মনে করুন:
1: LOAD R1, 0(R2)
2: ADD R3, R1, R4
3: SUB R5, R3, R6
4: BEQ R5, R0, LABELএবার forwarding hardware সক্রিয় ধরে trace করি (control hazard এখনো unresolved — লেসন ১২-এর বিষয়, এখানে শুধু data hazard অংশ):
Instruction 1→2 (LOAD→ADD, R1 নিয়ে): এটা একটা
load-use hazard (উপরে দেখানো ঠিক এই প্যাটার্ন) — ১ cycle
stall অনিবার্য, তারপর MEM/WB forwarding।
Instruction 2→3 (ADD→SUB, R3 নিয়ে): ADD তার stall-এর
কারণে এক cycle পিছিয়ে গেছে, কিন্তু এটা এখন ADD→SUB
back-to-back ALU নির্ভরতা (স্ট্যান্ডার্ড EX-to-EX forwarding
ক্ষেত্র) — ০ cycle stall।
Instruction 3→4 (SUB→BEQ, R5 নিয়ে): একইভাবে
back-to-back ALU নির্ভরতা — ০ cycle stall, BEQ-এর
condition গণনায় forwarded R5 ব্যবহৃত হয়।
Cycle: 1 2 3 4 5 6 7 8 9
1 LOAD R1,0(R2): IF ID EX MEM WB
2 ADD R3,R1,R4: IF ID ID EX MEM WB
3 SUB R5,R3,R6: IF IF ID EX MEM WB
4 BEQ R5,R0,L: IF ID EX MEM WBলক্ষ্য করুন ADD-এর ID cycle ৩ আর ৪-এ দুইবার দেখানো হয়েছে —
এই একটাই stall (cycle ৪-এ পুনরায় চেষ্টা করে সফল হয়)। এই একটা
stall পুরো পাইপলাইনকে পিছনের সবার জন্যও এক cycle পিছিয়ে
দেয়: SUB-এর IF cycle ৩-এ শুরু হয় কিন্তু ADD ID স্টেজ
ছেড়ে না দেওয়া পর্যন্ত (cycle ৫) সেখানেই আটকে থাকে (cycle ৩ ও ৪
দুইবার IF দেখানো — pipeline-এর সামনের অংশ freeze থাকে), আর
BEQ-এর IF তাই cycle ৫-এ শুরু হয়, ৪-এ নয়। এটাই স্বাভাবিক —
একটা instruction stall করলে তার পেছনের সবাই এক cycle পিছিয়ে
যায়, কিন্তু কেউই নতুন করে বাড়তি stall পায় না (SUB→ADD আর
BEQ→SUB উভয়ই এখনো ০ cycle অতিরিক্ত stall, ঠিক EX-to-EX
forwarding-এর কারণে)।
মোট stall: ১ cycle (শুধু load-use-এর জন্য), যেখানে গত লেসনে কোনো fix ছাড়া প্রতিটা পরপর জোড়ায় ৩ cycle করে stall লাগত — মোট ৯ cycle বেঁচে গেছে, শুধু একটা load-use stall বাদে। এটাই forwarding-এর প্রকৃত শক্তি প্রমাণিত সংখ্যায়: ৪টা RAW hazard-এর মধ্যে ৩টা সম্পূর্ণ শূন্য cycle-এ নেমে এসেছে, একটা মাত্র (load-use) কমেছে ৩ থেকে ১-এ।
নিজে চালিয়ে দেখুন
Load-use hazard বাস্তবে মাপুন — pointer chasing বনাম independent load
mathematics/asymptotic-notation লেসনের pointer-chasing experiment-এর
সাথে তুলনা করুন — সেখানে আমরা cache miss-এর খরচ মেপেছিলাম।
এখানে আমরা একই রকম dependent-access প্যাটার্ন ব্যবহার করছি,
কিন্তু ছোট array (L1 cache-এ আঁটে) দিয়ে — যাতে cache miss না,
বরং pipeline-এর load-use latency-ই মূল প্রভাবক হয়।
// chase_small.c — ছোট array (L1-তে আঁটে), pointer chasing
#include <stdio.h>
#include <stdlib.h>
#define N 1024 // ছোট, L1 cache-এ সহজেই আঁটে
int main(void) {
int next[N];
for (int i = 0; i \< N; i++) next[i] = (i + 1) % N;
volatile int idx = 0;
long iters = 200 * 1000 * 1000L;
for (long i = 0; i \< iters; i++) {
idx = next[idx]; // প্রতিটা load আগের load-এর ফলাফলের উপর নির্ভরশীল
}
printf("%d\n", idx);
return 0;
}// independent_loads.c — একই সংখ্যক load, কিন্তু একে অপরের থেকে স্বাধীন
#include <stdio.h>
int main(void) {
int arr[1024];
for (int i = 0; i \< 1024; i++) arr[i] = i;
volatile int sum = 0;
long iters = 50 * 1000 * 1000L;
for (long i = 0; i \< iters; i++) {
// চারটা independent load — একটা আরেকটার ঠিকানার উপর নির্ভর করে না
sum += arr[i % 1024] + arr[(i+1) % 1024]
+ arr[(i+2) % 1024] + arr[(i+3) % 1024];
}
printf("%d\n", sum);
return 0;
}gcc -O1 -o chase_small chase_small.c
gcc -O1 -o independent_loads independent_loads.c
perf stat -e cycles,instructions ./chase_small
perf stat -e cycles,instructions ./independent_loadsসাধারণ প্যাটার্ন:
chase_small (dependent):
IPC প্রায় ০.৩–০.৫ — প্রতিটা load পরের load-এর ঠিকানা
গণনার জন্য প্রয়োজনীয়, তাই সিরিয়ালাইজড
independent_loads:
IPC প্রায় ২–৩ — একাধিক load একসাথে issue হতে পারে,
কেউ কারো ঠিকানার উপর নির্ভরশীল নাদুইটাই একই সংখ্যক memory access করছে, দুইটাই L1 cache hit (array ছোট) — তবু বিশাল পার্থক্য। এটাই load-use latency-র প্রভাব, cache miss-এর সাথে গুলিয়ে ফেলবেন না: এমনকি cache hit হলেও, একটা load-এর ফলাফল ALU input হিসেবে ব্যবহার করার আগে কয়েক cycle-এর latency আছে (বাস্তব CPU-তে সাধারণত ৩-৫ cycle, এই লেসনের সরলীকৃত মডেলে ১ cycle) — dependent chain-এ এই latency লুকানো যায় না, independent access-এ CPU একাধিক load একসাথে in-flight রাখতে পারে।
একটা dependent load chain (প্রতিটা load-এর ঠিকানা আগের load-এর ফলাফলের উপর নির্ভরশীল) বাস্তবেই পরিমাপযোগ্যভাবে ধীর, এমন কি L1 cache hit হলেও — কারণ load-use latency (mathematics module-এর asymptotic-notation লেসনের cache experiment-এর মতো cache miss না, বরং pipeline-এর নিজস্ব load-to-use বিলম্ব) এড়ানো যায় না।
নিজে বানান
Forwarding Simulator — stall বনাম forward, পাশাপাশি তুলনা
- গত লেসনের hazard detector প্রসারিত করুন — প্রতিটা RAW hazard-এ producer instruction-এর ধরন (ALU op নাকি LOAD) শনাক্ত করুন
- ALU-op producer হলে forwarding দিয়ে ০ stall গণনা করুন
- LOAD producer হলে forwarding থাকা সত্ত্বেও ১ stall যোগ করুন (load-use hazard)
- দুইটা মোড আউটপুট দিন — "stall-only" (forwarding নেই) বনাম "with forwarding" — আর মোট cycle তুলনা করুন
from dataclasses import dataclass, field
@dataclass
class Instr:
text: str
op: str
dest: str | None
srcs: list[str] = field(default_factory=list)
is_load: bool = False
def parse(line: str) -> Instr:
parts = line.replace(',', '').split()
op = parts[0]
is_load = (op == 'LOAD')
dest = parts[1] if op != 'BEQ' else None
srcs = parts[2:] if op != 'BEQ' else parts[1:3]
if is_load:
srcs = [s.split('(')[-1].rstrip(')') for s in srcs]
return Instr(line, op, dest, srcs, is_load)
def trace(program: list[str], forwarding: bool):
"""প্রতিটা instruction-এর real IF/ID/EX/MEM/WB cycle ধাপে ধাপে
গণনা করে — প্রতিটা নতুন instruction-এর ID অন্তত আগের
instruction-এর ID-এর পরের cycle-এ, প্লাস hazard থাকলে stall।"""
instrs = [parse(l) for l in program]
wb = [] # প্রতিটা instruction-এর WB cycle
ex = [] # প্রতিটা instruction-এর EX cycle
id_ = []
next_if = 1
total_stalls = 0
for i, ins in enumerate(instrs):
this_id = max(next_if + 1, id_[-1] + 1 if id_ else next_if + 1)
# হাজার্ড চেক
stall = 0
for j in range(i):
prev = instrs[j]
if prev.dest and prev.dest in ins.srcs:
if forwarding:
# EX-to-EX বা MEM/WB forwarding: producer-এর EX cycle + (2 যদি load, নাহলে 1)
needed_ex_no_earlier_than = ex[j] + (2 if prev.is_load else 1)
else:
# কোনো forwarding নেই: producer-এর WB-এর পরের cycle পর্যন্ত ID আটকাতে হয়
needed_id_no_earlier_than = wb[j] + 1
stall = max(stall, needed_id_no_earlier_than - this_id)
continue
needed_id_no_earlier_than = needed_ex_no_earlier_than - 1
stall = max(stall, needed_id_no_earlier_than - this_id)
this_id += stall
total_stalls += stall
this_ex = this_id + 1
this_mem = this_ex + 1
this_wb = this_mem + 1
id_.append(this_id); ex.append(this_ex); wb.append(this_wb)
next_if = this_id # পরের instruction-এর IF অন্তত এই instruction-এর ID cycle-এ
print(f" {ins.text:<20} IF~{this_id-1:<3} ID{this_id:<3} EX{this_ex:<3} "
f"MEM{this_mem:<3} WB{this_wb:<3} (stall={stall})")
print(f" মোট stall cycle: {total_stalls}\n")
return total_stalls
program = [
"LOAD R1, 0(R2)",
"ADD R3, R1, R4",
"SUB R5, R3, R6",
"BEQ R5, R0, LABEL",
]
print("── Forwarding ছাড়া ──")
trace(program, forwarding=False)
print("── Forwarding সহ ──")
trace(program, forwarding=True)প্রত্যাশিত সারমর্ম:
── Forwarding ছাড়া ──
মোট stall cycle: 9 (প্রতিটা RAW জোড়ায় ৩ cycle করে)
── Forwarding সহ ──
মোট stall cycle: 1 (শুধু load-use hazard)নিজে বাড়ান:
- একটা
--scheduleমোড যোগ করুন যেটা load-use hazard পেলে পরের ২টা independent instruction থেকে একটা খুঁজে সেখানে বসিয়ে দেয় (সহজ greedy scheduler) — stall কমে যায় কি না পরীক্ষা করুন - দেখুন dependency chain-এর দৈর্ঘ্য (৩, ৫, ১০টা পরপর নির্ভরশীল instruction) বাড়ালে forwarding-এর সাথেও কি কোনো stall লাগে (উত্তর: না, যতক্ষণ প্রতিটা ধাপ ALU op — শুধু load-use-এই সমস্যা)
বাস্তব সিস্টেমে
Forwarding ও stalling যেখানে বাস্তবে দেখা যায়
MIPS classic ৫-স্টেজ pipeline। এই লেসনের forwarding path আর hazard detection unit ঠিক MIPS R2000/R3000-এর ডিজাইনের সরাসরি বর্ণনা — Patterson & Hennessy-র বইয়ের কেন্দ্রীয় কেস স্টাডি।
Delay slot ISA — MIPS ও SPARC-এর ঐতিহাসিক সিদ্ধান্ত। পুরনো MIPS ও SPARC ISA-তে load delay slot এবং branch delay slot সরাসরি ISA-র অংশ ছিল — অর্থাৎ compiler বাধ্য ছিল প্রতিটা load বা branch-এর ঠিক পরের instruction slot-টা পূরণ করতে (হয় useful কাজ দিয়ে, নাহলে explicit NOP দিয়ে)। এটা hardware-কে সরল রাখত, কিন্তু compiler-এর কাজ কঠিন করে তুলত।
RISC-V-এর সিদ্ধান্ত — কোনো delay slot নেই। RISC-V ডিজাইনাররা MIPS-এর এই ঐতিহাসিক অভিজ্ঞতা থেকে শিখে ইচ্ছাকৃতভাবে delay slot বাদ দিয়েছেন — কারণ delay slot ISA-তে “উন্মুক্ত” (exposed) করে ফেলে, যা পরবর্তী প্রজন্মের superscalar/out-of-order implementation-এ (লেসন ১৩) জটিলতা তৈরি করে। এটা একটা চমৎকার ইঞ্জিনিয়ারিং শিক্ষা: এক প্রজন্মের জন্য সরল একটা সিদ্ধান্ত পরের প্রজন্মের জন্য বোঝা হয়ে দাঁড়াতে পারে।
আধুনিক OOO CPU — stalling-এর বদলে reordering। x86 বা ARM-এর আধুনিক out-of-order core-এ load-use hazard-কেও প্রায়ই stall না করে — বরং independent পরের instruction-কে এগিয়ে যেতে দেয় (লেসন ১৩-এর মূল বিষয়), stalling আর কম্পাইলার scheduling-এর দরকারই কমিয়ে দেয়। কিন্তু in-order core-এ (embedded, low-power) আজও এই লেসনের কৌশলগুলোই মূল কথা।
GCC/LLVM instruction scheduler pass। -O2/-O3-এ compiler
স্বয়ংক্রিয়ভাবে instruction-গুলো পুনর্বিন্যাস করে — ঠিক এই
লেসনের “স্বাধীন instruction-কে গ্যাপে বসানো” কৌশল, target
CPU-র pipeline model অনুযায়ী। gcc -O0 বনাম -O2-এ generated
assembly পাশাপাশি রেখে দেখলে এই পুনর্বিন্যাস প্রায়ই খালি চোখেই
ধরা পড়ে।
ARM Cortex-M সিরিজের ডেটাশিটে explicit stall-cycle টেবিল। এই মাইক্রোকন্ট্রোলার পরিবারের প্রতিটা ডেটাশিটে সরাসরি লেখা থাকে কোন instruction sequence কত cycle stall করবে — এই লেসনের ঠিক এই cycle-counting যুক্তি বাস্তব ইঞ্জিনিয়ারিং ডকুমেন্টে।
GPU shader compiler-এ software pipelining। উচ্চ-latency texture memory access-এর কারণে GPU shader compiler প্রায়ই বহু independent thread-এর কাজ interleave করে ঠিক এই একই সমস্যার সমাধান করে — একটা thread-এর memory-latency-এর ফাঁকে আরেকটা thread-এর কাজ ভরিয়ে দেয় (Level ১১-এর GPU architecture লেসনে বিস্তারিত)।
যে ভুলগুলো সবাই করে
“Forwarding সব data hazard দূর করে দেয়।”
না — এই লেসনেরই মূল বিষয়: load-use hazard forwarding দিয়েও পুরোপুরি দূর হয় না। কারণ forwarding একটা তথ্য “তাড়াতাড়ি পাঠাতে” পারে, কিন্তু তথ্যটা যদি এখনো তৈরিই না হয়ে থাকে (যেমন memory থেকে data আসতে সময় লাগছে), তাহলে forwarding করার মতো কিছুই নেই। কমপক্ষে ১ cycle stall (এই লেসনের সরলীকৃত মডেলে; বাস্তব CPU-তে L1 cache latency-র কারণে প্রায়ই বেশি) অনিবার্য।
“Stalling আর forwarding দুইটা বিকল্প পদ্ধতি — যেকোনো একটা বেছে নিতে হয়।”
বাস্তব CPU দুটোই একসাথে ব্যবহার করে, প্রতিযোগী হিসেবে না, সহযোগী হিসেবে। Forwarding বেশিরভাগ hazard সামলায় (০ cycle খরচে), আর stalling শুধু সেই ন্যূনতম ক্ষেত্রে ব্যবহৃত হয় যেখানে forwarding দিয়েও সমাধান সম্ভব না (load-use)। “শুধু stall কর” বা “শুধু forward কর” — কোনোটাই বাস্তবসম্মত নীতি না; বাস্তব ডিজাইন নীতি হলো যতটা সম্ভব forward করো, যেটুকু বাকি থাকে সেটুকু stall করো।
“একটা stalled cycle মানেই সময় নষ্ট, তাই সবসময় এড়ানো উচিত।”
এই ধারণাটা আংশিক সত্য কিন্তু বিভ্রান্তিকর। প্রতিটা stall cycle-এ throughput-এর সরাসরি খরচ আছে, ঠিক। কিন্তু stall এড়ানোরও একটা খরচ আছে — hardware জটিলতা (আরও forwarding path, আরও comparator, আরও control logic), যা silicon area, power, আর design/verification সময় বাড়ায়।
একটা খুব কম ঘটা hazard (যেমন একটা বিরল multi-cycle floating-point
op-এর সাথে dependency) এড়াতে জটিল forwarding hardware বানানো
প্রায়ই লাভজনক না — সেখানে মাঝে মাঝে stall মেনে নেওয়াই বাস্তবসম্মত।
Load-use hazard-এর জন্য সবাই forwarding+১stall-এর কম্বিনেশন
ব্যবহার করে কারণ এটা অত্যন্ত ঘন ঘন ঘটে (প্রতিটা LOAD-এর
পরের instruction-এ সম্ভাবনা আছে) — cost-benefit হিসাব এখানে
স্পষ্টভাবে hardware fix-এর পক্ষে।
“কম্পাইলারের instruction scheduling সবসময় 'ফ্রি' পারফরম্যান্স এনে দেয়।”
শুধু তখনই কাজ করে যখন প্রকৃতপক্ষে একটা independent instruction পাওয়া যায় যেটা সেই ফাঁকে বসানো যায়। ছোট, ঘনভাবে সম্পর্কিত কোড-এ (যেমন একটা টাইট recurrence loop, যেখানে প্রায় সবকিছু আগেরটার উপর নির্ভরশীল) compiler কিছু খুঁজে না পেয়ে বাধ্য হয়ে explicit NOP বসায় — তখন hardware stall আর compiler-এর “সমাধান” ঠিক একই খরচ বহন করে, শুধু সিদ্ধান্তটা compile-time-এ নেওয়া। “Free lunch” শুধু তখনই আসে যখন প্রোগ্রামে সত্যিকারের instruction-level parallelism (স্বাধীন কাজ) বিদ্যমান থাকে।
বুঝেছেন কি না দেখুন
1ADD R2, R1, R1 এর ঠিক পরে ADD R3, R2, R2 থাকলে — forwarding
সহ কত cycle stall লাগবে? আপনার উত্তর ব্যাখ্যা করুন cycle
নম্বর দিয়ে।
যুক্তি
ADD R2, R1, R1 এর ঠিক পরে ADD R3, R2, R2 থাকলে — forwarding
সহ কত cycle stall লাগবে? আপনার উত্তর ব্যাখ্যা করুন cycle
নম্বর দিয়ে।০ cycle stall। এটা একটা সাধারণ back-to-back ALU-op নির্ভরতা
(EX-to-EX forwarding ক্ষেত্র), ঠিক এই লেসনের ADD→SUB
উদাহরণের মতো।
প্রথম ADD: IF@1, ID@2, EX@3, MEM@4, WB@5।
দ্বিতীয় ADD: IF@2, ID@3, EX@4, ...।
প্রথম ADD-এর ফলাফল EX/MEM pipeline register-এ cycle ৪-এর
শুরুতে উপলব্ধ — ঠিক তখনই যখন দ্বিতীয় ADD-এর EX স্টেজ
(cycle ৪) সেই মান চায়। EX-to-EX forwarding path এটা সরাসরি
সরবরাহ করে, কোনো stall ছাড়াই।
2LOAD R1, 0(R2) এর ঠিক পরে LOAD R3, 0(R1) থাকলে (দ্বিতীয়
LOAD-এর ঠিকানা প্রথম LOAD-এর ফলাফলের উপর নির্ভরশীল) — এটা
কোন hazard, আর কত stall লাগবে?
প্রয়োগ
LOAD R1, 0(R2) এর ঠিক পরে LOAD R3, 0(R1) থাকলে (দ্বিতীয়
LOAD-এর ঠিকানা প্রথম LOAD-এর ফলাফলের উপর নির্ভরশীল) — এটা
কোন hazard, আর কত stall লাগবে?এটাও একটা load-use hazard, কারণ দ্বিতীয় LOAD-এর ঠিকানা
গণনা (address calculation, যেটা EX স্টেজে ঘটে) প্রথম
LOAD-এর ফলাফল (R1) দরকার — আর প্রথম LOAD-এর ফলাফল MEM
স্টেজে তৈরি হয়, EX-এ না।
গণিতটা ঠিক এই লেসনের LOAD→ADD উদাহরণের মতোই: ১ cycle
stall, তারপর MEM/WB-থেকে forward করে দ্বিতীয় LOAD-এর
ঠিকানা গণনায় ব্যবহার করা হয়। লক্ষ্য করুন — “load-use hazard”
নামটা producer LOAD হলেই প্রযোজ্য, consumer instruction
নিজে LOAD না ADD তা গুরুত্বপূর্ণ না।
3নিচের sequence-এ কয়টা stall cycle লাগবে (forwarding সহ)?
LOAD R1, 0(R2)
LOAD R3, 4(R2)
ADD R4, R1, R3
প্রয়োগ
LOAD R1, 0(R2)
LOAD R3, 4(R2)
ADD R4, R1, R3এখানে দুইটা LOAD একে অপরের থেকে স্বাধীন (একটাই ঠিকানা
R2-নির্ভর হলেও একে অপরের ফলাফলের উপর না)। তারা পরপর
পাইপলাইনে চলবে কোনো stall ছাড়াই:
LOAD1: IF@1, ID@2, EX@3, MEM@4, WB@5
LOAD2: IF@2, ID@3, EX@4, MEM@5, WB@6
ADD-এর R1 আর R3 দুটোই দরকার। কোনো stall ছাড়া ADD-এর
EX হতো cycle ৫-এ (IF@3, ID@4, EX@5)।
LOAD1 (R1) নিয়ে যাচাই: LOAD1-এর MEM output cycle
৪-এর শেষে তৈরি, forward হয়ে উপলব্ধ cycle ৫-এর শুরু থেকে —
ঠিক তখনই যখন ADD-এর EX (cycle ৫) সেটা চায়। কোনো stall
লাগে না, EX-to-EX-এর মতোই margin ঠিক শূন্য।
LOAD2 (R3) নিয়ে যাচাই: LOAD2-এর MEM output cycle
৫-এর শেষে তৈরি, forward হয়ে উপলব্ধ cycle ৬-এর শুরু থেকে —
কিন্তু ADD-এর EX (stall ছাড়া) হতো cycle ৫-এ, তার এক
cycle আগে। এটাই classic load-use hazard।
তাই ১ cycle stall লাগবে — শুধু LOAD2-এর কারণে। Stall-এর
পর ADD-এর ID cycle ৫-এ সফল হয়, EX cycle ৬-এ — ঠিক তখনই
যখন LOAD2-এর forwarded মান উপলব্ধ। LOAD1-এর R1 ততক্ষণে
আরও আগেই উপলব্ধ ছিল (margin-সহ), তাই সেই নির্ভরতা কোনো বাড়তি
stall যোগ করে না।
4একজন ছাত্র প্রস্তাব দিলো: “load-use hazard-ও তো forwarding দিয়ে
সমাধান করা যায় — শুধু MEM স্টেজের মাঝখান থেকে (memory
read সম্পূর্ণ হওয়ার আগেই) ডেটা forward করে দাও।” এই প্রস্তাবের
সমস্যা কী?
ডিজাইন
MEM স্টেজের মাঝখান থেকে (memory
read সম্পূর্ণ হওয়ার আগেই) ডেটা forward করে দাও।” এই প্রস্তাবের
সমস্যা কী?সমস্যাটা মৌলিক, শুধু ইঞ্জিনিয়ারিং জটিলতার না: memory read
সম্পূর্ণ হওয়ার আগে ডেটা অস্তিত্বেই নেই। MEM স্টেজের কাজ
হলো memory access করা — এটার একটা নির্দিষ্ট সময় লাগে (SRAM
হলেও কয়েক gate delay, এক-দুই cycle)। “মাঝখান থেকে forward
করা” মানে ডেটা তৈরি হওয়ার আগেই সেটা ব্যবহার করার চেষ্টা —
এটা কোনো hardware দিয়েই সম্ভব না, কারণ এটা causality (কারণ-ফল
সম্পর্ক) লঙ্ঘন করে।
Forwarding সবসময় “যা ইতিমধ্যে গণনা হয়ে গেছে কিন্তু এখনো সঠিক জায়গায় পৌঁছায়নি” এমন ডেটার জন্য কাজ করে — তথ্যটা নিজেই এখনো তৈরি না হলে forwarding-এর কিছু করার নেই। এটাই দেখায় কেন load-use hazard-এর ন্যূনতম stall (memory access latency যতটুকু) কোনো পরিমাণ hardware প্রকৌশল দিয়েও এড়ানো যায় না — শুধু কমানো যায় (দ্রুততর memory, বা বেশি independent কাজ দিয়ে ঢেকে দেওয়া)।
5এই লেসনের CPI সূত্র (CPI = 1 + stalls per instruction)
ব্যবহার করে: একটা প্রোগ্রামে প্রতি ৫টা instruction-এ ১টা
load-use hazard থাকে (প্রতিটাতে ১ cycle stall)। CPI কত? গত
লেসনের 4× ideal speedup বাস্তবে কত হবে (একই ৫-স্টেজ, ২০০ps
ক্লক মডেল ধরে)?
যুক্তি
CPI = 1 + stalls per instruction)
ব্যবহার করে: একটা প্রোগ্রামে প্রতি ৫টা instruction-এ ১টা
load-use hazard থাকে (প্রতিটাতে ১ cycle stall)। CPI কত? গত
লেসনের 4× ideal speedup বাস্তবে কত হবে (একই ৫-স্টেজ, ২০০ps
ক্লক মডেল ধরে)?Stalls per instruction: (1/5) × 1 = 0.2।
CPI = 1 + 0.2 = 1.2।
বাস্তব speedup: ideal 4× কে CPI-এর অনুপাতে ভাগ করে —
4 / 1.2 ≈ 3.33×। গত লেসনের কোনো fix-ছাড়া উদাহরণের CPI
(3.98/2.5 অনুপাতে হিসাব করলে অনেক বেশি) এর তুলনায় 1.2
CPI প্রায় ideal-এর কাছাকাছি — forwarding-এর প্রভাব এখানে
সরাসরি সংখ্যায় দৃশ্যমান।
এরপর কী
এরপর কী
এই লেসনে data hazard-এর গল্প শেষ — forwarding বেশিরভাগ কেস শূন্য cycle-এ নামায়, বাকি (load-use) একটা predictable, ছোট cycle স্ট্যাক হয়ে থাকে যা compiler scheduling দিয়ে প্রায়ই ঢেকে দেওয়া যায়।
কিন্তু গত লেসনের তৃতীয় hazard এখনো অস্পর্শিত: control hazard। Forwarding এখানে কোনো কাজে আসে না — কারণ সমস্যাটা কোনো ডেটার মান নিয়ে না, বরং কোন instruction-টা পরে আসবে তা নিয়ে। একটা branch-এর ফলাফল জানার আগেই CPU-কে fetch চালিয়ে যেতে হয়।
পরের লেসনে আমরা দেখব কীভাবে CPU এই অনিশ্চয়তার মুখোমুখি হয়ে একটা শিক্ষিত অনুমান (prediction) করে — প্রথমে সরল নিয়মে (সবসময় not-taken ধরে নাও), তারপর একটা ছোট state machine দিয়ে (১-বিট, তারপর ২-বিট saturating counter) যা প্যাটার্ন মনে রাখতে শেখে। আর দেখব ভুল অনুমানের real খরচ — misprediction penalty — কীভাবে pipeline depth-এর সাথে সরাসরি সম্পর্কিত।
আরও পড়ুন
- Computer Organization and Design (RISC-V Edition), Section 4.7 — Data Hazards: Forwarding versus Stalling — David A. Patterson, John L. Hennessy · Forwarding unit-এর control logic আর load-use hazard-এর প্রামাণ্য derivation — এই লেসনের ভিত্তি
- The MIPS-X RISC Microprocessor — delayed branch ও delayed load-এর মূল নকশা আলোচনা — John Hennessy et al., Stanford University · Load delay slot-কে কম্পাইলার-visible করার মূল যুক্তি — এই লেসনের 'compiler scheduling' অংশের ঐতিহাসিক উৎস