M Stanek-wieloagentowa Architektura Rozproszonego Systemu Przetwarzania Zadan Z Dynamicznym Rownowazeniem Obciazen

systemy wieloagentowe, systemy rozproszone, przetwarzanie rozproszone, obliczenia równoległe, migracja zadań, równowaŜenie obciąŜeń,

Kamil PAŚKO, Michał STANEK*

WIELOAGENTOWA ARCHITEKTURA ROZPROSZONEGO SYSTEMU PRZETWARZANIA ZADAŃ Z DYNAMICZNYM RÓWNOWAśENIEM OBCIĄśEŃ

W artykule przedstawiona została architektura wieloagentowego systemu rozproszonego przetwarzania zadań wraz z omówieniem algorytmu równowaŜenia obciąŜenia poszczególnych węzłów systemu. W pierwszej części artykułu opisane zostały zadania wykonywane przez agentów poszczególne typy agentów, następnie przedstawiony został algorytm równowaŜenia obciąŜenia systemu prowadzący do minimalizacji średniego czasu wykonania zadania w. W końcowej części artykułu zaprezentowane zostały otrzymane wyniki oraz moŜliwe dalsze usprawnienia.

1. WSTĘP Analizując historię rozwoju superkomputerów, wyróŜnić moŜemy dwa sposoby ich projektowania. Pierwszy, w którym bardzo duŜa moc obliczeniowa wynika z zastosowania jednego bardzo szybkiego procesora, drugi zakładający wykorzystanie duŜej ilości średnio wydajnych i powszechnie dostępnych procesorów w celu osiągnięcia wzrostu mocy obliczeniowej poprzez zrównoleglenie procesu obliczeniowego. Nie trzeba jednak kupować superkomputera, aby móc korzystać z dobrodziejstw przetwarzania równoległego. Rozwój sieci komputerowych w tym Internetu umoŜliwił powstanie takich projektów jak np. SETI@HOME[1], w którym do analizy odbieranego przez radioodbiorniki sygnału wykorzystywana była moc obliczeniowa tysięcy komputerów uŜytkowników Internetu.

*

Politechnika Wrocławska, Instytut Informatyki Stosowanej, 50-370 Wrocław, Wyb. Wyspiańskiego 27, e-mail: [email protected], [email protected], Koło Naukowe Sztucznej Inteligencji „CJANT"

W artykule przedstawiona jest architektura oraz algorytm równowaŜenia obciąŜenia systemu rozproszonego przetwarzania zadań umoŜliwiającego wykorzystanie mocy obliczeniowej wielu połączonych za pomocą sieci komputerów.

2. BUDOWA SYSTEMU Rozproszony system przetwarzania zadań tworzą połączone siecią komputery z uruchomionym autorskim programem MARS (MultiAgent Resource Sharing System). KaŜdy komputer w takim systemie nazywać będziemy dalej węzłem. Zlecone zadania obliczeniowe mogą być wykonywane na kaŜdym węźle systemu, istnieje jednak dokładnie jeden węzeł, który poza wykonywaniem zadań komunikuje się z uŜytkownikami w celu przyjmowania od nich Ŝądań oraz zwracania rezultatów obliczeń. Wśród zadań, jakie mogą zlecić uŜytkownicy wyróŜnić moŜemy zadania niepodzielne oraz n-dekomponowalne. Poprzez zadanie n-dekomponowalne rozumiemy takie zadanie, które moŜe zostać rozłoŜone na n zadań niepodzielnych (np. poszukiwanie liczb pierwszych, wyszukiwanie wzorca w tekście, itp.). Zadania takie mogą być następnie realizowane równolegle. Zadanie niepodzielne, to takie, które w całości musi zostać wykonane w sposób sekwencyjny. Celem działania systemu jest zrealizowanie wszystkich zleconych przez uŜytkowników zadań w jak najkrótszym czasie. Oczywistym jest, Ŝe cel ten zostanie osiągnięty tylko wtedy, kiedy wykorzystywana będzie w sposób równomierny moc obliczeniowa wszystkich węzłów systemu[3]. Zaproponowany system składa się z wielu współpracujących ze sobą agentów (rys. 1), czyli programów „działających w pewnym środowisku, zdolnych do komunikowania się między sobą, monitorowania swego otoczenia i podejmowania autonomicznych decyzji w celu osiągnięcia celu”[2]. PoniŜej opisane są zadania jakie wykonują poszczególni agenci. Dokładnie jeden agent obsługujący, umieszczony w pierwszym węźle systemu, pełni funkcję pośrednika pomiędzy klientami a systemem. Dla kaŜdego zadania tworzy odpowiedniego agenta zadania oraz wskazuje mu węzeł sieci, na którym ma rozpocząć pracę. Agent obsługujący przekazuje równieŜ wyniki pracy agentów zadań odpowiednim klientom. Agent zadań jest podstawową jednostką systemu, wykonuje on zadania zlecone przez klientów. Agent zadań ma moŜliwość migracji pomiędzy węzłami systemu [4] lub w przypadku zadań n-dekomponowalnych utworzenie nowego agenta zadania i przekazanie mu części realizowanego obecnie zadania, a następnie odebrania wyników jego obliczeń. Tablica, jest to współdzielona i dostępna dla wszystkich agentów przestrzeń informacyjna. W tablicy tej znajdują się informacje na temat poziomu obciąŜenia poszczególnych węzłów obliczeniowych.

Tablica ogłoszeń Węzeł 2

Węzeł N System operacyjny

System operacyjny

JAVA

JAVA

MARS

MARS

Agent zadania 1

.....

Agent zadania 1

....

....

Agent sterujący

Agent sterujący

Agent zadania K

TCP/IP

Agent zadania K

TCP/IP

Sieć System operacyjny JAVA MARS

Klient

Agent sterujący

Agent zadania 1

....

Klient

Agent obsługujący

Agent zadania K

TCP/IP

Węzeł 1

Rys. 1. Diagram przedstawiający poszczególne elementy systemu

3. ALGORYTM RÓWNOWAśENIA OBCIĄśEŃ Aby cel pracy systemu, czyli wykonanie wszystkich zleconych zadań w moŜliwie najkrótszym czasie, mógł być zrealizowany konieczne jest dynamiczne równowaŜenie obciąŜenia pracy kaŜdego węzła systemu, co przejawia się między innymi kierowaniem nowych zadań na najmniej obciąŜone węzły systemu oraz przenoszenie zadań z węzłów najbardziej obciąŜonych na węzły o mniejszym obciąŜeniu. Od algorytmu równowaŜenia obciąŜenia zaleŜy średni czas, po jakim klient otrzyma rozwiązanie swojego zadania [3]. Za dynamiczne równowaŜenie obciąŜenia w systemie odpowiedzialni są agenci sterujący oraz agent obsługujący. Zadanie agenta obsługującego polega na wskazaniu nowo tworzonym agentom zadań węzłów systemu o najmniejszym obciąŜeniu. Zadaniem agenta sterującego jest badanie poziomu obciąŜenia węzła, na którym się znajduje i w przypadku stwierdzenia, Ŝe poziom obciąŜenia innych węzłów jest niŜszy wybranie jednego agenta zadania i zaŜądanie od niego podzielenia zadania (w przypadku zadania n-dekomponowalnego) lub wymuszenie migracji na inny węzeł (w przypadku zadanie nie podzielnego). Dokładny algorytm działania agenta sterującego opisany jest poniŜej.

Algorytm działania agenta sterującego 1. monitoruj obciąŜenie procesora węzła przez okres ∆t 2. wyślij średnią wartość obciąŜenia procesora w czasie ∆t do tablicy ogłoszeń 3. pobierz wartości obciąŜeń innych węzłów systemu 4. 5. 6. 7. 8.

wyznacz średnie obciąŜenie systemu c (wzór 1) wyznacz odchylenie standardowe σ (wzór 2) sprawdź czy aktualne obciąŜenie węzła jest większe niŜ c + σ , jeŜeli tak to przejdź do kroku 7, jeŜeli nie to do kroku 1 stwórz listę B zawierająca agentów zadań realizujących zadania n-dekomponowalne, jeŜeli lista B jest niepusta to przejdź do kroku 9 w przeciwnym razie do 12

9. stwórz listę A węzłów których obciąŜenie jest mniejsze od c − σ (wzór 3) 10. wyślij Ŝądanie podziału zadania do dowolnego agenta z listy B oraz przekaŜ mu listę A (najmniej obciąŜonych węzłów) 11. przejdź do kroku 1 12. jeśli w węźle znajduje się przynajmniej dwóch agentów zadań to wyślij informację do dowolnego agenta o konieczności migracji oraz podaj adres najmniej obciąŜonego węzła cmin (wzór 4) N

c=

∑c i =1

N

N

σ=

∑ (c i =1

i

i

+ c) 2

N −1

{

(1)

,

(2)

,

}

A = i i ∈ W ∧ ci < c + σ , c min = arg min{ci }, i ∈ W , i

(3) (4)

Opis wzorów wykorzystywanych w algorytmie: N to całkowita liczba węzłów, c to średnie obciąŜenie wszystkich węzłów systemu, ci oznaczona obciąŜenie i-tego węzła, σ to odchylenie standardowe obciąŜenia węzłów, W oznacza zbiór wszystkich węzłów systemu, A to zbiór najmniej obciąŜonych węzłów, cmin to najmniej obciąŜony węzeł w systemie. Agent zadań realizujący zadanie n-dekomponowalne w przypadku otrzymania Ŝądania podziału zadania tworzy nowego agenta zadań, przekazuje mu część swojego zadania oraz z przekazanej przez agenta sterującego listy A (węzłów najmniej obciąŜonych) wybiera węzeł, z którym ma najszybszą komunikację (czas wysłania i odebrania komunikatu jest najkrótszy). W przypadku otrzymania Ŝądania migracji na inny

węzeł zaprzestaje wykonywania zadania na bieŜącym węźle, przenosi się na wskazany przez agenta sterującego węzeł docelowy i kontynuuje realizację wstrzymanego wcześniej zadania.

4. WYNIKI BADAŃ Przedstawiony system oraz algorytm równowaŜenia obciąŜenia zaimplementowany został w języku JAVA oraz przetestowany w ramach systemu składającego się z czterech węzłów, których konfiguracja podana została poniŜej: A. B. C. D.

Pentium II – 300 MHz/192 MB/ Linux Debian Pentium III – 500 MHz/256 MB/ Linux Debian Pentium M – 1.3 GHz/512 MB/ Linux Debian AMD Sempron 1.5 GHz/256 MB/ MS Windows XP Profesional

Jako zadanie n-dekomponowalne wybrany został problem poszukiwania liczb pierwszych, natomiast jako zadanie niepodzielne wybrany został problem poszukiwania ekstremów liniowych funkcji wielu zmiennych z ograniczeniami liniowymi metodą simpleks[5]. Przebadane zostały czasy wykonania pojedynczego zadania, serii pięciu zadań jednego typu oraz dziesięciu zadań, z czego pięć stanowiły zadania niepodzielne, a drugie pięć zadania n-dekomponowalne. 250 225

150

Średnia

125 100

Czas [sek]

175

75 50 25 0

A B

C D

M

Komputer Średnia

350 325

Średnia

A

B

C D

A

B C D

M

Komputer Średnia

b) 1 zadanie podzielne

c) 5 zadań niepodzielnych 350 325

1200 1100 900 800

Średnia

700 600 500 400 300 200

A

B

C D

M

Średnia Komputer

d) 5 zadań n-dekomponowalnych

Czas [sek]

1000

0

Średnia

175 150 125 100 75 50 25 0

M

1300

100

300 275 250 225 200

Komputer Średnia

a) 1 zadanie n-dekomponowalne

Czas [sek]

Czas [sek]

200

37,5 35 32,5 30 27,5 25 22,5 20 17,5 15 12,5 10 7,5 5 2,5 0

Czas [sek]

275

300 275 250 225 200

Średnia

175 150 125 100 75 50 25 0

A

B

C D

M

Komputer Średnia

e) 5 zadań niepodzielnych oraz 5 zadań podzielnych

Rys. 2. Wyniki pomiarów realizacji zadań na pojedynczych węzłach w rozproszonym systemie realizacji zadań MARS

Na rys. 2 przedstawione zostały czasy wykonania zadań, na pojedynczym węźle (wszystkie zadania wykonywane były przez jeden komputer) oraz z wykorzystaniem rozproszonego systemu przetwarzania zadań (MARS) wykorzystującym omówiony

mechanizm równowaŜenia obciąŜeń. Uzyskane wyniki wskazują, Ŝe z wykorzystaniem systemu czas wykonania zadania jest średnio 44% mniejszy niŜ przy wykorzystaniu tylko jednego węzła obliczeniowego.

5. PODSUMOWANIE Zaproponowana wieloagentowa architektura systemu rozproszonego przetwarzania zadań w znaczący sposób pozwoliła zmniejszyć czas oczekiwania klienta na wykonanie zadania. Przedstawiony algorytm równowaŜenia zasobów zapewnia ponadto, Ŝe moc komputerów wchodzących w skład systemu będzie wykorzystana w sposób równomierny. Dalsze kierunki rozwoju systemu polegać będą na odejściu od stosowanej obecnie miary uwzględniającej jedynie stopień obciąŜenia procesora na rzecz bardziej obiektywnej miary uwzględniającej dostępną moc obliczeniową węzła oraz poziom zasobów pamięci. Planowane jest równieŜ opracowanie algorytmów pozwalających na odzyskanie zadań w przypadku uszkodzenia któregokolwiek z węzłów systemu.

LITERATURA

[1] D.P. Anderson, J. Cobb, E. Korpela, M. Lebofsky, D. Werthimer, SETI@home: an experiment in public-resource computing, Communications of the ACM, 56-61, 2002 [2] G. Weiss, Multiagent systems: a modern approach to distributed artificial intelligence, MIT Press, 1999 [3] K. Chow and Y. Kwok, On Load Balancing for Distributed Multiagent Computing, IEEE Transactions On Parallel And Distributed Systems, VOL. 13, NO. 8, AUGUST 2002, 787-801 [4] Andreia C. de Aquino, Adriana C. Biancho, Maurício G.V. Ferreira, José Demisio S. da Silva, A Multi-agent Load Balancing Architecture for Distributed Object Applications, Real-Time Computing Systems and Applications, volume 2, 1056-1061, 2006 [5] Operations Research - Linear Programming - Simplex Algorithm, 10 marzec 2007, http://www.egwald.com/operationsresearch/lpsimplex.php

MULTIAGENT DISTRIBUTED TASK SOLVING SYSTEM ARCHITECURE WITH LOAD BALANCING ALGORITHM

Article describes architecture of multiagent distributed task solving system and load balancing algorithms used to distribute tasks among systems nodes to achieve better performance. First section present system architecture and agents responsibility, next section describes details of load balancing algorithm. Last section contains obtained results and possible future improvements.