Rinnakkaisen ohjelmakoodin kirjoittaminen

Käy läpi seuraava lista ennen rinnakkaistamista

Valitse numeerisesti vakaa ja tehokas algoritmi
- Tehoton tai epävakaa rinnakkainen ohjelmakoodi ei ole kenellekkään hyödyksi
Etsi ohjelmakoodin ns. "kuumat pisteet" (hotspots)
Tunnista rinnakkaistamista rajoittavat tekijät
Selvitä voidaanko hotspotit rinnakkaistaa

Onko tehtävä rinnastettavissa?

Rinnakkaistuva tehtävä

Laske sisätulo \[ x \cdot y = \sum_{i=1}^{n} x_iy_i, \; x,y \in \mathbb{R}^n \]
Joukko \(\{1, 2, \dots, n\}\) voidaan jakaa osajoukkoihin \(M_1, M_2, \dots, M_m\), jolloin \[ x \cdot y = \sum_{j=1}^{m} \underbrace{\left( \sum_{i \in M_j} x_iy_i \right)}_{\text{Rinnakkainen tehtävä}} \]

Havainnekuva sisätulon laskemisesta rinnakkain

Ei-rinnakkaistuva tehtävä

Laske Fibonaccin luvut \[ F_1 = 0, \\ F_2 = 1, \\ F_i = F_{i-2} + F_{i-1}, \; 3 \leq i \]
Seuraava luku jonossa riippuu kahdesta edellisestä, tehtävä ei rinnakkaistu:

Keskity hotspotteihin

Tunnista ohjelmakoodin hotspot'it eli koodirivit, joissa tehdään eniten töitä
Keskity hotspot'ien rinnakkaistamiseen, unohda turha virittely
Koodirivien määrä \(\neq\) tehtävä työ:

Hotspottien tunnistaminen

Hotspottien löytäminen ei ole välttämättä triviaali tehtävä vaan vaatii algoritmin toiminnan syvällistä ymmärrystä
Jos ohjelmakoodi on tuntematon, sisäkkäisten silmukoiden etsiminen on hyvä paikka aloittaa. Laske iteraatiomäärät ja arvioi iteraation hinta (kompleksisuusanalyysi):

Erilaiset profilointityökalut ovat myöskin hyödyksi

Esimerkkejä kompleksisuusanalyysistä

Luokkaa \(\mathcal{O}(1)\) laskentaoperaatiota:

double y = x + 7.0;

Luokkaa \(\mathcal{O}(2N) = \mathcal{O}(N)\) laskentaoperaatiota:

for(int i = 0; i < N; i++) 
    y[i] = 4.0 * x[i] + 7.0;

Luokkaa \(\mathcal{O}(N(1 + 2M)) = \mathcal{O}(NM)\) laskentaoperaatiota:

for(int i = 0; i < N; i++) {
    x[i] = x[i] + 5.0;
    for(int j = 0; j < M; j++)   
        y[i] =  A[i][j] * x[i] + 7.8;
}

Tehtävän osituksesta

Rinnakkaisen ohjelmakoodin toteutuksessa lähdetään liikkeelle tehtävän jakamisesta osiin eli osituksesta (partition, decomposition)
Kaksi lähestymistapaa: toiminnallinen ositus (functional decomposition) ja tilaositus (domain decomposition)
Myöskin termit tehtävärinnakkaisuus (task parallel) ja datarinnakkaisuus (data parallel) esiintyvät usein

Toiminnallinen ositus / Tehtävärinnakaisuus

Laskennalliset tehtävät jaetaan laskentasolmujen kesken

Tilaositus / Datarinnakaisuus

Laskennassa käytettävä data jaetaan laskentasolmujen kesken

Tehtävärinnakaisuus vs datarinnakaisuus

Tehtävä- ja datarinnakkaisuuden välillä sijaitsee jatkumo
Ohjelman eri osat saattavat hyödyntää eri suhteissa tehtävä- ja datarinnakkaisuutta

Esimerkki tehtävä- ja datarinnakkaisuuden yhdistämisestä

Tarvitaanko kommunikointia aina?

Jotkut tehtävät voidaan rinnakkaistaa ilman kommunikointia
Termiä embarrassingly parallel viljellään paljon tässä yhteydessä
Myöskin termi triviaalisti rinnakkaistuva on esiintynyt joissakin lähteissä
Esimerkiksi kahden vektorin yhteenlasku \(x+y\), \[ (x + y)_i = x_i + y_i, \; i=1,\dots,n, \; x,y \in \mathbb{R}^n, \] ei vaadi kommunikointia ja on siten triviaalisti rinnakkaistuva:

Milloin kommunikointia tarvitaan?

Usein kommunikointi on tarpeellista
Esimerkiksi sisätulon laskeminen tarvitsee kommunikointia:

Kommunikoinnin laajuus (scope)

Pisteestä pisteeseen -kommunikointi (point-to-point): Kaksi tehtävää kommunikoivat keskenään. Toinen tehtävistä on lähettäjä ja toinen vastaanottaja.

Kollektiivinen kommunikointi

Kollektiivinen kommunikointi (collective): Useat tehtävät osallistuvat kommunikointiin

Synkroninen kommunikointi

Synkroniseen kommunikointiin liittyy tyypillisesti jonkinlainen kättely (handshaking)
Viestin vastaanottaja kuittaa viestin ja lähettäjä saa tiedon onnistuneesta siirrosta
Kyseessä on ns. blocking-tyyppinen kommunikointi eli prosessien tulee odottaa kunnes kommunikointi on saatettu loppuun

Esimerkki synkronisesta kommunikoinnista

Asynkroninen kommunikointi

Asynkroniseen kommunikointiin ei liity kättelyä
Viestin lähettäjä ei odota kuittausta
Kyseessä on ns. non-blocking-tyyppinen kommunikointi eli prosessit eivät odota kommunikoinnin loppumista
Laskenta ja kommunikointi voivat tapahtua samanaikaisesti
Parantaa useimmissa tilanteissa ohjelmakoodin tehokkuutta, mutta on hankalampi toteuttaa

Esimerkki asynkronisesta kommunikoinnista

Synkronointi

Synkronointi mahdollistaa rinnakkaisien tehtävien suorituksen koordinoinnin
Käytetään tilanteissa, joissa halutaan
- varmistua siitä, että kaikki tehtävät ovat suorittaneet jonkin toiminnon (esim. ratkaisseet osatehtävän)
- halutaan suojata jokin resurssi (esim. jaettu muistiresurssi)

Synkronointi “esteen” (barrier) avulla

Käytetään tilanteissa, joissa halutaan varmistua siitä, että kaikki tehtävät ovat suorittaneet jonkin toiminnon
Yleensä kaikki tehtävät osallistuvat synkronointiin
Kaikki tehtävät tekevät töitä kunnes saavuttavat erityisen synkronointipisteen
Tehtävät odottavat muita tehtäviä synkronointipisteessä
Synkronointiin saattaa liittyä erityisen ohjelmakoodin suorittaminen tai tehtävät saattavat jatkaa suoritustaan normaalisti

Esimerkki synkronoinnista esteen avulla

Synkronointi lukon tai semaforin avulla

Käytetään tyypillisesti jonkin resurssin suojaamiseen
Synkronointiin osallistuvien tehtävien määrä voi vaihdella
Ensimmäinen tehtävä ottaa haltuunsa lukon/semaforin. Vain yksi tehtävä voi omistaa lukon/semaforin kerrallaan
Muiden tehtävien tulee odottaa lukon/semaforin vapautumista
Lukko vs samafori
- Semafori asettaa tehtävät jonoon FIFO-periaatteella
- Lukon tapauksessa estetyt tehtävät yrittävät toistuvasti saada lukon käyttöönsä

Esimerkki kriittisen ohjelmakoodin suojaamisesta semaforin avulla

Synkronointi ja laitteisto

Esteen tai lukon/semaforin avulla tapahtuva synkronointi nojaa usein laitteistotason ominaisuuksiin:
- Erillinen konekielinen synkronointikomento rautatasolla tapahtuvaan synkronointiin (esim. GPU)
- Erilliset atomiset operaatiot lukkojen ja semaforien turvalliseen käsittelyyn (normaali prosessori)

Synkronointi viestinvälityksen avulla

Synkronointi voi tapahtua myös synkronisen viestinvälityksen avulla:
- Yksi tehtävä (master) odottaa muilta tehtäviltä synkronointipyytöä
- Muut tehtävät lähettävät synkronointipyynnön masterille ja jäävät odottamaan
- Master lähettää kuittauksen muille tehtäville saatuaan synkronointipyynnön kaikilta tehtäviltä ja jatkaa suoritustaan
- Muut tehtävät jatkavat suoritusta saatuaan kuittauksen masterilta

Latenssi ja kaistanleveys

Latenssi on aika, joka kuluu minimaalisen viestin (0 tavua) välittämiseen, joko muistin ja prosessorin tai prosessorien välillä. Ilmoitetaan (milli- tai mikro-) sekunteina tai kellojaksoina.
Kaistanleveys kertoo paljonko informaatiota voidaan siirtää annetun ajanjakson aikana. Ilmoitetaan usein gigatavuina sekunnissa.
\(L\) tavun kommunikoimiseen kuluu siis \[ t = t_{lat} + L/B \] aikayksikköä, jossa \(t_{lat}\) on latenssi ja \(B\) kaistanleveys

Havainnekuva latenssin ja kaistaleveyden erosta

Laskenta vs kaistanleveys vs latenssi

Laskenta on verrattain halpaa:
- Moderni CPU: \(\mathcal{O} (10^{10})\) Flops
- Moderni GPU: \(\mathcal{O} (10^{12})\) Flops
Datan siirtäminen on hieman kalliimpaa:
- Ethernet: \(\mathcal{O} (10^{8})\) B/s
- RAM-muisti: \(\mathcal{O} (10^{10})\) B/s
- GPU:n videomuisti: \(\mathcal{O} (10^{11})\) B/s

Laskenta vs kaistanleveys vs latenssi (jatkuu)

Latenssin aiheuttamat kustannukset ovat mittavat:
- Ethernet \(\mathcal{O} (10^{-3})\) sekuntia
- RAM-muisti / GPU:n videomuisti: \(\mathcal{O} (10^{-7})\) sekuntia
GPU voisi siis (erittäin karkeasti arvioiden)
- suorittaa \(\mathcal{O}(10)\) laskentaoperaatiota yhtä siirrettyä tavua kohden
- siirtää \(\mathcal{O}(10^4)\) tavua latenssiajan aikana
- suorittaa \(\mathcal{O}(10^5)\) laskentaoperaatiota latenssiajan aikana

Laskenta vs kaistanleveys vs latenssi (jatkuu)

On tehokkaampaa pakata useampi pieni viesti suuremman viestin sisälle ja tehdä välissä mahdollisimman paljon laskentaa:

Yhteenveto: kommunikointi on kallista

Kellojaksoja kuluu datan odottamiseen laskennan sijasta
Monimutkaistaa ohjelmakoodia (synkronointi jne)
Kommunikointi saattaa estää rinnakkaistamisen käytännössä kokonaan
Rajoittaa kääntäjän toimintaa
Annetun ajanjakson aikana voidaan suorittaa vain rajoitettu määrä kommunikointia

Datariippuvuudet

Ohjelman komentojen välillä on datariippuvuus silloin kun komentojen suoritusjärjestys vaikuttaa lopputulokseen
Seuraa tyypillisesti tilanteista, joissa samaa tallennuspaikkaa käyttää useampi tehtävä
Datariippuvuuksien ymmärtäminen on tärkeää, koska ne ovat yksi tyypillisimmistä rinnakkaistamisen estäjistä

Esimerkki datariippuvuudesta

Laske Fibonaccin luvut \[ F_1 = 0, \\ F_2 = 1, \\ F_i = F_{i-2} + F_{i-1}, \; 3 \leq i \]
Seuraava luku jonossa riippuu kahdesta edellisestä, tehtävä ei rinnakkaistu:

Datariipuvuuksien esittäminen graafin avulla

Datariippuvuudet voidaan esittää kompaktissa muodossa graafirakenteen (dependency graph) avulla:

Datariipuvuuksien käsitteleminen

Tunnista ohjelmakoodin toisistaan riippumattomat osat, ne voidaan käsitellä rinnakkain
Datariippuvuuksia sisältävät kohdan vaativat jonkin tyyppistä synkronointia:
- Hajautetun muistin tapaus: kommunikoi data synkronointipisteissä
- Jaetun muistin tapaus: synkronoi muistin käyttö tehtävien välillä

Kuorman jakaminen

Kuorman jakamisella (load balancing) tarkoitetaan laskentakuorman jakamista tehtävien kesken siten, että kaikki tehtävät työllistyvät
Voidaan ajatella “tyhjäkäyntiajan” minimoimisena
Esim. tilanne, jossa suuri joukko tehtäviä synkronoi esteen avulla. Tällöin hitain tehtävä määrää tahdin.

Kuorman jakaminen tasan tehtävien kesken

Soveltuu tilanteisiin, joissa tehdään paljon samanlaista työtä
Taulukko, jonka jokainen alkio käsitellään samalla tavalla
Silmukka, jonka jokainen iteraatio on yhtä kallis

Kuorman jakaminen dynaamisesti

Joissain tilanteissa tehtävän työn määrä saattaa vaihdella dynaamisesti tai työn jakaminen tasan on muuten mahdotonta/hankalaa
Ratkaisuksi saattaa sopia vuorotin (scheduler) ja “työpooli”, josta työ jaetaan dynaamisesti tehtävien kesken

Parallel Overhead

Rinnakkaistaminen aiheuttaa usein ylimääräistä työtä eli ns. parallel overhead'ia
Pahimmassa tapauksessa parallel overhead'in määrä kasvaa kun rinnakkaisuuden määrää lisätään
Parallel overhead'iin voi sisältyä esimerkiksi
- Tehtävien käynnistys- ja päättymisajat
- Kommunikointi ja synkronointi
- Dynaaminen kuorman jakaminen
- Käytetyn laskenta-alustan piilotetut kustannukset (käyttöjärjestelmä jne)

Havainnekuva parallel overhead'ista

Kuinka suuriin osiin tehtävä kannattaa osittaa?

Jotkin tehtävät jakautuvat helposti moneen rinnakkaiseen osatehtävään ja toiset eivät:
- Lineaarialgebran operaatioissa voidaan usein mennä vektorin komponenttien tasolle
- Toissa tapauksissa rinnakkainen tehtävä saattaa käsittää gigatavuja dataa
- Ositus vaikuttaa kommunikoinnin määrään (tästä lisää myöhemmin)
- Datariippuvuudet

Kuinka suuriin osiin tehtävä kannattaa osittaa? (jatkuu)

Myöskin laitteisto vaikuttaa valintoihin
Laskentayksiköiden määrällä on suurin vaikutus. Kaikille pitäisi riittää töitä:

Laskentasolmun koko (laiha/thin vai paksu/fat) vaikuttaa tehtävän ositukseen. Osatehtävän tulee mahtua laskentasolmun käytössä olevaan muistiin ja resussit tulisi käyttää mahdollisimman tehokkaasti
Tarvittavan kommunikoinnin määrä vs kommunikointiresurssit

Kuinka suuriin osiin tehtävä kannattaa osittaa? (jatkuu)

Tehtävän osituksen ja laitteiston tulisi vastata toisiaan
- Usein käytettävä algoritmi pitää vaihtaa toiseen kun laitteisto muuttuu liikaa
Ositusta voidaan myöskin tehdä monella eri tasolla
- Laskentaklusteri / Tietokone / CPU vs GPU / GPU:n sisäinen hierarkia

Hienojakaisuus (Granularity)

Laskennan ja kommunikoinnin määrän välinen suhde
Suhdeluku voidaan laskea (tähän palataan myöhemmin)
Tyypillisesti laskentaa sisältävien jaksojen välissä tapahtuu kommunikointia:
- Hienojakoinen (fine): Suhteellisen vähän laskentaa kommunikoinin välissä
- Karkeajakoinen (coarse): Suhteellisen paljon laskentaa kommunikoinnin välissä

Hienojakoisesta rinnakkaisuudesta

Suhteellisen vähän laskentaa kommunikoinin välissä
Matala laskenta / kommunikointi -suhde

Kuorman jakaminen on helpompaa
Kommunikointiin liittyvä parallel overhead on usein suuri \(\implies\) rinnakkaisuus ei välttämättä paranna tehokkuutta merkittävästi
Liian hieno jako \(\implies\) kommunikoinin ja synkronoinnin hinta on liian suuri

Karkeajakoisesta rinnaisuudesta

Suhteellisen paljon laskentaa kommunikoinnin välissä
Korkea laskenta / kommunikointi -suhde

Kuorman jakaminen saattaa olla hankalaa
Vähemmän parallel overhead'ia \(\implies\) Rinnakkaistamisessa on enemmän potentiaalia.