OpenMP

OpenMP (ang. Open Multi-Processing) – wieloplatformowy interfejs programowania aplikacji (API) umożliwiający tworzenie programów komputerowych dla systemów wieloprocesorowych z pamięcią dzieloną. Może być wykorzystywany w językach programowania C, C++ i Fortran na wielu architekturach, m.in. Unix i Microsoft Windows. Składa się ze zbioru dyrektyw kompilatora, bibliotek oraz zmiennych środowiskowych mających wpływ na sposób wykonywania się programu.

Dzięki temu, że standard OpenMP został uzgodniony przez głównych producentów sprzętu i oprogramowania komputerowego, charakteryzuje się on przenośnością, skalowalnością, elastycznością i prostotą użycia. Dlatego może być stosowany do tworzenia aplikacji równoległych dla różnych platform, od komputerów klasy PC po superkomputery.

OpenMP można stosować do tworzenia aplikacji równoległych działających na wieloprocesorowych węzłach klastrów komputerowych. W tym przypadku stosuje się rozwiązanie hybrydowe, w którym programy są uruchamiane na klastrach komputerowych pod kontrolą alternatywnego interfejsu MPI, natomiast do zrównoleglenia pracy węzłów klastrów wykorzystuje się OpenMP. Alternatywny sposób polegał na zastosowaniu specjalnych rozszerzeń OpenMP dla systemów pozbawionych pamięci współdzielonej (np. Cluster OpenMP[1] Intela).

Wprowadzenie

Zasada implementacji współbieżności w OpenMP: główny wątek co pewien czas rozgałęzia się na pewną liczbę wątków potomnych współbieżnie wykonujących określone fragmenty kodu. Za każdym razem liczba wątków potomnych może być inna, a obciążenia wątków przy realizacji konkretnych zadań mogą być zróżnicowane.

Celem OpenMP jest implementacja wielowątkowości, czyli metody zrównoleglania programów komputerowych, w której główny „wątek programu” (czyli ciąg następujących po sobie instrukcji) „rozgałęzia” się na kilka „wątków potomnych”, które wspólnie wykonują określone zadanie. Wątki pracują współbieżnie i mogą zostać przydzielone przez środowisko uruchomieniowe różnym procesorom. Fragment kodu, który ma być wykonywany równolegle, jest w kodzie źródłowym oznaczany odpowiednią dyrektywą preprocesora. Tuż przed wykonaniem tak zaznaczonego kodu główny wątek rozgałęzia się na określoną liczbę nowych wątków. Każdy wątek posiada unikatowy identyfikator (ID), którego wartość można odczytać funkcją omp_get_thread_num() (w C/C++) lub OMP_GET_THREAD_NUM() (w Fortranie). Identyfikator wątku jest liczbą całkowitą, przy czym identyfikator wątku głównego równy jest 0. Po zakończeniu przetwarzania zrównoleglonego kodu wątki „włączają się” z powrotem do wątku głównego, który samotnie kontynuuje działanie programu i w innym miejscu może ponownie rozdzielić się na nowe wątki.

Domyślnie wszystkie wątki przetwarzają zrównolegloną część kodu niezależnie od siebie. Do podziału zadania pomiędzy wątki służą specjalne „konstrukcje podziału zadania”. Posługując się nimi można w OpenMP osiągnąć zarówno zrównoleglenie na poziomie zadań (ang. task parallelism), jak i na poziomie danych (ang. data parallelism).

Za przydział wątków do poszczególnych procesorów odpowiada środowisko uruchomieniowe, które stosuje algorytm uwzględniający m.in. aktualne obciążenie poszczególnych procesorów oraz całej maszyny. Liczba nowych wątków może być określona tuż przed uruchomieniem programu za pośrednictwem zmiennych środowiskowych lub w kodzie źródłowym za pomocą specjalnych funkcji. Deklaracje funkcji biblioteki OpenMP dla języków C i C++ znajdują się w pliku nagłówkowym "omp.h").

Historia

Specyfikacje kolejnych wersji standardu OpenMP publikowane są przez OpenMP Architecture Review Board (ARB). Pierwsza z nich, tzw. OpenMP for Fortran v. 1.0, została opublikowana w październiku 1997 roku i dotyczyła wyłącznie języka Fortran. Miesiąc później opublikowano wersję Fortran 1.1. Pierwszy standard dla języków C i C++ (OpenMP for C/C++ 1.0) został opublikowana w październiku następnego roku. W 2000 roku opublikowano wersję 2.0 dla języka Fortran, a w 2002 wersję 2.0 dla języków C/C++. Pierwszą wspólną specyfikacją dla języków C, C++ i Fortran jest opublikowana w 2005 wersja 2.5.

Najnowszą wersją standardu jest OpenMP 3.0 z maja 2008 roku. Do nowych cech tego standardu należy konstrukcja task. Szczegółowy wykaz nowych cech standardu 3.0 znajduje się w Dodatku F specyfikacji OpenMP 3.0.

Kompilacja i uruchomienie programu OpenMP

Przykład kompilacji dla kompilatora Intel C++:

$ icc -openmp program.cpp -o program

Przykład kompilacji dla kompilatora GCC:

$ g++ -fopenmp program.cpp -o program

Uruchomienie programu dla czterech wątków:

$ env OMP_NUM_THREADS=4 ./program

Podstawowe elementy

Diagram konstrukcji OpenMP

Podstawowymi elementami OpenMP są konstrukcje służące do tworzenia wątków, rozdzielania (współdzielenia) pracy, zarządzania środowiskiem danych, synchronizacji wątków, procedury czasu wykonania (poziomu użytkownika) i zmienne środowiskowe.

Dyrektywa kompilatora C/C++ pragma (ang. pragmatic information), przy użyciu OpenMP jest zapisywana w kodzie następująco:

#pragma omp <reszta "pragmy">

Specyficzne dla OpenMP "pragmy":

Tworzenie wątku

omp parallel. Jest używana do przydzielenia dodatkowych wątków do równoległego wykonania pracy zawartej w konstrukcji. Oryginalny proces zostanie oznaczony jako główny wątek z ID równym 0.

Przykład: Wyświetl "Hello, world" przy użyciu wielu wątków.

 int main(int argc, char* argv[])
 {
   #pragma omp parallel
   printf("Hello, world!\n");
   return 0;
 }

Konstrukcje związane ze współdzieleniem pracy

Konstrukcje te są używane do ustalenia, jak przyporządkować niezależną pracę do jednego lub wszystkich wątków.

  • omp for lub omp do – używane do rozdzielania iteracji pętli pomiędzy wątki, zwane także konstrukcjami pętli.
  • sections – przypisanie następujących po sobie, ale niezależnych bloków kodu do różnych wątków
  • single – wyszczególnienie bloku kodu, który będzie przetwarzany przez tylko jeden wątek, z barierą na końcu[2]
  • master – podobne do single, przy czym kod jest przetwarzany tylko przez wątek główny, bez bariery na końcu[2]

Przykład: równoległa inicjalizacja wartości dużej tablicy, każdy wątek wykonuje część pracy:

int main(int argc, char **argv) {
    const int N = 100000;
    int i, a[N];

    #pragma omp parallel for
    for (i = 0; i < N; i++)
        a[i] = 2 * i;

    return 0;
 }

Klauzule OpenMP

Ponieważ OpenMP jest modelem programowania ze współdzieloną pamięcią, większość zmiennych w OpenMP jest domyślnie widoczna dla wszystkich wątków. Ponieważ czasami prywatne zmienne są niezbędne, aby zapobiec błędnemu stanowi przy przesyłaniu wartości pomiędzy sekwencyjną a równoległą częścią programu (blokiem kodu wykonywanym równolegle), środowisko zarządzania danymi jest realizowane za pomocą klauzul atrybutów współdzielenia danych poprzez dołączenie ich do dyrektyw OpenMP.

Różne typy warunków:

Klauzule atrybutów współdzielenia danych

  • shared – dane wewnątrz równolegle przetwarzanego regionu są współdzielone, co oznacza, że są widoczne i dostępne dla wszystkich wątków jednocześnie. Domyślnie wszystkie zmienne w regionie współdzielonej pracy są shared z wyjątkiem licznika iteracji pętli.
  • private – dane wewnątrz równolegle przetwarzanego regionu są prywatne dla każdego wątku, co oznacza, że każdy wątek posiada lokalną kopię i używa jej jako zmienną tymczasową. Prywatne zmienne nie są inicjalizowane, ich wartość nie jest udostępniana do użycia poza regionem przetwarzanym równolegle. Domyślnie liczniki iteracji pętli są prywatne.
  • default – pozwala programiście ustawiać domyślny zasięg zmiennych wewnątrz równolegle przetwarzanego regionu, poprzez użycie shared, private lub none. Opcja none zmusza programistę do deklarowania każdej zmiennej w równolegle przetwarzanym regionie przy użyciu klauzul atrybutów współdzielenia danych.

Klauzule synchronizacji

  • critical section – zawarty blok kodu będzie przetwarzany przez tylko jeden wątek w danym czasie, a nie jednocześnie przez kilka. Jest często używany do ochrony współdzielonych danych przed błędnym stanem
  • atomic – podobne do critical section, ale informuje kompilator aby zostały użyte specjalne instrukcje sprzętowe dla zapewnienia lepszej wydajności. Kompilatory mogą zignorować tę sugestię od użytkownika i użyć critical section.
  • ordered – zawarty blok jest przetwarzany w porządku w którym iteracje są uruchamiane w sekwencyjnej pętli
  • barrier – każdy wątek czeka, zanim wszystkie inne wątki osiągną ten punkt. Konstrukcje współdzielące prace posiadają ukrytą synchronizację barier na końcu.
  • nowait – ustala, że wątek kompletujący przyporządkowaną mu pracę, może pracować bez czekania na inne wątki przed zakończeniem. W przypadku braku tej klauzuli, wątki przeprowadzają synchronizację bariery na końcu bloku pracy współdzielonej.

Klauzule planowania

  • schedule(type, chunk) – Jest to użyteczne jeśli konstrukcja współdzieląca prace jest pętlą do lub for. Określa sposób podziału pętli na części wykonywane równolegle. Iteracja(iteracje) w konstrukcji współdzielącej pracę jest przyporządkowana do wątku bazując na metodzie planującej zdefiniowanej przez tę klauzulę. Parametr „type” określający sposób rozdziału iteracji (sposób szeregowania) jest obowiązkowy (sposoby planowania są opisanie poniżej). Drugi parametr „chunk” jest opcjonalny. Określa on wielkość równolegle przetwarzanej części. Musi być liczbą całkowitą. Poszczególne wątki w blokach są rozmiaru „chunk” do których przydzielane są iteracje. Typy planowania to:
  1. static – Tutaj, każdy z wątków posiada przypisane iteracje przed uruchomieniem iteracji pętli. Domyślnie, iteracje są dzielone po równo między wątki. Określenie całkowitej wartości dla parametru „chunk”, spowoduje przydzielenie tej ilości następujących po sobie iteracji do konkretnego wątku. Jeżeli programista pominie parametr „chunk”, zbiór iteracji zostanie podzielony na podzbiory o wielkości (w przybliżeniu) równej liczba_iteracji/liczba_wątków, a każdy wątek otrzyma przynajmniej jeden podzbiór.
  2. dynamic – Tutaj, pewna ilość iteracji jest przypisywana do mniejszej ilości wątków. Gdy konkretny wątek skończy swoją iterację, pobiera następną z pozostałych wolnych iteracji. Ostatni podzbiór może mieć mniejszą wielkość niż ta określona przez parametr „chunk”. Parametr „chunk” definiuje ilość iteracji, które są przyporządkowywane do wątku za każdym razem. Gdy „chunk” nie jest określony, wówczas podzbiory są jednoelementowe.
  3. guided – Duży fragment następujących po sobie iteracji jest przypisywany do każdego wątku dynamicznie (jak powyżej). Rozmiar fragmentu zmniejsza się wykładniczo, wraz z każdą pomyślną alokacją, do minimalnego rozmiaru zdefiniowanego w parametrze „chunk”. Jeśli programista ustawi parametr „chunk” na 1, to rozmiar każdego zbioru jest opisany algorytmem: liczba_nieprzydzielonych_iteracji/liczba_wątków. Wartość ta zmierza do 1. Adekwatnie jeśli „chunk” ustalony zostaje na m gdzie m>1, to rozmiar porcji ustalany jest podobnie jak wyżej, lecz nie może on stać się mniejszy od m. Wyjątkiem jest jedynie ostatnia porcja. Może ona być mniejsza od zadanej wielkości. Domyślny „chunk” (gdy nie jest ustalony) jest równy 1.
  4. „auto” – System samodzielnie określa podział zrównoleglenia zadania.
  5. „runtime” – Ta opcja zezwala na określanie na wykorzystywanie powyższych możliwości w trakcie działania programu. Przekazywanie jest powiązane ze zmienną środowiskową OMP_SCHEDULE:
$ export OMP_SCHEDULE="dynamic"
$ export OMP_SCHEDULE="guided,4"

Kontrola IF

  • if – Powoduje, że wątki zrównoleglają zadanie tylko wtedy gdy warunek jest spełniony. W innym wypadku blok kodu jest przetwarzany szeregowo.

Inicjalizacja

  • firstprivate – dane prywatne dla każdego wątku, inicjalizowane przy użyciu wartości zmiennych o nazwach takich jak w głównym wątku.
  • lastprivate – dane prywatne dla każdego wątku. Wartości są kopiowane na zewnątrz zrównoleglonego rejonu, do zmiennych globalnych o takiej samej nazwie, jeśli bieżąca iteracja jest ostatnią iteracją zrównoleglonej pętli. Zmienna może być zarówno firstprivate, jak i lastprivate.
  • threadprivate – dane są danymi globalnymi, stają się prywatne w każdym zrównoleglonym regionie podczas uruchomienia. Różnica pomiędzy threadprivate a private polega na tym, że w pierwszym występuje globalna przestrzeń przypisywana przez threadprivate a w drugim wartość przetwarzana w zrównoleglonych regionach.

Kopiowanie danych

  • copyin – podobnie do firstprivate dla zmiennych private, zmienne threadprivate nie są inicjalizowane, jeśli nie zostanie użyte copyin do przekazania wartości z powiązanej zmiennej globalnej. Nie jest potrzebne żadne copyout, ponieważ wartość zmiennej threadprivate jest zarządzana poprzez przetwarzanie całego programu.
  • copyprivate – używane z single do obsługi kopiowania danych z prywatnych obiektów jednego wątku (wątku single) do powiązanych obiektów w innych wątkach.

Redukcja

  • reduction(operator | intrinsic: list) – zmienna posiada lokalną kopię w każdym wątku, lecz wartości lokalnych kopii są podsumowywane (redukowane) do współdzielonej globalnie zmiennej. Jest to bardzo użyteczne jeśli dana operacja (ustalona w parametrze „operator” dla tego przypadku) pracuje na interaktywnym typie danych, takim, że jego wartość podczas konkretnej iteracji zależy od jego wartości w poprzedniej. Ogólnie, kroki, które prowadzą do operacyjnej inkrementacji są zrównoleglane, ale wątki gromadzą się i czekają na zaktualizowanie danych, dzięki temu inkrementacja następuje w dobrym porządku co zapobiega błędnym stanom. Jest to wymagane na przykład, przy całkowaniu numerycznym funkcji i równaniach różniczkowych.

Inne

  • flush – Punkt w którym kompilator upewnia się, że wszystkie wątki w obszarze równoległym mają takie samo pojęcie o zmiennych podanych w parametrze
  • master – Uruchamiane jedynie przez wątek główny (wątek zarządzający resztą podczas przetwarzania dyrektywy OpenMP) Żadna niewidoczna bariera nie występuje, inne wątki nie muszą jej osiągnąć.

Procedury poziomu użytkownika

Używane do edycji/sprawdzania ilości wątków, wykrywania czy kontekst jest w zrównoleglonym regionie, ile procesów jest dostępnych w systemie, ustawienia zamków, funkcji czasowych itd.

Zmienne środowiskowe

Metoda zmiany właściwości przetwarzania aplikacji OpenMP. Używane do kontroli planowania iteracji pętli, domyślnej ilości wątków itd. Na przykład OMP_NUM_THREADS jest używana do określenia ilości wątków dla aplikacji.

Przykładowe programy

W tej sekcji przedstawione zostaną przykładowe programy ilustrujące wytłumaczone wyżej koncepcje.

Hello world

Jest to prosty program wykorzystujący dyrektywy parallel, private i barrier oraz funkcje omp_get_thread_num i omp_get_num_threads.

C

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

 int main (int argc, char *argv[]) {
   int th_id, nthreads;
   #pragma omp parallel private(th_id)
   {
     th_id = omp_get_thread_num();
     printf("Hello World from thread %d\n", th_id);
     #pragma omp barrier
     if ( th_id == 0 ) {
       nthreads = omp_get_num_threads();
       printf("There are %d threads\n",nthreads);
     }
   }
   return 0;
 }

C++

#include <omp.h>
#include <iostream>
int main (int argc, char *argv[]) {
 int th_id, nthreads;
#pragma omp parallel private(th_id)
 {
  th_id = omp_get_thread_num();
  std::cout << "Hello World from thread" << th_id << "\n";
#pragma omp barrier
 if ( th_id == 0 ) {
   nthreads = omp_get_num_threads();
   std::cout << "There are " << nthreads << " threads\n";
  }
 }
 return 0;
}

Fortran 77

      PROGRAM HELLO
      INTEGER ID, NTHRDS
      INTEGER OMP_GET_THREAD_NUM, OMP_GET_NUM_THREADS
C$OMP PARALLEL PRIVATE(ID)
      ID = OMP_GET_THREAD_NUM()
      PRINT *, 'HELLO WORLD FROM THREAD', ID
C$OMP BARRIER
      IF ( ID .EQ. 0 ) THEN
        NTHRDS = OMP_GET_NUM_THREADS()
        PRINT *, 'THERE ARE', NTHRDS, 'THREADS'
      END IF
C$OMP END PARALLEL
      END

Fortran 90 (format swobodny)

 program hello90
 use omp_lib
 integer:: id, nthreads
   !$omp parallel private(id)
   id = omp_get_thread_num()
   write (*,*) 'Hello World from thread', id
   !$omp barrier
   if ( id == 0 ) then
     nthreads = omp_get_num_threads()
     write (*,*) 'There are', nthreads, 'threads'
   end if
   !$omp end parallel
 end program

Klauzule w konstrukcjach współdzielących pracę (w C/C++)

Wykorzystanie klauzul OpenMP jest zilustrowane prostymi przykładami w tej sekcji.

Schedule – język C

Zachowanie wszystkich typów klauzul schedule można w prosty sposób zobrazować, wykorzystując klauzule schedule z parametrem runtime. Pozwoli to na kontrolowanie zachowania klauzuli za pomocą zmiennej środowiskowej OMP_SCHEDULE.

#include <omp.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

/*defines the total amount of iterations*/
#define N_ITER 1024
int main(void)
{
    int i,id,chunk_size,numit;
    int array[N_ITER];
    memset(array,0,sizeof(array));
#pragma omp parallel default(none) private(i, id, numit) shared(array)
    {
	numit=0;
	id = omp_get_thread_num();
	printf ("Thread no %d starting... \n", id);
	srand(time(0)*(1+id));
#pragma omp for schedule(runtime) private(id)
	for (i = 0; i < N_ITER; ++i)
	{
	    id = omp_get_thread_num();
	    usleep(rand()%(10000*(1+id)));
	    array[i]=id;
	    numit++;
	}
	printf("Thread %d performed %d iterations\n",id,numit);
    }
    for (i = 0; i < N_ITER; ++i)
	printf("%d",array[i]);
    puts("");
    return 0;
}

Przykład użycia:

$ env OMP_SCHEDULE="static,8" ./schedule
Thread no 1 starting...
Thread no 3 starting...
Thread no 0 starting...
Thread no 2 starting...
Thread 3 performed 256 iterations
Thread 0 performed 256 iterations
Thread 2 performed 256 iterations
Thread 1 performed 256 iterations
0000000011111111222222223333333300000000111111112222222233333333000000001111111
1222222223333333300000000111111112222222233333333000000001111111122222222333333
3300000000111111112222222233333333000000001111111122222222333333330000000011111
1112222222233333333000000001111111122222222333333330000000011111111222222223333
3333000000001111111122222222333333330000000011111111222222223333333300000000111
1111122222222333333330000000011111111222222223333333300000000111111112222222233
3333330000000011111111222222223333333300000000111111112222222233333333000000001
1111111222222223333333300000000111111112222222233333333000000001111111122222222
3333333300000000111111112222222233333333000000001111111122222222333333330000000
0111111112222222233333333000000001111111122222222333333330000000011111111222222
2233333333000000001111111122222222333333330000000011111111222222223333333300000
0001111111122222222333333330000000011111111222222223333333300000000111111112222
2222333333330000000011111111222222223333333300000000111111112222222233333333
$ env OMP_SCHEDULE="dynamic,8" ./schedule
Thread no 2 starting...
Thread no 0 starting...
Thread no 1 starting...
Thread no 3 starting...
Thread 3 performed 120 iterations
Thread 0 performed 480 iterations
Thread 1 performed 256 iterations
Thread 2 performed 168 iterations
2222222200000000111111113333333300000000111111110000000000000000222222220000000
0111111113333333300000000000000001111111122222222000000000000000011111111000000
0022222222000000003333333311111111000000000000000022222222000000001111111100000
0003333333300000000111111110000000022222222000000001111111133333333000000001111
1111222222220000000011111111000000002222222200000000333333331111111100000000222
2222200000000000000001111111100000000111111110000000011111111222222223333333300
0000001111111100000000000000002222222211111111000000003333333300000000111111110
0000000222222220000000011111111000000002222222200000000333333331111111100000000
0000000000000000111111112222222200000000111111113333333300000000222222220000000
0111111110000000033333333000000001111111100000000222222220000000011111111000000
0033333333000000002222222211111111000000001111111100000000222222223333333300000
0000000000011111111000000002222222200000000111111110000000022222222333333330000
0000111111110000000022222222111111110000000033333333000000001111111100000000
$ env OMP_SCHEDULE="guided,8" ./schedule
Thread no 0 starting...
Thread no 2 starting...
Thread no 3 starting...
Thread no 1 starting...
Thread 2 performed 192 iterations
Thread 0 performed 454 iterations
Thread 1 performed 234 iterations
Thread 3 performed 144 iterations
0000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000222222222222222222222222222222222222222222222222222222222222
2222222222222222222222222222222222222222222222222222222222222222222222222222222
2222222222222222222222222222222222222222222222222222233333333333333333333333333
3333333333333333333333333333333333333333333333333333333333333333333333333333333
3333333333333333333333333333333333333331111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000011111111111111111111111111
0000000000000000000000000000000000111111111110000000011111111000000000000000
$ env OMP_SCHEDULE="auto" ./schedule
Thread no 0 starting...
Thread no 1 starting...
Thread no 3 starting...
Thread no 2 starting...
Thread 3 performed 256 iterations
Thread 2 performed 256 iterations
Thread 1 performed 256 iterations
Thread 0 performed 256 iterations
0000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111122222222222222222222222222222222222222222
2222222222222222222222222222222222222222222222222222222222222222222222222222222
2222222222222222222222222222222222222222222222222222222222222222222222222222222
2222222222222222222222222222222222222222222222222222222223333333333333333333333
3333333333333333333333333333333333333333333333333333333333333333333333333333333
3333333333333333333333333333333333333333333333333333333333333333333333333333333
3333333333333333333333333333333333333333333333333333333333333333333333333333

Reduction(operator:zmienna) – język C

Kolejny fragment kodu przedstawia typowy przykład użycia klauzuli „reduction” do zrównoleglenia obliczania sumy. W tym konkretnym przykładzie za pomocą pętli for wyznaczamy sumę elementów tablicy „a” mnożonych przez wagi zależne od zmiennej „i”. Do zrównoleglenia pętli używamy dyrektyw OpenMP i klauzuli redukcji. Klauzula schedule jest opcjonalna.

 #define N 10000 /*size of a*/
 void calculate(int); /*The function that calculates the elements of a*/
 int i;
 long w;
 long a[N];
 calculate(a);
 long sum = 0;
 /*forks off the threads and starts the work-sharing construct*/
 #pragma omp parallel for private(w) reduction(+:sum) schedule(static,1)
 for(i = 0; i < N; i++)
    {
      w = i*i;
      sum = sum + w*a[i];
    }
 printf("\n %li",sum);

Równoważna, acz mniej elegancka implementacja polega na zastosowaniu (lokalnej i prywatnej w każdym wątku) zmiennej przechowującej sumę częściową wyznaczoną w każdym wątku (loc_sum). Po wyznaczeniu wszystkich sum częściowych są one dodawane do zmiennej sum. Operacja ta wykonywana jest w sekcji krytycznej zadeklarowanej dyrektywą „critical” [1].

 ...
 long sum = 0, loc_sum = 0;
 /*forks off the threads and starts the work-sharing construct*/
 #pragma omp parallel for private(w,loc_sum) schedule(static,1)
 {
   for(i = 0; i < N; i++)
     {
       w = i*i;
       loc_sum = loc_sum + w*a[i];
     }
   #pragma omp critical
   sum = sum + loc_sum;
 }
 printf("\n %li",sum);

Implementacje

OpenMP zostało zaimplementowane w wielu komercyjnych kompilatorach. Na przykład w Visual C++ 2005 (w edycjach Professional i Team System[3], w Intel Parallel Studio dla różnych procesorów[4] oraz w kompilatorach z Sun Studio wspierających ostatnie specyfikacje OpenMP[5] z udoskonaleniami dla Solarisa (UltraSPARC i x86/x64) i Linuksa. Kompilatory Fortranu, C i C++ z The Portland Group[6] także wspierają OpenMp 2.5, GCC wspiera OpenMP od wersji 4.2.

Kilka kompilatorów posiada wczesną implementację OpenMp 3.0:

  • GCC 4.3.1
  • kompilator Nanos
  • kompilatory Intel Fortran i C/C++ wersje 11.0 i 11.1, Intel Parallel Studio.
  • IBM XL C/C++ Compiler[7]

Sun Studio 12 update 1 posiada pełną implementację OpenMP 3.0[8].

Za i przeciw

  • Za:
    • Prostota – nie ma potrzeby przejmowania się przesyłaniem wiadomości, jak w MPI
    • Układ danych i dekompozycja jest obsługiwana automatycznie przez dyrektywy
    • Równoległość inkrementacyjna – można pracować na jednej porcji programu w jednym czasie, nie są potrzebne drastyczne zmiany kodu
    • Zunifikowany kod dla szeregowych i równoległych aplikacji – konstrukcje OpenMP są traktowane jako komentarz podczas kompilacji przy użyciu sekwencyjnego kompilatora
    • Oryginalny (szeregowy) kod na ogół nie potrzebuje zmian przy jego zrównoleglaniu przy użyciu OpenMP. Redukuje to szanse nieumyślnego wprowadzenia błędów przy konwersji.
    • Zarówno grubo-, jak i drobnoziarnista równoległość jest możliwa.
  • Przeciw:
    • OpenMP przeznaczony jest wyłącznie do zrównoleglenia kodów działających w systemach z pamięcią wspólną (czyli architektura SMP oraz NUMA).
    • Wymaga kompilatora wspierającego OpenMP.
    • Skalowalność jest limitowana przepustowością pamięci.
    • Brakuje niezawodnej obsługi błędów.
    • Brakuje drobno-ziarnistych mechanizmów kontroli przypisania wątku do procesora (CPU affinity np. taskset)

Spodziewane wyniki działania

Można się spodziewać otrzymać N razy mniejszy czas wykonania (lub N-krotne przyspieszenie) podczas przetwarzania równoległego przy użyciu OpenMP na N-procesorowej platformie. W praktyce rzadko ma to miejsce z następujących powodów:

  • Duża część programu może nie być możliwa do zrównoleglenia przy użyciu OpenMP, co oznacza, że teoretyczny górny limit przyspieszenia jest zgodny z prawem Amdahla.
  • N procesorów w SMP może posiadać N * (moc obliczeniowa 1 procesora) mocy, jednak przepustowość pamięci zwykle nie mnoży się przez N. Całkiem często oryginalna ścieżka do pamięci jest współdzielona przez wiele procesorów, obniżenie wydajności może zostać zaobserwowane przy korzystaniu ze współdzielonej pamięci.
  • Wiele innych powszechnych problemów wpływających na przyspieszenie w przetwarzaniu równoległych stosuje się do OpenMp, takich jak równoważenie obciążenia i narzut związany z synchronizacją.

Przynależność wątków

Niektórzy producenci zalecają ustawianie koligacji procesorów na wątki OpenMP, w celu przyporządkowania ich do poszczególnych rdzeni procesora[9][10][11]. Minimalizuje to migrowanie wątków między procesorami i koszt przełączania kontekstu. Dodatkowo, poprawia dostęp do danych poprzez zredukowanie dostępu do cache procesora, na którym wątek nie jest uruchomiony.

Zobacz też

Przypisy

  1. ↑ Jay Hoeflinger: Cluster OpenMP for Intel® Compilers. Intel Corporation, 2008-05-20. [dostęp 2015-09-06]. (ang.).
  2. ↑ a b Blaise Barney: OpenMP. Lawrence Livermore National Laboratory. [dostęp 2015-09-06]. (ang.).
  3. ↑ Visual C++ Editions. [w:] MSDN [on-line]. Microsoft Corporation. [dostęp 2015-09-06]. (ang.).
  4. ↑ David Worthington: Intel addresses development life cycle with Parallel Studio. [w:] SD Times [on-line]. BZ Media LLC, 2009-05-26. [dostęp 2015-09-06]. [zarchiwizowane z tego adresu (2012-02-15)]. (ang.).
  5. ↑ OpenMP Specifications. OpenMP Architecture Review Board. [dostęp 2015-09-06]. [zarchiwizowane z tego adresu (2008-10-04)]. (ang.).
  6. ↑ PGI Products. The Portland Group. [dostęp 2015-09-06]. (ang.).
  7. ↑ XL C/C++ for Linux. IBM Corporation. [dostęp 2015-09-06]. (ang.).
  8. ↑ Oracle Solaris Studio Features. Oracle Corporation. [dostęp 2015-09-06]. [zarchiwizowane z tego adresu (2012-06-26)]. (ang.).
  9. ↑ Yurong Chen, Eric Li, Jianguo Li, Yimin Zhang. Accelerating Video Feature Extractions in CBVIR on Multi-Core Systems. „Intel Technology Journal”. 11 (4), s. 349, 2007-11-15. Intel Corporation. DOI: 10.1535/itj.1104.08. ISSN 1535-864X. (ang.). 
  10. ↑ OMPM2001 Result. Standard Performance Evaluation Corporation, 2008-02-13. [dostęp 2015-09-06]. (ang.).
  11. ↑ OMPM2001 Result. Standard Performance Evaluation Corporation, 2003-04-16. [dostęp 2015-09-06]. (ang.).

Bibliografia

  • Quinn Michael J, Parallel Programming in C with MPI and OpenMP McGraw-Hill Inc. 2004. ISBN 0-07-058201-7.
  • R. Chandra, R. Menon, L. Dagum, D. Kohr, D. Maydan, J. McDonald, Parallel Programming in OpenMP. Morgan Kaufmann, 2000. ISBN 1-55860-671-8.
  • R. Eigenmann (Editor), M. Voss (Editor), OpenMP Shared Memory Parallel Programming: International Workshop on OpenMP Applications and Tools, WOMPAT 2001, West Lafayette, IN, USA, July 30-31, 2001. (Lecture Notes in Computer Science). Springer 2001. ISBN 3-540-42346-X.
  • B.Chapman, G. Jost, R. vanderPas, D.J. Kuck, Using OpenMP: Portable Shared Memory Parallel Programming. The MIT Press (October 31, 2007). ISBN 0-262-53302-2.
  • Parallel Processing via MPI & OpenMP, M. Firuziaan, O. Nommensen. Linux Enterprise, 10/2002.

Linki zewnętrzne

Benchmarki

Źródła do nauki online

Pozostałe

Media użyte na tej stronie

Fork join pl.svg
Ilustracja implementacji wielowątkowości: główny wątek rozdziela się na pewną liczbę wątków potomnych współbieżnie wykonujących określony fragment kodu, które po wykonaniu zadania włączają się do wątku głównego, po czym proces ten może być wielokrotnie powtórzony.