Algoritmi Paralel şi Distribuit Stabilirea Topologiei (PDF)

Algoritmi Paraleli și Distribuiți Stabilirea Topologiei Prof. Ciprian Dobre [email protected]  Difuzarea mesajelor folosind sondaje typedef tip_arb int[1:N,1:N]; chan sondaj[1:N](tip_arb,tip_mesaj); const int inițiator = indexul nodului inițiator;...

Algoritmi Paraleli și Distribuiți Stabilirea Topologiei Prof. Ciprian Dobre [email protected]  Difuzarea mesajelor folosind sondaje typedef tip_arb int[1:N,1:N]; chan sondaj[1:N](tip_arb,tip_mesaj); const int inițiator = indexul nodului inițiator; process Nod[p=1 to N]{ tip_arb arb, T; tip_mesaj m; bool top[1:N,1:N]; if (inițiator == p) { calculeaza T pe baza top; m = mesaj_de_transmis top este o matrice cu } else receive sondaj[p](arb,m) topologia arborelui for [q = 1 to N st q este fiul lui p in arb] send sondaj[q](arb,m); } Numărul de mesaje = 𝑁 − 1  Difuzarea mesajelor folosind sondaje Inițiator T Matrice de adiacență T T 1 2 1 T 2 T 3 T 4 T 5 T 6 7 8 9 10 11 12 13 14 15 3 T T T 4 T T T 5 T T T 6 T T T 7 T T T 8 T 9 T 10 T 11 T 12 T 13 T T T T T 14 T 15 T T  Difuzarea mesajelor prin inundare chan sondaj[1:n](tip_mesaj); const int inițiator = indexul nodului inițiator; process Nod[p=1 to n]{ bool leg[1:n] = vecinii_lui_p; int num = numărul_vecinilor, răspunsuri = num; tip_mesaj m; if (p inițiator) { receive sondaj[p](m); răspunsuri = răspunsuri – 1; else m = mesaj_de_transmis; Numărul de mesaje = for [q = 1 to n st leg[q]] 2𝑚 send sondaj[q](m) (m = numărul legăturilor) for [q = 1 to răspunsuri] receive sondaj[p](m) }  Difuzarea mesajelor prin inundare S Inițiator S S S S S S S  Stabilirea topologiei unei reţele de procese Definiţii Colecție de procese Nod(p:1..N) Vecinii nodului p leg[1:N]:  𝑙𝑒𝑔 𝑞 = 𝑇𝑅𝑈𝐸dacă q este vecin cu p,  altfel 𝑙𝑒𝑔 𝑞 = 𝐹𝐴𝐿𝑆𝐸. Relație simetrică:  pentru p, 𝑙𝑒𝑔 𝑞 = 𝑇𝑅𝑈𝐸 pentru q, 𝑙𝑒𝑔 𝑝 = 𝑇𝑅𝑈𝐸 Problema Topologia reprezentată prin matricea de adiacenţe:  𝑡𝑜𝑝 𝑖, 𝑗 = 𝑇𝑅𝑈𝐸, dacă i este vecin cu j  𝑡𝑜𝑝 𝑖, 𝑗 = 𝐹𝐴𝐿𝑆𝐸, în caz contrar. Calculată pe baza cunoştinţelor locale  pentru orice p,q: 1 ≤ 𝑝, 𝑞 ≤ 𝑁 ∶ 𝑡𝑜𝑝 𝑝, 𝑞 = 𝑙𝑒𝑔𝑝 [𝑞] Algoritmul pulsatiilor  Algoritmul pulsaţiilor Fiecare proces calculează singur topologia, folosind informaţiile provenite de la vecini Fiecare nod transmite vecinilor matricea sa de adiacenţă, top şi primeşte matricea de adiacenţă a fiecărui vecin  după un rund complet, fiecare nod va dispune de informaţii de la nodurile vecine (figura stg. pentru nodul g)  După două runde complete, orice nod va avea informaţii de la noduri aflate la distanţa 2 (figura dr.), etc.  Dupa r runde sunt completate liniile din top corespunzătoare nodurilor q aflate la o distanţă