Ce este Legea lui Amdahl?
Formulata de Gene Amdahl in 1967, legea descrie limita fundamentala a paralelizarii.
Formula
S = 1 / ((1-P) + P/N)
P = partea paralelizabila, N = numarul de nuclee.
Exemplu
La 90% paralelizabil (P = 0.9):
- 2 nuclee: 1.82x accelerare
- 8 nuclee: 4.71x accelerare
- 64 nuclee: 8.19x accelerare
- Infinit: maxim 10x (limita!)
Chiar si cu infinitate nuclee, accelerarea maxima e 10x pentru ca 10% din cod e secvential.
Implicatii
Nu arunca pur si simplu mai multe procesoare la o problema. Identifica mai intai partea secventiala si optimizeaz-o. Legea lui Gustafson corecteaza pesimismul lui Amdahl: in practica, problemele cresc odata cu resursele.
Gustafson's Law — corecția pesimismului
John Gustafson a observat în 1988 că Amdahl presupunea dimensiunea problemei fixă. În realitate, când ai mai multe resurse, rezolvi probleme mai mari, nu aceeași problemă mai repede.
Legea lui Gustafson:
$$S = N - \alpha \cdot (N - 1)$$
unde $\alpha$ e partea secvențială și $N$ e numărul de nuclee. Spre deosebire de Amdahl, aici speedup-ul crește cu numărul de nuclee, chiar și când $\alpha > 0$.
Exemplu comparativ
| Nuclee | Amdahl (P=0.9) | Gustafson (α=0.1) | |---|---|---| | 8 | 4.71× | 7.3× | | 64 | 8.19× | 57.7× | | 1024 | 9.99× | 921.7× |
Diferența apare pentru că Amdahl fixează workload-ul, Gustafson îl scalează.
Aplicații practice
În arhitectura modernă
- GPU-urile exploatează Gustafson: mii de nuclee, probleme enorme (rendering, ML)
- MapReduce / Spark — workload-ul crește odată cu clusterul
- Amdahl domină acolo unde problema e fixă și trebuie optimizată latența (baze de date OLTP, sisteme real-time)
Strong vs Weak Scaling
| Tip | Scaling | Legea | Exemplu | |---|---|---|---| | Strong scaling | Problema fixă, cât de repede? | Amdahl | Simulare cu aceeași grilă pe mai multe nuclee | | Weak scaling | Problema crește cu resursele | Gustafson | Simulare cu grilă mai fină pe mai multe nuclee |
Limitări comune
Ambele legi ignoră:
- Overhead-ul de comunicare între nuclee
- Contenția pe memorie (coherence traffic, NUMA)
- Load imbalance — un nucleu poate aștepta după altul
- Costul de sincronizare (locks, bariere)
În practică, speedup-ul real e aproape întotdeauna sub predicția ambelor legi din cauza acestor factori. Vezi și articolul despre Memory Wall pentru limitările hardware reale.