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:

• Littleov zakon,
• Amdahlov zakon,
• Gustafsonov zakon.

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
  • programski alati: asembler -> C i C++ -> Java i Python

• era višejezgrenih sustava traje otprilike do 2011.

  • primjeri: AMD Phenom serija, AMD FX serija, Intel Core serija
  • razvoj omogućuju: paralelizacija softvera, Mooreov zakon, SMP arhitektura
  • razvoj ograničavaju: potošnja energije, (ne)paralelnost softvera, skalabilnost
  • programski alati: pthreads -> OpenMP -> MPI

• 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

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 su nekad bile značajne; kompletna podrška za MPI-1, djelomična podrška za MPI-2

  • LAM/MPI
  • MPICH1, koji je postao temelj za MVAPICH

• korišten u znanosti i istraživanju, dostupno puno tutoriala

  • Lawrence Livermore National Laboratory tutorial
  • Argonne National Laboratory tutorial
  • Kansas University tutorial
  • Torsten Hoefler (ETH Zürich) tutorials
  • Google pretraga za "MPI tutorial" daje još mnogo rezultata...

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

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.

Author: Vedran Miletić