Section author: Vedran Miletić
Osnovni pojmovi paralelnog, distribuiranog i heterogenog računarstva¶
Paralelna obrada¶
Paralelizacija čini da se više radnji, operacija ili proračuna izvodi istovremeno. Radnje, operacije ili proračuni moraju biti takvi da je paralelizacija moguća. Ako to nije slučaj, vrijeme izvođenja paralelne varijante biti će jednako serijskoj, ili čak duže.
Paralelizacija se može izvesti na tri razine:
procesi
procesne niti (engl. threads)
koprogrami (engl. coroutines), vlakna (engl. fibers) ili zelene niti (engl. green threads)
Općenito, tri zakona govore o mogućnosti kraćenja vremena izvođenja korištenjem paralelizacije:
Primjene paralelne obrade¶
Tipovi problema na koje se često primjenjuju metode paralelnog računarstva (preuzeto sa Wikipedijine stranice o paralelnom računanju):
gusta i rijetka linearna algebra,
spektralne metode (kao što je Cooley-Tukey brza Fourierova transformacija),
problemi međudjelovanja čestica (kao što je Barnes-Hutova simulacija),
problemi kvadratične rešetke (kao što su Boltzmannove metode rešetke),
problemi poligonalna rešetke (kao što se nalaze u analizi konačnih elemenata),
Monte Carlo simulacije,
kombinatorna logika (kao što su brute-force kriptografske tehnike),
obilazak grafa (kao što su algoritmi pretraživanja),
dinamičko programiranje,
metode grananja i ograničavanja,
multi-start metaheuristike,
grafički modeli (kao što je traženje skrivenih Markovljevih modela i konstrukcija Bayesovih mreža),
simulacije konačnih automata.
Razvoj paralelnih računala¶
Evolucija računalnih sustava prema AMD-u uključuje tri odvojene ere (preuzeto iz prezentacije AMD Fusion Fund Overview):
era jednojezgrenih sustava traje otprilike do 2004.
primjeri: AMD Athlon XP i stariji, Intel Pentium 4 i stariji
razvoj omogućuju: Mooreov zakon, povećanje napona, Dennardova teorija smanjivanja MOSFET-a
razvoj ograničavaju: potrošnja energije, složenost arhitekture
era višejezgrenih sustava traje otprilike do 2011.
era heterogenih sustava je trenutno hit tema u akademskom istraživačkom i nastavnom okruženju
primjeri: AMD Llano i Trinity (A, E i C serije), Intel Sandy Bridge i Ivy Bridge (Core i3/i5/i7-2000 i 3000 serije), NVIDIA Tegra
razvoj omogućuju: programabilni Shaderi, masivna paralelizacija softvera, energetski efikasni GPU-i, GPGPU
razvoj ograničavaju: načini programiranja, pretek zbog komunikacije
programski alati: NVIDIA Cg, Microsoft HLSL -> NVIDIA CUDA, Microsoft DirectCompute -> OpenCL
Distribuirano računarstvo¶
Arhitektura distribuiranih sustava¶
Todo
Ovaj dio treba napisati.
Cluster dio Bure je primjer distribuiranog sustava sastavljenog od više računala povezanih mrežom.
Standard Message Passing Interface (MPI)¶
sučelje za paralelizaciju aplikacija zasnovano na razmjeni poruka (engl. message passing)
procesi komuniciraju putem cijevi, nema dijeljene memorije
jednostavno raspodijeliti procese za izvođenje na više računala
donekle sličan način rada kao modul
multiprocessing
u Pythonu
aplikacija se pokreće korištenjem pomoćnih alata kao MPI posao (engl. MPI job)
svaki posao se sastoji od više procesa na jednom ili više računala
kod većih sustava alati kao HTCondor služe za redanje više MPI poslova za izvođenje
otvoreni standard, specifikacija dostupna na MPI Forumu
zadnja verzija standarda je MPI-3
najkorištenije značajke dio (koje ćemo i mi koristiti) su dio i MPI-1 verzije standarda; novosti iz MPI-2 se nešto rjeđe koriste
podržan u mnogim jezicima: C, C++ (Boost.MPI), Fortran, Java (MPJ), Python, Perl, Ruby, …
dvije implementacije se aktivno razvijaju; podrška za MPI-2 je postoji već dugo vremena, podrška za MPI-3 je dostupna odnedavno
Open MPI (najpopularnija implementacija, nasljednik LAM/MPI)
MPICH2 i MPICH 3 (također vrlo popularna implementacija, nasljednik MPICH)
velika prednost: standardizirano sučelje => kompatibilnost na razini izvornog koda
dvije implementacije se samo održavaju; kompletna podrška za MPI-1, djelomična podrška za MPI-2
korišten u znanosti i istraživanju, dostupno puno tutoriala
Heterogeno računarstvo¶
Arhitektura heterogenih sustava¶
Heterogeno računalo (kakvo postoji u GPGPU dijelu Bure) ima dva dijela:
domaćin (engl. host), u našem slučaju osnovni procesor
uređaj (engl. device), u našem slučaju grafički procesor
U budućnosti se očekuje hardver i s tim programske paradigme kod kojih će memorija domaćina i uređaja biti dijeljena i način programiranja će zbog toga biti biti nešto pojednostavljen, ali svi koncepti koje u nastavku opisujemo, kao i način razmišljanja koji koristimo, i dalje će vrijediti.
Osnvoni procesor je dobar za serijsku obradu, a grafički procesor je dobar za masivnu paralelnu obradu podataka. Heterogeni sustav kombinira oba.
HSA Foundation¶
AMD, ARM, Imagination, MediaTek i Texas Instruments su 12. lipnja 2012. godine u gradu Bellevu u saveznoj državi Washington osnovali HSA Foundation. Zakladi su se vremeno pridružili Vivante, Sonics, Apical, MulticoreWare, Symbio, Arteris, Qualcomm, DMP, LG Electronics, Ceva i Tensilica.
Iako heterogeno računarstvo (engl. heterogeneous computing) ne počinje s heterogenom sustavskom arhitekturom (engl. Heterogeneous System Architecture, HSA), ona je danas vjerojatno najbolji primjer istoga. Na stranicama zaklade HSA Foundation može se pronaći opis temeljnih značajki HSA i argumentacija zašto HSA predstavlja evoluciju računarstva. Prva specifikacija je objavljena 29. svibnja 2013. godine.
Tehnologije NVIDIA Compute Unified Device Architecture (CUDA) i OpenCL¶
Todo
Ovaj dio treba napisati.
Sadašnjost i budućnost heterogenih sustava¶
Pored toga, AMD opisuje razvoje heterogene arhitekture sustava kroz 4 etape (preuzeto iz AMD-ove prezentacije HSA Overview):
fizička integracija (2011. godine, Llano) – CPU i GPU nalaze se na jednom siliciju; CPU i GPU dijele jedinicu za upravljanje memorijom
optimizacija platforme (2012. godina, Trinity i 2013. godina, Richland) – CPU i GPU dijele cjelokupnu količinu memorije, GPU može alocirati koliko god je potrebno; CPU i GPU imaju zajedničko dinamičko upravljanje energijom
arhitekturalna integracija (2014. godina, Kaveri) – CPU i GPU vide unificirani memorijski prostor, pokazivači se mogu prosljeđivati u oba smjera; GPU može pristupati CPU međuspremnicima
sustavska integracija (2015. godina, Carrizo) – GPU multitasking, specifično mogućnost da se izvede context switch između grafičkih i compute aplikacija; GPU pre-emption, specifično mogućnost da se zaustavi proces koji se dugo izvodi radi procesa koji će se izvoditi kraće, prioriteti izvođenja aplikacija
Komercijalni čip koji sadrži CPU i GPU na jednom siliciju, zasnovan na heterogenoj sustavskoj arhitekturi, AMD naziva APU. Intel i NVIDIA, unatoč tome što imaju vrlo slične čipove, zasad ovaj termin nisu prihvatili.