Koncept paralelnog računarstva je opšta organizaciona šema. Paralelni računarski sistemi

Paralelni računarski procesi i sistemi (predavanje 13)

Vrste paralelizma

Paralelna obrada podataka ima dva tipa: cevovod i stvarni paralelizam.

Paralelna obrada. Ako određeni uređaj izvrši jednu operaciju u jedinici vremena, tada će izvršiti hiljadu operacija u hiljadu jedinica. Ako pretpostavimo da postoji pet identičnih nezavisnih uređaja sposobnih da rade istovremeno, onda sistem od pet uređaja može izvršiti istih hiljadu operacija ne u hiljadu, već u dvije stotine jedinica vremena.

Obrada transporterom. Šta je potrebno da se dodaju dva realni brojevi, predstavljeno u obliku s pomičnim zarezom? Puno malih operacija kao što su poređenje naloga, usklađivanje naloga, dodavanje mantisa, normalizacija itd. Procesori prvih računara izvodili su sve ove „mikrooperacije“ za svaki par argumenata, jedan za drugim, sve dok nisu došli do konačnog rezultata, pa tek onda prešli na obradu sledećeg para pojmova. Ideja cjevovodne obrade je da se izoluju pojedinačne faze izvođenja opće operacije, a svaka faza, nakon što završi svoj posao, prenijela bi rezultat na sljedeću, dok bi istovremeno primala novi dio ulaznih podataka. Postoji očigledan dobitak u brzini obrade zbog kombinacije prethodno raspoređenih operacija. Pretpostavimo da u jednoj operaciji postoji pet mikrooperacija, od kojih se svaka izvodi u jednoj jedinici vremena. Ako postoji jedan nedjeljiv serijski uređaj, tada će obraditi 100 parova argumenata u 500 jedinica. Ako se svaka mikrooperacija razdvoji u zasebnu fazu (ili drugačije nazvanu faza) transportnog uređaja, tada će se u petoj jedinici vremena, u različitim fazama obrade takvog uređaja, nalaziti prvih pet parova argumenata , a cijeli set od sto parova bit će obrađen za 5 + 99 = 104 jedinice vremena - ubrzanje u odnosu na serijski uređaj je skoro pet puta (na osnovu broja faza cevovoda).

Čini se da se procesiranje cjevovoda može uspješno zamijeniti običnim paralelizmom, za koji umnožavamo glavni uređaj onoliko puta koliko je predviđeno da se dodijeli broj faza cjevovoda. Ali povećanjem broja uređaja pet puta, značajno povećavamo i obim opreme i njenu cijenu.

Implementacija paralelnih sistema

Performanse računara su eksponencijalno rasle od 1945. do danas (na osnovu proseka svakih 10 godina). Arhitektura računara je pretrpela značajne promene, prelazeći sa serijske na paralelnu.

Performanse računara su direktno povezane sa vremenom potrebnim za obavljanje osnovnih funkcija i brojem ovih osnovnih operacija koje se mogu izvoditi istovremeno. Vrijeme izvršenja jedne jednostavne instrukcije je na kraju ograničeno.

Lako je zaključiti da se ne možete ograničiti na povećanje brzine samo na račun takta procesora. Ovisnost o procesorima na kraju vodi u ćorsokak. Druga strategija u ovoj oblasti je korištenje internog paralelizma u procesorskom čipu. Ali takva tehnologija je veoma skupa. Moderni superračunari su uglavnom zasnovani na ideji korištenja velikog broja relativno jeftinih procesora koji su već dostupni.

Ovo takođe uključuje sisteme kao što su: superračunari opremljeni hiljadama procesora; mreže radnih stanica; višeprocesorske radne stanice itd.

Multicomputer - ovo je određeni iznos von Neumann mašine(čvorovi) međusobno povezani mrežom. Svaki računar pokreće svoj program. Ovi programi mogu pristupiti lokalnoj memoriji i mogu slati i primati poruke preko mreže. Poruke koje se koriste za komunikaciju između računara su ekvivalentne operacijama čitanja ili pisanja iz udaljene memorije. U idealizovanoj mreži, vreme isporuke poruke između mašina ne zavisi od udaljenosti između čvorova ili mrežnog saobraćaja, već zavisi od dužine pisma koje se šalje.

Definirajući parametar višekompjuterskog modela je da je pristup lokalnoj (isti čvor) memoriji jeftiniji od pristupa udaljenoj (smještenoj u drugom čvoru) memoriji. One. Operacije čitanja i pisanja su jeftinije od slanja ili primanja poruka. Stoga je poželjno da se lokalnim podacima pristupa mnogo češće nego udaljenim podacima. Ovo osnovno svojstvo softvera naziva se lokalnost. Vrijednost lokaliteta ovisi o odnosu cijene udaljenog pristupa i lokalnog pristupa.

Ostali modeli automobila. Pogledajmo najvažnije računarske arhitekture. Multikompjuter je vrlo sličan onome što se često naziva MIMD (Multiple Instruction Multiple Data) računar distribuirane memorije. MIMD znači da svaki procesor može obraditi poseban tok instrukcija preko vlastitih lokalnih podataka. Distribuirana memorija znači da je memorija raspoređena među procesorima. Osnovna razlika između MIMD računara i multikompjutera je u tome što cena isporuke poruke između dva čvora ne zavisi od lokacije čvora i mrežnog saobraćaja. Glavni predstavnici ove klase: IBM SP, Intel Paragon, Thinking Machines CM 5, Cray T 3D, Meiko CS-2 i CUBE.

Druga klasa superračunara je multiprocesorski ili MIMD računar sa zajedničkom memorijom. U multiprocesoru, svi procesori dijele pristup zajedničkoj memoriji, obično preko magistrale ili kroz hijerarhiju magistrale. U modelu idealiziranog paralelnog stroja sa slučajnim pristupom (PRAM), koji često koristi teoretski proučavane paralelne algoritme, svaki procesor može pristupiti bilo kojem memorijskom elementu u isto vrijeme. Ova arhitektura obično uključuje neki poseban oblik memorijskog uređaja. Broj pristupa zajedničkoj memoriji se smanjuje pohranjivanjem kopija podataka kojima se često pristupa u keš memoriju povezan sa svakim procesorom.

Pristup ovoj keš memoriji je mnogo brži od pristupa dijeljenoj memoriji, stoga je lokacija vrlo važna. Programi dizajnirani za više računara mogu jednako efikasno raditi na višeprocesorima jer zajednička memorija omogućava efikasno prenošenje poruka. Predstavnici ove klase su Silicon Graphics Challenge, Sequent Symmetry i mnoge multiprocesorske radne stanice.

Specijalizovanija klasa paralelnih računara su SIMD (Single Instruction Miltiple Data) računari. U SIMD mašinama, svi procesori rade sa istim tokom instrukcija na različitim delovima podataka. Ovaj pristup može smanjiti složenost softvera i hardver, ali to ima smisla samo za specijalizovane probleme koje karakteriše visok stepen regularnosti, kao što su obrada slike i određene vrste digitalnog modeliranja. Algoritmi koji se primjenjuju na multikompjuterima općenito se ne mogu efikasno izvršavati na SIMD računarima.

Neuroračunarski sistemi.

Neuroračunarski uređaj je sistem čije je funkcionisanje maksimalno usmjereno na implementaciju algoritama neuronske mreže. Glavna razlika između neurokompjutera i drugih računarskih sistema je obezbeđivanje visokog paralelizma proračuna kroz korišćenje specijalizovane logičke osnove neuronske mreže ili specifičnih arhitektonskih rešenja. Korišćenje mogućnosti predstavljanja algoritama neuronske mreže za implementaciju na logičkoj osnovi neuronske mreže je glavni preduslov za naglo povećanje performansi neuroračunara.

Trenutno se razvoj digitalnih neuroračunara najaktivnije odvija u sljedećim područjima:

· softverska emulacija algoritama neuronske mreže zasnovana na upotrebi konvencionalnih računarskih objekata i softver za modeliranje neuronskih mreža;

· softverska i hardverska emulacija neuronskih mreža zasnovana na standardnim računarskim alatima sa priključnom jedinicom virtuelne neuronske mreže koja izvodi osnovne neurooperacije i softverom koji obavlja opšte kontrolne funkcije;

· hardverska implementacija neuronskih mreža.

Unatoč činjenici da se najveći učinak u implementaciji algoritama neuronske mreže može postići samo upotrebom neuroračunara trećeg smjera, njihova široka upotreba ograničena je visokom tehnologijom. Na primjer, neurokompjuter Synaps1 je jedan od predstavnika neuroračunara trećeg smjera, ima višeprocesorsku arhitekturu, originalan dizajn memorijskog podsistema i koristi procesore signala i posebne signalne matrične procesore MA16 za obavljanje računskih operacija. Zbog toga su performanse neurokompjutera iznosile nekoliko milijardi množenja i sabiranja u sekundi. Softver Ovaj sistem uključuje Synaps1 OS sa bibliotekom neuroalgoritama, kao i softver: osnovnu NS biblioteku, kompajler za neuroalgoritamski programski jezik (nAPL) (skup bibliotečkih funkcija za C++) itd. Primijenjena istraživanja su pokazala da korištenje neuroračunara trećeg smjera omogućava povećanje performansi konvencionalnih računarskih sistema za najmanje tri reda veličine i simulaciju neuronskih mreža sa milionima veza. Na primjer, Synaps1 vam omogućava da simulirate neuronsku mrežu sa 64 miliona sinapsi koristeći različite funkcije aktivacije.

Postoje dvije klase kompjuterskih sistema koji se ponekad koriste kao paralelni računari lokalnoj mreži(LAN), u kojem su računari koji se nalaze u fizičkoj blizini (na primjer, ista zgrada) povezani brzom mrežom, i globalna mreža(WAN), u koji su povezani geografski udaljeni računari. Iako sistemi ovog tipa donose dodatne probleme kao što su sigurnost, pouzdanost, mogu se smatrati za različite namjene kao multiračunari, ali uz visoku cijenu. daljinski pristup.

Poteškoće u korištenju paralelnih sistema

Ogromne performanse paralelnih računara i superračunara više su nego nadoknađene teškoćama njihovog korišćenja.

Imate program i pristup, recimo, računaru sa 256 procesora. šta očekuješ? Da, jasno je: sasvim opravdano očekujete da će se program izvršavati 256 puta brže nego na jednom procesoru. Ali to je ono što se najvjerovatnije neće dogoditi.

Amdahlov zakon. Pretpostavimo da je u programu dio operacija koje treba izvršiti uzastopno jednak f, gdje je 0<=f <=1 (при этом доля понимается не по статическому числу строк кода, а по числу операций в процессе выполнения). Крайние случаи в значениях f соответствуют полностью параллельным (f = 0) и полностью последовательным (f = 1) программам. Тогда для того, чтобы оценить, какое ускорение S может быть получено на компьютере из "p" процессоров при данном значении f, можно воспользоваться законом Амдала: если 9/10 программы исполняется параллельно, а 1/10 по-прежнему последовательно, то ускорения более, чем в 10 раз получить в принципе невозможно вне зависимости от качества реализации параллельной части кода и числа используемых процессоров (10 получается только в том случае, когда время исполнения параллельной части равно 0).

Posljedica Amdahlovog zakona. Da bi se izvođenje programa ubrzalo za q puta, potrebno je ubrzati najmanje q puta ne manje od (1-1/q)-tog dijela programa. Stoga, ako želite ubrzati program 100 puta u odnosu na njegovu sekvencijalnu verziju, onda morate postići ništa manje ubrzanje za najmanje 99,99% koda!

Dakle, učiniti da paralelni računarski sistem radi sa maksimalnom efikasnošću na određenom programu nije lak zadatak, jer je potrebno pažljivo uskladiti strukturu programa i algoritama sa arhitektonskim karakteristikama paralelnih računarskih sistema.

Programiranje paralelnih sistema

Model von Neumannove mašine pretpostavlja da procesor izvršava niz instrukcija. Instrukcije mogu specificirati, pored različitih aritmetičkih operacija, adrese podataka koji se čitaju/zapisuju u memoriju i/ili adresu sljedeće instrukcije koja će se izvršiti. Iako je računar moguće programirati samo u smislu ovog osnovnog modela, ova metoda je pretjerano složena za većinu namjena zbog činjenice da moramo pratiti milione memorijskih pozicija i orkestrirati izvršenje hiljada mašinskih instrukcija. Kao posljedica toga, primjenjuje se tehnika modularnog dizajna, pri čemu se složeni programi kreiraju od jednostavnih komponenti, a komponente su strukturirane u smislu apstrakcija višeg nivoa (kao što su strukture podataka, iterativne petlje i procedure). Apstrakcije (npr. procedure) olakšavaju eksploataciju modularnosti omogućavajući manipulisanje objektima bez narušavanja njihove unutrašnje strukture. Tako se prave jezici visokog nivoa, kao što su Fortran, C, Ada i Java, koji omogućavaju razvoj u smislu ovih apstrakcija, koje se automatski prevode u izvršni kod. Paralelno programiranje uvodi dodatne izvore složenosti: ako moramo programirati na najnižem nivou, ne samo da moramo povećati broj izvršenih instrukcija, već i upravljati izvršavanjem hiljada procesora i koordinirati milione međuprocesorskih komunikacija. Stoga su apstrakcija i modularnost barem jednako važni kao kod sekvencijalnog programiranja. Zapravo, ističemo modularnost kao četvrti osnovni zahtjev za paralelni softver, pored paralelizma, skalabilnosti i lokalnosti.

Glavne apstrakcije koje se koriste u paralelnom programiranju svode se na zadatke i kanale:

1. Paralelno računanje se sastoji od jednog ili više zadataka. Zadaci se izvršavaju paralelno. Broj zadataka se može promijeniti tokom izvršavanja programa.

2. Zadatak izolira sekvencijalni program i lokalnu memoriju. Pored toga, skup ulaza i izlaza definira njegov interfejs u svom okruženju.

3. Zadatak može izvršiti četiri osnovne radnje pored čitanja i pisanja u lokalnu memoriju: poslati poruku na svoje izlazne portove, primiti poruku sa svojih ulaznih portova, kreirati nove zadatke i uništiti (dovršiti) zadatak.

4. Operacija slanja poruke je asinhrona i završava se odmah. Operacija primanja je sinhrona i uzrokuje izvršavanje zadatka, blokirajući proces dok se poruka ne primi.

5. I/O parovi mogu biti povezani porukama u redu čekanja koje se nazivaju kanali. Kanali se mogu kreirati i brisati, a reference na kanale (portove) mogu biti uključene u poruke tako da se povezanost dinamički mijenja.

6. Poslovi se mogu mapirati na fizičke procesore na različite načine; display aplikacija ne utiče na semantiku programa. Konkretno, više poslova se može mapirati na jedan procesor (može se zamisliti i da se jedan zadatak može mapirati na više procesora, ali ova mogućnost ovdje nije uzeta u obzir.)

Apstrakcija zadataka zahtijeva svojstvo lokaliteta: podaci sadržani u lokalnoj memoriji zadatka su „zatvoreni“; ostali podaci se „brišu“. Apstrakcija kanala pruža mehanizam za određivanje koji podaci iz jednog zadatka moraju biti izračunati prije nego što se drugi zadatak može pokrenuti. (Ovo karakterizira ovisnost o podacima). Model zadataka i kanala također ima neka druga svojstva:

Performanse . Apstrakcije sekvencijalnog programiranja, kao što su procedure i strukture podataka, su efikasne jer se mogu jednostavno i efikasno preslikati na von Neumann računar. Zadaci i kanali imaju sličnu direktnu distribuciju u multikompjuteru. Zadatak predstavlja dio koda koji se može izvršiti uzastopno na jednom procesoru. Ako se dva zadatka koji dijele kanal mapiraju na druge procesore, veza kanala se implementira kao međuprocesorska veza; ako su mapirani na isti procesor, mogu se koristiti neki efikasniji mehanizmi.

Nezavisnost distribucije . Budući da zadaci komuniciraju koristeći isti mehanizam (kanale) bez obzira na lokaciju zadatka, rezultat izračunat od strane programa ne ovisi o tome gdje se zadatak izvršava. Stoga se algoritmi mogu dizajnirati i implementirati bez brige o broju procesora na kojima će raditi; u stvari, algoritmi su često dizajnirani da kreiraju mnogo više zadataka nego procesori. Ovo je jednostavan način za postizanje skale: kako se broj procesora povećava, broj zadataka po procesoru se smanjuje, ali sam algoritam ne treba mijenjati. Kada postoji više zadataka nego što bi procesori mogli da riješe da maskiraju kašnjenja u komunikaciji, osiguravaju se druga izračunavanja koja se mogu izvesti dok je komunikacija u toku radi pristupa udaljenim podacima.

Modularnost. U modularnom programiranju, različite programske komponente se razvijaju odvojeno kao nezavisni moduli, a zatim se kombinuju u potpuni program. Interakcija između modula je ograničena na jasno definisana sučelja. Shodno tome, modularne implementacije se mogu mijenjati bez modifikacije drugih komponenti, a svojstva programa mogu se odrediti iz specifikacije njegovih modula i koda koji te module povezuje zajedno. Kada se modularni razvoj uspješno primjenjuje, smanjuje se složenost softvera i olakšava ponovna upotreba koda.

Determinizam. Algoritam ili program je deterministički ako, kada se izvršava sa određenim ulazom, uvijek proizvodi isti izlaz. Nedeterministički je ako višestruka izvršenja istog ulaza mogu proizvesti različiti izlaz. Dok je nedeterminizam ponekad koristan i treba ga podržati, model paralelnog programiranja koji olakšava pisanje determinističkih programa je vrlo poželjan. Deterministički programi obično su razumljiviji. Također, prilikom provjere ispravnosti treba izračunati samo jednu sekvencu izvršavanja paralelnog programa, a ne sve moguće sekvence izvršavanja.

Trenutna verzija stranice još nije potvrđena

Trenutna verzija stranice još nije potvrđena od strane iskusnih učesnika i može se značajno razlikovati od verzije verifikovane 5. oktobra 2014.; provjere su potrebne.

Parallel Computing- metoda organizovanja računarskog računarstva, u kojoj se programi razvijaju kao skup računarskih procesa u interakciji koji rade paralelno (istovremeno). Pojam pokriva skup pitanja paralelizma u programiranju, kao i stvaranje efikasnih hardverskih implementacija. Teorija paralelnog računanja predstavlja granu primijenjene teorije algoritama.

Postoje različiti načini za implementaciju paralelnog računanja. Na primjer, svaki računarski proces može biti implementiran kao proces operativnog sistema, ili računarski procesi mogu biti zbirka niti izvršenja unutar jednog procesa OS. Paralelni programi se mogu fizički izvršavati ili sekvencijalno na jednom procesoru - naizmjenično mijenjajući korake svakog računskog procesa, ili paralelno - dodjeljivanjem jednog ili više procesora (lociranih u blizini ili distribuiranih u računarskoj mreži) svakom računarskom procesu.

Glavna poteškoća u dizajniranju paralelnih programa je osigurati ispravan slijed interakcija između različitih računarskih procesa, kao i koordinaciju resursa koji se dijele između procesa.

U nekim sistemima paralelnog programiranja, prijenos podataka između komponenti je skriven od programera (na primjer, korištenjem mehanizma obećanja), dok u drugim mora biti eksplicitno specificiran. Eksplicitne interakcije se mogu podijeliti u dvije vrste:

Paralelni sistemi za prosleđivanje poruka su često lakši za razumevanje od sistema deljene memorije i generalno se smatraju superiornim metodom paralelnog programiranja. Postoji širok spektar matematičkih teorija za proučavanje i analizu sistema za prenošenje poruka, uključujući model aktera i različite vrste proračuna procesa. Razmjena poruka se može efikasno implementirati na simetričnim multiprocesorima sa ili bez zajedničke koherentne memorije.

Paralelizam distribuirane memorije i paralelizam prenošenja poruka imaju različite karakteristike performansi. Tipično (ali ne uvijek), troškovi memorije procesa i vremena prebacivanja zadataka manji su za sisteme za prosljeđivanje poruka, ali je prosljeđivanje poruka skuplje od poziva procedura. Ove razlike su često zasjenjene drugim faktorima koji utiču na performanse.

Plaksin M.A.

Nacionalni istraživački univerzitet Visoka ekonomska škola (filijala u Permu), Perm, doktor nauka, vanredni profesor Odseka za informacione tehnologije u poslovanju, mapl @ list. ru

"SUPERKOMPJUTERI" VS "PARALELNO PROGRAMIRANJE". “PARALELNO PROGRAMIRANJE” VS “KOLABORATIVNA AKTIVNOST”. KAKO U SREDNJOJ ŠKOLI UČITI TEMU “PARALELNO RAČUNARSTVO”?

KLJUČNE RIJEČI

Računarstvo, paralelno programiranje, paralelno računarstvo, paralelni algoritmi, superračunari, osnovna škola, srednja škola, TRIZformashka.

ANOTATION

Članak je posvećen pitanju uključivanja teme „paralelno računanje“ u školski kurs informatike. Naveden je niz problema koji se javljaju u ovom slučaju, razmotrena je svrha proučavanja teme, izbor materijala, neki prijedlozi nastavnih metoda, mehanizmi testiranja predložene metodologije i stečeno iskustvo. Pitanje mjesta ovog materijala u nastavnom planu i programu nije obrađeno.

Sadašnja faza razvoja računarstva povezana je sa masovnim širenjem paralelizma proračuna na svim nivoima (klasteri sa više mašina, višeprocesorski računari, višejezgarni procesori).

Masovno širenje paralelizma ima ozbiljne posljedice koje tek treba identificirati i analizirati. Počnimo s navođenjem nekih teorijskih problema.

Moderna teorija algoritama nastala je s konceptom sekvencijalnog algoritma na umu. Kako će odbijanje zahtevanja niza koraka uticati na koncept algoritma?

Najmanje posljednjih 20 godina, koncept „algoritma“ je uveden u škole neraskidivo povezan s konceptom „izvođača“. Ovo je prirodno za sekvencijalni algoritam. Šta učiniti s paralelnim algoritmom? Da li ga izvodi jedan izvođač ili grupa izvođača? Da budemo konkretni, uzmimo za primjer kompjuterski program obuke "Tank Crew". U ovom programu od studenta se traži da programira radnje tenkovske posade koju čine tri osobe: topnik, vozač i utovarivač. Svaki od njih ima svoj komandni sistem. Da bi se izvršila borbena misija (pogoditi sve mete), svi članovi posade moraju djelovati usklađeno. Za primjer igrališta za program Tank Crew, pogledajte sliku 1.

Pitanje: treba li ova tri aktera smatrati nezavisnim izvođačima ili kao tri komponente (uređaja) jednog kompleksnog izvođača? Za tenkovsku posadu druga opcija se čini prirodnijom, jer nijedan lik ne može sam izvršiti zadatak. Ali što ako igra postane složenija, a borbena misija se dodijeli na dva tenka odjednom? Za tri tenka? Tri člana jedne ekipe mogu se smatrati kao tri dijela jednog izvođača. Ali svaka ekipa je očigledno samostalan izvođač. To znači da će paralelni algoritam za nekoliko rezervoara biti izvršen od strane grupe izvršitelja odjednom. Ispada da je za paralelni algoritam potrebno razmotriti obe mogućnosti: izvršavanje paralelnih radnji od strane jednog izvršioca i od strane grupe izvršilaca. U slučaju tenk posade, povlačenje linije je lako. Izvođač je onaj koji je u stanju da riješi zadatak. Ovaj izvršitelj se može sastojati od nekoliko komponenti, od kojih svaka obavlja određeni dio zadatka, ali ne može samostalno izvršiti cijeli zadatak bez pomoći drugih komponenti. Ali da li će razdvajanje “cjelih izvođača” i dijelova složenog izvođača uvijek biti tako jednostavno, sada je nemoguće reći.

Fajl 1*ra Prozor O programu

Vpolyet everything

Bbno.n«fTb do označene linije

Povratak na početnu stranicu**"

bi popnlt korak po korak (nakon izvršavanja „.order komande nesykoa^“ dugme gV ygolg „n-b next uwr“ će biti pritisnuto)

Ë GGVD iTHWTt. poseban korak

Informacije korak po korak

Fig.1. Fragment igrališta programa Tank Crew

Identifikacija dijelova izvođača koji su sposobni za samostalne radnje zahtijeva da se ti dijelovi nekako imenuju. Štaviše, ime mora dozvoliti ponavljanje, budući da sami glumački dijelovi izvođača mogu imati složenu strukturu.

Potrebno je dogovoriti termin za određivanje grupe zadružnih izvođača. Termin “komanda” nije prikladan; on se povezuje sa “sustavom komandi izvršioca” i sa “komandama centralnog procesora”. "Kolektiv izvođača"? "Brigada izvođača"?

Sh. Algoritam

n Udaranje1"; Driver Charger

1 Izmjerite orun* na “master sgkll V Stop V Charge 1

g Pci V Stop V Punjenje 2

3 Veleprodaja! V Okrenite u smjeru kazaljke na satu za 90 stepeni V Napunite 1 V

L V V prvo V punjenje? V

5 Vatra! V Stop V Punjenje 1

Í P^chm V St*p V Zaryasya? V

7 Vatra! V Stop V Punjenje 1 V

3 Pa^ V Okrenite u smjeru kazaljke na satu za 45 stepeni V Napunite 2 V

S Pauza V Start V Pauza V

10 Pvdea V Naprijed V Pauza ¿d

11 Plrl V Naprijed V Pauza V

12 Paum V Okrenite u smjeru kazaljke na satu za 45 stupnjeva V Pauza V

13 Padm V Naprijed V Pauza V

14 V

Fig.2. Fragment programa za “Tank Crew” (primjer komandnih linija) Tradicionalni koncept “sistema komande izvršioca” (SCS) i koncept samog tima zahtijevaju poboljšanje. Ako vjerujemo da tri člana posade tenka čine jednog izvođača, šta onda treba smatrati SKI-jem ovog izvođača? A šta se smatra timom? Ili ostavite koncept SKI za svaki lik? Odnosno, ovo više nije sistem komandi IZVRŠITELJA, već sistem komandi jedne od komponenti izvođača (za koju još nema imena)?

Zgodno je proširiti koncept tima na „liniju komandi“. Za primjer komandnih linija posade tenkova, pogledajte sliku 2. Međutim, koncept “linije naredbi” dobro funkcionira samo za linearne algoritme. U drugim slučajevima, vladari se formiraju dinamički. Nemoguće ih je prikazati u obliku vizualne tablice.

Među svojstvima algoritama izdvaja se nova praktično značajna karakteristika: sposobnost paralelizacije. Pitanje koje pojašnjava je o mogućem stepenu paralelizacije (u kojoj meri ima smisla povećavati broj procesora prilikom izvršavanja datog algoritma).

Posebno pitanje su metode za paralelizaciju postojećih sekvencijalnih algoritama.

Sve donedavno, paralelno programiranje je bila oblast malog broja visokokvalifikovanih sistemskih programera. Danas to postaje dio profesionalne kompetencije. Ali tehnologija paralelnog programiranja značajno se razlikuje od tradicionalnog sekvencijalnog programiranja. U prilog ovoj izjavi, slijedeći L.L. Bosova, citiraćemo najvećeg ruskog specijaliste u oblasti paralelnog računarstva V.V. Vojvodina:

„... Ovladavanje računarskom tehnologijom paralelne arhitekture... od strane mladih stručnjaka dolazi sa velikim poteškoćama. Smatramo da je to zbog činjenice da upoznavanje sa paralelnim računarstvom, kao i edukacija iz ove oblasti uopšte, ne počinje od toga odakle treba početi. Osim toga, ono od čega trebate početi nije pokriveno ni u jednom kursu. Sposobnost brzog rješavanja problema korištenjem računarske tehnologije s paralelnom arhitekturom prisiljava korisnike da promijene cijeli svoj uobičajeni stil interakcije s računarima. U poređenju, na primer, sa personalnim računarima i radnim stanicama, skoro sve se menja: koriste se drugi programski jezici, većina algoritama je modifikovana, od korisnika se traži da obezbede brojne nestandardne i teško dostupne karakteristike zadataka koji se rešavaju, interfejs prestaje da bude prijateljski, itd. Važna činjenica je da neuvažavanje u potpunosti novih uslova rada može značajno smanjiti efikasnost upotrebe nove i, osim toga, prilično skupe opreme.”

„Važno je samo da učenik što ranije nauči da postoje i drugi načini organizacije računskih procesa, a ne samo sekvencijalno izvođenje „operacija po operaciju“, da je na ovim drugim metodama izgrađena najmoćnija moderna kompjuterska tehnologija, da je samo takvom tehnologijom moguće rješavati velike probleme.industrijske i naučne zadatke itd. Važno je, prije svega, što ranije skrenuti pažnju učenika na potrebu kritičkog stava prema filozofiji sekvencijalnog računarstva. Na kraju krajeva, to je filozofija kojom se moraju baviti tokom cijelog svog obrazovanja, kako u školi tako i na fakultetu. I upravo ta filozofija ometa razumijevanje karakteristika rada na kompjuterima paralelne arhitekture.”

Danas su nam potrebne metode za masovnu obuku u tehnologiji paralelnog programiranja. Autor ovog članka smatra da je u procesu učenja došlo vrijeme za revoluciju u odnosu između sekvencijalnog i paralelnog programiranja. Do sada smo prvo učili sekvencijalno programiranje, a zatim - paralelizaciju sekvencijalnih algoritama. Sada moramo odmah postaviti pitanje podučavanja paralelnog programiranja. Sekvencijalni algoritam treba smatrati određenim dijelom paralelnog algoritma koji ne zahtijeva komunikaciju sa svojim ostalim dijelovima. Kako to uraditi je otvoreno pitanje. Još uvijek postoje neke ideje koje trebaju praktičnu implementaciju i testiranje. Nadamo se da će za godinu dana na sljedećoj konferenciji biti moguće razgovarati o postignutim rezultatima.

Prije trideset godina početak masovne kompjuterizacije proizvodnje zahtijevao je povećanje nivoa informatičke pismenosti stanovništva. To je dovelo do uvođenja informatike u školski program 1985. godine. No, kurs informatike u sovjetskoj (tada ruskoj) verziji nije bio ograničen samo na "nauku na dugme" - na ovladavanje tehnologijom rada sa softverskim paketima aplikacija i kompjuterskim igrama. Počeo je mijenjati stil razmišljanja mlađe generacije. Prije svega, ovo se odnosilo na algoritamnost, tačnost i strogost. Zatim je kurs informatike uključivao elemente logike i sistemske analize. Kasnije je sve to uvelike pojednostavilo distribuciju prijeko potrebne tehnologije u 21. vijeku. projektni pristup. Sada se priča da bi u narednoj deceniji trebalo da postanu paralelni algoritmi

element opšte kulture mišljenja. Pitanje: kako će ovladavanje konceptom paralelnog algoritma uticati na razmišljanje naredne generacije, do čega će dovesti restrukturiranje svijesti „na paralelan način“?

Masovno širenje paralelne obrade informacija čini hitnim premještanjem relevantnih pojmova u kategoriju javno dostupnih i opštekulturnih. Poznavanje paralelnih algoritama trebalo bi da postane deo pismenosti, baš kao što su osnovni koncepti teorije algoritama postali tokom poslednjih četvrt veka. To se može učiniti samo na jedan način – uključivanjem relevantnih tema u školski kurs informatike. To znači da nam je potrebna metodologija za početno upoznavanje sa paralelnim programiranjem na nivou srednje škole.

Istorijski gledano, prvi pokušaj da se tema paralelnog računarstva uključi u školski kurs informatike napravljen je prije dvadeset godina. Prije dvadeset godina, na predmetu pod nazivom „Algoritamika“, opisan je „direktor izgradnje“ koji je komandovao paralelnim akcijama nekoliko timova koji su gradili konstrukciju od pravougaonih i trouglastih blokova. Štaviše, kreirana je softverska implementacija za ovog izvođača. Avaj! Ovaj divni metodološki razvoj nije bio tražen sredinom 90-ih. Bila je skoro dvadeset godina ispred svog vremena!

Danas je situacija takva da je tema paralelnog računarstva u srednjoj školi prvenstveno vezana za temu superračunara. Upravo na superkompjutere autori različitih metodoloških razvoja usmeravaju pažnju studenata, čak i kada to nije neophodno. Dovoljno je reći da se odgovarajuća rubrika u časopisu “Informatika u školi” zove “Superkompjutersko obrazovanje u školi”. Ova situacija ima i pozitivne i negativne strane. Među pozitivnim aspektima su:

Tema superkompjutera je od interesa u društvu, uključujući studente. Ovo interesovanje ponavlja na savremenom nivou interesovanje koje su pre pola veka izazvale velike mašine - superkompjuteri njihovog vremena;

Organizaciona podrška od strane superkompjuterske zajednice. Svakog ljeta Fakultet računarske matematike i kibernetike Moskovskog državnog univerziteta je domaćin Ljetne superkompjuterske akademije. I svakog ljeta, u okviru ove Akademije, organizuje se školska staza za nastavnike informatike. Obuka je besplatna. Nerezidentnim studentima je stambeno zbrinuto po veoma povoljnim uslovima. Na konferenciji Russian Supercomputing Days u septembru 2015. organizovana je školska sekcija i majstorski kurs za nastavnike informatike. Dosljedan organizacioni rad doveo je do identifikacije i formiranja grupe nastavnika zainteresiranih za promociju ove teme;

Prisustvo bistrog, harizmatičnog vođe, kao što je Vladimir Valentinovič Voevodin - doktor fizičko-matematičkih nauka, profesor, dopisni član Ruske akademije nauka, zamenik direktora Istraživačko-računarskog centra Moskovskog državnog univerziteta;

Interes i podrška (uključujući materijal) ruskog predstavništva Intela i menadžera za strateški razvoj kompanije Intel, Igora Olegoviča Odintsova.

Nedostatak pristupa "superkompjutera" je što sužava obim paralelnog računarstva. Sami superkompjuteri su po pravilu nedostupni školarcima (osim ako se u velikim gradovima ne mogu vidjeti na ekskurzijama). Zadaci koje imaju za cilj su suviše složeni za školarce i u većini slučajeva nemaju neposredni praktični značaj i nisu od praktičnog interesa.

Prirodno proširenje polja superračunarstva je proučavanje paralelnog programiranja. Trenutno, za izvršavanje paralelnih programa uopšte nije potrebno imati superkompjuter. Dovoljan je višejezgreni procesor ili video kartica sa setom grafičkih akceleratora. A ovo je već dostupno gotovo svima. Među radovima u ovom pravcu ističemo kandidatsku disertaciju M.A. Sokolovskaya o metodologiji podučavanja budućih nastavnika informatike osnovama paralelnog programiranja i iskustvu E.Yu. Kiseleva o savladavanju CUDA tehnologije od strane školaraca.

Prema mišljenju autora ovog članka, fokusiranje na superračunare i paralelno programiranje značajno osiromašuje i komplikuje temu paralelnog računarstva i odvlači učenike od mnogih važnih i pristupačnih pitanja. Svrha teme „paralelno

računarstvo“ u srednjoj školi nije podučavanje „pravog“ paralelnog programiranja (proučavanje relevantnih jezičkih konstrukcija, programskih jezika i tehnologija), već upoznavanje učenika sa odgovarajućim skupom koncepata i razumijevanje karakteristika paralelnog rada. Svijet oko nas i unutar nas je složen paralelni sistem. I sam ovaj sistem pruža mnogo materijala za savladavanje pojmova i mehanizama paralelizma. Za to nisu potrebne složene vještačke strukture kao što su MPI i OpenMP tehnologije. Školska informatika treba da podstiče razmišljanje na „paralelan način“. A onda neka univerzitet u ovo razmišljanje ugradi stručno znanje, vještine i sposobnosti. U školi se ima smisla fokusirati ne na upoznavanje superkompjutera i proučavanje paralelnog programiranja, već na ovladavanje mehanizmima „zajedničke aktivnosti“ koji se stalno i široko koriste u životu. Kurs predlaže da se pokriju sljedeća pitanja:

1) Saradnja više izvršilaca (kopanje jarka sa više kopača) i paralelizacija „unutar“ jednog izvršioca uz prisustvo više uređaja za obradu (čitanje i jedenje jabuke). U računarskoj nauci, ovo će biti kompleks sa više mašina i višejezgarni procesor.

2) Vrste paralelizma: pravi paralelizam i pseudoparalelizam (jedan procesor izvršava više programa u dijelovima).

3) Izvođači istog tipa (kopači) i različitih tipova (posada tenkova).

4) Radovi iste vrste i različitih vrsta.

5) Odnos „izvršioci - poslovi“: 1 izvođač - 1 posao, 1 izvođač - N poslova (pseudoparalelno izvođenje ili pravi paralelizam u prisustvu više uređaja za obradu za različite poslove), N izvođača - 1 posao, N izvođača - N poslova.

6) Koordinacija aktivnosti izvođača. Vrste odobrenja: po dijelovima posla, po vremenu, po rezultatima aktivnosti, po resursima.

7) Resursi. Resursi su zajednički i nepodijeljeni, potrošni i ponovno upotrebljivi. Recikliranje utrošenih resursa („odvoz smeća“ u širem smislu).

8) Izvođenje istog djela od strane jednog izvođača i grupe izvođača. Zavisnost brzine rada od broja izvođača. Zavisnost cijene rada od broja izvođača. Nelinearno povećanje brzine rada sa povećanjem broja izvođača. Kritična putanja. Optimalan broj izvođača. Optimalno opterećenje izvođača. Optimalna procedura. Balansiranje opterećenja.

9) Konkurencija između izvođača za resurse. Blokiranje. Klinč (zastoj).

10) Mehanizmi za koordinaciju radnji izvođača.

11) Pseudoparalelno izvršavanje procesa na računaru (podela jednog resursa – procesora) između procesa izvršioca.

12) Pogodnost algoritama za paralelizaciju. Mogući stepen paralelizacije. Postojanje algoritama koji se ne mogu paralelizirati.

Napominjemo da gornja lista predstavlja privatno mišljenje autora članka i otvorena je za diskusiju, dopunu i ispravku. Štaviše, po mišljenju autora, bilo bi veoma korisno da „superkompjuterska zajednica” formuliše „društveni poredak” za školu: kakva znanja i veštine želi da vidi kod maturanata. Po čemu bi se diplomac škole "superkompjuterskog svijeta" trebao razlikovati od današnjeg diplomca? Ako postoji naredba, bit će i rezultat. Svježi primjer. Prvog dana Russian Supercomputing Days-2015, dva izvještaja su iznijela ideju da brzina modernih superračunara nije određena snagom procesora (što je u fokusu pažnje javnosti), već brzinom RAM-a. To je ono što postaje usko grlo, čija propusnost određuje produktivnost cijelog sistema. Kao rezultat toga, drugog dana konferencije, učesnici majstorske klase za nastavnike testirali su igru koju je izumio autor ovog članka, demonstrirajući interakciju centralnog procesora, RAM-a i keš memorije. Redoslijed i oblik prezentacije materijala je otvoreno pitanje.

Materijal treba demonstrirati na primjerima koji se ne odnose na rad računara. Izvođači moraju manipulirati materijalnim objektima.

Što veći dio obuke treba da bude u prirodi poslovnih (organizacijskih i aktivnosti) igara.

Ispunjavanje ovih zahtjeva će olakšati razumijevanje materijala koji se proučava. Ovo će biti korisno i kada se ova tehnika koristi u nastavi informatike u školi (uključujući osnovnu!), i kada podučavate odrasle: nastavnike informatike i učenike. Učenik, nastavnik u školi, student neosnovne specijalnosti moći će da se zaustavi na nivou upoznavanja i razumijevanja. Profesionalni student će morati napraviti sljedeći korak i prijeći od upoznavanja do proučavanja ovih mehanizama na profesionalnom nivou. Ali ovo je već korak dalje od metoda početnog upoznavanja s temom.

Autor ovog članka je započeo rad na pripremi metodologije za proučavanje paralelnog računarstva 2013. godine tokom pripreme takmičenja TRIZformashka-2013 i nastavio u narednim godinama.

(„TRIZformashka“ je međuregionalno internet takmičenje iz računarstva, sistemske analize i TRIZ-a. Održava se svake godine u drugoj polovini marta. Uzrast učesnika je od prvog razreda do četvrte godine. Geografija – od Vladivostoka do Rige. Prosek broj učesnika je 100 timova (300 ljudi.), maksimalno - 202 tima (više od 600 ljudi). Sajt takmičenja www.trizformashka.ru.) Zatim je 2013. cilj rada formulisan na sledeći način:

1. U roku od dvije do tri godine pripremiti opis izvođača, set igara i zadataka vezanih za paralelno računanje;

2. Ponuditi ih (u dijelovima, godišnje) učesnicima takmičenja;

3. Analizirati njihovu reakciju (procijeniti broj rješavača, njihovu starost, uspješnost rješenja, tipične greške, uočene netačnosti u formulaciji zadataka itd.). TRIZformashka takmičenje se pokazalo kao zgodan alat za otklanjanje grešaka, jer

omogućila je dobijanje reakcija svih uzrasta (od prvog razreda do četvrte godine), iz različitih regiona, iz različitih obrazovnih institucija.

Proteklih godina pripremljen je sljedeći set metodoloških alata i platformi za njihovo testiranje.

1. Zadaci o paralelizmu, počev od 2013. godine, uključeni su u takmičenje „TRIZformashka“ (od 2013. godine takmičenje ima podnaslov „Paralelno računanje“). Lista tipova zadataka je data ispod;

2. Za novu verziju udžbenika informatike za 4. razred pripremljeno je poglavlje o paralelizmu. Materijal je testiran u 3. i 4. razredu Liceja br. 10 u Permu;

3. Kompjuterska igra “Tank Crew” se razvija i koristi od 2014. godine u takmičenju TRIZformashka;

4. Razvijeno je i testirano više igara koje odražavaju sljedeće probleme:

Koordinacija aktivnosti izvođača. Razne vrste odobrenja;

Izvođenje istog djela od strane jednog izvođača i grupe izvođača. Zavisnost brzine rada od broja izvođača. Nelinearno povećanje brzine rada sa povećanjem broja izvođača. Kritična putanja. Optimalan broj izvođača. Optimalno opterećenje izvođača. Optimalna procedura;

Resursi. Zajednički i nepodijeljeni resursi;

Takmičenje između izvođača za resurse. Blokiranje. Klinč (zastoj). Predložene su i testirane sljedeće vrste problema:

1. Zadaci o vrstama odobrenja. (Koje vrste koordinacije postoje u školskoj menzi?);

2. Igra "Tank Crew". Zadatak za izgradnju paralelnog algoritma;

3. Izvođač “Izgradnja”. Istovremeno, radni timovi grade konstrukciju od horizontalnih i vertikalnih greda. Poslovi obuhvataju zadatke za izvršenje navedenog algoritma, za razvoj novog algoritma, za traženje grešaka u datom algoritmu, za istraživanje algoritama (upoređivanje vremena izgradnje koristeći različite algoritame, poređenje troškova izgradnje, procjenu mogućnosti uštede preraspodjelom rad, itd.);

4. Konkurencija za resurse. Tri praščića kuhaju svako svoj ručak. Za svako prase je naznačeno koja jela priprema, koja sredstva (oprema, pribor i sl.) su mu potrebna za to i koliko dugo treba koristiti ta sredstva. Potrebno je napraviti raspored rada za svako prase, ako kuha sam u kuhinji, ako kuhaju u paru, ako kuhaju sva tri odjednom. Vrijeme kuhanja treba svesti na minimum;

5. Mrežni dijagram. Dat je mrežni dijagram. Potrebno je prikazati (šematski) objekat koji će se graditi, odrediti koliko će dana biti potrebno za izgradnju sa određenim brojem ekipa, koji dio posla će biti završen do određenog vremena;

6. Slojevito-paralelne forme. Planiranje rada po raznim kriterijumima. Dati su radni zadatak, produktivnost radnika i pravila plaćanja. Potrebno je odrediti broj radnika koji je potreban da se posao završi u datom vremenu, odrediti period rada za zadati broj radnika, odrediti broj radnika koji je potreban za minimiziranje troškova rada;

7. Gantovi grafikoni. U tekstu je opisan plan rada za rekonstrukciju radionice: trajanje i međusobni redoslijed radnji, potrebni radnici. Potrebno je odrediti rok za završetak objekta, promjenu roka zbog određenih promjena u radnoj snazi, te spisak uključenih radnika na određeni datum.

8. Koordinacija rada koji se ponavlja. Neka se da zadatak da se proizvede serija uređaja u minimalnom vremenu, s tim da se svaki uređaj mora obraditi na različitoj opremi; postoje različite količine opreme različite produktivnosti. Potrebno je planirati vrijeme početka i rada svake opreme i minimizirati zastoje.

Danas imamo sljedeće rezultate:

1. Formuliran je pristup za proučavanje teme „paralelnog računarstva“: ići ne od problema informatike, već „iz života“, fokusirati se na „zajedničku aktivnost“;

2. Formulisana je lista pitanja koja se predlažu da se odraze u početnom kursu paralelnog računarstva;

3. Formulirane su neke klase problema. Na osnovu akumuliranog iskustva, možete procijeniti kakve probleme treba izmisliti;

4. Pripremljen je set zadataka imenovanih klasa. Problemi su testirani na takmičenjima TRIZformashka 2013, 2014, 2015. i/ili u osnovnoj školi (u odeljenjima sa učenicima trećeg i četvrtog razreda Liceja br. 10 u Permu);

5. Pripremljen je set poslovnih igara. Igre su testirane u osnovnim školama i na brojnim manifestacijama za nastavnike. Konkretno, predstavljeni su na školskoj stazi Ljetne superkompjuterske akademije Moskovskog državnog univerziteta 2014. godine, na majstorskoj klasi za nastavnike na ruskim danima superračunarstva-2015, na nekoliko drugih konferencija (uključujući na konferenciji IT-education-2015. udruženje APKIT) i drugi događaji za nastavnike informatike;

6. Za udžbenik za četvrti razred pripremljen je komplet tekstova o paralelizmu. Tekstovi su testirani u Liceju br. 10 u Permu;

7. Pripremljena je kompjuterska igrica “Tank Crew”. Igra je testirana na takmičenjima TRIZformashka 2014. i 2015. godine;

8. Takmičenje TRIZformashka se pokazalo kao platforma za testiranje;

9. Formulisan je zadatak „rokovanja“ u procesu učenja algoritamizacije: odmah naučiti paralelno programiranje, predstavljajući sekvencijalni algoritam kao deo paralelnog. Postoje razmišljanja o tome kako se ova ideja može implementirati. Postoji prilika da se ove ideje isprobaju tokom tekuće školske godine (za učenike 4-5 razreda);

10. Postoji potreba, želja i mogućnost da se nastavi rad.

Književnost

1. Algoritmi: 5-7 razred: Udžbenik i zadatak za opšte obrazovanje. obrazovne ustanove /A.K. Zvonkin, A.G. Kulakov, S.K. Lando, A.L. Semenov, A.Kh. Shen. - M.: Drfa, 1996.

2. Bosova L.L. Paralelni algoritmi u osnovnim i srednjim školama. //Informatika u školi. 2015, br. P.24-27.

3. Voevodin V.V. Računarska matematika i struktura algoritama: Predavanje 10 o tome zašto je teško rješavati probleme na računarskim sistemima paralelne arhitekture i koje dodatne informacije trebate znati. za uspješno prevazilaženje ovih poteškoća: udžbenik. M.: Izdavačka kuća MSU 2010.

4. Gavrilova I.V. Prvo putovanje u “paralelni svijet”. //Informatika u školi. 2015, br. 6. P.16-19.

5. Dieter M.L., Plaksin M.A. Paralelno računarstvo u školskoj informatici. Igra "Izgradnja". //Informatika u školi: prošlost, sadašnjost i budućnost.: Materijali Sveruskog. naučna metoda. konf. o upotrebi IKT-a u obrazovanju, 6-7 februara 2014. /Perm. stanje nacionalni istraživanja univ. - Perm, 2014. - P.258-261.

6. Ivanova N.G., Plaksin M.A., Rusakova O.L. TRIZformashka. //Računarska nauka. N05 Pristupljeno 10.10.2015.

14. Plaksin M.A. Informatika: udžbenik za 4. razred: 2 časa / M.A.Plaksin, N.G.Ivanova, O.L.Rusakova. - M.: BINOM. Laboratorij znanja, 2012.

15. Plaksin M.A. O metodi početnog upoznavanja sa paralelnim računarstvom u srednjoj školi. //Informatika u školi: prošlost, sadašnjost i budućnost.: Materijali Sveruskog. naučna metoda. konf. o upotrebi IKT u obrazovanju, 6-7 februara 2014. /Perm. stanje nacionalni istraživanja univ. - Perm, 2014. - P.256-258.

16. Plaksin M.A. Komplet poslovnih igara za uvođenje paralelnog računarstva u osnovnu školu. //Nastava informacionih tehnologija u Ruskoj Federaciji: materijali Trinaeste otvorene sveruske konferencije „IT-0education-2015“ (Perm, 14-15. maja 2015.). Permski državni nacionalni istraživački univerzitet, - Perm, 2015. P.60-62.

17. Plaksin M.A., Ivanova N.G., Rusakova O.L. Skup zadataka za upoznavanje sa paralelnim računarstvom na takmičenju TRIZformashka. //Nastava informacionih tehnologija u Ruskoj Federaciji: materijali Trinaeste otvorene sveruske konferencije „IT obrazovanje-2015“ (Perm, 14-15. maja 2015.). Permski državni nacionalni istraživački univerzitet, - Perm, 2015. str. 232-234.

18. Sokolovskaya M.A. Metodički sistem za nastavu osnova paralelnog programiranja budućim nastavnicima informatike.: apstrakt. dis. ...cand. ped. Nauke, Krasnojarsk, 2012.

Koncept paralelnog računarstva

OSNOVE PARALELNOG RAČUNARA

Predavanje br. 6

Ispod paralelna ili istovremena računanja možete razumjeti procese rješavanja problema u kojima se nekoliko računskih operacija može izvoditi istovremeno

Paralelno računarstvo čini osnovu superkompjuterskih tehnologija i računarstva visokih performansi

Paralelna obrada

Ako određeni uređaj izvrši jednu operaciju u jedinici vremena, tada će izvršiti hiljadu operacija u hiljadu jedinica. Ako pretpostavimo da postoji pet identičnih nezavisnih uređaja sposobnih da rade istovremeno, onda sistem od pet uređaja može izvršiti istih hiljadu operacija ne u hiljadu, već u dvije stotine jedinica vremena.

Slično, sistem od N uređaja će obaviti isti posao u 1000/N jedinica vremena. Slične analogije se mogu naći i u životu: ako jedan vojnik iskopa baštu za 10 sati, onda će se četa od pedeset vojnika sa istim sposobnostima, koji rade istovremeno, nositi s istim poslom za 12 minuta - princip paralelizma u akciji!

Pionir u paralelnoj obradi tokova podataka bio je akademik A.A. Samarsky, koji je izveo proračune potrebne za simulaciju nuklearnih eksplozija ranih 50-ih. Samarsky je rešio ovaj problem tako što je nekoliko desetina mladih dama sa mašinama za sabiranje postavio za stolove. Mlade dame su prenosile podatke jedna drugoj jednostavno riječima i unosile potrebne brojeve na mašine za sabiranje. Tako je posebno izračunata evolucija eksplozijskog vala.

Bilo je puno posla, mlade dame su bile umorne, a Aleksandar Andrejevič je hodao među njima i hrabrio ih. Ovo je, moglo bi se reći, bio prvi paralelni sistem. Iako su proračuni za hidrogensku bombu izvedeni maestralno, njihova preciznost je bila vrlo mala, jer je bilo malo korištenih čvorova u mreži, a vrijeme proračuna je bilo predugo.

Obrada transporterom

Ideja cjevovodne obrade je da se izoluju pojedinačne faze izvođenja opće operacije, a svaka faza, nakon što završi svoj posao, prenijela bi rezultat na sljedeću, dok bi istovremeno primala novi dio ulaznih podataka. Dobijamo očigledan dobitak u brzini obrade kombinovanjem prethodno raspoređenih operacija.

Pretpostavimo da u jednoj operaciji postoji pet mikrooperacija, od kojih se svaka izvodi u jednoj jedinici vremena. Ako postoji jedan nedjeljiv serijski uređaj, tada će obraditi 100 parova argumenata u 500 jedinica. Ako se svaka mikrooperacija razdvoji u zasebnu fazu (ili drugačije nazvanu faza) transportnog uređaja, tada će se u petoj jedinici vremena, u različitim fazama obrade takvog uređaja, nalaziti prvih pet parova argumenata , a cijeli set od sto parova bit će obrađen za 5 + 99 = 104 jedinice vremena - ubrzanje u odnosu na serijski uređaj je skoro pet puta (prema broju faza transportera).

Modeli paralelnih računara (Flynn klasifikacija)

· “Jedan tok komandi - jedan tok podataka” (SISD - “Jedinstveni instrukcijski pojedinačni podaci”)

Odnosi se na von Neumann arhitekturu. SISD računari su obični, “tradicionalni” sekvencijalni računari, u kojima se samo jedna operacija izvodi na jednom elementu podataka (numeričkom ili nekoj drugoj vrijednosti) u bilo kojem trenutku. Većina modernih personalnih računara spada u ovu kategoriju.

· "Jedan tok komandi - mnogo tokova podataka" (SIMD - "Jedna instrukcija - više podataka")

SIMD (jedna instrukcija, više podataka)- princip kompjuterskog računarstva koji omogućava paralelizam na nivou podataka. SIMD računari se sastoje od jednog komandnog procesora (kontrolnog modula), koji se naziva kontroler, i nekoliko modula za obradu podataka, koji se nazivaju elementi za obradu. Upravljački modul prima, analizira i izvršava komande.

Ako se u naredbi nađu podaci, kontroler šalje naredbu svim elementima procesora, a ova naredba se izvršava na nekoliko ili na svim elementima procesora. Svaki procesni element ima svoju memoriju za pohranjivanje podataka. Jedna od prednosti ove arhitekture je što se u ovom slučaju logika proračuna implementira efikasnije. SIMD procesori se takođe nazivaju vektorskim procesorima.

· „Mnogo tokova komandi – jedan tok podataka“ (MISD – „Višestruke instrukcije – pojedinačni podaci“)

Računara ove klase praktično nema i teško je dati primjer njihove uspješne implementacije. Jedan od rijetkih je sistolni niz procesora, u kojem su procesori smješteni na čvorovima regularne rešetke, čije ivice imaju međuprocesorske veze. Svim elementima procesora upravlja zajednički generator takta. U svakom radnom ciklusu, svaki element obrade prima podatke od svojih susjeda, izvršava jednu naredbu i prenosi rezultat svojim susjedima.

Pozivaju se nizovi PE-ova sa direktnim vezama između obližnjih PE-ova sistolni. Takvi nizovi su izuzetno efikasni, ali svaki od njih je fokusiran na rješavanje vrlo uske klase problema. Razmotrimo kako možete izgraditi sistolički niz za rješavanje određenog problema. Neka, na primjer, želite da kreirate uređaj za izračunavanje matrice D=C+AB, Gdje

Ovdje su sve matrice trakaste matrice reda n. Matrix A ima jednu dijagonalu iznad i dvije dijagonale ispod glavne; matrica B- jedna dijagonala ispod i dvije dijagonale iznad glavne; matrica C tri dijagonale iznad i ispod glavne. Neka svaki PE može izvesti skalarnu operaciju c+ab i istovremeno prenose podatke. Svaki PE, dakle, mora imati tri ulaza: a, b, c i tri izlaza: a, b, c. Unos ( in) i vikendom ( van) podaci su povezani relacijama

a out = a in , b out = b in , c out = c in + a in *b in ;

Ako u vrijeme operacije neki podaci nisu primljeni, onda ćemo pretpostaviti da su definirani kao nule. Pretpostavimo dalje da se svi PE nalaze u ravni i svaki od njih je povezan sa šest susjednih. Ako rasporedite podatke kao što je prikazano na slici, kolo će izračunati matricu D.

Niz radi u taktnim ciklusima. Tokom svakog ciklusa takta, svi podaci se premeštaju u susedne čvorove u smerovima označenim strelicama.

Slika prikazuje stanje sistoličkog niza u nekom trenutku. U sljedećem ciklusu takta, svi podaci će se premjestiti na jedan čvor i elemente a11, b11, c11će završiti u jednom PE koji se nalazi na raskrsnici isprekidanih linija. Stoga će izraz biti evaluiran c11+a11b11.U istom satu, podaci a12 I b21 doći će vrlo blizu PE, koji se nalazi na vrhu sistoličkog niza.

U sljedećem ciklusu takta, svi podaci će se ponovo pomjeriti za jedan čvor u smjeru strelica i pojavit će se u gornjem PE a12 I b21 i rezultat prethodnog rada PE koji se nalazi ispod, tj. c11+a11b11. Stoga će izraz biti evaluiran c11+a11b11+a12b21. Ovo je element d11 matrice D.

Nastavljajući korak po korak ispitivanje procesa, možemo potvrditi da se na PE izlazima koji odgovaraju gornjoj granici sistoličkog niza, elementi matrice periodično izlaze nakon tri koraka D, dok se na svakom izlazu pojavljuju elementi iste dijagonale. In about 3n ciklusa, izračunavanje cijele matrice će biti završeno D. U ovom slučaju, opterećenje svake sistoličke ćelije je asimptotski jednako 1/3 .

"Mnogo tokova komandi - mnogo tokova podataka" (MIMD - "Višestruke instrukcije - više podataka")

Ova kategorija računarskih arhitektura je najbogatija ako imajte na umu primjere njegove uspješne implementacije. Uključuje simetrične paralelni računarski sistemi, radne stanice sa više procesori, klasteri radnih stanica itd.

Ogromne performanse paralelnih računara i superračunara više su nego nadoknađene teškoćama njihovog korišćenja. Počnimo od najjednostavnijih stvari. Imate program i pristup, recimo, računaru sa 256 procesora. šta očekuješ? Da, jasno je: sasvim opravdano očekujete da će se program izvršavati 256 puta brže nego na jednom procesoru. Ali to je ono što se najvjerovatnije neće dogoditi.

Paralelno računarstvo je metoda organizovanja računarskog računarstva u kojoj se programi razvijaju kao skup računarskih procesa u interakciji koji se izvršavaju istovremeno.

Postoje različiti načini za implementaciju paralelnog računarstva: svaki računarski proces može biti implementiran kao proces operativnog sistema, ili računarski procesi mogu biti kolekcija niti izvršenja unutar jednog procesa. Nit (ili tačnije nit izvršenja) je najmanja jedinica obrade čije izvršenje može dodijeliti kernel operativnog sistema. Više niti izvršavanja može postojati unutar istog procesa i dijeliti resurse kao što je memorija, dok procesi ne dijele te resurse. Paralelni programi se mogu fizički izvršavati ili sekvencijalno na jednom procesoru - naizmjenično mijenjajući korake svakog računskog procesa, ili paralelno - dodjeljivanjem jednog ili više procesora (lociranih u blizini ili distribuiranih u računarskoj mreži) svakom računarskom procesu.

Glavni izazov u dizajniranju paralelnih programa je osigurati ispravan slijed interakcija između različitih računarskih procesa, kao i dijeljenje resursa kao što su RAM ili periferni uređaji.

U nekim sistemima paralelnog programiranja, prijenos podataka između komponenti je skriven od programera, dok u drugim mora biti eksplicitno specificiran. Eksplicitne interakcije se mogu podijeliti u dvije vrste:

1. Interakcija putem zajedničke memorije (na primjer, u Javi ili C#). Ova vrsta paralelnog programiranja obično zahtijeva neki oblik hvatanja kontrole kako bi se međusobno koordinirali niti.

2. Interakcija putem prosljeđivanja poruka. Poruke se mogu razmjenjivati asinhrono ili korištenjem metode susreta, u kojoj je pošiljatelj blokiran dok se njegova poruka ne dostavi. Asinhroni prijenos poruka može biti pouzdan (sa garancijom isporuke) ili nepouzdan. Paralelni sistemi za prosleđivanje poruka su često lakši za razumevanje od sistema deljene memorije i generalno se smatraju superiornim metodom paralelnog programiranja. Razmjena poruka se može efikasno implementirati na simetričnim multiprocesorima sa ili bez zajedničke koherentne memorije.

Postoji dosta različitih tehnologija paralelnog programiranja. Štaviše, ove tehnologije se ne razlikuju toliko u programskim jezicima koliko u arhitektonskim pristupima izgradnji paralelnih sistema. Na primjer, neke tehnologije uključuju izgradnju paralelnih rješenja baziranih na više računara (istih i različitih tipova), dok druge uključuju rad na jednoj mašini sa više procesorskih jezgara. Trenutno su glavni softverski alati za kreiranje paralelnih programa:

1. OpenMP koriste se u paralelnim sistemima sa zajedničkom memorijom (na primjer, moderni računari sa višejezgarnim procesorima);

2. MPI (Message Passing Interface) je standard za sisteme za prenos poruka između paralelno izvršavajućih procesa, koji se koristi u razvoju programa za superračunare;

3. POSIX Threads je standard za implementaciju niti izvršavanja;

4. Windows operativni sistem ima ugrađenu podršku za višenitne aplikacije za C++ na API nivou;

5. PVM (paralelna virtuelna mašina) omogućava vam da kombinujete heterogene računare povezane mrežom u zajednički računarski resurs.

Sistemi zasnovani na više računara klasifikovani su kao sistemi za distribuirano računarstvo. Ovakva rješenja se koriste već duže vrijeme. Najupečatljiviji primjer tehnologije distribuiranog računanja je MPI (Message Passing Interface). MPI je najčešći standard interfejsa za razmjenu podataka za paralelno programiranje; postoje implementacije za ogroman broj računalnih platformi. MPI pruža programeru jedinstveni mehanizam za interakciju grana unutar paralelne aplikacije, bez obzira na arhitekturu mašine (jednoprocesor/multiprocesor sa zajedničkom/odvojenom memorijom), relativnu lokaciju grana (na istom procesoru ili na različitim).

Budući da je MPI prvenstveno namijenjen sistemima sa zajedničkom memorijom, njegovo korištenje za organiziranje paralelnog procesa u sistemu sa zajedničkom memorijom je izuzetno teško i nepraktično. Međutim, ništa vas ne sprječava da napravite MPI rješenja za jednu mašinu.

Ali sistemi paralelnog programiranja za rad na jednoj mašini počeli su se razvijati relativno nedavno. Naravno, ovo nisu suštinski nove ideje, ali upravo su pojavom višejezgrenih sistema na tržištu personalnih računara i mobilnih uređaja tehnologije poput OpenMP-a dobile značajan razvoj.

Veoma je važno da tehnologija paralelnog programiranja podržava mogućnost da se program postepeno napravi paralelnim. Naravno, idealan paralelni program treba odmah paralelno napisati, možda na nekom funkcionalnom jeziku gdje se uopće ne postavlja pitanje paralelizacije. Ali u praksi je potrebno postepeno paralelizirati pisani sekvencijalni kako bi se povećale performanse. U ovom slučaju, OpenMP tehnologija će biti vrlo dobar izbor. Omogućava vam da odaberete mjesta u aplikaciji kojima je najpotrebnija paralelizacija i prije svega ih napravite paralelnim. Proces razvoja paralelne verzije može se prekinuti, srednje verzije programa objaviti i vratiti po potrebi. Zbog toga je tehnologija OpenMP postala prilično popularna.

OpenMP (Open Multi-Processing) je skup direktiva kompajlera, bibliotečkih procedura i varijabli okruženja koje su dizajnirane za programiranje višenitnih aplikacija na višeprocesorskim sistemima dijeljene memorije.

OpenMP specifikaciju razvija nekoliko velikih proizvođača hardvera i softvera, čiji rad reguliše neprofitna organizacija pod nazivom OpenMP Architecture Review Board (ARB).

Prva verzija pojavila se 1997. godine, namijenjena za jezik Fortran. C/C++ verzija je razvijena 1998. godine. 2008. godine izašao je OpenMP 3.0. OpenMP interfejs je postao jedna od najpopularnijih tehnologija za paralelno programiranje. OpenMP se uspješno koristi kako u programiranju superračunarskih sistema sa velikim brojem procesora, tako iu desktop korisničkim sistemima ili, na primjer, u Xbox 360.

OpenMP implementira paralelno računanje korištenjem višenitnog rada, u kojem “master” nit kreira skup podređenih niti i zadatak se distribuira među njima. Pretpostavlja se da se niti izvršavaju paralelno na mašini sa više procesora (broj procesora ne mora biti veći ili jednak broju niti).

Zadaci koje niti izvršavaju paralelno, kao i podaci potrebni za obavljanje ovih zadataka, opisani su pomoću posebnih predprocesorskih direktiva odgovarajućeg jezika - pragma. Na primjer, dijelu Fortran koda koji mora biti izvršen od nekoliko niti, od kojih svaka ima svoju kopiju varijable N, prethodi sljedeća direktiva: !$OMP PARALLEL PRIVATE(N)

Broj kreiranih niti može regulisati kako sam program pozivanjem bibliotečkih procedura, tako i eksterno, koristeći varijable okruženja.

Ključni elementi OpenMP-a su

1. konstrukcije za kreiranje niti (paralelna direktiva);

2. konstrukcije za distribuciju rada između niti (DO/for i section direktive);

3. konstrukcije za upravljanje radom s podacima (dijeljeni i privatni izrazi za definiranje memorijske klase varijabli);

4. konstrukcije za sinhronizaciju niti (kritičke, atomske i barijerske direktive);

5. Bibliotečke procedure podrške za vrijeme izvođenja (na primjer, omp_get_thread_num);

6. varijable okruženja (na primjer, OMP_NUM_THREADS).

OpenMP koristi model paralelnog izvršavanja sa spajanjem grana. OpenMP program počinje kao jedna nit izvršenja, koja se naziva početna nit. Kada nit naiđe na paralelnu konstrukciju, ona stvara novu grupu niti koja se sastoji od nje same i više dodatnih niti i postaje gospodar nove grupe. Svi članovi nove grupe (uključujući glavnu grupu) izvršavaju kod unutar paralelne konstrukcije. Na kraju paralelne strukture postoji implicitna barijera. Nakon paralelne konstrukcije, samo glavna nit nastavlja izvršavati korisnički kod. Paralelni region može biti ugniježđen sa drugim paralelnim regionima, u kojima svaka nit originalnog regiona postaje glavna nit za svoju grupu niti. Ugniježđene regije mogu zauzvrat uključiti regije na dubljem nivou ugniježđenja.

Broj niti u grupi koja se izvodi paralelno može se kontrolirati na nekoliko načina. Jedan od njih koristi varijablu okruženja OMP_NUM_THREADS. Drugi način je da pozovete proceduru omp_set_num_threads(). Drugi način je korištenje izraza num_threads u kombinaciji s paralelnom direktivom.

U ovom programu, dva niza (a i b) se dodaju paralelno sa deset niti.

#include

int main(int argc, char *argv)

float a[N], b[N], c[N];

omp_set_dynamic(0); // spriječiti openmp biblioteku da promijeni broj niti tokom izvršavanja

omp_set_num_threads(10); // postavljamo broj niti na 10

// inicijalizira nizove

za (I = 0; I< N; i++)

// izračunati zbir nizova

#pragma omp paralelno podijeljeno (a, b, c) privatno (i)

za (I = 0; I< N; i++)

c[i] = a[i] + b[i];

printf("%f\n", c);

Ovaj program se može kompajlirati pomoću gcc-4.4 i novijih sa –fopenmp zastavicom. Očigledno, ako uklonite uključivanje datoteke zaglavlja omp.h, kao i pozive OpenMP konfiguracijske funkcije, program se može kompajlirati na bilo kojem C kompajleru kao običan sekvencijalni program.

OpenMP je podržan od strane mnogih modernih kompajlera:

1. Sun Studio kompajleri podržavaju zvaničnu specifikaciju - OpenMP 2.5 - sa poboljšanim performansama pod Solaris OS; Podrška za Linux planirana je za sljedeće izdanje.

2. Visual C++ 2005 i novije verzije podržavaju OpenMP u Professional i Team System izdanjima.

3. GCC 4.2 podržava OpenMP, a neke distribucije (kao što je Fedora Core 5 gcc) imaju podršku u svojim verzijama GCC 4.1.

4. Intel C++ kompajler, uključujući verziju Intel Cluster OpenMP za programiranje u distribuiranim memorijskim sistemima.

Message Passing Interface (MPI Message passing interface) je programsko sučelje za prijenos informacija (API) koje omogućava razmjenu poruka između procesa koji obavljaju isti zadatak. Razvili su William Group, Evin Lusk i drugi.

MPI je najčešći standard interfejsa za razmenu podataka za paralelno programiranje, a postoje implementacije za veliki broj računarskih platformi. Koristi se u razvoju programa za klastere i superračunare. Glavno sredstvo komunikacije između procesa u MPI je prosljeđivanje poruka jedni drugima. MPI standardizaciju sprovodi MPI Forum. MPI standard opisuje interfejs za prosleđivanje poruka koji mora biti podržan i na platformi i u korisničkim aplikacijama. Trenutno postoji veliki broj besplatnih i komercijalnih implementacija MPI-ja. Postoje implementacije za jezike Fortran 77/90, C i C++.

MPI je prvenstveno fokusiran na sisteme sa distribuiranom memorijom, odnosno kada su troškovi prenosa podataka visoki, dok je OpenMP fokusiran na sisteme sa deljenom memorijom (višejezgarni sa zajedničkim ESH). Obje tehnologije se mogu koristiti zajedno za optimalno korištenje višejezgrenih sistema u klasteru.

Prva verzija MPI je razvijena 1993-1994, a MPI 1 je objavljen 1994.

Većina modernih MPI implementacija podržava verziju 1.1. MPI standard verzija 2.0 podržava većina modernih implementacija, ali neke karakteristike možda neće biti u potpunosti implementirane.

slanje i primanje poruka između odvojenih procesa;

kolektivne interakcije procesa;

interakcije u procesnim grupama;

implementacija procesnih topologija;

generiranje dinamičkih procesa i upravljanje procesima;

jednosmjerne komunikacije (Get/Put);

paralelni ulaz i izlaz;

proširene kolektivne operacije (procesi mogu obavljati kolektivne operacije ne samo unutar jednog komunikatora, već i unutar nekoliko komunikatora).

Verzija MPI 2.1 objavljena je početkom septembra 2008.

Osnovni mehanizam komunikacije između MPI procesa je prijenos i prijem poruka. Poruka sadrži prenesene podatke i informacije koje omogućavaju primaocu da ih selektivno primi:

1. pošiljalac - rang (broj u grupi) pošiljaoca poruke;

2. primalac - rang primaoca;

3. znak - može se koristiti za odvajanje različitih vrsta poruka;

4. komunikator - šifra procesne grupe.

Operacije prijema i prijenosa mogu biti blokirane ili neblokirajuće. Za neblokirajuće operacije definirane su funkcije za provjeru spremnosti i čekanje da se operacija završi.

Drugi način komunikacije je pristup udaljenoj memoriji (RMA), koji omogućava čitanje i modificiranje memorijskog područja udaljenog procesa. Lokalni proces može prenijeti memorijsko područje udaljenog procesa (unutar prozora koji su specificirali procesi) u njegovu memoriju i natrag, a također može kombinirati podatke prenesene u udaljeni proces s podacima dostupnim u njegovoj memoriji (na primjer, zbrajanjem ). Sve operacije udaljenog pristupa memoriji su neblokirajuće; međutim, blokirajuće sinhronizacijske funkcije moraju biti pozvane prije i nakon njihovog izvršenja.

Ispod je primjer programa za izračunavanje π u C koristeći MPI:

// Povezivanje potrebnih zaglavlja

#include

// Uključuje datoteku zaglavlja MPI

#include "mpi.h"

// Funkcija za međuproračune

duplo f (dvostruko a)

povratak (4,0 / (1,0+ a*a));

// Glavna funkcija programa

int main(int argc, char **argv)

// Deklariranje varijabli

int done = 0, n, myid, numprocs, I;

dupli PI25DT = 3,141592653589793238462643;

dupli mypi, pi, h, suma, x;

duplo startwtime = 0.0, endwtime;

char ime_procesora;

// Inicijaliziranje MPI podsistema

MPI_Init(&argc, &argv);

// Dobivamo veličinu komunikatora MPI_COMM_WORLD

// (ukupan broj procesa unutar zadatka)

MPI_Comm_size(MPI_COMM_WORLD,&numprocs);

// Dobivamo broj trenutnog procesa unutar

// komunikator MPI_COMM_WORLD

MPI_Comm_rank(MPI_COMM_WORLD,&myid);

MPI_Get_processor_name(processor_name,&namelen);

// Prikaz broja niti u dijeljenom bazenu

fprintf(stdout, “Proces %d od %d je na %s\n”, myid,numprocs,processor_name);

// broj intervala

fprintf(stdout, “Unesite broj intervala: (0 prekida)”);

if(scanf(“%d”,&n) != 1)

fprintf(stdout, “Nije unet broj; napuštanje\n”);

MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);

h = 1,0 / (dvostruko)n;

// Izračunaj tačku koja je dodijeljena procesu

for(I = myid + 1; (I<= n) ; I += numprocs)

x = h * ((dvostruko)I – 0,5);

// Poništi rezultate svih procesa i dodaj

MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);

// Ako je ovo glavni proces, ispiši rezultat

printf(“PI je približno %.16f, Greška je %.16f\n”, pi, fabs(pi – PI25DT));

endwtime = MPI_Wtime();

printf(“vrijeme na zidu = %f\n”, endwtime-startwtime);

// Otpuštanje MPI podsistema

Najčešći MPI implementacije danas su:

MPICH je najčešća besplatna implementacija, radi na UNIX sistemima i Windows NT

LAM/MPI je još jedna besplatna implementacija MPI-a. Podržava heterogene konfiguracije, LAM (http://www.lam-mpi.org) podržava heterogene konfiguracije, Globus paket i zadovoljava IMPI (Interoperable MPI).

Podržani su različiti komunikacioni sistemi (uključujući Myrinet).

WMPI - MPI implementacija za Windows

MPI/PRO za Windows NT - komercijalna implementacija za Windows NT

Intel MPI - komercijalna implementacija za Windows/Linux

Microsoft MPI je uključen u Compute Cluster Pack SDK. Zasnovano na MPICH2, ali uključuje dodatne mogućnosti upravljanja poslovima. Podržana je MPI-2 specifikacija.

HP-MPI - komercijalna implementacija od HP-a

SGI MPT - plaćena MPI biblioteka od SGI

Mvapich - besplatna MPI implementacija za Infiniband

Otvoreni MPI - besplatna implementacija MPI, nasljednik LAM/MPI

Oracle HPC ClusterTools - besplatna implementacija za Solaris SPARC/x86 i Linux baziran na Open MPI

MPJ - MPI za Javu

POSIX Threads- POSIX standard za implementaciju niti izvršavanja, definiranje API-ja za kreiranje i upravljanje njima.

Biblioteke koje implementiraju ovaj standard (i funkcije ovog standarda) se obično nazivaju Pthreads (funkcije imaju prefiks "pthread_"). Iako su najpoznatije opcije za operativne sisteme slične Unixu kao što su Linux ili Solaris, postoji i implementacija za Microsoft Windows (Pthreads-w32)

Pthreads definira skup tipova i funkcija u programskom jeziku C. Datoteka zaglavlja je pthread.h.

Tipovi podataka:

1. pthread_t – deskriptor niti;

2. pthread_attr_t – lista atributa niti.

Funkcije kontrole niti:

1. pthread_create() – kreiranje niti;

2. pthread_exit() – završetak niti (mora biti pozvan od strane funkcije niti nakon završetka);

3. pthread_cancel() – otkazati nit;

4. pthread_join() – blokira izvršavanje niti dok se druga nit navedena u pozivu funkcije ne završi;

5. pthread_detach() – oslobađanje resursa koje zauzima nit (ako je nit pokrenuta, resursi će biti oslobođeni nakon njenog završetka);

6. pthread_attr_init() – inicijalizira strukturu atributa niti;

7. pthread_attr_setdetachstate() – ukazuje sistemu da nakon što se nit završi, može automatski osloboditi resurse koje zauzima nit;

8. pthread_attr_destroy() – oslobodi memoriju iz strukture atributa niti (uništi deskriptor).

Funkcije sinhronizacije niti:

2. pthread_mutex_init(), pthread_mutex_destroy(), pthread_mutex_lock(), pthread_mutex_trylock(), pthread_mutex_unlock();

3. pthread_cond_init(), pthread_cond_signal(), pthread_cond_wait().

Primjer korištenja niti u C:

#include

static void wait_thread(void)

time_t start_time = vrijeme(NULL);

dok (vrijeme(NULL) == vrijeme_početka)

/* ne radi ništa osim žvakanja CPU rezova do jedne sekunde. */

statički void *thread_func(void *vptr_args)

za (I = 0; I< 20; i++)

fputs(“b\n”, stderr);

pthread_t thread;

if (pthread_create(&thread, NULL, thread_func, NULL) != 0)

return EXIT_FAILURE;

za (I = 0; I< 20; i++)

if (pthread_join(thread, NULL) != 0)

return EXIT_FAILURE;

return EXIT_SUCCESS;

Predstavljeni program koristi dvije niti koje ispisuju poruke na konzolu, jedna koja ispisuje "a", druga - "b". Izlaz poruke je pomiješan kao rezultat prebacivanja izvršenja između niti ili istovremenog izvršavanja na višeprocesorskim sistemima.

C program kreira jednu novu nit za štampanje "b", a glavna nit štampa "a". Glavna nit (nakon ispisa "aaaaa....") čeka da se podređena nit završi.

Kontrolna pitanja

Šta je paralelni program?
Koja je razlika između procesa i niti izvršenja?
Može li program kreirati 5 niti kada radi na četverojezgrenom procesoru?
Koje su karakteristike paralelnih programa dijeljene memorije?
Koji softverski alati postoje za razvoj paralelnih programa?
Zašto je OpenMP postao široko rasprostranjen prilikom kreiranja programa za PC, a ne, na primjer, MPI?