পাইপলাইনিং বেসিকস — কনসেপ্ট ও স্পিডআপ

১ · পাইপলাইনিং কী

M6/L31-এ দেখেছেন কীভাবে একটি ইনস্ট্রাকশনের এক্সিকিউশনকে কয়েকটি ছোট স্টেজে ভাগ করা যায় — Fetch (IF), Decode (ID), Execute (EX), Memory (MEM), Write-back (WB)। মাল্টি-সাইকেল ডিজাইনে একটি ইনস্ট্রাকশন এই স্টেজগুলো একটার পর একটা পার হয়, তারপরই পরের ইনস্ট্রাকশন শুরু হয়। পাইপলাইনিংPipeliningএকই স্টেজ ব্রেকডাউন ব্যবহার করে, কিন্তু প্রতিটি স্টেজ প্রতি সাইকেলে ভিন্ন একটি ইনস্ট্রাকশন নিয়ে কাজ করে — একাধিক ইনস্ট্রাকশন একসাথে "ইন-ফ্লাইট" থাকে। এই ধারণাটি বদলে দেয় — একটি ইনস্ট্রাকশন EX স্টেজে থাকা অবস্থাতেই পরের ইনস্ট্রাকশন ID স্টেজে, আর তার পরেরটা IF স্টেজে থাকতে পারে, সব একই সাইকেলে।

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

২ · আদর্শ সম্পন্ন-হওয়ার-সময় ও স্পিডআপ সূত্র

একটি K-স্টেজ পাইপলাইনে N-টি ইনস্ট্রাকশন প্রসেস করলে, প্রথম ইনস্ট্রাকশনটি সব K স্টেজ পার হতে লাগে K সাইকেল, আর বাকি (N-1) টি ইনস্ট্রাকশন প্রতি সাইকেলে একটি করে যোগ হয়ে সম্পন্ন হয় — তাই মোট সময়:

$$\text{pipeline\_cycles} = K + N - 1$$

অথচ সম্পূর্ণ সিকোয়েনশিয়াল (নন-পাইপলাইনড) এক্সিকিউশনে প্রতিটি ইনস্ট্রাকশন সব K স্টেজ শেষ করার পরই পরেরটি শুরু হয়, তাই মোট সময়:

$$\text{sequential\_cycles} = K \times N$$

এই দুইয়ের অনুপাতই স্পিডআপ —

$$\text{speedup} \approx \frac{K \times N}{K + N - 1}$$

N যখন খুব বড় হয় ($N \to \infty$), তখন $K+N-1 \approx N$, তাই speedup $\approx \frac{K \times N}{N} = K$ — অর্থাৎ স্পিডআপ ধীরে ধীরে K-এর কাছাকাছি যায়, কিন্তু N যতই বড় হোক, কখনও ঠিক K-এর সমান হয় না (এই আচরণটি M7-এর পরের পাঠগুলো পড়ার আগে ঠিক Operating Systems কোর্সের Amdahl's Law পাঠের asymptotic আচরণের সাথে খুবই মিল)।

৩ · কোড দিয়ে যাচাই — N=4, 10, 100

নিচের কোড সেলে pipeline_completion_cycles() ও sequential_completion_cycles() বাস্তবায়ন করে K=5 (একটি বাস্তবসম্মত ৫-স্টেজ পাইপলাইন) ধরে N=4, 10, 100-এর জন্য প্রকৃত স্পিডআপ গণনা করা হয়েছে।

# পাইপলাইন স্পিডআপ -- প্রকৃত গাণিতিক সূত্র, প্রকৃত গণনা
def pipeline_completion_cycles(k_stages, n_instructions):
    """K-স্টেজ পাইপলাইনে N ইনস্ট্রাকশন সম্পন্ন হতে লাগে K+N-1 সাইকেল"""
    return k_stages + n_instructions - 1

def sequential_completion_cycles(k_stages, n_instructions):
    """সম্পূর্ণ সিকোয়েনশিয়াল (নন-পাইপলাইনড) এক্সিকিউশনে লাগে K*N সাইকেল"""
    return k_stages * n_instructions

K = 5  # IF, ID, EX, MEM, WB

print(f"{'N':>5} | {'সিকোয়েনশিয়াল (K*N)':>20} | {'পাইপলাইনড (K+N-1)':>20} | {'Speedup':>10}")
print("-" * 65)
for n in (4, 10, 100):
    seq = sequential_completion_cycles(K, n)
    pipe = pipeline_completion_cycles(K, n)
    speedup = seq / pipe
    print(f"{n:>5} | {seq:>20} | {pipe:>20} | {speedup:>9.4f}x")

print(f"\nK={K} স্টেজের পাইপলাইনে N -> ∞ হলে speedup-এর সীমা: {K}x -- কখনও পৌঁছায় না, শুধু কাছাকাছি যায়।")

# নিশ্চিত করা: N বাড়ার সাথে সাথে speedup একঘেয়েভাবে K-এর কাছাকাছি যায়, কিন্তু কখনও K স্পর্শ করে না
speedups = [sequential_completion_cycles(K, n) / pipeline_completion_cycles(K, n) for n in (4, 10, 100)]
assert speedups[0] < speedups[1] < speedups[2] < K
print(f"যাচাই সম্পন্ন: {speedups[0]:.4f}x < {speedups[1]:.4f}x < {speedups[2]:.4f}x < {K}x")

৪ · কেন এই আদর্শ বাস্তবে পুরোপুরি অর্জিত হয় না

উপরের K+N-1 সূত্রটি একটি আদর্শ, হ্যাজার্ড-মুক্ত পরিস্থিতি ধরে নেয় — প্রতিটি স্টেজ প্রতিটি সাইকেলে নির্বিঘ্নে কাজ করে যায়। বাস্তবে তিন ধরনের হ্যাজার্ডHazardএমন পরিস্থিতি যেখানে পরের ইনস্ট্রাকশন প্রত্যাশিত সাইকেলে তার স্টেজ শুরু করতে পারে না — ফলে পাইপলাইন থামাতে বা "বাবল" ঢোকাতে হয়। এই আদর্শ ওভারল্যাপে বাধা দেয় —

• স্ট্রাকচারাল হ্যাজার্ড — দুটি স্টেজের একই হার্ডওয়্যার রিসোর্স দরকার (পরের পাঠ, L33)।
• ডেটা হ্যাজার্ড — একটি ইনস্ট্রাকশনের দরকারি মান আগের ইনস্ট্রাকশন তখনও লেখেনি (L34)।
• কন্ট্রোল হ্যাজার্ড — একটি ব্রাঞ্চের ফলাফল না জানা পর্যন্ত পরের ইনস্ট্রাকশন কোনটা তা অনিশ্চিত (L35)।