Pipelining ও Hazard — Assembly Line নীতি সিলিকনে

পাঁচটা স্টেশন

Level ২-এর datapath-কে পাঁচটা ধাপে ভাগ করলে দাঁড়ায়:

Level ২-এর single-cycle CPU-তে এই পাঁচটা ধাপই একই clock cycle-এর ভেতর, একটার পর একটা, combinational logic দিয়ে propagate হয়ে যেত — কোনো ধাপের মাঝখানে কোনো latch ছিল না। আজ আমরা প্রতিটা ধাপের মাঝে একটা pipeline register বসাব — একটা সাধারণ D flip-flop-ভিত্তিক রেজিস্টার যেটা এক স্টেজের আউটপুট পরের cycle-এ পরের স্টেজের কাছে ধরে রাখে। এটাই পুরো কৌশলের হার্ডওয়্যার ভিত্তি: IF/ID, ID/EX, EX/MEM, MEM/WB — চারটা pipeline register, পাঁচটা স্টেজের মাঝে।

Pipeline diagram — মূল ভাষা

এই পুরো module-এ আমরা বারবার একটা নির্দিষ্ট ধরনের ছবি আঁকব: সারি করে instruction, কলাম করে cycle, প্রতিটা ঘরে instruction-টা কোন স্টেজে আছে।

Cycle:      1    2    3    4    5    6    7    8    9
Instr 1:    IF   ID   EX   MEM  WB
Instr 2:         IF   ID   EX   MEM  WB
Instr 3:              IF   ID   EX   MEM  WB
Instr 4:                   IF   ID   EX   MEM  WB
Instr 5:                        IF   ID   EX   MEM  WB

এটা পড়ার নিয়ম: প্রতি সারি একটা instruction, প্রতি column একটা clock cycle। প্রতিটা instruction ঠিক এক cycle পর পর শুরু হচ্ছে — instruction 2 fetch হচ্ছে cycle 2-তে, ঠিক যখন instruction 1 decode হচ্ছে। cycle 5-এ লক্ষ্য করুন: instruction 1 write-back করছে (একদম শেষ ধাপ), অথচ instruction 5 তখনও fetch হচ্ছে (একদম প্রথম ধাপ) — পাঁচটা ভিন্ন instruction পাঁচটা ভিন্ন ধাপে, একই মুহূর্তে, একই হার্ডওয়্যারে (কিন্তু পাঁচটা ভিন্ন sub-circuit-এ)।

এই diagram-টাই এই পুরো ব্যাচের (lesson 10-13) কেন্দ্রীয় ভাষা — প্রতিটা hazard, প্রতিটা fix, প্রতিটা misprediction এই একই grid-এ আঁকা হবে।

থ্রুপুট গণিত — কতটা লাভ?

N টা instruction, K-স্টেজ pipeline। উপরের diagram থেকে প্যাটার্নটা স্পষ্ট: শেষ instruction-টা fetch হয় cycle N-এ, আর তারপর তাকে বাকি K−1 টা স্টেজ পার হতে হয়। মোট সময়:

$\text{Cycles}_{\text{pipelined}} = N + K - 1$

N=5, K=5 হলে: 5+5−1 = 9 cycle — উপরের diagram-এ ঠিক তাই দেখা যাচ্ছে (instruction 5-এর WB cycle 9-এ)।

তুলনায়, non-pipelined (single-cycle) পদ্ধতিতে প্রতিটা instruction সম্পূর্ণ একা একা K cycle সমান সময় নেয় (একটা লম্বা cycle, যার ভেতর সব স্টেজ sequentially চলে):

$\text{Cycles}_{\text{non-pipelined}} = N \times K$

$\text{Speedup} = \frac{N \times K}{N + K - 1} \xrightarrow{N \to \infty} K$

যত N বড় হয়, speedup তত K-এর কাছাকাছি যায় — এটাই “speedup ≈ pipeline depth” দাবিটার সঠিক, সীমাবদ্ধ রূপ। এটা ঠিক mathematics module-এর asymptotic notation লেসনের ভাষায় বলা যায়: Speedup(N) = O(K) as N → ∞, কিন্তু ছোট N-এ এই সীমা অনেক দূরে।

একটা বাস্তব সংখ্যার উদাহরণ

Level ২-এর single-cycle CPU-তে ক্লক পিরিয়ড ঠিক করতে হতো সবচেয়ে ধীর instruction-টার জন্য যথেষ্ট লম্বা করে। ধরা যাক প্রতিটা স্টেজের নিজস্ব combinational delay এরকম (এগুলো বাস্তবসম্মত আনুপাতিক সংখ্যা, real silicon-এর কাছাকাছি):

Single-cycle CPU-তে প্রতিটা instruction, তার ধরন যা-ই হোক (এমনকি ADD, যার MEM স্টেজে কিছুই করার নেই), পুরো ৮০০ ps অপেক্ষা করে — কারণ ক্লক পিরিয়ড একটাই, সবার জন্য সমান, আর সেটা সবচেয়ে ধীর instruction (LOAD) দিয়ে ঠিক হয়েছে।

Pipeline-এ প্রতিটা স্টেজ আলাদা hardware, তাই ক্লক পিরিয়ড ঠিক করা যায় সবচেয়ে ধীর একটা স্টেজ দিয়ে — গোটা instruction দিয়ে না:

$\text{Clock period}_{\text{pipelined}} = \max(200, 100, 200, 200, 100) = 200 \text{ ps}$

এবার N = 1000 instruction চালিয়ে দেখি সময় কতটা বাঁচে:

N বড় হওয়ায় 3.98× প্রায় আদর্শ 4×-এর সমান — fill/drain overhead (K−1 = 4 অতিরিক্ত cycle) মোট 1004 cycle-এর তুলনায় নগণ্য।

কিন্তু N = 5 হলে (ঠিক উপরের diagram-এর মতো ছোট প্রোগ্রাম):

একই hardware, একই clock period, শুধু N ছোট হওয়ায় speedup 4× থেকে নেমে 2.22×-এ। এটা ঠিক mathematics module-এর asymptotic-notation লেসনের সেই শিক্ষার প্রতিধ্বনি: একটা সীমা (এখানে Speedup → K) শুধু N → ∞-এ সত্য; ছোট N-এ “fill” আর “drain” (pipeline ভরা আর খালি হওয়ার সময়) উপেক্ষা করা যায় না।

Cycle:      1    2    3    4    5    6    7    8    9
Instr 1:    IF   ID   EX   MEM  WB
Instr 2:         IF   ID   EX   MEM  WB
Instr 3:              IF   ID   EX   MEM  WB
Instr 4:                   IF   ID   EX   MEM  WB
Instr 5:                        IF   ID   EX   MEM  WB
            └──── fill ────┘              └── drain ──┘

CPI — hazard-এর খরচ মাপার সাধারণ একক

Pipeline performance আলোচনা করার জন্য computer architecture-এর সবচেয়ে সাধারণ একক হলো CPI — Cycles Per Instruction (প্রতি instruction-এ গড়ে কত cycle লাগছে)। এই সংখ্যাটা পরের দুইটা লেসনেও বারবার ফিরে আসবে, তাই এখনই সংজ্ঞায়িত করা ভালো।

$\text{CPI} = \frac{\text{মোট cycle}}{\text{মোট instruction}}$

একটা ideal pipeline-এ (কোনো hazard নেই, প্রতি cycle-এ ঠিক একটা নতুন instruction ঢোকে) স্টেডি-স্টেটে CPI = 1 — বড় N-এ fill/drain-এর প্রভাব নগণ্য হয়ে যায়, তাই Cycles ≈ N, ফলে CPI ≈ 1।

যখনই কোনো hazard-এর কারণে একটা instruction-কে stall করতে হয় (পরের লেসনের বিষয়), সেই instruction-এর পেছনে অতিরিক্ত cycle যোগ হয়, আর CPI 1-এর বেশি হয়ে যায়:

$\text{CPI}_{\text{actual}} = \text{CPI}_{\text{ideal}} + \text{গড় stall cycle প্রতি instruction} = 1 + \text{stalls per instruction}$

উদাহরণ: যদি একটা প্রোগ্রামে প্রতি ৪টা instruction-এ গড়ে ১টা data hazard থাকে, আর প্রতিটা hazard গড়ে ২ cycle stall লাগায়, তাহলে:

$\text{stalls per instruction} = \frac{1}{4} \times 2 = 0.5 \quad\Rightarrow\quad \text{CPI}_{\text{actual}} = 1.5$

বাস্তব speedup তখন CPI_ideal / CPI_actual অনুপাতে কমে যায় — এই লেসনের 4× ideal speedup আসলে 4 / CPI_actual-এ নেমে আসে। CPI যত ১-এর কাছে, pipeline তত তার আদর্শ থ্রুপুটের কাছাকাছি। পরের লেসনে আমরা ঠিক এই CPI সংখ্যাটা দিয়েই forwarding কতটা throughput বাঁচায় তা পরিমাপ করব।