Kurs jest częścią programu Xtreme Computing.

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

Krok 1 - Zrównoleglanie pętli, opcje private i shared.

Lekcją tą rozpoczynamy tutorial, którego celem jest przedstawienie podstawowych zasad korzystania ze standardu OpenMP. W każdym odcinku tutorialu opiszemy podstawowe sposoby i techniki wykorzystywane podczas pisania programów korzystających z OpenMP. Każda lekcja będzie zilustrowana krótkim programem napisanym w języku C, który będzie można skompilować kompilatorem wspierającym standard OpenMP (np.: kompilator ICC wersja 10.1, czy też GCC wersja 4.2).

Zaczniemy od opisu metody zrównoleglania pętli. Jest to jedna z podstawowych technik w OpenMP. Zastosowana w poprawny sposób potrafi znacznie skrócić czas wykonywania programu. Ponieważ dobry przykład tłumaczy więcej niż najlepszy opis teoretyczny, spójrzmy na poniższy kod.

Program 01/01 - step_0101.c

#include <stdio.h> #include <stdlib.h> #include <time.h> #define NUM_LOOPS 50 int main(int argc, char *argv[]) { double **A; double *u, *v; long rows = 5000, columns = 5000; time_t begin_t, end_t; long i, j, k; // Inicjujemy wektory i macierz. u = (double*)malloc(columns * sizeof(double)); v = (double*)malloc(rows * sizeof(double)); A = (double**)malloc(rows * sizeof(double*)); for (i = 0; i < rows; i++) A[i] = (double*)malloc(columns * sizeof(double)); // Wypełniamy wektor u oraz macierz A dowolnymi wartościami. for (i = 0; i < columns; i++) { u[i] = (double)(i / 1000.0f); for ( j = 0; j < rows; j++ ) A[j][i] = (double)(i * j / 1000.0f); } begin_t = time(NULL); // Pętla zewnętrzna. for (k = 0; k < NUM_LOOPS; k++) { // Obliczamy v = A*u z wykorzystaniem dyrektyw OpenMP. #pragma omp parallel for shared(A, v, u, rows, columns) private(i, j) for (i = 0; i < rows; i++) { v[i] = 0.0f; for (j = 0; j < columns; j++) v[i] = v[i] + A[i][j] * u[j]; } } end_t = time(NULL); printf("Czas obliczen: %f.\n", difftime(end_t, begin_t)); // Zwalniamy pamięć. free(u); free(v); for (i = 0; i < rows; i++) free(A[i]); free(A); return 0; }
Powyższy program mnoży macierz A przez wektor u. Program w bardzo prosty sposób wykorzystuje dyrektywy OpenMP do zrównoleglenia głównej pętli. W ogólnym przypadku dyrektywy te mają następującą postać:
#pragma omp nazwa_dyrektywy opcje_i_parametry
Wyraz omp jest słowem kluczowym OpenMP. Programista wykorzystuje dyrektywę parallel, aby wskazać kompilatorowi obszar kodu, który będzie zrównoleglany. Kolejna dyrektywa - for - informuje kompilator, że zrównoleglana będzie pętle typu for. Następnie określa się, które zmienne, wykorzystane w pętli, będą zmiennymi wspólnymi (shared), a które prywatnymi (private). Zmienne wspólne są dostępne dla każdego wątku, natomiast do danej zmiennej prywatnej ma dostęp tylko jeden określony wątek. W naszym programie zmiennymi prywatnymi są i i k, czyli liczniki pętli. Uczynienie ich zmiennymi prywatnymi powoduje, że każdy wątek ma swój wewnętrzny licznik iteracji. Np.: jeśli pętla ma długość 100, to rozdzielając ją na cztery wątki, każdy wątek będzie miał do wykonania po 25 iteracji, a zmienne prywatne poinformują go, w którym miejscu wykonywania obliczeń się znajduje. Ściśle mówiąc, każdy wątek dostaje kopie zmiennych k oraz i i na tych kopiach pracuje. Jest to bardzo ważna część programu i użytkownik musi sam poprawnie określić, która zmienna ma być wspólna, a która prywatna.

Jeśli chodzi o zmienne wspólne to za takie zawsze przyjmuje się zmienne, które określają całkowitą ilość iteracji jaką dana pętla ma wykonać. Ponadto zmiennymi wspólnymi są również te zmienne, których wartości w trakcie obliczeń nie zmieniają się, ale za pomocą których te obliczenia wykonujemy. W programie zmiennymi wspólnymi są: macierz A, wektor u, wektor będący wynikiem mnożenia v = Au oraz zmienne określające liczbę wierszy i kolumn macierzy A. Uczyniliśmy zmienną v zmienną wspólną, mimo że jej wartość zmienia się w trakcie działania programu - powstaje pytanie czy nie spowoduje to konfliktu w czasie jego działania? Otóż nie. W danym momencie określony element wektora v jest obliczany przez jeden konkretny wątek. Ponadto każdy wątek ma swój wewnętrzny licznik pętli (zmienne prywatne!) i wie, które współrzędne wektora v ma jeszcze wyliczyć. OpenMP tak rozdzieli zadania, że nie zajdzie sytuacja, w której dwa wątki będą jednocześnie chciały nadpisać wartość i-tej współrzędnej wektora v.

Zauważmy, że nie podajemy ile wątków program ma wykorzystać. OpenMP sam wykrywa ilość dostępnych wątków i przydziela każdemu odpowiednią liczbę iteracji do wykonania. Np.: jeśli do wykonania będzie 100 iteracji i program ma dostępne dwa wątki, to 50 pierwszych iteracji będzie wykonywał wątek 1, a pozostałe wątek 2. Należy zaznaczyć, że nie zawsze iteracje są rozłożone pomiędzy wątki równomiernie. Za pomocą polecenia schedule możemy kontrolować sposób w jaki OpenMP przydziela iteracje dostępnym wątkom. Dokładniej zajmiemy się tym zagadnieniem w kolejnych lekcjach.

Należy pamiętać o tym, że różnica pomiędzy czasem wykonywania programu na komputerze wielordzeniowym, a czasem wykonywania tego samego programu na komputerze jednordzeniowym będzie zauważalna dopiero dla czasochłonnych operacji. W praktyce oznacza to zazwyczaj dużą liczbę iteracji, bądź konieczność wykonania złożonej funkcji podczas każdego przebiegu pętli. Powyższy program posiada pętlę zewnętrzną, której celem jest uwydatnienie różnic czasowych pomiędzy równoległym, a sekwencyjnym wykonaniem obliczeń. Na komputerze wyposażonym w procesor czterordzeniowy Intel Core2 Quad obliczenia zajęły 3 sekundy, natomiast po wyłączeniu obsługi OpenMP czas zwiększył się do 11 sekund. Oczywiście wyniki te nie mają charakteru absolutnego i będą zależeć od tego na jakim procesorze program został uruchomiony.

Zachęcamy do eksperymentowania na powyższym programie wykonując następujące proste ćwiczenia.

Ćwiczenia:

  1. Zamiast zrównoleglać tylko pętle wykonujące mnożenie macierzy przez wektor, spróbuj zrównoleglić pętlę zewnętrzną - pamiętaj, że zmienna k będzie musiała być teraz zmienną prywatną. Jaki jest teraz czas wykonywania programu?
  2. Manipulując rozmiarami macierzy A oraz ilością iteracji NUM_LOOPS określ w przybliżeniu minimalną ilość danych, przy której opłaca się wykorzystywać OpenMP.

Kolejne lekcje tutorialu:

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