ZAR = Zaawansowane Algorytmy rozproszone

co omówimy w zar01 ?

  1. rozproszony model obliczeń, synch i asynch
  2. symulator algorytmów symul

obliczenia z wieloma procesorami...

wiele procesorow, warianty modeli

nieformalna def modelu message passing...

mess pass nieformalnie
W modelu synch mamy rundy, w każdej rundzie każdy wierzchołek:

  1. wykonuje obliczenia lokalne („za darmo”)
  2. wymienia komunikaty z sąsiadami w grafie kom.
    (dokładniej: w i+1 rudzie otrzymuje kom wysłane w i-tej rundzie przez sąsiadów)

W modelu asynch nie ma rund, wysłane przez kraw komunikaty po jakimś czasie są dostarczane

Co jest celem alg rozproszonego? Odp: obliczenie „czegoś” w grafie kom, np. nakrótszej ścieżki między 1 a 5

Warianty modelu message-passing:

  1. graf kom może być: cyklem (ring), drzewem, pełnym grafem, …
  2. stopien synchronizacji: synch i asynch
  3. stopień symetrii, czy wierz v ma ID(v) czy też są nieodróżnialne?
  4. jednorodność (uniform), niejednorodny= wierz muszą znać „n” (liczbę wierz)

formalna def modelu message passing, asynch i synch...

form def modelu mess pass asynch
Co to znaczy, że dany algorytm asynch „A” działa ?
Odp: działa (oblicza to co trzeba) dla dowolnej dopuszczalnej egzekucji

Egzekucja jest dopuszczalna gdy:

  1. każdy wierz ma nieskoczenie wiele zdarzeń obliczeniowych,
  2. każdy wysłany komunikat jest dostarczany (kiedy?)

form def modelu mess pass synch
Co to znaczy, że dany algorytm synch „A” działa ?
Odp: działa dla każdej egz, która można podzielić na rundy...

Uwaga: alg asynch jest snych !!!

złożonośc algorytmów rozproszonych:

synch: liczba rund (=czas działania), liczba komunikatów
asynch: liczba komunikatów, czas (trudniejsze do zdef...)

symulator algorytmów (w modelu synch i asynch)

  1. tu jest szczegółowy opis symulatora - w wersji bez Jupytera!

model synchroniczny:

  1. wierzchołki sieci to fibery/"interpy logiczne Tcl-a"
  2. każdy fiber ma swój program (taki sam), napisany w j. Tcl
  3. runda jest realizowana przez przełączanie procesora z fibera na fiber (każdy wierz wykona fragment kodu = rundę)
    rundy uruchamia się ręcznie, po jednej, z innej komórki jupytera (lub z konsoli2c)
  4. granica między rundami jest zaznaczony w programie/algorytmie przez cmd "fiber yield"
    komenda ta przełącza procesor na następny fiber
  5. jest możliwość wysyłania/czytania komunikatów do/od sąsiadów przy pomocy cmd "wyślij" i "czytaj"
    istnieje także tablica kom() zawierająca komunkaty wysłane od sąsiada w poprzedniej rundzie
    np. kom(0), kom(1) zawierają komunkaty z połaczeń nr 0 i 1

model asynchroniczny:

  1. nie ma rund; zamiast tego mamy:
    zdarzenia obliczeniowe (cmd "fiber switchto")
    zdarzenia dostarczenia komunikatu (cmd "dostarczKom")
    uwaga: oba typu zdarzeń wywoływane są z innej komórki jupytera (lub z konsoli2c)
  2. zdarzenie obliczeniowe w programie/algorytmie wierz kończy się przez cmd "fiber switchto main"
  3. wysyłanie i odbieranie komunikatów podobnie jak w modelu synch
  4. cmd "pokazKom" pokazuje stan połączeń

symulator synch - przykład

In [1]:
## przykład użycia symulatora synch w jupyterze...
# + ten kod nalyży wykonać JEDEN raz !!!
# + jeśli chcemy zmodyfikować coś w kodzie, to należy "restartować kernel"
# + rundy uruchamiamia się przy pomocy następnej komórki
#

# ladowanie tkinter pod python3...
import tkinter; t=tkinter.Tcl()

t.eval("""
source symul_lib.tcl

# tworzymy graf komunikacyjny (w tym wypadku cykl)
set liczbaWierz 5
set sasiedzi(0) {4 1}
set sasiedzi(1) {0 2}
set sasiedzi(2) {1 3}
set sasiedzi(3) {2 4}
set sasiedzi(4) {3 0}
  # ^ numery połączeń zależą od kolejności id na liście sąsiadów

fiber create $liczbaWierz run

fiber_iterate { # kod wykona się we wszystkich fiberach
proc run {} {
  global id run kom; # zmienne globalne dostępne we wszystkich fiberach

  if {$id==0} {wyslij 1 0}
  fiber yield; # oznacza koniec rundy

  while {$run} { # zmienna run pozwala zakonczyc dzialanie symulacji!!
    if {$kom(0)!=""} {
      set x $kom(0)
      incr x
      wyslij 1 $x
    }
    fiber yield; # oznacza koniec rundy
  }
}
}

Inicjalizacja; # koniecznie trzeba to wywolac!!!

proc _puts s {append ::_ "$s\n"}; # specjalnie dla jupyter-a...

set licz_rund 1
proc wizualizacja {} {
  global licz_rund
  _puts "--- $licz_rund ---"; incr licz_rund
  #fiber_iterate {_puts "$id: kom0=$kom0, kom1=$kom1"}
  #fiber_iterate {_puts "$id: kom(0)=$kom(0), kom(1)=$kom(1)"}
  fiber_iterate {_puts "$id, $id_los: $kom(0), $kom(1)"}
}

""")
Out[1]:
''
In [19]:
# uruchomienie pojedynczej rundy...
print(t.eval("""
set _ ""; # można zakomentować...
fiber yield; runda; wizualizacja; set _
"""))

--- 18 ---
0, 440: , 
1, 590: , 
2, 321: , 
3, 339: 17, 
4, 67: ,
In [20]:
# wyswietla opisy błędów w fiberach (jeśli jakieś są)
print(t.eval('fiber error'))

{} {} {} {} {}

symulator asynch - przykład

In [2]:
## przykład użycia symulatora Asynch w jupyterze...
#

# ladowanie tkinter pod python3...
import tkinter; t=tkinter.Tcl()

t.eval("""
source symul_lib.tcl

# tworzymy graf komunikacyjny (w tym wypadku cykl)
set liczbaWierz 5
set sasiedzi(0) {4 1}
set sasiedzi(1) {0 2}
set sasiedzi(2) {1 3}
set sasiedzi(3) {2 4}
set sasiedzi(4) {3 0}
  # ^ numery połączeń zależą od kolejności id na liście sąsiadów

fiber create $liczbaWierz run

fiber_iterate {
proc run {} {
  global id id_los run kom

  wyslij 1 $id_los
  fiber switchto main; # oznacza koniec zdarzenia obliczeniowego

  while {$run} {
    if {$kom(0)!=""} {
      wyslij 1 [czytaj 0]
    }
    fiber switchto main; # oznacza koniec zdarzenia obliczeniowego
  }
}
}

InicjalizacjaAsynch; # koniecznie trzeba to wywolac!!!

proc _puts s {append ::_ "$s\n"}; # specjalnie dla jupyter-a...

""")
Out[2]:
''
In [3]:
print(t.eval('set _ ""; pokazKom; set _'))

0,  92: 0/ , 1/ , 0// , 1// , 
1, 567: 0/ , 1/ , 0// , 1// , 
2, 836: 0/ , 1/ , 0// , 1// , 
3, 825: 0/ , 1/ , 0// , 1// , 
4, 651: 0/ , 1/ , 0// , 1// ,
In [4]:
t.eval("""
fiber switchto 0; # generujemy zdarzenie obl, args: ID
""")
Out[4]:
''
In [8]:
t.eval("""
dostarczKom 1 0; # generujemy zdarzenie dost kom, args: ID nr_połączenia
""")
Out[8]:
'0'

Zadania

Uwaga: zadania można robić bezp w jupyterze LUB zewn symulatorem (w konsoli2c)

ZADANIE 1
Zaimplementuj algorytm synchroniczny obliczający max i min ID w cyklu zorientowanym;
te liczby mają być znane na wsz wierz po zakończeniu działania;
założenie: jest znany (pojedynczy) lider w cyklu (może to być wierz z id = 0)
algorytm ma używać min. liczby komunikatów
oszacuj także liczbę rund (czyli czas działania alg)
jako ID uzywaj zm id_los

ZADANIE 2
Zaimplementuj algorytm synchroniczny obliczający max i min ID w cyklu zorientowanym;
te liczby mają być znane na wsz wierz po zakończeniu działania;
w przeciwieństwie do poprzedniego zadania lider nie jest znany;
algorytm ma używać min. liczby komunikatów

ZADANIE 3
Zaimplementuj algorytm synchroniczny obliczający 2-kolorowanie-wierzchołkowe cyklu zorientowanego
tj kolejne wierz powinny mieć kolory: czerwony, niebieski, czerwony, niebieski, ...
(cykl musi mieć parzystą długość)
założenie: jest znany (pojedynczy) lider w cyklu (może to być wierz z id = 0)

ZADANIE 4
Zaimplementuj algorytm synchroniczny obliczający 2-kolorowanie-wierzchołkowe cyklu zorientowanego
jak w poprzednim zadaniu, ale tym razem NIE mamy lidera...
prosty sposób na obliczenie lidera możesz wywnioskować z poniższego rysunku:
LE w cyklu n^2
Wskazówka do zadania 4: jeśli łączymy dwa algorytmy, wybór lidera i 2-kolorowanie,
to trzeba się zastanowić, jak ograniczyć mieszanie się komunikatów tych alg!
można to zrobić w dziedzinie czasu lub dodać prefiks rozróżniający do komunikatów obu alg...

In [ ]:
""