1 Dynamiczna alokacja zadań w sieciach MESHAutorzy: Anna Tarasiewicz, Michał Tarnawski

2 Koło naukowe SISK

3 Plan prezentacji Czym są sieci MESH?Znaczenie dynamicznej alokacji zadań Popularne algorytmy Autorski algorytm System eksperymentowania Wyniki badań Podsumowanie

4 Sieci MESH - Definicja MESH – struktura komputerów połączonych w usystematyzowaną sieć pozwalająca rozwiązywać złożone obliczeniowo problemy. Każdy komputer to węzeł sieci. Do rozwiązywania problemów można użyć wielu węzłów na raz, aby szybciej uzyskać wynik.

5 Alokacja ciągła vs. rozproszonaAlokacja Ciągła - Każdy węzeł zadania sąsiaduje z innym węzłem tego samego zadania. Alokacja Rozproszona - Zadania rozłożone na węzły niekoniecznie sąsiadujące ze sobą. Małe straty na komunikację miedzy węzłami Możliwa trudność alokacji Łatwość alokacji Możliwe duże straty podczas komunikacji między oddalonymi węzłami

6 Dynamiczna alokacja zadańW każdej chwili dysponujemy jedynie informacją na temat zadań, które już znajdują się w systemie przetwarzania Nie wiadomo kiedy i jakie nowe zadania pojawią się w systemie Bardzo ważne z praktycznego punktu widzenia w rzeczywistych systemach przetwarzania

7 Przykładowe algorytmyLosowy ;) First-fit Busy list

8 Algorytm First Fit Kolejne zadania alokowane są w pierwszym wolnym miejscu na sieci MESH. Zalety: Łatwość implementacji Wady: Niezadawalające wykorzystanie potencjału sieci Duży stopień fragmentacji sieci uniemożliwiający alokowanie większych zadań

9 First Fit (t=0)

10 First Fit (t=1)

11 First Fit (t=2)

12 First Fit (t=3)

13 First Fit (t=4)

14 First Fit (t=5)

15 Algorytm Busy List Wszystkie zaalokowane zadania umieszczane są na tzw. liście „Busy”. Lista ta przyśpiesza proces szukania podsieci poprzez zawężenie analizy do sąsiedztwa zadań już zaalokowanych. Dla zadania, które w następnej kolejności ma być realizowane na sieci MESH tworzy tzw. listę kandydatów. Kandydaci to miejsca na sieci MESH o kształcie alokowanego zadania. Kandydaci szukani są w sąsiedztwie już zaalokowanych zadań. Najlepszy kandydat sąsiaduje z największą ilością zajętych węzłów lub krawędzi. Najlepszego kandydata wyłania się podliczając przyznaną ilość punktów za sąsiedztwo.

16 Busy List (t=0)

17 Busy List (t=1)

18 Busy List (t=2)

19 Busy List (t=3)

20 Busy List (t=4)

21 Busy List (t=5)

22 Busy List - ocena Zalety: Wady: Zmniejszona fragmentacja sieciLepsze wykorzystanie potencjału sieci Wady: Bardziej złożony algorytm – wymaga większego nakładu czasowego na stworzenie list i wielokrotne przeliczanie oraz ocenę kandydatów

23 Autorski algorytm Hybrid Busy ListBazuje na dwóch spostrzeżeniach: Bazując na aktualnym obciążeniu sieci można sprytnie wybierać zadania z kolejki oczekujących Wskazane jest alokowanie obok siebie zadań, które skończą się w tym samym momencie

24 Hybrid Busy List (t=0)

25 Hybrid Busy List (t=1)

26 Hybrid Busy List (t=2)

27 Hybrid Busy List (t=3)

28 Hybrid Busy List (t=4)

29 Hybrid Busy List (t=5)

30 Hybrid Busy List - ocenaZalety: Dzięki alokacji zadań o podobnym czasie realizacji zwalnianie większych, spójnych obszarów na sieci Łatwiejsza alokacja zadań mieszanych Wady: Wymaga optymalizacji parametrów - złe dobranie parametrów HBL daje wyniki gorsze od BL

31 System eksperymentowaniaW celu porównania efektywności działania opisywanych wyżej algorytmów, wprowadziliśmy dwa główne wskaźniki jakości: średnie obciążenie sieci (SOS) moment zakończenia przetwarzania (MZP) Badania przeprowadzono pod kątem dwóch aspektów: Porównania efektywności rozważanych algorytmów dla zmiennej liczby zadań Zbadania wpływu rozmiaru zadań na wyniki algorytmów. – Poddaliśmy badaniom 4 grupy zadań: losowe, małe, średnie i duże.

32 System eksperymentowaniaBadania przeprowadziliśmy na stworzonym przez nas symulatorze sieci

33 Analiza wyników badań

34 Analiza wyników badań

35 Podsumowanie Stworzony przez nas algorytm HBL ujawnia swoje optimum dla zadań bardzo zróżnicowanych. System Intelligent Choice można zastosować również w innych algorytmach

36 Bibliografia [1] YUNG-KANG CHU, I-LING YEN, ROVER D.T. „Guiding Processor Allocation Estimated Execution Time for Mesh Connected Multiple Processor Systems” Annual Hawaii International Conference on System Sciences , 1995 [2] SAAD BANI M. “Efficient Processor Allocation Strategies for Mesh-Connected Multicomputers” February 2008, Information and Mathematical Sciences University of Glasgow [3] SRINIVASAN T., SESHADRI J., CHANDRASEKHAR A., SIDDHARTH J. B. “A Minimal Fragmentation Algorithm for Task Allocation in Mesh-Connected Multicomputers” Proceedings of the IEEE International Conference on AISTA, IEEE Press, Nov 2004, Luxembourg

37 Dziękujemy za uwagę Teraz jest czas na: Pytania

38 Dziękujemy za uwagę Teraz jest czas na: Pytania BRAWA!!!