Llei d'Amdahl

Una representació gràfica de la llei d'Amdahl. L'augment de velocitat d'execució d'un programa per paral·lelització està limitat per la mesura en què el programa es pot paral·lelitzar. Per exemple, si el 90% del programa es pot paral·lelitzar, el màxim augment teòric de velocitat fent servir paral·lelisme seria 10x, no importa que la quantitat de processadors que es facin servir creixi molt.

La llei d'Amdahl, anomenada així en honor de l'enginyer d'ordinadors Gen Amdahl, s'utilitza per trobar la màxima millora esperada del sistema total quan solament part del sistema és millorada. Sovint s'utilitza un càlcul paral·lel per predir la màxima acceleració teòrica utilitzant múltiples processadors.

La llei d'Amdahl pot ser interpretada més tècnicament, però en termes simples significa que és l'algorisme qui decideix l'acceleració, no el nombre de processadors. Finalment, arribes a un lloc on no pots paral·lelitzar més l'algorisme.

Aquesta llei és una demostració de la llei de disminució de tornades: mentre un podria accelerar part de l'ordinador unes cent vegades o més, si la millora solament afecta el 12% del total de la tasca, la millor acceleració possiblement seria ${\frac {1}{1-0.12}}=1.136$ vegades més ràpida.

Més tècnicament, la llei es veu afectada amb l'acceleració assolible des d'una millora al càlcul que influeix una proporció P d'aquell càlcul on la millora té una acceleració de S. (Per exemple, si una millora pot accelerar una porció del 30% del total d'un càlcul, P seria 0.3; si la millora fa 2 cops més ràpida la porció afectada, S seria 2). La llei Amdahl declara que l'acceleració total d'aplicar la millora serà: ${\frac {1}{(1-P)+{\frac {P}{S}}}}$.

Per veure com va ser derivada aquesta fórmula, assumeix que el temps transcorregut del càlcul vell era 1, per alguna unitat de temps. El temps transcorregut del nou càlcul serà la duració de temps presa de la fracció no millorada (la qual és 1 – P) més la duració de temps pres de la fracció millorada. La duració de temps per a la part millorada del càlcul és la duració de l'anterior temps transcorregut de la part millorada dividit per l'acceleració, fent la duració de temps de la part millorada P/S. L'acceleració final és calculada per la divisió de l'antic temps transcorregut entre el nou temps, que és el que calcula la fórmula de dalt.

Aquí tenim un altre exemple. Donem una tasca que es divideix en quatre parts: P1 = 11 o \d1%, P2 = 18 o \d8%, P3 = 23 o \d3%, P4 = 48 o \d8%, lo qual suma 100%. Llavors diem que P1 no s'accelera, així S1 = 1 o \d00%, P2 s'accelera per 5x, així S2 = 5 o \d00%, P3 s'accelera per 20x ó 2000%, i P4 s'accelera 1.6x ó 160%.

Utilitzant la fórmula ${\frac {P1}{S1}}+{\frac {P2}{S2}}+{\frac {P3}{S3}}+{\frac {P4}{S4}}$,trobem que el temps transcorregut és ${{\frac {.11}{1}}+{\frac {.18}{5}}+{\frac {.23}{20}}+{\frac {.48}{1.6}}}=.4575$ ó una mica menys que ½ del temps original transcorregut que es coneix com a 1. Per tant, l'estímul total de velocitat és: ${\frac {1}{.4575}}=2.186$ ó un mica més que el doble de l'acceleració original utilitzant la fórmula ${\frac {1}{{\frac {P1}{S1}}+{\frac {P2}{S2}}+{\frac {P3}{S3}}+{\frac {P4}{S4}}}}$. Cal fixar-se en com l'acceleració de 20x i 5x no té gaire efecte sobre l'augment total d'acceleració i la disminució del temps total transcorregut quan més de la meitat de la tasca és accelerada només 1x (és a dir, no s'accelera) o 1.6x.

Paral·lelització

En el cas especial de paral·lelització, la llei d'Amdahl declara que si F és la fracció d'un càlcul seqüencial i (1 – F) és la fracció que pot ser paral·lelitzada, llavors la màxima acceleració que pot assolir utilitzant N processadors és: ${\frac {1}{F+(1-F)/N}}$.

Al límit, com N tendeix a infinit, la màxima acceleració tendeix a 1/F. A la pràctica, la relació preu/rendiment cau ràpidament quan N augmenta un cop (1 – F)/ N és petita en comparació amb F.

Per exemple, si F és solament 10%, el problema pot ser accelerat solament per un factor de 10 com a màxim, no importa el gran que sigui el valor utilitzat de N. Per aquesta raó, el càlcul paral·lel solament s'utilitza per qualsevol nombre petit de processadors, o problemes amb baixos valors de F. Una gran part de la feina de la programació paral·lela consisteix en l'intent de reduir F al valor més petit possible.

Regla general d'Amdahl

Diu que 1 byte de memòria i 1 byte per segon d'I/O és necessari per a cada instrucció per segon admesa per un ordinador.

Referències

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Llei d'Amdahl

• Gene Amdahl, "Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities", AFIPS Conference Proceedings, (30), pp. 483-485, 1967.

Vegeu també

• Regla del noranta-nou
• Llei de Gustafson
• Llei de Brooks
• Llei de Moore