Simulare pe Sisteme în Domeniul Calcul Paralel

Curs
7/10 (1 vot)
Domeniu: Calculatoare
Conține 1 fișier: doc
Pagini : 15 în total
Cuvinte : 10012
Mărime: 63.14KB (arhivat)
Cost: Gratis

Extras din document

Specificarea problemelor.

O problemă se poate specifica la nivelul interfeţei dintre algoritmul ce o rezolvă şi mediul extern.

O specificare de problemă P este o mulţime de evenimente de intrare in(P), o mulţime de evenimente de ieşire out(P) (cele două mulţimi constituind interfaţa lui P) şi o mulţime seq(P) de secvenţe admisibile de evenimente de intrare şi evenimente de ieşire (care precizează interleavingurile permise dintre intrări şi ieşiri).

Fiecare eveniment de intrare sau de ieşire are un nume şi poate avea asociate date ca parametri.

Exemplu. Problema excluderii mutuale pentru n procesoare:

- evenimente de intrare: Ti, Ei, 0 i n-1, unde

• Ti indică faptul că utilizatorul i doreşte să încerce să intre în secţiunea critică.

• Ei indică faptul că utilizatorul i doreşte să iasă din secţiunea critică.

- evenimentele de ieşire: Ci, Ri 0 i n-1, unde

• Ci indică faptul că utilizatorul i poate acum să intre în secţiunea critică.

• Ri indică faptul că utilizatorul i poate acum să intre în secţiunea remainder.

- o secvenţă a acestor evenimente este admisibilă dacă pentru i:

1. |i ciclează (Ti,Ci,Ei,Ri)

2. ori de câte ori Ci apare în , atunci j eveniment asociat lui j ce apare în înaintea lui Ci nu este lj.

(Condiţia 1 arată că utilizatorul şi algoritmul interacţionază propriu; ea impune utilizatorului un mod corect de comportare. Condiţia 2 afirmă că nu  doi utilizatori simultan în secţiunea critică).

Sisteme de comunicaţie

În problemele de simulare vom fi interesaţi în implementarea unor anumite tipuri de sisteme de comunicaţie între procesoare pe baza unor primitive.

Aceste sisteme de comunicaţie vor fi descrise cu ajutorul unei specificaţii de problemă.

Exemple.

1. Transmiterea asincronă de measej point-to-point

interfaţa:

- sendi (M): eveniment de intrare asociat procesorului pi care trimite o mulţime M (eventual vidă) de mesaje. Fiecare mesaj include o indicaţie a trimiţătorului şi a destinatarului; există cel mult un mesaj pentru fiecare destinatar şi perechea transmiţător-destinatar trebuie să fie compatibilă cu topologia sistemului.

- recvi(M): eveniment de ieşire asociat procesorului pi în care o mulţime M de mesaje este primită. Fiecare mesaj trebuie să-l aibă pe pi ca destinatar.

mulţimea secvenţelor admisibile.

Fie o secvenţă de evenimente de intrare şi ieşire.

Notăm cu R mulţimea tuturor mesajelor ce apar în toate evenimentele recvi(M) din şi cu S mulţimea tuturor mesajelor ce apar în toate evenimentele sendi(M) din . Există o funcţie K:RS care asociază fiecărui mesaj din R un mesaj cu acelaşi conţinut din S a.î.:

- Integrity: K este bine definită. Orice mesaj primit a fost în prealabil trimis. Nu este permisă corupţia mesajelor.

- No duplicates: K este injectivă. Nici un mesaj nu este primit mai mult de o dată.

- Liveness: K este surjectivă. Orice mesaj trimis va fi primit.

Observaţie. Aceste proprietăţi vor fi modificatecând se vor considera şi defecţiunile în sistem.

Broadcast asincron

interfaţa (la un sistem cu broadcast asincron de bază).

- bc-sendi(m): eveniment de intrare în care procesorul pi, trimite un mesaj m tuturor procesoarelor.

- bc-recvi(m,j): eveniment de ieşire în care procesorul pi primeşte mesajul m, în prealabil difuzat de pj.

mulţimea secvenţelor admisibile. Fie o secvenţă de evenimente de intrare şi de ieşire.

Există K o aplicaţie care asociază fiecărui bc-recvi(m,j) din un evniment precedent bc-sendj(m) a.î.

- Integrity: K este bine definită (orice mesaj primit a fost în prealabil trimis).

- No duplicates: Pentru ficare procesor pi 0 i n-1, restricţia lui K la evenimentele bc-recvi este injectivă (nici un mesaj nu este primit mai mult de o dată de un procesor).

- Liveness: Pentru ficare procesor pi 0 i n-1, restricţia lui K la evenimentele bc-recvi este surjectivă (orice mesaj trimis este primit de fiecare procesor).

Observaţie: Din nou s-a presupus că nu există defecţiuni.

Procese

Pe fiecare procesor se vor executa bucăţi de cod care implementează sistemul de comunicaţie dorit. Deci nu va mai fi corect să identificăm "algoritmul" cu procesorul, pentru că avem procese multiple ce se execută pe acelaşi procesor. Vom folosi noţiunea de nod iar sistemul de comunicaţie va fi reprezentat ca o cutie neagră în care este implementată o "stivă de protocoale".

Un sistem este o colecţie de noduri p0,...,pn-1, un sistem de comunicaţie C şi un mediu extern E.

C şi E nu sunt explicit modelate ca procese. Ele vor fi date ca specificaţii de probleme, care impun condiţii asupra comportării lor.

În fiecare nod există o stivă de nivele cu acelaşi număr de nivele. Fiecare nivel interior comunică cu cele două nivele adiacente. Nivelul de jos comunică cu sistemul de comunicaţie şi nivelul de sus cu mediul extern.

Fiecare proces este modelat ca un automat cu o mulţime (posibil infinită) de stări şi o mulţime de stări iniţiale. Tranziţiile dintre stări sunt declanşate de apariţia evenimentelor procesului. Un proces are patru tipuri de evenimente:

1. intrări din nivelul de deasupra (sau nivelul exterior dacă este nivelul de sus).

2. ieşiri către nivelul de deasupra.

3. intrări din nivelul de dedesubt (sau sistemul de comunicaţii dacă este nivelul de jos) .

4. ieşiri către nivelul de dedesubt.

Evenimentele de tipul 1 şi 2: interfaţa – top a procesului

Evenimentele de tipul 3 şi 4: interfaţa – bottom a procesului.

Un eveniment este activat într-o stare a procesului dacă există o tranziţie din acea stare, etichetată cu acel eveniment.

Un eveniment de intrare poate fi activat în orice stare a procesului.

Evenimentele de ieşire sunt activate de funcţia de tranziţie a procesului.

Intrările din mediul extern şi din sistemul de comunicaţii sunt intrările nodului.

Procesele de pe un singur nod interacţionează a.î. numai un număr finit de evenimente (diferit de intrările nodului) sunt activate de o intrare în nod.

Preview document

Simulare pe Sisteme în Domeniul Calcul Paralel - Pagina 1
Simulare pe Sisteme în Domeniul Calcul Paralel - Pagina 2
Simulare pe Sisteme în Domeniul Calcul Paralel - Pagina 3
Simulare pe Sisteme în Domeniul Calcul Paralel - Pagina 4
Simulare pe Sisteme în Domeniul Calcul Paralel - Pagina 5
Simulare pe Sisteme în Domeniul Calcul Paralel - Pagina 6
Simulare pe Sisteme în Domeniul Calcul Paralel - Pagina 7
Simulare pe Sisteme în Domeniul Calcul Paralel - Pagina 8
Simulare pe Sisteme în Domeniul Calcul Paralel - Pagina 9
Simulare pe Sisteme în Domeniul Calcul Paralel - Pagina 10
Simulare pe Sisteme în Domeniul Calcul Paralel - Pagina 11
Simulare pe Sisteme în Domeniul Calcul Paralel - Pagina 12
Simulare pe Sisteme în Domeniul Calcul Paralel - Pagina 13
Simulare pe Sisteme în Domeniul Calcul Paralel - Pagina 14
Simulare pe Sisteme în Domeniul Calcul Paralel - Pagina 15

Conținut arhivă zip

  • Simulare pe Sisteme in Domeniul Calcul Paralel.doc

Alții au mai descărcat și

AutoCad

APERTURE - controleazã mãrimea cursorului selector, caracteristic modului object snap. ARC - traseazã un arc de cerc de orice dimensiune. A -...

Biblioteca de Șabloane Standard

Biblioteca de Sabloane Standard (STL) asigura o abstractizare standardizata a datelor prin intermediul containerelor si o abstractizare procedurala...

Clase Derivate

1. Clase derivate. Prin mostenire, atributele unei clase de baza sunt transmise unor clase derivate. Derivarea permite definirea unor clase noi,...

Clase în Java

Clase pentru miniaplicatii Miniaplicatiile constituie extensii ale unei clase deja existente java.applet.Applet. Structura clasei unui applet...

Clase

1. Programare procedurala –Programare orientata pe obiecte. Limbajul C, ca si Pascal, utilizeaza modelul programarii structurate procedurale, care...

Comunicații internet

2.1. Stilurile caracterelor {n sfirsit pagina dvs. contine ceva, chiar daca este vorba numai de un nume. Vom analiza in continuare elementele de...

Crearea unei aplicații independente în Java

Toate aplicatiile Java contin o metoda main(), spre deosebire de miniaplicatii. class FirstApp { public static void main( String argsst) {...

Curs Excel

Deplasarea prin foi Deplasarea dintr-o foaie in alta se face cu clic cu mouse-ul pe eticheta foii dorite. Deplasarea prin celule Va puteti...

Te-ar putea interesa și

Rețea de prelucrarea distribuită a imaginilor

INTRODUCERE Procesul de informatizare se caracterizează prin apariţia şi dezvoltarea în interiorul diverselor organizaţii a unor reţele de...

Sistem Inteligent de Gestiune a Datelor

Preambul Înţelegerea mecanismelor vieţii şi în special ale inteligenţei umane a constituit o preocupare permanentă a multor categorii de...

Bazele sistemelor de achiziție a datelor

1. Tema de proiectare. Să se proiecteze un sistem de achiziţie de date interfaţat cu PC pe portul serial care să achiziţioneze 4 semnale de la 4...

Modelarea Dispersiilor Poluante

MODEL-MODELARE Simularea înlocuieşte sistemul de studiat folosind o altă formă de reprezentare care se numeşte model. Un model este o descriere -...

Previziune și Orientare în Activitatea Economică

1.1 Previziunea ca ştiinţă. Aspecte conceptuale În orice firmă există preocuparea permanentă pentru a anticipa mersul evenimentelor economice,...

USO - Automatică

Dobandirea/aprofundarea unor notiuni teoretice (c) 2. Dobandirea/aprofundarea unor abilitati practice (l) 3. Familiarizarea cu noi concepte (c+l)...

Cercetare științifică - modele de decizie, risc și prognoză

Introducere Unul dintre motivele pentru care logica fuzzy este de succes este faptul ca sistemele fuzzy sunt aproximatori universali, adica putem...

Ai nevoie de altceva?