Paralelni algoritam

U računarstvu, paralelni algoritam, kao suprotnost tradicionalnim serijskim algoritmima, je algoritam koji može biti izvršavan deo po deo na više procesorskih uređaja i onda biti spojen na kraju izvršavanja, za dobijanje konačnog rezultata.^[1]

Mnogi paralelni algoritmi se mogu izvršavati istovremeno, iako su uopšteno istovremeni algoritmi različit koncept, ti pojmovi se često preklapaju, jer se često gubi granica koji aspekt algoritma se izvršava paralelno a koji istovremeno. Neparalelni, neistovremeni algoritmi se često nazivaju "sekvencijalnim algoritmima", za razliku od istovremenih algoritama.^[2]^[3]

Paralelnost

Algoritmi se razlikuju po tome koliko se mogu paralelizovati, od algoritama koji se lako paralelizuju do algoritama koji se ne mogu paralelizovati. Štaviše, zadati problem se može prilagoditi različitim algoritmima , koji mogu biti lakše ili teže paralelizovani.

Neki problemi se mogu lako podeliti na delove na ovaj način - takvi problemi se nazivaju problemi koji se sramotno lako paralelizuju. Na primer, podeliti posao provere koji su brojevi od jedan do sto hiljada prosti, se može lako uraditi tako što se podskupovima brojeva pridruži slobodan procesor i zatim se liste prostih brojeva spoje u jednu. Paralelni algoritmi su često upotrebljavani za stvari poput rešavanja Rubikove kocke ili za heš dekripciju.

Neki problemi se ne mogu podeliti u parelelne delove, jer zahtevaju rezultate iz prethodnog koraka da bi efektivno nastavili sa izvršavanjem sledećeg koraka algoritma - oni se nazivaju nasledno serijski problemi. Primeri uključuju iterativne numeričke metode, kao što je Njutnov metod, iterativna rešenja za problem tri tela, a većina od dostupnih algoritama izračunavanje broja Pi (π).

Motivacija

Paralelni algoritmi na pojedinačnim uređajima su postali zastupljeniji od ranih 2000.tih godina zbog suštinskih poboljšanja u multiprocesorskim sistemima i uspona višejezgarnih procesora. Sve do kraja 2004. godine performanse jednojezgarnih procesora naglo su rasle pomoću frekvencijskog skaliranja, pa je bilo lakše izgraditi računar sa jednim, brzim jezgrom, nego sa više sporijih jezgara sa istim protokom. Međutim, od 2004. godine, frekvencijsko skaliranje je dostiglo granicu, i tako su multijezgarni sistemi postali rasprostranjeniji, čineći da se paralelni algoritmi generalno više upotrebljavaju.

Problemi

Komunikacija

Cena ili složenost serijskih algoritama se procenjuje u pogledu prostora (memorije) i vremena (ciklusa procesora) koje potroše. Paralelni algoritmi treba da optimizuju još jedan resurs, komunikaciju između različitih procesora. Postoje dva načina na koji paralelni procesori komuniciraju, to su deljena memorija i predavanje poruke.

Obrada denjene memorije, zahteva dodatno zaključavanje podataka,nameće opšte troškove dodatnih procesora i ciklusa magistrale i takođe serijalizuje neki deo algoritma.

Obrada predavanja poruka, koristi kanale i kutije za poruke, ali ovaj tip komunikacije dodaje opšte troškove magistrale, dodatne memorije koja je potrebna za redove i kutije za poruke, kao i kašnjenja poruka. Prilikom dizajniranja paralelnih procesora koriste se specijalne magistrale poput krosbar prekidača tako da će opšti troškovi komunikacije biti mali, ali paralelni algoritam odlušuje o brzini protoka.

Ako troškovi komunikacije između dodatih procesora prevazilaze korist dobijenu dodavanjem dodatnog procesora jedan od njih se paralelno usporava.

Balansiranje opterećenjem

Još jedan problem sa paralelnim algoritmima je obezbeđivanje da su odgovarajuće izbalansirani, obezbeđujući da je opterećenje (ukupan rad) balansirano, a ne veličina ulaznih podataka. Na primer , proveru koji su brojevi od jedan do sto hiljada prosti je lako podeliti između procesora. Međutim, ako se ti brojevi jednostavno podele ravnomerno (1-1000, 1001-2000, itd), količina rada će biti neuravnotežena, zbog toga što je manji broj lakši za obradu od strane ovog algoritma (lakše se testira da li je broj prost ), i tako će neki procesori dobiti više posla od drugih, koji će biti besposleni dok opterećeni procesori ne završe izvršavanje algoritma.

Raspodenjeni algoritmi

Podvrsta paralelnih algoritama, raspodeljeni algoritmi su algoritmi dizajnirani da rade u klaster i raspodeljenim računarskim okruženjima, gde treba rešiti dodatne probleme izvan okvira "klasičnih" paralelnih algoritama.

Vidi još

Reference

^ Blelloch, Guy E.; Maggs, Bruce M. „Parallel Algorithms” (PDF). USA: School of Computer Science, Carnegie Mellon University. Pristupljeno 27. 07. 2015.
^ "Concurrency is not Parallelism", Waza conference Jan 11, 2012, Rob Pike (slides) (video)
^ „Parallelism vs. Concurrency”. Haskell Wiki.

Spoljašnje veze

[1] Blelloch, Guy E.; Maggs, Bruce M. „Parallel Algorithms” (PDF). USA: School of Computer Science, Carnegie Mellon University. Pristupljeno 27. 07. 2015.

[waza-2] "Concurrency is not Parallelism", Waza conference Jan 11, 2012, Rob Pike (slides) (video)

[3] „Parallelism vs. Concurrency”. Haskell Wiki.

[1]

[2]

[3]