Pređi na sadržaj

Automatska paralelizacija

S Vikipedije, slobodne enciklopedije

Automatska paralelizacija, takođe autoparalelizacija, ili paralelizacija, koristi se u kontekstu pretvaranja sekvencijalnog koda u višenitni ili vektorski kod (ili čak oba), kako bi se simultano iskoristilo više procesora u zajedničkoj memoriji multiprocesorske (SMP) mašine. Cilj automatske paralelizacije je da oslobodi programere od napornih i grešakama sklonih procesa ručne paralelizacije.[1] Iako je kvalitet automatske paralelizacije poboljšan poslednjih nekoliko decenija, potpuna automatska paralelizacija sekvencijalnih programa kompajlerima ostaje veliki izazov zbog potrebe za kompleksnim analizama programa i nepoznatih faktora (kao što je opseg ulaznih podataka ) tokom kompilacije.[2]

Programske kontrolne strukture na kojima autoparalelizacija najviše stavlja akcenat su petlje, jer, generalno, najviše vremena izvršenja programa se odvija unutar nekog oblika petlje. Postoje dva osnovna pristupa paralelizaciji petlje: ugnežđena višenitna obrada i ciklična višenitna obrada.[3]

Na primer, razmotrimo petlju koja u svakoj iteraciji vrši stotine operacija, i traje hiljadu iteracija. Ovo se može posmatrati kao mreža 100 kolona od 1000 redova, ukupno 100.000 operacija. Ciklična višenitna obrada dodeljuje svaki red zasebnoj niti. Linijska višenitna obrada dodeljuje svaku kolonu zasebnoj niti. 

Ciklična višenitna obrada[uredi | uredi izvor]

Ciklična višenitna obrada paralelnog kompajlera pokušava da razdvoji petlju tako da se svako ponavljanje može izvršiti na zasebnom procesoru istovremeno. 

Kompajler paralelne analize[uredi | uredi izvor]

Kompajler obično sprovodi dve prolazne analize pre stvarne paralelizacije kako bi se utvrdilo sledeće: 

  • Da li je bezbedno da se paralelizuje petlja? Odgovar na ovo pitanje zahteva precizno analiziranje zavisnosti i alijasa. 
  • Da li je vredno da se paralelizuje? Ovaj odgovor zahteva pouzdanu procenu (modeliranje) programskog opterećenja i kapaciteta paralelnog sistema.

Prvi prolaz kompajlera obavlja analizu zavisnosti podataka petlje da bi se utvrdilo da li se svaka iteracija petlje može izvršiti nezavisno od drugih. Zavisnosti podataka se ponekad mogu razrešiti, ali to može da unese dodatno opterećenje u vidu razmene poruka, sinhronizacije zajedničke memorije, ili nekog drugog načina procesorske komunikacije. 

Drugi prolaz pokušava da opravda napore paralelizacije upoređivanjem teorijskog vremena izvršavanja koda nakon paralelizacije sa sekvencijalnim vremenom izvršenja. Ponekad se, u neskladu sa intuicijom, kod ne poboljšava paralelizacijom. Dodatni rad uzrokovan korišećenjem višestrukih procesora može da poništi potencijalna ubrzanja paralelizovanog koda. 

Primer[uredi | uredi izvor]

Petlja se zove DOALL ako se sve njene iteracije, u svakom prizivanju, mogu uporedo izvršiti. Fortran kod ispod je DOALL, i kompajler ga može automatski paralelizovati jer je svaka iteracija nezavisna od drugih, a krajnji rezultat niza z će biti ispravan bez obzira na redosled izvršavanja drugih iteracija. 

   do i = 1, n
     z(i) = x(i) + y(i)
   enddo

Postoji mnogo prijatnih paralelnih problema koje imaju takve DOALL petlje. Na primer, kada rendering prati film, svaki frejm filma može nezavisno da se iskaže, a svaki piksel pojedinačnog okvira može biti nezavisno iskazan. 

Sa druge strane, sledeći kod ne može biti autoparalelizovan, jer vrednost z(i) zavisi od rezultata prethodne iteracije, z(i - 1) .  

   do i = 2, n
     z(i) = z(i - 1)*2
   enddo

To ne znači da se kod ne može paralelizovati. Ekvivalentno je 

   do i = 2, n
     z(i) = z(1)*2**(i - 1)
   enddo

Međutim, sadašnji kompajleri paralelizacije obično nisu u stanju da proizvedu automatsku paralelizaciju, a i pitanje je da li će taj kod imati koristi od paralelizacije na prvom mestu.

Ugnežđeno korišćenje koda[uredi | uredi izvor]

Ugnežđeno korišćenje koda paralelnog kompajlera pokušava da rasčlani redosled operacija unutar petlje u niz kodnih blokova, tako da se svaki blok koda izvršava na odvojenim procesorima istovremeno. 

Postoje mnogi prijatno paralelni problemi koje imaju takve relativno nezavisne kodne blokove, posebno sistemi koji koriste cevi i filtere. Na primer, pri prenosu televizijkog programa uživo, sledeći zadaci se moraju obavljati više puta u sekundi: 

  1. Pročitajte okvir sirovog piksela podataka sa senzora slike,
  2. Izvršite MPEG kompenzaciju kretanja na sirovim podacima, 
  3. Entropski komprimujte vektore kretanja i druge podatke, 
  4. Razložite komprimovane podatke u pakete, 
  5. Dodajte odgovarajuću korekciju greške i izvršite FFT da biste konvertovali pakete podataka u COFDM signale, i 
  6. Pošaljite COFDM signale iz TV antene. 

Ugnežđena višenitna obrada paralelizirajućeg kompajlera može da dodeli svaku od ovih 6 operacija različitom procesoru, možda uređehih u sistolnom nizu, umećući odgovarajući kod da prosledi izlaz jednog procesora na sledeći procesor. 

Nedavna istraživanja su fokusirana na korišćenje moći GPU procesora[4] i višejezgarnih sistema[5] za izračunavanje takvih nezavisnih kodnih blokova (ili jednostavno nezavisnih iteracija petlje) u runtime. Memorija pristupa (direktno ili indirektno) može biti jednostavno obeležena za različite iteracije petlje i može se porediti radi detekcije zavisnosti. Koristeći ovu informaciju, iteracije se grupišu u nivoe tako da su iteracije istog nivoa nezavisne jedna od druge, te da se mogu paralelno izvršavati. 

Teškoće[uredi | uredi izvor]

Automatska paralelizacija kompajlerima ili alatima je veoma teška iz sledećih razloga:[6] 

  • analiza zavisnosti je teška za kod koji koristi indirektno adresiranje, pokazivače, rekurziju, ili posredne funkcijske pozive, jer je teško otkriti takve zavisnosti pri kompajliranju;
  • Petlje imaju nepoznat broj iteracija
  • pristup globalnim resursima se teško može koordinirati u smislu alokacije memorije, I/O, i zajedničkih promenljivih; 
  • neregularni algoritmi, koji koriste preusmerenja koja su zavisna od unosa, ometaju analizu pri kompajliranju i optimizaciji. [7]

Zaobilazak[uredi | uredi izvor]

Zbog svojstvenih poteškoća ostvarivanja potpuno automatske paralelizacije, postoji nekoliko lakših pristupa da bi se dobio paralelni program višeg kvaliteta. Oni su: 

  • Dozvoliti programerima da dodaju "savete" svijim programima za vođenje kompajlerske paralelizacije, kao što su HPF za distribuiranu memoriju sistema i OpenMP ili OpenHMPP za zajedničku memoriju sistema.
  • Graditi interaktivni sistem između programera i paralelizacionog alata/kompajlera. Značajni primeri su Pareon preduzeća Vector Fabrics, SUIF Explorer (konmpajler intermedijarnog formata Stanfordskog univerziteta), Polaris kompajler, i ParaVajs (formalno KAPalati). 
  • Hardverski podržana spekulativna višenitna obrada. 

Istorijska paralelizacija kompajlera[uredi | uredi izvor]

Vidi još: Automatic parallelization tool

Većina istraživanja kompajlera za automatsku paralelizaciju razmatra Fortran programe, jer Fortran čini jače garancije o alijasu nego jezici kao što su C. Tipični primeri su:

  • Paradigma kompajler
  • Polaris kompajler
  • Rajs Fortran kompajler D
  • SUIF kompajler
  • Beš Fortran kompajler

Vidi još[uredi | uredi izvor]

Reference[uredi | uredi izvor]

  1. ^ "Yehezkael, Rafael (2000). „Experiments in Separating Computational Algorithm from Program Distribution and Communication”. Lecture Notes in Computer Science of Springer Verlag. 1947: 268—278. "
  2. ^ Fox, Geoffrey; Williams, Roy; Messina, Paul (1994). Parallel Computing Works!. Morgan Kaufmann. str. 575,593. ISBN 978-1-55860-253-3. 
  3. ^ Simone Campanoni, Timothy Jones, Glenn Holloway, Gu-Yeon Wei, David Brooks.
  4. ^ J Anantpur, R Govindarajan, Runtime dependence computation and execution of loops on heterogeneous systems[1] Arhivirano na sajtu Wayback Machine (6. oktobar 2015)
  5. ^ X. Zhuang, A. E. Eichenberger, Y. Luo, Kevin O’Brien, Kathryn, Exploiting Parallelism with Dependence-Aware Scheduling
  6. ^ „Automatic parallelism and data dependency”. Arhivirano iz originala 14. 07. 2014. g. Pristupljeno 08. 01. 2016. 
  7. ^ Rünger, Gudula (2006). „Parallel Programming Models for Irregular Algorithms”. Parallel Algorithms and Cluster Computing. 52: 3—23. doi:10.1007/3-540-33541-2_1. 
Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Аутоматска_паралелизација&oldid=26815994”