headerphoto

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

Opis środowiska

Środowiskiem, na którym opracowałem wielowątkową wersję programu rozwiązującego problem n-królowych, był jednoprocesorowy komputer klasy PC. Komputer składał się z procesora Intel Celeron D o częstotliwości taktowania 2,6 GHz oraz 512 MB pamięci RAM. Na komputerze zainstalowany został system operacyjny Fedora Core 6 z wersją jądra 2.6.18-1.2798.fc6. W skład systemu wchodził kompilator GCC w wersji 4.1.1, do którego doinstalowano pakiet bibliotek Omni OpenMP 1.6. Aby przyśpieszyć działanie testowanych programów, uruchamiane były w środowisku tekstowym z pominięciem trybu graficznego.

Wyniki na komputerze jednoprocesorowym - model wielowątkowy

Wielowątkowe przetwarzanie danych może odbywać się nie tylko na maszynach wieloprocesorowych, lecz także na komputerach składających się tylko z jednego procesora. W tym rozdziale przedstawione zostały wyniki działania programu rozwiązującego problem n-królowych za pomocą wielu wątków na komputerze jednoprocesorowym. Sekwencyjne przetwarzanie wirtualnego drzewa przestrzeni stanów zastąpione zostało równoległą pracą grupy wątków, które są w stanie współbieżnie analizować wiele gałęzi, w poszukiwaniu rozwiązań. Pojawia się jednak pytanie, na ile sensowne jest stosowanie tego typu rozwiązania w systemie jednoprocesorowym, w którym wielowątkowość jest niejako emulowana za pomocą specjalnych rozkazów z rodziny SSE? Odpowiedź na to pytanie można uzyskać tylko poprzez obserwację zachowania programu wielowątkowego w środowisku jednoprocesorowym. Program rozwiązujący problem n-królowych zrównoleglony został za pomocą dyrektyw OpenMP. Na potrzeby testów został uruchomiony wielokrotnie dla różnych szachownic, za każdym razem z użyciem innej liczby wątków.

Jako pierwszą przetestowano szachownicę o wymiarach 4x4 z użyciem 1 wątku. Po zakończeniu obliczeń ta sama szachownica przetworzona została za pomocą 2 wątków, następnie 3, 4, itd. Ten sam schemat działania dotyczył każdej kolejnej szachownicy. Przykładowe pomiary dokonane w trakcie przetwarzania ośmiu kolejnych szachownic (od 8x8 do 15x15) zawarto w tabeli 1.

Tabela 1. Czas wykonania programu rozwiązującego problem n-królowych w wersji wielowątkowej na komputerze jednoprocesorowym.

Liczba wątków
ROZMIAR SZACHOWNICY
8x8
9x9
10x10
11x11
12x12
13x13
14x14
15x15
1
0,00134 0,00591 0,02879 0,15379 0,87924 5,43637 35,95946 252,10524
2
0,00156 0,00613 0,02845 0,15365 0,88313 5,45625 36,02305 252,36065
3
0,00160 0,00622 0,02906 0,15305 0,88212 5,46236 36,04585 252,74757
4
0,00164 0,00627 0,02892 0,15234 0,88238 5,45895 36,02722 252,43194
5
0,00171 0,00633 0,02911 0,15224 0,88341 5,45905 36,00848 252,39729
6
0,00175 0,00640 0,02894 0,15262 0,88385 5,45635 36,02294 252,45299
7
0,00179 0,00651 0,02886 0,15160 0,88348 5,45741 36,03487 252,43132
8
0,00185 0,00643 0,02909 0,15204 0,88228 5,45445 36,02348 252,69401
9
0,00188 0,00652 0,02902 0,15208 0,88339 5,45725 36,02491 252,55694
10
0,00193 0,00658 0,02894 0,15154 0,88270 5,45876 36,04819 252,40546
11
0,00198 0,00666 0,02920 0,15203 0,88443 5,45724 36,04060 252,46329
12
0,00204 0,00665 0,02927 0,15265 0,88443 5,45997 36,04062 252,48309
13
0,00207 0,00674 0,02924 0,15284 0,88265 5,45712 36,05771 252,52928
14
0,00212 0,00676 0,02920 0,15287 0,88339 5,46017 36,01067 252,50226
15
0,00216 0,00683 0,02948 0,15258 0,88339 5,46008 36,04062 252,79410

Z otrzymanych wyników jasno wynika, że wielowątkowe przetwarzanie drzewa przestrzeni stanów na komputerze jednoprocesorowym nie ma większego sensu. Stosowanie elementów programowania równoległego, generuje dodatkowy koszt w postaci czasu, który procesor musi poświęcić na obsługę wielowątkowości. W programie rozwiązującym problem n-królowych zastosowano kilka kosztownych konstrukcji, takich jak równoległe przetwarzanie pętli for czy synchronizację wątków za pomocą dyrektywy OMP_ATOMIC. Nadzorowanie grupą wątków realizujących tego typu zadania, w nieunikniony sposób wpływa na dodatkowe obciążenie procesora. W rozpatrywanym przypadku narzut danych jest tak duży, że efektywność wielowątkowego modelu przetwarzania danych, ustępuje opisanemu wcześniej modelowi sekwencyjnemu. Po prostu program wielowątkowy wykonuje się znacznie dłużej od swojego odpowiednika w wersji sekwencyjnej. Nawet stopniowy wzrost liczby wątków biorących udział w przetwarzaniu zadania, nie wpływa w żaden sposób na prędkość działania programu. W tabeli 2 dokonano porównania najlepszej prędkości działania programu w wersji wielowątkowej z pomiarami uzyskanymi w czasie testowania tradycyjnej (sekwencyjnej) wersji tego samego programu. W wersji z OpenMP najlepszy czas uzyskano niemal zawsze dla jednego wątku. Pewne odstępstwa od tej reguły mieszczą się w granicy błędu pomiarów.


Tabela 2. Czas trwania obliczeń (w sek.) na komputerze jednoprocesorowym podczas realizacji obliczeń sekwencyjnych i wielowątkowych.

Rozmiar
szachownicy (n*n)
Czas trwania obliczeń
(model sekwencyjny)
Czas trwania obliczeń
(model wielowątkowy)
Narzut czasu
wygenerowany
przez OpenMP
8x8
0,000872 0,002163 0,001291
9x9
0,004158 0,006826 0,002668
10x10
0,020833 0,029485 0,008652
11x11
0,108324 0,153654 0,045330
12x12
0,616445 0,884430 0,267985
13x13
3,766299 5,462360 1,696061
14x14
24,632354 36,057708 11,425354
15x15
170,701428 252,794104 82,092676
16x16
1255,315929 1902,57728 647,261351

Za każdym razem porównanie wypada na korzyść sekwencyjnego modelu przetwarzania danych. Koszt nadzorowania wielowątkowości jest zbyt duży, jak na możliwości przerobowe jednego procesora. Już dla szachownicy 14x14 odnotowano, że procesor musi poświęcić ok. 11 sekund dodatkowego czasu pracy na obsługę wielowątkowości. Wartość narzutu czasowego, rośnie wraz z wzrostem wymiaru szachownicy i w efekcie dla szachownicy 16x16 kształtuje się na poziomie 647 sekund.

Reasumując, najbardziej optymalny sposób rozwiązania problemu n-królowych na komputerze jednoprocesorowym, związany jest nierozłącznie z sekwencyjnym modelem przetwarzania danych. Zauważono, że wprowadzenie do kodu programu elementów wielowątkowości powoduje drastyczny spadek wydajności algorytmu. Z tego powodu równoległy model przetwarzania danych należy pominąć w odniesieniu do tego środowiska sprzętowego. Wniosek taki był do przewidzenia, biorąc pod uwagę fakt, że w przetwarzaniu danych bierze udział tylko jeden procesor. Programowanie równoległe ma tak naprawdę sens tylko w sytuacji, gdy na komputerze zainstalowane są przynajmniej dwa procesory (lub procesor wielordzeniowy).