Párhuzamos programozás OpenMP segítségével

Az OpenMP egy nyílt, fordító független szabvány, aminek a segítségével létrehozhatunk olyan C és C++ alkalmazásokat, amelyek párhuzamosan futó részeket alkalmaznak.

Az elÅ‘zÅ‘ fejezetben a szálak létrehozásánál láthattuk, hogy egy szál létrehozása viszonylag egyszerű, de ha ténylegesen hasznos feladatra szeretnénk Å‘ket használni, akkor már komplikáltabb a dolog. De mitÅ‘l is lesz ez komplikált? Tételezzük fel, hogy egy nagy méretű tömböt kellene feldolgoznunk. Egy szálon adódik az ötlet, hogy for ciklussal járjuk be és egyesével végezzük el a munkát.

Ha ezt több szálon szeretnénk megoldani, akkor a nagy tömböt N darab kisebb tömbre kell vágnunk, hogy minden szál külön tömbbÅ‘l dolgozzon (zárolás elkerülése érdekében), illetve N darab szálat kell indítanunk, amik elvégzik a munkát. Ez nem hangzik annyira vészesen, de ha leimplementáljuk, akkor könnyen tapasztaljuk, hogy a szálak felépítése, indítása és az adatok eljuttatása bÅ‘ven több kód lesz, mint a bonyolult algoritmusunk, amit párhuzamosítani szeretnénk.

Itt jön képbe az OpenMP, ami leginkább előfeldolgozó utasításokból és egy pár függvényből áll. Az OpenMP-t az összes komoly (GCC, Clang, MVSC) C és C++ fordító támogatja.

Az alábbi példa a Hello World program átültetése OpenMP környezetre:

#include <stdio.h>
#include <omp.h>

int main()
{
	#pragma omp parallel
	{
        printf("Hello OMP!\r\n");
	}
	return 0;
}

A fenti program a legegyszerűbb OpenMP program. Az omp.h fájl tartalmazza az OpenMP által biztosított függvényeket. A #pragma omp parallel utasítás a blokkban szereplÅ‘ kódot több szálon futóvá fogja átalakítani. Az OpenMP terminológiában ezt egy párhuzamos blokknak nevezzük.

Jelen esetben, mivel nem adtuk meg a szálak számát, ezért ezt a processzor magjainak száma fogja meghatározni. A programot a -fopenmp kapcsolóval kell fordítanunk GCC esetén az OpenMP használatához.

Szálak kezelése

OpenMP esetén a szálak kezelése automatikusan történik, de ez nem jelenti azt, hogy ne tudnánk befolyásolni, illetve információt szerezni róluk. Ezekhez az OpenMP pár hasznos függvényt biztosít.

int omp_get_max_threads(void);

Visszatérési értéke a felső korlátja az egy párhuzamos blokkban futó szálaknak. Fontos, hogy ez mindig a felső korlátot adja vissza és nem veszi figyelembe a korábban megadott szál számot.

void omp_set_num_threads(int num_threads);

Az egy blokkban párhuzamosan futó szálak számát tudjuk vele megadni. Paraméterének egy nullánál nagyobb számnak kell lennie. Negatív érték esetén implementáció függő (nem definiált), hogy mi fog történni.

int omp_get_num_threads(void);

Az omp_set_num_threads párja, ezzel lekérdezhetjük, hogy az aktuális párhuzamos blokkban mennyi szál fut.

double omp_get_wtime(void);
double omp_get_wtick(void);

Ezekkel a függvényekkel lekérdezhetjük a párhuzamos blokk futásának idejét. Az omp_get_wtime másodpercben kifejezve adja vissza az értéket, míg az omp_get_wtick platformtól függÅ‘en az implementáció által használt idÅ‘zító nyers értékét adja meg.

Ciklus párhuzamosítás

A párhuzamosítás akkor jön igazán jól, ha egy ismétlődő feladatot szeretnénk gyorsabbá tenni. Például a bevezetőben említett ciklus párhuzamosítása. Ez OpenMP esetén így néz ki:

#include <stdio.h>
#include <omp.h>

int main()
{
    int szalak = omp_get_max_threads();
    printf("Max szal szam: %d\r\n", szalak);

    omp_set_num_threads(szalak);
	#pragma omp parallel for
    for (int i=0; i<100; i++)
    {
        printf("%d ", i);
    }        
	return 0;
}

A omp_get_max_threads hívással lekérdezzük a maximálisan futtatható szálak számát, amit aztán a omp_set_num_threads segítségével be is állítunk. A #pragma omp parallel for utasítás után egy for ciklus állhat, amit aztán az OpenMP párhuzamosít. Ennek eredménye a kimeneten jól látható, valami hasonló lesz:

Max szal szam: 12
9 10 11 12 13 14 15 16 17 60 61 62 63 64 65 66 67 27 28 29 30 31 32 33 34 35
52 53 54 55 56 57 58 59 68 69 70 71 72 73 74 75 18 19 20 21 22 23 24 25 26 44 45 
46 47 48 49 50 51 92 93 94 95 96 97 98 99 36 37 38 39 40 41 42 43 84 85 86
87 88 89 90 91 76 77 78 79 80 81 82 83 0 1 2 3 4 5 6 7 8

Mint látható, a számok kiírása nem sorrendben történik. A fenti programot futtatva futásonként más eredményt fogunk kapni, mivel előre nem jósolható meg, hogy melyik szál fog hamarább hozzáférni a képernyőhöz.

A ciklusok párhuzamosításánál ügyelni kell arra, hogy a ciklusok bármilyen sorrendben futhassanak, vagyis ne legyenek cipelt függőségeik. Az alábbi példa egy ilyen kódrészletet mutat be:

int tomb[100];
int j = 3;
for (int i=0; i<100; i++) 
{
	j += 2;
	tomb[i] = fuggveny(i, j);
}

A példában cipelt függőség a j változó, mivel minden ciklusfutás hivatkozik rá. A sorrend ugyebár meg nem garantálható, ha párhuzamosan fut a kódrészlet. Ebből adódóan a tomb[i] elemei nem lesznek helyesek a végső számításban. A fenti példa esetén a függőség megszüntethető némi átrendezéssel:

int tomb[100];
for (int i=0; i<100; i++)
{
	int j = 3 + (2 * i);
	tomb[i] = fuggveny(i, j);
}

Ez a kódrészlet már gond nélkül párhuzamosítható. A függőségek megszüntetése azonban nem minden esetben lesz hasonlóan triviális, sőt bizonyos esetekben az algoritmusunk újragondolását, újratervezését is igényelheti, de az is lehet, hogy a művelet nem párhuzamosítható hatékonyan.

További buktató ciklusok párhuzamosításánál a redukció. Redukció akkor keletkezik, amikor a ciklus eredményeit kombináljuk össze egy végeredmény változóba. Az alábbi kódrészlet példa egy redukciós problémára:

double average=0.0, A[10];
for (int i=0; i< 10; i++)
{
	average + = A[i];
}
average = average/10.0;

A probléma áthidalására az OpenMP kínál megoldást, mégpedig a reduction direktívával:

#include <stdio.h>
#include <omp.h>

int main()
{
    int array[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int sum = 0;
    float avg;

    #pragma omp parallel for reduction(+ : sum)
    for (int i = 0; i < 10; i++)
    {
        sum += array[i];
    }

    avg = (float)sum / 10;

    printf("Atlag: %.2f\n", avg);

    return 0;
}

A reduction(+ : sum) záró részben a + a redukciós operátor, amit használunk, a sum pedig a változó neve, amibe redukálunk. Az alábbi táblázat a reduction részben használható operátorokat foglalja össze:

Amennyiben a futás során fontos, hogy a ciklus sorrendben fusson, akkor ki kell egészíteni az ordered jelzÅ‘vel a pragma utasítást: #pragma omp parallel for reduction(+ : sum) ordered Megjegyzés: az ordered alkalmazása lassabb futást fog eredményezni, mint ami lehetséges, mivel ez egy szinkronizációs művelet.

OpenMp és szálkezelés

Szálkezelésre és párhuzamosításra nem csak ciklusokkal van lehetÅ‘ségünk. Külön szálon futó kódot a #pragma omp section utasítással tudunk definiálni. Ezt követÅ‘en egy blokkot kell megadnunk. A blokkban elhelyezett kód külön szálon fog futni. A section utasítás egy #pragma omp parallel sections blokkon belül definiálható. Az alábbi példakód a korábbi pthread példa omp megfelelÅ‘je:

#include <stdio.h>
#include <omp.h>
#include <unistd.h>

void szal1()
{
    for (int i = 0; i < 5; i++)
    {
        printf("Elso szal\r\n");
        sleep(1);
    }
}

void szal2()
{
    for (int i = 0; i < 5; i++)
    {
        printf("Masodik szal\r\n");
        sleep(2);
    }
}

int main()
{
    #pragma omp parallel sections
    {
        #pragma omp section
        {
            szal1();
        }
        #pragma omp section
        {
            szal2();
        }
    }
    return 0;
}

Zárolási módszerek és szinkronizáció

A korábbi programjaink esetén a képernyő egy osztott erőforrás, aminek az elérése implementáció függően vagy szálbiztos, vagy nem. Futtatás közben több, mint valószínű nem fogunk problémával találkozni, mivel a legtöbb mai operációs rendszer esetén a konzol kezelő függvények szál biztosak és a belső működésükben az operációs rendszer elintézi a megfelelő zárolást, hogy egy időben csak egy valaki férjen hozzá.

Saját kódunk esetén azonban erről nekünk kell gondoskodnunk. Az OpenMP biztosít megoldásokat mind a zárolásra mind pedig a különböző szinkronizációs megoldásokra.

Zárolásra a #pragma omp critical utasítást alkalmazhatjuk. Az ezt követÅ‘ utasítást egy idÅ‘ben csak egy szál hajthatja végre.

Szinkronizációra a #pragma omp barrier utasítást alkalmazhatjuk. Ez csak egy blokkon belül jelenhet meg, például:

if (x != 0) {
   #pragma omp barrier
}

Az utasítás bevárja az aktuálisan futó szálakat és csak azután folytatódhat a végrehajtás, ha mindegyik szál végzett a feladatával.

Atomi műveletek

Tételezzük fel, hogy egy párhuzamosított ciklusban egy szálak közötti osztott x változót növelünk az x++ utasítással. Ez nem atomi művelet, mivel a művelet elvégzéséhez ki kell olvasni a változó értékét. Ha ezt futtatjuk, akkor nem helyes eredményeket kapunk, mivel versenyhelyzetek keletkeznek. Ezek áthidalásának egy módszere a korábban bemutatott zárolás, de ez egy relatíve költséges művelet.

Éppen ezért az OpenMP definiál atomi utasításokat, amelyek a #pragma omp atomic definícióval kezdÅ‘dnek.

#pragma omp atomic update

Egy változó értékét atomi módon frissíti. Garantálja, hogy egyszerre csak egy szál tudja frissíteni a megosztott változót, elkerülve az azonos változóba történÅ‘ egyidejű írásból származó hibákat. Egy záradék nélküli #pragma omp atomic utasítás egyenértékű a #pragma omp atomic update utasítással. Példa:

#pragma omp atomic
i++;
#pragma omp atomic
i--;

#pragma omp atomic read

Egy változó értékét atomi módon olvassa be, elkerülve annak a veszélyét, hogy a megosztott változó köztes értét olvassa ki egy szál. Példa:

/*a global egy szálak között megosztott tömb*/
#pragma omp atomic read
int local = global[i];

#pragma omp atomic write

Egy változó értékét atomi módon írja és garantálja, hogy a megosztott változót egy időben csak egy szál módosíthassa. Példa:

/*a global egy szálak között megosztott tömb*/
#pragma omp atomic write
global[i] = local * 2;

#pragma omp atomic capture

Frissíti a változó értékét, miközben atomosan rögzíti a változó eredeti vagy végső értékét. Példa:

#pragma omp atomic capture
global[i] = j++;