Foundationপ্রথম নীতি থেকে
LEVEL 3অ্যাডভান্সড~১০ ঘণ্টাPython

Pipeline Visualizer

Pipeline Visualizer

একটা ছোট ইন্সট্রাকশন সিকোয়েন্স নিয়ে 5-stage (IF/ID/EX/MEM/WB) পাইপলাইনের cycle-by-cycle টেবিল বানানো — data hazard স্বয়ংক্রিয়ভাবে ডিটেক্ট করে naive stall-only আর forwarding মোডের cycle-count পার্থক্য সংখ্যায় দেখানো, আর branch misprediction-এ ঠিক কত সাইকেল নষ্ট হয় সেটা flush করে গুনে দেখানো।

মাইলস্টোন

আগে যা পড়া দরকার

কেন এই প্রজেক্ট

Pipelining and hazards লেসনে আমরা দেখেছি কেন pipeline থিওরিতে সুন্দর (প্রতি সাইকেলে একটা ইন্সট্রাকশন শেষ) কিন্তু বাস্তবে hazard-এর কারণে সেই প্রতিশ্রুতি প্রায়ই ভাঙে। Forwarding and stalling লেসনে দেখেছি কীভাবে hardware সেই hazard-গুলো সামলায় — কখনো data বাইপাস করে (forwarding), কখনো বাধ্য হয়ে অপেক্ষা করে (stalling)।

এই দুটো ধারণা পড়ে বোঝা যায়, কিন্তু সংখ্যায় না দেখলে “forwarding কতটা লাভজনক” এই প্রশ্নটার উত্তর অনুভূতি-নির্ভর থেকে যায়। এই প্রজেক্টে একটা pipeline simulator বানাব যেটা একই প্রোগ্রাম দুইবার চালাবে — একবার naive stall-only মোডে, একবার forwarding মোডে — আর ঠিক কত সাইকেল বাঁচলো সেটা গুনে বলবে। শেষে একটা branch যোগ করে দেখাব misprediction-এর real cost কী।

Hazard-এর ধরন — সংক্ষিপ্ত রিক্যাপ

এই প্রজেক্টে দুই ধরনের hazard সামলাতে হবে:

  • Data hazard (RAW — read-after-write): একটা ইন্সট্রাকশন এমন একটা রেজিস্টার পড়তে চায় যেটা এখনো pipeline-এ থাকা আগের কোনো ইন্সট্রাকশন লিখছে। এটাই এই প্রজেক্টের মূল কাজ।
  • Control hazard: একটা branch-এর ফলাফল না জানা পর্যন্ত পরের কোন ইন্সট্রাকশন fetch করব সেটা অনিশ্চিত। শেষ অংশে predict-not-taken দিয়ে সামলাব।

ধাপে ধাপে

১. ইন্সট্রাকশন রিপ্রেজেন্টেশন

from dataclasses import dataclass

@dataclass
class Instr:
    text: str
    dest: str = None
    src1: str = None
    src2: str = None
    kind: str = 'alu'   # 'alu' — ফলাফল EX স্টেজের শেষে রেডি; 'load' — MEM স্টেজের শেষে রেডি

kind ফিল্ডটাই forwarding মোডে load-use hazard আলাদাভাবে ধরার চাবিকাঠি — ALU ইন্সট্রাকশনের ফলাফল এক সাইকেল আগে রেডি হয়ে যায় load-এর চেয়ে, কারণ ALU-এর উত্তর EX স্টেজেই বেরিয়ে যায়, load-এর উত্তর মেমরি থেকে আসে MEM স্টেজে।

২. Hazard detection ও cycle simulator

এটাই কেন্দ্রীয় ফাংশন। প্রতিটা ইন্সট্রাকশনের জন্য তার IF/ID/EX/MEM/WB সাইকেল বের করে, দরকার হলে ID স্টেজে stall ঢুকিয়ে:

def simulate(instrs, forwarding):
    dest_wb_cycle = {}      # রেজিস্টার -> সবচেয়ে সাম্প্রতিক writer-এর WB সাইকেল
    dest_ready_cycle = {}   # রেজিস্টার -> forward করা মান কোন সাইকেল থেকে ব্যবহারযোগ্য
    cum_delay = 0            # আগের stall-গুলোর সঞ্চিত প্রভাব — পরের সব ইন্সট্রাকশনের IF-ও পিছিয়ে যায়
    rows = []

    for i, instr in enumerate(instrs):
        IF = i + 1 + cum_delay
        ID = IF + 1

        # --- hazard detection: এই ইন্সট্রাকশনের src রেজিস্টার আগের কোনো
        #     in-flight ইন্সট্রাকশনের dest-এর সাথে মেলে কি না ---
        needed = 0
        for src in (instr.src1, instr.src2):
            if src is None:
                continue
            if not forwarding:
                # naive stall-only: producer-এর WB শেষ না হওয়া পর্যন্ত ID করা যাবে না
                if src in dest_wb_cycle:
                    producer_wb = dest_wb_cycle[src]
                    needed = max(needed, (producer_wb + 1) - ID)
            else:
                # forwarding: EX/MEM বা MEM/WB latch থেকে সরাসরি consumer-এর EX-এ বাইপাস
                if src in dest_ready_cycle:
                    ready = dest_ready_cycle[src]
                    consumer_ex_natural = ID + 1
                    needed = max(needed, ready - consumer_ex_natural)

        stall = max(0, needed)
        ID += stall
        cum_delay += stall

        EX, MEM, WB = ID + 1, ID + 2, ID + 3

        if instr.dest:
            dest_wb_cycle[instr.dest] = WB
            dest_ready_cycle[instr.dest] = (MEM + 1) if instr.kind == 'load' else (EX + 1)

        rows.append((instr.text, IF, ID, EX, MEM, WB, stall))
    return rows

needed গণনাটাই hazard detection: naive মোডে আমরা জিজ্ঞেস করছি “producer-এর regfile-write (WB) শেষ হওয়ার পরের সাইকেলে পৌঁছাতে consumer-এর ID-কে কত পিছাতে হবে?” — forwarding মোডে জিজ্ঞেস করছি “producer-এর forward-ready মান পৌঁছানোর আগেই consumer-এর EX হয়ে যাচ্ছে কি না, হলে কত পিছাতে হবে?” দুটোই max(0, ...) দিয়ে wrap করা আছে, তাই hazard না থাকলে স্বয়ংক্রিয়ভাবে stall = 0 হয়ে যায় — আলাদা কোনো “কোনো hazard নেই” শাখা লেখার দরকার নেই।

৩. Cycle-by-cycle টেবিল প্রিন্ট করা

def print_table(rows):
    max_cycle = max(r[5] for r in rows)   # সব WB-র মধ্যে সবচেয়ে বড়টা
    header = "ইন্সট্রাকশন".ljust(20) + "".join(f"{c:>4}" for c in range(1, max_cycle + 1))
    print(header)
    for text, IF, ID, EX, MEM, WB, stall in rows:
        cells = [" ."] * max_cycle
        for c in range(IF + 1, ID):        # স্টল বাবল
            cells[c - 1] = "**"
        for cycle, name in [(IF, "IF"), (ID, "ID"), (EX, "EX"), (MEM, "M "), (WB, "WB")]:
            cells[cycle - 1] = name
        print(text.ljust(20) + "".join(f"{c:>4}" for c in cells))

৪. উদাহরণ প্রোগ্রাম — দুই মোডে চালানো

program = [
    Instr("ADD R1,R2,R3",    dest='R1',  src1='R2', src2='R3'),
    Instr("SUB R4,R1,R5",    dest='R4',  src1='R1', src2='R5'),   # R1-এর উপর RAW
    Instr("LW  R6,0(R7)",    dest='R6',  src1='R7', kind='load'),
    Instr("ADD R8,R6,R9",    dest='R8',  src1='R6', src2='R9'),   # R6-এর উপর load-use RAW
    Instr("OR  R10,R11,R12", dest='R10', src1='R11', src2='R12'),  # স্বাধীন
]

print_table(simulate(program, forwarding=False))
print_table(simulate(program, forwarding=True))

আসল আউটপুট — naive stall-only (কোনো forwarding নেই):

ইন্সট্রাকশন            1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
ADD R1,R2,R3           IF ID EX M  WB  .  .  .  .  .  .  .  .  .  .
SUB R4,R1,R5            . IF ** ** ** ID EX M  WB  .  .  .  .  .  .
LW  R6,0(R7)             .  .  .  .  . IF ID EX M  WB  .  .  .  .  .
ADD R8,R6,R9              .  .  .  .  .  . IF ** ** ** ID EX M  WB  .
OR  R10,R11,R12            .  .  .  .  .  .  .  .  .  . IF ID EX M  WB

total cycles = 15, মোট stall cycle = 6

আসল আউটপুট — forwarding সহ:

ইন্সট্রাকশন            1  2  3  4  5  6  7  8  9 10
ADD R1,R2,R3           IF ID EX M  WB  .  .  .  .  .
SUB R4,R1,R5             . IF ID EX M  WB  .  .  .  .
LW  R6,0(R7)               .  . IF ID EX M  WB  .  .  .
ADD R8,R6,R9                 .  .  . IF ** ID EX M  WB  .
OR  R10,R11,R12                .  .  .  .  . IF ID EX M  WB

total cycles = 10, মোট stall cycle = 1

ফলাফল: naive stall-only-তে পুরো প্রোগ্রাম শেষ হতে ১৫ সাইকেল লাগে (৬টা stall সাইকেল), forwarding-এ লাগে মাত্র ১০ সাইকেল (১টা stall)। একই প্রোগ্রাম, একই hazard — শুধু forwarding path যোগ করাতেই ৫ সাইকেল বাঁচলো। এটাই forwarding-এর লাভ সংখ্যায়।

৫. কেন SUB forwarding-এ শূন্য stall পেল কিন্তু load-use ১ পেল

SUB-এর R1 লাগে ADD-এর থেকে। ADD-এর EX cycle ৩, তাই তার ফলাফল EX/MEM latch-এ রেডি হয়ে যায় সাইকেল ৪ থেকে (EX + 1)। SUB-এর স্বাভাবিক (কোনো stall ছাড়া) EX cycle-ও ৪ — ঠিক তখনই দরকার, ঠিক তখনই রেডি। শূন্য stall।

ADD R8,R6,R9-এর R6 লাগে LW-এর থেকে। কিন্তু LW-এর ফলাফল ALU-তে বের হয় না — মেমরি থেকে আসে, তাই সেটা রেডি হয় LW-এর MEM স্টেজ শেষ হওয়ার পর (MEM + 1), EX স্টেজ শেষ হওয়ার পর না। ADD-এর স্বাভাবিক EX cycle হতো ঠিক LW-এর MEM cycle-এর সমান — মানে তথ্যটা তখনও আসেনি, এক সাইকেল দেরিতে আসছে। তাই এমনকি forwarding থাকা সত্ত্বেও ঠিক ১ সাইকেল stall লাগে — এটাকে বলে load-use hazard, আর এটা প্রায় সব বাস্তব pipelined CPU-তেই থেকে যায় (forwarding hardware যত ভালোই হোক না কেন, ডেটা মেমরি থেকে এক সাইকেল আগে বেরোতে পারবে না)।

ধাপে ধাপে — Branch misprediction

৬. Predict-not-taken ও resolve stage

এই simulator-এ ধরে নিচ্ছি branch-এর শর্ত ও টার্গেট দুটোই তার EX স্টেজের শেষে resolve হয় (একটা ইচ্ছাকৃত সরলীকরণ — বাস্তব ডিজাইনে comparator-টা প্রায়ই ID স্টেজে সরিয়ে penalty কমানো হয়, ঠিক যেটা branch prediction লেসনে আলোচনা হয়েছে)। “Predict not-taken” মানে branch resolve না হওয়া পর্যন্ত আমরা ধরেই নিচ্ছি এটা নেওয়া হবে না, আর সোজা fall-through পথের ইন্সট্রাকশন speculative fetch করতে থাকি।

resolve stage-এর index অনুযায়ী কত সাইকেল নষ্ট হবে সেটা একটাই ছোট সূত্রে ধরা যায়:

STAGE_INDEX = {'IF': 0, 'ID': 1, 'EX': 2, 'MEM': 3}

def misprediction_penalty(resolve_stage):
    """
    Branch যে স্টেজে resolve হয়, তত সংখ্যক ইন্সট্রাকশন ততক্ষণে speculative-ভাবে
    fetch হয়ে গেছে — misprediction হলে ঠিক সেই সংখ্যক ইন্সট্রাকশন flush হয়।
    """
    return STAGE_INDEX[resolve_stage]

print(misprediction_penalty('EX'))    # 2

৭. উদাহরণ — মিসপ্রেডিক্ট হলে কী ঘটে

ADD R1,R2,R3          # ব্রাঞ্চের আগের সাধারণ ইন্সট্রাকশন
BEQ R1,R0,TARGET       # branch — এই উদাহরণে ধরে নিচ্ছি শর্ত সত্যি (taken)
ADD R4,R5,R6           # fall-through পথে speculative fetch (ভুল পথ)
SUB R7,R8,R9           # fall-through পথে speculative fetch (ভুল পথ)
TARGET: OR R10,R11,R12 # আসল, সঠিক টার্গেট
সাইকেল:         1    2    3    4    5    6    7    8    9
ADD R1,R2,R3   IF   ID   EX   MEM  WB
BEQ            .    IF   ID   EX*  MEM  WB
ADD (ভুল পথ)   .    .    IF   ID   FLUSH
SUB (ভুল পথ)   .    .    .    IF   FLUSH
OR (target)    .    .    .    .    IF   ID   EX   MEM  WB

EX* মানে branch এখানেই resolve হলো — সাইকেল ৪-এর শেষে জানা গেল আসলে branch নেওয়া হবে। ততক্ষণে সাইকেল ৩-এ fall-through-এর প্রথম ইন্সট্রাকশন (ADD, ID পর্যন্ত পৌঁছে গেছে) আর সাইকেল ৪-এ দ্বিতীয়টা (SUB, সবে IF করেছে) — দুটোই speculative, দুটোই ভুল পথে। সাইকেল ৫-এর শুরুতে দুটোই flush হয়, আর সঠিক target (OR) সাইকেল ৫-এ নতুন করে fetch হয়। যদি resolve একদম না দেরি হতো (ধরুন, branch fetch হওয়ার সাথে সাথেই resolve হয়ে যেত), OR সাইকেল ৩-এই fetch হতে পারতো — তাই আসল misprediction penalty হলো 5 − 3 = 2 সাইকেল, ঠিক misprediction_penalty('EX')-এর ফলাফলের সাথে মিলে যাচ্ছে।

তুলনা: branch যদি নেওয়া না হতো (prediction ঠিক থাকতো), ADD/SUB দুটোই সঠিক পথের ইন্সট্রাকশন, কোনো flush হতো না, ০ সাইকেল নষ্ট। এই পার্থক্যটাই বোঝায় কেন branch predictor-এর accuracy সরাসরি CPU-র গড় performance-এ প্রভাব ফেলে — প্রতিটা misprediction-এর দাম নির্দিষ্ট (এখানে ২ সাইকেল), কিন্তু কত ঘনঘন সেই দাম গুনতে হচ্ছে সেটা predictor-এর ভালো-খারাপের উপর নির্ভর করে।

নিজেকে চ্যালেঞ্জ করুন

  1. ID-স্টেজ resolve — misprediction_penalty('ID') ব্যবহার করে branch তুলনা early move করুন, penalty ২ থেকে ১-এ নামিয়ে দেখান
  2. Structural hazard — যদি instruction memory আর data memory একই মেমরি হয় (single-cycle CPU প্রজেক্টের মতো Harvard না হয়ে), তাহলে fetch আর memory-access stage একই সাইকেলে সংঘর্ষে পড়তে পারে — সেই hazard-ও ডিটেক্ট করে stall ঢোকান
  3. Static branch prediction — always-taken — একটা বিকল্প predictor যোগ করে দুটো policy-র (not-taken বনাম always-taken) গড় penalty বিভিন্ন loop-heavy প্রোগ্রামে তুলনা করুন
  4. 2-bit saturating counter predictor — প্রতিটা branch-এর নিজস্ব ২-বিট history রাখুন, misprediction rate-এর উন্নতি মাপুন
  5. ASCII animation — টেবিলের বদলে প্রতি সাইকেলে টার্মিনাল ক্লিয়ার করে “লাইভ” পাইপলাইন দেখান (প্রতিটা স্টেজে কোন ইন্সট্রাকশন আছে, রঙ করে বাবল দেখানো)

এটা যেখানে গিয়ে মিশবে

এখানে যা শিখলেনপরে কোথায় লাগবে
Cycle-accurate hazard detection ও stall injectionএই মডিউলেরই CPU Emulator প্রজেক্ট — একই fetch-decode-execute যুক্তি, এখানে স্টেজে ভাগ করা
Forwarding path (EX/MEM, MEM/WB) ও তার সীমা (load-use)Level 11 — Advanced Architecture-এর superscalar ও out-of-order execution, যেখানে forwarding নেটওয়ার্ক আরও জটিল হয়
Predict-not-taken ও misprediction penalty গণনাLevel 11 — branch predictor ডিজাইন (2-bit counter, tournament predictor)
Cycle count দিয়ে performance তুলনা করা অভ্যাসLevel 11 — profiling ও performance engineering, IPC (instructions-per-cycle) বিশ্লেষণ
স্বয়ংক্রিয় hazard detection-এর যুক্তিAssembly module — compiler-এর instruction scheduling (hazard এড়াতে reordering)