headerphoto

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

Opis środowiska

Ciekawą alternatywą dla archaicznej już konstrukcji komputerów jednoprocesorowych, są komputery oparte na architekturze wielordzeniowej. W niniejszym rozdziale przedstawiono jedną z takich maszyn. "Sercem" omawianego komputera był dwurdzeniowy procesor Intel Centrino Duo. Każdy z rdzeni procesora taktowany był zegarem o częstotliwości 1.7 GHz i miał do dyspozycji 1 GB pamięci RAM. Procesory Intel Centrino Duo, charakteryzują się doskonałymi właściwościami w dziedzinie równoległego przetwarzania danych. Technologia 45 nm oraz obwody elektryczne wewnątrz procesora wytwarzane z wykorzystaniem hafnu pozwoliły uzyskać bardzo dużą wydajność przy bardzo niskim zapotrzebowaniu na energię. Szczególnie z powodu tej ostatniej cechy, procesory Intel Centrino Duo bardzo często montowane są w laptopach. Jeden z nich posłużył jako pole do realizacji obliczeń równoległych na potrzeby rozwiązania problemu n-królowych.

Dwurdzeniowy laptop pracował pod kontrolą systemu operacyjnego Linux Ubuntu. W tym właśnie środowisku, z powodzeniem przetestowano dwie wersje programu rozwiązującego problem n-królowych (sekwencyjną i wielowątkową).

Wyniki działania programu sekwencyjnego

Testowanie programu rozwiązującego problem n-królowych rozpoczęto od przeanalizowania wersji sekwencyjnej. Uzyskane pomiary, stanowić będą dobry punkt odniesienia dla wyników z wersji wielowątkowej, opisanej w dalszej części pracy. Program uruchomiony został dla szachownic o wymiarach 8x8 - 16x16. Czas wykonywania obliczeń dla każdej kolejnej szachownicy przedstawiono w tabeli 1.

Tabela 1. Czas działania programu rozwiązującego problem n-królowych w wersji sekwencyjnej na komputerze dwurdzeniowym.

Rozmiar szachownicy
Liczba rozwiązań
Czas trwania obliczeń (w sek.)
8x8
92 0,0022
9x9
352 0,0102
10x10
724 0,0279
11x11
2 680 0,1250
12x12
14 200 0,7306
13x13
73 712 4,5469
14x14
365 596 29,5199
15x15
2 279 184 205,2777
16x16
14 772 512 1531,1732

Testowany program, specjalnie pozbawiony został elementów programowania równoległego, tak, aby sprawdzić jak komputer dwurdzeniowy poradzi sobie z przetwarzaniem programu typowo sekwencyjnego. Nie podjęto się w tym miejscu omówienia otrzymanych pomiarów, ponieważ ich prawdziwa wartość uwidacznia się dopiero po porównaniu ich z efektami działania programu w wersji wielowątkowej.

Wyniki działania programu wielowątkowego

Zdając sobie sprawę z ogromnych możliwości, jakie niesie ze sobą równoległe przetwarzanie danych na komputerach wieloprocesorowych, z tym większym zaangażowaniem przystąpiono do testowania programu rozwiązującego problem n-królowych na komputerze dwurdzeniowym. W sumie przeanalizowano 9 szachownic o wymiarach od 8x8 do 16x16. Każda z nich uruchomiona została przy udziale różnej liczby wątków. Najpierw program rozwiązywał zadanie za pomocą jednego wątku potem 2, kończąc na 15 lub nawet 16 wątkach. Przy każdorazowym uruchomieniu zmierzono czas trwania obliczeń (czyli czas poświęcony na znalezienie wszystkich możliwych ustawień królowych na danej szachownicy). Wyniki pomiarów przedstawione zostały w tabeli 2.


Tabela 2. Czas trwania obliczeń (w sek.) dla różnych szachownic w odniesieniu do liczby użytych wątków. Pomiary dla programu w wersji wielowątkowej.

Liczba wątków
ROZMIAR SZACHOWNICY
8x8
9x9
10x10
11x11
12x12
13x13
14x14
15x15
16x16
1
0,002 0,007 0,035 0,194 1,134 6,987 46,585 326,967 2447,327
2
0,001 0,006 0,021 0,103 0,585 3,794 24,881 185,288 1369,805
3
0,002 0,005 0,021 0,108 0,579 3,718 24,143 176,858 1332,435
4
0,002 0,005 0,021 0,101 0,582 3,706 23,586 172,865 1335,241
5
0,002 0,005 0,021 0,103 0,583 3,657 23,578 170,287 1252,012
6
0,002 0,006 0,025 0,102 0,580 3,666 23,482 169,902 1279,962
7
0,002 0,005 0,022 0,104 0,576 3,570 23,776 167,089 1238,740
8
0,002 0,005 0,022 0,102 0,578 3,585 23,483 169,580 1235,453
9
0,002 0,008 0,021 0,105 0,584 3,567 23,596 169,724 1262,303
10
0,002 0,009 0,022 0,102 0,584 3,577 24,209 168,498 1284,502
11
0,002 0,010 0,021 0,111 0,578 3,615 23,766 173,475 1242,652
12
0,002 0,005 0,022 0,103 0,588 3,606 23,405 168,733 1245,958
13
0,002 0,005 0,026 0,104 0,587 3,555 24,312 170,663 1271,086
14
0,002 0,006 0,021 0,103 0,594 3,552 23,416 168,606 1253,880
15
- - - - - - - 166,878 1266,358
16
- - - - - - - - 1228,395

Analizując otrzymane pomiary, szczególnie poprzez ich wizualizację dla przykładowej szachownicy 15x15 (rys. 1), Przy zastosowaniu jednego wątku zaobserwowano znaczne spowolnienie procesu przetwarzania wirtualnego drzewa przestrzeni stanów w porównaniu do sekwencyjnej wersji programu. Dla szachownicy o wymiarach 15x15 program wykonywał się o 2:02 minuty dłużej niż jego niezrównoleglony odpowiednik. Jednak wystarczyło uruchomić program dla grupy dwóch wątków, aby odnotować gwałtownie przyśpieszenie działania programu. Okazało się, że w ten sposób można zaoszczędzić kolejne 33 sekundy czasu pracy komputera. Dalsze zwiększanie ilości wątków nie przyniosło już tak spektakularnego przyśpieszenia. Można powiedzieć, że dla każdej kolejnej grupy wątków czas trwania obliczeń był porównywalny do czasu osiągniętego za pomocą dwóch wątków. Wynika z tego, że nie warto jest angażować zbyt dużej liczby wątków do pracy nad problemem n-królowych (na komputerze dwurdzeniowym).

Wiedząc już ile czasu zajmuje rozwiązanie zadania za pomocą programu wielowątkowego, warto porównać najlepsze z otrzymanych wyników z pomiarami dla wersji sekwencyjnej. Na rys. 23 przedstawiono rozkład czasu trwania obliczeń dla szachownicy 15x15 w programie sekwencyjnym i wielowątkowym (w tym drugim przypadku, wzięto pod uwagę liczbę wątków biorących udział w przetwarzaniu danych). Czas wykonywania się programu sekwencyjnego zaznaczono na wykresie grubą, czarną linią.


Rys. 1. Czas przetwarzania szachownicy 15x15 na komputerze dwuprocesorowym z wykorzystaniem sekwencyjnego i wielowątkowego modelu przetwarzania danych.

W oparciu o otrzymane wyniki, należy stwierdzić, że zrównoleglenie programu rozwiązującego problem n-królowych przyniosło zadowalające rezultaty. Co prawda przyśpieszenie programu w stosunku do wersji sekwencyjnej nie jest duże, jednak przeprowadzone badania potwierdziły, że zrównoleglanie programu sekwencyjnego nawet pod kątem maszyny dwurdzeniowej jest sensowne i ma uzasadnienie w praktyce.

Aby obliczyć dokładną wartość wspomnianego wyżej przyśpieszenia należy podzielić czas przetwarzania danej szachownicy za pomocą programu w wersji sekwencyjnej (Ts), przez podobny pomiar, tylko że dla "p" wątków w programie wielowątkowym (Tp). W wyniku otrzymamy przyśpieszenie P(p). Powyższe działanie, zapisać można następującym wzorem:

Przykładowo, aby wyznaczyć przyśpieszenie dla szachownicy 16x16 i 3 wątków należy najpierw zmierzyć czas trwania obliczeń dla programu w wersji sekwencyjnej (Ts) a następnie podzielić tę wartość przez czas uzyskany dla tej samej szachownicy, ale już w programie wielowątkowym dla grupy 3 wątków (T(3)). W wyniku otrzymamy poziom przyśpieszenia (P(3)). Przykładowy rozkład wartości przyśpieszenia dla szachownicy 16x16 przedstawiono w tabeli 3 i na rys. 2.


Tabela 3. Wartość przyśpieszenia dla szachownicy 16x16 z użyciem różnej liczby wątków.

Liczba wątków
Czas trwania obliczeń dla
szachownicy 16x16 (w sek.)
Przyśpieszenie
1
2447,3266 0,63
2
1369,8047 1,12
3
1332,4345 1,15
4
1335,2410 1,15
5
1252,0125 1,22
6
1279,9619 1,20
7
1238,7395 1,24
8
1235,4528 1,24
9
1262,3029 1,21
10
1284,5017 1,19
11
1242,6522 1,23
12
1245,9579 1,23
13
1271,0863 1,20
14
1253,8799 1,22
15
1266,3577 1,21
16
1228,3949 1,25


Rys. 2. Wykres przyśpieszenia dla szachownicy 16x16 przy użyciu różnej liczby wątków.


Analizując dane z tabeli 3 i rys. 2 można zauważyć, że po zastosowaniu grupy dwóch wątków przyśpieszenie programu kształtuje się na poziomie 1,12 w porównaniu do wersji sekwencyjnej. Przetwarzanie szachownicy przy pomocy większej liczby wątków, już tylko w śladowym stopniu przekłada się na podwyższenie współczynnika przyśpieszenia. Przy grupie 16 wątków odnotowano przyśpieszenie równe 1,25. Inaczej mówiąc, osiągnięto 25% przyśpieszenie w czasie wykonywania programu względem wersji sekwencyjnej.

Otrzymane pomiary są niezwykle obiecujące szczególnie w odniesieniu do obliczeń na znacznie silniejszych i nowszych komputerach wieloprocesorowych, których procesory składają się z dużo większej liczby rdzeni.