headerphoto

Problem n-królowych i wielowatkowość - PLIKI DO POBRANIA NA KOŃCU STRONY

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
Nazwa
OS
Rozmiar Pobierz plik
Screenshot
Problem n-królowych z elementami OpenMP (src)
Unix
2.1 kb.