OpenMP (na podstawie OpenMP C/C++ API)

Sławomir Petrykowski



    OpenMP to zbiór dyrektyw kompilacji, funkcji bibliotecznych i zmiennych środowiskowych mających pomóc w tworzeniu programów równoległych w systemach z pamięcią dzieloną. Atutem standardu jest fakt, iż większość producentów takiego sprzętu wspiera OpenMP.

    OpenMP rozszerza sekwencyjny model programowania o Single-Program Multiple Data (SPMD), pracę dzieloną (work-sharing) i synchronizację, oraz wspomaga operowanie na wspólnych i prywatnych danych. Równoległość programu musimy wskazać jawnie i do nas należy przewidywanie wszelkich zależności, konfliktów i uwarunkowań.

    Program zaczyna działanie jako pojedynczy wątek, wątek główny (master thread), aż do momentu napotkania konstrukcji równoległej. W tym momencie utworzona zostaje grupa wątków, przy czym wątek główny staje się nadrzędny w stosunku do pozostałych. Dalej każdy wątek wykonuje program znajdujący się w dynamicznym rozszerzeniu konstrukcji równoległej (model SPMD) , poza obszarami w których program jest wykonywany w modelu pracy dzielonej. Po zakończeniu pracy w konstrukcji równoległej wątki zostają zsynchronizowane niejawną barierą i tylko wątek główny kontynuuje pracę. W programie można użyć dowolnej ilości konstrukcji równoległych. Możemy również używać dyrektyw w funkcjach które są wywoływane z konstrukcji równoległych.
 
 

Definicje

Bariera - punkt synchronizacji, który musi zostać osiągnięty przez wszystkie wątki w grupie. Każdy z wątków oczekuje aż wszystkie wątki osiągną ten punkt.

Konstrukcja - instrukcja złożona z dyrektywy OpenMP i bezpośrednio po niej następującego bloku strukturalnego. Niektóre dyrektywy nie są częścią konstrukcji.

Rozszerzenie dynamiczne - wszystkie instrukcje w rozszerzeniu leksykalnym oraz każda instrukcja wewnątrz funkcji, której wykonanie jest konsekwencją wykonania instrukcji z rozszerzenia leksykalnego.

Rozszerzenie leksykalne - instrukcje znajdujące się wewnątrz bloku strukturalnego.

Wątek główny - wątek tworzący grupę na wejściu w obszar równoległy.

Obszar równoległy - instrukcje wykonywane przez wiele wątków równolegle.

Prywatny - w obszarze równoległym dostępny tylko dla jednego wątku z grupy.

Obszar sekwencyjny - instrukcje wykonywane tylko przez wątek główny poza obszarem równoległym.

Usekwencyjnienie- wykonanie konstrukcji równoległej przez grupę wątków składającą się z jednego wątku. Porządek wykonywania instrukcji wewnątrz bloku strukturalnego jest wtedy taki, jak w sytuacji, gdy blok ten nie byłby częścią konstrukcji równoległej.

Wspólny - w obszarze równoległym dostępny dla wszystkich wątków z grupy.

Blok strukturalny - instrukcja posiadająca jedno wejście i jedno wyjście. Instrukcja skoku, instrukcja etykietowana, oraz instrukcja deklaracji nie tworzą bloku strukturalnego.

Zmienna- identyfikator nazywający obiekt.
 
 

Dyrektywy

    Dyrektywy OpenMP bazują na dyrektywie #pragma zdefiniowanej w standardach C i C++. Ogólny format dyrektyw jest następujący:

    #pragma omp dyrektywa [klauzula [klauzula ] ... ] NL

    NL oznacza nową linię. Zasadniczo porządek klauzul nie ma znaczenia i mogą one być zagnieżdżane o ile nie posiadają dodatkowych restrykcji. Lista będąca klauzulą może zawierać wyłącznie nazwy zmiennych. Tylko jedna nazwa dyrektywy może występować w pojedynczej dyrektywie. Dyrektywa odnosi się do występującego bezpośrednio pod nią bloku strukturalnego.
 
 

Kompilacja warunkowa.

    Kompilatory OpenMP rozpoznają makrodefinicję _OPENMP, co pozwala na przeprowadzenie kompilacji warunkowej postaci:

    #ifdef _OPENMP
    ...
    #endif

    Makrodefinicja _OPENMP nie może być poddawana operacjom preprocesora #define i #undef.
 
 

Konstrukcja parallel:
    Dyrektywa parallel definiuje obszar równoległy, wykonywany przez grupę wątków. Jest to podstawowa konstrukcja rozpoczynająca pracę równoległą.

    #pragma omp parallel [klauzula [klauzula] ... ] NL
        blok strukturalny

    Klauzulą może być:
        if (wyrażenie skalarne)
        private (lista)
        firstprivate (lista)
        default (shared | none)
        shared (lista)
        copyin (lista)
        reduction (operator: lista)

    Kiedy wątek osiąga konstrukcję parallel zostaje stworzona grupa wątków, pod warunkiem, że w dyrektywie nie występuje klauzula if, lub wyrażenie skalarne w if sprowadza się do niezerowej wartości. Wówczas wątek tworzący grupę staje się wątkiem głównym grupy i wszystkie wątki w grupie, włącznie z głównym, wykonują obszar programu współbieżnie. Ilość wątków w grupie jest kontrolowana przez zmienne środowiskowe lub wywołania funkcji bibliotecznych. Gdy wartość wyrażenie skalarne w if jest zerowa, to obszar jest wykonywany sekwencyjnie. Na końcu obszaru równoległego znajduje się domyślna bariera. Po opuszczeniu obszaru równoległego pracę kontynuuje jedynie wątek główny grupy. Jeśli któryś z wątków wykonujących obszar równoległy napotka następną konstrukcję parallel, wówczas tworzy nową grupę i staje się jej wątkiem głównym. Domyślnie zagnieżdżone konstrukcje równoległe są usekwencyjniane, co w rezultacie oznacza, że grupa składa się z jednego wątku. Zachowanie to może zostać zmienione za pomocą funkcji omp_set_nested, lub zmiennej środowiskowej OMP_NESTED.
 
 

Praca dzielona.

    Konstrukcja pracy dzielonej rozdziela wykonywanie stowarzyszonej z nią instrukcji pomiędzy członków istniejącej grupy (nie tworząc nowych wątków). Nie ma bariery na wejściu w ten tryb pracy. Sekwencja wystąpień dyrektyw konstrukcji pracy dzielonej i barier powinna być taka sama dla wszystkich wątków w grupie.

Konstrukcja for:
    Identyfikuje pętlę for która zostanie wykonana równolegle. Iteracje pętli zostaną rozdzielone pomiędzy istniejące wątki. Skłania wygląda następująco:

    #pragma omp for [klauzula [klauzula] ... ] NL
        pętla for

    Klauzulą może być:
        private (lista)
        firtsprivate (lista)
        lastprivate (lista)
        reduction (operator: lista)
        ordered
        shedule (rodzaj [, porcja])
        nowait

    Pętla for użyta w takiej konstrukcji musi mieć kształt kanoniczny:
       for (init-expr; var logical-op b; incr-expr)
    ,gdzie
        init-expr - jedno z:
            var = lb
            integer-type var = lb
        incr-expr - jedno z:
            ++var
            var++
            --var
            var--
            var += incr
            var -= incr
            var = var + incr
            var = incr + var
            var = var - incr
        var - jest to zmienna całkowita ze znakiem, która nie może być modyfikowana wewnątrz pętli
        logical-op - jedna z poniższych:
            <
            <=
            >
            >=
        lb, b, incr - wyrażenie całkowite nie zmieniające się w pętli.

    Klauzula shedule określa sposób w jaki iteracje zostaną rozdzielone na wątki z grupy. Poprawność programu nie powinna zależeć od tego który z wątków wykona daną iterację. Wartość porcja, o ile wystąpiła w klauzuli, powinna być niezależnym od wykonywanej pętli wyrażeniem całkowitym większym od zera. rodzaj powinien być jednym z poniższych:

        static
        dynamic
        guided
        runtime
    Jeżeli nie została użyta klauzula nowait, to na końcu konstrukcji for znajduje się domyślna bariera.

Konstrukcja sections:
    Dyrektywa sections identyfikuje zbiór sekcji które zostaną rozdzielone do wykonania wątkom w grupie. Każda sekcja zostanie wykonana dokładnie raz przez jeden wątek z grupy. Składnia jest następująca:

    #pragma omp sections [klauzula [klauzula] ...] NL
    {
    [#pragma omp section NL]
        blok strukturalny
    [#pragma omp section NL]
        blok strukturalny
    ...
    }

    Klauzulą może być jedna z poniższych:
        private (lista)
        firstprivate (lista)
        lastprivate (lista)
        reduction (operator: lista)
        nowait

    Dyrektywa nowait ma takie same znaczenie jak w przypadku konstrukcji for.

Konstrukcja single:
    Dyrektywa single oznacza, że stowarzyszony z nią blok strukturalny zostanie wykonany wyłącznie przez jeden wątek z grupy (nie koniecznie musi to być wątek główny). Składnia:

    #pragma omp single [klauzula [klauzula ] ... ] NL
        blok strukturalny

    Klauzulą może być:
        private (lista)
        firstprivate (lista)
        nowait

    Klauzula nowait jak w poprzednich przypadkach.
 
 

Konstrukcje łączone.

    Konstrukcje łączone są skrótami konstrukcji parallel i konstrukcji pracy dzielonej zawierającymi jedynie obszar pracy dzielonej.

Konstrukcja parallel for:
    Dyrektywa parallel for jest skrótem dla konstrukcji parallel zawierającej pojedynczą dyrektywę for. Jest równoważna dyrektywie parallel z bezpośrednio po niej następującą dyrektywą for. Składnia jest następująca:

    #pragma omp parallel for [klauzula [klauzula ]... ] NL
        pętla for

    Klauzule są takie same jak dla parallel i dla for, za wyjątkiem klauzuli nowait.

Konstrukcja parallel sections:
    Dyrektywa parallel sections jest skrótem dla konstrukcji parallel zawierającej pojedynczą dyrektywę sections. Jest równoważna dyrektywie parallel z bezpośrednio po niej następującą dyrektywą sections. Składnia:

    #pragma omp parallel sections [klauzula [klauzula ]... ] NL
    {
    [#pragma omp section NL]
        blok strukturalny
    [#pragma omp section NL]
        blok strukturalny
    ...
    }

    Klauzule są takie same jak dla parallel i dla sections, za wyjątkiem klauzuli nowait.
 
 

Konstrukcja master i konstrukcje synchronizacji.

Konstrukcja master:
    Dyrektywa master oznacza, że stowarzyszony z nią blok strukturalny zostanie wykonany przez wątek główny grupy. Składnia:

    #pragma omp master NL
        blok strukturalny

    Pozostałe wątki nie wykonują stowarzyszonego bloku. Nie ma domyślnej bariery ani na początku, ani na końcu bloku.

Konstrukcja critical:
    Dyrektywa critical oznacza, że stowarzyszony z nią blok może być wykonywany tylko przez jeden wątek na raz. Składnia:

    #pragma omp critical [ (nazwa) ] NL
        blok strukturalny

    Opcjonalny parametr nazwa jest używany do identyfikacji obszaru krytycznego.
    Wątek jest wstrzymywany na początku obszaru krytycznego aż do momentu, gdy żaden inny wątek nie wykonuje pracy w obszarze o takiej samej nazwie nazwa (dotyczy to całego programu ) . Wszystkie nienazwane dyrektywy critical są traktowane jako jeden obszar krytyczny.

Dyrektywa barrier:
    Dyrektywa barrier synchronizuje wszystkie wątki z grupy w punkcie wystąpienia dyrektywy. Składnia:

    #pragma omp barrier NL

    Wątki kontynuują pracę po osiągnięciu bariery przez wszystkie wątki z grupy.

Konstrukcja atomic:
    Dyrektywa atomic zapewnia, że określona lokacja w pamięci jest aktualizowana atomowo (niepodzielnie), bez narażania na możliwość pisania do niej z wielu wątków równocześnie. Składnia:

    #pragma omp atomic NL
        wyrażenie

    ,gdzie wyrażenie przybiera jedną z form:
        x binop = expr
        x++
        ++x
        x--
        --x
    , a
        x jest l-wartością typu skalarnego,
        expr jest wyrażeniem typu skalarnego i nie odwołuje się do obiektu oznaczonego przez x,
        binop jest jedną z operacji (nie przesłoniętych) : +,*,-,/,&,^,|,<<,>>.

    Czytanie i pisanie atomowo odbywa się jedynie na obiekcie oznaczonym przez x. Obliczanie wartości expr nie jest atomowe.

Dyrektywa flush:
    Dyrektywa flush oznacza, że wątki w grupie muszą mieć uzgodnione wartości określonych obiektów, czyli poprzednie obliczenia dotyczące obiektów zostały zakończone, a nowe jeszcze się nie zaczęły. Na przykład wszystkie operacje związane z buforowaniem muszą zostać zakończone. Składnia:

    #pragma omp flush [(lista)] NL

    lista jest parametrem opcjonalnym i jeśli nie zostanie podana wszystkie obiekty wspólne zostaną zsynchronizowane. Jeśli w lista występuje wskaźnik, to obiekt na który wskazuje nie podlega operacji flush.

Konstrukcja oredered:

    Blok strukturalny znajdujący się pod dyrektywą ordered jest wykonywany w porządku takim, jak w pętli sekwencyjnej. Składnia:
    #pragma omp ordered NL

        blok strukturalny

    Dyrektywa ordered musi znajdować się w dynamicznym rozszerzeniu konstrukcji for lub parallel for, posiadającej klauzulę ordered.
 
 

Środowisko danych.

Dyrektywa threadprivate:
    Dyrektywa threadprivate oznacza, że wszystkie zmienne podane jako parametry w lista będą prywatne dla wątków w całej przestrzeni programu. Składnia:

    #pragma omp threadprivate (lista) NL

    Każda z kopii zmiennej jest inicjowana raz, w nieokreślonym punkcie programu, przed pierwszym odwołaniem do niej.
 
 

Klauzule zakresu widoczności danych.

    Wiele dyrektyw akceptuje klauzule, które pozwalają na kontrolowanie zakresu widoczności zmiennych podczas wykonywania obszaru związanego z tymi dyrektywami. Klauzule zakresu widoczności odnoszą się jedynie do leksykalnego rozszerzenia konstrukcji danej dyrektywy.

    Domyślnie każda zmienna, widoczna podczas pracy równoległej, która nie została opisana klauzulą zakresu lub dyrektywą threadprivate jest traktowana jako wspólna dla wszystkich wątków. Zmienne statyczne zadeklarowane wewnątrz rozszerzenia dynamicznego są traktowane jako wspólne. Zaalokowana pamięć jest wspólna (chociaż wskaźnik do niej może być prywatny). Zmienne o automatycznie określonym okresowym czasie istnienia zadeklarowane wewnątrz rozszerzenia dynamicznego są prywatne.
private:
    Zmienne zadeklarowane w klauzuli private są prywatne dla każdego z wątków w grupie. Składnia:
    private (lista)

    Na czas wykonywania bloku strukturalnego dla każdego z wątków w grupie tworzony jest nowy obiekt o właściwościach takich jak typ zmiennej znajdującej się w liście lista. Jego wartość jest nieokreślona na wejściu do bloku, nie może być modyfikowana wewnątrz rozszerzenia dynamicznego, i ma nieokreśloną wartość po wyjściu z bloku. Dla każdego z wątków zmienne z listy lista, w rozszerzeniu leksykalnym , wskazują na taki właśnie obiekt.

firstprivate:

    Klauzula firstprivate rozszerza klauzulę private. Składnia:
    firstprivate (lista)

    Działanie jest takie jak dla klauzuli private, ale obiekt tworzony wewnątrz bloku strukturalnego jest inicjowany wartością obiektu oryginalnego.

lastprivate:

    Klauzula lastprivate rozszerza klauzulę private. Składnia:
    lastprivate (lista)

    Działanie jest takie jak dla klauzuli private. Dodatkowo, jeśli klauzula znajduje się w dyrektywie określającej konstrukcję pracy dzielonej, to oryginalnemu obiektowi przypisywana zostanie wartość jak w ostatniej (sekwencyjnie) iteracji pętli, albo z ostatniej sekcji konstrukcji sections.

shared:
    Zmienne wypunktowane w klauzuli shared są traktowane jako wspólne dla wszystkich wątków w grupie. Każdy z wątków ma dostęp do tego samego miejsca przechowywania zmiennej. Składnia:

    shared (lista).

default:
    Klauzula default pozwala określić zakresy zmiennych. Składnia:

    default (shared | none)

    default(shared) oznacza, że każda z widocznych zmiennych będzie traktowana jako wspólna, poza zadeklarowanymi przy pomocy threadprivate i stałymi.
    default(none) wymaga, aby każda z aktualnie widocznych w rozszerzeniu leksykalnym zmiennych była jawnie zadeklarowana w którejś z klauzul zakresu widoczności danych.

reduction:
    Klauzula przeprowadza redukcję na wyrażeniach skalarnych wymienionych w liście lista, z operatorem op. Składnia:

    reduction (op: lista)

    reduction jest używana dla instrukcji przyjmujących jedną z następujących form:
        x = x op expr
        x <binop>= expr
        x = expr op x (oprócz odejmowania)
        x++
        ++x
        x--
        --x

    , gdzie


        x jedna ze zmiennych podlegających operacji redukcji wymieniona w liście lista
        lista lista zmiennych podlegających operacji redukcji

        expr wyrażenie typu skalarnego nie odnoszące się do x


        op jeden z nieprzesłoniętych operatorów: +, *, -, &, ^, |, &&, ||

        binop jeden z nieprzesłoniętych operatorów: +, *, -, &, ^, |.
    Instrukjca operacji redukcji może pojawiać się w rozszerzeniu dynamicznym. Zmienne zawarte w klauzuli muszą być wspólna dla wątków w danej konstrukcji.
    Na początku wykonywania obszaru dla każdego wątku tworzone są prywatne kopie zmiennych z listy, tak jak podczas działania klauzuli private. Następnie są one inicjowane wartościami zależnymi od używanego operatora (wartości te są podane w odpowiedniej tabelce w specyfikacji OpenMP). Na końcu wykonywanego obszaru oryginalne zmienne są aktualizowane wartością stanowiącą połączenie wartości przed wykonaniem konstrukcji z końcowym rezultatem operacji redukcji wykonanej na prywatnych kopiach. W przypadku użycia klauzuli nowait wartość zmiennej dzielonej jest niezdeterminowana, aż do wystąpienia punktu synchronizacji.

copyin:

    Każda kopia zmiennej zadeklarowanej jako threadprivate i wymienionej w klauzuli copyin jest przy wejściu do bloku równoległego inicjowana wartością zmiennej z wątku głównego. Skłądnia klauzuli.
    copyin (lista)
 


Runtime Library Functions

    Nagłówek <omp.h> deklaruje dwa typy, funkcje użyteczne dla kontrolowania środowiska wykonywania równoległego, oraz funkcje blokujące, służące synchronizacji dostępu do danych.

    Typ omp_lock_t reprezentuje obiekty noszące informacje: wolny - zajęty (blokada prosta).


    Typ omp_nest_lock_t oprócz funkcojanlności typu omp_lock_t posiada możliwość identyfikacji aktualnego właściciela blokady, oraz licznik zagnieżdżenia (blokada zagnieżdżona).
 
 

Funkcje środowiska wykonywania równoległego:

    omp_set_num_threads - Ustawia ilość wątków używanych podczas wykonywania obszaru równoległego. Działanie jest zależne od tego, czy umożliwione jest dynamiczne przydzielanie wątków. Jeśli nie, to ustawiona wartość oznacza ilość wątków tworzoną przy wejściu w każdy obszar równoległy (także zagnieżdżony). W przeciwnym wypadku wartość oznacza maksymalną ilość wątków która może zostać użyta.

    omp_get_num_threads - Funkcja zwraca aktualną ilość wątków w grupie wykonujących obszar równoległy z którego wywołano funkcję.
    omp_get_max_threads - Zwraca maksymalną wartość, jaka może zostać zwrócona po wywołaniu funkcji omp_get_num_threads.
    omp_get_thread_num - Zwraca numer wątku w jego aktualnej grupie. Wątek główny ma numer 0.
    omp_get_num_procs - Zwraca maksymalną liczbę procesorów jaka może być przeznaczona na na wykonywanie programu.
    omp_in_parallel - Zwraca wartość niezerową jeśli została wywołana z dynamicznego rozszerzenia obszaru równoległego wykonywanego równolegle. W przeciwnym wypadku zwraca 0.
    omp_set_dynamic - Umożliwia lub zabrania dynamicznego przydzielania wątków do wykonywania obszarów równoległych. Jeżeli zezwolimy na dynamiczne przydzielanie, to ilość wątków używanych do wykonywania obszarów równoległych może zmieniać się automatycznie, tak, aby jak najlepiej wykorzystane zostały zasoby systemowe. W szczególności ilość wątków podana przez użytkownika jest ilością maksymalną. Ustawienie domyślne jest zależne od implementacji.


    omp_get_dynamic - Zwraca wartość niezerową, gdy ustawione jest dynamiczne przydzielanie wątków, w przeciwnym przypadku 0.

    omp_set_nested - Włącza lub wyłącza zagnieżdżanie równoległości. Jeżeli nie ma zgody na zagnieżdżanie, to zagnieżdżające się obszary równoległe są usekwencyjniane, w przeciwnym wypadku zagnieżdżające się obszary równoległe mogą tworzyć dodatkowe grupy wątków.


    omp_get_nested - Zwraca wartość niezerową jeśli zagnieżdżanie jest włączone, a 0 w przeciwnym wypadku.
 
 

Funkcje blokujące

    omp_init_lock, omp_init_nest_lock - Inicjuje blokadę podaną jako parametr funkcji. Nie może ona być zablokowana. Po wykonaniu funkcji blokada nie posiada właściciela. Dla blokady zagnieżdżonej licznik zgnieżdżenia jest ustawiany na 0.
    omp_destroy_lock, omp_destroy_nest_lock - Upewnia nas, że podana jako argument blokada będzie zdeinicjowana. Blokada podana w parametrze wywołania nie może być zablokowana, musi być wcześniej zainicjowana.
    omp_set_lock, omp_set_nest_lock - Obydwie funkcje wstrzymują wykonywanie wątku dopóki blokada podana jako parametr wywołania nie zostanie zwolniona, a następnie zajmują tę blokadę. Blokada prosta jest dostępna o ile nie jest zablokowana. Blokada zagnieżdżana jest dostępna jeśli nie jest zablokowana, lub zablokowana jest przez ten sam wątek, który wywołał funkcję. Prawo własności blokady prostej jest nadawane wątkowi, który wywołał funkcję. Prawo własności blokady zagnieżdżonej jest nadawane lub utrzymywane, przy czym zwiększany jest licznik zagnieżdżenia.

    omp_unset_lock, omp_unset_nest_lock - Funkcja umożliwia właścicielowi zniesienie blokady. W przypadku blokady zagnieżdżonej każde wywołanie odnoszące się do niej zmniejsza jej licznik zagnieżdżenia, a odblokowanie następuje przy wartości 0.
    omp_test_lock, omp_test_nest_lock - Funkcja przystępuje do próby ustawienia blokady, lecz nie przerywa wykonywania wątku. Dla blokady prostej zwraca niezerową wartość, jeśli próba ustawienia blokady powiodła się, zero w przeciwnym wypadku. Dla blokady zagnieżdżonej zwracana jest nowa wartość licznika zagnieżdżenia w przypadku sukcesu, albo 0 w przypadku porażki.

 
 
 

Zmienne środowiskowe

OMP_SHEDULE - ustawia rodzaj i ewentualnie porcję dla parametru runtime klauzuli shedule (patrz konstrukcja for)
OMP_NUM_THREADS - ustawia ilość wątków używaną podczas wykonywania programu.
OMP_DYNAMIC - ustawia lub blokuje dynamiczne przydzielanie wątków.
OMP_NESTED - ustawia lub blokuje zagnieżdżanie równoległości.
 

Literatura

OpenMP C/C++ API, v1.0, 1998, http://www.openmp.org