Amdahlov zakon

V računalniški arhitekturi je Amdahlov zakon (ali Amdahlov argument^[1]) formula, ki podaja teoretično pospešitev latence izvajanja naloge pri fiksni delovni obremenitvi, ki se lahko pričakuje od sistema, katerega viri so izboljšani.

Zakon se običajno navaja v obliki izjave:

"Splošno izboljšanje zmogljivosti, pridobljeno z optimizacijo posameznega dela sistema, je omejeno z deležem časa, ko se izboljšani del dejansko uporablja".^[2]

Imenuje se po računalniškem znanstveniku Genu Amdahlu in je bil predstavljen na spomladanski skupni računalniški konferenci Ameriške zveze društev za obdelavo informacij (AFIPS) leta 1967.

Amdahlov zakon se pogosto uporablja pri vzporednem računanju za napovedovanje teoretične pospešitve pri uporabi več procesorjev. Na primer, če program potrebuje 20 ur za dokončanje z uporabo ene same niti in enournega dela programa ni mogoče vzporediti, potem je mogoče vzporediti le preostalih 19 ur ( p = 0.95 ) časa izvajanja. Zato je ne glede na to, koliko niti je namenjenih vzporednemu izvajanju tega programa, minimalni čas izvajanja vedno daljši od 1 ure. Zato je teoretično pospešitev največ 20-kratna zmogljivost ene niti, $\left({\dfrac {1}{1-p}}=20\right)$ .

Amdahlov zakon ni omejen samo na računalništvo. Pojavlja se tudi pri transportu, organizaciji proizvodnje in še kje. Na primer, vsi vemo, da pri potovanju povečanje hitrosti letala ni bistveno, če letalo potrebuje za let 30 minut, prevoz na letališče in z njega pa traja 2 uri.

Definicija

Amdahlov zakon lahko formuliramo na naslednji način:^[3]

S_{\text{latenca}}(s)={\frac {1}{(1-p)+{\frac {p}{s}}}}

kjer je

S _latenca teoretična pospešitev izvedbe celotne naloge;
s je pospešitev dela naloge, ki ima koristi od izboljšanih sistemskih virov;
p je delež časa izvajanja, ki ga je prvotno zasedel del, ki ima koristi od izboljšanih virov.

Poleg tega

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

kaže, da se teoretična pohitritev izvedbe celotne naloge povečuje z izboljšavo virov sistema in da je ne glede na velikost izboljšave teoretična pohitritev vedno omejena z delom naloge, ki ne more imeti koristi od izboljšave.

Amdahlov zakon velja samo za primere, kjer je velikost problema fiksna. V praksi, ko je na voljo več računalniških virov, se običajno uporabljajo za večje probleme (večji nabori podatkov), čas, porabljen v delu, ki ga je mogoče vzporediti, pa pogosto raste veliko hitreje kot inherentno serijsko delo. V tem primeru daje Gustafsonov zakon manj pesimistično in bolj realistično oceno vzporedne uspešnosti.^[4]

Sklici

↑ Rodgers, David P. (Junij 1985). »Improvements in multiprocessor system design«. ACM SIGARCH Computer Architecture News. New York: ACM. 13 (3): 225–231 [p. 226]. doi:10.1145/327070.327215. ISBN 0-8186-0634-7. ISSN 0163-5964.
↑ Reddy, Martin (2011). API Design for C++. Burlington (MA): Morgan Kaufmann Publishers. str. 210. doi:10.1016/C2010-0-65832-9. ISBN 978-0-12-385003-4. LCCN 2010039601. OCLC 666246330.
↑ Bryant, Randal E.; David, O'Hallaron (2016), Computer Systems: A Programmer's Perspective (3 izd.), Pearson Education, str. 58, ISBN 978-1-488-67207-1
↑ McCool, Michael; Reinders, James; Robison, Arch (2013). Structured Parallel Programming: Patterns for Efficient Computation. Elsevier. str. 61. ISBN 978-0-12-415993-8.

[1] Rodgers, David P. (Junij 1985). »Improvements in multiprocessor system design«. ACM SIGARCH Computer Architecture News. New York: ACM. 13 (3): 225–231 [p. 226]. doi:10.1145/327070.327215. ISBN 0-8186-0634-7. ISSN 0163-5964.

[2] Reddy, Martin (2011). API Design for C++. Burlington (MA): Morgan Kaufmann Publishers. str. 210. doi:10.1016/C2010-0-65832-9. ISBN 978-0-12-385003-4. LCCN 2010039601. OCLC 666246330.

[3] Bryant, Randal E.; David, O'Hallaron (2016), Computer Systems: A Programmer's Perspective (3 izd.), Pearson Education, str. 58, ISBN 978-1-488-67207-1

[4] McCool, Michael; Reinders, James; Robison, Arch (2013). Structured Parallel Programming: Patterns for Efficient Computation. Elsevier. str. 61. ISBN 978-0-12-415993-8.

[1]

[2]

[3]

[4]