Amdahl's Law ও প্যারালাল স্পিডআপ

১ · Amdahl's Law কী

Amdahl's LawAmdahl's Lawএকটি প্রোগ্রামকে একাধিক প্রসেসরে প্যারালালাইজ করে সর্বোচ্চ সম্ভাব্য স্পিডআপ পরিমাপ করার সূত্র, যেখানে প্রোগ্রামের একটি অংশ অনিবার্যভাবে সিকোয়েন্সিয়াল থাকে। পরিমাপ করে দেয় একটি প্রোগ্রামকে প্যারালালাইজ করে সর্বোচ্চ কতটুকু স্পিডআপ পাওয়া সম্ভব — যদি সেই প্রোগ্রামের একটি অংশ অনিবার্যভাবে সিকোয়েন্সিয়াল থাকে (যত প্রসেসরই যোগ করা হোক না কেন, সেই অংশ প্যারালাল করা যায় না)। এটি সরাসরি M5-এর ক্রিটিক্যাল সেকশন ধারণার সাথে যুক্ত — একটি প্রোগ্রামের ক্রিটিক্যাল সেকশনে একবারে মাত্র একটি থ্রেড ঢুকতে পারে, তাই সেই অংশটুকু কার্যত সিকোয়েন্সিয়াল।

যদি $S$ হয় প্রোগ্রামের সিকোয়েন্সিয়াল (অ-প্যারালালাইজযোগ্য) ভগ্নাংশ এবং $N$ হয় প্রসেসরের সংখ্যা, তাহলে —

$$\text{speedup} = \frac{1}{S + \dfrac{1-S}{N}}$$

অর্থাৎ মোট সময়ের $S$ অংশ কখনও ছোট হয় না (যত প্রসেসর যোগ করা হোক), আর বাকি $(1-S)$ অংশ $N$টি প্রসেসরের মধ্যে ভাগ হয়ে যায়।

২ · Worked Example — S=0.25, N=4

ধরা যাক একটি প্রোগ্রামের ২৫% ($S=0.25$) সিকোয়েন্সিয়াল, এবং আমরা ৪টি প্রসেসর ($N=4$) ব্যবহার করছি। হাতে-কলমে হিসাব — $\frac{1-S}{N} = \frac{0.75}{4} = 0.1875$, তাই $S + \frac{1-S}{N} = 0.25 + 0.1875 = 0.4375$, এবং $\text{speedup} = \frac{1}{0.4375} \approx 2.286$x। লক্ষ্য করুন — ৪টি প্রসেসর ব্যবহার করেও স্পিডআপ ৪x নয়, মাত্র প্রায় ২.২৮৬x — কারণ সেই অনিবার্য ২৫% সিকোয়েন্সিয়াল অংশ একটি বটলনেক হয়ে থেকেই যায়।

৩ · প্রসেসর বাড়ালে কী হয় — একটি হার্ড সীলিং

$N \to \infty$ হলে $\frac{1-S}{N} \to 0$, তাই speedup $\to \frac{1}{S}$ — একটি কঠিন সীলিং (hard ceiling) যা যতই প্রসেসর যোগ করা হোক না কেন কখনও অতিক্রম করা যায় না। $S=0.25$-এর জন্য এই সীলিং $\frac{1}{0.25} = 4$x — অর্থাৎ এই প্রোগ্রামটি কখনওই ৪x-এর বেশি স্পিডআপ পাবে না, এমনকি অসীম সংখ্যক প্রসেসর দিলেও নয়। এটি একটি গুরুত্বপূর্ণ, প্রায়ই বিস্ময়কর বাস্তবতা।

৪ · কোড দিয়ে যাচাই

নিচের কোড সেলে amdahl_speedup() ফাংশনটি বাস্তবায়ন করা হয়েছে এবং উপরের worked example-সহ N=8, N=100, N=1,000,000-এর জন্যও গণনা করে দেখানো হয়েছে স্পিডআপ কীভাবে ধীরে ধীরে ৪x-এর কাছাকাছি যায়, কিন্তু কখনওই তা অতিক্রম করে না।

# Amdahl's Law -- বাস্তব সূত্র, প্রকৃত গণনা (toy simulation নয়, এটি সরাসরি গাণিতিক সূত্র)
def amdahl_speedup(sequential_fraction, num_processors):
    S = sequential_fraction
    N = num_processors
    parallel_fraction = 1 - S
    return 1 / (S + parallel_fraction / N)

S = 0.25  # ২৫% অংশ অনিবার্যভাবে সিকোয়েন্সিয়াল (যেমন M5-এর ক্রিটিক্যাল সেকশন)

print("--- মূল worked example: S=0.25, N=4 ---")
speedup_4 = amdahl_speedup(S, 4)
print(f"speedup = {speedup_4:.3f}x  (প্রত্যাশিত ≈ 2.286x, 4x নয়!)")

print("\n--- প্রসেসর সংখ্যা বাড়ালে কী হয় (একই S=0.25) ---")
for n in [4, 8, 16, 100, 1_000_000]:
    s = amdahl_speedup(S, n)
    print(f"N = {n:>10,} -> speedup = {s:.6f}x")

ceiling = 1 / S
print(f"\nহার্ড সীলিং (N -> ∞): 1/S = {ceiling:.3f}x -- যতই প্রসেসর যোগ করি, এই সীমা কখনও পার হবে না।")