Amdahl's law

Amdahl's law adalah prinsip fundamental dalam ilmu komputer yang menjelaskan batas teoritis peningkatan performa ketika kita melakukan parallelisasi suatu program atau sistem. Dicetuskan oleh Gene Amdahl pada tahun 1967, hukum ini jadi patokan penting dalam desain sistem paralel dan multicore.

Ide Dasar

Misal kita punya program yang butuh 100 detik untuk selesai. Jika kita menambah lebih banyak prosesor, apakah programnya bakal 2x lebih cepat kalau prosesornya 2x? Jawabannya: tidak pernah sebanding, karena selalu ada bagian dari program yang tidak bisa diparallelkan (harus berjalan secara serial/berurutan).

Formula

$S (n) = \frac{1}{(1 - p) + \frac{p}{n}}$

Di mana:

$S (n)$ = speedup teoritis maksimum
$p$ = proporsi program yang bisa diparallelkan (0 sampai 1)
$n$ = jumlah prosesor
$(1 - p)$ = proporsi yang harus tetap serial

Contoh: Misal kita punya program yang memiliki persentase parallel yaitu 20% (P = 0.2), dan kita punya 5 prosesor (N = 5):
$\frac{1}{(1 - 0.2) + \frac{0.2}{5}} = 1.19$

Artinya, meski kita punya 5 prosesor, programnya cuma 19% lebih cepat. Kenapa? Karena 80% program harus tetap berjalan serial - keempat prosesor lainnya nganggur menunggu bagian serial itu selesai.

Cara hitung ceiling

Ceiling (atau batas atas) adalah nilai maksimum speedup yang secara teoritis tidak akan pernah bisa dilampaui, tidak peduli berapa banyak prosesor yang kita tambahkan. Asalnya dari rumus Amdahl ketika N dibuat tak terhingga (N → ∞): $S_{m a x} = \frac{1}{(1 - p) + \frac{p}{\infty}} = \frac{1}{(1 - p) + 0} = \frac{1}{1 - p}$

Suku $\frac{p}{N}$ mengecil mendekati nol saat N sangat besar, sehingga yang tersisa hanya bagian serialnya saja. Dengan P = 0.2:

$S_{m a x} = \frac{1}{1 - 0.2} = \frac{1}{0.8} = 1.25 \times$

Maka mau berapun prosesor pasti akan mentok di maximal 25%

Diminishing Returns

Ini adalah inti dari Amdahl's law. Semakin banyak prosesor yang ditambah, semakin kecil manfaat tambahan yang didapat: Kalau 5% program tidak bisa diparallelkan, batas speedup maksimum hanyalah 20x - tidak peduli kita pakai 1.000 atau 1.000.000 prosesor. Menambah prosesor dari 1 → 2 memberi keuntungan terbesar. Menambah dari 1.000 → 1.001 hampir tidak terasa bedanya.