mini|180px|desno|Cray-2 je bilo najbrže računalo na svijetu od 1985. do 1989. godine Paralelna obrada je postupak kod kojega se više instrukcija obrađuje istovremeno.G.S. Almasi and A. Gottlieb. Highly Parallel Computing. Benjamin-Cummings publishers, Redwood city, CA, 1989. Obrada se zasniva na principu da se veliki problemi gotovo uvijek mogu podijeliti na manje te onda obraditi istovremeno (paralelno). Ovaj tip obrade postoji u nekoliko oblika: 1. Paralelizam na razini bita, 2. Paralelizam na razini instrukcije, 3. Podatkovni paralelizam, 4. Zadaćni paralelizam ().
Navedeni oblik obrade je korišten dugo vremena u procesiranju visoke brzine, ali interes je ovih godina jako porastao zbog fizičkih ograničenja koja sprječavaju frekvencijsko skaliranje. U posljednje vrijeme paralelna obrada je postala vodeća paradigma u računalnim arhitekturama, najvećim djelom u obliku višejezgrenih procesora.Krste Asanovic et al. The Landscape of Parallel Computing Research: A View from Berkeley (PDF). University of California, Berkeley. Technical Report No. UCB/EECS-2006-183. 18. prosinca, 2006.: "Stara [dogovoren pogled]: Povećanje frekvencije takta je osnovna metoda poboljšanja performansi procesora. Nova[dogovoren pogled]: Povećanje paralelizma je osnovna metoda za poboljšanje performansi procesora ... Čak i predstavnici Intela, kompanije koja se općenito vezala za hipotezu "viši takt znači brže izvođenje", proglasila je da tradicionalni pristup povećanja performansi putem povećanja takta dosegao svoj maksimum." Ipak je potrošnja u paralelnim računalima postala zabrinjavajuća.Asanovic et al. Stara [dogovoren pogled]: Snaga je besplatna, ali tranzistori su skupi. Nova [dogovoren pogled] je [da] je snaga skupa, ali su tranzistori "besplatni".
Paralelne računalne programe je mnogo teže razvijati nego sekvencijalneDavid A. Patterson i John L. Hennessy. Computer Organization and Design (Drugo izdanje) Morgan Kaufmann Publishers, 1998. , p. 715. zato što istodobnost uvodi nekoliko novih klasa potencijalnih softverskih bugova od kojih su „race condition“ najčešći. Komunikacija i sinkronizacija između različitih podzadataka je jedno od najvećih ograničenja za dobivanje dobrih performansi paralelnog programa. Ubrzanje izvršavanja programa kao rezultat paralelne obrade je opisano Amdahlovim zakonom.
Pozadina
Uobičajeno se programska podrška piše za serijsku obradu. Rješenje problema nalazi se u kreiranju algoritma koji proizvodi serijski niz instrukcija. Ove instrukcije se izvršavaju na centralnom procesoru jednog računala. Samo jedna instrukcija se može izvršiti u jednom periodu vremena, a nakon njenog izvršenja sljedeća.
Nasuprot tome paralelna obrada koristi simultano više paralelnih elemenata kako bi riješila problem. To je postignuto podjelom problema u dijelove koji su neovisni pa svaki element obrade može izvršiti jedan dio vlastitog algoritma istovremeno s drugima. Elementi obrade su različiti i uključuju resurse kao što su računala s više procesora, mreža računala, specijalizirani hardver ili bilo koja kombinacija navedenog.
Frekvencijsko skaliranje je bilo glavni uzrok rasta računalnih performansi od sredine 1980-ih do 2004. godine. Vrijeme izvođenja programa je jednako broju instrukcija, pomnoženom sa srednjim vremenom izvršenja po instrukciji. Održavajući sve ostalo konstantnim, povećanjem frekvencije smanjuje se srednje vrijeme izvršavanja po instrukciji. Iz toga razloga, povećanjem frekvencije se smanjuje vrijeme izvođenja svih računski zahtjevnih programa.John L. Hennessy i David A. Patterson. Computer Architecture: A Quantitative Approach. 3rd edition, 2002. Morgan Kaufmann, , p. 43.
Potrošnja energije u čipu je dana izrazom:
gdje je P snaga, C - kapacitivnost uključenja po ciklusu takta (proporcionalna broju tranzistora čiji se ulazi mijenjaju), V - napon i F - frekvencija procesora.J.M. Rabaey. Digital Integrated Circuits. Prentice Hall, 1996. , p. 235.
Povećanje frekvencije utječe na snagu koju procesor koristi. Povećana potrošnje energije procesora je dovelo do prekida razvoja Intelovih Tejas i Jayhawk procesora, što se povezuje s krajem frekvencijskog skaliranja kao dominantne paradigme računale arhitekture.Laurie J. Flynn. Intel Halts Development of 2 New Microprocessors. The New York Times, 8. svibnja, 2004. Otkriveno 22. travnja, 2008.
Mooreov zakon je empirijsko opažanje koje opisuje udvostručavanje gustoće tranzistora u mikroprocesoru u periodu od 18 do 24 mjeseci. Usprkos problemima s disipacijom i ponavljanim predviđanjima kraja, Mooreov zakon još uvijek vrijedi. S krajem frekvencijskog skaliranja, dodatni tranzistori (koji se više ne koriste za frekvencijsko skaliranje) se mogu iskoristiti kako bi dodali hardver potreban za paralelnu obradu.
Amdahlov i Gustafsonov zakon
mini|300px|desno|Izvođenje programa i ubrzanje real-world programa sa suboptimalnom paralelizacijom. Plava krivulja prikazuje moguće (linearno) ubrzanje izvođenja u optimalnom slučaju, dok ljubičasta krivulja prikazuje stvarno (suboptimalno) ubrzanje. Iz istog razloga žuta krivulja prikazuje moguće vrijeme izvođenja u optimalnom slučaju (asimptota koja se približava nuli), dok crvena krivulja prikazuje stvarno vrijeme izvođenja (asimptota koja se približava vrijednosti većoj od nule)
Teoretski gledano, ubrzanje dobiveno paralelizacijom udvostručenjem elemenata za obradu trebalo bi prepoloviti vrijeme izvođenja, a drugim udvostručenjem također bi se vrijeme izvođenja trebalo prepoloviti. Ipak, vrlo mali broj paralelnih algoritama postiže optimalno ubrzanje. Većina ima skoro pa linearno ubrzanje za mali broj elemenata za obradu. Daljnjim povećanjem broja elemenata za obradu vrijeme obrade postaje jednoliko (konstantno).
Performanse algoritma u platformama s paralelnom obradom ovise o paraleliziranosti algoritma u cilju dostizanja performansi, stoga je važno pripaziti na Amdahlov zakon. Amdahlov zakon je formulirao Gene Amdahl 60-ih godina 20. stoljeća.G. Amdahl. The validity of the single processor approach to achieving large-scale computing capabilities. In Proceedings of AFIPS Spring Joint Computer Conference, pp. 483–85, Atlantic City, N.J., April 1967. AFIPS Press. On tvrdi da mali dijelovi programa koji se ne mogu paralelizirati ograničavaju ukupno ubrzanje dobiveno paralelizacijom. Bilo koji matematički ili inženjerski problem uobičajeno će se sastojati od nekoliko dijelova, koji se mogu paralelizirati i nekoliko koji se ne mogu paralelizirati (sekvencijalne komponente). Ovaj odnos je dan izrazom:
gdje je S ubrzanje programa (kao faktor njegovog osnovnog sekvencijalnog izvođenja), a P dio koji se paralelizira. Ne može se ostvariti ubrzanje više od 10x, ako sekvencijalni dio programa iznosi 10% izvođenja, bez obzira koliko procesora dodajemo. Na ovaj način je postavljena gornja granica korisnosti dodavanja više paralelnih izvršnih jedinica."The Mythical Man-Month: Essays on Software Engineering. Frederick P. Brooks Jr.. Chapter 2 - The Mythical Man Month.
Gustafsonov zakon je drugi zakon računalnog inženjeringa, usko vezan za Amdahlov zakon. Gustafsonov zakon se može formulirati kao:
mini|400px|desno|Grafički prikaz Amdahlova zakona, pretpostavljeno je da zadatak ima dva nezavisna dijela, A i B. B zauzima otprilike 25% vremena ukupne obrade. Programer naporima može ubrzati taj dio 5 puta, ali to samo malo smanjuje vrijeme ukupne obrade. Za usporedbu, drugi bi trebao mnogo manje vremena kako bi ubrzao A-dio dva puta. Obrada će sada biti mnogo brža nego li optimiziranjem B-dijela, iako B ima veće ubrzanje (5x naprema 2x).gdje je P - broj procesora, S - ubrzanje, i α - neparalelizirani dijelovi procesa.Reevaluating Amdahl's Law Communications of the ACM 31(5), 1988. pp. 532–33. Amdahlov zakon pretpostavlja konačnu veličinu problema i ta veličina sekvencijalnog dijela je neovisna o broju procesora, dok Gustafsonov zakon nema tih pretpostavki.
Ovisnosti
Razumijevanje podatkovnih ovisnosti je jedan od osnova shvaćanja implementacije paralelnih algoritama. Niti jedan program se ne može izvesti brže od najdužeg lanca ovisnih izračuna (kritični put) zbog činjenice da izračuni koji su ovisni, a uvode slijed izvršavanja. Na sreću, većina algoritama se ne sastoji od dugačkih lanaca, međusobno ovisnih izračuna i uvijek postoje mnoge mogućnosti paralelnog izvršavanja neovisnih izračuna.
Neka su Pi i Pj dva fragmenta programa. Bernsteinovi uvjetiA.J. Bernstein, "Program Analysis for Parallel Processing,' IEEE Trans. on Electronic Computers, EC-15, listopad 1966., pp. 757–62. opisuju stanje kada su dva fragmenta neovisna i mogu biti paralelno izvršeni. Neka su Ii sve ulazne varijable od Pi i Oi - izlazne varijable.
Analogno tome Pj. Pi i Pj su neovisne ako zadovoljavaju uvjete:
Narušavanjem prvog uvjeta uvodi se ovisnost toka, što znači da prvi izraz daje rezultat koji koristi drugi izraz. Drugi uvjet predstavlja protuovisnost, kad prvi iskaz prepisuje varijablu koju koristi drugi izraz. Zadnji uvjet q je ovisnost izlaza. Kad dvije varijable zapisuju na istu lokaciju, konačni izlaz mora biti iz drugog iskaza.Roosta, Seyed H. Parallel processing and parallel algorithms: theory and computation. 2000. Springer, , p. 114.
Na primjer, pretpostavi se sljedeća funkcija:
1: function Dep(a,b) 2: c := a*b 3: d := 2*c 4: end function
Operacija u trećoj liniji koda funkcije Dep(a,b) ne može se izvršiti prije (ili čak paralelno) druge operacije zbog činjenice da treća operacija koristi rezultat iz druge. Navedeno krši prvi uvjet i tako ubacuje ovisnost toka.
1: function NoDep(a,b) 2: c := a*b 3: d := 2*b 4: e := a+b 5: end function
U ovom primjeru ne postoje ovisnosti između instrukcija pa se one mogu obraditi paralelno.
Bernsteinov uvjet ne dopušta dijeljenje memorije između različitih procesa, stoga zahtjeva neku od metoda raspodjeljivanja pristupa, kao što su semafori, barijere ili neku drugu sinkronizacijsku metodu.
“Race condition”, međusobno isključivanje, sinkronizacija i paralelno usporavanje
Podzadatke u paralelnim programima često se nazivaju nitima. Neke paralelne računalne arhitekture koriste manje, lakše verzije niti, poznate kao vlakna, dok drugi koriste veće verzije poznate kao procesi. Ipak, „niti“ () se općenito prihvaćaju kao opći nazivi za podzadatke. Niti će često morati obnoviti neke varijable koje međusobno dijele. Instrukcije između dva programa se isprepliću u bilo kojem redoslijedu. Navedeno se može vidjeti na sljedećem primjeru programa.
Nit ANit B1A: Pročitaj varijablu V1B: Pročitaj varijablu V2A: Povećaj varijablu V za 12B: Povećaj varijablu V za 13A: Zapiši varijablu V3B: Zapiši varijablu V
Ako je instrukcija 1B izvršena između 1A i 3A ili je instrukcija 1A izvršena između 1B i 3B, program će izračunati pogrešni podatak. Ovo se još naziva i "race condition". Programer mora koristi zaključavanje kako bi pružio međusobna isključivost. Zaključavanje je konstruktor u programskom jeziku koji pruža kontrolu jednooj niti nad varijablom i sprječava druge niti da ih čitaju ili zapisuju dok se varijabla ne oslobodi. Dok nit drži pravo pristupa ona može izvršiti svoj kritični dio (dio programa koji zahtjeva prvenstvo pristupa varijabli)i otključati pristup podatcima kada je završila s obradom. Ovo garantira ispravno izvođenje programa, gornji program se može ponovno napisati korištenjem zaključavanja.
Nit ANit B1A: Zaključaj varijablu V1B: Zaključaj varijablu V2A: Pročitaj varijablu V2B: Pročitaj varijablu V3A: Povećaj varijablu V za 13B: Povećaj varijablu V za 14A: Zapiši varijablu V4B: Zapiši varijablu V5A: Otključaj varijablu V5B: Otključaj varijablu V
Jedna nit će uspješno zaključati varijablu V, dok će druga biti onemogućena – nemoguće ju je proslijediti dok V nije nanovo otključana. Ovo pruža ispravno izvršenje programa. Zaključavanje će istodobno jako usporiti izvođenje programa, dok neophodno osigurava ispravno izvršavanje programa.