Kurs jest częścią programu Xtreme Computing.

Autorem kursu jest Paweł Przybyłowicz - asystent na Wydziale Matematyki Stosowanej AGH.

Krok 4 - zrównoleglanie pętli, opcja reduction.

Powracamy do tematu zrównoleglania pętli for, aby omówić jeden szczególny jej przypadek. Traktujemy go oddzielnie, gdyż przypadek ten nie da się zrównoleglić w sposób opisany na Lekcji 1 i Lekcji 2. Zastanówmy się, jak rozdzielić iteracje pętli występujące w funkcjach count_pi1 oraz count_pi2 z Lekcji 3? Problem ten istotnie różni się od problemu z Lekcji 1, ponieważ teraz obliczone wartości akumulujemy, za pomocą operacji dodawania lub mnożenia, do jednej zmiennej tmp. Przypominamy, że każdy element tablicy był wyliczany przez jeden odpowiedni wątek, który nie wchodził w drogę pozostałym. W związku z tym zastosowanie poznanych metod w funkcjach count_pi1 i count_pi2 może prowadzić do błędów. Wystarczy, że dwa wątki będą chciały jednocześnie uaktualnić wartość zmiennej tmp. Konflikt między wątkami wystąpi, gdy na przykład w procedurze count_pi1 napiszemy:

Program 04/01 - step_0401.c

// ... void count_pi1(double *pi) { double tmp = 1.0, a_n; long int i, N; N = ACCURACY; #pragma omp parallel for default(none) shared(N, tmp) private(a_n, i) for (i = 1; i <= ACCURACY; i++) { a_n = (double)(4.0*i*i / (4.0*i*i - 1.0)); tmp = tmp * a_n; } *pi = (double)(2.0 * tmp); } // ...

lub

Program 04/02 - step_0402.c

// ... void count_pi1(double *pi) { // ... #pragma omp parallel for default(none) shared(N) private(a_n, i, tmp) // ... } // ...

Powyższe procedury mogą zawiesić program albo dać niepoprawne wyniki (ćwiczenie 1). Jak rozwiązać ten problem? Z pomocą przychodzi kolejna dyrektywa OpenMP, nazwana reduction. Ma ona następującą składnię:

reduction (operator : lista)
Opcja operator mówi kompilatorowi jakie działanie jest wykorzystane do aktualizacji zmiennej (zmiennych) wymienionej (wymienionych) w list. Dopuszczalnymi działaniami są:
OperatorNazwa działania
+dodawanie
-odejmowanie
*mnożenie
&koniunkcja bitowa
|alternatywa bitowa
^operacja bitowa EXOR
&&koniunkcja logiczna
||alternatywa logiczna
Poniższy przykład ilustruje zasadę użycia tej dyrektywy.

Program 04/03 - step_0403.c

#include <stdio.h> #include <stdlib.h> #include <time.h> #include <omp.h> #define ACCURACY 200000000 // Metoda Wallis'a obliczania wartosci liczby Pi bez OpenMP. void count_pi1(double *pi) { double tmp = 1.0, a_n; long int i, N; N = ACCURACY; for (i = 1; i <= N; i++) { a_n = (double)(4.0*i*i / (4.0*i*i - 1.0)); tmp = tmp * a_n; } *pi = (double)(2.0 * tmp); } // Metoda Leibniza obliczania wartosci liczby Pi bez OpenMP. void count_pi2(double *pi) { double tmp = 0.0, a_n; long int i, N; N = ACCURACY; for (i = 0; i < N; i++) { if (i % 2 == 0) { a_n = (double)(1.0 / (2.0*i + 1.0)); } else { a_n = (double)(-1.0 / (2.0*i + 1.0)); } tmp = tmp + a_n; } *pi = (double)(4.0 * tmp); } // Metoda Wallis'a obliczania wartosci liczby Pi z wykorzystaniem OpenMP. void count_pi1_omp(double *pi) { double tmp = 1.0, a_n; long int i, N; N = ACCURACY; #pragma omp parallel for default(none) shared(N) private(a_n, i) \ reduction(* : tmp) for (i = 1; i <= N; i++) { a_n = (double)(4.0*i*i / (4.0*i*i - 1.0)); tmp = tmp * a_n; } *pi = (double)(2.0 * tmp); } // Metoda Leibniza obliczania wartosci liczby Pi z wykorzystaniem OpenMP. void count_pi2_omp(double *pi) { double tmp = 0.0, a_n; long int i, N; N = ACCURACY; #pragma omp parallel for default(none) shared(N) private(a_n, i) \ reduction(+ : tmp) for (i = 0; i < N; i++) { if (i % 2 == 0) { a_n = (double)(1.0 / (2.0*i + 1.0)); } else { a_n = (double)(-1.0 / (2.0*i + 1.0)); } tmp = tmp + a_n; } *pi = (double)(4.0 * tmp); } // Program glowny. int main(int argc, char *argv[]) { double p1, p2; time_t begin_t, end_t; printf("Bez OpenMP:\n"); begin_t = time(NULL); count_pi1(&p1); count_pi2(&p2); end_t = time( NULL); printf("Metoda Wallis'a Pi = %f.\n" , p1); printf("Metoda Leibniz'a Pi = %f.\n" , p2); printf("Czas wykonywania obliczen: %f.\n\n", difftime(end_t, begin_t)); printf("Z OpenMP:"); begin_t = time(NULL); count_pi1_omp(&p1); count_pi2_omp(&p2); end_t = time(NULL); printf("Metoda Wallis'a Pi = %f.\n" , p1); printf("Metoda Leibniz'a Pi = %f.\n" , p2); printf("Czas wykonywania obliczen: %f.\n\n", difftime(end_t, begin_t)); return 0; }

Pisząc reduction(+ : tmp) w funkcji count_pi2_omp, informujemy kompilator, że do zmiennej tmp będziemy dodawać (operator +) kolejno wyliczone wartości a_n. Kompilator utworzy odpowiednią liczbę prywatnych kopii zmiennej tmp dla każdego wątku i rozdzieli iteracje pomiędzy dostępne wątki. Każdy wątek będzie operował tylko na swojej kopii zmiennej tmp. Po wykonaniu wszystkich iteracji, wartości wyliczone przez wszystkie wątki są do siebie dodawane. Obliczona wartość zmiennej tmp typu reduction jest dostępna poza sekcją parallel dlatego możemy napisać:

*pi = (double)(2.0 * tmp);
Taka sama jest zasada działania dyrektywy reduction dla innych operatorów.

Zastanówmy się jeszcze przez moment nad następującą linią programu:

N = ACCURACY;
Czy to przypisanie zmiennej N wartości zawartej w predefiniowanej stałej ACCURACY nie jest czasem zbędne? Okazuje się, że nie. Dyrektywy private i shared wymagają zmiennych jako argumentów. Pisząc
#pragma omp parallel shared(ACCURACY)
spowodowalibyśmy błąd, zakomunikowany przez kompilator. Poleceniem shared(ACCURACY) nie wskazujemy kompilatorowi zmiennej, która ma być wspólna dla wszystkich wątków, gdyż ACCURACY jest tylko etykietą.

Dyrektywy reduction używamy razem z dyrektywą parallel. Ponadto, może ona być użyta w jednej pętli for więcej niż raz. Możemy bowiem napisać:

Program 04/04 - step_0404.c

// ... void count_pi12_omp(double *pi) { double tmp1 = 0.0, tmp2 = 1.0; double a_n1, a_n2; long int i, N; N = ACCURACY; #pragma omp parallel for default(none) shared(N) private(a_n1, a_n2, i) \ reduction(+ : tmp) reduction(* : tmp2) for (i = 0; i < N; i++) { // Metoda Wallis'a if (i % 2 == 0) { a_n1 = (double)(1.0 / (2.0*i + 1.0)); } else { a_n1 = (double)(-1.0 / (2.0*i + 1.0)); } tmp1 = tmp1 + a_n; // Metoda Leibniz'a a_n2 = (double)(4.0*(i+1)*(i+1) / (4.0*(i+1)*(i+1) - 1.0)); tmp2 = tmp2 * a_n2; } *pi1 = (double)(4.0 * tmp1); *pi2 = (double)(2.0 * tmp2); } // ...

Funkcja count_pi12_omp wylicza, obiema metodami jednocześnie, wartość liczby Pi.

Ćwiczenia:

  1. Przypomnij sobie zasady działania opcji private i shared. Czy potrafisz wytłumaczyć na czym będzie polegał konflikt wątków w przypadku funkcji w Program 04/01? Dlaczego funkcja w Program 04/02 daje również złe wyniki?
  2. Napisz funkcję, która w jednej pętli for wyliczy wartości średniej arytmetycznej i średniej geometrycznej liczb zawartych w tablicy N-elementowej.

Kolejne lekcje tutorialu:

OpenMP.pl - polski portal użytkowników standardu OpenMP.