La legge di Amdahl - Amdahl's law

L'accelerazione teorica della latenza di esecuzione di un programma in funzione del numero di processori che lo eseguono, secondo la legge di Amdahl. L'accelerazione è limitata dalla parte seriale del programma. Ad esempio, se il 95% del programma può essere parallelizzato, la velocità massima teorica utilizzando il calcolo parallelo sarebbe 20 volte.

Nell'architettura dei computer , la legge di Amdahl (o l'argomentazione di Amdahl ) è una formula che fornisce l' accelerazione teorica in latenza dell'esecuzione di un compito a carico di lavoro fisso che ci si può aspettare da un sistema le cui risorse sono migliorate. Prende il nome dallo scienziato informatico Gene Amdahl ed è stato presentato all'AFIPS Spring Joint Computer Conference nel 1967.

La legge di Amdahl viene spesso utilizzata nel calcolo parallelo per prevedere l'accelerazione teorica quando si utilizzano più processori. Ad esempio, se un programma richiede 20 ore per essere completato utilizzando un singolo thread, ma non è possibile parallelizzare una parte del programma di un'ora, quindi è possibile parallelizzare solo le restanti 19 ore ( p = 0,95 ) di tempo di esecuzione, quindi indipendentemente da quanti thread sono dedicati all'esecuzione parallela di questo programma, il tempo minimo di esecuzione non può essere inferiore a un'ora. Quindi, l'accelerazione teorica è limitata a un massimo di 20 volte le prestazioni del singolo thread, . ${\displaystyle \left({\dfrac {1}{1-p}}=20\right)}$

Definizione

La legge di Amdahl può essere formulata nel modo seguente:

${\displaystyle S_{\text{latency}}(s)={\frac {1}{(1-p)+{\frac {p}{s}}}}}$

dove

• La _latenza S è l'accelerazione teorica dell'esecuzione dell'intera attività;
• s è l'accelerazione della parte del compito che beneficia di migliori risorse di sistema;
• p è la proporzione del tempo di esecuzione che la parte che beneficiava di risorse migliorate occupava originariamente.

Per di più,

${\displaystyle {\begin{cases}S_{\text{latency}}(s)\leq {\dfrac {1}{1-p}}\\[8pt]\lim \limits _{s\to \infty }S_{\text{latency}}(s)={\dfrac {1}{1-p}}.\end{casi}}}$

mostra che la velocità teorica dell'esecuzione dell'intero compito aumenta con il miglioramento delle risorse del sistema e che, indipendentemente dall'entità del miglioramento, la velocità teorica è sempre limitata dalla parte del compito che non può beneficiare del miglioramento .

La legge di Amdahl si applica solo ai casi in cui la dimensione del problema è stata risolta. In pratica, man mano che diventano disponibili più risorse di calcolo, tendono ad essere utilizzate su problemi più grandi (set di dati più grandi) e il tempo trascorso nella parte parallelizzabile spesso cresce molto più velocemente del lavoro intrinsecamente seriale. In questo caso, la legge di Gustafson fornisce una valutazione meno pessimistica e più realistica della performance parallela.

Derivazione

Un'attività eseguita da un sistema le cui risorse sono migliorate rispetto a un sistema simile iniziale può essere suddivisa in due parti:

• una parte che non beneficia del miglioramento delle risorse del sistema;
• una parte che beneficia del miglioramento delle risorse del sistema.

Un esempio è un programma per computer che elabora i file dal disco. Una parte di quel programma può scansionare la directory del disco e creare un elenco di file internamente in memoria. Successivamente, un'altra parte del programma passa ogni file a un thread separato per l'elaborazione. La parte che esegue la scansione della directory e crea l'elenco dei file non può essere accelerata su un computer parallelo, ma la parte che elabora i file può.

Il tempo di esecuzione dell'intero compito prima del miglioramento delle risorse del sistema è indicato come . Comprende il tempo di esecuzione della parte che non trarrebbe beneficio dal miglioramento delle risorse e il tempo di esecuzione di quella che ne trarrebbe beneficio. La frazione del tempo di esecuzione dell'attività che beneficerebbe del miglioramento delle risorse è indicata con . Quella relativa alla parte che non ne trarrebbe beneficio è quindi . Quindi: ${\displaystyle T}$${\displaystyle p}$${\displaystyle 1-p}$

${\displaystyle T=(1-p)T+pT.}$

È l'esecuzione della parte che beneficia del miglioramento delle risorse che viene accelerata dal fattore dopo il miglioramento delle risorse. Di conseguenza, il tempo di esecuzione della parte che non ne beneficia rimane lo stesso, mentre la parte che ne beneficia diventa: ${\displaystyle}$

${\displaystyle {\frac {p}{s}}T.}$

Il tempo teorico di esecuzione dell'intera attività dopo il miglioramento delle risorse è quindi: ${\displaystyle T(s)}$

${\displaystyle T(s)=(1-p)T+{\frac {p}{s}}T.}$

La legge di Amdahl fornisce l' accelerazione teorica in latenza dell'esecuzione dell'intera attività a carico di lavoro fisso${\displaystyle W}$ , che produce

${\displaystyle S_{\text{latency}}(s)={\frac {TW}{T(s)W}}={\frac {T}{T(s)}}={\frac {1} {1-p+{\frac {p}{s}}}}.}$

Programmi paralleli

Se il 30% del tempo di esecuzione può essere oggetto di un aumento di velocità, p sarà 0,3; se il miglioramento rende la parte interessata due volte più veloce, s sarà 2. La legge di Amdahl afferma che l'accelerazione complessiva dell'applicazione del miglioramento sarà:

${\displaystyle S_{\text{latency}}={\frac {1}{1-p+{\frac {p}{s}}}}={\frac {1}{1-0.3+{\frac { 0,3}{2}}}}=1,18.}$

Ad esempio, supponiamo che ci venga assegnato un compito seriale suddiviso in quattro parti consecutive, le cui percentuali di tempo di esecuzione sono rispettivamente p 1 = 0,11 , p 2 = 0,18 , p 3 = 0,23 e p 4 = 0,48 . Quindi ci viene detto che la 1a parte non è accelerata, quindi s 1 = 1 , mentre la 2a parte viene accelerata 5 volte, quindi s 2 = 5 , la 3a parte viene accelerata 20 volte, quindi s 3 = 20 , e la quarta parte viene accelerata di 1,6 volte, quindi s 4 = 1,6 . Usando la legge di Amdahl, l'accelerazione complessiva è

${\displaystyle S_{\text{latency}}={\frac {1}{{\frac {p1}{s1}}+{\frac {p2}{s2}}+{\frac {p3}{s3} }+{\frac {p4}{s4}}}}={\frac {1}{{\frac {0.11}{1}}+{\frac {0.18}{5}}+{\frac {0.23} {20}}+{\frac {0.48}{1.6}}}}=2.19.}$

Notare come l'accelerazione di 5 e 20 volte sulla seconda e terza parte, rispettivamente, non abbia molto effetto sull'accelerazione complessiva quando la quarta parte (48% del tempo di esecuzione) viene accelerata solo di 1,6 volte.

Programmi seriali

Supponiamo che un compito abbia due parti indipendenti, A e B . La parte B richiede circa il 25% del tempo dell'intero calcolo. Lavorando molto duramente, si potrebbe essere in grado di rendere questa parte 5 volte più veloce, ma questo riduce solo leggermente il tempo dell'intero calcolo. Al contrario, potrebbe essere necessario eseguire meno lavoro per far funzionare la parte A due volte più velocemente. Ciò renderà il calcolo molto più veloce rispetto all'ottimizzazione della parte B , anche se l' accelerazione della parte B è maggiore in termini di rapporto (5 volte contro 2 volte).

Ad esempio, con un programma seriale in due parti A e B per cui T _A = 3 s e T _B = 1 s ,

• se la parte B viene fatta funzionare 5 volte più velocemente, cioè s = 5 e p = T _B /( T _A + T _B ) = 0,25 , allora

${\displaystyle S_{\text{latency}}={\frac {1}{1-0,25+{\frac {0.25}{5}}}}=1,25;}$

• se la parte A viene fatta correre 2 volte più velocemente, cioè s = 2 e p = T _A /( T _A + T _B ) = 0,75 , allora

${\displaystyle S_{\text{latency}}={\frac {1}{1-0,75+{\frac {0,75}{2}}}}=1,60.}$

Pertanto, far funzionare la parte A 2 volte più velocemente è meglio che far funzionare la parte B 5 volte più velocemente. Il miglioramento percentuale della velocità può essere calcolato come

${\displaystyle {\text{miglioramento percentuale}}=100\left(1-{\frac {1}{S_{\text{latenza}}}}\right).}$

• Migliorare la parte A di un fattore 2 aumenterà la velocità complessiva del programma di un fattore di 1,60, il che lo rende del 37,5% più veloce del calcolo originale.
• Tuttavia, migliorando la parte B di un fattore 5, che presumibilmente richiede uno sforzo maggiore, si otterrà un fattore di accelerazione complessivo di solo 1,25, che lo rende il 20% più veloce.

Ottimizzazione della parte sequenziale dei programmi paralleli

Se la parte non parallelizzabile è ottimizzata di un fattore , allora ${\displaystyle O}$

${\displaystyle T(O,s)=(1-p){\frac {T}{O}}+{\frac {p}{s}}T.}$

Dalla legge di Amdahl segue che l'accelerazione dovuta al parallelismo è data da

${\displaystyle S_{\text{latenza}}(O,s)={\frac {T(O)}{T(O,s)}}={\frac {(1-p){\frac {1 }{O}}+{p}}{{\frac {1-p}{O}}+{\frac {p}{s}}}}.}$

Quando , abbiamo , a significare che l'accelerazione viene misurata rispetto al tempo di esecuzione dopo che la parte non parallelizzabile è stata ottimizzata. ${\displaystyle s=1}$${\displaystyle S_{\text{latenza}}(O,s)=1}$

quando , ${\displaystyle s=\infty}$

${\displaystyle S_{\text{latenza}}(O,\infty)={\frac {T(O)}{T(O,s)}}={\frac {(1-p){\frac { 1}{O}}+{p}}{{\frac {1-p}{O}}+{\frac {p}{s}}}}=1+{\frac {p}{1-p }}O.}$

Se , e , allora: ${\displaystyle 1-p=0.4}$${\displaystyle O=2}$${\displaystyle s=5}$

${\displaystyle S_{\text{latency}}(O,s)={\frac {T(O)}{T(O,s)}}={\frac {{0.4}{\frac {1}{ 2}}+0.6}{{\frac {0.4}{2}}+{\frac {0.6}{5}}}}=2.5.}$

Trasformare parti sequenziali di programmi paralleli in parallelizzabili

Successivamente, consideriamo il caso in cui la parte non parallelizzabile viene ridotta di un fattore , e la parte parallelizzabile viene corrispondentemente aumentata. Quindi ${\displaystyle O'}$

${\displaystyle T'(O',s)={\frac {1-p}{O'}}T+\left(1-{\frac {1-p}{O'}}\right){\frac {T}{s}}.}$

Dalla legge di Amdahl segue che l'accelerazione dovuta al parallelismo è data da

${\displaystyle S'_{\text{latency}}(O',s)={\frac {T'(O')}{T'(O',s)}}={\frac {1}{ {\frac {1-p}{O'}}+\left(1-{\frac {1-p}{O'}}\right){\frac {1}{s}}}}.}$

La derivazione di cui sopra è in accordo con l'analisi di Jakob Jenkov del compromesso tra tempo di esecuzione e accelerazione.

Relazione con la legge dei rendimenti decrescenti

La legge di Amdahl è spesso confusa con la legge dei rendimenti decrescenti , mentre solo un caso speciale di applicazione della legge di Amdahl dimostra la legge dei rendimenti decrescenti. Se si sceglie in modo ottimale (in termini di velocità raggiunta) ciò che deve essere migliorato, si vedranno miglioramenti monotona decrescenti man mano che si migliora. Se, tuttavia, si sceglie in modo non ottimale, dopo aver migliorato un componente non ottimale e si è passati a migliorare un componente più ottimale, si può notare un aumento del rendimento. Si noti che spesso è razionale migliorare un sistema in un ordine "non ottimale" in questo senso, dato che alcuni miglioramenti sono più difficili o richiedono tempi di sviluppo maggiori di altri.

La legge di Amdahl rappresenta la legge dei rendimenti decrescenti se, considerando il tipo di rendimento che si ottiene aggiungendo più processori a una macchina, se si esegue un calcolo a dimensione fissa che utilizzerà tutti i processori disponibili alla propria capacità. Ogni nuovo processore aggiunto al sistema aggiungerà meno potenza utilizzabile rispetto a quello precedente. Ogni volta che si raddoppia il numero di processori, il rapporto di accelerazione diminuirà, poiché il throughput totale si dirige verso il limite di 1/(1 −  p ).

Questa analisi trascura altri potenziali colli di bottiglia come la larghezza di banda della memoria e la larghezza di banda di I/O. Se queste risorse non scalano con il numero di processori, la semplice aggiunta di processori fornisce rendimenti ancora inferiori.

Un'implicazione della legge di Amdahl è che per velocizzare le applicazioni reali che hanno porzioni sia seriali che parallele, sono necessarie tecniche di calcolo eterogenee .

Guarda anche

• La legge di Gustavson
• Metodo del percorso critico
• La legge di Moore

Riferimenti

Ulteriori letture

• Amdahl, Gene M. (1967). "Validità dell'approccio del singolo processore per ottenere capacità di elaborazione su larga scala" (PDF) . Atti della conferenza AFIPS (30): 483-485. doi : 10.1145/1465482.1465560 .

link esterno

• "Programmazione parallela: quando la legge di Amdahl è inapplicabile?" . 2011-06-25. Archiviato dall'originale il 14/04/2013 . Estratto il 26/06/2011 .
• Gene M. Amdahl (1989), Intervista di storia orale con Gene M. Amdahl , Charles Babbage Institute , Università del Minnesota, hdl : 11299/104341. Amdahl discute il suo lavoro di laurea presso l'Università del Wisconsin e il suo progetto di WISC . Discute il suo ruolo nella progettazione di diversi computer per IBM tra cui STRETCH , IBM 701 e IBM 704 . Discute il suo lavoro con Nathaniel Rochester e la gestione del processo di progettazione di IBM. Le menzioni lavorano con Ramo-Wooldridge , Aeronutronic e Computer Sciences Corporation
• Legge di Amdahl: non tutti i miglioramenti delle prestazioni sono uguali (2007)
• "Legge di Amdahl" di Joel F. Klein, Wolfram Demonstrations Project (2007)
• La legge di Amdahl nell'era multicore (luglio 2008)
• Che $#@! è Parallelismo, comunque? (Charles Leiserson, maggio 2008)
• Valutazione della funzione Intel Core i7 Turbo Boost , di James Charles, Preet Jassi, Ananth Narayan S, Abbas Sadat e Alexandra Fedorova (2009)
• Calcolo dell'accelerazione di programmi paralleli in funzione del numero di thread , di George Popov, Valeri Mladenov e Nikos Mastorakis (gennaio 2010)
• Danny Hillis - Dimostrare che la legge di Amdahl è sbagliata, video registrato nell'ottobre 2016