Programowanie równoległe i rozproszone

Projekt

Równoległy Algorytm Genetyczny

Autorzy:
Mateusz Macięga
Piotr Gębala

27 stycznia 2015

Wstęp

Obliczenia równoległe to forma wykonywania obliczeń, w której wiele instrukcji

jest wykonywanych jednocześnie. Taka forma przetwarzania danych była wykorzystywana
przez wiele lat, głównie przy wykorzystaniu superkomputerów, a szczególne zainteresowa-
nie zyskała w ostatnich latach, z uwagi na fizyczne ograniczenia uniemożliwiające dalsze
zwiększanie częstotliwości taktowania procesorów. Obliczenia równoległe stały się domi-
nującym wzorcem w architekturze komputerowej, głównie za sprawą upowszechnienia pro-
cesorów wielordzeniowych.

Dokument ten pełni rolę dokumentacji do projektu zaliczeniowego z przedmiotu

„Programowanie równoległe i rozproszone”i zawiera wstęp teoretyczny do zagadnień po-
ruszanych w programie, szczegółowy opis wykorzystanych technologi i funkcji oraz wyniki
pomiarów wydajności.

1 Cel projektu

Celem projektu było zaimplementowanie równoległego algorytmu genetycznego, któ-

rego zadaniem jest wyszukiwanie lokalnego ekstremum funkcji w zadanym przedziale (w
naszym przypadku jest to wartość maksymalna, nic jednak nie stoi na przeszkodzie, aby
zmienić to w prosty sposób). W aplikacji zostały wykorzystane technologie MPI (w celu
rozproszenia danych pomiędzy maszynami) oraz OpenMP (do zrównoleglenia pracy w
obrębie pojedynczej maszyny). Dzięki zastosowaniu wyżej wymienionych technik mamy
nadzieję na znaczne przyspieszenie wyszukiwania rozwiązania.

2 Algorytmy genetyczne

Algorytmy genetyczne są próbą symulowania w pamięci komputera populacji ja-

kiegoś gatunku. Na taką populację składają się dziesiątki, setki, tysiące pojedynczych
osobników. Osobniki te krzyżują się między sobą, mogą również następować jakieś samo-
istne zmiany w strukturze pojedynczego osobnika (tzw. mutacja). W wyniku krzyżowania
i mutacji powstają nowe osobniki. Ze względu na fakt, że populacja ma swój z góry na-
rzucony maksymalny rozmiar część osobników należy z niej usunąć (ten krok nazywany
jest selekcją). Cały ten proces (krzyżowanie, mutacja, selekcja) może być powtarzany w
nieskończoność.

Algorytmy genetyczne stosowane są do problemów NP-trudnych (np. Problem ko-

miwojażera: komiwojażer ma do odwiedzenia n miast, wszystkie są ze sobą połączone,
oznacza to że z każdego miasta komiwojażer może dojechać do wszystkich pozostałych, a
więc dodanie jednego miasta powoduje dwukrotne zwiększenie czasu obliczeń).

W tym przypadku każdy osobnik pamięta jedną trasę, krzyżowanie polega na wy-

mianie elementów tras, mutacja pozwala na wymianę miast w obrębie jednego osobnika, a
selekcje odrzuca osobniki z najgorszą trasą. Niestety algorytmy genetyczne są tylko heu-
rystyką. Oznacza to, że otrzymane rozwiązania nie zawsze będą najlepszymi możliwymi.
W zamian za to otrzymujemy rozwiązania bardzo dobre w rozsądnym czasie.

1

2.1 Losowanie populacji

W tym miejscu należy ustalić jak wielka będzie tworzona populacja. Jeśli populacja

będzie zawierała zbyt mało osobników to algorytm może zatrzymać się w jakimś minimum
lokalnym (gdy jakieś niezłe, ale nie najlepsze rozwiązanie zdominuje całą populację). Z
drugiej strony zbyt duża liczebność populacji zmniejsza szybkość działania algorytmu. Po
ustaleniu wielkości populacji należy stworzyć wszystkie osobniki. Ze względu na fakt, że
początkowa populacja powinna być jak najbardziej różnorodna każdy osobnik powinien
być tworzony całkowicie losowo.

2.2 Ocena osobników

W tym kroku badana jest jakość poszczególnych osobników. W zależności od ro-

dzaju problemu różne są funkcje sprawdzające przystosowanie osobników. W przypadku
ekstremum funkcji jakością jest po prostu wartość funkcji w zadanym „x”. W przypadku
rozwiązywania problemu komiwojażera jest to długość trasy jaka jest reprezentowana
przez danego osobnika.

2.3 Selekcja

Krok ten jest esencją całej genetyki. W tym miejscu tworzona jest nowa popula-

cja na podstawie już istniejącej. W zależności od wartości funkcji oceny (obliczanej w
poprzednim kroku) dany osobnik ma większe (gdy jest „dobry”) lub mniejsze (gdy jest
„słaby”) szanse na znalezienie się w kolejnym pokoleniu. Istnieje kilka sposobów obliczania
„szansy”poszczególnych osobników:

2.3.1 Ruletka

Polega na n krotnym losowaniu (n - liczba osobników w populacji) ze starej populacji

osobników, które zostaną przepisane do nowej populacji. Oczywiście wszystkie osobniki
mają różne prawdopodobieństwa wylosowania.

2.3.2 Ranking liniowy

Selekcja tą metodą jest bardzo podobna do selekcji metodą koła ruletki. Modyfika-

cja polega jedynie na zmianie funkcji określającej prawdopodobieństwo wyboru danego
osobnika. Przed przystąpieniem do tej selekcji należy nadać każdemu z osobników pewną
wartość (przystosowanie) zależną od jego położenia na liście posortowanej względem war-
tości funkcji oceny.

2.3.3 Turniej

Metoda jest zupełnie różna od powyższych i polega na losowym wyborze z całej po-

pulacji kilku osobników (jest to tzw. grupa turniejowa), a później z tej grupy wybierany
jest osobnik najlepiej przystosowany i on przepisywany jest do nowo tworzonej popu-
lacji. Losowanie grup turniejowych oraz wybieranie z nich najlepszego osobnika należy
powtórzyć aż do utworzenia całej nowej populacji.

2

2.4 Krzyżowanie

Zadaniem kroku krzyżowania jest wymiana „materiału genetycznego”pomiędzy dwoma

rozwiązaniami w populacji. W wyniku krzyżowania na podstawie dwóch rozwiązań (ro-
dzice) tworzone są dwa nowe osobniki (dzieci). Po wykonaniu krzyżowania dzieci zastępują
w populacji rodziców. Oczywiście w tym kroku nie wszystkie rozwiązania muszą się ze
sobą krzyżować. Liczbę krzyżowań określa tzw. współczynnik krzyżowania (o wartości
od 0 do 1), który pokazuje jaka liczba osobników powinna być w jednej iteracji skrzyżo-
wana, bądź określa prawdopodobieństwo z jakim każde rozwiązanie może wziąć udział w
krzyżowaniu.

2.5 Mutacja

Mutacja podobnie jak krzyżowanie zapewnia dodawanie do populacji nowych osob-

ników. Jednak w odróżnieniu od krzyżowania w przypadku mutacji modyfikowany jest
jeden a nie dwa osobniki. Podobnie jak w przypadku krzyżowania istnieje tzw. współ-
czynnik mutacji, który określa ile osobników będzie w jednej iteracji ulegało mutacji.

2.6 Powrót do oceny osobników

W zasadzie algorytm genetyczny powinien działać w nieskończoność jednak dobrze

jest zapewnić jakieś rozsądne wyjście z pętli. Może to być np. pewna liczba iteracji, war-
tość osiągniętego najlepszego rozwiązania, czas, brak poprawy wyniku przez pewną ilość
iteracji lub inne w zależności od rodzaju zadania.

Sekwencyjne algorytmy genetyczne przynoszą bardzo dobre wyniki w wielu różnych

dziedzinach nauki. Istnieją jednak sytuacje, w których sekwencyjne podejście nie jest
wystarczające np. jeżeli poszukiwanie rozwiązania trwa zbyt długo. W celu przyspieszenia
obliczeń można zastosować zrównoleglenie algorytmu. W naszym przypadku proces ten
został zaimplementowany poprzez rozproszenie populacji pomiędzy procesy (MPI) oraz
zrównoleglenie pętli szukających rozwiązania (OpenMP).

3

3 Metody zrównoleglenia algorytmu

3.1 MPI - Message Passing Interface

„Protokół komunikacyjny będący standardem przesyłania komunikatów pomiędzy

procesami programów równoległych działających na jednym lub więcej komputerach. In-
terfejs ten wraz z protokołem oraz semantyką specyfikuje, jak jego elementy winny się
zachowywać w dowolnej implementacji. Celami MPI są wysoka jakość, skalowalność oraz
przenośność. MPI jest dominującym modelem wykorzystywanym obecnie w klastrach
komputerów oraz superkomputerach.”

W przypadku algorytmu genetycznego MPI zostało wykorzystane do podzielenia

populacji na podpopulacje, a następnie przesłanie ich do osobnych procesów, w których
proces wyszukiwania osobników będzie się wykonywał równolegle.

Zastosowany został model Master-Slave, w którym jeden proces (Master) dzieli dane

i rozsyła je do procesów Slave, który wykonują obliczenia.

Następnie wyniki częściowe z procesów Slave zostają redukowane do procesu Master

i tym sposobem otrzymujemy najlepszy wyniki.

Rysunek 1: Proces master rozdziela zadania pomiędzy procesy slave

Rysunek 2: Proces master redukuje wynik z procesów slave

3.2 OpenMP - Open Multi-Processing

„Wieloplatformowy interfejs programowania aplikacji (API) umożliwiający tworze-

nie programów komputerowych dla systemów wieloprocesorowych z pamięcią dzieloną.
Może być wykorzystywany w językach programowania C, C++ i Fortran na wielu archi-
tekturach, m.in. Unix i Microsoft Windows. Składa się ze zbioru dyrektyw kompilatora,
bibliotek oraz zmiennych środowiskowych mających wpływ na sposób wykonywania się
programu.”

MPI służy do przesyłania komunikatów między procesami, nie wspiera jednak wie-

lowątkowości. Aby ją zapewnić zastosowaliśmy interfejs OpenMP. Zrównolegleniu uległy
funkcje odpowiedzialne za wykonywanie kolejnych etapów algorytmu genetycznego.

4

4 Szczegółowy opis programu

W celu wykonania zadania stworzyliśmy program sekwencyjny, który realizuje ko-

lejne etapy algorytmu genetycznego, a następnie zrównolegliliśmy go przy pomocy MPI i
OpenMP. Aplikacja składa się z programu głównego oraz kilku funkcji. Ważniejsze bloki
kodu zostały opisane poniżej.

4.1 Funkcja celu

1

d o u b l e

f c e l u

(

d o u b l e

x

) {

2

r e t u r n

s i n

( 2 ∗

x

) +

pow

(

c o s

( 4 ∗

x

) , 3 ) ;

3

}

Jest to funkcja, dla której nasz algorytm liczy wartość maksymalną w zadanych

przedziale.

y = sin(2x) + cos(4x)

Rysunek 3: Wykres funkcji celu

4.2 Program główny

Kiedy wiadomo już jak wygląda nasza funkcja można przejść do wyszukiwania roz-

wiązania. Proces ten zaimplementowany jest w programie głównym, który składa się z z
trzech zasadniczych części: zainicjowania środowiska, wykonania obliczeń oraz zwolnienia
zasobów.

Uruchamiamy środowisko MPI (MPI Init thread), pobieramy podstawowe informa-

cje takie jak numer procesu (MPI Comm rank) i liczba procesów (MPI Comm size).

1

SAFE CALL

(

M P I I n i t t h r e a d

(&

a r g c

, &

argv

,

MPI THREAD FUNNELED

, &

p r o v i d e d

) , 0 ) ;

2

3

i f

(

p r o v i d e d

<

MPI THREAD FUNNELED

)

4

{

5

SAFE CALL

(

MPI Abort

(

MPI COMM WORLD

, 1 ) , 0 ) ;

6

e x i t

(

EXIT FAILURE

) ;

7

}

5

8

9

SAFE CALL

(

MPI Comm rank

(

MPI COMM WORLD

,&

t a s k I d

) , 0 ) ;

10

SAFE CALL

(

MPI Comm size

(

MPI COMM WORLD

,&

nTasks

) ,

t a s k I d

) ;

11

SAFE CALL

(

M P I C o m m s e t e r r h a n d l e r

(

MPI COMM WORLD

,

MPI ERRORS RETURN

) ,

t a s k I d

) ;

12

i f

(

t a s k I d

== 0 ) {

13

i f

(

nTasks

< 2 ) {

14

c o u t

<<

” N a l e z y uruchomic p r z y n a j m n i e j dwa p r o c e s y ) . ”

<<

e n d l

;

15

e x i t

(

EXIT FAILURE

) ;

16

}

17

}

Po inicjacji zmiennych losowana jest nowa populacja, obliczany jest krok oraz przy-

gotowywana jest tablica z osobnikami podzielonymi między procesy. Podział oraz prze-
syłanie informacji o ilości osobników dla każdego procesu wykonywane jest przez proces
macierzysty.

1

i f

(

t a s k I d

== 0 ) {

2

sendCounts

=

new i n t

[

nTasks

] ;

3

d i s p l s

=

new i n t

[

nTasks

] ;

4

p r z y g o t u j t a b l i c e

(

P

,

nTasks

,

sendCounts

,

d i s p l s

) ;

5

6

f o r

(

i n t

i

=0;

i

<

nTasks

;

i

++) {

7

c o u t

<<

” P r o c e s ”

<<

i

<<

” osobnikow ”

<<

sendCounts

[

i

] <<

e n d l

;

8

}

9

}

1

SAFE CALL

(

M P I S c a t t e r

(

sendCounts

, 1 ,

MPI INT

, &

l i c z b a O s o b n i k o w

, 1 ,

MPI INT

,

0 ,

MPI COMM WORLD

) ,

t a s k I d

) ;

Przed wysłaniem podpopulacji do procesów slave musimy stworzyć nowy typ danych,

który pozwoli na przechowywanie potrzebnych nam danych. Wygląda to następująco:

1

MPI Datatype typ

,

podtyp

;

2

3

SAFE CALL

(

M P I T y p e c r e a t e s u b a r r a y

( 2 ,

r o z m i a r o r y g i n a l n y

,

podrozmiar

,

p u n k t y p o c z a t k o w e

,

MPI ORDER C

,

MPI INT

, &

typ

) ,

t a s k I d

) ;

4

5

SAFE CALL

(

M P I T y p e c r e a t e r e s i z e d

(

typ

, 0 ,

N

∗

l i c z b a b i t o w

∗

s i z e o f

(

i n t

) , &

podtyp

) ,

t a s k I d

) ;

6

7

SAFE CALL

(

MPI Type commit

(&

podtyp

) ,

t a s k I d

) ;

Tak przygotowane dane możemy wysłać do procesów. Z racji tego, że rozmiar danych

może być różny, wykorzystana została funkcja Scatterv.

1

SAFE CALL

(

M P I S c a t t e r v

(&(

t a b l i c a

[ 0 ] [ 0 ] ) ,

sendCounts

,

d i s p l s

,

podtyp

,

2

&(

o s o b n i k i

[ 0 ] [ 0 ] ) ,

l i c z b a O s o b n i k o w

∗

N

∗

l i c z b a b i t o w

,

MPI INT

, 0 ,

MPI COMM WORLD

) ,

t a s k I d

) ;

Po powyższej operacji można przystąpić do obliczeń. Uruchamiamy pomiar czasu,

a następnie wszystkie funkcje algorytmu genetycznego odpowiedzialne kolejno za: rozko-
dowanie i ocenę populacji, metodę ruletki, mutację oraz krzyżowanie.

1

SAFE CALL

(

M P I B a r r i e r

(

MPI COMM WORLD

) ,

t a s k I d

) ;

2

i n i t T i m e

=

MPI Wtime

( ) ;

6

1

i f

(

t a s k I d

!= 0 ) {

2

3

d o u b l e

∗∗

t a b r o z

;

4

t a b r o z

=

r o z k o d u j

(

o s o b n i k i

,

l i c z b a O s o b n i k o w

,

N

,

l i c z b a b i t o w

,

dx2

,

a

) ;

5

6

d o u b l e

∗∗

w c t a b

;

7

i n t

n r w i e r s z a m a x

;

8

w c t a b

=

o c e n a p o p u l a c j i

(

t a b r o z

,

l i c z b a O s o b n i k o w

, &

n r w i e r s z a m a x

) ;

9

10

f o r

(

i n t

h

=0;

h

<

H

;

h

++) {

11

R u l e t k a

(

o s o b n i k i

,

wc tab

,

l i c z b a O s o b n i k o w

,

N

,

l i c z b a b i t o w

) ;

12

13

Krzyzowanie

(

o s o b n i k i

,

l i c z b a O s o b n i k o w

,

N

,

l i c z b a b i t o w

,

Pk

) ;

14

15

Mutacja

(

o s o b n i k i

,

l i c z b a O s o b n i k o w

,

N

,

l i c z b a b i t o w

,

Pm

) ;

16

17

t a b r o z

=

r o z k o d u j

(

o s o b n i k i

,

l i c z b a O s o b n i k o w

,

N

,

l i c z b a b i t o w

,

dx2

,

a

) ;

18

19

w c t a b

=

o c e n a p o p u l a c j i

(

t a b r o z

,

l i c z b a O s o b n i k o w

, &

n r w i e r s z a m a x

) ;

20

21

i f

(

n a j l w a r t

<

w c t a b

[

n r w i e r s z a m a x

] [ 0 ] ) {

22

n a j l w a r t

=

w c t a b

[

n r w i e r s z a m a x

] [ 0 ] ;

23

f o r

(

i n t

i

=0;

i

<

N

;

i

++) {

24

n a j l o s o b n i k

[

i

] =

t a b r o z

[

n r w i e r s z a m a x

] [

i

] ;

25

}

26

}

27

}

28

}

Po odnalezieniu najlepszych osobników w lokalnych populacjach, wykorzystujemy

funkcję MPI Reduce w celu wybrania najlepszego rozwiązani globalnego. Następnie za-
trzymujemy pomiar czasu u ustawiamy barierę dla procesów.

1

SAFE CALL

(

MPI Reduce

(&

n a j l w a r t

, &

g l o b a l n a n a j l w a r t o s c

, 1 ,

MPI DOUBLE

,

MPI MAX

, 0 ,

MPI COMM WORLD

) ,

t a s k I d

) ;

2

3

SAFE CALL

(

M P I B a r r i e r

(

MPI COMM WORLD

) ,

t a s k I d

) ;

4

t o t a l T i m e

=

MPI Wtime

( ) −

i n i t T i m e

;

Kiedy mamy już rozwiązanie, zwalniamy niepotrzebną pamięć oraz zamykamy śro-

dowisko MPI.

1

SAFE CALL

(

M P I F i n a l i z e

( ) ,

t a s k I d

) ;

W programie głównym został wykorzystany interfejs MPI oraz funkcje odpowie-

dzialne za znalezienie rozwiązania. Ich opis znajduje się poniżej.

7

4.3 Przygotowanie tablicy

Funkcja odpowiedzialna za przygotowanie wektorow wykorzystywanych podczas roz-

sylania danych (osobnikow) po miedzy procesami. Dokonanie podzialu wszystkich osob-
nikow rownomiernie pomiedzy wszystkimi pracujacymi procesami.

Argumenty:

• nCount - liczba osobnikow w populacji,

• nTastks - liczba procesow do ktorych, zostana rozeslane liczby,

• sendCounts[] - wektor zawierajacy informacje ile liczb ma zostac przeslanych do

kazdego procesu (rozmiar wektora zależny od rozmiaru grupy),

• displs[] - element i-ty określa przemieszczenie danych wychodzących do procesu i-

tego (rozmiar wektora zależny od rozmiaru grupy).

1

v o i d

p r z y g o t u j t a b l i c e

(

i n t

nCount

,

i n t

nTasks

,

i n t

sendCounts

[ ] ,

i n t

d i s p l s

[ ] ) {

2

sendCounts

[ 0 ] = 0 ;

3

d i s p l s

[ 0 ] = 0 ;

4

5

i n t

nMin

=

nCount

/ (

nTasks

−1) ;

6

i n t

nExtra

=

nCount

%(

nTasks

−1) ;

7

i n t

k

= 0 ;

8

f o r

(

i n t

i

=0;

i

<(

nTasks

−1) ;

i

++) {

9

i f

(

i

<

nExtra

)

10

sendCounts

[

i

+1] =

nMin

+1;

11

e l s e

12

sendCounts

[

i

+1] =

nMin

;

13

14

d i s p l s

[

i

+1] =

k

;

15

k

=

k

+

sendCounts

[

i

+ 1 ] ;

16

}

17

}

4.4 Losowanie populacji

Funkcja odpowiedzialna za wygenerowanie nowej populacji. Nowa populacja jest w

pełni losowa, zostaje wypełniona wylosowanymi wartościami (1 lub 0). Tablica populacji
zaalokowana jest w sposób ciągły.

Argumenty:

• P - liczba osobników populacji,

• N - liczba zmiennyc funkcji,

• G - liczba bitów potrzebnych do zakodowania jednego osobnika.

Zwracana wartość:

• macierz z populacją zakodowaną w bitach

8

1

i n t

∗∗

pop

(

i n t

P

,

i n t

N

,

i n t

G

) {

2

i n t

∗

dane

=

new i n t

[

P

∗

N

∗

G

] ;

3

4

i n t

∗∗

t a b

=

new i n t

∗ [

P

] ;

5

f o r

(

i n t

i

= 0 ;

i

<

P

; ++

i

) {

6

t a b

[

i

] = &(

dane

[

N

∗

G

∗

i

] ) ;

7

}

8

f o r

(

i n t

i

=0;

i

<

P

;

i

++)

9

f o r

(

i n t

j

=0;

j

<

N

∗

G

;

j

++)

10

t a b

[

i

] [

j

] =

rand

( ) % 2 ;

11

r e t u r n

t a b

;

12

}

4.5 Rozkodowanie populacji

Funkcja odpowiedzialna za rozkodowanie osobnika z postaci bitowej na postać liczby.

Argumenty:

• pop - tablica populacji,

• P - liczba osobników populacji,

• N - liczba zmiennych funkcji,

• G - liczba bitów,

• dx - krok,

• a - granica dolna zakresu.

Zwracana wartość:

• macierz z rozkodowaną populacją

1

d o u b l e

∗∗

r o z k o d u j

(

i n t

∗∗

pop

,

i n t

P

,

i n t

N

,

i n t

G

,

d o u b l e

dx

,

d o u b l e

a

) {

2

d o u b l e

∗∗

t a b

=

new d o u b l e

∗ [

P

] ;

3

f o r

(

i n t

i

= 0 ;

i

<

P

;

i

++) {

4

t a b

[

i

] =

new d o u b l e

[

N

] ;

5

}

6

f o r

(

i n t

i

=0;

i

<

P

;

i

++)

7

f o r

(

i n t

j

=0;

j

<

N

;

j

++)

8

t a b

[

i

] [

j

] = 0 ;

9

i n t

waga

;

10

f o r

(

i n t

i

= 0 ;

i

<

P

;

i

++) {

11

f o r

(

i n t

k

= 1 ;

k

<=

N

;

k

++) {

12

waga

=0;

13

f o r

(

i n t

j

=(

k

∗

G

) −1;

j

>=

G

∗ (

k

−1) ;

j

−−) {

14

t a b

[

i

] [

k

−1] +=

pow

( 2 , (

d o u b l e

)

waga

) ∗

pop

[

i

] [

j

] ;

15

waga

++;

16

}

17

t a b

[

i

] [

k

−1] =

t a b

[

i

] [

k

−1] ∗

dx

+

a

;

18

}

19

}

20

r e t u r n

t a b

;

21

}

9

4.6 Ocena populacji

Funkcja odpowiedzialna za ocenę całej populacji. Dla każdego osobnika wyliczamy

wartość funkcji, wartości te zostają zapisane do macierzy. Z całej populacji wyszukujemy
element dla którego wartość funkcji jest największa i zapisujemy ją do odpowiedniej.

Argumenty:

• tab rozk - rozkodowana populacja,

• P - liczba osobników populacji,

• nr wiersza max [out] - zmienna do zapisania numer wiersza z wartością funkcji celu

największą.

Zwracana wartość:

• macierz z wartościami funkcji celu dla każdego osobnika populacji.

1

d o u b l e

∗∗

o c e n a p o p u l a c j i

(

d o u b l e

∗∗

t a b r o z k

,

i n t

P

,

i n t

∗

n r w i e r s z a m a x

) {

2

d o u b l e

∗∗

t a b

=

new d o u b l e

∗ [

P

] ;

3

f o r

(

i n t

i

= 0 ;

i

<

P

;

i

++) {

4

t a b

[

i

] =

new d o u b l e

[ 1 ] ;

5

}

6

d o u b l e

max

=

f c e l u

(

t a b r o z k

[ 0 ] [ 0 ] ) ;

7

∗

n r w i e r s z a m a x

= 0 ;

8

f o r

(

i n t

i

=0;

i

<

P

;

i

++) {

9

t a b

[

i

] [ 0 ] =

f c e l u

(

t a b r o z k

[

i

] [ 0 ] ) ;

10

i f

(

t a b

[

i

] [ 0 ] >

max

)

11

∗

n r w i e r s z a m a x

=

i

;

12

}

13

r e t u r n

t a b

;

14

}

4.7 Metoda selekcji: Ruletka

Metoda selekcji, odpowiedzialna za wyselekcjonowanie najlepszych osobników w pro-

cesie tworzenia kolejne populacji. Metoda ruletki polega na zbudowaniu wirtualnego koła,
którego wycinki odpowiadają poszczególnym osobnikom. Im lepszy osobnik, tym większy
wycinek koła zajmuje. Rozmiar wycinka zależy od wartości funkcji celu dla danego osob-
nika. W takim układzie prawdopodobieństwo, że lepszy osobnik zostanie wybrany jako
rodzic, jest większe.

Argumenty:

• pop - zakodowana populacja,

• wc tab - wartości funkcji celu populacji,

• P - liczba osobników populacji,

• N - liczba zmiennych funkcji,

• G - liczba bitów potrzebnych do zakodowania osobnika.

10

Poszukiwanie wartości maksymalnej w tablicy z wartościami funkcji oraz sumowanie

elementów tablicy:

1

v o i d

R u l e t k a

(

i n t

∗∗

pop

,

d o u b l e

∗∗

wc tab

,

i n t

P

,

i n t

N

,

i n t

G

) {

2

3

#

pragma omp p a r a l l e l

f o r

d e f a u l t

(

none

)

f i r s t p r i v a t e

(

P

)

s h a r e d

(

wc tab

,

min

)

r e d u c t i o n

(+ :

suma wc tab

)

n u m t hr e a ds

(

n t h r e a d s

)

4

f o r

(

i n t

i

=0;

i

<

P

;

i

++) {

5

i f

(

w c t a b

[

i

] [ 0 ] <

min

)

6

min

=

w c t a b

[

i

] [ 0 ] ;

7

suma wc tab

+=

w c t a b

[

i

] [ 0 ] ;

8

}

9

10

i f

(

min

>=0) {

11

#

pragma omp p a r a l l e l

f o r

d e f a u l t

(

none

)

f i r s t p r i v a t e

(

P

)

s h a r e d

(

wc tab

,

tab

,

suma wc tab

,

min

)

r e d u c t i o n

(+ :

suma wekt prawdo

)

n um t hr e a ds

(

n t h r e a d s

)

12

f o r

(

i n t

i

=0;

i

<

P

;

i

++) {

13

t a b

[

i

] [ 0 ] =

w c t a b

[

i

] [ 0 ] /

suma wc tab

;

14

suma wekt prawdo

+=

t a b

[

i

] [ 0 ] ;

15

}

16

}

17

e l s e

18

{

19

suma wc tab

+=

P

∗ (

f a b s

(

min

) +1) ;

20

#

pragma omp p a r a l l e l

f o r

d e f a u l t

(

none

)

f i r s t p r i v a t e

(

P

)

s h a r e d

(

wc tab

,

tab

,

suma wc tab

,

min

)

r e d u c t i o n

(+ :

suma wekt prawdo

)

n um t hr e a ds

(

n t h r e a d s

)

21

22

f o r

(

i n t

i

=0;

i

<

P

;

i

++) {

23

t a b

[

i

] [ 0 ] = (

w c t a b

[

i

] [ 0 ] +

f a b s

(

min

) +1)/

suma wc tab

;

24

suma wekt prawdo

+=

t a b

[

i

] [ 0 ] ;

25

}

26

}

Losowanie wartości:

1

s r a n d

( (

u n s i g n e d i n t

)

t i m e

( 0 ) ) ;

2

3

f o r

(

i n t

k

=0;

k

<

P

;

k

++) {

4

w a r t l o s o w a

= (

d o u b l e

)

rand

( ) / (

d o u b l e

)

RAND MAX

;

5

s u m a e l

= 0 ;

6

wynik

=

f a l s e

;

7

8

f o r

(

i n t

i

=0;

i

<

P

;

i

++) {

9

s u m a e l

+=

t a b

[

i

] [ 0 ] ;

10

i f

(

w a r t l o s o w a

<

s u m a e l

) {

11

w i e r s z

=

i

;

12

wynik

=

t r u e

;

13

}

14

15

i f

(

wynik

)

16

b r e a k

;

17

}

18

19

f o r

(

i n t

j

=0;

j

<

N

∗

G

;

j

++)

20

pop temp

[

k

] [

j

] =

pop

[

w i e r s z

] [

j

] ;

21

}

11

Przypisanie tablicy przekazanej do funkcji wylosowanych elementów:

1

#

pragma omp p a r a l l e l

f o r

d e f a u l t

(

none

)

f i r s t p r i v a t e

(

P

,

N

,

G

)

s h a r e d

(

pop

,

pop temp

)

nu m t hr e a ds

(

n t h r e a d s

)

2

f o r

(

i n t

i

=0;

i

<

P

;

i

++)

3

f o r

(

i n t

j

=0;

j

<

N

∗

G

;

j

++)

4

pop

[

i

] [

j

] =

pop temp

[

i

] [

j

] ;

5

}

4.8 Krzyżowanie

Funkcja reprezentująca operator krzyżowania. Krzyżowanie polega na połączeniu

niektórych (wybierane losowo) osobników w jeden. Kojarzenie ma sprawić, że potomek
dwóch osobników rodzicielskich ma zespół cech, który jest kombinacją ich cech (może się
zdarzyć, że tych najlepszych).

Argumenty:

• pop - populacja osobników,

• P - liczba osobników,

• N - liczba zmiennych funkcji,

• G - liczba bitów potrzebnych do zakodowania,

• Pk - prawdopodobieństwo krzyżowania.

1

v o i d

Krzyzowanie

(

i n t

∗∗

pop

,

i n t

P

,

i n t

N

,

i n t

G

,

d o u b l e

Pk

) {

2

i f

( (

Pk

<0) | |

(

Pk

>1) ) {

3

c o u t

<<

” Bledna w a r t o s c prawodpodobienswa k r z y z o w a n i a . Musi s i e

z a w i e r a c w p r z e d z i a l e

[ 0 ; 1 ] ”

<<

e n d l

;

4

r e t u r n

;

5

}

6

7

f o r

(

i n t

j

=0;

j

<(

P

−1) ;

j

=

j

+2) {

8

r

= (

d o u b l e

)

rand

( ) / (

d o u b l e

)

RAND MAX

;

9

10

i f

(

r

>=

Pk

)

11

c o n t i n u e

;

12

13

b i t p r z e c i e c i a

=(

rand

( ) %((

N

∗

G

) −1) ) + 1 ;

14

15

f o r

(

i n t

i

=0;

i

<

b i t p r z e c i e c i a

;

i

++) {

16

pop temp

[

j

] [

i

]=

pop

[

j

] [

i

] ;

17

pop temp

[

j

+ 1 ] [

i

]=

pop

[

j

+ 1 ] [

i

] ;

18

}

19

20

f o r

(

i n t

i

=

b i t p r z e c i e c i a

;

i

<

N

∗

G

;

i

++) {

21

pop temp

[

j

] [

i

]=

pop

[

j

+ 1 ] [

i

] ;

22

pop temp

[

j

+ 1 ] [

i

]=

pop

[

j

] [

i

] ;

23

}

24

}

25

}

12

4.9 Mutacja

Metoda reprezentująca mutację w algorytmie genetycznym. Mutacja wprowadza do

osobników losowe zmiany. Jej zadaniem jest wprowadzanie różnorodności w populacji,
czyli zapobieganie (przynajmniej częściowe) przedwczesnej zbieżności algorytmu. Muta-
cja zachodzi z pewnym przyjętym prawdopodobieństwem - zazwyczaj rzędu 1%. Jest ono
niskie, ponieważ zbyt silna mutacja przynosi efekt odwrotny do zamierzonego.

Argumenty:

• pop - populacja osobników,

• P - liczba osobników,

• N - liczba zmiennych funkcji,

• G - liczba bitów potrzebnych do zakodowania,

• Pm - prawdopodobieństwo mutacji.

1

v o i d

Mutacja

(

i n t

∗∗

pop

,

i n t

P

,

i n t

N

,

i n t

G

,

d o u b l e

Pm

) {

2

i f

( (

Pm

<0) | |

(

Pm

>1) ) {

3

c o u t

<<

” Bledna w a r t o s c prawodpodobienswa m u t a c j i . Musi s i e

z a w i e r a c

w p r z e d z i a l e

[ 0 ; 1 ] ”

<<

e n d l

;

4

r e t u r n

;

5

}

6

7

#

pragma omp p a r a l l e l

f o r

d e f a u l t

(

none

)

f i r s t p r i v a t e

(

P

,

N

,

G

)

s h a r e d

(

pop

,

pop temp

)

nu m t hr e a ds

(

n t h r e a d s

)

8

f o r

(

i n t

i

=0;

i

<

P

;

i

++)

9

f o r

(

i n t

j

=0;

j

<

N

∗

G

;

j

++)

10

pop temp

[

i

] [

j

] =

pop

[

i

] [

j

] ;

11

12

d o u b l e

r

;

13

14

f o r

(

i n t

i

=0;

i

<

P

;

i

++) {

15

f o r

(

i n t

j

=0;

j

<

N

∗

G

;

j

++) {

16

r

= (

d o u b l e

)

rand

( ) / (

d o u b l e

)

RAND MAX

;

17

18

i f

(

r

>=

Pm

)

19

c o n t i n u e

;

20

21

i f

(

pop temp

[

i

] [

j

]==0)

22

pop temp

[

i

] [

j

] = 1 ;

e l s e

pop temp

[

i

] [

j

] = 0 ;

23

}

24

}

25

26

#

pragma omp p a r a l l e l

f o r

d e f a u l t

(

none

)

f i r s t p r i v a t e

(

P

,

N

,

G

)

s h a r e d

(

pop

,

pop temp

)

nu m t hr e a ds

(

n t h r e a d s

)

27

f o r

(

i n t

i

=0;

i

<

P

;

i

++)

28

f o r

(

i n t

j

=0;

j

<

N

∗

G

;

j

++)

29

pop

[

i

] [

j

] =

pop temp

[

i

] [

j

] ;

30

}

13

5 Wykorzystane funkcje i dyrektywy zrównoleglające

5.1 Funkcje MPI

W części głównej programu wykorzystane zostały następujące funkcje MPI:

• MPI Init thread - inicjalizacja środowiska MPI (wykorzystany został parametr

MPI THREAD FUNNELED oznaczający, że proces uruchomiony zostanie w trybie
wielowątkowym ale tylko wątek główny będzie wywoływał metody środowiska MPI
(wszystkie wywołania metod MPI zostają skierowane do wątku głównego),

• MPI Comm rank - pobranie ID aktualnego procesu,

• MPI Comm size - pobranie liczby procesów procesu,

• MPI Comm set errhandler - skojarzenie uchwytu funkcji obsługi błędu z komunika-

torem,

• MPI Type create subarray - tworzy nowy typ danych na podstawie tablicy wielo-

wymiarowej,

• MPI Type create resized - ustawianie wyrównania w pamięci dla nowo utworzonego

typu,

• MPI Type commit - zatwierdzenie nowego typu danych,

• MPI Scatter - wysyłanie danych od jednego procesu do wszystkich pozostałych w

grupie,

• MPI Scatterv - wysyłanie danych o zmiennej długości od jednego procesu do wszyst-

kich pozostałych w grupie,

• MPI Reduce - redukowanie wartości we wszystkich procesach do pojedynczej war-

tości,

• MPI Barrier - wstrzymanie pracy procesu aż do wywołania tej funkcji przez wszyst-

kie procesy należące do grupy,

• MPI Finalize - zatrzymanie środowiska MPI.

5.2 Składniki OpenMP

• konstrukcja OMP for - rozdzielenie iteracji pętli pomiędzy wątki,

• klauzula firsprivate - przypisanie zmiennym w wątku wartości jak przed wejściem

do bloku równoległego,

• klauzula shared - ustalenie danych współdzielonych,

• klauzula reduction - redukcja wyników częściowych do współdzielonej zmiennej glo-

balnej,

• klauzula num threads - ustalenie ilości wątków.

14

6 Przeprowadzone pomiary

Testy zostały przeprowadzone na serwerze CUDA, gdzie do dyspozycji mieliśmy 4

rdzenie w technologi hyperthreading (8 wątków). Pomiary wykonaliśmy dla następujących
wartości parametrów programu:

• liczba osobników:

P = 2000,

• liczba zmiennych funkcji:

N = 1,

• liczba iteracji programu:

H = 8000,

• prawdopodobieństwo krzyżowania:

Pk = 0.9,

• prawdopodobieństwo mutacji:

Pm = 0.05,

• początek przedziału:

a = -1,

• koniec przedziału:

b = 1,

• krok:

dx = 0.00001.

Pierwsza część pomiarów została wykonana tylko dla środowiska MPI (liczba wąt-

ków OpenMP została ustalona na 1). Wątek macierzysty nie uczestniczy w obliczeniach
więc liczba procesów liczących jest o 1 mniejsza (wartość w nawiasie).

Liczba procesów MPI

Liczba wątków OpenMP

Czas[ms]

Przyspieszenie

2 (1)

1

120035

1,0000000000

3 (2)

1

40631,1

2,9542640982

4 (3)

1

24236,2

4,9527153597

5 (4)

1

22667,3

5,2955138018

6 (5)

1

17675,3

6,7911152852

7 (6)

1

13765,1

8,7202417709

8 (7)

1

11758,5

10,2083599099

9 (8)

1

11825,2

10,1507796908

15

Rysunek 4: Czas obliczeń (MPI)

Rysunek 5: Przyspieszenie (MPI)

16

W drugiej części pomiarów rozdzieliliśmy pracę za pomocą wątków OpenMP (liczba

procesów pracujących wynosi 1). Niestety działanie takie nie przyniosło lepszych rezulta-
tów.

Liczba procesów MPI

Liczba wątków OpenMP

Czas[ms]

Przyspieszenie

2 (1)

1

115456

1,0000000000

2 (1)

2

114820

1,0055391047

2 (1)

3

111538

1,0351270419

2 (1)

4

110191

1,0477806717

2 (1)

5

113452

1,0176638578

Rysunek 6: Czas obliczeń (OpenMP)

Rysunek 7: Przyspieszenie (OpenMP)

17

7 Wnioski

Algorytmy genetyczne są ciekawą metodą na znalezienie rozwiązania danego pro-

blemu. Podczas projektowania takiego algorytmu musimy wybrać metodę selekcji oraz
operatory kodowania, które zostaną wykorzystane. Bardzo istotne jest poprawne określe-
nie funkcji przystosowania osobników, gdyż w dużym stopniu otrzymane rozwiązania od
niej zależą.

W przypadku naszego problemu tj. znalezienie ekstremum lokalnego funkcji algo-

rytm genetyczny osiągnął bardzo dobre wyniki.

Powyższe wyniki prowadzą do wniosku, że w przypadku naszego problemu wykorzy-

stanie środowiska MPI przyniosło znaczną poprawę czasu wykonania (praktycznie dziesię-
ciokrotne przyśpieszenie). Środowisko OpenMP przyśpieszyło czas obliczeń w nieznaczny
sposób. Połączenie obu tych technologii nie przyniosło oczekiwanych wyników.

Udało nam się pokazać, że programowanie równoległe jest bardzo przydatne i po-

zwala przyspieszyć czas wykonywania programu.

18