Opis środowiska
Trzecim i zarazem ostatnim środowiskiem sprzętowym, na którym przetestowano program rozwiązujący problem n-królowych
był wydajny serwer oparty na dwóch
64-bitowych procesorach typu Quad-Core Intel Xeon E5345. Każdy procesor składał się
z czterech rdzeni taktowanych zegarem o częstotliwości 2.33 GHz. Na pamięć operacyjną RAM składały się 4 kości Kingston
w standardzie DDR2 ECC Fully Buffered CL5 DIMM, Dual Rank o pojemności 2048 MB każda, taktowane zegarem 667MHz.
Wszystkie te elementy umieszczone zostały na płycie głównej Intel S5000PSLSATA 2GBE 2xXeon/6xSATA/32G FBDIMM (rys. 25).
Serwer pracował pod kontrolą systemu operacyjnego Linux Debian Etch, a jednym z jego elementów był kompilator GCC w
wersji 4.3. Dał on możliwość kompilowania programów z elementami OpenMP. Uruchamianie programu rozwiązującego problem
n-królowych mogło odbywać się bezpośrednio z poziomu powłoki systemu operacyjnego lub za pomocą narzędzi do kolejkowania
zadań (takich jak system OpenPBS). Gruntownym testom poddano obie wersje programu - sekwencyjną i wielowątkową.
Wyniki działania programu sekwencyjnego
Efekty działania programu w wersji sekwencyjnej są niezbędnym elementem w rozważaniach nad bardziej istotną, z punktu
widzenia tej pracy, wielowątkową wersją rozwiązania problemu n-królowych. W tabeli 1 przedstawiono czas trwania obliczeń
dla jedenastu kolejnych szachownic o wymiarach 8x8 - 18x18. Program użyty do testów nie został w żaden sposób zrównoleglony.
|
|
|
|
92 | 0,000724 |
|
352 | 0,004023 |
|
724 | 0,017171 |
|
2 680 | 0,092496 |
|
14 200 | 0,538083 |
|
73 712 | 3,350685 |
|
365 596 | 21,81584 |
|
2 279 184 | 152,1769 |
|
14 772 512 | 1125,413 |
|
95 815 104 | 8734,1560 |
|
666 090 624 | 71134,2489 |
Otrzymane wyniki najlepiej odnieść do podobnych pomiarów dokonanych
w środowisku wielowątkowym.
Wyniki działania programu wielowątkowego
Wielowątkowa wersja programu rozwiązującego problem n-królowych została już przetestowana
na maszynie jedno i dwuprocesorowej (dwurdzeniowej). Teraz przedstawię wyniki pomiarów
przeprowadzone na komputerze ośmiordzeniowym. Przeanalizowałem 9 szachownic, stosując zróżnicowaną liczbę wątków.
W przypadku szachownic o niewielkich rozmiarach (np. 10x10) wszystkie możliwe ustawienia królowych wyznaczono
w przeciągu kilku milisekund. Znacznie bardziej czasochłonne okazały się obliczenia związane z analizą większych
szachownic (np. 17x17 czy 18x18), dla których rozwiązanie problemu n-królowych zajmowało nawet kilkadziesiąt godzin!
Tak jak w przypadku komputera dwurdzeniowego, tak i tutaj wielowątkowy program rozwiązujący problem n-królowych
uruchomiono kilkunastokrotnie dla każdej szachownicy. Przy każdym kolejnym uruchomieniu zwiększano liczbę wątków
biorących udział w przetwarzaniu drzewa przestrzeni stanów. Dokładne wyniki pomiarów dla szachownic o wymiarach
10x10 - 18x18 przedstawiono w tabeli 2.
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
0,02 | 0,014 | 0,80 | 5,01 | 33,24 | 233,94 | 1745,17 | 13646,72 | 111894,38 |
|
0,02 | 0,08 | 0,48 | 3,14 | 21,04 | 158,49 | 1248,35 | 9310,50 | 78970,21 |
|
0,01 | 0,06 | 0,33 | 2,14 | 14,59 | 101,63 | 747,61 | 6051,26 | 51044,55 |
|
0,01 | 0,05 | 0,27 | 1,68 | 11,77 | 382,89 | 637,65 | 5193,96 | 41390,27 |
|
0,01 | 0,04 | 0,23 | 1,42 | 9,70 | 68,34 | 531,77 | 3879,77 | 33996,91 |
|
0,01 | 0,04 | 0,19 | 1,28 | 8,63 | 58,90 | 450,02 | 3456,17 | 28919,05 |
|
0,01 | 0,04 | 0,17 | 1,09 | 7,84 | 54,93 | 388,68 | 3228,63 | 26834,43 |
|
0,01 | 0,04 | 0,17 | 0,98 | 6,78 | 49,31 | 400,46 | 3223,77 | 24189,32 |
|
0,01 | 0,04 | 0,16 | 0,94 | 6,54 | 47,24 | 332,94 | 2695,72 | 22906,92 |
|
0,01 | 0,04 | 0,16 | 0,94 | 6,27 | 46,02 | 346,94 | 2736,01 | 22490,62 |
|
0,01 | 0,04 | 0,16 | 0,93 | 6,23 | 44,07 | 343,23 | 2576,66 | 22780,80 |
|
0,01 | 0,04 | 0,16 | 0,93 | 6,13 | 43,00 | 303,40 | 2745,43 | 20708,21 |
|
0,01 | 0,04 | 0,16 | 0,93 | 5,98 | 40,11 | 283,34 | 2337,61 | 20262,59 |
|
0,01 | 0,04 | 0,16 | 0,92 | 5,97 | 38,87 | 278,03 | 2473,63 | 20508,91 |
|
0,01 | 0,04 | 0,16 | 0,93 | 5,91 | 40,16 | 286,80 | 2174,42 | 19326,26 |
|
- | - | - | - | - | - | 311,32 | 2216,45 | 19089,43 |
|
- | - | - | - | - | - | 277,35 | 2179,55 | 18381,97 |
|
- | - | - | - | - | - | - | - | 17410,19 |
W oparciu o uzyskane wyniki, warto od razu wyliczyć przyśpieszenie uzyskane w procesie przetwarzania szachownic przy użyciu różnej liczby wątków. Dokonano tego na przykładzie szachownicy o wymiarach 17x17. Wyniki obliczeń przedstawiono w tabeli 3, zaś wyznaczone przyśpieszenie ilustruje rys. 1.
|
dla szachownicy 17x17 (w sek.) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Odnosząc się do rys. 1, już na pierwszy rzut oka widać, że rozkład przyśpieszenia jest w miarę regularny.
Mimo drobnych wahań pod koniec wykresu, można wywnioskować że zwiększanie liczby wątków prowadzi do osiągnięcia
coraz wyższego poziomu przyśpieszenia. Szczególnie dla pierwszych 9 wątków prędkość wzrastała bardzo szybko. Już
dla grupy 5 wątków program rozwiązał problem n-królowych ponad dwa razy szybciej niż jego odpowiednik w wersji
sekwencyjnej. Zwiększenie liczby wątków do 10 zaowocowało trzykrotnym przyśpieszeniem, zaś przy 15 wątkach program
wykonywał się prawie cztery razy szybciej w porównaniu do wersji sekwencyjnej.
Czas potrzebny na rozwiązanie problemu n-królowych zmieniał się w zależności od rozmiaru szachownicy, ale także
od sposobu przetwarzania danych. Biorąc za przykład szachownicę o wymiarach 17x17, zauważono, że już dla grupy 3
wątków program wielowątkowy rozwiązuje problem n-królowych szybciej o 44 minuty w porównaniu do wyników wersji
sekwencyjnej. Testowanie programu z większą liczbą wątków prowadzi do uzyskania jeszcze lepszych wyników, co dokładnie
zilustrowano na rys 2. Czas wykonywania się programu w wersji sekwencyjnej, zaznaczono na wykresie czarną linią.
Tak jak wspomniano wcześniej, najlepszy czas uzyskano po zastosowaniu 15 wątków, kiedy to program wyznaczył wszystkie możliwe
ustawienia królowych na szachownicy 17x17 w ciągu zaledwie 36 minut. Dla porównania, ta sama szachownica przetwarzana w klasyczny
(sekwencyjny) sposób wymagała poświęcenia aż 2 godzin i 25 minut czasu pracy serwera. Widać wyraźnie jak duże przyśpieszenie
procesu wykonywania obliczeń można uzyskać poprzez stosowanie wielowątkowego przetwarzania danych na maszynie ośmiordzeniowej.
... więcej czadu ...
Szachownica o wymiarach 17x17 nie jest jednak największą szachownicą, jaką udało się w całości przeanalizować na komputerze
ośmiordzeniowym. Z powodzeniem poczyniono próbę rozwiązania problemu n-królowych dla szachownicy o wymiarach 18x18. Aby obliczyć
czas trwania obliczeń programu w wersji wielowątkowej dla wszystkich osiemnastu wątków, serwer musiał pracować nieprzerwanie przez
niemal cały tydzień (dokładnie: sześć dni, 22 godziny i 59 minut). Uzyskane wyniki nie były jednak zaskakujące, szczególnie na tle
wcześniejszych pomiarów. Program przy największej grupie wątków uzyskał czterokrotne przyśpieszenie względem wersji sekwencyjnej
(podobnie jak to miało miejsce przy szachownicy 17x17). Najlepszy czas otrzymano po uruchomieniu programu z użyciem 18 wątków,
rozwiązanie problemu
n-królowych zajęło wtedy "tylko" 4 godziny i 50 minut. Dla porównania, to samo zadanie, ale zlecone programowi w wersji sekwencyjnej
wymagało poświęcenia aż 19 godzin i 45 minut czasu pracy komputera.
... suma sumarum ...
Korzystając z zasobów silnego ośmiordzeniowego serwera, udało się znacznie wzbogacić wiedzę o zachowaniu programu rozwiązującego
problem n-królowych
w środowisku wielordzeniowym. Odnaleziono wszystkie możliwe ustawienia królowych na bardzo dużej szachownicy 18x18. I mimo że była
to operacja niezmiernie czasochłonna to jednak dzięki dużej mocy obliczeniowej obu procesorów Intel Xeon E5345, stała się możliwa
do zrealizowania. Poza tym, za pomocą dokonanych pomiarów czasu trwania obliczeń dla różnych szachownic (i różnej liczby wątków),
udało się poznać jak zmienia się poziom przyśpieszenia wraz ze wzrostem liczby wątków. Okazało się, że możliwe jest uzyskanie nawet
czterokrotnego przyśpieszenia względem wyników wersji sekwencyjnej. Tak dobry wynik mógł zostać osiągnięty tylko poprzez użycie
procesorów specjalnie zaprojektowanych do równoległego przetwarzania instrukcji. Takimi jednostkami są niewątpliwie bardzo wydajne
procesory z rodziny Xeon 5000, a wśród nich model 5345 zainstalowany w liczbie dwóch sztuk na testowanym serwerze. Nie mniej ważny
(o ile nie najważniejszy) był sam program rozwiązujący problem n-królowych, wzbogacony
o elementy programowania równoległego w OpenMP. Program doskonale przystosowywał się do konfiguracji sprzętowej komputera,
wykorzystując najlepiej jak to tylko możliwe każdy z czterech rdzeni obu procesorów.