Simulare pe Sisteme în Domeniul Calcul Paralel

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.