IV100-Paralelní a distribuované výpočty pěkně v klidu... (část 1)

Původně jsem si tento "manuál pro blbce" psal pro sebe majíc se za jednoho z "tupějších", který hned jen tak všechno napoprvé na přednášce nepochopí. Nicméně ukázalo se, že by i jiní uvítali, kdyby byla problematika okolo paralelních a distribuovaných systémů průhlednější, tak začínám psát tento seriál veřejně. Neberte to jako nějakou beletrii, spíš jako poznámky z přednášek a výpisy a postřehy z různých zdrojů na internetu.

Distribuovaný systém

Distribuovaný systém je síť autonomních procesů.
Síť/graf budeme značit G=(V,E), kde V jsou procesy/uzly grafu, E jsou kanály/hrany.
Dvě základní komunikační paradigmata distribuovaných systémů jsou posílání zpráv a sdílení proměnných. My budeme uvažovat pouze posílání zpráv.
Asynchronní komunikace znamená, že posílání a příjímání zprávy jsou nezávislé události.
Naproti tomu, v případě synchronní komunikace zasílání a příjem zprávy jsou koordinovány do samostatné události -zaslání zprávy je povoleno až když je cíl ji přijmout.

Přechodové systémy

Globální stav distribuovaného algoritmu nazýváme konfigurace.
Konfigurace se rozvíjí do diskrétních kroků, zvaných transakce.

Transakční systém se zkládá z:
-množiny C všech konfigurací
-binární přechodové relace → nad C
-množiny I <= C počátečních konfigurací

γ je terminál, pokud neexistuje přechod γ→δ pro každé δ z C.

Vykonání (execution) je sekvence γ₀,γ₁,γ₂,... (nekonečná nebo končící v nějaké terminální konfiguraci) taková, že:
γ₀I a
γ_i→γ_i+1 pro i>=0

δ je dosažitelná z γ pokud existuje sekvence γ₀,γ₁,γ₂,..,γ_k=δ, kde γ_i→γ_i+1 pro každé 0<=i<k.
δ je dosažitelná jestliže je dosažitelná z γI.

Stavy a události

Konfigurace (neboli globální stav) distribuovaného algoritmu je souhrnem všech lokálních stavů a jejich komponent. Transakce je spojená s událostí (nebo v případě synchronní komunikace se dvěma událostmi) a jejími komponenty.

Lokální algoritmus procesu se zkládá z:
-množiny stavů Z
-množiny počátečních stavů I
-relace ⁱ interních událostí (c,d)
-relace ^s send událostí (c,m,d)
-relace ^r receive událostí (c,m,d)
(c,d-stavy, m-zpráva/message)

"Tvrzení" v kontextu distr. a paralel. systémů

Tvrzení (assertion) je predikát na množině konfigurací algoritmu.

Tvrdíme, že algoritmus má vlastnost bezpečnosti (safety property), pokud je pravdivý v každé své konfiguraci každého vykonání. (pro lidi: Bezpečnost je vlastnost, která říká, že algoritmus by neměl dělat nic špatného a to nikdy).
Tvrdíme, že algorigmus má vlastnost životnosti (liveness property), pokud je pravdivý v nějaké své konfiguraci každého vykonání. (pro lidi: Životnost je vlastnost, která říká, že v průběhu vykonávání algoritmu by se něco dobrého mohlo stát. Jinými slovy: pokud počítá, je ještě naděje...).

Příklad-meziprocesová komunikační služba jako je TCP:
TCP zajišťuje, že zprávy vyměněné mezi dvěma procesy se neztratí, neduplikují a jsou přijaty přijímajícím ve správném pořadí v takovém, v jakém byly odeslány. Fakt, že zpráva se neztratí je vlastností životnosti. Fakt, že zprávy nejsou duplikovány ani přijaty v nesprávném pořadí je vlastností bezpečnosti.

Tvrzení P je invariant pokud:
-P(γ) pro všechny γI a
-jestliže γ→δ a P(γ), pak i P(δ).
Každý invariant je tedy bezpečnostní vlastností.

Nechť P,Q jsou tvrzení. Říkáme, že P je Q-derivát, jestliže:
-pro každé γI, jestli Q(γ) pak i P(γ)
{Q^P}→{Q implikuje P}

Následnost (Causality, Causal Order)

V každé konfiguraci asynchronního systému jsou události v různých procesech na sobě nezávislé.

Následnostjednotlivých událostí při vykonání je nejmenší transitivní relace taková,že:
jestliže a a b jsou událostmi stejného procesu a a se vyskutuje před b, potom ab a
jestliže a je událost send a b je odpovídající událost receive, pak ab.

Události a a b nazveme konkurentní, pokud neplatí, že ab a ani že ab.

Permutace událostí při vykonání, které respektují následnost, nemají vliv na výsledek vykonání. Tyto permutace dohromady tvoří výpočet (computation).

Všecha vykonání výpočtu začínají ve stejné konfiguraci a pokud jsou konečná, tak i ve stejné konfiguraci končí.

Logické hodiny

Logické hodiny jsou hodiny, které neberou v úvahu čas, ale vyjadřují následnost událostí při výpočtu.
Hodiny mapují události výpočtu k částečně setříděné množině tak, že ab => (a)<(b).

Lamportovy logické hodiny _L
(a) definuje jako délku nejdelší posloupnosti (b₁,...,b_k) takové, že b₁b₂ ...b_k=a

když b je interní nebo send událost,
a předcházející událost stejného procesu,
tak _L(b)= _L(a)+1

když r je receive událost,
i předcházející událost stejného procesu,
s odpovídající send událost,
tak _L(r)=max{ _L(i), _L(s)}+1

když a je první událost procesu, pak _L(a)=0

Floyd-Warshallův algoritmus

Floyd-Warshallův algoritmus slouží k nalezení všech nejkratších cest v grafu G, tedy nejkratších cest pro všechny dvojice uzlů grafu i,j.

Jako vstup algoritmu je zapotřebí tzv. matice sousednosti. Matice sousednosti grafu G o n uzlech je čtvercová matice W řádu n (=matice n krát n) definovaná následovně:
W[i,i]=0 (z uzlu i se do toho samého uzlu dostanu cestou délky 0)
W[i,j]=x když mezi uzly i a j je hrana s váhou/ohodnocením x
W[i,j]=nekonečno(v praxi např. hodně velké číslo) když mezi uzly i a j není hrana
Matice sousednosti se vygeneruje následovně:

n:=počet uzlů grafu G
for i:=1 to n do
    for j:=1 to n do
        if (i=j) then W[i,j]:=0
        else if existuje_hrana(i,j) then W[i,j]:=váha/ohodnocení hrany
                                    else W[i,j]:=nekonečno;
    done
done

Samotný Floyd-Warshall algoritmus pak tedy vypadá následovně:
Vstup: ohodnocený graf G reprezentovaný maticí sousedností W

n:=počet uzlů grafu G (řád matice W);
for k:=1 to n do
    for i:=1 to n do
        for j:=1 to n do
            W[i,j]:=min(W[i,j],W[i,k]+W[k,j]);
        done
    done
done

Výstup: matice W obsahující pro každou dvojici uzlů jejich minimální vzdálenost (délku nejkratší cesty)

Algoritmus má kubickou asymptotickou časovou složitost vzhledem k počtu vrcholů - O(n^3), což je vidět z toho, že jsou v sobě zanořeny 3 for cykly přes všechny uzly n.

Pokud už jsme předešlé algoritmy trochu vstřebali, tak je teď můžeme spojit a mírně modifikovat:

n:=počet uzlů grafu G
for i:=1 to n do
    for j:=1 to n do
        if (i=j) then { W[i,j]:=0 ; Nb[i,j]:=0 }
        else if existuje_hrana(i,j) then { W[i,j]:=váha/ohodnocení hrany; Nb[i,j]:=j }
                                    else { W[i,j]:=nekonečno; Nb[i,j]:=0 }
        for k:=1 to n do
            for i:=1 to n do
                for j:=1 to n do
                    if(W[i,k]+W[k,j]<W[i,j]) then { W[i,j]:=W[i,k]+W[k,j]; Nb[i,j]:=Nb[i,k] }
                done
            done
        done
    done
done

Výstup: matice W obsahující pro každou dvojici uzlů jejich minimální vzdálenost (délku nejkratší cesty) a také matice Nb obsahující pro každou dvojici uzlů i,j souseda uzlu i na nejkratší cestě k uzlu j

Touegův algoritmus

Distribuovaná verze Floyd-Warshallova algoritmu.
Předpoklady: Každý uzel od začátku zná:
-všechny své sousední uzly
-váhu/ohodnocení svých hran(odchozích kanálů)
-identity všech uzlů grafu
-pivoti musí být na všech uzlech vybíráni stejným způsobem