Algoritmi Paralelți èi Distribuițiăți (Algoritmi undă) PDF

Algoritmi Paraleli și Distribuiți Algoritmi undă Ciprian DOBRE [email protected]  Algoritmi undă În dezvoltarea algoritmilor distribuiți apar frecvent anumite tipuri de probleme generale pentru rețele de procese. R...

Algoritmi Paraleli și Distribuiți Algoritmi undă Ciprian DOBRE [email protected]  Algoritmi undă În dezvoltarea algoritmilor distribuiți apar frecvent anumite tipuri de probleme generale pentru rețele de procese. Rezolvate prin transmitere de mesaje după o schemă predefinită, dependentă de topologie care asigură participarea tuturor proceselor. Justifică tratarea lor izolată de alți algoritmi în care aceste scheme pot fi folosite.  Notiuni preliminare - configuratii Un program distribuit consta dintr-o colectie de procese secventiale comunicante Configuratie = Ansamblul starilor tuturor proceselor la un moment dat O operatie modifica starea unui proces, implicit configuratia O executie a programului poate fi modelata printr-o secventa de configuratii. Ex.1 Program distribuit = colectie a doua procese, initial a si b au valoarea 0 process P1{ int a =0; process P2{ int b =0; a = a+1;} b = b+1;} configuratia = ansamblul valorilor celor doua variabile modificate de procese → configuratia initiala este daca operatia primului proces se executa mai intai, configuratia devine O executie posibila = secventa de configuratii: ( , , )  Sisteme de tranziţii Un program distribuit poate fi modelat ca un sistem de tranziții:  Mulțimea tuturor stărilor (configurațiilor) posibile ale sistemului  Tranzițiile pe care sistemul le poate face între stări  Stările din care sistemul poate porni (inițiale) Formal, un sistem de tranziții este un triplet 𝑆 = (𝐶, →, 𝐼) 𝐶 este o mulțime de configurații → este relația de tranziție binară pe 𝐶 𝐼 este setul configurațiilor inițiale (o submulțime a lui 𝐶) O execuție a lui 𝑆 este o secvență maximală 𝐸 = 𝛾0 , 𝛾1 , 𝛾2 , … , unde 𝛾0 ∈ 𝐼 și 𝛾𝑖 → 𝛾𝑖+1 , 𝑝𝑒𝑛𝑡𝑟𝑢 𝑖 ≥ 0. O configurație terminală 𝛾 nu are succesor: ∄ 𝛿 astfel încât 𝛾 → 𝛿.  Sisteme de tranziţii (2) O secvență 𝐸 este maximală dacă:  Este infinită sau  Sfârșește într-o configurație terminală. Configurația 𝛿 este tangibilă din 𝛾 dacă există o secvență 𝜸𝟎, 𝜸𝟏, 𝜸𝟐, … , 𝜸𝒌 a.î.: 𝛾 = 𝛾0 δ = 𝛾𝑘 𝛾𝑖 → 𝛾𝑖+1 , 𝑝𝑒𝑛𝑡𝑟𝑢 𝑖 = 0, 𝑘 − 1 Un sistem distribuit constă dintr-o colecție de procese și un subsistem de comunicații. Convenții:  pentru sistem: tranziții și configurații  pentru proces: evenimente (interne / send,receive) și stări Unei execuții E îi corespunde o secventă de evenimente din diferite procese.  Sisteme de tranziţii (3) Pentru o execuție 𝐸, relația de ordine cauzală < este cea mai slabă relație care satisface:  dacă 𝒂 și 𝒃 sunt două evenimente diferite ale aceluiași proces și 𝒂 se produce înaintea lui 𝒃 atunci 𝒂 < 𝒃  dacă 𝒂 este un eveniment send, iar 𝒃 evenimentul receive corespunzător atunci 𝒂 < 𝒃  dacă 𝒂 < 𝒃 și 𝒃 < 𝒄 atunci 𝒂 < 𝒄 (< este tranzitivă). Dacă 𝒂 < 𝒃 și 𝒃 < 𝒂 atunci 𝑎 și 𝑏 sunt concurente. O execuție 𝐸 este echivalentă cu 𝐹 (𝐸~ 𝐹 ) dacă:  au aceeași colecție de evenimente (ordinea diferă)  evenimentele respectă aceeași relație de ordine cauzală  ultima configurație a lui 𝐸 coincide cu ultima configurație a lui 𝐹 Obs: două execuții echivalente pot să nu aibă aceleași configurații. Un calcul (computation) al unui algoritm distribuit este o clasă de echivalență (sub relația ~) a execuțiilor algoritmului.  Algoritmi undă (Wave algorithms) Schema de transmitere de mesaje:  dependentă de topologie  asigură participarea tuturor proceselor Algoritmii undă implementează astfel de scheme pentru:  difuzarea informației  realizarea unei sincronizări globale între procese  declanșarea unui eveniment în fiecare proces  calculul unei funcții în care fiecare proces participă cu o parte a datelor de intrare Proprietăți:  terminare – fiecare calcul este finit  decizie – fiecare calcul conține cel puțin un eveniment de decizie (decide)  dependență – în fiecare calcul, fiecare decide este precedat cauzal de un eveniment în fiecare proces  Definiții (1) Calcul (computation)  undă (wave) Categorii de procese: Inițiatori (starters) – primul eveniment este unul intern sau un send Neinițiatori (followers) – primul eveniment este un receive Clasificare: centralizare  algoritmi centralizați – un inițiator  algoritmi descentralizați – set arbitrar de inițiatori topologie  inel, arbore, clică etc.  fixă (nu se produc modificări topologice)  nedirecționată (canale bidirecționale); excepțiile menționate explicit  conectată (există o cale între oricare două procese)  Definiții (2) cunoștințe inițiale – exemple:  identitatea proprie (nume)  identitățile vecinilor  setul direcției (ordinea vecinilor) numărul de decizii (regulă = cel mult o decizie în fiecare proces)  un singur proces decide  toate decid  unele decid complexitate  număr de mesaje schimbate  număr de biți interschimbați  timpul necesar pentru un calcul  Noțiuni preliminare Sensul legăturilor Complexitatea comunicării într-un algoritm distribuit depinde de topologie, dar și de:  cunoașterea topologiei la nivelul fiecărui nod (topological awareness)  setul de direcții (sense of direction) ▪ muchiile incidente unui nod sunt etichetate cu direcția spre care conduc în rețea ▪ setul de etichete este același pentru fiecare nod ▪ mărimea setului depinde de topologie (2 pt. inel, 4 pt. tor, etc) ▪ trebuie respectată o condiție suplimentară de consistență  Noțiuni preliminare Sensul legăturilor (2) Inel:  2 direcții: Prec (precedent) și Urm (următor)  condiția de consistență: precedentul lui 𝒑 este 𝒒  următorul lui 𝒒 este 𝒑 Prec q Urm p  Noțiuni preliminare Sensul legăturilor (3) Clică:  𝑁 noduri de grad 𝑁 − 1  set 𝑑𝑖𝑟𝑒𝑐ții = {1, 2, … , N − 1}  condiția de consistență: direcția de la nodul 𝒊 la 𝒋 are sensul (𝒋 − 𝒊) 𝒎𝒐𝒅 𝑵  Noțiuni preliminare Sensul legăturilor (4) Hipercub:  pentru un hipercub 𝑛 dimensional  set 𝑑𝑖𝑟𝑒𝑐ț𝑖𝑖 = {0, … 𝑛 − 1}  condiția de consistență: două noduri (𝒃𝟎 , … , 𝒃𝒏−𝟏 ), (𝒄𝟎 , … , 𝒄𝒏−𝟏 ) legate prin muchie cu eticheta 𝒊 diferă doar în bitul 𝒊 0 3 1 2 2 0 3 1  Notație transmitere mesaje 1. transmitere prin adresare directă send ch[q] (mesaj)  unde q este identitatea unică, globală a canalului către receptor 2. transmitere prin adresare indirectă send ch[direcție] (mesaj)  unde direcție este locală procesului care execută operația send  identifică unul din canalele pe care procesul poate transmite Algoritm inel  Algoritmul inel fiecare proces are un vecin dedicat, Urm transmiterea folosește adresarea prin direcție (Urm, Prec) toate canalele selectate prin Urm formează un ciclu Hamiltonian algoritmul este centralizat:  inițiatorul trimite un token (jeton) care este pasat de fiecare proces de-a lungul ciclului până ajunge înapoi la inițiator;  inițiatorul ia apoi decizia  Algoritmul inel chan token[1..n](tok_type tok); process P[I]{ tok_type tok; send token[Urm](tok); receive token[I](tok); decide } process P[k=1 to n, kI] { tok_type tok; receive token[k](tok); send token[Urm](tok) } Număr de mesaje = n, Timp = n Algoritm arbore  Algoritmul arbore Se aplică:  unei topologii arbore  unei topologii arbitrare în care se cunoaște un arbore de acoperire Fiecare nod cunoaște identitatea proprie și identitățile vecinilor Mulțimea tuturor identităților este Ids Pentru fiecare proces, se folosesc variabilele locale  Vecini – mulțimea identităților vecinilor (q = identitatea procesului q)  rec[q] – true dacă procesul a primit un mesaj de la vecinul q Inițiatorii sunt toate nodurile frunză Algoritm:  fiecare proces trimite exact un mesaj  când un proces a primit un mesaj pe fiecare canal incident mai puțin unul (condiție îndeplinită inițial de frunze) el trimite un mesaj pe canalul rămas  când un proces a primit câte un mesaj pe toate canalele sale atunci decide  Algoritmul arbore (2) chan ch[1:n](int id, tok_type tok); process Proc[p = 1 to n]{ bool Vecini[1:n] = vecinii_lui_p; bool rec[1:n] = ([|n|] * false); int r = numar_vecini_p; tok_type tok; int id, q0; while (r > 1){ receive ch[p](id, tok); rec[id] = true; r = r - 1 } afla q0 : Vecini[q0] and NOT rec[q0]; send ch[q0](p, tok); receive ch[p](q0, tok); rec[q0] = true; decide } Număr de mesaje = N egal cu nr. procese , Timp = O(D)  Algoritmul arbore (3) exemplu de execuție p q (b) (c)(a) pnodurile șinodurile defrunză nivel q transmit intermediar transmit reciproc şi, după recepţie, decid transmit  Algoritmul arbore (4) Algoritmul "arbore" este un algoritm undă. 1. calcul finit  algoritmul foloseşte cel mult N mesaje → algoritmul atinge o configuraţie terminală 𝛾 după un număr finit de paşi. 2. în 𝛾, cel puţin un proces a executat un eveniment "decide“ 3. "decide" este precedat de un eveniment în fiecare proces 𝑇𝑝𝑞 𝑇𝑞𝑝 Subseturile 𝑇𝑝𝑞 şi 𝑇𝑞𝑝 p q Algoritm ecou  Algoritmul ecou se aplică unor topologii arbitrare este centralizat; există un singur inițiator, 𝐼 propus de Chang; prezentam versiunea mai eficientă Segall bazat pe inundarea rețelei cu mesaje tok  se stabilește un arbore de acoperire  mesaje tok sunt transmise înapoi spre rădăcină prin canalele arborelui de acoperire  Algoritmul ecou chan ch[1:n](int id, tik_type tok); const int I = id_initiator; process Proc(I){ bool Vecini[1:n] = vecinii_lui_I; int r = numar_vecini_I, id; tok_type tok; for [i=1 to n st Vecini[i]] send ch[i](I, tok); while (r > 0) { receive ch[I](id, tok); r = r – 1; } decide; }  Algoritmul ecou (2) process Proc[p=1 to n, p I]{ bool Vecini[1:n] = vecinii_lui_p; int r = numar_vecini_p, id, parinte; tok_type tok; receive ch[p](parinte, tok); r = r - 1; for [q=1 to n st Vecini[q] and q parinte) send ch[q](p, tok); while (r > 0) { receive ch[p](id, tok); r = r – 1; } send ch[parinte](p, tok) } 𝑴𝒆𝒔𝒂𝒋𝒆 = 𝟐 𝑬 , 𝑻𝒊𝒎𝒑 = 𝑶(𝑵)  Algoritmul ecou (3) exemplu de execuție 1 estedecide inițiator T T decide T T T T decide 4 T T 3 decide Nodul 1 Nodul 2 Nodul 3 Nodul 4 Vecini = {2} {1, 3, 4} {2, 4} {2, 3} părinte = 1 2 2 r = 1 0 0 2 3 0 2 1 2 1 0  Algoritmul fazelor (pulsatiilor, heartbeat, gossiping..)  Algoritmul fazelor algoritm descentralizat topologii arbitrare canale unidirecționale vecinii sunt: in-vecini și out-vecini procesele cunosc diametrul grafului 𝐷 (sau o valoare 𝐷′ > 𝐷) fiecare proces trimite exact 𝐷 mesaje fiecărui out-vecin mesajul 𝑖 + 1 este trimis fiecărui out-vecin numai după ce 𝑖 mesaje au fost primite de la fiecare in-vecin  Algoritmul fazelor chan ch[1:n](int id, tok_type tok); const int D = diametrul_retelei; process Proc[p = 1 to n] { bool in[1:n] = in-vecinii_lui_p; bool out[1:n] = out-vecinii_lui_p; int rec[1:n] = ([n] 0); int sent = 0; tok_type tok; int id;  Algoritmul fazelor (2) if (p este inițiator) { for [q = 1 to n st out[q]] send ch[q](p, tok); sent = sent + 1 } while (min(rec) < D) { receive ch[p](id, tok); rec[id] = rec[id] + 1; if (min(rec) >= sent and sent < D) { for [q=1 to n st out[q]] send ch[q](p, tok); sent = sent + 1; } } decide; } 𝐌𝐞𝐬𝐚𝐣𝐞 = 𝟐𝐃 𝐄 , 𝐮𝐧𝐝𝐞 𝐄 𝐞𝐬𝐭𝐞 𝐦𝐮𝐥ț. 𝐜𝐚𝐧𝐚𝐥𝐞𝐥𝐨𝐫 𝐧𝐞𝐝𝐢𝐫𝐢𝐣𝐚𝐭𝐞 (𝟐 𝐜𝐚𝐧𝐚𝐥𝐞 𝐝𝐢𝐫𝐢𝐣𝐚𝐭𝐞) 𝐓𝐢𝐦𝐩 = 𝟐𝐃  Algoritmul fazelor (3) exemplu de execuție D (diametrul rețelei) = 3 min(rec) 1 este>= min(rec) >=sent D inițiator T min(rec) min(rec)>= >=sent D anddecide sent < D T anddecide sent < D T T min(rec) min(rec)>= anddecide >=sent sent < D D 4 T 3 min(rec) min(rec)>= anddecide >=sent D sent < D Nodul 1 Nodul 2 Nodul 3 Nodul 4 rec = {2:3} {2:0} {2:2} {2:1} {1:0, 4:0} {1:1, {1:3, {1:2, 4:1} 4:2} 4:3} {2:1} {2:2} {2:3} {2:0} {3:3} {3:0} {3:1} {3:2} sent = 0 1 3 2 0 1 2 3 0 1 2 3 3 0 1 2  Algoritmul fazelor (4) Teoremă: Algoritmul "fazelor" este un algoritm undă 1. calcul finit fiecare proces trimite cel mult D mesaje prin fiecare canal ⇒ algoritmul atinge o configurație terminală 𝛾 după un număr finit de pași 2. în 𝛾, fiecare proces a executat un eveniment "decide" presupunem cel puțin un inițiator în 𝐶 (pot fi mai mulți) 2.1. fiecare proces a trimis cel puțin un mesaj 2.2. fiecare proces a decis 3. "decide" este precedat de un eveniment în fiecare proces  T. Algoritmul "fazelor" este un algoritm unda (1) calcul finit fiecare proces trimite cel mult D mesaje fiecarui out-vecin → algoritmul atinge o configuratie terminala γ intr-un calcul C cu numar finit de pasi (2) in γ, fiecare proces a inregistrat un eveniment "decide" presupunem cel putin un initiator in calculul C (pot fi mai multi) (2.1) fiecare proces a trimis cel putin un mesaj if (p este initiator){ for [q = 1 to n st out[q]]{ send ch[q](p, tok); sent = sent+1;} while (min(rec) < D){ receive ch[p](id, tok); rec[id] = rec[id]+1; if (min (rec) >= sent and sent < D){ for (q=1 to N st out[q]] send ch[q](p, tok); daca p ne-initiator: sent = 0 → cand p sent = sent+1;} primeste primul mesaj, transmite unul … tuturor out-vecinilor  (2.2) In configuratia terminala γ fiecare proces a decis while (min(rec) < D){ receive ch[p](id, tok); rec[id] = rec[id]+1; if (min (rec) >= sent and sent < D){ for (q=1 to N st out[q]] send ch[q](p, tok); sent = sent+1;} } decide; Demonstram ca orice proces iese din ciclu, adica min(rec) = D , deci nu exista in-vecin care sa-i fi trimis mai putin de D mesaje Fie p procesul cu cel mai mic sentp in γ ➔ Yq sentq >= sentp (1) In particular, se aplica pentru toti in-vecinii q ai lui p In γ, toate mes. trimise de q sunt recept. de p ➔ sentq = recp[q] (2) (1)&(2) → minq (recp[q]) >= sentp conditia din if este semi-indeplinita ➔ sentp =D; altfel p ar fi trimis mesaje suplimentare la ultima receptie sentq =D Y q ➔ recp[q] =D pentru orice canal qp min(rec) = D ➔ fiecare proces a iesit din ciclu si a decis  (3) "decide" este precedat de un eveniment in fiecare proces Ne referim la decizia din procesul p D este diametrul → pentru orice q exista o cale la p cu lungime