Zrównoleglanie kodu programu z wykorzystaniem standardu OpenMP
Praktyczne zrównoleglanie problemu n-królowych sprowadza się do wyposażenia programu w elementy wielowątkowości.
Program dedykowany jest komputerom z pamięcią wspólną, dlatego do jego zrównoleglenia użyty zostanie
standard OpenMP. W myśl założeń tego standardu, nie trzeba całkowicie przebudowywać pierwotnego programu. Wystarczy
tylko dodać dyrektywy OpenMP określające operacje (lub bloki operacji), które mają zostać wykonane równolegle. W
przypadku problemu
n-królowych założono, że dystrybucja zadań między wątkami nastąpi w czasie ustawiania pierwszych "n" królowych w 1
wierszu szachownicy "n x n". Ten wymóg wymusił małą modyfikację kodu pierwotnego programu, tak, aby zrównoleglanie
zainicjowane było tylko i wyłącznie w pierwszym wierszu szachownicy. Modyfikacji uległa także tablica col przechowująca
współrzędne królowych na szachownicy. Teraz tablica ta zyskała drugi wymiar, który przechowuje informacje o numerze
gałęzi. Gałęzią nazwano wszystkie rozwinięcia i kombinacje ustawień królowych, które u źródła mają tę samą królową
w pierwszym wierszu. Np. gałęzią nr 0, są wszystkie możliwe kombinacje ustawień królowych (również te nieobiecujące)
zaczynające się od królowej w wierszu 1 i kolumnie 1. Gałąź nr 1 to kombinacje ustawień królowych począwszy od królowej
w wierszu 1
i kolumnie 2, itd. Numer gałęzi jest obok numeru wiersza, zmienną przekazywaną za każdym rekurencyjnym uruchomieniem
funkcji ustaw_Krolowe. W ten sposób obliczenia dla każdej z gałęzi mogą być przechowywane w bezpiecznym, odrębnym
obszarze tablicy col. Gdyby nie istniał ten drugi wymiar, wątki nadpisywałyby wartości w tablicy col, przez co spójność
danych zostałaby naruszona. Załóżmy, że dwa wątki pracują w tym samym czasie nad wierszem nr 3 (analizując dwie różne
gałęzie). W klasycznej implementacji programu oba wątki modyfikowałyby wartość tablicy col[3], przez co wartości pochodzące
z jednego wątku byłyby nadpisane przez drugi. Dzięki zastosowaniu dodatkowego wymiaru zabezpieczono się na wypadek takiej
sytuacji. Wątki modyfikują więc dwa różne obszary tablicy col np. jeden wątek pracuje na col[2][3], a drugi na col[5][3]
(gdzie wartości 2 i 5 to numery gałęzi).
Główny obszar zrównoleglania rozpoczyna się następującą dyrektywą:
#pragma omp parallel shared (wiersz,n,col) private (galaz) default (none)
Określono w nim "widzialność" zmiennych biorących udział w zrównoleglaniu. Domyślnie nie są one ani prywatne ani
współdzielone (klauzula default(none)), należy więc jasno określić ich zasięg. Zmienną współdzieloną przez wszystkie
wątki, jest zmienna określająca numer aktualnie przetwarzanego wiersza (wiersz), rozmiar szachownicy (n) oraz tablica
zawierająca lokalizacje królowych (col). Zmienną prywatną jest zaś numer gałęzi, którą przetwarza w danym momencie
czasu tylko jeden wątek.
Następna konstrukcja określa sposób, w jaki gałęzie drzewa przestrzeni stanów zostaną rozdystrybuowane między wątkami.
Tryb dynamic,1 wskazuje, że gałęzie będą przydzielane dynamicznie, po jednej iteracji na wątek.
#pragma omp for schedule(dynamic,1)
W zrównoleglonej pętli for następuje wypełnienie królowymi pierwszego wiersza szachownicy. Każda królowa staje się podstawą nowej gałęzi, co jest odnotowywane w tablicy col. Do każdej królowej z wiersza 1 dołączany jest unikalny numer gałęzi, który potem przekazywany jest jako parametr funkcji w kolejnych wywołaniach metody ustaw_Krolowe (już jako zmienna num_g). Dzięki temu wątki pracują równocześnie na różnych gałęziach drzewa przestrzeni stanów. Jedynym miejscem programu, w którym wątki niejako spotykają się ze sobą, jest zmienna rozw. Jest to globalna zmienna, przechowująca liczbę możliwych ustawień królowych na danej szachownicy. Na początku wartość ta zostaje wyzerowana. Jeżeli któryś z wątków odnajdzie rozwiązanie w swojej gałęzi drzewa przestrzeni stanów, inkrementuje wartość zmiennej rozw. Oczywiście w takiej sytuacji należy wzbogacić inkrementację zmiennej rozw o mechanizmy zapobiegające "wyścigowi wątków". Jest to konieczne, w przypadku, gdy kilka wątków modyfikuje zmienną w tym samym czasie. Dlatego, aby uniknąć przypadkowego uszkodzenia danych lub nadpisania wartości przez inny wątek, inkrementację zmiennej rozw określono jako instrukcję atomową. Operacja ta znajduje się poza głównym obszarem zrównoleglania, dlatego ponownie musi zostać zastosowana klauzula OMP PARALLEL.
#pragma omp parallel #pragma omp atomic rozw++;
Dzięki instrukcji atomowej, tylko jeden wątek może modyfikować zmienną rozw w danym momencie czasu. I mimo, że inne wątki
również mogły odnaleźć rozwiązanie i chcą ten fakt odnotować inkrementując zmienną rozw, muszą jednak poczekać aż wątek
realizujący operacje atomową zakończy jej wykonywanie. Taka konstrukcja spowalnia nieco przetwarzanie danych, ponieważ
wprowadziła swoiste kolejkowanie wątków. Jednak jest to jedyny skuteczny i zarazem najbardziej efektywny sposób synchronizowania
wątków. Bez zastosowania instrukcji atomowej w tym miejscu, algorytm wykonywałby się z pewnością znacznie szybciej jednak
zwracane przez niego wyniki byłyby niepoprawne.
Poniżej przedstawiono zbiór metod składających się na kompletny i działający algorytm rozwiązania problemu n-królowych
w środowisku wielowątkowym.
#include < sys/time.h > // obsługa funkcji gettimeofday() #include < unistd.h > // obsługa funkcji usleep() #include < stdio.h > #include < math.h > #include < omp.h > // obsługa wielowątkowości w OpenMP int n; // zmienna przechowuje rozmiar szachownicy int col[25][25]; // tablica współrzędnych na szachownicy unsigned long int rozw=0; // zmienna przechowuje liczbę rozwiązań double czas; // zapamiętuje czasu trwania obliczeń // poniższa metoda zwracajaca aktualny czas z dokładnością do mikrosekund double time_in_seconds() { struct timeval tv; gettimeofday(&tv, NULL); return (double)(tv.tv_sec) + ((double)(tv.tv_usec))/1.0e6; } /* --- GŁÓWNA FUNKCJA PROGRAMU --- */ int main(int argc, char *argv[]) { // zainicjowanie tablicy col for (x=0;x<=25;x++) { for (y=0;y<=25;y++) { col[x][y]=y; } } n = atoi(argv[1]); // odczytanie wielkości szachownicy podanej // przez użytkownika jako argument w linii poleceń. czas = time_in_seconds(); // rozpoczęcie liczenia czasu ustaw_Krolowe (0,0); // wywołanie metody ustaw_Krolowe // dla wiersza 0 i gałęzi 0 czas = time_in_seconds() - czas; // zakończenie liczenia czasu i zwrócenie // różnicy otrzymanych pomiarów. printf("czas trwania obliczeń: %f",czas); return 0; }
Główna funkcja programu zawsze wywołuje metodę ustaw_Krolowe z zerowym parametrem dla rozmiaru szachownicy i numeru gałęzi.
To pojedyncze wywołanie metody ustaw_Krolowe, wprawia w ruch cały rekurencyjny mechanizm algorytmu z powrotami
rozwiązującego problem n-królowych. Bardzo łatwo jest w takiej sytuacji zmierzyć czas potrzebny do wyznaczenia
wszystkich kombinacji ustawień królowych na szachownicy. Wystarczy zmierzyć czas przed wywołaniem funkcji ustaw_Krolowe
i zaraz po. Różnica uzyskanych pomiarów to ogólny czas trwania obliczeń wyrażony z dokładnością do mikrosekund.
Funkcja ustaw_Krolowe zawierająca elementy programowania równoległego
w ramach standardu OpenMP, ma następującą postać:
void ustaw_Krolowe (int wiersz, int num_g) { // num_g - numer gałęzi w drzewie p. stanów int galaz; if (czy_Obiecujacy(wiersz,num_g)==1) // algorytm sprawdza czy królowa // ustawiona w danym wierszu jest // szachowana przez inne. Jeśli tak, // uznaje ten wierzchołek za nieobiecujący { // i nie kontynuuje jego dalszej analizy if (wiersz==n) // jeżeli algorytm dotarł do ostatniego wiersza { // i udało się ustawić królowe we wszystkich // wierszach (wiersz==n) #pragma omp parallel #pragma omp atomic // instrukcja ATOMOWA rozw++; // w tej zmiennej wątki odnotowują // odnalezione rozwiązania // ew. wyświetlają rozwiązanie } else // jeżeli jeszcze nie dotarł { // do ostatniego wiersza szachownicy. if(wiersz==0) // Jeżeli wiersz == 0 to kolejnym wierszem { // jest wiersz 1 szachownicy // i w tym wierszu gałęzie drzewa // zostaną rozdzielone między wątki. // ------------------- OBSZAR ZRÓWNLOLEGLANIA ----------------- // #pragma omp parallel shared (wiersz,n,col) private (galaz) default(none) { #pragma omp for schedule(dynamic,1) // wątki będą przydzielane // dynamicznie for (galaz=1; galaz<=n; galaz++) { col[galaz-1][wiersz+1] = galaz; // ustawienie po jednej królowej // w każdej kolumnie wiersza pierwszego // (wiersz+1), zmienna "galaz" to // indywidualny numer każdej gałęzi, // numeracja od 0 (dlatego galaz-1) ustaw_Krolowe(wiersz+1,galaz-1); // uruchomienie metody dla wiersza // (wiersz+1) wraz z numerem gałęzi. } // koniec pętli for } // ------------- KONIEC OBSZARU ZRÓWNOLEGLANIA -----------// } else // nie jest to pierwszy wiersz szachownicy zatem { // nie następuje już inicjacja wątków. // Bazując na numerze gałęzi (num_g) oraz numerze // wiersza (wiersz) algorytm uruchamia rekurencyjnie // metodę ustaw_Krolowe dla kolejnego wiersza (wiersz+1) // szachownicy. for (galaz=1; galaz<=n; galaz++) { col[num_g][wiersz+1] = galaz; // ustawienie po jednej królowej // w każdej kolumnie kolejnego ustaw_Krolowe(wiersz+1,num_g); // wiersza (wiersz+1) i rekurencyjne // wywołanie metody ustaw_Krolowe } } } } }
Dodatkowa funkcja weryfikująca zależności przestrzenne między królowymi (czy_Obiecujący) nie uległa praktycznie większym zmianom w stosunku do wersji sekwencyjnej. Została jedynie dostosowana do dwuwymiarowej tablicy col i teraz wygląda w następujący sposób:
int czy_Obiecujacy (int i, int num_g) // i - aktualnie analizowany wiersz { // num_g - numer gałęzi int k; int obiecujacy; k = 1; obiecujacy = 1; // domyślnie węzeł jest obiecujący while (k < i && obiecujacy==1) { if (col[num_g][i] == col[num_g][k] || abs (col[num_g][i]-col[num_g][k])==i-k) obiecujacy = 0; // węzeł nieobiecujący k++; } return obiecujacy; }
PLIKI DO POBRANIA |
|