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.
|
|
||||||||
|
|
|
|
|
|
|
|
||
|
0,00134 | 0,00591 | 0,02879 | 0,15379 | 0,87924 | 5,43637 | 35,95946 | 252,10524 | |
|
0,00156 | 0,00613 | 0,02845 | 0,15365 | 0,88313 | 5,45625 | 36,02305 | 252,36065 | |
|
0,00160 | 0,00622 | 0,02906 | 0,15305 | 0,88212 | 5,46236 | 36,04585 | 252,74757 | |
|
0,00164 | 0,00627 | 0,02892 | 0,15234 | 0,88238 | 5,45895 | 36,02722 | 252,43194 | |
|
0,00171 | 0,00633 | 0,02911 | 0,15224 | 0,88341 | 5,45905 | 36,00848 | 252,39729 | |
|
0,00175 | 0,00640 | 0,02894 | 0,15262 | 0,88385 | 5,45635 | 36,02294 | 252,45299 | |
|
0,00179 | 0,00651 | 0,02886 | 0,15160 | 0,88348 | 5,45741 | 36,03487 | 252,43132 | |
|
0,00185 | 0,00643 | 0,02909 | 0,15204 | 0,88228 | 5,45445 | 36,02348 | 252,69401 | |
|
0,00188 | 0,00652 | 0,02902 | 0,15208 | 0,88339 | 5,45725 | 36,02491 | 252,55694 | |
|
0,00193 | 0,00658 | 0,02894 | 0,15154 | 0,88270 | 5,45876 | 36,04819 | 252,40546 | |
|
0,00198 | 0,00666 | 0,02920 | 0,15203 | 0,88443 | 5,45724 | 36,04060 | 252,46329 | |
|
0,00204 | 0,00665 | 0,02927 | 0,15265 | 0,88443 | 5,45997 | 36,04062 | 252,48309 | |
|
0,00207 | 0,00674 | 0,02924 | 0,15284 | 0,88265 | 5,45712 | 36,05771 | 252,52928 | |
|
0,00212 | 0,00676 | 0,02920 | 0,15287 | 0,88339 | 5,46017 | 36,01067 | 252,50226 | |
|
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.
szachownicy (n*n) |
(model sekwencyjny) |
(model wielowątkowy) |
wygenerowany przez OpenMP |
|
0,000872 | 0,002163 | 0,001291 |
|
0,004158 | 0,006826 | 0,002668 |
|
0,020833 | 0,029485 | 0,008652 |
|
0,108324 | 0,153654 | 0,045330 |
|
0,616445 | 0,884430 | 0,267985 |
|
3,766299 | 5,462360 | 1,696061 |
|
24,632354 | 36,057708 | 11,425354 |
|
170,701428 | 252,794104 | 82,092676 |
|
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).