Gustafsonov zakon

Gustafsonov zakon

Gustafsonov zakon (još poznat i kao Gustafsonov i Barsisov zakon) je zakon u računarstvu koji nam govori da se izračunavanja, koja koriste proizvljno velike skupove podataka, mogu efikasno paralelizovati. Gustafsonov zakon obezbeđuje kontrapunkt Amdalovom zakonu, koji opisuje granicu povećanja brzine koje omogućava paralelizam (tako što daje fiksnu veličinu skupova). Gustafsonov zakon je prvi put opisao Džon L. Gustafson i njegov kolega Edvin H. Barsis.

$S(P)=P-\alpha \cdot (P-1)$

Gde je:

• P broj procesora
• S je ubrzanje
• $\alpha$ je ne-paralelizovan deo bilo kog paralelnog procesa

Gustafsonov zakon govori o manama Amdalovog zakona, koji ne eksploatiše potpuno moć izračunavanja koja postaje dostupna kako se povećava broj mašina. Umesto toga, Gustafsonov zakon predlaže da programeri teže da odrede veličinu problema da bi koristili dostupnu operemu da bi rešili probleme u praktičnom fiksnom vremenskom periodu. Ako je brža ili dostupnija oprema dostupna, veći problemi će se rešavati u istom vremenskom periodu.

Navodno, Gustafson je nazvao svoje metrično „skalarno ubrzanje”, jer je u iznad navedenom izrazu S(P) odnos vremena izvršavanja jednog procesa i vremena paralelnog izvršavanja po procesu, prethodni izraz je skaliran sa P, dok dotično slovo predstavlja pretpostavku zaokruživanja ili vrednost najbližu tome. Ovo je kontrast u odnosu na Amdalov zakon, čime je vreme izvršavanja jednog procesa fiksne veličine, i poredi ga sa smanjivanjem vremena paralelnog izvršavanja po jednom procesu. Tako da je Amdalov zakon baziran na pretpostavci da postoji problem fiksne veličine: pretpostavlja se da se sveukupno opterećenje programa ne menja sa brojem procesora. Oba zakona pretpostavljaju da je paralelizovan deo jednako podeljen na P procesora.

Cilj Gustafsonovog zakona je bio da pomeri granice ciljeva istraživanja ili da reformuliše probleme tako da bi bilo moguće rešiti veći problem za isto vreme. U neku ruku zakon redefiniše efikasnost zbog mogućnosti da granice, koje je sekvencijalni program nametnuo, mogu biti odbijene povećanjem broja izračunavanja.

Izvođenje Gustafsonovog zakona

Vreme izvršavanja programa na računaru sa paralelnom obradom se može svesti na:

$(a+b)$

Gde je $a$ sekvencijalno vreme a $b$ paralelno vreme na bilo kom od P procesora.

Ključna pretpostavka Gustafsona i Barsisa je da ukupna količina posla koji se obavlja paralelno "varira linearno sa brojem procesora". U tom slučaju, praktična implikacija jednog procesora je sposobnija od jednog zadatka obrade koja treba da se izvrši paralelno sa (obično sličnim) drugim zadacima. To podrazumeva da bi b trebalo da bude fiksno kako P varira. Vreme koje odgovara sekvencijalnoj obradi je:

$a+P\cdot b.$

Ubrzanje je prema tome:

$(a+P\cdot b)/(a+b).$

Pošto je

$\alpha =a/(a+b)$

sekvencijalan deo paralelnog vremena izvršavanja, imamo:

$S(P)=\alpha +P\cdot (1-\alpha )=P-\alpha \cdot (P-1).$

Tako da, ako je $\alpha$ malo, ubrzanje je približno P, kao i što je traženo. Može čak biti slučaj i da se $\alpha$ umanjije dok P raste (zajedno sa veličinom problema). Ako je to tačno, onda S pristupa P monotono sa rastom P.

Gustafsonov zakon izgleda spašava paralelnu obradu od Amdalovog zakona. Baziran je na ideji da, ako je dozvoljeno da raste veličina problema monotono sa P, onda sekvencijalan deo opterećenja ne bi dominirao. Ovo se omogućava time što se većina zadataka individualno sadrži u jednom procesorovom obimu obrade. Time, jedan procesor može omogućiti više zadataka, dok jedan zadatak ne može biti na više procesora. Ovo je takođe pravilo za projekte radnih sajtova, koji imaju više projekata po sajtu, ali samo jedan sajt po projektu.

Metafora vožnje

Amdalov zakon otprilike kaže:

„ Pretpostavimo da vozilo putuje između 2 grada koji su 100km jedan od drugog, i da je već proputovalo pola puta, brzinom od 50km/h, za jedan sat. Bez obzira na to koliko će se vozilo brzo kretati do kraja puta, nemoguće je da će dostići prosečnu brzinu od 145km/h pre nego što dođe do drugog grada. Pošto mu je već bilo potrebno 1 sat da pređe 100km, vožnjom beskonačno velikom brzinom bi postigli brzinu od samo 100km/h. ”

Gustafsonov zakon otprilike kaže:

„ Pretpostavimo da se vozilo već kretalo neko vreme od najmanje 145km/h. Ako mu damo dovoljno vremena i puta koje treba da pređe, prosečna brzina vozila bi uvek dostizala brzinu od 145km/h, bez obzira na to koliko daleko ili koliko sporo se beć kretalo. Na primer, ako se vozilo kretalo sat vremena brzinom od 50km/h, moglo bi da postigne ovo vozeći još dva sata brzinom od 200km/h ili barem 250km/h još jedan sat, itd. ”

Aplikacije

Aplikacije u istraživanjima

Amdalov zakon pretpostavlja da će zahtevi za izračunavanje ostati isti, iako nam je dato povećanje procesorske moći. Drugim rečima, za analizu istih podataka će trebati manje vremena sa povećanjem procesorke moći.

Gustafson, u drugu ruku, govori da će više procesorske moći izazvati da podaci budu pažljivije i u potpunosti analizirani: piksel po piklsel ili jedinica po jedinica, umesto u većoj meri. Ne bi bilo moguće, niti praktično, simulirati nuklearnu detonaciju na svakoj zgradi, automobilu i njihovim sadržajima (nameštaj, snaga strukture, itd.) jer bi ovakvi proračuni oduzeli više vremena nego što je potrebno da se dobije odgovor i zbog toga će povećanje moći izračunavanja navesti istraživače da dodaju više podataka da bi u potpunosti simulirali više promenljivih i time dobili preciznije rezultate.

Aplikacije u svakidašnjim računarskim sistemima

Amdalov zakon otkriva ograničenje u, na primer, sposobnosti više jezgara da smanje vreme koje je potrebno računaru da pokrene operativni sistem i da bude spreman za upotrebu. Pod pretpostavkom da se proces podizanja sistema uglavnom vrši paralelno, učetvorostručuvanjem računarske moći na sistemu kome treba minut da se pokrene dobićemo smanjenje vremena pokretanja sistema od čak samo 15 sekundi. Ali veća i veća paralelizacija kad tad neće uspeti da pokrene sistem brže ako se bilo koji deo procesa za pokretanje operativnog sistema izvrši sekvencijalno.

Gustafsonov zakon tvrdi da će četvorostruko povećanje računarske moći, umesto toga, da dovede do sličnog povećanja u očekivanjima, za šta će sistem biti sposoban. Ako je jedno-minutno dizanje sistema prihvatljivo većini korisnika, onda je to početna tačka od koje će se povećavati karakteristike i funkcije sistema. Vreme koje je potrebno da se podigne operativni sistem će ostati isto tj. jedan minut, ali će novi sistem obuhvatati više grafičkih ili korisnički prijateljskih karakteristika.

Ograničenja

Neki problemi nemaju suštinski veće skupove podataka. Na primer, obrada jednog podatka po stanovniku sveta se povećava za samo par procenata godišnje. Suštinska tačka Gustafsonovog zakona je da će takvi problemi manje verovatno postati plodne aplikacije paralelizma.

Nelinearni algoritmi će teško iskoristiti prednost paralelizma „izloženog” od strane Gustafsonovog zakona. Snajder (engl. Snyder) ističe da algoritmi složenosti O(N³) koji dupliraju koherentnost daju samo oko 26% povećanje veličine problema. Tako, dok je moguće da se zauzme ogromna konkurentnost, to može dovesti do samo male prednosti u odnosu na original. Manje konkurentna rešenja, međutim, u praksi, su davala masivna poboljšanja.

Hil i Marti (Hill,Marty) takođe naglašavaju da su metode ubrzavanja sekvencijalnog izvršavanja i dalje potrebne, čak i za višeprocesorske mašine. Izlažu da lokalne neefikasne metode mogu biti globalno efikasne kada smanje sekvencijalne faze. Štaviše, Vu i Li (Woo,Lee) su proučavali implikaciju energije i snage na budućim više-jezgarnim procesorima baziranim na Amdalovom zakonu, što je pokazalo da asimetrični više-jezgarni procesori mogu postići najbolju moguću efikasnost energije aktiviranjem optimalnog broja jezgara kojima (pod uslovom da je poznata količina paralelizma pre izvršavanja).

Vidi još

• Skalabilni paralelizam
• Amdalov zakon