Amdalov zakon

Ubrzanje programa, koji koristi više procesora u paralelnoj obradi, je ograničeno sekvencijalnim razlomkom programa. Na primer, ako 95% programa može biti paralelizovano, teoretski maksimalno ubrzanje, korišćenjem paralelne obrade, bi bilo 20 puta veće nego na dijagramu, bez obzira na to koliko se procesora koristi.

Amdalov zakon, još poznat kao i Amdalov argument, se koristi da se pronađe maksimalno očekivano poboljšanje sveukupnog sistema, kada se poboljša samo jedan deo sistema. Često se koristi u paralelnoj obradi da bi se predvideo teoretski maksimalno ubrzanje pri korišćenju više procesora. Zakon je dobio ime po računarskom arhitekti Džȋnu Amdalu (Gene Amdahl). Zakon je predstavljen u američkoj federaciji društva za obrađivanje podataka (engl. American Federation of Information Processing Societies, AFIPS) na „Spring Joint“ računarskoj konferenciji 1967.

Ubrzanje programa, koji koristi više procesora u paralelnom okruženju, je ograničen vremenom koje je potrebno da se obradi sekvencijalni deo programa. Na primer, ako je programu potrebno 20 sati korišćenja jednog jezgra, i ako se određeni deo programa (kome treba sat vremena da se izvrši) ne može paralelizovati, dok se ostalih 95% (19 sati) može paralelizovati, onda, bez obzira na to koliko je procesora posvećeno paralelnom izvršavanju programa, minimalno vreme izvršavanje ne može biti manje od jednog sata. Odatle je ubrzanje ograničeno na najviše 20 puta veće.

Definicija

Dato nam je:

• $n\in \mathbb {N}$, broj niti izvršavanja
• $B\in [0,1]$, deo algoritma koji je strogo serijalan

Vreme $T\left(n\right)$, koje je potrebno nekom algoritmu da se završi kada se izvršava na $n$ niti, odgovara:

$T(n)=T(1)\left(B+{\frac {1}{n}}\left(1-B\right)\right)$

Dakle, teoretsko ubrzanje koje se može dobiti izvršavanjem algoritma na sistemu koji je sposoban da izvrši $n$ niti je:

$S(n)={\frac {T\left(1\right)}{T\left(n\right)}}={\frac {T\left(1\right)}{T\left(1\right)\left(B+{\frac {1}{n}}\left(1-B\right)\right)}}={\frac {1}{B+{\frac {1}{n}}\left(1-B\right)}}$

Opis

Amdalov zakon je model za vezu između očekivanog ubrzanja paralelne implementacije nekog algoritma i algoritma koji se izvršava serijalno, pod pretpostavkom da veličina problema ostaje ista pri paralelizaciji. Na primer, ako za jedan problem, algoritam paralelno implementiran radi 12% operacija proizvoljnom brzinom (dok ostalih 88% operacija nije paralelizovano), Amdalov zakon tvrdi da je maksimalno ubrzanje paralelizovanog algoritma 1/(1 – 0.12) = 1.136 puta veće od algoritma koji nije paralelno impplementiran.

Tehnički, zakon se bavi ubrzanjem koje se ostvaruje od poboljšanja do izračunavanja koje utiče na razmeru P tog izračunavanja gde poboljšanje ima ubrzanje S. Na primer, ako 30% izračunavanja može biti predmet ubrzanja, P će biti 0,3. Ako poboljšanje učini pogođeni deo duplo bržim, S će biti 2. Amdalov zakon tvrdi da će ukupno ubrzanje biti:

${\frac {1}{(1-P)+{\frac {P}{S}}}}={\frac {1}{(1-0,3)+{\frac {0,3}{2}}}}=1,1765$

Da bi videli kako je ova formula izvedena, pretpostavimo da je vreme izvršavanja starog izvršavanja bilo 1 (za neku jedinicu vremena). Vreme izvršavanja novog izvršavanja će biti dužine dela koji nije poboljšan (1 − P) plus dužine dela koliko treba poboljšanom delu da se izvrši. Vreme koje je potrebno da se izvrši poboljšani deo jednak je prethodnoj dužini vremena izvršavanja ovog dela, podeljenog ubrzanjem. Time dobijamo dužinu vremena poboljšanog dela P/S. Konačno ubrzanje se računa deljenjem starog vremena izvršavanja, novim vremenom izvršavanja, koje se izračunava formulom gore.

Još jedan primer ovoga: dat nam je sekvencijalan zadatak koji se deli na četiri uzastopna dela: P1, P2, P3 i P4 koji se izvršavaju, procentualno, 11%, 18%, 23% i 48%, redom. Onda nam je rečeno da P1 ne ubrzava (tako da je S1 = 1) dok P2 ubrzava 5 puta, P3 ubrzava 20 puta i P4 ubrzava 1.6 puta. Korišćenjem formule P1/S1 + P2/S2 + P3/S3 + P4/S4, vidimo da je novo sekvencijalno vreme izvršavanja:

${\frac {0,11}{1}}+{\frac {0,18}{5}}+{\frac {0,23}{20}}+{\frac {0,48}{1,6}}=0,4575.$

ili malo manje od ​¹⁄₂ tj. početnog vremena izvršavanja. Korišćenjem formule (P1/S1 + P2/S2 + P3/S3 + P4/S4)⁻¹, ukupan dobitak na ubrzanju je 1 / 0,4575 = 2,186, ili malo više nego duplo veće od početne brzine. Primetimo kako ubrzanja od 20 i 5 puta nemaju puno efekta na ukupnu brzinu kada P1 (11%) ne ubrzava, a P4 (48%) ubrzava samo 1.6 puta.

Paralelizacija

U slučaju paralelelizacije, Amdalov zakon tvrdi da ako je P deo programa koji se može učiniti paralelnim (tj. može imati korist od paralelizacije), i ako je 1 − P deo koji se ne može paralelizovati (ostaje serijski), onda maksimalno ubrzanje, koje se može postići korišćenjem N procesora, je:

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

U granici, ako N teži beskonačnosti, maksimalno ubrzanje teži 1 / (1 − P). U praksi, odnos performanse i cene pada drastično kako se N povećava jednom kada ima i najmanja komponenta (1 − P).

Kao primer, ako je P 90%, onda je 1 − P 10% i problem se može ubrzati najviše 10 puta, bez obzira na to kolika je vrednost N. Zbog toga je paralelna obrada korisna samo za, ili male brojeve procesora, ili probleme koji imaju jako veliku vrednost P (takozvani neometano paralelni problemi). Veliki deo veštine paralelnog programiranja se sastoji od pokušaja da se smanji komponenta 1 – P na što manju vrednost.

P se može proceniti korišćenjem izmerenog ubrzanja (SU) na određenom broju procesora (NP) korišćenjem:

$P_{\text{процењено}}={\frac {{\frac {1}{SU}}-1}{{\frac {1}{NP}}-1}}$.

P, procenjeno na ovaj način, se može koristiti u Amdalovom zakonu da bi se predvidelo ubrzanje za drugačiji broj procesora.

Veza sa zakonom opadajućih povratnih vrednosti

Amdalov zakon se često spaja sa zakonom opadajućih povratnih vrednosti, s obzirom samo na specijalan slučaj kada primenom Amdalovog zakona, demonstriramo zakon opadajućih povratnih vrednosti. Ako se optimalno izabere šta želi da se poboljša (u smislu ostvarivanja ubrzanja), onda se mogu videti monotona opadanja nekih poboljšanja dok se neka druga još više poboljšavaju. Međutim, ako se izbor izvrši neoptimalno, posle poboljšanja manje optimalnih komponenti i prelaženja na poboljšanje više optimalnih komponenti, mogu se videti povećanja poboljšanja. Često je racionalno poboljšati sistem u redosledu koji nije optimalan zato što je neka poboljšanja teže dostići ili zato što zahtevaju više vremena.

Amdalov zakon predstavlja zakon opadajućih povratnih vrednosti ako se uzima u obzir koja sorta povratnih vrednosti se dobija dodavanjem više procesora nekoj mašini ako se pokreće računanje fiksne veličine koje će iskoristiti sve dostupne procesore do maksimuma. Svaki novi procesor koji se doda sistemu će dodati manje snage prema granici $\scriptstyle 1/(1\,-\,P)$.

Ova analiza zanemaruje druge potencijalne slučajeve gde se javljaju uska grla (kao što su propusni opseg memorije i propusni opseg ulaza/izlaza) ako se ne skalira sa brojem procesora. Međutim, uzimajući u obrzir ove slučajeve uskih grla bi težilo da, još detaljnije, demonstrira, opadajuće povratne vrednosti dodavanjem samo procesora.

Ubrzanje u sekvencijalnom programu

Pretpostavimo da zadatak ima 2 nezavisna dela, delove A i B. B delu treba otprilike 25% vremena celokupnog računanja. Radeći naporno, neko može učiniti ovaj deo 5 puta bržim, ali bi to samo smanjilo vreme izvršavanja celog računanja za malo. Suprotno, taj neko može uložiti manje napora i učiniti A deo duplo bržim. To će učiniti računanje mnogo bržim nego optimizovanje B dela, čak iako je brzina B dela veća (5 puta u odnosu na 2 puta).

Maksimalno ubrzanje u poboljšanom sekvencijalnom programu, gde je neki deo ubrzan $p$ puta je ograničeno nejednakošću:

${\text{максимално убрзање}}\leq {\frac {p}{1+f\cdot (p-1)}}$

gde je $\scriptstyle f$ ($\scriptstyle 0\;<\;f\;<\;1$) deo vremena (pre poboljšanja) potrošeno u delu koje nije poboljšano. Na primer (videti sliku desno:)

• Ako učinimo deo B pet puta bržim ($\scriptstyle p\;=\;5$), $\scriptstyle t_{A}\;=\;3$, $\scriptstyle t_{B}\;=\;1$, i $\scriptstyle f\;=\;t_{A}/(t_{A}\,+\,t_{B})\;=\;0,75$, onda

  ${\text{максимално убрзање}}\leq {\frac {5}{1+0,75\cdot (5-1)}}=1,25$

• Ako učinimo deo A dva puta bržim ($\scriptstyle p\;=\;2$), $\scriptstyle t_{B}\;=\;1$, $\scriptstyle t_{A}\;=\;3$, i $\scriptstyle f\;=\;t_{B}/(t_{A}\,+\,t_{B})\;=\;0,25$, onda

  ${\text{максимално убрзање}}\leq {\frac {2}{1+0,25\cdot (2-1)}}=1,60$

Stoga, duplo brži A deo je bolji slučaj nego pet puta brži B deo. Procenat poboljšanja u brzini se računa:

${\text{проценат побољшања}}=\left(1-{\frac {1}{\text{фактор убрзања}}}\right)\cdot 100$

• Poboljšanjem dela A duplo, dobija se povećanje ukupne brzine programa za 1,6 puta, što znači da je program brži za 37,5%.
• Međutim, poboljšanjem dela B pet puta, što zahteva i više napora, će rezultovati da ukupan program bude samo 20% brži.

Odnos sa Gustafsonovim zakonom

Džon L. Gustafson je 1988. godine istakao Gustafsonov zakon: ljudi obično nisu zainteresovani za rešavanje fiksnih problema u najkraćem vremenskom roku (kao što opisuje Amdalov zakon), već će radije rešavati kompleksnije probleme (tj. najprecizniju moguću aproksimaciju) u fiksnom „razumnom“ vremenskom periodu. Ako se ne-paralelizovani deo problema popravi, ili ako raste jako sporo sa veličinom problema (tj. O(log n)), onda dodatni procesori mogu povećati veličinu mogućeg problema bez ikakvih ograničenja.

Vidi još

• Murov zakon
• Gustafsonov zakon

Reference

• Amdahl, Gene (1967). „Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities” (PDF). AFIPS Conference Proceedings (30): 483—485. 
• Rodgers, David P. (1985). „Improvements in multiprocessor system design”. ACM SIGARCH Computer Architecture News archive. New York, NY, USA: ACM. 13 (3): 225—231. ISSN 0163-5964. doi:10.1145/327070.327215. 

Spoljašnje veze

• Cases where Amdahl's law is inapplicable
• Oral history interview with Gene M. Amdahl Charles Babbage Institute, University of Minnesota. Amdal diskutuje svoj diplomski rad i svoj WISC dizajn na univerzitetu u Viskonsinu. Diskutuje svoju ulogu u dizajniranju nekoliko računara za IBM uključujući STRETCH, IBM 701, i IBM 704. Diskutuje svoj rad sa Natanijelom Rohesterom i IBM-ovim menadžmentom procesa dizajniranja. Pominje rad sa Ramo-Wooldridge, Aeronutronic, i Computer Sciences Corporation
• Reevaluating Amdahl's Law
• A simple interactive Amdahl's Law calculator
• "Amdahl's Law" by Joel F. Klein, Wolfram Demonstrations Project, 2007.
• Amdahl's Law in the Multicore Era
• Amdahl's Law explanation
• Blog Post: "What the $#@! is Parallelism, Anyhow?"
• Amdahl's Law applied to OS system calls on multicore CPU