Algoritmi Paraleli și Distribuiți - C06_ComunicareaPrinMesaje PDF

Algoritmi Paraleli și Distribuiți Comunicarea prin mesaje. Complexitatea algoritmilor distribuiți Prof. Ciprian Dobre [email protected] 1. Comunicarea prin mesaje  Transmiterea de mesaje Îndeplinește cele două funcții:  comu...

Algoritmi Paraleli și Distribuiți Comunicarea prin mesaje. Complexitatea algoritmilor distribuiți Prof. Ciprian Dobre [email protected] 1. Comunicarea prin mesaje  Transmiterea de mesaje Îndeplinește cele două funcții:  comunicarea - datele ajung de la transmiţător la receptor  sincronizarea - un mesaj nu poate fi recepţionat înainte de a fi transmis Canalele sunt obiectele puse în comun de procese Programe distribuite Comunicare asincrona prin mesaje  Comunicarea asincronă prin mesaje Modelul Canalele păstrează ordinea mesajelor Canalele nu pierd mesajele canalele sunt cozi FIFO de mesaje, de capacitate nelimitata operaţia send nu este blocantă operaţia receive este blocantă Declaraţie – forma generală chan nume_canal (tip1 id1,..., tipn idn) Grup indexat de canale chan rezultat [1:n](int) Operaţii send nume_canal (expresie1,..., expresien) receive nume_canal (variabila1,..., variabilan) empty (nume_canal)  Exemplu - Filtru chan input (char), output (char [1:Maxl]); process car_linii{ char line[1:Maxl]; int i=1; while (true) { receive input (line[i]); while (line[i] CR and i < Maxl) { i = i + 1; receive input (line[i]); } send output (line); i = 1; } } Modelul Replicated Workers  Integrare numerica fb fb fa fa a b a m b ▪ Stanga – varianta secventiala ‒ calcul iterativ - la fiecare pas se dubleaza numarul de subintervale ‒ se termina cand diferenta intre doua valori succesive este acceptabila ▪ Dreapta – varianta distribuita ‒ un proces primeste un subinterval [a,b] si aria corespunzatoare ‒ imparte intervalul in doua sub-intervale [a.m], [m,b] si calculeaza ariile ‒ compara suma celor doua arii cu aria primita ‒ continua calculul separat pe cele doua subintervale, daca este cazul  Replicated workers Lucru(1) rezultat Administrator sac Lucru(n)  Exemplu - Replicated Workers (2) chan sac (real a, b, fa, fb, aria); chan rezultat (real a, b, aria); process Administrator{ real xl, xr, yl, yr, a, b, aria, total: real; yl = f(xl); yr = f(xr); aria = (yl + yr) * (xr - xl) / 2; send sac(xl, xr, yl, yr, aria); while (nu s-a calculat toata aria) { receive rezultat (a, b, aria); total = total + aria; marchează intervalul [a, b] terminat; } }  Exemplu - Replicated Workers (3) process Lucru[i=1 to n]{ real a, b, m, ya, yb, ym; real ariaSt, ariaDr, ariaTot, dif; while (true) { receive sac (a, b, ya, yb, ariaTot); m = (a + b) / 2; ym = f(m); calculează ariaSt și ariaDr; dif = ariaTot - ariaSt - ariaDr; if (dif mic) send rezultat (a, b, ariaTot); else { send sac (a, m, ya, ym, ariaSt); send sac (m, b, ym, yb, ariaDr); } } } Comunicare sincrona prin mesaje  Comunicarea sincrona prin mesaje Modelul Caracteristici similare cu comunicarea asincrona Diferenta: si operaţia send este blocantă – transmitatorul se blocheaza pana cand mesajul este receptionat Operaţii synch_send nume_canal (expresie1,..., expresien) receive nume_canal (variabila1,..., variabilan) empty (nume_canal) Neajunsuri reduce concurenta  Exemplu – comunicare producator / consumator chan prodcons (real); process prod { real date[n]; for [i = 1 to n] { calculeaza date[i]; synch_send prodcons (date[i]); } } process cons { real buf[n]; for [i = 1 to n] { receive prodcons (buf[i]); prelucreaza datele primite; } } 2. Complexitatea algoritmilor distribuiți Modelul Foster  Modelul Foster 0 1 2 3 4 5 6 7 O Calcul Comunicare Inactiv (Foster 1995)  Timpul total de execuţie Definiţie  Timpul scurs de la începerea execuţiei primului proces până la terminarea execuţiei ultimului proces. 𝑇 = 𝑓 ( 𝑁, 𝑃, 𝑈, … ) = 𝑇𝑗𝑐𝑜𝑚𝑝 + 𝑇𝑗𝑐𝑜𝑚𝑚𝑢𝑛 + 𝑇𝑗𝑖𝑑𝑙𝑒 1 = ∗ ( σ𝑃−1 𝑖=0 𝑇 𝑖 𝑐𝑜𝑚𝑝 + σ 𝑃−1 𝑖 𝑖=0 𝑇 𝑐𝑜𝑚𝑚𝑢𝑛 + σ 𝑃−1 𝑖 𝑖=0 𝑇 𝑖𝑑𝑙𝑒 ) 𝑃 1 = ∗ (𝑇𝑐𝑜𝑚𝑝 + 𝑇𝑐𝑜𝑚𝑚𝑢𝑛 + 𝑇𝑖𝑑𝑙𝑒) 𝑃  Timpul de calcul - 𝑇𝑐𝑜𝑚𝑝 Depinde de:  dimensiunea problemei N  numărul de task-uri sau procesoare  caracteristicile procesoarelor şi memoriei Exemplu:  scalarea dimensiunii problemei sau a numărului de procesoare poate modifica performanța cache-ului sau eficacitatea pipelining-ului procesorului  Timpul de comunicare – 𝑇𝑐𝑜𝑚𝑚𝑢𝑛 (1) Timpul petrecut cu transmiterea - recepţia de date Tipuri:  inter-procesor  intra-processor Presupunere: au costuri comparabile 𝑇𝑚𝑠𝑔 = 𝑡𝑠 + 𝑡𝑤 𝐿 Machine 𝒕𝒔 (µs) 𝒕𝒘(µs) IBM SP2 40 0.11 Intel DELTA 77 0.54 T = time Intel Paragon 121 0.07 Meiko CS-2 87 0.08 𝒕𝒘 = 𝒄𝒐𝒔𝒕/𝒘𝒐𝒓𝒅 nCUBE-2 154 2.4 Thinking 82 0.44 Machines CM-5 Workstations on 1500 5.0 Ethernet 𝒕𝒔 = 𝒔𝒕𝒂𝒓𝒕𝒖𝒑 𝒄𝒐𝒔𝒕 Workstations on 1150 1.1 FDDI L = message length  Timpul de comunicare – 𝑇𝑐𝑜𝑚𝑚𝑢𝑛 (1) Măsurători experimentale: timp dus-întors pentru mesaje (RTT) 10000 Ethernet FDDI Paragon 8000 SPI Timp (µs) 6000 4000 2000 0 0 1000 2000 3000 4000 5000 Dimensiune mesaj (octeți)  Timpul idle - 𝑇𝒊𝒅𝒍𝒆 Datorită:  lipsei calculelor → load balancing  lipsei datelor → overlapping computation and communication P1 P2 P1 P2 t t+2 t+4 t+6 t+8 t+10 (a) (b)  Model revizuit pentru cost comunicare Model comunicare simplu: Tmsg = ts + twL Competiţie pentru bandă: Tmsg-b = ts + twSL S = număr de procesoare care comunică concurent pe acelaşi canal (și în același sens) (a) S=1 P0 P1 P2 P3 P0 P1 P2 P3 (b) S=2 P0 P1 P2 P3 (c) S=1  Exemplu – Sequential Floyd I[i,j]0 = 0, daca i == j I[i,j]0 = cost(i,j), dacă există muchie și i != j I[i,j]0 = MAX, altfel for [k = 0 to N – 1] for [i = 0 to N – 1] for [j = 0 to N – 1] I[i,j]k+1 = min(I[i,j]k, I[i,k]k + I[k,j]k) Durata unei iterații T = tc N 3  Exemplu – Parallel Floyd 1 (1) Bazat pe o descompunere uni-dimensională pe rânduri a matricei I (algoritmul poate folosi cel mult P procesoare, P