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.
|
|
|
|
92 | 0,0022 |
|
352 | 0,0102 |
|
724 | 0,0279 |
|
2 680 | 0,1250 |
|
14 200 | 0,7306 |
|
73 712 | 4,5469 |
|
365 596 | 29,5199 |
|
2 279 184 | 205,2777 |
|
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.
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
0,002 | 0,007 | 0,035 | 0,194 | 1,134 | 6,987 | 46,585 | 326,967 | 2447,327 |
|
0,001 | 0,006 | 0,021 | 0,103 | 0,585 | 3,794 | 24,881 | 185,288 | 1369,805 |
|
0,002 | 0,005 | 0,021 | 0,108 | 0,579 | 3,718 | 24,143 | 176,858 | 1332,435 |
|
0,002 | 0,005 | 0,021 | 0,101 | 0,582 | 3,706 | 23,586 | 172,865 | 1335,241 |
|
0,002 | 0,005 | 0,021 | 0,103 | 0,583 | 3,657 | 23,578 | 170,287 | 1252,012 |
|
0,002 | 0,006 | 0,025 | 0,102 | 0,580 | 3,666 | 23,482 | 169,902 | 1279,962 |
|
0,002 | 0,005 | 0,022 | 0,104 | 0,576 | 3,570 | 23,776 | 167,089 | 1238,740 |
|
0,002 | 0,005 | 0,022 | 0,102 | 0,578 | 3,585 | 23,483 | 169,580 | 1235,453 |
|
0,002 | 0,008 | 0,021 | 0,105 | 0,584 | 3,567 | 23,596 | 169,724 | 1262,303 |
|
0,002 | 0,009 | 0,022 | 0,102 | 0,584 | 3,577 | 24,209 | 168,498 | 1284,502 |
|
0,002 | 0,010 | 0,021 | 0,111 | 0,578 | 3,615 | 23,766 | 173,475 | 1242,652 |
|
0,002 | 0,005 | 0,022 | 0,103 | 0,588 | 3,606 | 23,405 | 168,733 | 1245,958 |
|
0,002 | 0,005 | 0,026 | 0,104 | 0,587 | 3,555 | 24,312 | 170,663 | 1271,086 |
|
0,002 | 0,006 | 0,021 | 0,103 | 0,594 | 3,552 | 23,416 | 168,606 | 1253,880 |
|
- | - | - | - | - | - | - | 166,878 | 1266,358 |
|
- | - | - | - | - | - | - | - | 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ą.
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.
|
szachownicy 16x16 (w sek.) |
|
|
2447,3266 | 0,63 |
|
1369,8047 | 1,12 |
|
1332,4345 | 1,15 |
|
1335,2410 | 1,15 |
|
1252,0125 | 1,22 |
|
1279,9619 | 1,20 |
|
1238,7395 | 1,24 |
|
1235,4528 | 1,24 |
|
1262,3029 | 1,21 |
|
1284,5017 | 1,19 |
|
1242,6522 | 1,23 |
|
1245,9579 | 1,23 |
|
1271,0863 | 1,20 |
|
1253,8799 | 1,22 |
|
1266,3577 | 1,21 |
|
1228,3949 | 1,25 |
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.