headerphoto

Problem n-królowych i wielowatkowość - wyniki na komputerze ośmiordzeniowym

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.

Tabela 1. Czas wykonania programu rozwiązującego problem n-królowych w wersji sekwencyjnej na komputerze ośmiordzeniowym.

Rozmiar szachownicy
Liczba rozwiązań
Czas trwania obliczeń (w sek.)
8x8
92 0,000724
9x9
352 0,004023
10x10
724 0,017171
11x11
2 680 0,092496
12x12
14 200 0,538083
13x13
73 712 3,350685
14x14
365 596 21,81584
15x15
2 279 184 152,1769
16x16
14 772 512 1125,413
17x17
95 815 104 8734,1560
18x18
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.


Tabela 2. Czas trwania obliczeń (w sek.) na komputerze ośmiordzeniowym dla różnych szachownic w zależności od liczby użytych wątków.

Liczba wątków
ROZMIAR SZACHOWNICY
10x10
11x11
12x12
13x13
14x14
15x15
16x16
17x17
18x18
1
0,02 0,014 0,80 5,01 33,24 233,94 1745,17 13646,72 111894,38
2
0,02 0,08 0,48 3,14 21,04 158,49 1248,35 9310,50 78970,21
3
0,01 0,06 0,33 2,14 14,59 101,63 747,61 6051,26 51044,55
4
0,01 0,05 0,27 1,68 11,77 382,89 637,65 5193,96 41390,27
5
0,01 0,04 0,23 1,42 9,70 68,34 531,77 3879,77 33996,91
6
0,01 0,04 0,19 1,28 8,63 58,90 450,02 3456,17 28919,05
7
0,01 0,04 0,17 1,09 7,84 54,93 388,68 3228,63 26834,43
8
0,01 0,04 0,17 0,98 6,78 49,31 400,46 3223,77 24189,32
9
0,01 0,04 0,16 0,94 6,54 47,24 332,94 2695,72 22906,92
10
0,01 0,04 0,16 0,94 6,27 46,02 346,94 2736,01 22490,62
11
0,01 0,04 0,16 0,93 6,23 44,07 343,23 2576,66 22780,80
12
0,01 0,04 0,16 0,93 6,13 43,00 303,40 2745,43 20708,21
13
0,01 0,04 0,16 0,93 5,98 40,11 283,34 2337,61 20262,59
14
0,01 0,04 0,16 0,92 5,97 38,87 278,03 2473,63 20508,91
15
0,01 0,04 0,16 0,93 5,91 40,16 286,80 2174,42 19326,26
16
- - - - - - 311,32 2216,45 19089,43
17
- - - - - - 277,35 2179,55 18381,97
18
- - - - - - - - 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.


Tabela 3. Przyśpieszenie dla szachownicy 17x17 w zależności od liczby wątków.

Liczba wątków
Czas trwania obliczeń
dla szachownicy 17x17
(w sek.)
Przyśpieszenie
1
13646,72
0,64
2
9310,50
0,94
3
6051,26
1,44
4
5193,96
1,68
5
3879,77
2,25
6
3456,17
2,53
7
3228,63
2,71
8
3223,77
2,71
9
2695,72
3,24
10
2736,01
3,19
11
2576,66
3,39
12
2745,43
3,18
13
2337,61
3,74
14
2473,63
3,53
15
2174,42
4,02
16
2216,45
3,94
17
2179,55
4,01


Rys. 1. Zmiana poziomu przyśpieszenia na komputerze ośmiordzeniowym dla szachownicy 17x17 przy użyciu różnej liczby wątków.


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ą.


Rys. 2. Czas przetwarzania szachownicy 17x17 na komputerze ośmiordzeniowym z wykorzystaniem sekwencyjnego i wielowątkowego modelu przetwarzania danych.


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.