Legge di Amdahl

La legge di Amdahl nomina il tetto che il lavoro seriale residuo impone all'accelerazione parallela. Se una frazione P di un programma può eseguire in modo concorrente e il resto deve restare sequenziale, aggiungere processori non moltiplica mai il tempo di esecuzione per N. L'accelerazione teorica è uno su uno meno P più P su N: il resto seriale resta al denominatore per quanto grande diventi N. Questo calcolatore della legge di Amdahl accetta la frazione parallelizzabile e il numero di processori, poi restituisce il fattore di accelerazione, la frazione seriale, l'efficienza parallela e il limite asintotico seriale uno su uno meno P ogni volta che rimane lavoro seriale. L'aritmetica è un'identità in forma chiusa, pienamente deterministica, senza simulazione e senza modello linguistico. Serve a dimensionare un cluster, confutare un'affermazione ingenua di N volte o verificare una curva di accelerazione da manuale prima di acquistare hardware.

Cosa misura la legge di Amdahl e come si ricava il fattore di accelerazione

La legge di Amdahl è l'osservazione di Gene Amdahl del 1967: il lavoro seriale rimasto limita quanto più veloce può diventare un programma intero, quanti processori si applichino alla parte parallela. Scriva P per la frazione del tempo di orologio di un singolo processore che può eseguire in modo concorrente, e N per il numero di processori. La frazione sequenziale è uno meno P.

Dopo aver diviso il lavoro parallelo in N parti, il tempo relativo diventa uno meno P più P su N, così l'accelerazione teorica S di N è il reciproco di quella somma: uno diviso per uno meno P più P su N. Quando P vale uno, ogni ciclo si parallelizza e l'accelerazione è uguale a N. Quando P vale zero, il lavoro è puramente seriale e l'accelerazione resta uno per ogni N.

Tra quegli estremi, l'accelerazione cresce con N ma si appiattisce verso il limite seriale uno su uno meno P. Quel tetto è il senso della legge: un programma che è solo il cinque per cento seriale non può mai superare un'accelerazione di venti volte, nemmeno su un milione di core, perché il cinque per cento seriale resta dopo che l'oceano parallelo è stato affettato all'infinito. L'efficienza parallela è l'accelerazione divisa per N; scende al crescere di N a meno che P non sia esattamente uno.

Questo calcolatore valuta quelle identità in modo diretto. Non è un profiler, né un simulatore a eventi discreti, né il modello di accelerazione scalata di Gustafson, che pone un'altra domanda facendo crescere il problema con la macchina. Se Lei conosce P da una misura o da una stima sul retro della busta che separa i loop caldi dalla preparazione, la formula di Amdahl dà l'accelerazione teorica da attendersi prima che effetti di cache, contesa di lock o traffico NUMA peggiorino la curva reale.

Dove un calcolatore della legge di Amdahl rende il proprio valore

Usi lo strumento del browser quando dimensiona un cluster, esamina un'affermazione di prestazione secondo cui l'accelerazione seguirà il numero di core, o guida una classe sul perché il novantacinque per cento parallelo si fermi comunque a venti volte. Incrementi N finché l'accelerazione si avvicina al limite seriale, poi smetta di acquistare core che non potrà sfruttare.

Confronti il risultato con la legge di Gustafson se il carico cresce con la macchina; Amdahl tiene fissa la dimensione del problema, che è il limite conservativo per lotti, compilatori e kernel scientifici che non si ingrandiscono per magia quando si aggiungono socket. I risultati sono pienamente deterministici: gli stessi P e N producono sempre lo stesso vettore di accelerazione, così può fissare esempi in test e materiali didattici. Non c'è modello linguistico, né servizio esterno di profiling, né casualità.