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:

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 raralelnih računala

Evolucija računalnih sustava prema AMD-u uključuje tri odvojene ere (preuzeto iz prezentacije AMD Fusion Fund Overview):

Distribuirano računarstvo

Arhitektura distribuiranih sustava

Todo

Ovaj dio treba napisati.

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

Iako AMD nije izmislio termine heterogeno računarstvo (engl. heterogeneous computing) i heterogena sustavska arhitektura (engl. heterogeneous system architecture, HSA), na svojim stranicama opisuje oba pojma:

Arhitektura heterogenih sustava

Računalo s kojim ćemo raditi ima dva dijela:

  • domaćin (engl. host), u našem slučaju CPU

  • uređaj (engl. device), u našem slučaju GPU

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.

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 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 (2013. 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 (2014. godina) – 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.