Kurs jest częścią programu Xtreme Computing.

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

Krok 6 - prosty problem praktyczny

W poprzednich lekcjach koncentrowaliśmy się głównie na opisie dyrektyw OpenMP. Każda lekcja zawierała opis nowej opcji, a podane przykłady miały jedynie ilustrować jej działanie. W tej części postąpimy odwrotnie - zastosujemy zdobyte do tej pory wiadomości do rozwiązania konkretnego problemu. Mianowicie, pokażemy jak zrównoleglić wyszukiwanie najmniejszego elementu w jednowymiarowej tablicy liczb rzeczywistych.

Klasyczna funkcja wyszukująca przyjmuje na początku, że najmniejszym elementem jest pierwszy element tablicy. Następnie porównuje ten element z pozostałymi i jeśli trafi na mniejszy, to za nowy element minimalny przyjmuje ten mniejszy. Następnie procedura ta jest kontynuowana, póki nie dojdziemy do końca tablicy.

Korzystając z OpenMP możemy zrównoleglić procedurę wyszukującą. W tym celu, dzielimy tablicę na tyle rozłącznych pod-tablic ile jest dostępnych wątków. Każdy wątek będzie teraz poszukiwał elementu minimalnego w swojej części tablicy. Biorąc minimum z minimów pod-tablic dostajemy najmniejszą wartość wyjściowej tablicy. Stosujemy więc metodę dziel i zwyciężaj.

Funkcje w poniższym programie realizują algorytm opisany powyżej.

Program 06/01 - step_0601.c

#include <stdio.h> #include <stdlib.h> #include <time.h> #include <omp.h> // Szukamy najmniejszego elementu w pod-tablicy tablic tab. void min_sub_tab(double *tab, long start_point, long n_points, double *sub_min) { long i; double tmp; // Tymczasowo przyjmujemy ze pierwszy element jest najmniejszy. tmp = tab[start_point]; for (i = 0; i < n_points; i++) { // Porownujemy z reszta elementow i jesli trafimy na mniejszy // to przyjmujemy ze tymczasowym minimum jest ten nowy element. if (tmp > tab[start_point+i]) tmp = tab[start_point+i]; } *sub_min = tmp; } void min_tab_omp(double *tab, long n_points, double *tab_min) { // ppt - points per thread - liczba elementów na watek. // sp - starting point. int n_threads, id; long ppt, sp; double *min, global_min; #pragma omp parallel default(none) private(id, ppt, sp) \ shared(n_threads, min, n_points, tab) { #pragma omp single { n_threads = omp_get_num_threads(); min = (double*)malloc(n_threads * sizeof(double)); } id = omp_get_thread_num(); ppt = (long)((n_points + n_threads - 1) / n_threads); sp = id * ppt; if (id == n_threads - 1) ppt = n_points - sp; min_sub_tab(tab, sp, ppt, &min[id]); } min_sub_tab(min, 0, n_threads, &global_min); *tab_min = global_min; free(min); } int main(void) { long N = 70502000, j, k; double *tab1, *tab2, *tab3, min1[3], min2[3]; time_t begin_t, end_t; tab1 = (double*)malloc(N * sizeof(double)); tab2 = (double*)malloc(N * sizeof(double)); tab3 = (double*)malloc(N * sizeof(double)); for (j = 0; j < N; j++) { tab1[j] = N - j; tab2[j] = (double)((j+1.0) * (N-j)/33.2); tab3[j] = (double)(j * (N - j) * (2.0 * N - j) / 100.0); } printf("Bez OpenMP:\n"); begin_t = time(NULL); min_sub_tab(tab1, 0, N, &min1[0]); min_sub_tab(tab2, 0, N, &min1[1]); min_sub_tab(tab3, 0, N, &min1[2]); end_t = time(NULL); printf("Czas obliczen %f sekund:\n", difftime(end_t, begin_t)); printf("Element najmniejszy tab1 %f.\n", min1[0]); printf("Element najmniejszy tab2 %f.\n", min1[1]); printf("Element najmniejszy tab3 %f.\n", min1[2]); printf("Z uzyciem OpenMP:\n"); begin_t = time(NULL); min_tab_omp(tab1, N, &min2[0]); min_tab_omp(tab2, N, &min2[1]); min_tab_omp(tab3, N, &min2[2]); end_t = time(NULL); printf("Czas obliczen %f sekund:\n", difftime(end_t, begin_t)); printf("Element najmniejszy tab1 %f.\n", min2[0]); printf("Element najmniejszy tab2 %f.\n", min2[1]); printf("Element najmniejszy tab3 %f.\n", min2[2]); free(tab1); free(tab2); free(tab3); return 0; }

Funkcja min_sub_tab szuka minimum w określonej części tablicy tab, tzn. szuka minimum w tab pośród jej n_points elementów, zaczynając od elementu numer start_point. Jeśli zatem napiszemy:

// ... min_sub_tab(tab, 0, N, &min); // ...

wówczas zostanie przeszukana cała tablica tab licząca N elementów i wartość minimalna będzie zapisana w zmiennej min. Natomiast wywołanie:

// ... min_sub_tab(tab, 3, 10, &min); // ...

spowoduje znalezienie minimalnego elementu spośród tych o numerach od 3 do 12. Wywołując funkcję min_sub_tab należy pamiętać aby wartość start_point + n_points nie przekroczyła zakresu tablicy tab.

Funkcja min_tab_omp szuka minimum tablicy tab złożonej z n_points liczb. W tym celu najpierw sprawdza ile jest dostępnych wątków, a następnie tworzy dynamicznie tablicę min o tylu elementach ile jest wątków. Każdemu wątkowi zostaje przypisana pewna porcja (ppt) elementów tablicy tab, wśród których będzie on szukał minimum. Liczba ta jest określona przez funkcję sufit z ilorazu n_points / n_threads. Punkt startu dla każdego wątku określa zmienna sp. Ponieważ wartość ppt jest wyznaczana przez dzielenie całkowite, więc nie zawsze wątki będą obdzielone danymi równomiernie. Jeśli iloraz n_points / n_threads nie jest liczbą całkowitą, to ostatni wątek otrzymuje mniej elementów niż pozostałe. Zobaczmy to na przykładzie. Załóżmy, że tab ma 10 elementów i mamy 4 wątki. Wówczas ppt = 3 i pierwszym trzem wątkom zostanie przypisane po trzy elementy. Ponieważ 3*3 = 9, więc ostatni wątek otrzyma tylko jeden element. W tablicy min zostają zapisane minima znalezione przez poszczególne wątki. Na końcu szukamy sekwencyjnie minimum w tablicy min. Znaleziona wartość jest równa minimum tablicy tab. Zauważmy, że procedura ta będzie wydajna jeśli, paradoksalnie, liczba wątków nie będzie zbyt duża. Jeśli bowiem mielibyśmy tyle wątków ile elementów tablicy tab, to szukanie minimum tablicy min byłoby równoważne szukaniu minimum w tablicy wyjściowej tab i nic w tym przypadku nie zyskujemy.

Ćwiczenia:

  1. Napisz program, który wykonuje również inne operacje na różnych częściach danej tablicy. Na przykład niech szuka minimum z pierwszej połowy, a maksimum z drugiej. Lub też niech sortuje pierwszą część rosnąco, a drugą malejąco.

Kolejne lekcje tutorialu:

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