Strategia zrównoleglania
Problem n-królowych z powodzeniem rozwiązano z wykorzystaniem trzech różnych platform sprzętowych.
Pierwsza z nich obejmowała komputery wyposażone w pojedynczy procesor wykonany w architekturze 32-bitowej.
Do drugiej zaliczono konstrukcje oparte na procesorach dwurdzeniowych, a w ostatniej kategorii znalazły się
64-bitowe maszyny dysponujące mocą aż ośmiu rdzeni. Przetwarzanie szachownic na każdym z komputerów wygenerowało
sporą ilość interesujących danych wyjściowych, począwszy od czasu trwania obliczeń, a skończywszy na poziomie
przyśpieszenia. Celem tego rozdziału jest porównanie wyników pochodzących z trzech różnych platform sprzętowych
i określenie, w jaki sposób radziły sobie one z realizacją obliczeń równoległych w trakcie intensywnej pracy nad
rozwiązaniem problemu n-królowych.
Porównanie czasu trwania obliczeń dla wersji sekwencyjnej
Rozwiązanie problemu n-królowych za pomocą sekwencyjnej wersji programu, przyniosło bardzo ciekawe wyniki,
szczególnie w odniesieniu do komputerów wielordzeniowych. Jak wiadomo komputery te przetwarzają program
sekwencyjny tylko za pomocą jednego rdzenia. Pozostałe rdzenie nie biorą czynnego udziału w procesie przetwarzania
danych. Doskonale widać to na przykładzie zwykłego komputera PC (z pojedynczym procesorem Intel Celeron D) porównanego
z bardzo silnym serwerem, pracującym na dwóch czterordzeniowych procesorach Intel Xeon E5345. Mimo ogromnych różnic
pod względem architektury i ogólnej mocy obliczeniowej, zaobserwowano, że obie maszyny potrzebują niemal tyle samo
czasu na rozwiązanie problem n-królowych. Tak niska wydajność komputera ośmiordzeniowego wynika ze wspomnianego
już wcześniej faktu, że przetwarza on programy typowo sekwencyjne za pomocą tylko jednego rdzenia. W przypadku
omawianego serwera, jeden rdzeń procesora Intel Xeon E5345 taktowany jest zegarem o częstotliwości 2,3 GHz. Jak
widać jest to bardzo zbliżona wartość do mocy zwykłego komputera PC, którego procesor pracował z częstotliwością
2,6 GHz. Z tego powodu nie mogą dziwić bardzo zbliżone wyniki obu maszyn w kwestii przetwarzania sekwencyjnej wersji
programu rozwiązującego problem n-królowych. Jeszcze gorzej w tej konkurencji wypada komputer dwurdzeniowy oparty na
procesorze Intel Centrino Duo. Każdy z jego rdzeni taktowany były zegarem o częstotliwości 1,7 GHz. Również w tym przypadku,
program sekwencyjny wykonywał się z wykorzystaniem tylko jednego rdzenia. To spowodowało, że czas trwania obliczeń przy
większych szachownicach był znacznie dłuższy w porównaniu do wyników maszyny jednoprocesorowej. Dokładne zestawienie
otrzymanych wyników przedstawiono w tabeli 1 i na rys. 1.
|
|
||||||||
(2,66 GHz/CPU) |
(1,7 GHz/rdzeń) |
(2,33 GHz/rdzeń) |
|||||||
|
0,0009 | 0,0022 | 0,0007 | ||||||
|
0,0042 | 0,0102 | 0,0040 | ||||||
|
0,0208 | 0,0279 | 0,0171 | ||||||
|
0,1083 | 0,1250 | 0,0924 | ||||||
|
0,6164 | 0,7306 | 0,5380 | ||||||
|
3,7663 | 4,5469 | 3,3506 | ||||||
|
24,6324 | 29,5199 | 21,8156 | ||||||
|
170,7014 | 205,2777 | 152,1769 | ||||||
|
1255,316 | 1531,1732 | 1125,4139 |
Analizując otrzymane wyniki, można stwierdzić jednoznacznie, że uruchamianie programu w wersji sekwencyjnej
mija się z celem w odniesieniu do nowoczesnych komputerów wielordzeniowych. Komputery tego typu dokonują
obliczeń tylko za pomocą pojedynczego rdzenia. Dochodzi więc do dosyć paradoksalnej sytuacji, kiedy program
sekwencyjny uruchomiony na nowoczesnym, ośmiordzeniowym serwerze wykonuje się z porównywalną prędkością, co
na przestarzałym komputerze PC. Aby nie dochodziło do tak rażącego marnotrawstwa mocy obliczeniowej, należy
zwrócić baczniejszą uwagę na sposoby zrównoleglania programów sekwencyjnych, specjalnie pod kątem maszyn
wieloprocesorowych. W dalszej części przedstawiłem jak każdy z
testowanych komputerów poradził sobie z tą właśnie, zupełnie odmienną wersją rozwiązania problemu ustawienia
królowych na szachownicy.
Porównanie czasu trwania obliczeń w wersji wielowątkowej
Pełne wykorzystanie zasobów komputera wielordzeniowego możliwe jest tylko poprzez zrównoleglenie kodu źródłowego
i uruchomienie skompilowanego programu
w trybie wielowątkowym. Takie kroki zostały poczynione z myślą o bardziej optymalnym rozwiązaniu problemu n-królowych
na komputerach wieloprocesorowych. Wielowątkową wersję programu przetestowano także na komputerze jednoprocesorowym,
jednak jak już dowiedziono z wcześniejszych analiz, komputer "uzbrojony" w tylko jeden procesor nie radził sobie
dobrze przy jawnym zrównoleglaniu kodu za pomocą dyrektyw OpenMP. Zupełnie inaczej sytuacja przedstawiała się w
"obozie" komputerów wielordzeniowych,
w końcu miały one szansę wykazać się swoimi możliwościami w dziedzinie równoległego przetwarzania danych. Wyniki
tego ciekawego eksperymentu przedstawione zostały
w ramach zbiorczej tabeli, zawierającej najlepsze wyniki uzyskane w czasie przetwarzania szachownic o wymiarach
8x8 - 16x16, przez program wielowątkowy.
|
|
||||||||
(2,66 GHz/CPU) |
(1,7 GHz/rdzeń) |
(2,33 GHz/rdzeń) |
|||||||
|
0,002163 | 0,0015 | 0,00141 | ||||||
|
0,006826 | 0,0051 | 0,00417 | ||||||
|
0,029485 | 0,0205 | 0,01333 | ||||||
|
0,153654 | 0,1014 | 0,03735 | ||||||
|
0,884430 | 0,5756 | 0,15772 | ||||||
|
5,462360 | 3,5520 | 0,92152 | ||||||
|
36,057708 | 23,4052 | 5,96648 | ||||||
|
252,794104 | 166,8782 | 38,87093 | ||||||
|
1902,57728 | 1228,3949 | 278,03262 |
Komputery wielordzeniowe doskonale poradziły sobie z przetwarzaniem programu wielowątkowego. Maszyna dwurdzeniowa
przeanalizowała przykładową szachownicę 16x16 szybciej o 11 minut i 18 sekund w porównaniu do wyniku uzyskanego na
maszynie jednoprocesorowej. Jeszcze lepszy czas uzyskano w trakcie testowania programu na komputerze ośmiordzeniowym.
Długość trwania obliczeń dla tej samej szachownicy mieściła się w granicach 4 minut (to o 27 minut krócej niż na
komputerze jednoprocesorowym).
Należy zauważyć, że czas rozwiązywania problemu n-królowych w wersji wielowątkowej na komputerze jednoprocesorowym
był dłuższy w porównaniu do wersji sekwencyjnej. Ten spadek wydajności programu, spowodowany był przez dodatkowy
narzut pracy związany z obsługą wielowątkowości. Oszacowano, że na komputerze jednoprocesorowym program wielowątkowy
wykonywał się średnio o 35% wolniej dla każdej z szachownic w porównaniu do wersji niezrównoleglonej.