OpenMP

Kirjallisuutta

Johdanto

OpenMP-kääntäjälaajennus mahdollistaa sarjamuotoisen ohjelmakoodin rinnakkaistaisen suhteellisen vähällä ylimääräisellä vaivalla. Yksinkertaisimmassa tapauksessa for-silmukka, jonka iteraatiot ovat toisistaan riippumattomia, voidaan rinnakkaistaa seuraavasti:

#pragma omp parallel for
for(int i = 0; i < n; i++) {
    a[i] = i;
}

Kääntäjän täytyy kuitenkin tukea OpenMP:stä ja esimerkiksi gcc-kääntäjän OpenMP-tuki kytketään päälle -fopenmp-lipulla:

g++ ... -fopenmp

Joissain tapauksissa omp.h-otsikkotiedoston sisällyttäminen on tarpeellista:

#include <omp.h>

Pragmat toimivat ilman otsikkotiedostoa, mutta esimerkiksi OpenMP-aliohjelmien prototyypit on määritelty kyseisessä otsikkotiedostossa.

Rinnakkainen koodilohko

Parallel-pragma

Kaikki OpenMP:n rinnakkaisuus tapahtuu rinnakkaisen koodilohkon sisällä:

#pragma omp parallel
{
    // Tämä koodilohko suoritetaan rinnakkain useammalla säikeellä
}

Rinnakkaisen koodilohkon määrittely käynnistää joukon säikeitä / tiimin (team). Johdannossa esiintynyt omp parallel for-pragma on siis lyhennys seuraavasta:

#pragma omp parallel
{
    #pragma omp for
    for(int i = 0; i < n; i++) {
        a[i] = i;
    }
}

Pragma omp for jakaa for-silmukan rinnakkaisiin osatehtäviin

Sections-pragma

Rinnakkaisen koodilohkon sisällä oleva ohjelmakoodi voidaan jakaa myöskin osatehtäviin omp sections ja omp section pragmoilla. Pragmalla omp section määritellyt osatehtävät jaetaan automaattisesti säikeiden kesken siten, että yksi osatehtävä suoritetaan vain kerran:

#pragma omp parallel
{
    // Kaikki säikeet suorittavat seuraavan aliohjelman
    aliohjelma1();
    
    // Aloitetaan osatehtävistä koostuva koodilohko
    #pragma omp sections
    {
        // Kaikki säikeet suorittavat seuraavan aliohjelman
        aliohjelma2();
    
        #pragma omp section
        {
            // Ainoastaan yksi säie suorittaa seuraavat komennot
            int k = 55;
            aliohjelma2();
        }
        
         #pragma omp section
         aliohjelma3(); // Ainoastaan yksi säie suorittaa aliohjelman
    }
}

Edellinen voidaan kirjoittaa lyhemmin muodossa:

#pragma omp parallel sections
{
    // Kaikki säikeet suorittavat seuraavan aliohjelman
    aliohjelma1();
    
    // Kaikki säikeet suorittavat seuraavan aliohjelman
    aliohjelma2();

    #pragma omp section
    {
        // Ainoastaan yksi säie suorittaa seuraavat komennot
        int k = 55;
        aliohjelma2();
    }
    
     #pragma omp section
     aliohjelma3(); // Ainoastaan yksi säie suorittaa aliohjelman
}

Task-pragma

Rinnakkaisia tehtäviä voidaan määritellä myöskin suoraan task-pragmalla:

// aliohjelma1 ja aliohjelma2 muodostavat rinnakkaiset tehtävät ja ne voidaan
// käsittellään rinnakkain

#pragma omp task
aliohjelma1();

#pragma omp task
aliohjelma2();

// Odotetaan rinnakkaisien tehtävien valmistumista
#pragma omp taskwait

Lohkon suorittaminen yhdellä säikeellä

Tarvitaessa osa rinnakkaisesta koodilohkosta voidaan suorittaa vain yhdellä säikeellä:

#pragma omp parallel
{
    aliohjelma1(); // Kaikki säikeet suorittavat aliohjelman
    
    #pragma omp single
    {
        // Vain yksi säie suorittaa aliohjelman. Muut säikeet odottavat lohkon
        // lopussa.
        aliohjelma2(); 
    }
    
    // Kaikki säikeet suorittavat aliohjelman kunhan edellinen single-lohko
    // on ensin käsitelty
    aliohjelma3(); 
    
}

Pragma omp master käyttäytyy hyvin samalla tavalla, mutta lohkon suorittaa joka kerta ns. master-säie (sama säie, joka suorittaa rinnakkaisen koodilohkon ulkopuoliset osat) ja muut säikeet eivät odota lohkon lopussa.

Datan omistajuus

Jaettu ja yksityinen muuttuja

Rinnakkaisen lohkon ulkopuoliset muuttujat ovat oletuksena jaettuja (shared) eli kaikki säikeet käsittelevät samaa muuttujaa. Rinnakkaisen lohkon sisällä määritellyt muuttujat ovat oletuksena yksityisiä (private) eli jokaisella säikeellä on oma versio muuttujasta:

int a = 3; // Jaettu muuttuja
#pragma omp parallel
{
    int b = 5; // Yksityinen muuttuja
}

Race condition

Jaetut muuttujat täytyy joissakin tilanteissa suojata:

int a = 3; // Jaettu muuttuja
#pragma omp parallel
{
    int b = a; // Yksityinen muuttuja
    b += 5;
    a = b; // Rivi (*)
}

Kahdella säikeellä suoritettuna yllä oleva saattaa tehdä esimerksiksi seuraavaa:

Molemmat säikeet käyttäytyvät nätisti, jolloin jaettua muuttujaa a kasvatetaan kahdesti luvulla 5 eli rinnakkaisen lohkon jälkeen a = 13
Säie 1 käy kirjoittamassa muuttujaan a rivillä (*) sillä välin kun säie 2 suorittaa vielä omaa plus-laskuaan. Tällöin muuttujan a arvoksi tulee ensin 8, jonka jälkeen säie 2 tallentaa oman muuttujansa b (= 8) muuttujaan a. Tällöin rinnakkaisen lohkon jälkeen a = 8, joka ei ole välttämättä odotettu tulos. Tapahtui siis ns. race condition

Säie 1	Säie 2	Muuttuja `a`	Säikeen 1 `b`	Säikeen 2 `b`
int b = a;	int b = a;	3	= 3	= 3
b += 5;	-	3	3 -> 8	3
a = b;	b += 5;	3 -> 8	8	3 -> 8
	a = b;	8 -> 8

Lue resurssien suojaaminen -aliluku oppiaksisi, että miten tämä vältetään.

Muuttujan tyypin määritteleminen eksplisiittisesti

Muuttujat voidaan määritellä myös eksplisiittisesti jaetuiksi tai yksityiseksi:

int a = 3;
int b = 5;
#pragma omp parallel private(a) shared(b)
{
    cout << a << endl; // Määrittelemätön
    cout << b << endl; // 5
    
    #pragma omp single
    b = 7; // Yksi säie muuttaa jaetun muuttujan arvoa
    
    cout << b << endl; // 7
}

Yllä rinnakkaisen lohkon sisällä esiintyvän muuttujan a arvo on määrittelemätön, koska jokaisella säikeellä on oma muuttuja a, jota ei alusteta oletuksena. Ongelma voidaan ratkaista firstprivate-avainsanalla, joka kopioi rinnakkaisen lohkon ulkopuolisen muuttujan arvon säikeen saman nimiseen ykstyiseen muuttujaan:

int a = 3;
int b = 5;
#pragma omp parallel firstprivate(a) shared(b)
{
    cout << a << endl; // 3
    cout << b << endl; // 5
    
    #pragma omp single
    {
        b = 7; // Yksi säie muuttaa jaetun muuttujan arvoa
        a = 15; // Yksi säie muuttaa omaa muuttujaansa
    }

    cout << a << endl; // Yksi säie tulostaa luvun 15, loput luvun 3
    cout << b << endl; // 7
}

Reduction-avainsana

reduction-avainsana yhdistää private, shared ja atomic (hyppää atomic-avainsanan käsittelyyn) avainsananat:

TYPE MUUTTUJA = ...
#pragma omp PRAGMA reduction(OP:MUUTTUJA)
{
    // Käytä muuttujaa MUUTTUJA jotenkin...
}

Yllä oleva pseudokoodi tekee effektiivisesti seuraavaa:

TYPE MUUTTUJA = ...
#pragma omp PRAGMA
{
    TYPE _MUUTTUJA = INIT;
    
    // Käytä muuttujaa _MUUTTUJA jotenkin...
    
    #pragma omp atomic
    MUUTTUJA = MUUTTUJA OP _MUUTTUJA;
}

Binäärioperaattori OP ja sitä vastaava alkuarvo INIT voivat olla esimerkiksi jotkin seuraavista:

OP	INIT
+, -, \|, ^, \|\|	0
*, && 1
& ~	0 = 1111...

Esimerkiksi ohjelmakoodi

int a = 0;
#pragma omp parallel for reduction(+:a)
for(int i = 0; i < N; i++)
    a += i;

on effektiivisesti sama kuin

int a = 0;
#pragma omp parallel
{
    int _a = 0;

    #pragma omp for nowait
    for(int i = 0; i < N; i++)
        _a += i;
    
    #pragma omp atomic
    a = a + _a;
}

Flush-pragma

Kääntäjä saattaa optimoida ohjelmakoodia siten, että jaettu muuttuja on tallennettu rekisteriin muistin sijasta. Tämä saattaa vääristää tuloksia joissakin tapauksissa, koska toinen säie näkee pelkästään muistin, mutta ei toiselle säikeelle "kuuluvan" rekisterin sisältä:

int a = 5;
#pragma omp parallel sections shared(a)
{
    #pragma omp section
    {
        a = 66;
        #pragma omp flush(a)
    }
    
     #pragma omp section
    {
        #pragma omp flush(a)
        cout << a << endl;
    }
}

Pragma flush pakottaa kääntäjän kirjoittamaan muuttujan arvon muistiin kirjoituksen jälkeen ja pakottaa kääntäjän lukemaan muuttujan arvon muistista ennen lukuoperaatiota. Tämän kaltainen virittely on vain harvoin tarpeellista, joten kannattaa käyttää ennemmin atomisia operaatioita tai kriittisiä koodilohkoja (katso alla).

Säikeiden hallinta

Säikeiden määrän asettaminen

Säikeiden määrä voidaan valita num_threads(säiemäärä)-avainsanalla pragmam yhteydessä esimerkiksi näin:

// Ajetaan for-silmukka kolmella säikeellä
#pragma omp parallel for num_threads(3)
for(int i = 0; i < n; i++) 
    a[i] = i;

Vaihtoehtoisesti säikeiden määrä voidaan asettaa OMP_NUM_THREADS ympäristömuuttujalla Linuxissa (esim. $ OMP_NUM_THREADS=3 ./ohjelma). Säikeiden määrä voidaan asettaa myöskin ajonaikaisesti aliohjelmakutsulla:

void omp_set_num_threads(int num_threads);

Muita OpenMP-aliohjelmia

Käytössä olevien säikeiden määrä saadaan selville aliohjelmalla:

int omp_get_num_threads(void);

Jokaisella säikeellä on oma indeksinumero, jonka saa käyttöön aliohjelmalla:

int omp_get_thread_num(void);

Suurin mahdollinen säiemäärä silloin kun num_threads-avainsanaa ei ole annettu saadaan selville aliohjelmalla:

int omp_get_max_threads(void);

Resurssien suojaaminen

Tilanteissa, joissa on oleellista, että vain yksi säie voi kerrallaan suorittaa jonkin koodilohkon, täytyy turvautua joko atomisiin operaatioihin tai kriittisen koodilohkon määrittelyyn.

Atomiset operaatiot

Atomic-pragma määrittelee sitä seuraavan komennon atomiseksi eli tapahtumaksi, joka tehdään joko kokonaan kerralla tai ei ollenkaan. Tällöin muut säikeet eivät "ehdi" häiritä komennon suorittamista. Useimmissa tapauksissa atomisesti suoritettava komento täytyy olla toteutettavissa yhdellä konekäskyllä. Muissa tilanteissa täytyy käyttää esimerkiksi kriittistä koodilohkoa. Jos en ole varma niin älä käytä atomisia operaatioita vaan pitäydy kriittisien lohkojen käytössä (katso seuraava aliluku). Katso sivu 127 OpenMP:n manuaalista oppiaksesi lisää.

Esimerkkejä atomic-pragman käytöstä:

// Atominen operaatio
#pragma omp atomic
v += jotain;

// Atominen lukuoperaatio
#pragma omp atomic read
v = x;

// Atominen kirjoitusoperaatio
#pragma omp atomic write
v = jotain;

// Atominen päivitysoperaatio (sama kuin omp atomic)
#pragma omp atomic update
v++;

// Atominen yhdistety päivitys- ja lukuoperaatio
#pragma omp atomic capture
v = x += jotain;

Erityisesti aikaisemmin esiintynyt race condition voidaan korjata seuraavasti:

int a = 3; // Jaettu muuttuja
#pragma omp parallel
{
    #pragma omp atomic
    a += 5; // Vain yksi säie ehtii lukea a:n arvon ja päivittää sitä
}

Kriittiset koodilohkot

Critical-pragmaa voidaan käyttää hieman vapaammin, mutta se ei ole läheskään yhtä nopea kuin atomic-pragma. Pragman jälkeen tuleva komento tai koodilohko suojataan automaattisesti lukon avulla ja muiden säikeiden tulee odottaa lohkoon ensimmäisenä päätyneen säikeen poistumista lohkosta. Esimerkki critical-pragman käytöstä aikaisemman race conditionin korjaamiseksi:

int a = 3; // Jaettu muuttuja
#pragma omp parallel
{
    #pragma omp critical(nimi)
    {
        int b = a; // Yksityinen muuttuja
        b += 5;
        // Mikään muu säie ei voi suorittaa riviä (*) tässä välissä
        a = b; // Rivi (*)
    }
}

Yllä olevassa esimerkissä (nimi) on vapaaehtoinen nimi kriittiselle koodilohkolle. Usealla kriittisellä koodilohkolla voi olla sama nimi ja vain yksi säie voi kerralla suorittaa mitään samalla nimellä nimetyistä kriittisistä lohkoista. Saman nimiset kriittiset lohkot jakavat siis saman lukon.

Synkronointi

Säikeiden suoritus voidaan synkronoida esteen avulla seuraavasti:

#pragma omp parallel
{

    aliohjelma1();
    
    // Este
    #pragma omp barrier
    
    // aliohjelma2-aliohjelmaa aletaan suorittaa vasta sen jälkeen kun edeltävä
    // este on käsitelty kaikkien säikeiden osalta
    aliohjelma2();

}

Jokaisen sections-, for- ja single-lohkon lopussa on myöskin implisiittinen synkronointikomento (eli säikeiden suoritus synkronoidaan automaattisesti). Voit estää tämän nowait-avainsanan avulla:

#pragma omp parallel for nowait
for(int i = 0; i < n; i++) {
    a[i] = i;
}

Sisäkkäiset silmukat

Voit myöskin rinnakkaistaa kaksi sisäkkäistä silmukkaa, joiden iteraatiot ovat toisistaan riippumattomia, collapse-avainsanan avulla:

// Puretaan kaksi silmukan tasoa auki siten, että molemmat silmukat ajetaan
// rinnakkain samanaikaisesti
#pragma omp parallel for collapse(2)
for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
        A[i][j] = i + j;

Esimerkki

Tässä luvussa käydään läpi esimerkkikoodi taulukon summaamisesta rinnakkain OpenMP-rajapinnan avulla. Esimerkkikoodit ovat ladattavista Yousourcesta.

Sarjamuotoinen toteutus

Tarkastellaan seuraavaa C/C++-aliohjelmaa:

double sum(double *x, int n) {
	double tmp = 0.0;
	for(int i = 0; i < n; i++)
		tmp += x[i];
	return tmp;
}

Aliohjelma laskee taulukon x alkiot yhteen for-silmukassa. Testiohjelman tulostus:

Time: 0.0400391 s
Flops: 1.08482 GFlops
Sum value: -2906.08
Real value: -2906.08

Tulosteen mukaan taulukon summaamiseen (n = 43435342) kului aikaa noin 40ms.

Esimerkkikoodi

Ensimmäinen (epäonnistunut) yritys

OpenMP:n omp parallel for -pragma mahdollistaa for-silmukan automaattisen rinnakkaistamisen niissä tapauksissa, joissa silmukan iteraatiot ovat toisistaan riippumattomia. Yritetään siis käyttää sitä:

double sum(double *x, int n) {
    
	//
	// Tämän version on tarkoitus näyttää miten asiat voi tehdä VÄÄRIN!
	// ÄLÄ OTA TÄSTÄ MALLIA!!!
	//

	double tmp = 0.0; // Jaettu muuttuja
	
	#pragma omp parallel for
	for(int i = 0; i < n; i++)
		tmp += x[i];
	
	return tmp;
}

Yllä tmp on jaettu muuttuja, joka näkyy jokaiselle säikeelle eli kaikki säikeet muokkaavat for-silmukassa samaa tmp-muuttujaa. Testiohjelman tulostus:

Time: 0.0093472 s
Flops: 4.64688 GFlops
Sum value: 944.953
Real value: 910.438

Taulukon summaamiseen kuilui siis noin 9ms eli rinnakkainen toteutus on noin neljä kertaa nopeampi. Valitettavasti tulos on väärä! Syynä virheelliseen lopputulokseen on for-silmukan sisällä esiintynyt race condition eli kaikki säikeet yrittävät muuttaa tmp-muuttujan sisältöä samanaikaisesti.

Esimerkkikoodi

Toimiva, mutta hidas ratkaisu kriittisen lohkon avulla

Race condition ratkaistaan tyypillisesti suojaamalla kilpailtu resurssi eli tässä tapauksessa tmp-muuttuja. Yritetään tehdä tämä omp critical -pragman avulla:

double sum(double *x, int n) {
    
	//
	// Tämän version on tarkoitus näyttää miten asiat voi tehdä VÄÄRIN!
	// ÄLÄ OTA TÄSTÄ MALLIA!!!
	//

	double tmp = 0.0; // Jaettu muuttuja
	
	#pragma omp parallel for
	for(int i = 0; i < n; i++)
		#pragma omp critical
		tmp += x[i];
	
	return tmp;
}

Yllä käytetty omp critical -pragman määrittelee sitä seuraavan koodilohkon kriittiseksi koodilohkoksi. Käytännössä tämä tarkoittaa sitä, että lohko suojataan lukon tai semaforin avulla, jolloin vain yksi säie voi kerrallaan suorittaa suojatun koodilohkon.

Testiohjelman tulostus:

Time: 7.64137 s
Flops: 0.00568424 GFlops
Sum value: 3746.95
Real value: 3746.95

Ohjelma toimii siis oikein, mutta on noin 190 kertaa hitaampi kuin rinnakkaistamaton versio! Hitaus johtuu siitä, että kriittinen lohko on sijoitettu for-silmukan sisälle, joten siihen liittyvä lukko avataan ja suljetaan n kertaa ja muut säikeet joutuvat odottamaan. Käytännössä ohjelmakoodissa ei siis ole yhtään rinnakkaisuutta!

Esimerkkikoodi

Hieman nopeampi versio

Yksinkertaiset koodilohkot voidaan suojata atomisen operaation avulla. Rivi tmp += x[i]; on yksinkertainen yhden muuttujan päivitysoperaatio, joten se voidaan suojata omp atomic -pragmalla:

double sum(double *x, int n) {
    
	//
	// Tämän version on tarkoitus näyttää miten asiat voi tehdä VÄÄRIN!
	// ÄLÄ OTA TÄSTÄ MALLIA!!!
	//

	double tmp = 0.0;
	
	#pragma omp parallel for
	for(int i = 0; i < n; i++)
		#pragma omp atomic
		tmp += x[i];
	
	return tmp;
}

Testiohjelman tulostus:

Time: 3.90907 s                                                                                                                            
Flops: 0.0111114 GFlops
Sum value: 7738.2
Real value: 7738.2

Ohjelmakoodi tuottaa oikean lopputuloksen, mutta on edelleen noin 100 kertaa hitaampi kuin rinnakkaistamaton versio! Syy tähän on jälleen se, että atominen operaatio on for-silmukan sisällä.

Esimerkkikoodi

Nopea versio

Kahden edellisen esimerkin perusteella haluamme siis siirtää atomisen operaation pois for-silmukan sisältä. Tämä ei onnistu käyttäen omp parallel for -pragmaa vaan meidän täytyy palata takaisin omp parallel -pragman (linkki) käyttöön:

double sum(double *x, int n) {

    double tmp = 0.0; // Jaettu muuttuja
	
    // omp parallel -pragman jälkeinen koodilohko suoritetaan useammalla säikeellä
    #pragma omp parallel
    {
        // Jokaisella säikeellä on oma muuttuja p, johon ne tallentavat oman
        // osasummansa tuloksen
        double p = 0.0;
		
        // omp for -pragma jakaa for-silmukan automaattisesti osatehtäviin.
        // Jokaisella säikeellä on nyt oma summausmuuttuja p, joten säikeet
        // eivät sotke toistensa tuloksia! Saimme atomisen operaation pois
        // for-silmukasta!!!
        #pragma omp for nowait
        for(int i = 0; i < n; i++)
            p += x[i];
		
        // Lopuksi jokainen säie lisää oman välituloksensa tmp-muuttujaan
        // Nyt omp atomic -pragma suoritetaan vain kerran per säie!!!
        #pragma omp atomic
        tmp += p;
    }
	
    return tmp;
}

Yllä muuttuja tmp on määritelty omp parallel -lohkon ulkopuolella, joten se on jaettu muuttuja. Muuttuja p on puolestaan määritelty lohkon sisällä, joten se on yksityinen muuttuja. Jokaisella säikeellä on siis oma muuttuja p, jonka arvoa ne voivan muuttaa ilman race conditionia!

Testiohjelman tulostus:

Time: 0.00854421 s
Flops: 5.0836 GFlops
Sum value: 3836.15
Real value: 3836.15

Ohjelma tuottaa oikean tuloksen ja on lähes 5 kertaa nopeampi kuin rinnakkaistamaton versio!

Esimerkkikoodi

Yhden rivin versio

Ohjelmakoodi voidaan rinnakkaistaa yhdellä ylimääräisellä koodirivillä:

double sum(double *x, int n) {

	double tmp = 0.0;
	
	#pragma omp parallel for reduction(+:tmp)
	for(int i = 0; i < n; i++)
		tmp += x[i];
	
	return tmp;
}

Yllä oleva ohjelmakoodi perustuu reduction-avainsanan käyttöön. Reduction-avainsanan käyttö vaatii edellä käsiteltyjen käsitteiden hyvää hallintaa.

Testiohjelman tulostus:

Time: 0.00862789 s
Flops: 5.03429 GFlops
Sum value: 2112.93
Real value: 2112.93

Reduction-avainsana on siis yhtä nopea kuin edellisen aliluvun ohjelmakoodi.

Esimerkkikoodi