headerphoto

Problem n-królowych i wielowatkowosc

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.


Tabela 1. Czas przetwarzania szachownic za pomocą programu w wersji sekwencyjnej na komputerach wyposażonych w różne procesory.

Rozmiar szachownicy
Czas trwania obliczeń (w sek.)
Intel Celeron D
(2,66 GHz/CPU)
Intel Centrino Duo
(1,7 GHz/rdzeń)
2 x Xeon E5345
(2,33 GHz/rdzeń)
8x8
0,0009 0,0022 0,0007
9x9
0,0042 0,0102 0,0040
10x10
0,0208 0,0279 0,0171
11x11
0,1083 0,1250 0,0924
11x11
0,6164 0,7306 0,5380
13x13
3,7663 4,5469 3,3506
14x14
24,6324 29,5199 21,8156
15x15
170,7014 205,2777 152,1769
16x16
1255,316 1531,1732 1125,4139


Rys. 1. Czas wykonywania się programu w wersji sekwencyjnej dla szachownic o wymiarach 14x14 - 16x16 w zależności od użytego modelu procesora.

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.


Tabela 2. Czas przetwarzania szachownic za pomocą programu w wersji wielowątkowej na komputerach wyposażonych w różne procesory.

Rozmiar szachownicy
Czas trwania obliczeń (w sek.)
Intel Celeron D
(2,66 GHz/CPU)
Intel Centrino Duo
(1,7 GHz/rdzeń)
2 x Xeon E5345
(2,33 GHz/rdzeń)
8x8
0,002163 0,0015 0,00141
9x9
0,006826 0,0051 0,00417
10x10
0,029485 0,0205 0,01333
11x11
0,153654 0,1014 0,03735
11x11
0,884430 0,5756 0,15772
13x13
5,462360 3,5520 0,92152
14x14
36,057708 23,4052 5,96648
15x15
252,794104 166,8782 38,87093
16x16
1902,57728 1228,3949 278,03262


Rys. 2. Czas trwania obliczeń dla szachownic 14x14 - 16x16 w zależności od modelu procesora (wielowątkowa wersja programu).

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.