Legge di Amdahl

L'aumento di velocità di un programma che usa più processori nell'informatica parallela è limitato dalla frazione sequenziale del programma. Per esempio, se metà del programma è sequenziale, l'aumento massimo teorico di velocità che si ottiene usando un sistema distribuito sarebbe 2 (1/(0.5+(1-0.5)/N)) quando N è grandissimo

La legge di Amdahl, che ha preso il nome del progettista di computer Gene Amdahl, viene usata per trovare il miglioramento atteso massimo in una architettura di calcolatori o in un sistema informatico quando vengono migliorate solo alcune parti del sistema^[1][2]. Nella sua forma più generale può essere espressa come^[3]:

"Il miglioramento delle prestazioni di un sistema che si può ottenere ottimizzando una certa parte del sistema è limitato dalla frazione di tempo in cui tale parte è effettivamente utilizzata"

che può essere ulteriormente semplificata nella pratica regola^[4]:

"Make the common case fast" (rendi veloce il caso più frequente)

Ad esempio: se per percorrere un tragitto si impiegano 10 minuti in automobile più 40 minuti a piedi, non ha molto senso acquistare un'automobile più veloce.

La legge di Amdahl viene usata spesso nell'informatica parallela per predire l'aumento massimo teorico di velocità che si ottiene usando più processori. Nell'ambito dei sistemi software può essere interpretata in modo più tecnico, ma il significato basilare è che l'algoritmo decide l'aumento di velocità, non il numero di processori. Prima o poi si raggiungerà un punto in cui non si potrà parallelizzare ulteriormente l'algoritmo^[5][6].

La legge di Amdahl è una dimostrazione della legge dei rendimenti decrescenti: anche se si potesse aumentare la velocità di una parte di un computer di cento o più volte, se tale parte influisce solamente sul 12% dell'elaborazione complessiva, al massimo l'accelerazione può essere di un fattore ${\displaystyle {\frac {1}{1-0.12}}=1.136}$.

Supponiamo che un'elaborazione abbia due parti indipendenti, A e B. B impiega circa il 25% del tempo dell'intero calcolo. Lavorando molto intensamente, si riesce a rendere questa parte 5 volte più veloce, ma ciò riduce di poco il tempo dell'intero calcolo. D'altra parte, può bastare meno lavoro per rendere la parte A veloce il doppio. Ciò renderà il calcolo molto più veloce che ottimizzando la parte B, anche se B è stato accelerato di più (5x contro 2x).

Più tecnicamente, la legge riguarda l'aumento di velocità ottenibile con un miglioramento a un'operazione che influisce per un P sul complesso e dove il miglioramento riduce il tempo di calcolo di un fattore S^[7]. (Per esempio, se il calcolo da migliorare influisce per il 30% del calcolo, P sarà 0.3; se il miglioramento raddoppia la velocità della porzione modificata, S sarà 2.)^[8][9]. La legge di Amdahl afferma che l'aumento di velocità complessivo prodotto dal miglioramento sarà^[5]

${\displaystyle {\frac {1}{(1-P)+{\frac {P}{S}}}}}$.

Per vedere come si arriva a questa formula, supponiamo che il tempo di esecuzione del vecchio calcolo sia 1, in una data unità di tempo. Il tempo di esecuzione del nuovo calcolo sarà il tempo impiegato per la frazione non migliorata (che è 1 − P) più il tempo impiegato dalla frazione migliorata. Il tempo impiegato dalla parte del calcolo migliorata è il tempo di esecuzione della parte non ancora migliorata diviso per il fattore di accelerazione, ossia P/S. L'aumento finale di velocità è calcolato dividendo il vecchio tempo di esecuzione per il nuovo tempo di esecuzione, ottenendo così la formula sopra indicata.

Un altro esempio. Abbiamo un compito scomponibile nelle seguenti quattro parti: P1 = 0,11 ossia 11%, P2 = 0,18 ossia 18%, P3 = 0,23 ossia 23%, P4 = 0,48 ossia 48%, aventi come somma 100%. Poi, non miglioriamo P1, perciò S1 = 1 ossia 100%, acceleriamo P2 di un fattore 5, perciò S2 = 5 ossia 500%, acceleriamo P3 di un fattore 20, perciò S3 = 20 ossia 2000%, e acceleriamo P4 di un fattore 1,6, perciò S4 = 1,6 ossia 160%. Usando la formula ${\displaystyle {\frac {P1}{S1}}+{\frac {P2}{S2}}+{\frac {P3}{S3}}+{\frac {P4}{S4}}}$, troviamo che il tempo di esecuzione è ${\displaystyle {{\frac {0,11}{1}}+{\frac {0,18}{5}}+{\frac {0,23}{20}}+{\frac {0,48}{1,6}}}=0,4575}$ ossia un po' meno della metà del tempo di esecuzione originale che sappiamo essere 1. Perciò l'accelerazione complessiva è ${\displaystyle {\frac {1}{0,4575}}=2,186}$, ossia, usando la formula ${\displaystyle {\frac {1}{{\frac {P1}{S1}}+{\frac {P2}{S2}}+{\frac {P3}{S3}}+{\frac {P4}{S4}}}}}$, poco più del doppio della velocità originale. Si noti come le accelerazioni 20x e 5x non hanno un grande effetto sull'accelerazione e sul tempo di esecuzione complessivi, dato che oltre la metà del compito viene accelerato solo di un fattore 1,6 o non viene accelerato affatto^[10][11].

Parallelismo

Nel caso speciale del parallelismo, la legge di Amdahl afferma che se F è la frazione di un calcolo che è parallelizzabile (cioè che può beneficiare dal parallelismo), e (1 − F) è la frazione che non può essere parallelizzata, allora l'aumento massimo di velocità che si può ottenere usando N processori è

${\displaystyle {\frac {1}{(1-F)+{\frac {F}{N}}}}}$.

Al limite, al tendere di N all'infinito, l'accelerazione tende a 1/(1-F). In pratica, il rapporto prestazioni/prezzo scende rapidamente al crescere di N, dato che F/N diventa piccolo rispetto a (1-F).

Per fare un esempio, se (1-F) è solamente il 10%, la velocità del calcolo può essere al massimo decuplicata, indipendentemente dal valore di N. Per questa ragione, il calcolo parallelo è utile solamente o per piccoli numeri di processori o per problemi con valori molto bassi di (1-F). Gran parte della ricerca sul calcolo parallelo consiste nel tentativo di ridurre (1-F) al valore più piccolo possibile^[12].

Note

1. David P. Rodgers, Improvements in multiprocessor system design, in ACM SIGARCH Computer Architecture News, vol. 13, n. 3, New York, NY, USA, ACM, giugno 1985, pp. 225–231 [p. 226], DOI:10.1145/327070.327215, ISBN 0-8186-0634-7, ISSN 0163-5964 (WC · ACNP).
2. Legge di Amdahl per i calcolatori elettronici, su Informatica e Ingegneria Online, 3 luglio 2017. URL consultato il 29 ottobre 2021.
3. fe.infn.it (PDF). URL consultato il 29 ottobre 2021 (archiviato dall'url originale il 29 ottobre 2021).
4. Legge di Amdahl, su it.freejournal.org. URL consultato il 29 ottobre 2021 (archiviato dall'url originale il 29 ottobre 2021).
5. Randal E. Bryant e O'Hallaron David, Computer Systems: A Programmer's Perspective, 3ª ed., Pearson Education, 2016, p. 58, ISBN 978-1-488-67207-1.
6. (EN) Computer Organization | Amdahl's law and its proof - GeeksforGeeks, in GeeksforGeeks, 11 giugno 2018. URL consultato il 29 ottobre 2021.
7. (EN) What is Amdahl's Law? - Definition from Techopedia, su Techopedia.com. URL consultato il 29 ottobre 2021.
8. (EN) Moore's and Amdahl's Law, su umsl.edu. URL consultato il 29 ottobre 2021.
9. (EN) 2.1: The Amdahl's law, su Workforce LibreTexts, 5 marzo 2021. URL consultato il 29 ottobre 2021.
10. http://tutorials.jenkov.com/java-concurrency/amdahls-law.html
11. Amdahl's Law - an overview | ScienceDirect Topics, su sciencedirect.com. URL consultato il 29 ottobre 2021.
12. Mark D. Hill e Michael R. Marty, Amdahl's Law in the Multicore Era, in Computer, vol. 41, n. 7, 2008, pp. 33–38, DOI:10.1109/MC.2008.209.

Altri progetti

Altri progetti

• Wikibooks
• Wikimedia Commons

• Wikibooks contiene testi o manuali sulla legge di Amdahl
• Wikimedia Commons contiene immagini o altri file sulla legge di Amdahl

Collegamenti esterni

• (EN) Denis Howe, Amdahl's Law, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL