Pagina documente » Informatica, Matematica » Modelarea si evaluarea performantelor sistemelor de calcul prin retele Petri

Despre lucrare

lucrare-licenta-modelarea-si-evaluarea-performantelor-sistemelor-de-calcul-prin-retele-petri
Aceasta lucrare poate fi descarcata doar daca ai statut PREMIUM si are scop consultativ. Pentru a descarca aceasta lucrare trebuie sa fii utilizator inregistrat.
lucrare-licenta-modelarea-si-evaluarea-performantelor-sistemelor-de-calcul-prin-retele-petri


Cuprins

CUPRINS
INTRODUCERE 4
1 ELEMENTE DE PROCESE STOCHASTICE 6
1.1 GENERALITATI 6
1.2 LANTURI MARKOV 7
1.3 PROCESE MARKOV IN TIMP CONTINUU 9
1.4 CONSERVAREA FLUXULUI DE PROBABILITATE 11
2 RETELE PETRI COLORATE 16
2.1 NOTIUNI INTRODUCTIVE 16
2.2 CULORI SI FUNCTII DE COLORARE 18
2.3 DEFINITIA UNEI RETELE PETRI COLORATE 21
2.4 EVOLUTIA MARCAJELOR 23
2.5 PROPRIETATILE UNEI RETELE PETRI COLORATE 24
2.5.1 Reteaua marginita 28
2.5.2 Viabilitate si blocaj 28
2.5.3 Conflict 28
2.5.4 Invariante de marcaje 28
2.5.5 Invariante de declansari 29
2.5.6 Analiza proprietatilor de functionare 29
2.6 MODELAREA PROCESELOR DE CALCUL PRIN RETELE PETRI COLORATE 30
2.7 ALEGEREA CULORILOR 32
2.8 FUNCTII DE COLORARE A RETELEI PETRI 38
3 RETELE PETRI STOCHASTICE COLORATE 41
3.1 RETELE PETRI MARKOVIENE COLORATE 41
3.1.1 Definirea unei retele markoviene colorate 41
3.1.2 Construirea grafului de marcaje accesibile 42
3.1.3 Matricea dinamica colorata 43
3.1.4 Probabilitati stationare de stare colorata 44
3.2 MODELAREA UNUI SISTEM MULTIPROCESOR SPECIALIZAT 46
3.2.1 Modelul de retea RPM 47
3.2.2 Modelul de retea RMC 54
3.2.3 Matricea dinamica colorata 59
BIBLIOGRAFIE 64

EXTRAS DIN DOCUMENT

?Introducere

Sistemele de calcul cu prelucrare distribuita a datelor sunt concepute ca un ansamblu de subsisteme, care, la randul lor, sunt supuse unor constrangeri de functionare in paralel. Definirea unei confguratii a sistemului de calcul, destinata sa functioneze intr-un anumit context, trebuie sa corespunda, in general, unor restrictii de performanta si de cost specific. In ceea ce priveste restrictiile de performanta se urmareste asigurarea caracteristicilor functionale impuse de tipul aplicatiilor carora le este destinat sistemul de calcul si aceasta la un nivel acceptabil, in sensul satisfacerii timpului de raspuns, puterii de procesare a fiabilitatii, tolerantei la defecte etc.

Caracteristicile functionale si de performata ale sistemului elaborat sunt determinate printr-o activitate de modelare a contextului real in care urmeaza sa functioneze. Modelul de referinta adoptat trebuie sa captureze toate proprietatile si caracteristicele viitorului sistem. Precizia si completitudinea definirii acestor proprietati si caracteristici sunt de o importanta vitala pentru obtinerea unui sistem corespunzator obiectivului pentru care a fost construit. Scopul unui model este de a defini caracteristicele si proprietatile sistemului de construit si de a prevedea o baza pentru verificarea acestora. Diferite modele pot fi folosite pentru a exprima proprietati diferite: in mod alternativ pentru a exprima o proprietate a sistemului dintr-o clasa de modele se alege sau se construieste un model adecvat pentru a reprezenta aceste proprietati. Exista mai multe modele bazate pe metode, tehnici si formalisme in mod potential ce pot fi folosite pentru a descrie proprietati de comportare ale sistemelor de calcul distribuie: functii matematice, ierarhia functionala, masini cu stari finite, logica temporala, retele de sisteme de asteptare, retele Petri etc. In general nu exista un model prin care pot fi reprzentate toate proprietatile sistemului studiat. De regula, aceste modele sunt folosite in mod complementar, in cadrul unor metode si tehnici dublate de instrumente de modelare, verificare, analiza si evaluare a performantelor sistemului de proiectat.

Prezenta lucrare isi propune o descriere a conceptelor teoretice si a realizarilor practice ale tehnicilor de modelare si evaluare a performantelor sistemelor de calcul prin retele Petri de cateva modificatii. Selectarea materialului a fost facuta pentru a crea, pe cat posibil, o imagine de ansamblu a stadiului actual a problematicii folosirii tehnicilor de specificare, modelare, validare si evaluare a performantelor executarii proceslor paralele ale sistemelor de calcul cu retele Petri markovine.

In primul capitol sunt prezentate unele elemente de baza a teoriei proceselor stochastice, astfel ca lanturile Markov si procesele Markov discrete in timp continuu. Tot aici sunt determinate si proprietatile de conservare a fluxului de probabilitate in graful de trecere al unui lant Markov.

In capitilul doi este prezentata o interpretare a temporizarilor aleatorii ale tranzitiilor retelelor Petri, in baza careia este definita in forma generala o retea Petri stochastica, ceea ce da posibilitatea de a descrie in continuare retele Petri markoviene si retele Petri markoviene generalizate. Sunt determinate proprietatile de conservare ale proceselor de marcare a locatiilor si de declansare a tranzitiilor si se aduc conditiile necesare si suficiente de ergocitate ale retelelor Petri markoviene. Un loc aparte il ocupa matricea dinamica si caracteristicile numerice de performanta ale retelelor Petri markoviene, in baza carora sunt efectuate unele studii de caz.

1 Elemente de procese stochastice

1.1 Generalitati

Procesele stochastice permit modelarea matematica a numeroaselor componente ale sistemelor tehnice, economice, sociale etc.

Prin definitie, un proces stochastic este o familie de variabile aleatoare X(?) ce apartin unui spatiu Wx(?), numit spatiu de stari si care sunt indexate dupa un parametru ???. Atunci un proces il putem reprezenta astfel:

{ X(?)?Wx(?), ???}. (1.1)

Ansamblurile Wx(?) si ? pot fi de tip discret sau continuu. Se poate adopta terminologia de proces sau lant in functie de variabila continua sau discreta a parametrului ?, care in mod frecvent reprezinta timpul.

Pentru a evalua starea unui sistem, trebuie utilizat un vector X de stare, reprezentat printr-o familie de variabile aleatoare X(?i), independente intre ele:

X={X(?1), X(?2),, X(?i),} (1.2).

Este necesara introducerea notiunii de probabilitate de stare, ?x(?):

?x(?)=Prob{X(?)=x}, (1.3)

care este si ea o functie de parametrul ?, reprezentand probabilitatea ca variabila X sa ia valoarea x la momentul ?; este de fapt, probabilitatea absoluta a starii X(?).

Probabilitatea conditionata a trecerii de la o stare x1 la o alta x2 , prin unul sau mai multe salturi temporale, se noteaza prin:

(1.4)

si reprezinta probabilitatea trecerii intre cele doua stari, eveniment ce se desfasoara in intervalul de timp ??=?2-?1.

Procesele stochastice se analizeaza urmarindu-se, functia de repartitie a probabilitatilor FX(X,?):

FX(X,?)=Prob{X(?1)?x1, X(?2)?x2,, X(?i)?xi,} (1.5).

Pe aceasta linie procesele stochastice se impart in:

? procese stationare

Un proces X(?) este stationar daca functia de repartitie a probabilitatilor ramane egala cu ea insasi pentru orice traslatie ? ? pe axa timpului, adica:

FX(X,?+??)= FX(X,?) (1.6).

? procese independente

Conceptul de independenta intre variabilele X(?i) se traduce prin:

(1.7).

? procese Markov

In aceasta categorie se incadreaza procesele ale caror variatie aleatoare are loc, astfel incat fiecare dintre starile X(?o), X(?1), , X(?i), care corespund momentelor succesive ?o, ?1, , ?i, care nu depind decat de un numar finit k de stari precedente. Daca spatiul starilor este discret, atunci este cazul unui lant Markov de ordin k. Clasa cea mai frecventa de procese Markov este aceea pentru care k=1. Aceasta inseamna ca, fiind data o succesiune de stari X(?k) ale unui asemenea proces, starea X(?j+1) depinde de starea precedenta X(?j), adica in termeni probabilistici:

Prob{ Xj+1(?j+1)=Xj+1|X(?0)=X0, X(?j)=Xj}=Prob{X(?j+1)=Xj+1| X(?i)=Xi} (1.8).

Aceasta reprezinta proprietatea fundamentala a proceselor markoviene:

O stare viitoare nu depinde decat de starea prezenta, adica tot trecutul este continut in prezent. Cu alte cuvinte, procesele Markov sunt procese fara memorie.

1.2 Lanturi Markov

In domeniul de interes al sistemelor de calcul se afla procesele Markov cu spatiul discret de stari si cu parametrul temporal discret, numit lanturi Markov (LM).

Starile unui asemenea proces sunt reprezentate printr-o variabila aleatoare M(?) ce parcurge ansamblul numerelor intregi nenegative N+. parametrul temporal ? poate parcurge la randul lui ansamblul numerelor intregi succesive, reprezentate de exemplu prin litera j, cu j?0 ce formeaza un lant discret.

Deci, starea M(j) a sistemului, a carei evolutie se analizeaza, este prezentata prin nj, ceea ce se citeste ca starea n la momentul j.

Daca are loc trecerea de la starea nj in starea nk cu k>j, atunci, inseamna, ca are loc o tranzitie.

Conform definitiei proceselor Markov se poate scrie ca:

Prob {Mk = nk | M(1)=n1, , M(j)=nj}=Prob{Mk=nk | M(j)= nj} (1.9)

Adica starea viitoare la momentul j+1 nu depinde decat de cunoasterea celei prezente din momentul actual j.

Daca este probabilitatea absoluta a starii ni, atunci, spatiul probabilitatilor la momentul j este prezentat printr-o matrice-linie ?(j) ale carei componente sunt ?0(j), ?1(j),, fiecare din ele avand valori inferioare sau egale cu unitatea, adica:

?(j) = [ ?0(j), ?1(j),, ?k(j),] (1.10)

si stiind ca pentru orice nj?0 exista: cu .

Daca sistemul executa trecerea intre doua momente succesive j si j+1, adica daca trece din starea nj=n in starea nj+1 = k, atunci este probabilitatea conditionata de trecere.

In graful de trecere al LM din fig 1.1 este reprezentat spatiul starilor unui sistem. Prin noduri sunt reprezentate starile posibile {0, 1, 2, , n} la momentul j, iar arcele orientate arata trecerile spre starea k la momentul j+1. Aceste arce sunt ponderate cu probabilitatile de trecere rn,k respective.

Respectand caracteristica procesului Markov, se poate scrie ca:

(1.11)