Równolegla implementacja modulów CoDi za pomoca mpi



Pobieranie 438.94 Kb.
Strona1/2
Data07.05.2018
Rozmiar438.94 Kb.
  1   2

Andrzej Pastusiak

Projekt z przedmiotu "Środowiska przetwarzania równoległego" prowadzonego przez mgr Grzegorza Skrzypczyńskiego



Temat projektu

Równoległa implementacja genetycznej ewolucji modułów CoDi w oparciu o bibliotekę MPI.


Wprowadzenie

Opis problemu


Jako problem do rozwiązania z wykorzystaniem MPI zostało wybrane zrównoleglenie procesów ewolucyjnych opartych o algorytmy genetyczne (GA). Jak wiadomo algorytmy genetyczne są klasą problemów, które świetnie nadają się do paraleizacji i rozpraszania. Jednakże te z natury równoległe algorytmy, zazwyczaj rozwiązuje się sekwencyjnie. Cechą GA jest to, że ich zapotrzebowanie na moc obliczeniową jest duże. Im więcej mocy obliczeniowej pochłonie proces ewolucji, tym możemy być pewniejsi, że wyniki są bliżej optimum globalnego problemu postawionego przed GA.

Zadaniem, które zostało postawione ewolucja modułów CoDi, które są klasa sieci neuronowych opartych o automaty komórkowe (CA). Jest to nowatorski podejście do konstrukcji sieci za pomocą mechanizmów ewolucyjnych zainicjowany przez Hugo de Garisa [2]. Moduły CoDi jako automaty komórkowe nadają się świetnie do zrównoleglenia, jednak komunikacja między poszczególnymi komórkami automatu powinna być szybka, ich ilość wielka, a operacje wykonywane w komórce zbyt proste, aby rozpatrywać zrównoleglenie obliczeń na poziomie MPI. Bardziej adekwatna jest konstrukcja specjalnego sprzętu opartego o FPGA (Field Programmable Gate Array). Takie rozwiązanie jest już stworzone i funkcjonuje [2]. W projekcie zrównoleglone zostały same procesy ewolucyjne. Sama zasada działania modułu CoDi, opisana w [1,2] nie jest istotna z punktu widzenia tego rozwiązania.


Przyjęte założenia


Istotą działania GA jest dobre zdefiniowanie funkcji przystosowania (fitness) dla osobników populacji kodowanych za pomocą zestawu genów zawartych w chromosomie. Następnie algorytmy selekcji tak dobierają osobniki, aby w kolejnych pokoleniach przeżywały te, dla których funkcja przystosowania jest największa. Dobre mają większe szansę, na przeżycie i na wymianę materiału genetycznego z innymi, niż te o słabym przystosowaniu. W większości zastosowań operacje genetyczne takie, jak krzyżowanie i mutacja mają znikomy wpływ na szybkość procesów ewolucyjnych, a najbardziej czasochłonną częścią implementacji jest algorytm obliczania funkcji przystosowania. Dzieje się tak głównie za sprawą tego, że zazwyczaj do uzyskania dobrych wyników ilość osobników biorących udział w ewolucji powinna być możliwie największa. Liczby pokoleń również nie należy zmniejszać, aby dać możliwość GA dobrego przeszukania przestrzeni rozwiązań nie dopuszczając do utykania w minimach lokalnych funkcji przystosowania.

Podobnie jest w wypadku modułów CoDi, jednakże czas obliczenia funkcji przystosowania jest naprawdę duży i określenie przystosowania chromosomu kodującego jednego osobnika jest rzędu sekund. Zakładając skromne wielkości populacji 100 i liczbę pokoleń na 1000 cały eksperyment należy szacować w dniach.

Założono, że zrównolegleniu ulegnie sam proces wyznaczania przystosowania pojedynczego osobnika natomiast, cały proces ewolucji będzie scentralizowany. Proces master będzie przechowywał aktualny stan populacji, a procesy slave otrzymywać będą zadania obliczania przystosowania pojedynczych osobników. Centralny proces jest także odpowiedzialny za wykonywanie wszelkich operacji genetycznych na materiale genetycznym (selekcja, krzyżowanie, mutacja).

W ramach eksperymentu ewolucyjnego koszt obliczeniowy wyznaczenia wartości funkcji przystosowania nie zmienia się. W trakcie prowadzonych testów elementem, który niepotrzebnie spowalniał obliczenie była konieczność zebrania wszystkich wartości fitness przed przystąpieniem do operacji genetycznych i dystrybucją kolejnych zadań do poszczególnych węzłów. Najpowolniejszy węzeł często wstrzymywał pracę pozostałych mimo tego, iż inny szybszy mógłby wykonywać następne zadania. Aby zapewnić optymalne wykorzystanie wszystkich węzłów, proces Master zbiera ostatnie 10 czasów obliczenia funkcji fitness, dla każdego z węzłów. Na tej podstawie może prognozować czasy zakończenia obliczeń przez procesy slave. Przed przystąpieniem do ewolucji kolejnego pokolenia, tak rozkłada liczbę obliczeń dla każdego węzła, aby całkowity czas obliczenia fitness dla wszystkich osobników pokolenia był najkrótszy. W trakcie, gdy napływają wyniki, czasy prognozowanego zakończenia obliczeń mogą ulec zmianie i obliczenia mogą być przesunięte z węzła wolniejszego na węzeł szybszy. Jak pokazały testy wprowadzenie tej modyfikacji pozwoliło przyśpieszyć obliczenia angażując także jednostki o stosunkowo małej mocy obliczeniowej względem innych.


Komunikacja między procesami


Komunikacja między procesami master i slave przebiega w klasyczny sposób – za pomocą dwóch podwójnych par skrzyżowanej operacji MPI_Send i MPI_Recv. Każde przesłanie danych sprowadza się do przesłania wartości całkowitej (MPI_INT) określającej długość paczki danych do odebrania. Paczka danych składa się z przesłanej właśnie ilości znaków (MPI_CHAR) i jest wysyłana asynchronicznie MPI_ISend. Na podstawie tak przesłanej informacji odbiorca rozkodowuje niezbędne dane.

Tak zaproponowane rozwiązanie jest może niezbyt wydajne, gdyż nadawca musi przekonwertować przesyłane dane na postać tekstową, a odbiorca musi je zinterpretować. Jednakże jest bardzo wygodne z punktu widzenia implementacji, gdzie dane możemy traktować jako strumień (plik) tekstowy.


Slave


Każdy proces slave początkowo czeka na dane do obliczeń. Może otrzymać bądź dane, bądź informację sygnalizujący, aby zakończył swoje wykonanie (paczka o długości 0). Po otrzymaniu paczki przystępuje do obliczeń. Po ich wykonaniu odsyła wyniki (w paczce) do procesu zarządcy i oczekuje na kolejne zadanie.

Master


Po rozpoczęciu pracy inicjuje wszelkie niezbędne struktury oraz sporządza listę współpracujących z nim procesów obliczeniowych. O każdym ze "współpracowników" gromadzi dane, o tym czy proces jest obciążony oraz oblicza wydajność każdego z nich. Na podstawie tych danych wyznacza liczbę obliczeń funkcji fitness dla każdego procesu dającą najszybszy czas obliczenia przystosowania wszystkich osobników populacji, zakładając, że wydajność węzłów pozostanie niezmieniona. Następnie generowane są paczki danych i rozsyłane do oczekujących procesów. Gdy wszystkie procesy mają rozdzielone zadania zgodnie z planem dystrybucji, master oczekuje na informację o długości paczki do odebrania od dowolnego z procesów (MPI_Wait). Po jej otrzymaniu pobierane są właściwe wyniki obliczeń – wyniki na wyjściach modułu CoDi z fazy sygnalizacji. Po stronie procesu centralnego są one następnie przekształcane na właściwą wartość funkcji przystosowania. Jeżeli konieczne, dokonywana jest korekcja planu przydziału zadań i dystrybuowane jest zadanie dla nieobciążonych procesów.

Algorytm obciążania procesorów


Dzięki zastosowaniu prognozowania czasu zakończenia zadań procesory są obciążane w sposób optymalny. Przy dużej populacji nawet bardzo wolne węzły nie spowalniają obliczeń. Jednym z minusów tego rozwiązania wymagającym jeszcze ulepszenia jest wypadek, kiedy jeden z węzłów jest przez pewien krótki czas mocno obciążony. Wtedy zostanie on zapamiętany jako bardzo wolny i nie będą mu przydzielane zadania, nawet jeżeli jego obciążenie zmniejszy się. Należałoby wprowadzić pewną korekcję umożliwiającą testowanie co pewien czas szybkości węzła.

Innym problemem jest sytuacja, gdy prognozy do końca się nie sprawdzą, a ewolucja pojedynczego pokolenia dobiega końca. Nieobciążone są szybkie węzły, które być może poradziłyby sobie z zadaniem szybciej niż oczekiwanie na "maruderów". W tym wypadku można rozsyłać to samo zadanie do kilku węzłów na raz i oczekiwać najszybszej odpowiedzi po czym przerywać powolniejsze obliczenia.

Innym sposobem na przyśpieszenie może być zmiana algorytmu selekcji na taki, który nie wymaga znajomości wszystkich funkcji przystosowania przed przystąpieniem do operacji genetycznych.

Komunikacja w oparciu o gniazdka unixowe (sockets)


Sposób przesyłania danych oparty o pakowanie danych w paczki o określonej długości i przesyłanie między odbiorcą i nadawcą został głównie narzucony przez fakt, iż możliwe jest również rozpraszać obliczenia w oparciu o gniazdka (sockets). Jest to rozwiązanie dużo bardziej elastyczne i przenośne, gdyż nie wymaga instalacji oprogramowania zapewniającego obsługę MPI. Umożliwia ono dystrybucję zadań za pomocą rozległych sieci TCP/IP do heterogenicznych węzłów. Jak się okazało rozwiązanie to było dużo wygodniejsze w praktyce i z powodzenie zastąpiło rozwiązanie oparte o MPI. Jego konstrukcja jest analogiczna do tego opartego o MPI – jedyną różnicą jest medium - protokół TCP w miejsce komunikacji MPI.

Ten sam program wykonawczy może realizować funkcje serwera obliczeń oraz centralnego procesu zarządcy ewolucji. Wybór dokonywany jest na podstawie parametrów linii komend. Dla procesu mającego być serwerem obliczeń jedynym parametrem jest port, na którym powinien nasłuchiwać nadchodzących połączeń. Centralny proces sterujący ewolucją jako parametry otrzymuje plik z listą adresów i portów maszyn, które mają wziąć udział w obliczeniach. Proces ten podobnie jak master przy implementacji opartej o bibliotekę MPI nie wykonuje obliczeń a jedynie łączy się z serwerami, dystrybuuje obliczenia oraz przeprowadza operacje genetyczne. Implementacja oparta o gniazdka została stworzona przy wykorzystaniu przenośnej biblioteki socket++. Dzięki czemu możliwe jest rozpraszanie obliczeń zarówno do systemów UNIXowych i systemów operacyjnych z rodziny Windows. Umożliwia ona potraktowanie połączenia TCP jako obiektu strumieniowego C++, pozwalając bardzo wygodnie odwoływać się do operacji związanych z komunikacją TCP/IP.

Ze względu na utrzymanie przenośności między wspomnianymi systemami operacyjnymi, serwery obliczeń mogą obsługiwać tylko jedno nadchodzące połączenie w danej chwili. Możliwość obsługiwania wielu procesów centralnych wydaje się zbyteczna, gdyż taka konkurencja o dostęp do procesora powodowałaby spadek wydajności obliczeń. Same obliczenia mają charakter raczej długotrwały i akceptowanie większej liczby połączeń prowadziłoby do przeciążenia węzła

Kodowanie przesyłanej informacji


Wąskim gardłem przy połączeniu TCP okazał się rozmiar paczki, gdy był za duży, możliwe było wysyłanie jednej paczki w danej chwili, gdyż dane blokowały się na buforze TCP, co przy powolnym połączeniu jest bardzo niekorzystne.

Problem został rozwiązany za pomocą dwóch poprawek. Po skrócono rozmiar paczki przez kodowanie informacji za pomocą binarnego strumienia bajtów ale tak, aby był on przenośny między platformami. Pozwoliło to zredukować rozmiar paczki kodującej chromosom 2 do 3 razy. Dawało to około 45KB danych niezbędnych do przesłania do węzła obliczeniowego. Następnie ustawiono bufor TCP na maksymalny rozmiar - 64 KB, co pozwoliło rozsyłać dane równolegle do wszystkich węzłów jednocześnie.

Rozwiązanie z kodowaniem binarnym chromosomu ostatecznie zastosowano także w wersji MPI redukując ilość przesyłanych danych między węzłami.

Opis uzyskanych wyników

Wydajność

Test 1


Przeprowadzona została seria pomiarów wydajności dla bardzo krótkiego procesu ewolucyjnego długiego na 9 pokoleń. W pierwszym pokoleniu liczba osobników wynosi 1, w drugim 2 potem 4,8,16,30. Razem daje to 151 funkcji fitness do obliczenia. Po osiągnięciu poziomu 30 osobników w 6 pokoleniu ich liczba zatrzymuje się na tym poziomie. Zmierzono czasy dla wykonania sekwencyjnego i od 2 do 27 współpracujących ze sobą procesów MPI. Użyty wariant algorytmu to codi.slow. Każda seria badań była przeprowadzana kolejno po sobie dając w sumie 6 serii wyników. Ich analiza pokazuje, iż wszystkie 6 serii nie wykazuje większych rozbieżności. Lista obciążanych 14 węzłów IBMa SP2 wyglądała następująco (węzeł n05 był wyłączony):

n15,


n01, n02, n03, n12,

n13, n04, n06, n07, n08, n09, n10, n11, n14

n01, n02, n03, n12, n13, n04, n06, n07, n08, n09, n10, n11, n14

Pierwszy wiersz (węzeł n15 to wide node, pozostałe to thin nodes) to węzeł będący procesem master dystrybuującym zadania. Drugi wiersz na liście to węzły nieobciążone w trakcie obliczeń. 3 wiersz to węzły, które w trakcie obliczeń były obciążone długotrwałymi obliczeniami z kolejki LoadLevelera. Obciążanie ich powodowało rywalizację procesów z tej kolejki i procesów MPI o dostęp do procesora. Ostatni wiersz badał wpływ uruchamiania więcej niż jednego procesu na jednym węźle. Oczywiście takie "przeciążanie" węzłów nie powinno zaowocować wielkim wzrostem szybkości, jeżeli każdy proces jest przez większość czasu zajęty obliczeniami, jak w wypadku rozpatrywanego problemu. Co też zostało potwierdzone pomiarami. Plusem takiego podejścia może być zwiększenie mocy obliczeniowej poprzez "wykradnięcie" czasu procesora procesom z kolejki LoadLevelera. Niestety zaobserwować można nieznaczny spadek prędkości przy zwiększonej liczbie procesów. Jest to spowodowane mechanizmem rozdziału zadań do procesorów na podstawie pomiarów czasu wykonania. Początkowa faza obliczeń dystrybuuje tylko jedno zadanie do jednego procesu i mierzy czas wykonania. Gdy uzyskany jest już obraz wydajności kolejnych procesów, na podstawie prognoz są rozsyłane zadania. Przy obciążaniu węzła więcej niż jednym procesem takie podejście jest mocno niedokładne, gdyż początkowe wyniki nie odzwierciedlają faktu, iż procesy będą konkurować o procesor. Dopiero w dalszym toku obliczeń wartości czasu wykonania stabilizują się przy rzeczywistych wartościach. Przeprowadzone testy były stosunkowo krótkie (151 zadań do dystrybucji) i powinny być najbardziej adekwatne do kilku węzłów. Potwierdziły to dłuższe testy (nieujęte w tym zestawieniu). Wtedy czas działania całej aplikacji zależy właściwie tylko od całkowitej rozproszonej mocy obliczeniowej, pod warunkiem, że wielkość populacji jest dużo mniejsza od liczby węzłów.

W podanych wykresach przyśpieszenie to stosunek czasu wykonania programu sekwencyjnego do programu równoległego. Efektywność to stosunek przyśpieszenia do liczby wykorzystywanych procesorów.

Jak widać na wykresie efektywności, jest ona daleka od 1.Jak zostało wspomniane, dzieje się tak głównie dlatego, że w teście początkowo nie wszystkie procesory są obciążone. Na wykresie czasu wykonania zaznaczone są słupki błędów obliczone jako standardowe odchylenie z 6 prób.








Test 2


W celu wyeliminowania usterek poprzedniego testu, przeprowadzono kolejny. Różnica polegała na tym, iż był dłuższy, a wszystkie procesory były obciążone w pełni od początku do końca testu. Liczba osobników w każdym pokoleniu była stała i wynosiła 30, co daje 270 obliczeń funkcji fitness. Zmodyfikowano algorytm predykcji czasu wykonania tak, że od samego początku obliczeń przydziela on zadnia jednocześnie wszystkim procesom biorącym udział w obliczeniach nie sprawdzając po kolei wydajności każdego węzła, jak to miało miejsce w poprzednim eksperymencie. Lista obciążanych analogicznie do poprzedniego testu wyglądała następująco:

n15,


n01, n09, n13,

n02, n03, n04, n06, n07, n08, n10, n11, n12, n14,



n01, n09, n13, n02, n03, n04, n06, n07, n08, n10, n11, n12, n14
Na przytoczonych poniżej wykresach można zaobserwować, że taka modyfikacja daj istotną poprawę współczynników przyśpieszenia i efektywności. Dużo większe odchylenie standardowe zaznaczone jako słupek błędu na pierwszym wykresie, należy tłumaczyć tym, że w trakcie przeprowadzania testów jeden z węzłów zostały wstrzymane obliczenia z kolejki LoadLevelera dając w kolejnych próbach do dyspozycji większą moc obliczeniową.








Pobieranie 438.94 Kb.

Share with your friends:
  1   2




©operacji.org 2020
wyślij wiadomość

    Strona główna