Amdahl ও Gustafson-এর সূত্র — সমান্তরালতার সীমা

আগে এটা বুঝি

এতক্ষণে আমরা GPU-র হাজার হাজার কোর দেখেছি, CUDA দিয়ে হাজার হাজার thread launch করা শিখেছি, আর map/reduce/scan দিয়ে বাস্তব সমস্যাকে সমান্তরাল আকারে ভাঙা শিখেছি। স্বাভাবিক প্রশ্ন: তাহলে যথেষ্ট প্রসেসর জোগাড় করতে পারলে যেকোনো প্রোগ্রামকে যত খুশি দ্রুত করা সম্ভব, তাই না?

না — আর এই লেসনটা বলবে ঠিক কেন না, সংখ্যা দিয়ে।

ধরুন একটা ছবি-প্রসেসিং প্রোগ্রাম — ৯০% সময় একটা filter চালাতে যায় (lesson ১৩-এর মতো, pure map pattern, পুরোপুরি সমান্তরাল করা যায়), বাকি ১০% সময় যায় ফাইল থেকে ছবি পড়তে আর ডিস্কে লিখতে (সিরিয়াল — I/O একটা single stream)। আপনি ৪ কোর ব্যবহার করলেন, তারপর ৬৪, তারপর কল্পনা করুন অসীম কোর — filter অংশটা প্রায় শূন্য সময়ে শেষ হয়ে যাবে। কিন্তু সেই ১০% I/O সময় কখনো কমবে না, কারণ সেটা সমান্তরাল করাই যায় না। তাই পুরো প্রোগ্রামের সময় কখনো সেই ১০%-এর নিচে নামবে না — অসীম কোর দিয়েও।

এটাই Amdahl’s Law-এর হৃদয়: একটা প্রোগ্রামের সিরিয়াল অংশই তার সমান্তরাল speedup-এর চূড়ান্ত সীমা নির্ধারণ করে, প্রসেসর সংখ্যা যতই বাড়ুক না কেন।

মূল ধারণা

Amdahl’s Law — সূত্র derive করা

ধরি একটা প্রোগ্রামের মোট (normalized) সময় ১ একক, single processor-এ। এর p ভাগ সমান্তরাল করা যায়, (1-p) ভাগ অবশ্যই সিরিয়াল থাকতে হবে (কোনো ভাবেই সমান্তরাল করা যায় না — একটা lock, একটা I/O stream, একটা setup ধাপ)।

Single processor-এ সময়: $T_1 = (1-p) + p = 1$

N processor-এ সময়: সিরিয়াল অংশ অপরিবর্তিত থাকে (এটাই তো “সিরিয়াল”-এর সংজ্ঞা), কিন্তু সমান্তরাল অংশ ঠিক N গুণ দ্রুত হয় (আদর্শ ক্ষেত্রে, কোনো overhead ছাড়া):

$T_N = (1-p) + \frac{p}{N}$

Speedup সংজ্ঞায়িত হয় $T_1 / T_N$ হিসেবে:

$\text{Speedup}(N) = \frac{1}{(1-p) + \dfrac{p}{N}}$

এটাই Amdahl’s Law। এখন সবচেয়ে গুরুত্বপূর্ণ পদক্ষেপ — N → ∞ করলে কী হয় দেখি:

$\lim_{N \to \infty} \text{Speedup}(N) = \lim_{N \to \infty} \frac{1}{(1-p) + \dfrac{p}{N}} = \frac{1}{(1-p) + 0} = \frac{1}{1-p}$

p/N পদটা N বাড়ার সাথে সাথে শূন্যের দিকে যায়, কিন্তু (1-p) পদটা অপরিবর্তিত থেকে যায় — এটাই ceiling-এর উৎস। যত বেশি processor যোগ করুন, speedup 1/(1-p)-এর কাছাকাছি যাবে, কিন্তু কখনো ছাড়িয়ে যাবে না।

সংখ্যা দিয়ে — কতটা সোবারিং

p = 0.9 (৯০% সমান্তরাল, উপরের ছবি-প্রসেসিং উদাহরণ) হলে:

$\text{max speedup} = \frac{1}{1 - 0.9} = \frac{1}{0.1} = 10$

অসীম প্রসেসর দিয়েও, সর্বোচ্চ ১০× speedup — এর বেশি কখনো নয়। ৯০% সমান্তরাল শুনতে চমৎকার লাগে, কিন্তু বাকি ১০%-ই আপনার প্রোগ্রামের চূড়ান্ত গতির সীমা নির্ধারণ করে দিচ্ছে।

p = 0.5 (অর্ধেক সমান্তরাল) হলে সিলিং আরও নিচে: 1/0.5 = ২× মাত্র। p = 0.99 (অত্যন্ত সমান্তরাল-বান্ধব কোড)-এও সিলিং ১০০×, অসীম নয়।

সম্পূর্ণ টেবিল — বিভিন্ন `p`, বিভিন্ন `N`-এ

$\text{Speedup}(N) = \frac{1}{(1-p) + p/N}$

`p`	`N=2`	`N=4`	`N=8`	`N=16`	`N=64`	`N=∞`
0.50	1.33×	1.60×	1.78×	1.88×	1.97×	2.00×
0.90	1.82×	3.08×	4.71×	6.40×	8.77×	10.00×
0.95	1.90×	3.48×	5.93×	9.14×	15.42×	20.00×
0.99	1.98×	3.88×	7.48×	13.91×	39.26×	100.00×

হাতে-কলমে যাচাই — p=0.9, N=4: $\text{Speedup} = \frac{1}{(1-0.9) + 0.9/4} = \frac{1}{0.1 + 0.225} = \frac{1}{0.325} = 3.077 \approx 3.08\times \checkmark$

হাতে-কলমে যাচাই — p=0.99, N=64: $\text{Speedup} = \frac{1}{(1-0.99) + 0.99/64} = \frac{1}{0.01 + 0.015469} = \frac{1}{0.025469} = 39.26\times \checkmark$

তিনটা পর্যবেক্ষণ যা টেবিলটা থেকে সরাসরি বেরিয়ে আসে:

১. প্রতিটা row-এর সংখ্যাগুলো ডান দিকে যত এগোয়, বৃদ্ধির হার কমতে থাকে — N=16 থেকে N=64-এ যাওয়া (৪× বেশি প্রসেসর) speedup-কে ৪× করে না, ছোট একটা অংশ বাড়ায়। এটাই diminishing returns-এর গাণিতিক রূপ।

২. p সামান্য বাড়লে (৯০%→৯৯%) সিলিং নাটকীয়ভাবে বাড়ে (১০×→১০০×) — কারণ 1/(1-p) একটা hyperbolic ফাংশন, p → 1-এর কাছে বিস্ফোরিত হয়। এই কারণেই সেই “শেষ কয়েক শতাংশ সিরিয়াল কোড দূর করা” প্রায়ই একটা প্রোগ্রামের সবচেয়ে মূল্যবান optimization।

৩. N=∞ কলামটাই আসল গল্প বলে — বাকি কলামগুলো শুধু দেখায় আপনি কত দ্রুত সেই সিলিং-এর কাছে পৌঁছান।

ভেতরে কী ঘটছে

আগের লেসনগুলো এখানে ফিরে আসে — `(1-p)` আসলে কোথা থেকে আসে

Amdahl’s Law-এর (1-p) পদটা বিমূর্ত মনে হতে পারে, কিন্তু এই পুরো module-এর প্রতিটা আগের লেসন বাস্তবে (1-p) কীভাবে বেড়ে যায় তারই উদাহরণ:

একটা lock (computer-architecture মডিউলের atomics/lock-free লেসন) — lock-সুরক্ষিত critical section, যতই ছোট হোক, একবারে একটা মাত্র thread চালাতে পারে। বাকি thread অপেক্ষা করে — এটা কার্যকরভাবে সিরিয়াল সময়, তা সোর্স কোডে “সমান্তরাল loop”-এর ভেতরে লুকানো থাকলেও।
False sharing (আগের লেসন) — দুইটা thread ভিন্ন variable লিখছে বলে মনে হলেও, একই cache line-এ থাকলে সেই cache line বারবার core-এর মধ্যে “ping-pong” করে। প্রতিটা ping-pong একটা coherence protocol বিলম্ব — কোডে কোনো explicit lock নেই, তবু কার্যকরভাবে thread-গুলো একে অপরকে সিরিয়ালাইজ করছে।
NUMA-remote access (আগের লেসন) — একটা shared data structure যদি একটা নির্দিষ্ট NUMA node-এ বসে থাকে, অন্য node-এর thread-দের access ধীর, আর যদি সেই structure-এ contention থাকে, সব thread কার্যকরভাবে সেই একটা memory controller-এর মধ্য দিয়ে সিরিয়ালাইজ হয়।

মূল অন্তর্দৃষ্টি — 'সমান্তরাল দেখতে হওয়া' আর 'সমান্তরাল হওয়া' এক জিনিস নয়

সোর্স কোডে একটা parallel for লেখা থাকলেই p স্বয়ংক্রিয়ভাবে সেই loop-এর অনুপাতের সমান হয়ে যায় না। যদি সেই loop-এর ভেতরে একটা shared counter atomically increment হয় (progress tracking-এর জন্য, প্রায়ই দেখা যায়), বা একটা shared logging buffer-এ write হয়, সেই ছোট্ট অংশটাই প্রকৃত (1-p), কোডের যতটা “সমান্তরাল দেখতে” ততটা নয়।

উদাহরণ: একটা loop যেখানে ৯৮% কাজ সত্যিই independent, কিন্তু প্রতিটা iteration শেষে একটা shared, lock-সুরক্ষিত progress counter update হয়, যা মোট সময়ের ২% নেয় (contention-এর কারণে, lock ছাড়া হলে যা লাগত তার চেয়ে বেশি)। কার্যকর p = 0.98 নয় — যদি সেই lock-এর contention বেশি thread-এ বাড়তেই থাকে, effective p আরও কমে যেতে পারে ৬৪ বা ১২৮ thread-এ, কারণ lock contention নিজেই N-এর সাথে বাড়ে।

একটা concrete সংখ্যা — p = 0.98 (মাত্র ২% সিরিয়াল, একটা lock-এর কারণে):

$\text{max speedup} = \frac{1}{0.02} = 50$

`N`	Speedup	max-এর কত শতাংশ
16	12.31×	২৪.৬%
64	28.32×	৫৬.৬%
256	41.97×	৮৩.৯%
∞	50.00×	১০০%

লক্ষ্য করুন 256-কোরেও সিলিং-এর মাত্র ৮৪% পাওয়া যাচ্ছে — আর মাত্র ২% সিরিয়াল কোডের জন্য! এটাই দেখায় কেন lock contention বা false sharing-এর মতো “ছোট” সমস্যা large-scale system-এ এত ব্যয়বহুল হয়ে দাঁড়ায়।

উদাহরণ

সম্পূর্ণ উদাহরণ — ছবি-প্রসেসিং পাইপলাইন

ভূমিকার সেই ৯০% filter + ১০% I/O উদাহরণটা সংখ্যা দিয়ে সম্পূর্ণ করি। p = 0.9:

`N`	Filter সময় (একক)	I/O সময় (একক)	মোট সময়	Speedup
1	0.900	0.100	1.000	1.00×
2	0.450	0.100	0.550	1.82×
4	0.225	0.100	0.325	3.08×
16	0.056	0.100	0.156	6.40×
64	0.014	0.100	0.114	8.77×
∞	~0.000	0.100	0.100	10.00×

N = ∞-এ মোট সময় ঠিক ০.১ একক-এ নেমে আসে — অর্থাৎ পুরো প্রোগ্রামের সময় সেই একটা সিরিয়াল অংশের সময়ের সমান হয়ে যায়, তার কম কখনো নয়। এটাই ceiling-এর সবচেয়ে স্বজ্ঞাত রূপ: সিরিয়াল অংশটাই একটা “মেঝে” (floor) তৈরি করে দেয় মোট সময়ের জন্য, যত প্রসেসরই থাকুক।

বাস্তব প্রকৌশল সিদ্ধান্ত

এই উদাহরণে ৬৪ কোর ব্যবহার করে ৮.৭৭× পাওয়া (সিলিং ১০×-এর ৮৮%) বনাম ৪ কোর দিয়ে ৩.০৮× পাওয়ার মধ্যে যে বাড়তি ১৬× হার্ডওয়্যার বিনিয়োগ লাগছে, তার বিনিময়ে speedup বাড়ছে মাত্র ~২.৮৫×। একটা বাস্তব সিদ্ধান্তে এই বাড়তি হার্ডওয়্যারের খরচ কি সেই সামান্য speedup-এর জন্য মূল্যবান? প্রায়ই উত্তর না — বরং সেই ১০% I/O অংশটাকেই optimize করা (যেমন async I/O, বা দ্রুত storage) বেশি লাভজনক, কারণ সেটাই আসল সিলিং তুলে দেয়।

নিজে চালিয়ে দেখুন

EXPERIMENT

তাত্ত্বিক বনাম বাস্তব speedup — overhead-সহ মাপা

Python 3 (multiprocessing)· ২০ মিনিট

import time
import math
from multiprocessing import Pool


def serial_work(duration):
    """সিরিয়াল অংশ simulate — কোনোভাবেই সমান্তরাল করা যায় না"""
    t_end = time.perf_counter() + duration
    x = 0
    while time.perf_counter() \< t_end:
        x += 1
    return x


def parallel_chunk(duration):
    """সমান্তরাল অংশের একটা chunk — independent কাজ"""
    t_end = time.perf_counter() + duration
    x = 0
    while time.perf_counter() \< t_end:
        x += 1.0000001
    return x


def run(p, total_time, n_workers):
    serial_time = total_time * (1 - p)
    parallel_time_per_worker = (total_time * p) / n_workers

    t0 = time.perf_counter()
    serial_work(serial_time)
    if n_workers == 1:
        parallel_chunk(total_time * p)
    else:
        with Pool(n_workers) as pool:
            pool.map(parallel_chunk, [parallel_time_per_worker] * n_workers)
    return time.perf_counter() - t0


def amdahl_speedup(p, n):
    return 1 / ((1 - p) + p / n)


if __name__ == "__main__":
    p = 0.9
    total_time = 0.5   # সেকেন্ড, single-processor baseline
    print(f"p = {p},  baseline (N=1) সময় ≈ {total_time}s\n")
    print(f"{'N':>4} {'measured (s)':>13} {'measured speedup':>17} {'তাত্ত্বিক speedup':>18}")

    t1 = run(p, total_time, 1)
    for n in [1, 2, 4, 8]:
        t_n = run(p, total_time, n)
        measured_speedup = t1 / t_n
        theoretical = amdahl_speedup(p, n)
        print(f"{n:>4} {t_n:>13.4f} {measured_speedup:>16.2f}× {theoretical:>17.2f}×")

সাধারণ output (৪-কোর মেশিনে; সংখ্যা hardware-ভেদে বদলাবে):

p = 0.9,  baseline (N=1) সময় ≈ 0.5s

   N  measured (s)  measured speedup  তাত্ত্বিক speedup
   1        0.5021              1.00×              1.00×
   2        0.2893              1.74×              1.82×
   4        0.1782              2.82×              3.08×
   8        0.1601              3.14×              4.71×

লক্ষ্য করার মতো — N=8-এ measured speedup (৩.১৪×) তাত্ত্বিক Amdahl মান (৪.৭১×)-এর চেয়ে অনেক পিছিয়ে। কারণ Pool(8) তৈরি করা, ৮টা process spawn করা, কাজ pickle করে পাঠানো — এই সবকিছুই সময় নেয়, যা Amdahl-এর সূত্র মডেলই করে না (সূত্রটা ধরে নেয় সমান্তরাল অংশ ঠিক N গুণ দ্রুত হয়, কোনো communication cost ছাড়াই — একটা idealization)।

এই পার্থক্যটাই একটা গুরুত্বপূর্ণ, প্রায়ই ভুলে যাওয়া বাস্তবতা: Amdahl’s Law একটা সেরা-ক্ষেত্রে upper bound দেয়, বাস্তব speedup-এর guarantee নয়। প্রকৃত সিস্টেমে communication overhead, load imbalance, আর synchronization cost যোগ হয়ে speedup-কে তাত্ত্বিক সীমার চেয়েও কম করে দেয় — কখনো কখনো (lesson ১৩-এর build exercise-এ যেমন দেখা গেছে) এত কম যে বেশি প্রসেসর ব্যবহার করা আসলে ধীর করে দেয়।

নিজে বাড়ান: parallel_chunk-এর কাজ আরও ছোট করে দেখুন (duration কমিয়ে) — overhead-এর অনুপাত বাড়ার সাথে সাথে measured আর theoretical curve-এর ফাঁক কীভাবে আরও বড় হয়।

এটা কী প্রমাণ করে

Amdahl-এর সূত্র একটা আদর্শ upper bound দেয়; বাস্তব measured speedup প্রায় সবসময় তার চেয়ে খারাপ, কারণ সূত্রটা process/thread overhead গণনায় ধরে না।

নিজে বানান

BUILD IT

Speedup Calculator — Amdahl বনাম Gustafson

Python · ●●○○○

একটা function লিখুন যা p ও N নিয়ে Amdahl speedup বের করে
একটা function লিখুন যা একই p ও N নিয়ে Gustafson scaled speedup বের করে
দুটোকে পাশাপাশি একটা টেবিলে দেখান, বিভিন্ন p ও N-এ
Amdahl-এর সূত্র উল্টে, একটা টার্গেট speedup পেতে ন্যূনতম কত p লাগবে তা বের করার function লিখুন

def amdahl_speedup(p, n):
    return 1 / ((1 - p) + p / n)


def gustafson_speedup(p, n):
    """p এখানে Gustafson-এর অর্থে — N প্রসেসরে চলা সময়ের সমান্তরাল ভগ্নাংশ"""
    return (1 - p) + p * n


def required_p_for_speedup(target_speedup, n):
    """Amdahl উল্টে — N প্রসেসরে target_speedup পেতে ন্যূনতম p"""
    return (1 - 1 / target_speedup) / (1 - 1 / n)


print(f"{'p':>6} {'N':>5} {'Amdahl':>10} {'Gustafson':>11}")
for p in [0.5, 0.9, 0.95, 0.99]:
    for n in [4, 16, 64]:
        a = amdahl_speedup(p, n)
        g = gustafson_speedup(p, n)
        print(f"{p:>6.2f} {n:>5} {a:>9.2f}× {g:>10.2f}×")

print("\n--- সূত্র উল্টে — টার্গেট speedup পেতে দরকারি p ---")
for target, n in [(10, 16), (20, 32), (50, 64)]:
    p_needed = required_p_for_speedup(target, n)
    check = amdahl_speedup(p_needed, n)
    print(f"N={n:>3}-এ {target}× speedup পেতে p ≥ {p_needed*100:.3f}%   (যাচাই: {check:.2f}×)")

প্রত্যাশিত output (সংক্ষিপ্ত):

     p     N     Amdahl   Gustafson
  0.50     4       1.60×       2.50×
  0.50    16       1.88×       8.00×
  0.50    64       1.97×      32.50×
  0.90     4       3.08×       3.70×
  0.90    16       6.40×      14.50×
  0.90    64       8.77×      57.70×
  0.99    64      39.26×      63.37×

--- সূত্র উল্টে — টার্গেট speedup পেতে দরকারি p ---
N= 16-এ 10× speedup পেতে p ≥ 96.000%   (যাচাই: 10.00×)
N= 32-এ 20× speedup পেতে p ≥ 98.065%   (যাচাই: 20.00×)
N= 64-এ 50× speedup পেতে p ≥ 99.556%   (যাচাই: 50.00×)

দুইটা জিনিস লক্ষ্য করুন। প্রথমত, একই (p, N)-এ Amdahl আর Gustafson সংখ্যা নাটকীয়ভাবে ভিন্ন — p=0.9, N=64-এ Amdahl বলে ৮.৭৭×, Gustafson বলে ৫৭.৭×। এই পার্থক্যটাই পরের অংশের বিষয়। দ্বিতীয়ত, উচ্চ speedup পেতে p কতটা কাছে ১০০% হতে হয় সেটা দেখুন — ৫০× speedup পেতে ৬৪ প্রসেসরে ৯৯.৫৬% সমান্তরাল কোড লাগবে, ৯৯%ও যথেষ্ট না।

নিজে বাড়ান: required_p_for_speedup-এ n → ∞ দিলে সূত্রটা কী হয়ে যায়, হাতে সরল করে দেখান (উত্তর: p = 1 - 1/target_speedup — ঠিক ceiling সূত্রেরই উল্টো রূপ)।

ভেতরে কী ঘটছে

Gustafson’s Law — প্রশ্নটাই পাল্টে দেওয়া

Amdahl’s Law একটা লুকানো অনুমান করে: সমস্যার আকার fixed — আপনি একই কাজ, শুধু দ্রুত শেষ করতে চান। একে বলে strong scaling।

John Gustafson ১৯৮৮ সালে একটা ভিন্ন, সমান বৈধ প্রশ্ন করলেন: বাস্তবে মানুষ প্রায়ই বেশি প্রসেসর পেলে একই কাজ দ্রুত করে না — বড় কাজ করে, একই সময়ে। একটা weather simulation team ৪ প্রসেসর থেকে ৬৪-তে upgrade করলে সাধারণত সেই একই coarse-grained simulation-কে ১৬ গুণ দ্রুত চালায় না — বরং finer resolution grid, বা বেশি sample, বা দীর্ঘ সময়ের forecast simulate করে, একই wall-clock বাজেটে। একে বলে weak scaling।

Gustafson-এর reframe: ধরুন N প্রসেসরে চলা প্রোগ্রামের সময়ের p ভাগ সমান্তরাল অংশে ব্যয় হয় (আকার বড় হওয়া সত্ত্বেও, wall-clock সময় প্রায় স্থির রাখা হয়েছে), (1-p) ভাগ সিরিয়াল। প্রশ্ন: এই একই, এখন বড় কাজটা যদি single processor-এ করতে হতো, কতগুণ সময় লাগত?

সিরিয়াল অংশ একই সময় নিত ((1-p))। কিন্তু সমান্তরাল অংশ — যেটা N প্রসেসরে সমান্তরালে হয়েছিল — single processor-এ সিরিয়ালি করতে N গুণ বেশি সময় লাগত (কারণ কাজের পরিমাণ N-এর সমানুপাতিক বড়, একটা প্রসেসরই তা এক এক করে করবে):

$\text{Scaled Speedup}(N) = (1-p) + p \cdot N$

এটাই Gustafson’s Law। লক্ষ্য করুন — এটা N-এর সাথে রৈখিকভাবে বাড়ে, Amdahl-এর মতো একটা সিলিং-এর দিকে saturate করে না।

একই p, দুইটা সম্পূর্ণ ভিন্ন সংখ্যা কেন

p = 0.9, N = 64:

Amdahl: $\frac{1}{0.1 + 0.9/64} = \frac{1}{0.1141} \approx 8.77\times$
Gustafson: $0.1 + 0.9 \times 64 = 0.1 + 57.6 = 57.7\times$

দুইটাই “সঠিক” — কারণ তারা ভিন্ন প্রশ্নের উত্তর।

Amdahl জিজ্ঞেস করছে: “এই নির্দিষ্ট, fixed-আকারের কাজটা N প্রসেসরে কত দ্রুত শেষ হবে, single-processor-এর তুলনায়?”

Gustafson জিজ্ঞেস করছে: “যদি আমি N প্রসেসরে তার সামর্থ্য অনুযায়ী বড় একটা কাজ একই সময়ে করি, সেই কাজটা single-processor-এ করতে কত বেশি সময় লাগত?”

p-এর সংজ্ঞাও টেকনিক্যালি ভিন্ন এই দুই সূত্রে — Amdahl-এর p হলো fixed-size কাজের সমান্তরাল ভগ্নাংশ (single-processor সময়ের হিসাবে); Gustafson-এর p হলো N-processor রানে সমান্তরাল সময়ের ভগ্নাংশ (scaled/বড় কাজের হিসাবে)। বাস্তবে দুটো ভগ্নাংশ কাছাকাছি হতে পারে যদি সিরিয়াল অংশ কাজের আকারের সাথে না বাড়ে (যেমন একটা fixed setup cost) — কিন্তু ধারণাগতভাবে এরা ভিন্ন জিনিস মাপছে, এটা মনে রাখা জরুরি।

সৎ রায় — কোনটাই “ভুল” নয়

Amdahl’s Law ভুল নয়। যদি আপনার কাজ সত্যিই fixed-size হয় (একটা নির্দিষ্ট ২ GB ভিডিও ফাইল কম্প্রেস করা, একটা নির্দিষ্ট ডেটাসেটে একটা query চালানো), তাহলে speedup-এর একটা কঠোর সিলিং আছে, আর Amdahl-ই সঠিক লেন্স।

Gustafson’s Law-ও ভুল নয়। যদি আপনার কাজের আকার প্রসেসর সংখ্যার সাথে স্বাভাবিকভাবে বাড়ে (একটা বড় সিমুলেশন, বেশি ডেটা প্রসেস করা, উচ্চতর রেজোলিউশন), তাহলে scaled speedup প্রায় রৈখিক, আর অনেক বাস্তব বৈজ্ঞানিক/ডেটা-ইন্টেনসিভ কাজে এটাই ঘটে।

দুটো একে অপরকে খণ্ডন করে না — তারা দুইটা ভিন্ন প্রশ্নের উত্তর দেয়, দুইটা ভিন্ন বাস্তবতার জন্য। সঠিক প্রশ্ন কখনোই “Amdahl নাকি Gustafson সঠিক?” নয় — বরং “আমার workload-এর আকার কি fixed, নাকি প্রসেসর সংখ্যার সাথে বাড়ে?”

বাস্তব সিস্টেমে

এই সূত্রগুলো যেখানে বাস্তব সিদ্ধান্ত নেয়

Parallel build (make -j)। কম্পাইলেশন গ্রাফের বেশিরভাগ ফাইল স্বাধীনভাবে compile হতে পারে (map-সদৃশ), কিন্তু final linking ধাপ সিরিয়াল, আর dependency graph-এর “critical path” (deepest chain of dependent files) একটা কঠিন নিচের সীমা তৈরি করে — Amdahl’s Law সরাসরি প্রযোজ্য, fixed-size কোডবেস।

ডেটাবেস parallel query execution। PostgreSQL-এর parallel seq scan একাধিক worker ব্যবহার করে, কিন্তু query planning ও final result merge/sort সিরিয়াল ধাপ — বড় N worker-এও speedup plateaus করে, ঠিক Amdahl-এর পূর্বাভাস অনুযায়ী।

Video encoding (x264/x265)। ফ্রেম-লেভেল slicing দিয়ে motion estimation সমান্তরাল করা যায়, কিন্তু entropy coding (CABAC) ও rate control-এর একটা অংশ inherently সিরিয়াল নির্ভরতা রাখে (পরের bit-এর encoding আগের bit-এর অবস্থার উপর নির্ভর করে) — এজন্য video encoder-এর thread-count বাড়ানোর একটা practical সিলিং আছে, CPU কোর সংখ্যা যতই বাড়ুক।

MapReduce/Spark shuffle। Lesson ১৩-এর realworld section-এ দেখা map/reduce জব-এ shuffle ধাপ (map আউটপুটকে reducer-দের মধ্যে পুনর্বণ্টন করা) network-bound ও আংশিক সিরিয়াল — এটাই প্রায়ই বড় MapReduce জবের speedup সিলিং করে দেয়, map অংশ যতই বেশি node-এ ছড়ানো হোক না কেন।

Distributed ML training — gradient all-reduce। হাজার হাজার GPU জুড়ে একটা মডেল train করার সময়, প্রতিটা training step শেষে সব GPU-র gradient synchronize (all-reduce) করতে হয় — এই synchronization একটা barrier, যার সময় GPU সংখ্যার সাথে বাড়ে (network overhead)। এটা আধুনিক HPC-র সবচেয়ে বাস্তব, সক্রিয় Amdahl bottleneck — GPU সংখ্যা হাজার ছাড়ালে synchronization overhead-ই dominant হয়ে যায়, যার সমাধানে gradient compression ও asynchronous update-এর মতো কৌশল গবেষণা করা হচ্ছে।

আবহাওয়া/জলবায়ু সিমুলেশন — Gustafson-এর ক্লাসিক উদাহরণ। একটা weather center বেশি কম্পিউট পেলে সাধারণত একই grid resolution-এ দ্রুত forecast বের করে না — বরং finer grid (বেশি সঠিক পূর্বাভাস) বা আরও বেশি ensemble member (uncertainty কমাতে) একই সময়ে চালায়। এটাই মূল উদাহরণ যা দিয়ে Gustafson তার ১৯৮৮-এর paper-এ লিখেছিলেন — তার নিজের team-এর hypercube সুপারকম্পিউটার প্রায় রৈখিক scaled speedup দেখাচ্ছিল, যা তৎকালীন Amdahl-নির্ভর pessimism-এর বিপরীত ছিল।

Multicore যুগ কেন Moore’s Law-এর সমাপ্তির উত্তর, কিন্তু পুরোপুরি নয়। Single-core clock speed ২০০৪-এর পর থেকে মূলত স্থির (power/thermal সীমার কারণে) — তাই আজকের কম্পিউটিং বৃদ্ধি মূলত core সংখ্যা বাড়িয়ে আসে। Amdahl’s Law বলছে এই পথে একটা মৌলিক সীমা আছে fixed কাজের জন্য — যা Gustafson-এর reframe-কে আজকের big-data/AI যুগে বিশেষভাবে প্রাসঙ্গিক করে তোলে: আমরা প্রায়ই “একই কাজ দ্রুত” চাই না, “বেশি ডেটা/বড় মডেল একই সময়ে” চাই।

যে ভুলগুলো সবাই করে

“N কোর মানেই সবসময় প্রায় N গুণ speedup।”

এই লেসনের কেন্দ্রীয় বিষয়। Amdahl’s Law অনুযায়ী speedup N-এর সাথে সাব-রৈখিকভাবে বাড়ে, আর একটা 1/(1-p) সিলিং-এ saturate করে — p \< 1 হলে (বাস্তবে প্রায় সবসময়ই, কারণ perfectly-parallel কোড বিরল)। p = 0.9-তে ৬৪ কোর ব্যবহার করলে ৬৪× নয়, মাত্র ৮.৭৭× পাওয়া যায়।

এমনকি experiment section দেখিয়েছে বাস্তব measured speedup প্রায়ই তাত্ত্বিক Amdahl মানের চেয়েও কম, কারণ সূত্রটা communication/synchronization overhead ধরে না।

“সিলিং-এ না পৌঁছানো পর্যন্ত, বেশি প্রসেসর যোগ করা সবসময় লাভজনক।”

Amdahl’s Law নিজেই একটা idealized upper bound — বাস্তবে overhead থাকে (process/thread spawn, communication, lock contention, memory bandwidth saturation)। এই overhead প্রায়ই N-এর সাথে বাড়ে (বেশি worker মানে বেশি coordination), তাই বাস্তব speedup curve একটা point-এর পরে সমতল হয়ে যেতে পারে, এমনকি নিচেও নামতে পারে — lesson ১৩-এর build exercise-এ ঠিক এটাই দেখা গেছে (হালকা কাজে parallel_reduce সিরিয়ালের চেয়ে ধীর হয়ে গিয়েছিল)।

বাস্তব প্রকৌশল প্রশ্ন কখনো “সিলিং কী” নয় — সবসময় “কোন N-এ marginal বেনিফিট আর marginal cost (হার্ডওয়্যার, বিদ্যুৎ, জটিলতা)-এর সমান হয়ে যাচ্ছে।”

“Amdahl's Law প্রমাণ করে parallel computing-এর একটা মৌলিক সীমা আছে, তাই সেটা বেশি দূর কাজে লাগবে না।”

এটা ঠিক সেই ভুল ধারণা যা Gustafson ১৯৮৮-এ challenge করেছিলেন। Amdahl’s Law শুধু fixed-size কাজের জন্য প্রযোজ্য pessimism তৈরি করে। বাস্তবে HPC, big data, আর AI-এর অধিকাংশ workload-এই সমস্যার আকার হার্ডওয়্যারের সাথে বাড়ে — বেশি ডেটা, বড় মডেল, finer simulation grid। সেই ক্ষেত্রে Gustafson’s Law-এর scaled speedup প্রায় রৈখিক, আর parallel computing-এর মূল্য অসীম বাস্তব, সিলিং-নির্ভর নয়।

সঠিক সিদ্ধান্ত-প্রক্রিয়া: আপনার সমস্যার আকার fixed থাকবে, নাকি হার্ডওয়্যারের সাথে বাড়বে — এই প্রশ্নের উত্তর অনুযায়ী সঠিক সূত্র বেছে নিন, একটাকে সার্বজনীন সত্য ধরে নেবেন না।

“Gustafson's Law Amdahl's Law-কে খণ্ডন/ভুল প্রমাণ করে।”

দুটো সূত্র একে অপরের সাথে contradict করে না — তারা ভিন্ন প্রশ্নের গাণিতিক উত্তর, ভিন্ন অনুমানের অধীনে (fixed-size বনাম scaled-size)। উভয়ই তাদের নিজস্ব অনুমানের অধীনে সম্পূর্ণ সঠিক, আর একই ডেটা থেকে (“N প্রসেসরে সমান্তরাল সময়ের ভগ্নাংশ p”) দুটো ভিন্ন, উভয়ই বৈধ, প্রশ্ন-নির্দিষ্ট উপসংহার বের করা যায় — এই লেসনের build exercise-এর টেবিলে যেমন পাশাপাশি দেখানো হয়েছে।

বুঝেছেন কি না দেখুন

p = 0.8 (৮০% সমান্তরাল), N = 4। Amdahl’s Law অনুযায়ী speedup কত?

স্মরণ

$\text{Speedup} = \frac{1}{(1-0.8) + 0.8/4} = \frac{1}{0.2 + 0.2} = \frac{1}{0.4} = 2.5\times$

সরল সংখ্যা দিয়ে যাচাই: 1-p = 0.2, p/N = 0.8/4 = 0.2 — দুটোই কাকতালীয়ভাবে সমান, যোগফল 0.4, তার reciprocal 2.5।

একই p = 0.8 প্রোগ্রামের জন্য, N → ∞-এ সর্বোচ্চ সম্ভাব্য speedup কত? প্রশ্ন ১-এর N=4-এর ফলাফলের সাথে তুলনা করুন।

প্রয়োগ

$\text{max speedup} = \frac{1}{1-p} = \frac{1}{1-0.8} = \frac{1}{0.2} = 5\times$

N=4-এ আমরা ইতিমধ্যে 2.5× পেয়েছি — যা সিলিং-এর ঠিক অর্ধেক। N-কে ৪ থেকে অসীম পর্যন্ত বাড়ালেও speedup মাত্র দ্বিগুণ হবে (2.5× থেকে 5×)। এটা দেখায় diminishing returns কত দ্রুত শুরু হয়ে যায় — N=4-ই ইতিমধ্যে সিলিং-এর একটা উল্লেখযোগ্য অংশ তুলে ফেলেছে।

একজন ডেভেলপার সোর্স কোড দেখে দাবি করছেন তাদের প্রোগ্রামের p = 0.99 (মাত্র ১% সিরিয়াল লুপ)। কিন্তু ৩২-কোরে measured speedup মাত্র ৮×, যেখানে Amdahl অনুযায়ী p=0.99, N=32-এ প্রায় ২৪.৩× হওয়ার কথা। এই বিশাল ফাঁকের সম্ভাব্য কারণ কী হতে পারে, আগের লেসনগুলোর জ্ঞান ব্যবহার করে ব্যাখ্যা করুন?

যুক্তি

সোর্স কোডে “সমান্তরাল দেখতে হওয়া” আর “কার্যকরভাবে সমান্তরাল হওয়া” ভিন্ন — hood section-এর মূল অন্তর্দৃষ্টি। সম্ভাব্য কারণ:

১. False sharing। যদি প্রতিটা thread তার নিজের ফলাফল একটা array-তে লেখে, আর সেই array-র element-গুলো একই cache line-এ পড়ে (যেমন একটা results[thread_id] array যেখানে প্রতিটা element মাত্র ৪ বাইট, একটা ৬৪-বাইট cache line-এ ১৬টা element আঁটে), তাহলে coherence protocol বারবার সেই line-কে core-এর মধ্যে ping-pong করাবে — কোডে কোনো explicit lock নেই, কিন্তু কার্যকর সিরিয়ালাইজেশন ঘটছে।

২. Lock contention একটা shared resource-এ। হয়তো প্রতিটা thread একটা shared logging system বা memory allocator ব্যবহার করছে যা internally lock ব্যবহার করে — সোর্স কোডে “সমান্তরাল loop”-এর ভেতরে এই lock দৃশ্যমান নাও হতে পারে (একটা library কলের ভেতরে লুকানো)।

৩. NUMA প্রভাব। ৩২ কোর সাধারণত একাধিক NUMA node জুড়ে থাকে। যদি shared data একটা node-এ বসানো থাকে, অন্য node-এর thread-দের access ধীর — এটা p-কে না কমিয়েও effective per-thread throughput কমিয়ে দেয়, যা measured speedup-এ Amdahl মডেলের বাইরে একটা অতিরিক্ত penalty যোগ করে।

৪. Memory bandwidth saturation। ৩২ কোর একই memory bus ভাগাভাগি করে — যদি কাজটা memory-bound হয় (compute-bound নয়), N কোর ব্যবহার করলেও সবাই একই bandwidth-এর জন্য প্রতিযোগিতা করবে, যা কার্যকর speedup-কে সিরিয়াল-ফ্র্যাকশন মডেলের বাইরেই সীমিত করে দেয়।

উপসংহার: measured speedup-এর ফাঁক দেখলে ধরে নেওয়া উচিত নয় যে p-এর হিসাব ভুল ছিল — বরং সন্দেহ করা উচিত hidden serialization (lock, false sharing) বা অতিরিক্ত resource contention (NUMA, bandwidth) যা Amdahl-এর সরল মডেলে ধরা পড়ে না।

একই p = 0.95, N = 32 নিয়ে Amdahl speedup আর Gustafson scaled speedup দুটোই হিসাব করুন। এত বড় পার্থক্যের কারণ এক বাক্যে বলুন।

প্রয়োগ

Amdahl: $\frac{1}{(1-0.95) + 0.95/32} = \frac{1}{0.05 + 0.0296875} = \frac{1}{0.0796875} \approx 12.55\times$

Gustafson: $(1-0.95) + 0.95 \times 32 = 0.05 + 30.4 = 30.45\times$

কারণ, এক বাক্যে: Amdahl জিজ্ঞেস করে “একই কাজ কত দ্রুত শেষ হয়” (সমান্তরাল অংশ ছোট হয়ে যায়, N বাড়ার সাথে সাথে তার প্রভাব কমতে থাকে), Gustafson জিজ্ঞেস করে “একই সময়ে কত বেশি কাজ হয়” (সমান্তরাল অংশ N-এর সাথে সরাসরি বাড়ে, কারণ কাজের আকারও বেড়েছে) — সম্পূর্ণ ভিন্ন হিসাব, তাই সংখ্যাও সম্পূর্ণ ভিন্ন।

N = 32 প্রসেসরে 20× speedup পেতে চান (Amdahl-এর অর্থে)। ন্যূনতম কত p দরকার?

প্রয়োগ

সূত্র উল্টে (build exercise-এ derive করা):

$p = \frac{1 - 1/\text{target}}{1 - 1/N} = \frac{1 - 1/20}{1 - 1/32} = \frac{0.95}{0.96875} \approx 0.98065$

অন্তত ৯৮.০৭% সমান্তরাল কোড দরকার — মাত্র ~২% সিরিয়াল কোডের বেশি সহ্য করা যাবে না।

যাচাই: 1-p = 0.01935, p/N = 0.98065/32 = 0.03065, যোগফল = 0.05 ঠিক, আর 1/0.05 = 20× — মিলেছে।

এই সংখ্যাটাই দেখায় কেন উচ্চ speedup পাওয়া এত কঠিন ব্যবহারিকভাবে — ৯৫% সমান্তরাল কোড (যা শুনতে চমৎকার) N=32-এ মাত্র ~12.55× দেয় (প্রশ্ন ৪), 20× পেতে আরও ~৩ শতাংশ বিন্দু বেশি সমান্তরালতা লাগে, যা বাস্তবে প্রায়ই সবচেয়ে কঠিন অংশ (সেই শেষ কয়েক শতাংশ সিরিয়াল কোড, যেমন logging, error handling, progress tracking, প্রায়ই দূর করা সবচেয়ে কঠিন)।

দুইটা পরিস্থিতি: (ক) একটা মোবাইল অ্যাপ একটা নির্দিষ্ট ৫০০ MB ভিডিও ফাইল যত দ্রুত সম্ভব কম্প্রেস করতে চায় একাধিক CPU কোর ব্যবহার করে। (খ) একটা জলবায়ু গবেষণা কেন্দ্র নতুন সুপারকম্পিউটার পেয়েছে, আগেরটার চেয়ে ৮× বেশি কোর সহ। কোন পরিস্থিতিতে Amdahl’s Law প্রাসঙ্গিক লেন্স, কোনটায় Gustafson’s Law, আর কেন?

ডিজাইন

(ক) মোবাইল ভিডিও কম্প্রেশন → Amdahl’s Law (strong scaling)।

কাজের আকার fixed — ৫০০ MB ফাইল, তার বেশি না কম না। ব্যবহারকারী চান এই নির্দিষ্ট কাজটা যত দ্রুত সম্ভব শেষ হোক। বেশি কোর ব্যবহার করলে একই কাজ দ্রুত শেষ হবে, কিন্তু encoder-এর সিরিয়াল অংশ (entropy coding, realworld section দ্রষ্টব্য) একটা সিলিং তৈরি করবে — ৮ কোর ব্যবহার করলেও ৮× দ্রুত হবে না। এখানে সঠিক প্রশ্ন: “আমার p কত, আর সেই সিলিং কী?”

(খ) জলবায়ু সিমুলেশন আপগ্রেড → Gustafson’s Law (weak scaling)।

এখানে স্বাভাবিক প্রশ্ন “আগের সিমুলেশন ৮× দ্রুত চালাব” নয় — বাস্তবে গবেষণা কেন্দ্র প্রায় সবসময় “একই সময়ে আরও নিখুঁত সিমুলেশন চালাব” বেছে নেয় (finer grid resolution, বেশি ensemble run, দীর্ঘ forecast window)। কাজের আকার হার্ডওয়্যারের সাথে বাড়ছে, wall-clock সময় প্রায় স্থির রাখা হচ্ছে — এটাই Gustafson-এর মূল দৃশ্যকল্প, আর সেখানে scaled speedup প্রায় রৈখিক (৮× কোর ≈ ৮× তথ্য/নিখুঁততা একই সময়ে)।

সাধারণ পার্থক্যকারী প্রশ্ন: “বেশি হার্ডওয়্যার পেলে আপনি একই কাজ দ্রুত শেষ করবেন, নাকি একই সময়ে বড় কাজ করবেন?” প্রথম উত্তরে Amdahl, দ্বিতীয়টায় Gustafson।

এরপর কী

আমরা এখন জানি কেন speedup-এর একটা গাণিতিক সিলিং আছে (Amdahl), আর কখন সেই সিলিং আসলে প্রাসঙ্গিক প্রশ্নই নয় (Gustafson)। কিন্তু এই পুরো বিশ্লেষণ একটা জিনিস ধরে নিয়েছে যা আমরা এখনও প্রশ্ন করিনি: একটা প্রোগ্রাম আসলে compute-bound নাকি memory-bound, আর তার theoretical peak performance আসলে কত।

Level ১১-এর বাকি লেসনগুলো (অন্য agent-রা সমান্তরালে লিখছেন) সেই প্রশ্নগুলোর দিকে যাবে — Roofline model (একটা program-এর performance তার arithmetic intensity আর hardware-এর compute/bandwidth সীমার সাপেক্ষে কোথায় পড়ে, সেটা visualize করার একটা কাঠামো), আর তারপর profiling ও benchmarking methodology — কীভাবে perf, flamegraph, আর PMU counter ব্যবহার করে সত্যিই বের করা যায় আপনার প্রোগ্রামের p কত, bottleneck কোথায়, আর measurement নিজেই কতটা বিশ্বাসযোগ্য। এই লেসনের তাত্ত্বিক সূত্রগুলো তখন হাতে-কলমে, বাস্তব সংখ্যায় রূপ নেবে।

Amdahl ও Gustafson-এর সূত্র — সমান্তরালতার সীমা

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

মূল ধারণা

Amdahl’s Law — সূত্র derive করা

সম্পূর্ণ টেবিল — বিভিন্ন `p`, বিভিন্ন `N`-এ

ভেতরে কী ঘটছে

আগের লেসনগুলো এখানে ফিরে আসে — `(1-p)` আসলে কোথা থেকে আসে

উদাহরণ

সম্পূর্ণ উদাহরণ — ছবি-প্রসেসিং পাইপলাইন

নিজে চালিয়ে দেখুন

তাত্ত্বিক বনাম বাস্তব speedup — overhead-সহ মাপা

নিজে বানান

Speedup Calculator — Amdahl বনাম Gustafson

ভেতরে কী ঘটছে

Gustafson’s Law — প্রশ্নটাই পাল্টে দেওয়া

সৎ রায় — কোনটাই “ভুল” নয়

বাস্তব সিস্টেমে

এই সূত্রগুলো যেখানে বাস্তব সিদ্ধান্ত নেয়

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী

এরপর কী

আরও পড়ুন

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

◔আগে এটা বুঝিWhy this matters

◆মূল ধারণাCore concept

Amdahl’s Law — সূত্র derive করা

সম্পূর্ণ টেবিল — বিভিন্ন p, বিভিন্ন N-এ

⚙ভেতরে কী ঘটছেUnder the hood

আগের লেসনগুলো এখানে ফিরে আসে — (1-p) আসলে কোথা থেকে আসে

▶উদাহরণExample

সম্পূর্ণ উদাহরণ — ছবি-প্রসেসিং পাইপলাইন

⌘নিজে চালিয়ে দেখুনExperiment

তাত্ত্বিক বনাম বাস্তব speedup — overhead-সহ মাপা

⚒নিজে বানানBuild it yourself

Speedup Calculator — Amdahl বনাম Gustafson

⚙ভেতরে কী ঘটছেUnder the hood

Gustafson’s Law — প্রশ্নটাই পাল্টে দেওয়া

সৎ রায় — কোনটাই “ভুল” নয়

◉বাস্তব সিস্টেমেReal-world usage

এই সূত্রগুলো যেখানে বাস্তব সিদ্ধান্ত নেয়

⚠যে ভুলগুলো সবাই করেMisconceptions

?বুঝেছেন কি না দেখুনCheck understanding

→এরপর কীNext step

এরপর কী

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

সম্পূর্ণ টেবিল — বিভিন্ন `p`, বিভিন্ন `N`-এ

ভেতরে কী ঘটছে

আগের লেসনগুলো এখানে ফিরে আসে — `(1-p)` আসলে কোথা থেকে আসে

উদাহরণ

নিজে চালিয়ে দেখুন

নিজে বানান

ভেতরে কী ঘটছে

বাস্তব সিস্টেমে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী