Uvod v strategije vzporedne obdelave
V prejšnjih poglavjih smo raziskali temeljne razloge, zakaj so superračunalniki in močno vzporedno izvajanje tako pomembni. Spoznali smo, da lahko z vzporednim izkoriščanjem več procesnih enot bistveno skrajšamo čas, potreben za reševanje zapletenih problemov. Toda čeprav je korist vzporednega računalništva očitna, se poraja vprašanje: kako pravzaprav razdeliti problem, da lahko v celoti izkoristimo vzporedne vire?
To poglavje se osredotoča na različne strategije vzporedne obdelave, s katerimi lahko strukturiramo opravila za izrabo večjedrnih procesorjev, porazdeljenih sistemov ali specializiranih pospeševalnikov (kot so grafične procesne enote (GPU)). Obravnavali bomo tri glavne pristope:
- Vzporedna obdelava podatkov (Data Parallelism) – razdeljevanje velikih naborov podatkov v manjše dele, ki se obdelujejo istočasno, ko vsak del zahteva podobno obdelavo.
- Vzporedna obdelava opravil (Task Parallelism) – izvajanje več različnih opravil hkrati, kar je idealno, ko se posamezna opravila lahko izvajajo neodvisno.
- Cevovodna (Pipeline) vzporedna obdelava – razdelitev opravila v zaporedne faze, pri čemer se vsaka faza lahko obdeluje neodvisno, podobno tekočemu traku v proizvodnji.
V vsaki sekciji bomo ob primerih iz resničnega sveta (od obdelave slik do letaliških postopkov) pokazali, kako te metode v praksi delujejo. Z razumevanjem, kdaj in kako uporabiti določeno metodo, lahko obsežne in časovno zahtevne izračune pretvorimo v učinkovite poteke dela, ki popolnoma izkoristijo sodobne vzporedne sisteme.
Vzporedna obdelava podatkov (Data Parallelism)
Vzporedna obdelava podatkov je ena najbolj neposrednih in učinkovitih metod pri vzporednem računalništvu. Temelji na razdeljevanju velikih naborov podatkov na manjše, neodvisne dele, ki jih hkrati obdelujemo na več procesorjih. Ta pristop je najustreznejši, ko je treba na različnih kosih podatkov izvesti enako operacijo.
Osnovni koncept
Pri takšni obliki vzporednosti se ista operacija izvaja nad več elementi podatkov istočasno. Denimo, da želimo sliko pretvoriti v sivinsko različico: sliko razdelimo na več delov, pri čemer vsak del obdeluje drug procesor. Ker je operacija enaka za vse dele, se lahko vsi deli obdelujejo hkrati, kar bistveno skrajša postopek.
Primer: Obdelava slik
Zamislite si zbirko tisočev slik. Če želite na vsaki sliki izvesti transformacijo, na primer skaliranje ali filtriranje, bi zaporedna obdelava vsako sliko obdelala posamično. V vzporednem okolju lahko več procesorjev istočasno obdela različne slike, kar drastično zmanjša skupni čas obdelave. Podobno velja za video upodabljanje, fizične simulacije in velike podatkovne analize.
Primerjave z resničnim svetom
Vzporedna obdelava podatkov ni omejena zgolj na računalništvo. Če se en sam kombajn loti celotnega polja, bo delo potekalo precej dlje, kot če bi več kombajnov hkrati obdelovalo različne dele. V proizvodnji pa je pogosto več izdelkov v isti fazi obdelave, le da jih obdelujejo vzporedno in z enakimi postopki.
Uporabnost pri superračunalnikih
V superračunalništvu je takšna vzporedna obdelava podatkov praviloma najbolj učinkovit način izkoriščanja stotin ali celo tisočev procesorskih jeder in GPU-jev. Kadar obsežni nabori podatkov, kot so podnebni modeli ali zbirke genomskih zaporedij, potrebujejo enako vrsto obdelave, lahko razdelitev na manjše sklope in razporeditev med številna vozlišča oziroma GPU-je prinese izjemen pospešek. Superračunalniki so namreč zasnovani prav za takšne množično vzporedne (massively parallel) obremenitve.
Vzporedna obdelava opravil (Task Parallelism)
Za razliko od vzporedne obdelave podatkov, kjer je operacija enaka, a podatki različni, se pri vzporedni obdelavi opravil več različnih opravil izvaja istočasno. Vsako opravilo lahko zahteva drugačno vrsto obdelave ali uporablja drugačen nabor podatkov.
Osnovni koncept
Vsak procesor pri takšni obliki vzporednosti obdela drugačno opravilo. Na primer, na spletnem strežniku lahko en procesor posreduje spletne strani, drugi pa obdeluje poizvedbe v podatkovni bazi. Ker sta opravili neodvisni, se lahko izvajata vzporedno in se med seboj ne ovirata.
Primer: Letališke operacije
Letališče lepo ilustrira vzporedno obdelavo opravil: prijava potnikov, obdelava prtljage, točenje goriva v letala in urejanje vzletov ter pristankov se vse odvija sočasno. Ker ta opravila med seboj niso neposredno odvisna, lahko potekajo paralelno in zagotovijo nemoteno delovanje letališča.
Gradbišče kot primer
Na gradbišču je polaganje opek, mešanje betona in napeljava elektrike vsak zase neodvisna naloga. Če potekajo hkrati, se celoten projekt zaključi hitreje, saj se delo na posameznih delih ne čaka zaporedno.
Uporabnost pri superračunalnikih
Vzporedna obdelava opravil se sicer lahko uporablja tudi na superračunalnikih, vendar je pri velikem številu jeder manj učinkovita kot obdelava podatkov. Za različno kodo in različen nabor podatkov je namreč kompleksno zagotoviti optimalno razporeditev na stotine ali tisoče procesorjev. Kljub temu pa pri določenih večnamenskih scenarijih – še posebej, če vsako opravilo potrebuje več virov – tudi tak pristop najde svojo vrednost.
Cevovodna (Pipeline) vzporedna obdelava
Cevovodna vzporedna obdelava je razširitev obdelave opravil, pri kateri je opravilo razdeljeno na zaporedne faze. Ko ena faza konča, njen rezultat preide v naslednjo, podobno tekočemu traku v tovarni.
Osnovni koncept
Pri cevovodni obdelavi podatki potujejo skozi niz faz. Če ena faza obdeluje podatke, lahko druga faza istočasno dela na drugem sklopu. Tako se obdelava prekriva in izkoriščenost virov poveča. Ta pristop je koristen, kadar je pomembno strogo zaporedje korakov, vendar jih je možno izvesti sočasno na različnih sklopih podatkov.
Primer: Tekoči trak
V proizvodnji se pri tekočem traku izdelek postopoma pomika od ene postaje do druge: ena postaja sestavlja, druga barva, tretja pakira. Vsaka faza je sicer odvisna od prejšnje, a zaradi hkratnega delovanja različnih postaj sistem teče hitreje kot pri zaporedni izdelavi enega izdelka naenkrat.
Kuhanje
V restavracijski kuhinji lahko en kuhar pripravlja sestavine, drugi kuha, tretji pa že dokončuje krožnik. Čeprav morajo koraki potekati v določenem vrstnem redu, lahko potekajo sočasno za različne jedi.
Uporabnost pri superračunalnikih
Cevovodna obdelava se v superračunalništvu pojavlja redkeje, saj so ti sistemi večinoma prilagojeni množični (data) ali zmerni (task) vzporednosti. V posebnih primerih, ko je več vozlišč moč serijsko povezati (denimo za predobdelavo, simulacijo in vizualizacijo), pa lahko taki cevovodi vendarle najdejo svojo rabo.
Dodatni primeri vzporednosti iz vsakdana
Vzporednost ni omejena na računalništvo. Zavedanje, da lahko več opravil poteka sočasno v realnem življenju, prikazuje prednosti in izzive takega pristopa.
Kmetijstvo
Na večjih kmetijah deluje več strojev istočasno: za sajenje, žetev ali vzdrževanje. Tako se polje obdela hitreje, kot če bi se ga lotil samo en stroj.
Proizvodnja
Pri množični proizvodnji je uporaba vzporednosti nujna za večjo produktivnost. Tovarne pogosto hkrati izvajajo več vrst nalog (vzporedna obdelava opravil) in razdelijo delo po fazah (cevovodna obdelava), kar omogoča hitro izdelavo v velikih količinah.
Turizem
V velikih turističnih znamenitostih lahko več vodnikov istočasno vodi različne skupine, da se izognemo zastojem in dolgemu čakanju. Tako lahko znamenitost obišče bistveno več obiskovalcev v istem času.
Programska oprema
Sodobni spletni brskalniki omogočajo, da ima vsak zavihek svojo nit ali jedro. Tako lahko odpremo več zavihkov, ne da bi se uporabniška izkušnja opazno poslabšala, kar kaže na vzporedno obdelavo opravil tudi v vsakdanjih programih.
Promet
Več avtobusov, vlakov in letal lahko vozi neodvisno po različnih urnikih. Medtem ko en avtobus še prihaja na postajo, se drugi že odpelje, kar zagotavlja tekoč promet in preprečuje ozka grla.
Z razumevanjem teh strategij vzporedne obdelave – vzporedne obdelave podatkov, opravil in cevovodne obdelave – ter kako se prilegajo superračunalnikom (najbolj učinkovito, zmerno ali redkeje) lahko sprejemamo utemeljene odločitve pri načrtovanju vzporednih opravil. To je ključno za popoln izkoristek sodobne HPC (High Performance Computing) infrastrukture in za pospešitev tudi najzahtevnejših znanstvenih, raziskovalnih ali industrijskih projektov.