স্ট্রাকচারাল হ্যাজার্ড

Structural hazards

৭ মিনিট পড়া মধ্যম · Intermediate Python কোডসহ সম্পূর্ণ বাংলায়

এক নজরে · TL;DR

স্ট্রাকচারাল হ্যাজার্ডStructural Hazardদুটি ইনস্ট্রাকশন, ভিন্ন পাইপলাইন স্টেজে থাকা অবস্থাতেই, একই সাইকেলে একই হার্ডওয়্যার রিসোর্স ব্যবহার করতে চাইলে ঘটে। ঘটে যখন দুটি ইনস্ট্রাকশন একই সাইকেলে একই হার্ডওয়্যার রিসোর্স চায়, কিন্তু সেই রিসোর্সের মাত্র একটিই কপি আছে।
ক্লাসিক উদাহরণ: একক (ইউনিফায়েড) মেমরিতে LOAD-এর MEM স্টেজ পরের কোনো ইনস্ট্রাকশনের IF (Fetch) স্টেজের সাথে সংঘর্ষে পড়ে।
সমাধান দুটি — (১) রিসোর্স ডুপ্লিকেট করা (আলাদা ইনস্ট্রাকশন ও ডেটা মেমরি), অথবা (২) স্টল করা (এক সাইকেলের "বাবল" ঢোকানো)।
কোড দিয়ে যাচাই করা হয়েছে — স্টল-ভিত্তিক সমাধান আদর্শ K+N-1 টাইমিংয়ের চেয়ে ঠিক ১ সাইকেল বেশি সময় নেয়, প্রতিটি হ্যাজার্ড ঘটনার প্রকৃত খরচ।

এই পাঠে যা শিখবেন

স্ট্রাকচারাল হ্যাজার্ড কী এবং এটি ঠিক কীভাবে ঘটে
একক মেমরির উদাহরণ দিয়ে LOAD-এর MEM স্টেজ ও পরের ইনস্ট্রাকশনের IF স্টেজের সংঘর্ষ সনাক্ত করা
দুটি রেজোলিউশন কৌশল — রিসোর্স ডুপ্লিকেশন ও স্টল — এবং বাস্তবে কোনটি সাধারণত ব্যবহৃত হয়
কোড দিয়ে যাচাই করা যে স্টল রেজোলিউশন আদর্শ K+N-1 টাইমিংয়ের চেয়ে ঠিক কতটা বেশি সময় নেয়

১ · স্ট্রাকচারাল হ্যাজার্ড কী

L32-এর K+N-1 আদর্শ টাইমিং ধরে নিয়েছিল প্রতিটি স্টেজ প্রতিটি সাইকেলে নিজের কাজ নির্বিঘ্নে করে যেতে পারবে। কিন্তু বাস্তবে, দুটি ভিন্ন ইনস্ট্রাকশন, ভিন্ন পাইপলাইন স্টেজে থাকা অবস্থাতেই, একই সাইকেলে একই হার্ডওয়্যার রিসোর্স চাইতে পারে — অথচ সেই রিসোর্সের মাত্র একটিই কপি হার্ডওয়্যারে বিদ্যমান। একে বলা হয় স্ট্রাকচারাল হ্যাজার্ড।

সবচেয়ে ক্লাসিক উদাহরণ: যদি ইনস্ট্রাকশন মেমরি ও ডেটা মেমরি একই, একক (unified) মেমরি হয় (আলাদা না করা হয়), তাহলে একটি LOAD ইনস্ট্রাকশনের MEM স্টেজ (ডেটা পড়া) ঠিক সেই সাইকেলে অন্য একটি পরের ইনস্ট্রাকশনের IF স্টেজের (পরবর্তী ইনস্ট্রাকশন ফেচ করা) সাথে সংঘর্ষে পড়তে পারে — দুটোরই একই মেমরি হার্ডওয়্যার দরকার, কিন্তু একটি মাত্র পোর্ট আছে।

দুই ভিন্ন ইনস্ট্রাকশনের দুটি ভিন্ন স্টেজ (LOAD-এর MEM, পরের ইনস্ট্রাকশনের IF) একই সাইকেলে একই মেমরি হার্ডওয়্যার চাইছে — এটিই স্ট্রাকচারাল হ্যাজার্ড।

২ · দুটি রেজোলিউশন কৌশল

রিসোর্স ডুপ্লিকেশন
মেমরির ক্ষেত্রে বাস্তব সমাধান — আলাদা ইনস্ট্রাকশন মেমরি ও ডেটা মেমরি (বা আলাদা I-cache/D-cache, M8-এ বিস্তারিত), যাতে fetch ও memory-access একসাথে কনফ্লিক্ট ছাড়াই চলতে পারে।

স্টল (বাবল)
ডুপ্লিকেট করা সম্ভব না হলে, সংঘর্ষরত ইনস্ট্রাকশনকে এক বা একাধিক সাইকেল অপেক্ষা করানো হয় ("বাবল" ঢোকানো) — একটি বাস্তব, পরিমাপযোগ্য পারফরম্যান্স খরচ।

বাস্তব CPU ডিজাইনে মেমরির ক্ষেত্রে প্রায় সবসময় প্রথম সমাধানটিই ব্যবহৃত হয় — আলাদা ইনস্ট্রাকশন ও ডেটা মেমরি (বা আলাদা L1 ইনস্ট্রাকশন-ক্যাশ ও ডেটা-ক্যাশ, M8/L42-এ বিস্তারিত দেখা যাবে) — কারণ ডুপ্লিকেশনের হার্ডওয়্যার খরচ তুলনামূলকভাবে সস্তা, অথচ প্রতি ইনস্ট্রাকশনে স্টল খরচ করলে পুরো পাইপলাইনের লাভই কমে যায়। কিন্তু সব রিসোর্সের ক্ষেত্রে ডুপ্লিকেশন সাশ্রয়ী বা সম্ভব নয় (যেমন একটি জটিল, ব্যয়বহুল মাল্টিপ্লাইয়ার ইউনিট) — তখন স্টলই একমাত্র বাস্তবসম্মত উপায়।

৩ · কোড দিয়ে যাচাই — সংঘর্ষ সনাক্তকরণ ও স্টল খরচ

নিচের কোড সেলে একটি ৫-স্টেজ (K=5) পাইপলাইনে ৬টি (N=6) ইনস্ট্রাকশন সিমুলেট করা হয়েছে, যার দ্বিতীয়টি একটি LOAD। একক মেমরি ধরে নিয়ে কোন সাইকেলে সংঘর্ষ ঘটে তা L32-এর টাইমিং মডেল পুনর্ব্যবহার করে গণনা করা হয়েছে, তারপর ১ সাইকেলের স্টল যোগ করে মোট সময় কতটা বাড়ল তা নিশ্চিত করা হয়েছে।

Python

# স্ট্রাকচারাল হ্যাজার্ড -- একক মেমরিতে LOAD বনাম পরের IF-এর সংঘর্ষ, ও স্টল খরচ
IF, ID, EX, MEM, WB = 1, 2, 3, 4, 5

def ideal_stage_cycle(instr_pos, stage_num):
    """হ্যাজার্ড-মুক্ত অবস্থায় instr_pos ইনস্ট্রাকশন stage_num স্টেজে কোন সাইকেলে থাকবে (L32-এর মডেল)"""
    return instr_pos + stage_num - 1

K, N = 5, 6
load_position = 2  # ইনস্ট্রাকশন #২ একটি LOAD, একক মেমরি ব্যবহার করে MEM স্টেজে

ideal_total = K + N - 1
print(f"আদর্শ (হ্যাজার্ড-মুক্ত ধরে নিলে) সম্পন্ন হওয়ার সময়: {ideal_total} সাইকেল")

# ধাপ ১: সংঘর্ষ সনাক্তকরণ -- LOAD-এর MEM স্টেজ বনাম পরের ইনস্ট্রাকশনগুলোর IF স্টেজ
load_mem_cycle = ideal_stage_cycle(load_position, MEM)
colliding_position = None
for pos in range(load_position + 1, N + 1):
    if ideal_stage_cycle(pos, IF) == load_mem_cycle:
        colliding_position = pos
        break

print(f"\nLOAD (ইনস্ট্রাকশন #{load_position}) এর MEM স্টেজ পড়ে সাইকেল {load_mem_cycle}-এ।")
print(f"ইনস্ট্রাকশন #{colliding_position}-এর IF স্টেজও একই সাইকেল {load_mem_cycle}-এ পড়ে -- স্ট্রাকচারাল হ্যাজার্ড!")

# ধাপ ২: স্টল রেজোলিউশন -- সংঘর্ষরত ইনস্ট্রাকশন ও তার পরের সবগুলো ১ সাইকেল পিছিয়ে যায়
stall_cycles = 1
stalled_total = ideal_total + stall_cycles
print(f"\n১ সাইকেলের 'বাবল' যোগ করে সমাধান করলে মোট সময়: {stalled_total} সাইকেল")

difference = stalled_total - ideal_total
print(f"পার্থক্য: {difference} সাইকেল বেশি -- ঠিক প্রত্যাশিত মতোই, আদর্শ K+N-1 এর চেয়ে ১ বেশি")
assert stalled_total == ideal_total + 1

# তুলনা: রিসোর্স ডুপ্লিকেশন (আলাদা ইনস্ট্রাকশন/ডেটা মেমরি) ব্যবহার করলে কোনো সংঘর্ষই ঘটে না
duplicated_total = ideal_total  # কোনো স্টল দরকার নেই
print(f"\nআলাদা ইনস্ট্রাকশন ও ডেটা মেমরি থাকলে মোট সময়: {duplicated_total} সাইকেল -- আদর্শ টাইমিংই বজায় থাকে")

লক্ষ্য করুন — ইনস্ট্রাকশন #৫-এর IF ঠিক LOAD (#২)-এর MEM-এর সাথে একই সাইকেল (৫)-এ পড়ে, কারণ MEM স্টেজ IF-এর ঠিক ৩ স্টেজ পরে (IF→ID→EX→MEM), আর ৫-২=৩ — এই দূরত্বের মিল দিয়েই সংঘর্ষটি অনিবার্য হয়ে ওঠে যতক্ষণ না মেমরি ডুপ্লিকেট করা হয় বা স্টল যোগ করা হয়।

মূল কথা · Key takeaway

স্ট্রাকচারাল হ্যাজার্ড একটি খাঁটি হার্ডওয়্যার-রিসোর্স সমস্যা, ইনস্ট্রাকশনের ডেটার সাথে এর কোনো সম্পর্ক নেই। সবচেয়ে সাধারণ ও সস্তা সমাধান হলো ডুপ্লিকেশন (আলাদা মেমরি/ক্যাশ) যেখানেই সম্ভব — কিন্তু যেখানে ডুপ্লিকেশন ব্যয়বহুল, সেখানে স্টল অনিবার্য, এবং প্রতিটি স্টল সাইকেল সরাসরি L32-এর আদর্শ স্পিডআপ থেকে কেড়ে নেয়।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ উপরের কোড সেলে LOAD ইনস্ট্রাকশন #২-এর বদলে যদি #৩ হতো, সংঘর্ষ কোন ইনস্ট্রাকশনের সাথে ও কোন সাইকেলে ঘটত?

দূরত্বের নিয়ম একই থাকে — MEM স্টেজ IF-এর ৩ স্টেজ পরে, তাই সংঘর্ষ সবসময় LOAD-এর ৩ ইনস্ট্রাকশন পরের ইনস্ট্রাকশনের সাথে ঘটে। LOAD #৩ হলে সংঘর্ষ ঘটত ইনস্ট্রাকশন #৬-এর সাথে, সাইকেল ideal_stage_cycle(3, MEM) = 3+4-1 = 6-এ। অর্থাৎ LOAD-এর পজিশন যাই হোক, সংঘর্ষ সবসময় ঠিক ৩ পজিশন পরের ইনস্ট্রাকশনের সাথে ঘটবে (যদি পাইপলাইনে অতগুলো ইনস্ট্রাকশন থাকে)।

প্র ০২ যদি একটি প্রোগ্রামে ৩টি ভিন্ন LOAD ইনস্ট্রাকশন থাকে, প্রতিটিই একক মেমরির কারণে ১ সাইকেল স্টল দাবি করে, মোট কতটা সময় নষ্ট হবে?

প্রতিটি স্বতন্ত্র সংঘর্ষ ঘটনার জন্য আলাদাভাবে ১ সাইকেল স্টল প্রয়োজন (যদি সংঘর্ষগুলো একে অপরকে ওভারল্যাপ না করে), তাই মোট ৩ সাইকেল অতিরিক্ত সময় লাগবে — মোট সম্পন্ন-হওয়ার-সময় হবে (K+N-1)+৩। এটিই দেখায় কেন বাস্তব প্রোগ্রামে অনেক LOAD থাকলে (যা সাধারণ), একক মেমরির স্টল-ভিত্তিক সমাধান দ্রুত ব্যয়বহুল হয়ে ওঠে, আর ডুপ্লিকেশন (আলাদা মেমরি) হয়ে ওঠে অর্থনৈতিকভাবে অপরিহার্য।

প্র ০৩ আলাদা ইনস্ট্রাকশন ও ডেটা মেমরি ব্যবহার করলে কি স্ট্রাকচারাল হ্যাজার্ড সম্পূর্ণভাবে অদৃশ্য হয়ে যায়, নাকি অন্য কোনো রিসোর্সে এখনও ঘটতে পারে?

শুধু এই নির্দিষ্ট মেমরি-সংঘর্ষটি দূর হয় — কিন্তু স্ট্রাকচারাল হ্যাজার্ড একটি সাধারণ ধারণা, যেকোনো একক-কপি হার্ডওয়্যার রিসোর্সে ঘটতে পারে (যেমন একটি ভাগাভাগি করা মাল্টিপ্লাইয়ার ইউনিট, বা রেজিস্টার ফাইলের সীমিত সংখ্যক রিড/রাইট পোর্ট)। প্রতিটি সম্ভাব্য রিসোর্স কনফ্লিক্ট আলাদাভাবে বিশ্লেষণ করে হয় ডুপ্লিকেট করতে হয়, নয়তো স্টল লজিক ডিজাইন করতে হয় — মেমরি ডুপ্লিকেশন শুধু সবচেয়ে সাধারণ, সবচেয়ে গুরুত্বপূর্ণ কেসটি সমাধান করে।

অনুশীলন

চিন্তা করুন: কেন স্ট্রাকচারাল হ্যাজার্ড মেমরির ক্ষেত্রে নির্দিষ্টভাবে LOAD/STORE ইনস্ট্রাকশনের সাথে যুক্ত, R-type (ADD, SUB) ইনস্ট্রাকশনের সাথে নয়?

কারণ একমাত্র LOAD/STORE ইনস্ট্রাকশনই তাদের MEM স্টেজে সত্যিকারের মেমরি অ্যাক্সেস করে — R-type ইনস্ট্রাকশন MEM স্টেজে কিছুই করে না (শুধু "নো-অপ"-এর মতো পার হয়ে যায়, M6/L31-এর প্রসঙ্গে)। তাই একক মেমরিতে সংঘর্ষ ঘটার সম্ভাবনা শুধুই তখন থাকে যখন LOAD/STORE-এর MEM স্টেজ কোনো ইনস্ট্রাকশনের IF-এর সাথে সাইকেল-মিল খায়।
পরীক্ষা করুন: উপরের কোড সেলে N = 6-কে N = 3 করে Run চাপুন — কী ঘটে যখন LOAD-এর ৩ পজিশন পরে আর কোনো ইনস্ট্রাকশনই বাকি নেই?

N=3-এ লুপ range(load_position + 1, N + 1) অর্থাৎ range(3, 4) শুধু pos=3 পরীক্ষা করে, যার IF সাইকেল $3+1-1=3$, আর LOAD-এর MEM সাইকেল $2+4-1=5$ — মিলছে না, তাই colliding_position কখনও সেট হবে না (None থাকবে)। এটি স্পষ্টভাবে দেখায় — পাইপলাইনে যথেষ্ট পরের ইনস্ট্রাকশন না থাকলে (প্রোগ্রামের একেবারে শেষে LOAD থাকলে) স্ট্রাকচারাল হ্যাজার্ড আদৌ ঘটার সুযোগই পায় না।