Konkurentno i paralelno programiranje: definicija, prakse i metrike

Formarse » Besplatni online tečajevi » Konkurentno i paralelno programiranje: definicija, prakse i metrike

Ako se bavite razvojem, vjerovatno ste čuli za konkurentnost i paralelizam, ali nije uvijek jasno gdje jedno završava, a drugo počinje. Ukratko, Obje tehnike nastoje bolje iskoristiti sistemske resurse, iako teže malo drugačijim ciljevima i provode se pomoću različitih alata i kriterija.

Prije nego što se upustimo u detalje, vrijedi napomenuti da, iako se često koriste kao sinonimi u svakodnevnom jeziku, oni to nisu. U stvari, Konkurencija opisuje kako strukturiramo i koordiniramo zadatke koji koegzistiraju, dok se paralelizam odnosi na istovremeno izvršavanje nekoliko ovih zadataka na odgovarajućem hardveru. Odavde, hajde da to polako razložimo i objasnimo jasnim primjerima.

Jasna definicija konkurentnosti i paralelizma

Kada govorimo o konkurentnosti, mislimo na sposobnost sistema da upravlja više zadataka koji se odvijaju na preklapajući način. To se može dogoditi na jednom CPU-u bez stvarnog izvršavanja više instrukcija istovremeno: Sistem se naizmjenično preklapa između zadataka (ispreplitanje) tako da sav napredak, smanjujući vrijeme čekanja i poboljšavajući korisničko iskustvo. To je pristup dizajnu i koordinaciji softvera.

Paralelizam, sa svoje strane, zasnovan je na ideji "zavadi pa vladaj": Veliki problem dijelimo na podprobleme i te dijelove obrađujemo istovremeno. na više računarskih jedinica (jezgara, procesora ili čvorova). Ovo je pravo paralelno izvršavanje; stoga, performanse uveliko zavise od dostupnog hardvera.

U praksi, ova dva koncepta su povezana: konkurentnost opisuje orkestraciju zadataka, dok paralelizam opisuje simultano izvršavanje. Zato se ponekad kaže da Konkurencija se fokusira na dizajn softvera, a paralelizam na njegovo izvršavanjeTo su dvije strane iste medalje, ali nisu zamjenjive.

Važno pojašnjenje: ponekad ćete vidjeti definicije koje izjednačavaju konkurentnost s obradom više procesa istovremeno. U stvarnosti, Ova konkurentnost je obično očigledna na jednojezgrenim mašinama., zahvaljujući brzim promjenama konteksta; prava konkurentnost odgovara paralelizmu i zahtijeva više procesorskih jedinica.

Ključne razlike i hardverski zahtjevi

Jedna praktična razlika leži u sistemskim zahtjevima. Da bi se postigao pravi paralelizam, potrebno je više računarskih jedinica: više jezgara, procesora ili mašinaS druge strane, konkurentnost se može implementirati na jednoj jezgri naizmjeničnim izvršavanjem zadataka. To direktno utiče na troškove hardvera.

Glavna svrha se također razlikuje: dok je saglasnost smanjuje percipiranu latenciju i poboljšava odziv sistema upravljanjem više tekućih zadataka, paralelizam nastoji ubrzati ukupno vrijeme izvršavanja zadatka tako što ga dijeli i izvršava istovremeno.

Još jedna vrlo korisna razlika: paralelno, podzadaci su obično blisko povezani i njihovi rezultati se kombinuju u završni korak. U konkurentnosti, Zadaci mogu biti nezavisni i ne zavise jedan od drugog; svaki napreduje svojim tempom i završit će kada dođe vrijeme, bez nužne sinhronizacije s ostalima.

Konačno, u svrhu dizajna, često kažemo da se konkurentnost odnosi na to kako strukturiramo program u jedinice koje koegzistiraju i kako one komuniciraju, dok se paralelizam odnosi na kako pokrenuti te jedinice zajedno da bi se postigle performanseMožete imati konkurentnost bez paralelizma (jedno jezgro koje naizmjenično izvršava zadatke) i paralelizam bez mnogo konkurentnosti (čisto izračunavanje podataka podijeljenih i izvršavanih paralelno).

Svakodnevni primjeri kako biste izbjegli zabunu

Zamislite aplikaciju za preuzimanje muzike. Korisnik odabire nekoliko pjesama, a aplikacija mu omogućava da ih preuzme "odjednom". Glavna ideja ovdje je da Svako preuzimanje je nezavisno i ne utiče na ostala.Ako je jedan spor, to ne usporava ostale. Ovo je tipičan scenario konkurentnosti: više zadataka koegzistira i kreće se naprijed, moguće naizmjenično koristeći CPU-e na istoj jezgri.

Sada zamislite stranicu za poređenje letova. Primamo kriterije korisnika (datume, odredište, broj zaustavljanja) i pokrećemo istovremene pretrage za nekoliko aviokompanija. U ovom slučaju, sve pretrage doprinose jednom konačnom rezultatuPronaći najbolju ponudu. Moramo sačekati da svi završe, prikupiti rezultate i kombinovati ih. Ovo je klasična strategija paralelizma zasnovana na podjeli posla i sinhronizaciji na kraju.

Ključno zapažanje u paralelizmu je korak spajanja rezultata. Nakon particioniranja problema, mora postojati faza kombinovanja koja integrirati djelomične odgovore u konačno rješenjeBez tog koraka, paralelizam ne isporučuje kompletan proizvod.

U stvarnom svijetu, oba obrasca često koegzistiraju. Na primjer, web stranica može istovremeno obrađivati ​​mnogo korisničkih zahtjeva, a unutar svakog od njih, izvršavanje paralelnih rutina koje koriste prednosti više jezgara da ubrzaju intenzivne proračune.

Hardverski i softverski modeli: Pregled

Da bismo razumjeli mogućnosti, vrijedi pregledati pejzaž paralelnog hardvera i softvera koji ga iskorištava. Što se tiče hardvera, Postoje različiti nivoi paralelizmaod više jezgara u jednom procesoru do klastera mašina sa distribuiranom memorijom. Flynnova hijerarhija klasificira arhitekture u kategorije kao što su SISD, SIMD, MISD i MIMD.

Sa strane softvera, krećemo se između procesa i niti. Proces ima svoj vlastiti adresni prostor, dok više niti dijeli memoriju u istom procesuIzbor jednog ili drugog uključuje odluke o troškovima komunikacije, izolacije i sinhronizacije.

Operativno, niti su lagane i brze u dijeljenju podataka, ali zahtijevaju izuzetnu pažnju u pogledu integriteta memorije. Procesi, s druge strane, Nude izolaciju i sprečavaju određene vrste korupcije, u zamjenu za skuplje komunikacije i veću potrošnju resursa.

Ciljevi, ose i raščlamba osnovnog sadržaja

Dobar program obuke za konkurentno i paralelno programiranje obično je organiziran u velike dijelove. Prvi je Razumijevanje motivacija i trendova: Zašto nam je potrebno paralelno računarstvo, kakve podjele odgovornosti olakšavaju dizajn i kako performanse utiču na odluke.

U bloku Paralelni hardver, proučavaju se modeli i hijerarhije, uključujući Flynnovu taksonomiju, GPU-ove i višejezgrene/NUMA sisteme. Blok Paralelni softver bavi se koncept procesa i niti, njegovi API-ji i kako organizirati adresni prostor i dijeljenu ili distribuiranu memoriju.

Druga osa se vrti oko dizajniranja konkurentnih i distribuiranih rješenja. To uključuje razumijevanje šta razlikuje paralelne algoritme od serijskih i kako... Analiziramo prostor i vrijeme u prisustvu prisutnih i komunikacije.

Također su obuhvaćene tehnike dekompozicije: rekurzivna, data-driven, istraživačka, spekulativna i druge. Bez dobre dekompozicije, paralelizam ne kompenzira preopterećenjeOsim toga, zadaci moraju biti mapirani na procese ili niti, balansirajući opterećenje i minimizirajući interakciju.

Najčešće korišteni paralelni programski modeli spadaju u ovu osu: paralelizam podataka (ista operacija na više elemenata), graf zadataka (eksplicitne zavisnosti) i obrazac radni bazen (skup poslova koje niti dinamički koriste). Ovi modeli pomoć pri raspravi o distribuciji i vremenu.

Treći blok se fokusira na rješavanje tipičnih problema sinhronizacije i koordinacije. Ovdje se proučavaju simbolični slučajevi, kao što su proizvođač-potrošač, komenzalni filozofi, problem pušača, brijačnica, problem Djeda Mraza, formiranje vode i takozvani problem Modus Halla. Svaki od njih ilustruje opasnosti poput gladi, zastoja i uslova trke.

Sljedeći blokovi se fokusiraju na Izgradnju konkurentnih programa sa dijeljenim resursima (po nitima) i Izgradnju konkurentnih programa sa distribuiranim resursima (po procesima). U prvom, radite sa interfejsi poput Pthreads i OpenMP, zajednički adresni prostor je shvaćen i učite pratiti memoriju i aktivnost niti.

Drugi se bavi konkurentnošću u procesima s distribuiranom memorijom i API-jima kao što je MPI. Proučava paralelni ulaz i izlaz, kao i komunikacija od tačke do tačke i kolektivna komunikacija (emitovanje, raspršivanje, prikupljanje, sveobuhvatna redukcija). Također se vježba skeniranje memorije i procesa.

Konačno, postoje odjeljci o testiranju softvera i evaluaciji i poređenju. Testiranje pokriva tehnike crne i bijele kutije prilagođene konkurentnosti i distribuciji. Evaluacija pokriva Amdahlov zakon, metrike ubrzanja, efikasnosti i skalabilnosti, mjerenje vremena na zidu i vizualizacija pomoću grafike.

Tehnike dekompozicije: kako razložiti problem

Izbor načina podjele radnog opterećenja čini razliku između dobijanja ili gubitka performansi. Dekompozicija podataka dodjeljuje podskupove skupa podataka različitim izvršiteljima; čini čuda u homogenim operacijama kako primijeniti filter na piksele ili iterirati kroz liste.

Rekurzivna dekompozicija se pojavljuje u metodi "zavadi pa vladaj": problem se fragmentira na manje podprobleme do određenog praga; paralelno sortiranje spajanjem ili brzo sortiranje su klasični primjeriIstraživačka dekompozicija dodjeljuje različite grane ili scenarije pretraživanja različitim nitima ili čvorovima.

Spekulativna dekompozicija paralelno provodi alternativne puteve ili pretpostavke, prihvatajući da neki proračuni su uzaludni ako nisu potrebniKorisno je kada predviđamo da bi nekoliko grana moglo biti validno, ali ne znamo koja a priori.

Bez obzira na tehniku, morate razmisliti o troškovima koordinacije: ako su previsoki, paralelizam gubi na efikasnostiZato je granulacija rada ključna: zadaci koji nisu ni premali ni toliko veliki da narušavaju ravnotežu radnog opterećenja.

Mapiranje zadataka i balansiranje opterećenja

Nakon što je dekompozicija odlučena, vrijeme je za dodjeljivanje zadataka procesima ili nitima. Statičko mapiranje unaprijed raspoređuje posao; Jednostavno je i jeftino, ali može postati neuravnoteženo ako su zadaci nepravilni. Dinamičko mapiranje (ili rad kradu) omogućava podešavanje u hodu.

Balansiranje opterećenja ima za cilj osigurati da su svi izvršitelji razumno zauzeti. To se postiže korištenjem dijeljenih ili lokalnih redova s ​​krađom posla. Osim toga, smanjiti preopterećenje interakcijom između zadataka, minimiziranje komunikacija i kritičnih područja.

U distribuiranim okruženjima, afinitet podataka i topologija mreže utiču na alokaciju. Približavanje podataka onima koji ih obrađuju izbjegava latencije i uska grlaU dijeljenoj memoriji, preporučljivo je izbjegavati lažno dijeljenje kako bi keš memorije radile u vašu korist, a ne protiv vas.

Modeli paralelnog programiranja

Paralelizam podataka primjenjuje istu operaciju na različite elemente paralelno; Idealan je za GPU-ove i SIMD-oveGraf zadataka definira čvorove sa zavisnostima, omogućavajući planerima da izvrše ono što je već spremno bez narušavanja redoslijeda.

Šef radni bazen Grupira poslove u red; više radnika ih koristi i proizvodi rezultate. Njegova snaga leži u njegovoj prilagodljivosti: Ako jedan zadatak traje duže, drugi napreduju u međuvremenuKoristi se u cjevovodima, serverima i pretraživačima.

Izbor modela ne utiče samo na performanse: on takođe određuje koliko je lako zaključiti o ispravnosti i tačnosti. mogućnost uvođenja ili izbjegavanja blokada, aktivna čekanja i uslovi trke.

Nitna konkurentnost i dijeljena memorija

U dijeljenoj memoriji, više niti pristupa istom adresnom prostoru. To omogućava prenos podataka putem reference bez kopiranja, ali zahtijeva osiguranje integriteta. Najčešći alati su Pthreadovi i OpenMPPrvi nudi detaljnu kontrolu; drugi, direktive visokog nivoa ugrađene u kompajler.

Izazov je napisati kod bez uslova utrke. Moramo zaštititi kritične regije mutexima ili bravama za čitanje i pisanje, koristiti varijable uslova za koordinaciju i oslanjaju se na barijere i operacije smanjenja kada je to prikladno.

Nadalje, potrebno je razlikovati reentrantni i nereentrantni kod: reentrantni kod se može izvršavati paralelno bez rizika ako ne održava globalno stanje. Ovo je uslov za pravilan govor o kod siguran za korištenje u više niti, koji podnosi istovremeno izvršavanje bez oštećenja podataka.

Konkurencija po procesima i distribuirana memorija

Kada svaki proces ima svoju memoriju, na scenu stupaju biblioteke poput MPI-ja. Ovdje se podaci ne dijele: šalju se eksplicitne porukeOvo povećava otpornost na greške u dijeljenoj memoriji, ali po cijenu povećanog komunikacijskog opterećenja.

MPI nudi i komunikaciju od tačke do tačke (slanje/prijem) i kolektivnu komunikaciju (emitovanje, raspršivanje, prikupljanje, svi-svima, redukcija). Prilikom dizajniranja, važno je imati jasnu predstavu o zahtjevima za paralelni ulazno/izlazni promet: Dobar obrazac pristupa disku može promijeniti pravila igre pri intenzivnom opterećenju podacima.

Horizontalna skalabilnost je njen prirodni teren: ako problem raste, dodajemo još čvorova. Međutim, latencija mreže i kolektivna sinhronizacija zahtijevaju algoritme koji ograničite vrijeme čekanja i favorizujte lokalno računanje.

Sinhronizacija: uobičajeni mehanizmi i zamke

Za koordinaciju niti ili procesa koristimo primitive za sinhronizaciju. U dijeljenoj memoriji, klasični su mutex, semafori, brave za čitanje i pisanje i varijable uslova. Na višem nivou, koristimo barijere i redukcije za globalne tačke susreta.

Zauzeto čekanje ima lošu reputaciju, i to s dobrim razlogom: Zauzima CPU bez obavljanja korisnog poslaTo je opravdano samo u scenarijima s minimalnom latencijom i vrlo kratkim trajanjem. Općenito preferiramo blokiranje čekanja koje oslobađa CPU dok ne bude posla koji treba obaviti.

Tipični problemi uključuju zastoje, aktivne zastoje (niko ne napreduje iako se svi kreću), gladovanje (neke niti nikada ne napreduju) i loše upravljane prioritete. Dizajnirajte s potpunim redom u prikupljanju resursa i razumna vremena čekanja pomaže u njihovom izbjegavanju.

Testiranje ispravnosti u konkurentnim programima

Testiranje konkurentnog softvera nije trivijalno jer kvarovi mogu biti nedeterministički. Međutim, postoje strategije. Testiranje crne kutije validira interfejs i uočljivo ponašanje; Bijele kutije, prožimaju betonske elemente sile kako bi se otkrili trčanja i blokovi.

Alati za detekciju utrke podataka, statička analiza i provjera modela su odlični saveznici. Osim toga, preporučljivo je ubrizgati greške (npr. nasumično dodavanje malih čekanja) u povećati vjerovatnoću otkrivanja problematičnih preplitanja tokom testova.

U distribuiranim procesima, testiranje komunikacija i simulacija mrežne particije su neophodni. I nikada ne zaboravite precizno zabilježiti: dobro praćenje događaja i vremena To je čisto zlato kada je u pitanju rafiniranje.

Metrike performansi: ubrzanje, efikasnost i skalabilnost

Za objektivnu procjenu koristimo standardne metrike. Ubrzanje mjeri koliko paralelni program ubrzava u poređenju sa serijskim programom. Efikasnost normalizuje ovo ubrzanje brojem resursa, što ukazuje na... Koji dio kapaciteta koristimo.

Amdahlov zakon nas podsjeća da neparalelizabilni dio ograničava maksimalno ubrzanje: čak i ako dodate beskonačne resurse, Sekvencijalni dio postavlja plafonParalelno s tim, Gustafsonov zakon nudi drugu perspektivu kada veličina problema raste s resursima.

Skalabilnost opisuje kako se performanse mijenjaju s povećanjem podataka i resursa. Razlikujemo jaku skalabilnost (riješen problem, više resursa) i slabu skalabilnost (problem raste kako resursi rastu). Obje Zahtijevaju rigorozno mjerenje vremena provedenog na zidu (zidni sat) i rezultate predstavite u jasnim grafikonima.

Praktični zahtjevi i troškovi

U paralelizmu, hardver je na snazi: da bi se zaista istovremeno izvršavalo više zadataka, potrebno je više jezgara ili mašina. To donosi troškove i operativnu složenost. Međutim, u konkurentnosti... Možete poboljšati odziv na jednoj jezgri, uz manje ulaganja, ako dobro dizajnirate.

Ne dajte se zavarati: ne ubrzava se svaki paralelizam. Ako dominira komunikacija ili sinhronizacija, Preopterećenje može uništiti koristZato toliko insistiramo na dekompoziciji, mapiranju i odabiru pravog modela za svaki problem.

Klasične studije slučaja i obrasci

Kanonske vježbe postoje s razlogom: one uče obrascima koordinacije i zamkama koje treba izbjegavati. Proizvođač-potrošač ilustruje redove čekanja, signale i povratni pritisak. Komenzalni filozofi otkrivaju zastoje i kako... prekršite simetrije da biste ih izbjegli.

Problemi pušača, brijačnica i Djeda Mraza nas tjeraju da razmišljamo o propisima, obavještenjima i jednakosti. Formiranje vode uči atomske kombinacije i barijere za poravnavanje entiteta. Modus Hall (u svojoj klasičnoj formulaciji) je još jedan izgovor za praktikovanje ovih mehanizama.

Kombinovanje ovih obrazaca sa dobrim bibliotekama (Pthreads, OpenMP, MPI) i solidnim testiranjem priprema vas za stvarni život: web servise sa visokom konkurentnošću, naučno računanje koje stišće jezgra i distribuirane podatkovne kanale.

Kada se sve ovo mudro primijeni, rezultat je brži, skalabilniji i jednostavniji za korištenje softver. Ključno je znati kada je konkurentnost najbolja za vas, kada je paralelizam najbolji za vas i, prije svega, kako ga koristiti. natjerajte ih da žive zajedno, a da jedno drugom ne gaze na žulj u dobro osmišljenoj arhitekturi.

Gledajući širu sliku, konkurentnost vam omogućava da istovremeno opslužujete više zadataka i brže reagujete, čak i sa jednom jezgrom kroz alternaciju, dok paralelizam povećava performanse rješavanjem jednog zadatka istovremenim na više računarskih jedinica; uz odgovarajuće tehnike dekompozicije, mapiranja, sinhronizacije i testiranja, a podržan modelima kao što su paralelizam podataka, grafovi zadataka ili objedinjavanje posla. Moguće je dizajnirati sisteme koji podnose veliko opterećenje, a ujedno i rade brže. bez gubitka ispravnosti.