All Coursesas
-
Upload
smarandache-gabi -
Category
Documents
-
view
287 -
download
4
description
Transcript of All Coursesas
Instructori:
Modelarea sistemelor de calculModelarea sistemelor de calculCurs, anul III Calculatoare
Instructori: Prof.dr.ing. Mihai Mocanu Conf.dr.ing.Ileana NicolaeE-mail: [email protected] curs: Joi 16:00-18:00Ore consultatie (la cerere): Joi 14:00-16:00Pagina curs: http://software.ucv.ro/~mocanu_mihai/(pe intrarea corespunzătoare cursului, introduceţi user/pasw)
Obiectul cursuluiDomeniul distinct de studiu/cercetare al modelariisi simularii (M&S) face parte din zona disciplineloringineresti generale (management ingineresc)n Termenii “modelare” si “simulare” sunt deseori utilizati
alternativ → conceptualizarea si implementarea (M&S) alternativ → conceptualizarea si implementarea (M&S) sunt activitati mutual dependente – ce pot fi conduseinsa si independent (de indivizi diferiti)
O definitie generala a obiectului M&S:n “Modelarea si simularea (M&S) consta in utilizarea de
modele, inclusiv emulatoare, prototipuri, simulatoareetc, fie static sau in timp, pentru a dezvolta date si a le folosi apoi ca baza pentru luarea unor decizii (tehnicesau manageriale)”
Locul cursului
Operations Research*
Software
Physics
Mathematics Control Theory
Artificial Intelligence
Numerical and Symbolic
ComputationGraphics &
Visualization
Systems Engineering
Computer Science
Software Engineering
Modeling & Simulation
Zone de cunostinte conexe
Fundamente necesareProgramarea calculatoarelor
Tehnici de programare
Metode numerice
Algoritmi şi structuri de dateAlgoritmi şi structuri de date
Teoria generală a sistemelor dinamiceTeoria probabilităţilor şi statistica matematicăProgramarea orientată pe obiecte
Medii de programare vizuală
ObiectiveIntroducerea conceptelor de bază de modelare şi simulare discretăÎnsuşirea metodelor analitice de modelare pentru sisteme cu cozi de aşteptare şi reţele de coziIntroducerea tehnicilor de modelare, simulare şi analiza performantelor pentru sisteme cu evenimente discrete complexe performantelor pentru sisteme cu evenimente discrete complexe Identificarea posibilităţilor şi limitărilor modelelor matematice, extinderea lor prin simulareUtilizarea unor pachete şi biblioteci de programe specializate pentru modelare şi simulareDezvoltarea abilităţilor de modelare/ simulare a unui sistem nu doar prin exerciţii şi probleme, ci şi prin realizarea unui proiect
Structura cursuluiModelarea analitică a sistemelor discreteProbabilităţi şi procese aleatoare (review)Teoria elementară a cozilor de aşteptareReţele de cozi de aşteptareReţele PetriReţele PetriTehnici de aproximareModele de simulare pentru SEDLimbaje si medii de simulareTopici avansaten Simularea paralelă si distribuităn Analiza perturbaţiilor
Conţinutul cursului pe largSisteme dinamicen Sisteme cu evenimente discrete (SED, SDED)Modelarea analitică a SEDn Categorii de modele şi nivele de studiun Modele algebrice şi logicen Modele algebrice şi logicen Modele dinamice: reţele Petrin Modele temporale: reţele Petri temporizate
Modelarea operaţională a SEDn Statistica in modelaren Lanţuri şi procese Markov şi semi-Markov generalizate n Formalismul GSMP ca bază a modelelor de simularen Sisteme cu cozi de aşteptare şi reţele de cozi
Conţinutul cursului (cont.)Modele de simulare pentru SEDn Generarea numerelor şi variabilelor aleatoaren Construcţia şi verificarea modelului de simularen Execuţia secvenţiala şi analiza simulărilor (ieşirilor)n Validarea simulărilor. Estimatori şi inferenţa statistica
Limbaje şi medii de simulareLimbaje şi medii de simularen Limbaje de simularen Construcţia unui simulator. Biblioteci de componenten Metode de accelerare a execuţiei simulărilor: simularea paralela
(distribuita), tehnici de gradientAplicaţii ale modelarii şi simulării pentru:n Sisteme cu cozi de aşteptare şi reţele de cozin Sisteme de calcul şi reţele de calculatoare n Sisteme şi reţele de comunicaţii
Referințe bibliograficeBanks J., Carson J.S., Nelson A., Nicol D., Discrete-Event System Simulation, 3rd Ed., Prentice-Hall, 2000Cassandras C.G., Discrete Event Systems: Modeling and Performance Analysis, Irwin & Aksen, Boston, 1993Lazowska E.D., Zahorjan J., Scott-Graham G., Sevcik K. Lazowska E.D., Zahorjan J., Scott-Graham G., Sevcik K. C.: Quantitative System Performance - Computer System Analysis Using Queueing Network Models, 1984Sadiku M., Ilyas M.: Simulation of Local Area Networks, CRC Press, 1995Mocanu M., Principii, concepte şi instrumente de modelare şi simulare in studiul sistemelor dinamice discrete, Ed. Sitech, 2004
NotareaSe face in PV (pct. virtuale, max.100) repartizate astfel:• 20% teme practice periodice → proiect (P) • 20% evaluare continua a activită ii de laborator (L)• 20% teste de evaluare (T)• 40% examen scris final (E)• 40% examen scris final (E)Trebuie să obţineţi minim 50% din punctaj - minim 10p la
fiecare dintre formele de evaluare pe parcursul semestrului, pentru a putea lua examenul din prima sesiune.
La examenul final, trebuie să ob ine i minim 50% din punctaj (20p) pentru a promova.
Nota reflectă curba lui Gauss aplicată punctajului final.
Capitolul I
Sisteme dinamice cu evenimente Sisteme dinamice cu evenimente discrete
Sisteme dinamice: Aspecte calitative
Se are în vedere dezvoltarea de tehnici de proiectare, analiză, control, măsurare de performanţe, bazate pe unele metode şi criterii Definiţii:Definiţii:n un sistem constă din “componente” in interacţiunen un sistem este complet descris de “funcţia” asociată,
pe care o îndeplineşte prezumptiv [Cas93]n modelul - o reprezentare abstractă (o schemă, un
set de ecuaţii etc.) replicând, cu un anumit grad de acurateţe, comportarea sistemului însuşi
Un model matematic general< X, T, U, f, Y, g, R >, unde:
X este mulţimea stărilor;T este timpul (continuu sau discret);U este domeniul intrărilor admise;f : XxTxUxT→X, funcţia de tranziţie a stărilor;f : XxTxUxT→X, funcţia de tranziţie a stărilor;Y este domeniul de ieşire;g : XxT→Y este funcţia de ieşire;R : UxT→U este funcţia de admisibilitate a intrării (datorata sau nu unei reacţii a sistemului).
Variabile măsurabilevariabile de intrare – variabile in timp: u1(t), u2(t), ...variabile de ieşire – modificate de sistem ca răspuns: y1(t), y2(t), ....
Daca:u(t) = [u (t), u (t), ..., u (t)]Tu(t) = [u1(t), u2(t), ..., um(t)]T
y(t) = [y1(t), y2(t), ..., yn(t)]T
Modelul matematic general al sistemului, din punct devedere intrare-ieşire, este:
y(t) = g(u(t)) = [g1(u1(t), u2(t), ..., um(t)), g2(u1(t), u2(t),..., um(t)),..., gn(u1(t), u2(t), ..., um(t))]T
Clasificarea sistemelor (1)sisteme statice – in care toate relaţiilefuncţionale intrare-ieşire pe care le putemconstrui sunt descrise simplu prin ecuaţiialgebrice, in care ieşirea y(t) este, pentru orice t,independenta de valorile trecute ale intrării u(τ),independenta de valorile trecute ale intrării u(τ),τ<t;sisteme dinamice – in care relaţiile funcţionale intrare-ieşire construite sunt descrise prin ecuaţii diferenţiale, deci in care ieşirea y(t) depinde de valorile trecute ale intrării u(τ), τ<t, deci de momentul iniţierii studierii relaţiilor i/e
Clasificarea sistemelor (2)sisteme invariante in timp: răspunsulintrare-ieşire nu depinde de momentulaplicării intrării (daca u(t) ⇒ y(t), atunciu(t+τ) ⇒ y(t+τ), ∀τ∈T);sisteme variabile in timp: răspunsulintrare-ieşire depinde de momentul aplicăriiintrării (daca u(t) ⇒ y1(t), atunci u(t+τ) ⇒y2(t+τ), cu y1(t)≠ y2(t+τ) pentru t,τ∈T)
“Stare” sistemIeşirea unui sistem nu este întotdeauna aceeaşi atunci când se aplică aceeaşi intrareSimpla observare a ieşirii y(t) atunci când Simpla observare a ieşirii y(t) atunci când intrarea u(t) este complet specificată nu conduce la predicţia ieşirii viitoareDeci “starea” sistemului diferă!
Clasificarea sistemelor (3)Introducerea noţiunii de stare este
importantă pentru înţelegerea corectă aechilibrului intre influenta factorilor externişi interni in răspunsul unui sistem.şi interni in răspunsul unui sistem.
Numărul stărilor poate fi finit, numărabilsau infinit :
- sisteme cu stări discrete;- sisteme cu stări continue.
Clasificarea sistemelor (4)Nu doar numărul stărilor influenţează
capacitatea de predicţie a comportăriiviitoare a sistemului pentru o intrare data.
- sisteme deterministe: ieşirile sunt- sisteme deterministe: ieşirile suntdeterminate complet de stare, intrări şimomentul aplicării;
- sisteme stochastice: cel puţin una dintreieşiri este variabila aleatoare.
Clasificarea sistemelor (rev.)SISTEME
STATICE DINAMICE
VARIANTE INTIMP
INVARIANTEIN TIMP
LINIARE NELINIARE
CU STARICONTINUE
CU STARIDISCRETE
CONDUSE DETIMP
CONDUSE DEEVENIMENTE
DETERMINISTE STOCHASTICE
Sisteme dinamice cu evenimente discrete
SDED - sistemele dinamice cu evenimente discreteExemple:
Obiect de studiu:
Exemple:liniile de fabricaţie/de asamblare reţelele de calculatoare şi de comunicaţiisistemele de dirijare a traficului aerianprocesele de business (supermarket) etc.
Elemente distinctive ale SDEDSisteme artificiale - create de noile tehnologiiSisteme dinamice - prin natura evoluţiei interne Starea lor se schimba la momente discrete de timp şi nu continuu ca în cazul sistemelor fizice timp şi nu continuu ca în cazul sistemelor fizice Evoluţia în timp - depinde de interacţiunea complexa a momentelor de apariţie a diferitelor tipuri de evenimenteNu pot fi descrise prin ecuaţii diferenţiale, cu derivate parţiale sau cu diferenţe finite
SDED - definiţiiSisteme dinamice al căror spaţiu de stări estediscret şi ale căror traiectorii de stare suntconstante pe porţiuniMomentele de timp la care tranziţiile survin, ca şiMomentele de timp la care tranziţiile survin, ca şitranziţiile în sine sunt în general impredictibileTranziţiile de stare se numesc evenimenteAcestea dirijează mecanismul tranziţiilor de stareSDED se deosebesc profund de sistemele cueşantionare, obţinute prin discretizarea timpului
• discrete - privind timpul de referinţa şi spaţiul stărilor
• natura lor discontinuă nu împiedica analiza prin aproximare continua (ex. prin modele de difuzie)
•
SDED - proprietăţi
• asincrone - raportate la evenimente, nu la timp• nedeterministe - generative şi capabile de alegeri
interne • deşi perturbări neplanificate, defectări şi căderi
sunt inerente, modelarea determinista este posibila (prin algebra min-max sau reţelele Petri)
• gradul de complexitate şi dimensiunile lor sunt mari:Ønumărul de stări ale unui SDED “explodează”
combinatorialØenumerarea stărilor duce la sarcini computaţionale
inadecvate
SDED – proprietăţi (cont.)
inadecvate• sunt modulare - compuse din componente cvasi-
independente⇒ pot fi aplicate metode de decompoziţie şi agregare⇒ pot fi echipate cu mijloace de control şi comunicare
Modelarea analitica Simularea
Metodologii de studiu:
DE CE studiem un sistem?Scopurin Proiectaren Măsurare şi controln Îmbunătăţire
ModalităţiModalităţin Studiul sistemului realw Prezintă avantajul exactităţii obiectului de studiu
n Uneori imposibil, deoarece:w Sistemul real nu existaw Studiul sistemului real poate fi distructiv, periculos
sau costa prea mult
DE CE recurgem la modele?Este necesar ca orice experiment să aibă “o bază”,
• dar uneori realitatea nu este construită(absenţa sistemului real)(absenţa sistemului real)
• alteori realitatea nu este disponibilă(lipsa accesului la sistemul real)
Studiul modelelorDe obicei uşor, rapid, ieftin, sigur – faţă de studiul sistemului realPermite încercarea unor idei şi ipotezeSimpla construcţie a unui model este instructivă– indiferent de utilizarea sa– indiferent de utilizarea saValiditatea unui model are in vedere:n similaritatea cu sistemul realn nivelul de detaliu
Numai ea poate garanta concluzii corecte prin studiul modelului in locul sistemului real
Definiţii: modelare şi modelUn proces de modelare este o etapa preliminara necesara in studiul oricărui sistem, pentru:n calcul analiticn simulare
Un model:Un model:n este o reprezentare abstracta a unui sistemn nu doar o reprezentare a unui sistem - ci şi o
simplificare a san totuşi suficient de detaliata, ca sa permită, prin
studiul sau, concluzii valide asupra sistemului
Modelarea in studiul sistemelor
Tipuri de modeleModele fizice (iconice)n Planuri, scheme, schiţe – necesare in multe domeniin De tip manechin (phantom) – in medicinan De tip “virtual reality” sau “augmented reality” – in
domenii de înalta tehnologie (simulatoare de zbor)domenii de înalta tehnologie (simulatoare de zbor)
Modele matematice (logice)n Aproximează modul de operare al unui sistemn Deseori reprezentate printr-un software adecvatn Execuţia programului permite încercări, obţinerea de
rezultate, studiul comportamentului modelului
Modelarea predictivăEste o modelare in absenta realităţii
Exemple:
a) Construcţia unei caroserii care trebuie sa satisfacă anumite criterii de greutate, rezistenta, geometrice, tehnologicerezistenta, geometrice, tehnologice
b) Studiul performantei unui algoritm in ipoteza implementării pe o arhitectura incă inexistenta (dar posibila)
c) Experimentarea unor medicamente ce trebuie sa aibă unele proprietăţi speciale
Modelarea restrictivăEste modelarea in condiţiile restricţiilor de acces la un sistem real existent
Exemple:
a) Nu putem opri o reţea de calculatoare ce monitorizează a) Nu putem opri o reţea de calculatoare ce monitorizează o centrala nucleara in scopul efectuării de experimente
b) Nu putem opri procese de fabricaţie ritmice pentru a experimenta noi metode de management
c) Nu putem perturba circulaţia pe o artera aglomerata pentru a decide in ce măsura, de exemplu, schimbarea unor reguli de trafic (viteza, prioritatea) este benefica
Studiul modelelor logiceDaca un sistem este destul de simplu, şi modelul este simplu, pot fi aplicate metode matematice tradiţionalePermit obţinerea de rezultate exacte:n Aparatul matematic integro-diferenţialn Teoria aşteptării (cozi şi reţele de cozi)n Teoria aşteptării (cozi şi reţele de cozi)n Programare liniara
Sistemele complexe pot fi uneori reprezentate de modele analitice simple, validen Presupunerile simplificatoare păstrează validitatea?
Cel mai adesea, un sistem complex necesită un model complex, metodele analitice nu se aplică … ce facem?
Simularea pe calculatorIn sens larg, se refera la metode de studiu ce pp. n evaluare numerica a unor modele de sistemn utilizarea unui model software pentru a mima operaţii/
caracteristici sistem, in timpPoate fi validata de studiul modelelor simple, pentru care este disponibila şi o soluţie analiticapentru care este disponibila şi o soluţie analiticaPotenţial ridicat in studiul modelelor complexeSimularea este foarte utila in studiul unor sisteme complexe, unde nu se întrevede soluţia analiticaFundamente teoretice ale modelelor de simulare:n automatele de stare (stohastice) n procesele semi-Markov generalizate (GSMP)
Acurateţea simulărilorPrin simulare nu se obţin răspunsuri exacte, doar aproximaţii, estimări; totuşi:n Aceasta nu este o problema specifica, ci una generala
pentru multe alte metode de studiun Erorile pot fi limitate, prin verificare si validare (V&V)n Erorile pot fi limitate, prin verificare si validare (V&V)n Verificarea si validarea sunt compuse din proceduri
integrate in dezvoltarea modelului (de simulare)Ceea ce trebuie evitat este obţinerea ieşirilor aleatoare (RIRO) din simulări stochastice, prin:n Proiectarea şi analiza statistică a experimentelor de
simularen Controlul “zgomotului”, replicabilităţii, eşantionării
secvenţiale, tehnicilor de reducere a variantei
Verificarea şi validarea simulărilorVerificarea simulării consta in principal in compararea modelului conceptual cu codul programatMetode de verificare a unei simulări: n Compararea modelului implementat cu alte modele, atât la nivel
de structura interna cat si de intrare/ ieșiren Testarea la nivel de sistem, subsistem sau componente pentru
îndeplinirea cerințelor sau specificațiilor documentate
Validarea unei simulări consta in analiza corespondentei intre model si sistemul realMetode de validare a unei simulări:n Examinarea atenta a ieșirilor modelului in condițiile variabilității
cat mai mari a intrărilor, si compararea cu datele de observațien Execuția repetata a modelului programat
Diversitatea metodelor de simulareCel mai adesea, simularea are loc pentru starea stabila, dupa eliminarea regimurilor tranzitoriiMetode statice vs. dinamicen Ce rol joaca timpul in model?
Metode continue vs. discreteMetode continue vs. discreten “starea” se poate schimba continuu, sau tranziţiile de
stare apar doar la momente discrete in timp?Metode deterministe vs. stochasticen este evoluţia sistemului sigura sau exista elemente
de incertitudine?
Majoritatea modelelor operaţionale sunt: dinamice, discrete şi stochastice
Ex.de simulare manuală: estimarea nr.π prin aruncarea acului (Buffon)
Se aruncă un ac de lungime L pe o masa cu Se aruncă un ac de lungime L pe o masa cu dungi d- echidistante (d >L)P (acul sa “taie” o linie) = (2*L)/(π*d)Se repetă experimentul de un număr mare de ori şi se determina R = raportul intre nr. traversărilor şi nr. aruncărilorSe estimează π prin (2*L)/(R*d)
JustificareAcul poate ateriza in poziţii diferite (fig.1)
Orice poziţie intre 2 linii se caracterizează prin:n Distanta capătului acului (interior) fata de cea mai
apropiata linie de deasupra sa (y): 0 < y < dapropiata linie de deasupra sa (y): 0 < y < d
n Unghiul format cu direcţia liniilor (θ): 0 < θ < π.
Fig.1 Fig.2
Justificare (cont.)Acul intersectează linia dacă y < L·sinθ
Perechea (θ, y) determină in mod unic poziţia acului (fără a ţine cont de translaţii)
Spaţiul de eşantionare:
Justificare (cont.)
Probabilitatea ca acul sa intersecteze
o linie:
După efectuarea calculelor:ππ
θ⋅=
==
dAdlaturideuluidreptunghiariaLycurbasubdeariaP
:,)sin(
ConcluziiProblema acului (Buffon) pare banală, dar aduce in atenţie unele caracteristici de simulare importante:
n Execuţia in vederea estimării unei mărimi dificil de calculat exact (in 1733)
n Factorul aleator, ce face ca estimatorul sa nu fie exactn Factorul aleator, ce face ca estimatorul sa nu fie exactn Posibilitatea estimării erorii estimatoruluin Replicarea (mai mult=mai bine) pentru reducerea eroriin Eşantionarea secvenţiala pentru controlul erorii – repetă
aruncarea pana când eroarea estimatorului este “destul de mica”
n Reducerea varianţei (“crucea Buffon” sau tehnica Fox)w În esenţă, artificii ca rotirea mesei pe care este
aruncat acul pot elimina imperfecţiunea aruncărilor
Modelarea sistemelor de calculModelarea sistemelor de calcul
Fundamente matematice ale modelarii.
Curs, anul III Calculatoare
Fundamente matematice ale modelarii. Elemente de probabilităţi şi statistică
matematică.
Definiţii nonformale şi exemple
Def: Spaţiu de eşantionare (eng. sample space) , notat S: o mulţime in care fiecare element reprezintă “rezultatele” unui “experiment”
Exemple:Exemple:n S = Ban, Marca in aruncarea unei moneden S = 1, 2, …, 6 in aruncarea unui zar
Def.: Eveniment: un subset al spaţiului SExemple:
n Obţinerea unei valori dintr-o submulţime a spaţiului S (Ban, 1,2,3) in cadrul unei aruncări
Relaţii în mulţimea evenimentelorImplicaţia evenimentelor: evenimentul A implicaevenimentul B (notam A → B sau A ⊂ B) daca atunci când se produce A se produce in mod necesar şi BReuniunea evenimentelor A, B (notata A ∪ B): este evenimentul care se produce atunci când se produce cel puţin unul dintre evenimentele A, Bpuţin unul dintre evenimentele A, BIntersecţia evenimentelor A, B (notata A ∩ B): este evenimentul care se produce doar atunci când se produc ambele evenimente A, BEvenimente incompatibile: evenimentele care nu se pot produce simultanEvenimente contrare: producerea unuia înseamnă nerealizarea celorlalte
Evenimente elementare Def.: Evenimentul elementar este un element din mulţimea S
Evenimentele elementare se mai definesc ca rezultate cu valori booleene ale unor probe (experimente)Un experiment poate aduce: n fie realizarea unui anumit evenimentn fie nerealizarea sa
Există 2 evenimente speciale în mulţimea de evenimente asociate unui experiment :evenimentul sigur S = A ∪ Ā
evenimentul imposibil ∅ = A ∩ Ān Evenimentele A şi B sunt mutual exclusive daca A ∩ B = ∅
Distribuţia de probabilitate
Def.: Distribuţia de probabilitate Pr este o funcţie
definita pe evenimentele din S cu valori in R
Proprietăţi:Proprietăţi:
1. PrA ≥ 0 pentru orice eveniment A
2. PrS = 1
3. If A ∩ B = ∅ then PrA∪B = PrA + PrB
else PrA∪B = PrA + PrB – PrA ∩ B
Exemplul 1Aruncarea a doua monede:
n Spaţiu de eşantionare: S = BB, BM, MB, MM
n Oricare eveniment elementar se produce cu n Oricare eveniment elementar se produce cu
aceeaşi probabilitate: ¼ (ev. echiprobabile)
n Probabilitatea de a obţine cel puţin o data B:
PrBB, BM, MB = PrBB + PrBM + PrMB = ¾
Exemplul 2Aruncarea a doua zaruri:
n Calculam probabilitatea de a da 4 sau dublen Spaţiul de eşantionare S conţine 36 de evenimente
elementare posibile, echiprobabile (probabilitatea fiecăruia fiind 1/36)fiecăruia fiind 1/36)
n Eveniment A: sa obţinem 4 (3 evenimente elementare)n Eveniment B: sa dam duble (6 evenimente elementare)n A ∩ B: roll (2, 2)
Pr4 ori duble = = Pr4 + Prduble – Pr(2, 2)= 3/36 + 6/36 – 1/36= 8/36
Definiţii formalizateSunt necesare operaţii ca: n implicaţia & echivalenta evenimentelor
n reuniunea evenimentelor, ∪
n intersecţia evenimentelor, ∩∩
n complementaritatea evenimentelor, ¯
n incompatibilitatea evenimentelor
Mulţimea evenimentelor ataşate unui experiment formează o algebră Boole în raport cu operaţiile definite (∪, ∩ şi ¯)
Câmp de evenimenteFie S o mulţime de evenimente elementare, iar B ⊂ P(S) un sistem de submulţimi ale lui S
Dacă:1. S ∈ B;1. S ∈ B;
2. E1, E2 ∈ B ⇒ E1 ∪ E2 ∈ B; E1 ∩ E2 ∈ B; Ē1∈ B; Ē2∈ B
3. E1, E2,..., En,... ∈ B ⇒ E1 ∪ E2 ∪ ... ∪ En ∪ ... ∈ B; E1 ∩ E2 ∩ ... ∩ En ∩ ... ∈ B,
atunci B se numeşte câmp Borel de evenimente
Măsura de probabilitateDefinirea se face intr-un câmp borelian de evenimente şi are la bază sistemul de axiome al lui Kolmogorov:Axioma 1: Fiecărui eveniment elementar E din câmpul
de evenimente îi este ataşat un număr real nenegativ numit probabilitatea lui E, notat P(E)
Axioma 2: Probabilitatea evenimentului sigur S este Axioma 2: Probabilitatea evenimentului sigur S este 1, P(S)=1
Axioma 3: Dacă evenimentele E1, E2,..., En sunt incompatibile 2 câte 2, atunci P(E1 ∪ E2 ∪ ... ∪ En) = P(E1)+P(E2)+...+P(En).
Axioma de adunare extinsă: Dacă apariţia unui eveniment E e echivalentă cu apariţia evenimentelor E1, E2,..., En,... incompatibile 2 câte 2, P(E)=P(E1)+P(E2)+...+P(En)+...
Distribuţie de probabilitate discretaDef.: O distribuţie de probabilitate este discreta daca e definita
pe un spaţiu de eşantionare finit sau infinit numărabil
n Pentru orice eveniment A:PrA = Prs1 + Prs2 + … Prsn = Σs∈APrs, şi ∈ APrA = Prs1 + Prs2 + … Prsn = Σs∈APrs, şi ∈ A
Def.: O distribuţie de probabilitate este uniforma pe un spaţiu finit S
n |S| = n
n Prs = 1/|S| pentru orice eveniment elementar s ∈ SEx: Aruncarea unui zar netrucat:
n Fiecare fata are probabilitatea de apariţie 1/6
Variabile aleatoare discrete
Def.: O variabila aleatoare (discreta) X e o functie definita pe un
spaţiu de eşantionare finit/ infinit numărabil cu valori reale
n Ea asociază un număr real cu orice rezultat posibil al unui
experiment
Pentru o v.a. X şi un număr real x:
Def.: Evenimentul X = x = s ∈ S: X(s) = x
Def.: f(x) = PrX=x = Σs∈S: X(s) = xPrs se numeşte funcţia
densităţii de probabilitate a v.a. X
ExempluAruncarea unei perechi de zaruri:
Spaţiul de eşantionare S are 36 evenimente elementare posibile
Fiecare eveniment elementar s∈S este echiprobabil: Fiecare eveniment elementar s∈S este echiprobabil: Prs = 1/36
V.a. X = maximul celor doua valoriProbabilitatea ca maximul celor doua valori sa fie 3:n X asignează valoarea 3 pentru 5 din cele 36 evenimente posibile:
(1, 3), (2, 3), (3, 3), (3, 2), (3, 1)
n Deci: PrX = 3 = 5/36
V.a. şi eşantion (discret)Este o funcţie X : (Ω, B, P) → R, ce ia valori diferite în cazul unor experimente efectuate în condiţii identice, apariţia fiecărei valori fiind un eveniment incontrolabilX(ω) e valoarea reală a variabilei aleatoare, ca funcţie de experimentul sau eşantionul considerat, unde ω este eşantionul (engl."sample").O v.a. X=X(ω) determină o desfacere a evenimentului O v.a. X=X(ω) determină o desfacere a evenimentului total în evenimente incompatibile: intuitiv, pentru cazul discretizării Ω luand k valori posibile ale variabilei X(ω), notate x1, x2,..., xk, cu probabilităţile ataşate p1, p2,..., pk (p1+p2+...+pk =1), variabila aleatoare e dată sub forma:
x1 x2 ... xkX =
p1 p2 ... pk
Variabile aleatoare continuePrin analogie valorile sunt funcţii continue, de ex. peste RProbabilităţile apariţiei acestor valori sunt definite (dacaexista) de o funcţie f(x) definita pe întreaga dreapta reala
( ) xptxfdxxfxXxPx
x∀≥=≤≤ ∫ .0)(,)(2
21
Pentru orice x1, x2 a.i. x1≤x2, X este o v.a. continua iar f(x) se numeşte funcţia densităţii de probabilitateAtât v.a.discrete cat şi v.a.continue pot fi dependente sau independenten In cazul a 2 v.a. independente, X şi Y, definite ca mai sus:
P(Xi ∩ Yj) = P(Xi)∙P(Yj)
( ) xptxfdxxfxXxPx
∀≥=≤≤ ∫ .0)(,)(1
21
Distribuţii (repartiţii) continueAvând in vedere “aspectul” v.a., se definesc:
Funcţia de distribuţie sau repartiţie (c.d.f) a unei v.a. X:
F(x)=P(ω|X(ω)<x)F(x)=P(ω|X(ω)<x)Densitatea de probabilitate (p.d.f.), pentru orice A ⊂ R, prin:
P(x∈A)=∫A f(x)dx, sau f(x)=dF(x)/dx
dacă F este diferenţiabilă în x
Media, dispersia, alte momenteMedia sau valoarea aşteptată a unei v.a. este:µ = E[X] = ∫-∞
∞ xdF(x) = ∫-∞∞ xf(x)dx;
Momentul de ordinul k al v.a.:E[Xk] = ∫-∞
∞ xkdF(x) = ∫-∞∞ xkf(x)dx;
Dispersia (variabilitatea) v.a.:Dispersia (variabilitatea) v.a.:σ2 = var(X) = E[(X-E[X])2] = E[X2]-(E[X])2.Numita şi abatere medie pătratică, pentru un şir xi cu n (nr. mare) valori, ea se calculează astfel :
−
−≈
− ∑∑∑∑
====
2
11
22
11
2 11
111 n
ii
n
ii
n
ii
n
ii x
nx
nx
nx
n
Aplicatie practicaPentru 2 v.a. distribuite uniform:1. Discreta pe intervalul [1,6] (aruncarea
zarului)2. Continua in intervalul [a,b]se cere:se cere:I. Calculul mediilor şi dispersiilorII. Reprezentarea grafica a pdf şi cdfRăspunsuriI. 1. µ = 7/2; σ2 = 35/12
2. µ = (a+b)/2; σ2 = (b-a)2/12 ...
Teoreme importante: Inegalitatea lui Cebîşev
Putem avea o imagine asupra repartiţiei prin cunoaşterea mediei şi dispersiei
Inegalitatea lui Cebîşev arata cat de mari sunt probabilităţile abaterilor de la medie:probabilităţile abaterilor de la medie:
Se poate aplica atât v.a. discrete cat şi continue
2
2
)|(|εσ
εµ ≤≥−xP
Teoreme importante: Legea numerelor mari
Bernoulli: Probabilitatea ca modulul diferenţei intre frecventa relativa de aparitie a unui eveniment E şi probabilitatea p a lui E sa fie mai mic decât un ε pozitiv, arbitrar de mic, este ≈1 pentru un nr. de experimente n suficient de mare
pnP 1 11)|(| ε −≥<−
Cebîşev: Probabilitatea ca modulul diferenţei intre media aritmetica A a valorilor medii a n v.a. i.i.d. şi media aritmetica a uneia dintre v.a. să fie mai mica decât un ε pozitiv, arbitrar de mic, este ≈1 pentru n suficient de mare
np
nnP 2
1
411)|(|ε
ε −≥<−
nbAX
nP
n
ii 2
2
1
1)|1(|ε
ε −≥<−∑=
Distribuţia binomiala (Bernoulli)Se defineşte printr-un experiment Bernoulli, ce are doar doua valori:
Succes/Esec (1/0)0.3
0.4
0.5
0.6
0.7
P(X=
x)
n Succes/Esec (1/0)
0
0.1
0.2
0.3
0 1
X
P(X=
x)
pXP
pXP
−==
==
1)0(
)1(
pXE =][ )1()( ppXVar −=
Distribuţia binomiala Definita de numărul de încercări reuşite dintr-un total de n experimente Bernoulli
0.2
0.3
P(X=
x)
Sau ca suma a n variabile aleatoare de tip Bernoulli
xnxxn ppCxXPxf −−=== )1()()( npXE =][
)1()( pnpXVar −=
0
0.1
0 1 2 3 4 5 6 7 8 9 10
X
Distribuţia binomiala negativa Definita de numărul necesar de repetări ale unui experiment Bernoulli pana la obţinerea de m ori a unui eveniment legat de el (m reuşite)Sau ca o suma infinita de variabile aleatoare de tip Bernoulli, cu valori ce încep cu m, m+1, ...tip Bernoulli, cu valori ce încep cu m, m+1, ...
xmmxm ppCxXPxf )1()()( 1
1 −=== −−+
ppmXE /)1(][ −=
2/)1()( ppmXVar −=
Distribuţia geometrica
Definita de numărul de experimente Bernoulli necesar pentru a obţine primul succes
0.3
0.4
0.5
0.6
0.7
P(X=
x)
primul succes
0
0.1
0.2
0 1 2 3 4 5 6 7 8 9 10
X1)1()( −−= xppxf
pXE 1][ =
2)1()(
ppXVar −
=xpxF )1(1)( −−=
Distribuţia Poisson Definita de nr. de evenimente aleatoare ce au loc intr-un interval de timp de mărime fixa 0.1
0.2
0.3
P(X=
x)
Sau ca o limita a distribuţiei binomiale când n→∞ şi p→0
00 1 2 3 4 5 6 7 8 9 10
X
λλ −=== ex
xXPxfx
!)()(
λ=][XE λ=)( XVar
xexF λ−−= 1)(
Procese Poisson omogeneDaca numărul de evenimente apărute pana la momentul t este distribuit Poisson cu rata λtn Numărul de evenimente apărute in intervale de timp
disjuncte este independentn Timpii intre evenimente sunt independenţi şi identic
distribuiţi ca v.a. exponenţiale cu media 1/λdistribuiţi ca v.a. exponenţiale cu media 1/λn Un proces Poisson omogen este staţionar (distribuţia
nr. de evenimente depinde doar de lungimea intervalului, nu şi de punctul sau de început)
Alte proprietăţi:n Combinarea a 2 procese Poisson cu ratele λ şi µ da
un alt proces Poisson cu rata λ+µn Alegerea evenimentelor dintr-un proces Poisson cu
probabilitatea p da un proces Poisson cu rata p λ
Procese de naştere şi moarteDaca timpii intre evenimente sunt i.i.d. atunci numărul de evenimente ce apar in timp formează un proces “de naştere şi moarte” n Un proces Poisson omogen este un proces de naştere
şi moarte cu timpii intre sosiri exponenţialişi moarte cu timpii intre sosiri exponenţialin Majoritatea proceselor de sosire pot fi modelate
folosind procese de naştere şi moarten Uşor de utilizat deoarece timpii intre sosiri pot fi
obţinuţi prin eşantionare dintr-o distribuţie datan Un proces de naştere şi moarte este staţionar
Procese de sosire nestaţionare Evenimentele externe (inclusiv sosirile in sistem) pot avea rate variabile in timp, de ex.n Sosirile la un restaurant fast-food in jurul prânzuluin Traficul in “rush-hour” in oraşe sau pe autostrăzin Cererile sezoniere pentru un produs
28
n Cererile sezoniere pentru un produs
Caracterul de nestaţionaritate al sosirii trebuie păstrat in model – acest lucru este critic pentru validitatea modeluluiModelul adecvat este cel al unui proces Poisson neomogen
Distribuţia exponenţialaModelează:n Timpii intre sosiri,
când sosirile sunt complet aleatoare
n Timpii de servire ce 0.2
0.3
0.4
0.5
f(x)
n Timpii de servire ce prezintă o mare variabilitate
Este o distribuţie “fără memorie”:
0
0.1
0 2 4 6 8 10
X
β
β/1)( xexf −=
β=][XE 2)( β=XVar)()|( xfyXyxf =>+
Distribuţia normalaDescrisa de următoarele proprietăţi:n Limitele pdf la -∞ şi +∞
sunt 0n Valoarea maxima a pdf 0.15
0.3
0.45
f(x)
n Valoarea maxima a pdf este atinsa când X=μ
n Graficul pdf este simetric după μ
Distribuţia mediei unui sir de v.a. i.i.d. este normalaPentru µ=0: distribuţia normala standard
0
0.15
0 2 4 6 8 10
X
( )222
1
221)(
µσ
πσ
−−=
xexf
µ=][XE 2)( σ=XVar
Distribuţia log-normala (→Weibull)V.a. ln(X) este distribuita normalSe utilizează in modelarea mărimilor ce reprezintă
0.2
0.3
0.4
f(x)
ce reprezintă produse ale unui număr mare de mărimi aleatoare
22 2/))(ln(
21)( σµ
πσ−−= xe
xxf
2/2
][ σµ+= eXE )1()(222 −= + σσµ eeXVar
0
0.1
0 1 2 3 4 5
X
Distribuţia uniformaUtilizata in situaţii cu date echiprobabile pe un interval
1 ≤≤
2/)(][ baXE += 12/)()( 2abXVar −=
a b0
altfel 0
bx a 1)(
≤≤−= abxf
Distribuţia triangularaUtilizata in situaţii cu date puţine sau lipsan Se obţine pe baza a 2
distribuţii uniformen Sunt necesare doar 0.1
0.2
0.3
f(x)
n Sunt necesare doar minimul, maximul şi c.m.probabilă valoare
0
0.1
0 1 2 3 4 5 6 7 8 9 10
X
altfel ,0
,))((
)(2
,))((
)(2)(
=
<≤−−
−=
<≤−−
−=
bxmabmb
xb
mxaabam
axxf
2/)(][ baXE +=
12/)()( 2abXVar −=
Relatii intre distributii
Chi-SquaredDistribution
Lognormal
Distribution
Normal
Distribution
Extreme-ValueDistribution
ExponentialDistribution
GammaDistribution
ErlangDistribution
WeibullDistribution
Tema: ReferatInstalati pe calculatorul personal sau in laboratorpachetul utilitar Analysis ToolPak din Exceln Dupa instalare, comanda Data Analysis trebuie sa fie
disponibila in Excel in grupul Analysis sub tab-ul Data
Folositi aceasta comanda si/ sau alte functii Excel Folositi aceasta comanda si/ sau alte functii Excel pentru a genera multiple esantioane de numerealeatoare cu diferite distributiiReprezentati grafic distributiile obtinuteCalculati momentele (statisticile) semnificativepentru esantioanele generate; comparati-le cu cele teoretice
Modelarea sistemelor de calculModelarea sistemelor de calcul
Generarea datelor de intrare
Curs, anul III Calculatoare
Generarea datelor de intrare1. Generarea numerelor aleatoare
Date de intrare in simularea dinamica discreta
Fie un SED pentru care “stim” ca timpul necesarservirii unui client este cuprins intre 10 si 20 de minute, fiind distribuit uniform (media fiind 15 minute). Cum putem determina timpii de servireai primilor 100 clienti – ca date de baza de ai primilor 100 clienti – ca date de baza de intrare pentru simularea SDED?§ Recurgand din nou la sistemul si procesul real
si la colectarea datelor§ Prin generarea automata (distributionala), cu
grija de a respecta parametrii procesului real
Colectarea datelorIn general grea, costisitoare, frustranta – in plus:n Sistemul real poate sa nu existen Datele sunt din sisteme/ procese “similare” modelului si
nu exact coincidente, disponibilitatea lor poate impunechiar schimbarea modelului
n Datele pot fi incomplete sau prea “incarcate” (zgomotsau cantitati mari de date)
Iesirile sunt sensibile la incertitudinea intrarilor(“garbage in, garbage out”)Gradul de acuratete (detaliere) al modelului estedependent (si) de calitatea datelorn Variabilitatea datelor e o conditie a validitatii modelului
Generarea datelorIn exemplul anterior, am putea folosi la fel de bine un sir de 100 de numere aleatoare uniform distribuite intre 10 si 20, cu media “apropiata” de 15 (cu atat mai apropiata cu cat numarul lor este mai mare)mai mare)Apare ca metoda generala aceea de a desprinde observatii sintetice din proces pentru a genera date de intrare pentru modelProblema este de a “potrivi” datele generate cu cele observate n datele de intrare generate trebuie si validate!
DiscutieEste clar ca in multe cazuri simularea implicaelemente aleatoare/ stochasticeIn exemplul anterior, nu stim apriori cat va luaservirea unui client, dar stim ca timpul de servireurmeaza o distributie de probabilitateurmeaza o distributie de probabilitateFiindca modelul de simulare este oricum o aproximare, scopul generarii n.a. si v.a. este saaproximam “corect” datele de intrare“Corect” inseamna ca generarea de numere sivariabile aleatoare trebuie sa produca dintr-o formula distributionala un set de esantioane(numerice), avand doua proprietati importante…
Proprietatile esantioanelorIdentitatea distributiei (potrivire, uniformitate): Esantioanele produse trebuie sa aiba aceeasidistributie ca si datele reale din procesà in termeni statistici, c.p. media si varianta esantionuluisunt aceleasi cu media si varianta populatiei de intrare
Independenta: Cand un set de esantioane esteplasat in secventa in care este produs, nu trebuiesa existe vreun sablon (chiar si neintentionat!) de repetare a acelei secvente
Cum garantam similaritatea distributiei cu datele?
Presupunem ca datele ce pot fi culese din sistem sunt IID (independente si identic distribuite)Mai intai se incearca gasirea unei distributii de probabilitate, ce va fi apoi utilizata in generarea intrarilor modelului de simulareintrarilor modelului de simulareCea mai buna distributie “teoretica” este cea care se potriveste cel mai bine cu cea a datelor empirice (culese)“Adecvarea” distributiei teoretice (tip, parametri) cu datele empirice este uneori dificila
Metoda histogramelorModalitate simpla de a vedea daca un esantion de date este adecvat unei distributii; etape:n Se deseneaza histograma frecventelor aparitiei datelor n Se estimeaza parametrii unei distributii posibilen Se deseneaza functia densitatii de probabilitaten Se deseneaza functia densitatii de probabilitaten Se determina cat de similare sunt cele doua forme
frecv
ente
valori ale datelor
Testul Hi-patrat (Pearson)Formalizeaza notiunea ant. de
similaritate a distributiilorn Oi reprezinta numarul valorilor
de date observate in cel de-al i-lea interval (sunt k intervale)
n pi este prob. ca o valoare saintre in cel de-al i-lea interval
frecv
ente
valori ale datelor
iO
ii npE =intre in cel de-al i-lea interval sub distributia ipotetica
n Ar fi de asteptat sa observamin intervalul I, Ei = npi, dintr-un total de n observatii
n Daca pp. distributionala estecorecta, atunci χ0
2 urmeaza o distr.χ2 cu k-s-1 gr.de libertate(s e nr.parametrilor distributieiipotetice)
valori ale datelor
ii npE =
∑=
−=
k
i i
ii
EEO
1
220χ
Independenţa datelorDouă seturi de date (esantioane) sunt independente dacă orice subset de valori dintr-unul nu oferă nici o informaţie despre vreun subset de valori “corespondente” in celălalt2 sau mai multe v.a. sunt independente dacă pentru orice submulţime proprie de v.a. orice eveniment determinat de v.a. din submulţime este independent de orice eveniment v.a. din submulţime este independent de orice eveniment determinat de variabilele din mulţimea complementară2 sau mai multe v.a. X1, X2, . . . , sunt independente şi identic distribuite dacă variabilele au aceeaşi distribuţie de probabilitate şi sunt independente (i.i.d.)2 observaţii sunt independente dacă obţinerea primei observaţii nu influenţează obţinerea celeilalte observaţii Echivalent, includerea în eşantion a unui element nu influenţează includerea altui element
Generarea numerelor aleatoare
Notiuni de baza
Generarea numerelor aleatoare
AplicabilitateApare ca instrument de lucru in cazul sistemelor si proceselor stochastice (nedeterministe) – ce necesita modele cu elemente stochasticeImplica utilizarea distributiilor de probabilitate ca elemente de baza de modelareelemente de baza de modelareLarg utilizata si in alte domenii: n Simularea statica (Monte-Carlo) – de ex. calculul lui πn Analiza probabilistica a algoritmilor – cu conditia sa putem
caracteriza in mod rezonabil distributia datelor de intraren Criptografia – la baza constructiei cheilor de criptare si a
altor parametri ai algoritmilor si protocoalelor criptografice...
Ce este un numar “aleator”?Nu putem spune ca un anumit numar este aleator “Aleatorizarea” (randomness) este un proces nedeterminist ce produce astfel de numere (fara insa a putea fi siguri niciodata asupra urmatoarei insa a putea fi siguri niciodata asupra urmatoarei valori produse)Surse bune de numere puraleatoare: ruleta, dar si altedispozitive fizice (electronice,radioactive) mult mai rapide§Totusi, acestea sunt foarte greu de utilizat in simulare
Numere pseudo-aleatoareCel mai important in simulari, care de obicei se fac pentru a compara diverse evolutii ale unui sistem, este pastrarea conditiilor de operareAceste conditii sunt influentate de esantioanele datelor de intrare, la randul lor determinate de datelor de intrare, la randul lor determinate de numerele aleatoare folosite
⇒trebuie pastrata sursa de numere aleatoare in toate simularile
⇒chiar daca sunt pseudo-aleatoare (generate de algoritmi - deterministi) acestea trebuie sa satisfaca anumite proprietati statistice
Proprietati ale unui “bun” generator si numerelor aleatoare generate
Numerele generate trebuie sa fie independente statistic (fara autocorelare)Generatorul trebuie sa fie rapidMemoria necesara algoritmului de generare nu trebuie sa fie excesivasa fie excesivaPerioada de repetitie a numerelor generate trebuie sa fie suficient de marePericolul degenerarii sirului de numere trebuie eliminat (nu trebuie ca de la un anumit rang, numerele sa nu mai respecte conditiile impuse)Sirul de numere aleatoare trebuie sa fie reproductibil
Metode analitice de generare a n.a.(1)
Mijlocul patratului (Von Neumann)Ø Un numar initial (seed) este ridicat la patrat, si cifrele
din mijloc formeaza primul n.a. (prin repozitionareapunctului zecimal se poate obtine un numar intre 0 si1); acesta se ridica din nou la patrat si se obtine prin1); acesta se ridica din nou la patrat si se obtine prinaceeasi tehnica al doilea n.a., iar procedeul continua
Ø Sursă slaba de n.a. – prin faptul ca anumite secventede numere aleatoare se repeta
Ø Pornind de la ideea de baza, s-au construit algoritmimai buni, bazati pe metode recurente de generare
X0 = 9524 (seed)X0
2 = 95242 = 90706576à X1=7065R1= 0.7065
X 2 = 70652 = 49914225à X =9142
Exemplul 1
X12 = 70652 = 49914225à X2=9142
R2 = 0.9142
X22= 91422=83576164 à X3 = 5761
R3 = 0.5761…
X0 = 1258 (seed)1258, la patrat = 15825645825 339306259306 866016366016 36192256
Exemplul 2
6016 361922561922 36940846940 481636001636 26764966764.....
…
Probleme ale algoritmului “mid-square”.Repetarea secventelor
ExempluX0 = 5197X0
2 = 51972 = 27008809à X1=0088R1= 0.0088R1= 0.0088X1
2 = 882 = 00007744à X2=0077R2= 0.0077X2
2= 772=00005929 à X3 = 0059R3 = 0.0059
Zero-urile dupa punct apar in fiecare n.a. R i din sir
ExempluXi = 6500Xi
2 = 65002 = 42250000 à Xi+1=2500Ri= 0.2500
Probleme ale algoritmului “mid-square”.Degenerarea sirului
Ri= 0.2500Xi+1
2 = 25002 = 06250000 à Xi+2=2500Ri+1=0.2500
...Toate valorile ulterioare ale lui Xi, Ri vor fi 2500Concluzie: algoritmul mid-square nu este bun!
Metode analitice de generare a n.a.(2): Metode congruentiale liniare (Lehmer,1951)
LCG produc secvente de intregi X1, X2,… intre 0..m -1 conform cu urmatoarea relatie recursiva:
Xi+1 = (aXi + c) mod m, i = 0, 1, 2,…n Numim valoarea initiala X0 sămânţa generatorului (seed), a
este multiplicatorul constant, c e incrementul, iar m modululeste multiplicatorul constant, c e incrementul, iar m modululn Toti parametri sunt intregi n Dupa cum c ≠ 0 sau c = 0, avem doua forme:w Metoda congruentiala mixtaw Metoda congruentiala multiplicativa
n Selectia valorilor pentru a, c, m si x0 afecteaza foarte mult proprietatile statistice si lungimea ciclului
n N.a. distribuite uniform intre 0 si 1, U(0,1) se genereaza cu relatia: Ui = Xi /m, i = 1, 2, …
Metoda congruentiala mixta
Se caracterizeaza prin c ≠ 0 Exemplu:O secventa de n.a. cu x0 = 27, a = 17, c = 43, m = 100m = 100X1 = (17 x 27 + 43) mod 100 = 502 mod 100 = 2R1 = 2/100 = 0.02X2 = (17 x 2 + 43) mod 100 = 77 mod 100 = 77R2 = 77/100 = 0.77X3 = (17 x 77 + 43) mod 100 = 1352 mod 100 = 52R3 = 52/100 = 0.52...
Metoda congruentiala multiplicativa
Se caracterizeaza prin c = 0 Exemplu:Putem genera n.a. intre 0 si 1 prin aplicarea relatiei:relatiei:
si limitarea numarului de cifre zecimale retinut dupa efectuarea impartirii
mxx i
i =+1
Probleme ale LCG
i 22Xi+4 Xi+1 Ui--------------------------0 191 422 44 .69842 972 27 .4286
i 22Xi+4 Xi+1 Ui---------------------------11 378 0 .000012 4 4 .063513 92 29 .4603
X0=19, Xi+1=(22Xi + 4)mod 63
2 972 27 .42863 598 31 .49214 686 56 .88895 1236 39 .61906 862 43 .68257 950 5 .07948 114 51 .80959 1126 55 .873010 1214 17 .2698
13 92 29 .4603…62 708 15 .238163 334 19 .301664 422 44 .6984…
Observam: repetarea sirului dupagenerarea a 64 valori (modulul), darsi faptul ca repetitia valorilor nu s-a produs inainte.
Proprietati generale ale LCG
Orice LCG va cicla (cel mult dupa generarea a m n.a.); lungimea ciclului s.n. perioada LCGPerioada maxima pentru un LCG este mConditia necesara de a obtine un bun generator este “m foarte mare”foarte mare”Perioada este de obicei mai mica decat mExemplu:
X0 = 20, Xi+1 = (50Xi + 20)mod 100X1 = (50*20 + 20)mod 100 = (1020)mod 100 = 20
Conditia “m foarte mare” nu este si suficienta pentru a obtine un bun generatorExista conditii generale ce garanteaza un bun generator?
Teorema 1Un LCG are perioada maxima d.d.:
1. (m,c)=1 – m si c sunt prime intre ele2. daca exista q, prim, ce divide m, atunci acesta divide a-13. daca 4 divide m, atunci 4 divide a-1.Demonstratia este f. dificila (teorema de numere prime)Demonstratia este f. dificila (teorema de numere prime)Exemplu:n m=10d, pentru un intreg pozitiv d.n a se alege din seria 1, 21, 41, 61, 81,.....n c se alege din seria 1, 3, 7, 9, 11, 13, 17, 19,...
(intregi impari ce nu se divid cu 5)Aplicatie: demonstrati ca LCG din exemplu verifica conditiile teoremei
Modalitati de accelerare a LCGDepasirea (Overflow Division)n Ideea: intr-un calculator zecimal cu lungimea cuvantului 4,
6000+4001=0001; sau 34561332 mod 10000 = 1332, deci stocarea pe 4 biti implica efectuarea operatiei modulo
n Putem alege m=2b unde b=lungimea cuvantului calculatorn Putem alege m=2b unde b=lungimea cuvantului calculator
n Exemplu: pentru un PC cu procesor pe 32 de biti, m=232 sau chiar m=231, tinand cont de lungimea reala (fara semn)
Eliminarea lui c si obtinerea unui LCG multiplicativn Totusi, fara c rezultatul din teorema 1 nu are sens
n Exista o teorema ce stabileste conditii asemanatoare pentru generatoare multiplicative cu modul prim (PMMG)
Teorema 2Perioada generatorului este m-1 daca:
1. m este cel mai mare numar prim mai mic decat 2b
2. cel mai mic numar k pentru care ak-1 este divizibil prin m este k=m-1
Exemplu: Exemplu: n m=231-1, prim; a=75=16807n Nu putem aplica “overflow division” pt. acceleraren O metoda apropiata, numita “simulated division”,
asigura practic aceeasi viteza (principiu asemanator)
Modalitate de verificare a n.a. generate
Utilizarea unei simulari pentru a calcula valoarea numarului π(pi)• Fie (x, y) coordonatele unui punct P din patrat• Pentru punctele de pe P(x,y)• Pentru punctele de pe circumferinta cercului:
x2 +y2 = r2
• Folosind generatorul de n.a. pe care il avem, acoperim patratul prin 10 000 puncte aleatoare; fie a numarul de puncte din sfertul de cerc
x
yr
P(x,y)
Fie a numarul de puncte din sfertul de cercAria sfertului de cerc = Numar de puncte in sfertul de cerc
Aria patrat Numar de puncte in patrat
Acuratetea determinarii lui pi depinde de calitatea generatorului de n.a.
2
arπ
2500
100001*14
110000*
4
2
2
a
a
arr
r
=⇒
=
=
π
π
π
x
yr
P(x,y)
Functii de generare a n.a. in C/C++. Functiile rand() si srand()
Returneaza valori intregi generate (pseudo) aleator
rand() – returneaza acelasi sir de numeren Aplica metoda congruentiala multiplicativa (factor 232) si
returneaza secvente de n.a. intre 0..RAND_MAX (constanta simbolica e definita in stdlib.h, valoarea uzuala este 32767)simbolica e definita in stdlib.h, valoarea uzuala este 32767)
n Sirul de numere returnat poate fi schimbat daca se modifica valoarea implicita a variabilei seed (reinitializare generator)
srand() – face (re)initializarea generatorului de n.a.n Utilizare: srand(int iSeed)
n iSeed poate fi data explicit, ca o constanta (1=val.implicita), sau setata diferit la fiecare rulare, in functie de timp
Functia time() si operatorul %Trebuie inclus header-ul <time.h> ce contine definitia: “time_t time(time_t *tloc);”, echivalenta cu:“int time(int *tloc);” n tloc este locatia de memorie a unei variabile intregi unde poate fi
stocata valoarea generata (optional)
Descriere: time() returneaza valoarea intreaga (in sec.) de Descriere: time() returneaza valoarea intreaga (in sec.) de la 1/1/1970, pentru a obtine o valoare diferita a sămânţei la fiecare rulare a unui program n Daca tloc ≠ 0, valoarea returnata este si stocata in locatia spre
care pointeaza tloc
Operatorul % (modulo) permite scalarea valorilor:n rand( ) % 10 ⇒ un n.a. intre 0 si 9 inclusivn rand( ) % b + a ⇒ un n.a. intre a si b-1 inclusiv
Exemplu: generarea a 10 numere intre 0..20
// printing 10 random numbers// between 0 and 20:// Same numbers each run#include <iostream.h>using namespace std; main()
// printing 10 random numbers// between 0 and 20// Different numbers each run#include <iostream.h>#include <time.h>using namespace std;main()
int i, iNum;i = 1while ( i<=10 )
iNum = rand() % 21;cout << iNum << " ";i++;
int i = 1;
// print the timecout << time(NULL) << endl;
// seed the random number// generator with the time
srand( time(NULL) );while( i<=10 )
cout << rand() % 21 << " ";i++;
Tema: Proiect + ReferatConstruiti pachetul propriu de rutine de generarede numere aleatoare; implementati cel putin treimetode (functii) de generare de n.a. Implementati functii-criteriu de verificare privindcalitatea numerelor generatecalitatea numerelor generateImplementati pe baza generatorului de n.a. 2-3 generatoare de distributii simple (de ex.uniforma, binomiala, Bernoulli)Studiati proprietatile esantioanelor generate, princomparatie si cu date generate folosind Excel
Modelarea sistemelor de calculModelarea sistemelor de calcul
Generarea datelor de intrare
Curs, anul III Calculatoare
Generarea datelor de intrare2. Generarea distribuţiilor.
Fiind data o v.a. X si o variabila x, se defineste funcţia de repartitie (cdf):Cazuri:n FX(x): functie continua in x, daca X este v.a. continua
F (x): discreta in x, daca X este v.a. discreta
Distribuţii (repartiţii)
n FX(x): discreta in x, daca X este v.a. discretan FX(x): continua pe portiuni, daca X este v.a. mixta
Proprietăţi :n 0 ≤ FX(x) ≤ 1, -∞ < x <∞n FX(x) este functie monoton crescatoare in xn Avem 1)(lim,0)(lim ==
∞→−∞→xFxF X
xX
x
Functia densitatii de probabilitate (pdf)Daca X este v.a. continua, atunci
Proprietati ale pdf :1.
2.
Functia de repartitie (pmf)
Daca X este v.a. discreta, cu valorile posibile:x1, x2, ..., xn (altfel scris xi unde i=1, 2,...,n)
cu probabilităţile de aparitie p(xi) = P(X=xi), vom numi:p(xi) – functia masei de probabilitate pentru v.a. X(xi, p(xi)) – distributia de probabilitate (repartitia) lui X(xi, p(xi)) – distributia de probabilitate (repartitia) lui X
Proprietati ale pmf (probabilităţii elementare):1.
2.
ioricepentruxp i ,0)( ≥
1)(1
=∑=
n
iixp
Distribuţia eșantionată (de sondaj)Este data de o functie de tipul pdf sau pmf (sauechivalent de cdf) ce caracterizeaza valorile cetrebuie obtinute (si pe care statistica si le poateasuma) din esantioane aleatoare repetateO modalitate simpla de aproximare a distributieiO modalitate simpla de aproximare a distributieieșantionate: selecţia repetată a unui mare numarde esantioane aleatoare din multimea de intrareCalculul valorilor statistice pentru fiecare esantionsi construirea unei histograme dă o imagine aproximata a distributiei esantionate
Histograma
Se consideră un număr mare de secvenţe de aruncare a unei monede netrucate, și proporţia medie de apariţie a a banului (cap)Histograma apariţiilor, la 10000 aruncări:la 10000 aruncări:(cf. Wikipedia)Alte ex. de statistici:n Suma v.a.n Media v.a.n Dispersia v.a.
Media aritmetică de sondaj(sample average, sample mean-value)
Raportul dintre suma tuturor valorilor xobservate în eşantionul considerat şi numărul total n al acestora:
Observaţii∑
=
=n
1i
*ix
n1x
ObservaţiiÎn cazul valorilor observate, aranjate în ordine crescătoare sau descrescătoare:
unde:n - numărul total al valorilor observate;ni - frecvenţa absolută corespunzătoare valorii xi;fi - frecvenţa relativă corespunzătoare valorii xi.
∑∑==
==n
1iii
n
1iii xfxn
n1x
Dispersia de sondaj (σ2)(sample variance)
S.n. și moment centrat de ordinul doi:
Valoarea numerică a sa caracterizează în modul cel mai
∑=
−=n
iii xxn
n 1
22 )(1σ
Valoarea numerică a sa caracterizează în modul cel mai adecvat împrăştierea repartiţiei statisticeDispersia de sondaj poate fi folosită ca estimareaproximativă a dispersiei din populaţia originară, considerându-se formula corectă:
∑=
−−
=n
ii xx
n 1
22 )(1
1σ
Generarea unor esantioane aleatoare de date dupa identificarea unei distributii de probabilitatetrebuie sa respecte doua proprietati importante:nUniformitate: Distributia esantionului aleator si cea
Metode de esantionare (sampling)
Uniformitate: Distributia esantionului aleator si ceaidentificata pentru datele colectate sunt identice à in termeni statistici, media si varianta esantionului suntidentice cu media si varianta populatiei de intrare
n Independenţă: Atunci cand setul de esantioane e plasatin secventa in care a fost produs, nu exista un sablonneintentionat in aceasta secventa
Teoreme importante: Inegalitatea lui Cebîşev
Putem avea o imagine asupra repartiţiei prin cunoaşterea mediei şi dispersiei
Inegalitatea lui Cebîşev arata cat de mari sunt probabilităţile abaterilor de la medie:probabilităţile abaterilor de la medie:
Se poate aplica atât v.a. discrete cat şi continue
2
2
)|(|εσ
εµ ≤≥−xP
Teoreme importante: Legea numerelor mari
Bernoulli: Probabilitatea ca modulul diferenţei intre frecventa relativa de aparitie a unui eveniment E şi probabilitatea p a lui E sa fie mai mic decât un ε pozitiv, arbitrar de mic, este ≈1 pentru un nr. de experimente n suficient de mare
pnP 1 11)|(| ε −≥<−
Cebîşev: Probabilitatea ca modulul diferenţei intre media aritmetica A a valorilor medii a n v.a. independente şi media aritmetica a v.a. sa fie mai mica decât un ε pozitiv, arbitrar de mic, este ≈1 pentru n suficient de mare
np
nnP 2
1
411)|(|ε
ε −≥<−
nbAX
nP
n
ii 2
2
1
1)|1(|ε
ε −≥<−∑=
Proprietati generale ale distributiilor esantionate1. Distributia esantionata a unei statistici tinde sa
se centreze pe valoarea estimata a parametrului statistic corespunzator
2. “Imprastierea” valorilor distributiei esantionate 2. “Imprastierea” valorilor distributiei esantionate a multor statistici tinde sa fie tot mai mica pe masura ce marimea esantionului creste
3. Tot pe masura ce marimea esantionului creste, distributia esantionata a multor statistici devine tot mai similara unei distributii normale (forma de “clopot”)
Proprietati generale ale distributiilor esantionate (cont.)
Cand distributia esantionata a unei statistici estecoincidenta cu parametrul corespunzator al populatiei din care este extrasa, statistica s.n. nebalansata (unbiased) și constituie un estimator nebalansat al parametrului populatieinebalansat al parametrului populatiein Ex. este un estimator nebalansat al mediei
Deviatiile standard ale distributiilor generate suntin general mai mici decat deviatia standard a populatiei de intrare (σ). Variatia in distributia generata scade pe masurace marimea esantionului creste
x
Distribuţia normală (Gauss-Laplace)
Este definită den funcţia de repartiţie:
unde:
( )( )
dxexFx x
∫∞−
−−
= 2
2
22
21;; σ
µ
πσσµ
unde:
n funcţia de densitate a repartiţiei v.a. X:
R x0,σ R,μ ∈>∈
( )( )
2
2
2
21 σ
µ
πσ
−−
=x
exf
Distributia esantionata a medieiDistributia esantionata a mediei, , este acea distributie de probabilitate descriind esantioane aleatoare repetate dintr-o populatie (proces)
x
Daca se considera valoridintr-o populatie de intraredintr-o populatie de intrarecu media µ si deviatiastandard σ, formand maimulte esantioane (n), valorile medii formeazadistributia esantionata a mediilor (simple)
Media si deviatia standard a distributieiesantionate a mediilor ( )
Daca este media esantioanelor aleatoare x1, x2, …,xn, dintr-o populatie sau proces cu media µ sideviatia standard σ, atunci media distributieiesantionate a mediilor coincide cu µ , indiferentde numarul de esantioane (n)
xx
de numarul de esantioane (n)Abaterea distributiei esantionate descrise de , este egala cu abaterea standard a populatiei, raportata la radicalul marimii esantionului
xxσ
nxσ
σµµ == x si
Teorema de limita centrala (TLC)TLC (eng. Central Limit Theorem) afirmă că: pentru nvariabile aleatoare continue, identic repartizate cu aceeaşi medie (m) şi aceeaşi dispersie (σ2), atunci v.a.medie a eșantioanelor este aprox. normal repartizată, cu aceeaşi medie (m) și dispersia mai mică (σ2/n)aceeaşi medie (m) și dispersia mai mică (σ2/n)
Acest fapt are loc chiar pentru valori mici ale lui n
De fapt, TLC este un rezultat important și pentru căstabilește o “cheie de verificare”: , distribuţiaesantionata a mediilor, este aproximativ normala, independent de tipul distributiei populatiei de intrare
x
Teorema de limita centrala (cont.)
Pe masurace marimeaesantionuluicreste destulde mult
Distributia de esantionare devine aproape
de mult(≥ 30) ...
devine aproape normala.
X
(cf. Kendall – Introduction to Statistics)
Metode de generare a v.a. de repartitie data (non-uniforma)
Metoda transformarii inverseMetoda transformarii directe – se aplica pentru distributia normalaMetoda convolutieiMetoda acceptarii-rejectarii
Metoda transformarii inverse (1)Este aplicabila daca functia de distributieeste inversabilaMetoda se aplica unor distributii continue:n Exponentialan Exponentialan Uniforma (≠ U[0,1])n Geometrica
cat si tuturor distributiilor discreteDesi cea mai directa, nu este si cea maieficienta dpdv computational
Metoda transformării inverse (2)Fie o distributie oarecare descrisa prin cdf FX(x), pentru care exista inversa F-1
X(y) pe 0 ≤ y ≤ 1:F-1(y) = min x | F(x) ≥ y Daca U[0,1] e distributia uniforma, atunci v.a. X Daca U[0,1] e distributia uniforma, atunci v.a. X = F-1(U) are cdf F(x)Justificare. Se poate da ca o consecinta directa a relatiei:
[U<F(x)] ⊂ [X≤x] ⊂ [U≤F(x)] pentru orice xsau:
Justificare: v.a. X = F-1(U) are cdf F(x)
Daca v.a. X are cdf FX(x) si exista inversa F-1X(y)
pe 0 ≤ y ≤ 1, putem defini o noua v.a. Z=FX(X) pentru care FZ(z) = P(Z ≤ z) = P(FX(X) ≤ z) daca0 ≤ z ≤ 1.Deoarece exista F-1 (y) si din cauza proprietatiiDeoarece exista F-1
X(y) si din cauza proprietatiide monotonie: P(FX(X) ≤ z) = P(X ≤ F-1
X(y)) = FX(F-1X(z)) = z
care defineste v.a. Z ca U[0,1] (distrib.uniforma) atunci v.a. X = F-1(U) are cdf F(x)
Transformarea inversa
Transformarea inversa aplicata unei distributii continue oarecare•Fie o v.a. avand pdf f(x) = x/2, pentru 0<x<2
•Prin integrare directa rezulta F(x) = x2/4, pentru0<x<2
•Inversa este U2(U)F-1 =•Inversa este
•Prin urmare, pe baza generatorului de n.a. cudistributie uniforma U[0,1], se obtine v.a. X cucdf F(x) = x2/4, data de:
U2(U)F-1 =
U2X =
Transformarea inversa aplicataunei distributii discrete oarecare•Fie o v.a. avand pmf f(x) data de:
•Transformarea inversa conduce la obtinerea v.a.X pe baza generatorului de n.a. cu distributie
.4,3,2,1pentru ,10/][ === xxxXP
X pe baza generatorului de n.a. cu distributieuniforma U[0,1]:
≤<≤<≤
<
== −
UUU
U
UFX
6.046.03.033.01.02
1.01
)(1
Transformarea inversa aplicata la generarea distributiei exponentialeInterpretand parametrul λ ca medie a nr.de aparitiipe unitatea de timp, stiind ca daca U este distributieuniforma pe [0,1] si 1-U este U[0,1], avem:
Transformarea inversa aplicata la generarea distributiei geometrice
Functiile distributionale sunt:
,...2,1pentru ,)1()(: 1 =−= − xppxfpmf x
[ ] [ ] intreaga partea denota unde ,)1(1)(: xpxFcdf −−=
Atunci:
unde prin log(1-U)=-E s-a notat exponentiala
[ ] intreaga partea denota unde ,)1(1)(: pxFcdf −−=
Distributii uzuale si aplicatiile lor
Distributie Aplicatii
Bernoulli • Modelarea unui calculator, daca e functional sau nu• Un pachet intr-o retea isi atinge sau nu destinatia• Un bit dintr-un pachet soseste la destinatie cu
eroare (afectat de zgomot)eroare (afectat de zgomot)
Binomiala • Modelarea numarului de procesoare functionaleintr-un sistem multiprocesor
• Numarul de pachete dintr-o retea care isi atingdestinatia, fara pierderi
• Numarul de biti dintr-un pachet ce sosesc la destinatie cu eroare
• Numarul de articole dintr-un lot ce au anumitecaracteristici
Distributii uzuale si aplicatiile lor (2)
Distributie Aplicatii
Binomiala negativa
• Numarul de interogari locale intr-o baza de date distribuita, inaintea accesului n la distanta
• Numarul de retransmiteri necesar pentru un mesaj continand n pachetecontinand n pachete
• Numarul de biti succesivi fara eroare intr-un pachet, inaintea primirii celui de-al n-lea bit eronat
Geometrica • Numarul de interogari locale intr-o baza de date distribuita, inaintea acceselor succesive la distanta
• Numarul de pachete transmise cu succes, intre cele ce necesita retransmiterea
• Numarul de biti succesivi fara eroare intr-un pachet
Distributii uzuale si aplicatiile lor (3)
Distributie Aplicatii
Poisson • Numarul de cereri la un server intr-un interval de timp dat
• Numarul de defectari ale componentelor, in timpunitarunitar
• Numarul de interogari intr-o baza de date in t sec.• Numarul de erori de tiparire intr-un formular
Exponentiala • Timpul intre cereri succesive de servire• Timpul intre caderi succesive ale unui dispozitiv
Erlang • Modelarea timpilor de servire intr-o retea de cozi (m servere cu timpi de servire distribuiti exponential)
Distributii uzuale si aplicatiile lor (4)
Distributie Aplicatii
Normala • Modelarea erorilor de masurare• Distributia mediilor simple ale esantioanelor unui
mare numar de observatii independente (cf. teoremei de limita centrala)teoremei de limita centrala)
Log-normala • Modelarea unei distributii normale transformate
Uniforma • Modelarea dispozitivelor de i/e selectate pentru urmatoarea operatie de i/e
• Numerele de inregistrari returnate de cautarile intr-un fisier
• Numerele de pista returnate de cautarile pe disc
Tema: Proiect + ReferatConstruiti un pachet propriu de generare de distributii; folositi metoda transformarii inverse acolo unde ea se aplicaReprezentati grafic distributiile obtinuteCalculati momentele (statisticile) semnificativepentru esantioanele generate; comparati-le cu cele teoreticeStudiati proprietatile esantioanelor generate, princomparatie si cu date generate folosind Excel
Modelarea sistemelor de calculModelarea sistemelor de calcul
Modele pentru sistemele (dinamice)
Curs, anul III Calculatoare
Modele pentru sistemele (dinamice) cu evenimente discrete
Terminologie şi concepte de bazăTipuri de modele. Modele bazate pe stareAutomate cu stări finiteReţele Petri “clasice”. Descrieri
Sumar
Reţele Petri “clasice”. Descrieri Modelarea conceptelor dinamiceModele şi limbaje. Exemple de modelareModele bazate pe urme. Nivele de studiuAlte tipuri de modele şi clasificări
Terminologie şi concepte de bazăSistem - o colecţie de entităţi in interacţiune
Model - o reprezentare abstractă a sistemului
Entitate - componentă a sistemului cu reprezentare explicităin model (obiect de interes in sistem)
Atribut - o proprietate a unei entităţi Atribut - o proprietate a unei entităţi
Set - colecţie de entităţi asociate, permanent sau temporar
Eveniment - o apariţie instantanee ce schimbă starea sistemului
Activitate - o perioada de timp de lungime cunoscuta la începutul ei
Întârziere - o perioada de timp nespecificată ca lungime →necunoscută până la terminarea ei
Concept cheie: “Eveniment”Este un rezultat brusc al îndeplinirii simultane a mai multor condiţiiPoate fi:§ Endogen: apărut in interiorul sistemului
§ Exogen: apărut in mediul extern, dar care afectează sistemul
Intr-o alta perspectiva: n evenimentul este rezultatul unui “proces-eveniment”,
doar acesta determinând timpul apariţiei salen tranziţiile de stare rezulta prin combinarea proceselor
eveniment, asincrone si concurente
Dinamica de sistem si modelEvoluţia in timp a SDED depinde de interacţiunea complexa a momentelor de apariţie a diferitelor tipuri de evenimente Dinamica SDED este determinata de interacţiunile complexe ale sincronizării evenimentelor discrete complexe ale sincronizării evenimentelor discrete asociate cu activităţile/resursele n Dinamica modelului trebuie sa o reflecte pe cea a
sistemului de baza n DAR: dinamica modelului poate fi ameliorata prin unele
metode
ComplexitateaImprimă dificultatea descrierii unui SDED
Complexitatea crescută a sistemului rezultă din: n Capacitatea crescută (numărul mare de componente)w Sisteme simple: aparate electrocasnice, linii de fabricaţie → w Sisteme simple: aparate electrocasnice, linii de fabricaţie →
un model programat poate avea sute sau mii de linii de cod
w Aplicaţii complexe: calculatoare, reţele de calcul sau de comunicaţie → modelele au sute de mii de linii de cod
n DAR şi din interacţiunea complexa a momentelor de apariţie a diferitelor tipuri de evenimente
Metode de descriereEste posibil ca “funcţionarea” dorită a modelului să nu poată fi obţinută fiindcă nu este descrisă corect şi complet funcţionarea sistemuluin Apar erori de implementare datorită descrierilor
incomplete sau eronateincomplete sau eronateMetodă uzuală: utilizarea unui limbaj naturaln Descrierea precisă a sistemului este foarte dificilă
Metodă recomandată: utilizarea de formalismeşi modele computaţionalen Sunt precise, neambiguen Pun la dispoziţie un set de obiecte şi reguli pentru
compunerea obiectelor
Tipuri de modele
n Modele bazate pe staren Modele bazate pe urmen Modele orientate pe activitaten Modele orientate pe activitaten Modele orientate pe structurăn Modele orientate pe daten Modele eterogene
Modelele bazate pe stareReprezintă sistemul ca un set de stări şi un set de tranziţii între stări – o tranziţie e determinatăde evenimente externeCategorii:n Automate cu stări finiten Automate cu stări finite şi căi de daten Automat cu stări finite ierarhice concurenten Reţele Petri
Se utilizează pentru sisteme de control:n monitorizarea unor intrări de control; n setarea unor ieşiri de control
Automate cu stări finite (ASF)Un set de stări ale sistemuluiUn set de tranziţii posibile între stăriUn set de acţiuni asociate cu stările sau tranziţiile<S, I, O, f, h, s ><S, I, O, f, h, s0>S = s0, s1, …, sl setul de stăriI = i0, i1, …, im setul de intrăriO = o0, o1, …, on setul de ieşirif – funcţia stării următoare, f : S x I → Sh – funcţia de ieşire s0 – starea iniţială
Tipuri de ASF (1)Maşina Mealy (bazată pe tranziţii)h : S x I → O
Ex. Controler de ascensor într-o clădire cu 3 etajeI = r1, r2, r3
→ etajul cerut → etajul cerut O = d1, d2, n, u1, u2
→ direcţia şi nr. de etajecu care trebuie să se deplaseze ascensorul
Tipuri de ASF (2)Maşina Moore (bazată pe stări)h : S → O
Ex.
Critica modelelor ASFMaşina Moore necesită un nr. mai mare de stări decât maşina Mealyn Justificare: fiecare valoare de ieşire necesită propria
stare (pot exista arce multiple ce indica aceeasi stare)
Ambele sunt modele teoretice si idealizateAmbele sunt modele teoretice si idealizateSpaţiul si timpul sunt modelate si referite absolutProcesele lucrează sincronSe pot utiliza pentru sisteme la care predominăpartea de controlNu permit descrierea sistemelor complexe (aparefenomenul de “explozie a stărilor”)
Automate cu stări finite şi căi de date
Extind modelul ASF cu tipuri de date complexe/ variabilen Modelul ASF utilizează numai tipuri de date şi operaţii booleene
Permit astfel reducerea numărului de stări
Descriere: ASFD = <S, I, O, V, f, h, s0>n V = v0, v1, …, vn setul variabilelor
n f – funcţia stării următoare, f : S x I x V → Sn h – funcţia de acţiune, h : S → O + V (Moore)
n I, O şi V pot conţine tipuri de date complexe, ca şi limbajele de programare
n f şi h pot conţine operaţii aritmetice
n h descrie şi actualizarea variabilelor
ASFD – Exemplu (controler ascensor)
ASFD se pot utiliza şi pentru sisteme (predominant) de control, şi pentru cele la care predomină partea de calculTotuşi, niciunul dintre modelele ASF si ASFD nu este adecvat pentru sistemele complexe, deoarece ele nu permit reprezentarea explicită a concurenţei şi a ierarhiei
Automate cu stări finite ierarhice concurente (ASFIC)
ASFIC reprezintă o extensie a ASF, ce permite:n Construcţia ierarhica a modelelor n Concurenţan Descrierea lor intr-un limbaj grafic (statecharts)
Se pot grupa într-o nouă stare ierarhică mai Se pot grupa într-o nouă stare ierarhică mai multe stări Fiecare stare poate fi descompusa intr-un set de (sub)stăriDouă metode de descompuneren SAU: o stare este descompusă în (sub)stări secvenţialen ŞI: stările se pot executa concurent
Ierarhizarea stărilor
Fără ierarhie
A
Cu ierarhie
Tranziţiile pot fi structurate sau nestructuratenTranziţiile structurate sunt permise între stări cu acelaşi nivel ierarhicnTranziţiile nestructurate pot apărea între 2 stări oarecare
Stările A1 şi A2 au fost grupate în starea ierarhică ATranziţia în starea B la evenimentul z se realizează din starea A, nu A1 sau A2
A1 z
B
A2 z
x y w
A1 z
B
A2
x y
A
w
Concurenţa
B
Concurenţă
Fiecare stare se execută prin mai multe sub-stări concurenteComunicaţia se realizează prin variabile globaleDouă sau mai multe stări concurente pot fi grupate într-o nouă stare ierarhică
Starea B a fost descompusă în stările concurente C şi DStările C şi D sunt descompuse fiecare în două stări ierarhice
C1
C2
x y
C
D1
D2
u v
D
StatechartsLimbaj grafic ce permite ierarhia, concurenţa şi comunicaţia între stările concurente; utilizează tranziţii nestructurate
Starea Y este descompusă în două stări concurente, A şi D; prima constă din două substări B şi C, iar a doua cuprinde substările E, F şi G.Dacă apare evenimentul b în timpul stării C, are loc transferul în starea B. Dacă apare evenimentul a în timpul stării B, are loc transferul în starea C, dar numai dacă este îndeplinită condiţia P în momentul apariţiei evenim. În timpul transferului din starea B în starea C, se va executa acţiunea c, care este asociată cu această tranziţie.
Reţele Petri “clasice” (C/E)Model orientat pe stare, ce extinde modelele de tipul AF pentru a permite modelarea dinamicii asincrone a unui sistem (inclusiv concurenta, comunicaţie etc.)Elemente: locaţii, conţin simboluri ce s.n. jetoane (0/ 1), si tranziţii, plus arce ce leagă elemente de tip diferit si tranziţii, plus arce ce leagă elemente de tip diferit n in RP C/E poate exista cel mult un arc intre 2 noduri
Terminologien Sistem C/E: reţea C/E + marcajn Configuraţii: marcajele posibile ale unei reţele C/E n Cazuri: configuraţiile accesibile din marcajul iniţial (→case graph)
In anii ’60 -’70, accentul principal s-a pus pe dezvoltări teoretice; din anii ’80 se insista pe instrumente şi aplicaţii
DescrieriGrafice (grafuri bipartite) şi matematice, cu semanticăformală şi posibilităţi de analizăCaracteristici importante: stări distribuite şi tranziţii localeExemplu: RP = <P, T, Pre, Post, M>Exemplu: RP = <P, T, Pre, Post, M>
P = l0, l1, …, lm setul poziţiilor (locaţiilor)T = t0, t1, …, tn setul tranziţiilorPre : T → L+, funcţia de intrare, ce defineşte locaţiile care
furnizează intrări unei tranziţiiPost : T → L+, funcţia de ieşire, defineşte locaţiile de ieşire
pentru fiecare tranziţieM : L → 0,1, funcţia de marcaj, defineşte numărul de simboluri
din fiecare locaţie
Condiţii şi resurseReţelele de tip C/E modelează fluxurile de informaţii, la nivel fundamental (true/false)
Aplicaţii: cele in care fluxul de resurse si/sau numarul de resurse disponibile este important (document workflow, data flow, linii de fabricaţie, reţele de comunicaţie, www)data flow, linii de fabricaţie, reţele de comunicaţie, www)
2
3
Reţelele de tip P/T reprezintă o generalizare (extensie) imediata:n Elementele de stare sunt echivalente locaţiilor
unde sunt stocate resurse (jetoanele)n Elementele de acţiune sunt reprezentate de
tranziţiile locale sau transportul resurselorn Poate fi aplicata o descriere matematica
similara cu cea a RP C/E
Exemplu RP: O reţea PT (1)p1
p2p3
t2p4t3
p5
t6t1
p8
p5 p6 p7t4 t5
Exemplu RP (2)p1
p2 p3
t6t1
p8
t2p4t3
7654321
001010100000010000001000100000000100000010000001
Pre
pppppppp
=
p5
p5 p6 p7t4 t5
654321
87
001010tttttt
p
654321
87654321
010100010000001000000001000100000010000001100000
Post
tttttt
pppppppp
=Matricea de incidenţă
−−−
−−
−−
−−
==
011110110000011000001001100100000110000011100001
Pre-PostI
Exemplu RP (3)p1p2 p3
p5
t6t1 p8
t2p4
p5
p
p7
t3
t t
=
=000014
)()5()4()3()2()1(
pMpMpMpMpMpM
M
=′
000104
Mp6t4 t5
110
)8()7()6(
pMpMpM
p5 p7
p1p2 p3
p5
t6t1 p8
t2p4
p6
t3
t4 t5
010
t2 este validata si se declanseaza
),(),(Post),(Pre'
tCMttMM
⋅+=⋅+⋅−=
O reţea PT poate fi mai întâi definită structural, de ex. prin 5-tuplul: (P, T, A, C, w), unden P este o mulţime finită de poziţii (locaţii)n T este un set finit de tranziţiin A este o mulţime de arce, o submulţime a mulţimii
(P×T)∪(T×P)
O alta definiţie formală (pt. reţele PT)
(P×T)∪(T×P) n C: P → (N ∪ ∞) \0 este o funcţie de capacitate a
poziţiilor (capacitatea unei poziţii e implicit nelimitată)n w e funcţia de ponderare aplicată arcelor, w:A→1,2,3 ...
(ponderea unui arc se consideră implicit unitară)Prin M0: P → N ∪ ∞ notăm funcţia numită marcaj iniţialDefiniţia dinamică a reţelei PT constă în evidenţierea modalităţilor (legilor) de evoluţie a marcajului iniţial
Modelarea conceptelor dinamice in RP (1)(C/E si PT)
A B
concurenţă
A B A B
concurenţă sincronizare comunicare
A B
conflict/alegere
A B
resurse/multiplicitate
A B
date/individualitate
Modelarea conceptelor dinamice in RP (2)
(a) secvenţiere; (b) ramificaţie; (c) sincronizare;(d) conflict la resurse; (e) concurenţă
Concluzii (modelare cu reţele Petri elem.)
Se poate utiliza pentru a testa şi valida anumite proprietăţi utile ale sistemelorn Siguranţa: este garantată prin faptul că numărul de
simboluri nu creşte nedefinitFuncţionalitatea: este garantată prin lipsa blocajelor n Funcţionalitatea: este garantată prin lipsa blocajelor → va exista întotdeauna cel puţin o tranziţie care poate fi declanşată
Avantaj: modelarea sistemelor concurenteDezavantaj: nu este utilă pentru sisteme complexe
Modele şi limbajeUn model computaţional: descrie funcţionalitatea dorită a sistemului → noţiune conceptualăLimbajul: descrie modelul sub o formă concretăUn model poate fi descris într-o varietate de Un model poate fi descris într-o varietate de limbajen Exemplu: model al programului secvenţial → C,
C++, Java
Un limbaj poate descrie o varietate de modelen Exemplu: C++ → model obiectual, model al
programului secvenţial, automat de stare
Exemplu
Controler pentru un ascensorn Specificaţie modificată:
“Deplasează ascensorul în sus sau în jos până la etajul cerut. La etajul cerut, deschide uşa pentru cel etajul cerut. La etajul cerut, deschide uşa pentru cel puţin 10 secunde şi păstrează uşa deschisă până când etajul cerut se modifică. Păstrează uşa închisă în timpul deplasării. Schimbă direcţia doar dacă nu sunt cereri la etaje superioare în timpul deplasării în sus sau dacă nu sunt cereri la etaje inferioare în timpul deplasării în jos…”
Interfaţa sistem
Două blocuri:n RezCereri
rezolvă diferitele cereri de etaje într-un
UnitControl
b1
down
open
floor
req
up
cereri de etaje într-un singur etaj cerut
n UnitControldeplasează ascensorul la etajul cerut
butoane îninteriorul
ascensorului
b1...
RezCereri
...
butoaneup/down la fiecare etaj
b2bNup1
up2dn2
dnN
up3
dn3
dn1
Descrierea unităţii de controlInputs: int floor; bit b1..bN; up1..upN-1; dn2..dnN;Outputs: bit up, down, open;Global variables: int req;void UnitControl()
up = down = 0; open = 1;while (1)
while (req == floor);while (req == floor);open = 0;if (req > floor) up = 1;else down = 1;while (req != floor);up = down = 0;open = 1;delay(10);
Modelul ASF pentru UnitControl
GoingUp
req > floor
!(req > floor)
req > floor
u,d,o, t = 1,0,0,0timer < 10
Idle
req < floor
!(timer < 10)
req < floor
DoorOpen
GoingDn
u,d,o,t = 0,0,1,0
u,d,o,t = 0,1,0,0
u,d,o,t = 0,0,1,1
u: up; d: down; o: open; t: timer_start
req == floor
!(req < floor)
Modelul ASFIC (1)Modificarea controlerului pentru ascensor n Intrarea fire → trecerea în modul de incendiun Deplasarea ascensorului la primul nivel şi deschiderea uşii
Fără ierarhie
req>floor UnitControl
Idle
GoingUp
req>floor
req<floor
!(req>floor)
timeout(10)
req<floor
DoorOpen
GoingDn
req>floor
u,d,o = 1,0,0
u,d,o = 0,0,1
u,d,o = 0,1,0
req==floor!(req<floor)
fire
firefire
fire
FireGoingDn
floor>1
u,d,o = 0,1,0
u,d,o = 0,0,1
!fire
FireDrOpen
floor==1
fire
u,d,o = 0,0,1
UnitControl
Modelul ASFIC (2)Cu ierarhie
GoingUp
req>floor
!(req>floor)req>floor
u,d,o = 1,0,0
ModNormal
UnitControl
fire
!fireFireGoingDn
floor>1
u,d,o = 0,1,0
FireDrOpen
floor==1
fire
ModIncendiu
u,d,o = 0,0,1
Idle
req<floor
timeout(10)
req<floor
DoorOpen
GoingDn
u,d,o = 0,0,1
u,d,o = 0,1,0
req==floor!(req>floor)
u,d,o = 0,0,1
Modelul ASFIC (3)Controlerul pentru ascensor reprezentat prin modelul ASFIC cu două stări concurente
ControlerAscensor
Cu starea concurentă RezCereri
ModNormal
ModIncendiu
fire!fire
UnitControl
ControlerAscensor
RezCereri
...
Exemplu ASF/ RPAutomat de distribuţie (vânzare): n Distribuie 2 tipuri de batoane, de 20 bani si 15 banin Se pot folosi doar 2 tipuri de monede, de 10 b si 5bn Nu returnează rest
Modelarea:n Se realizează diagrama de tranziţie a stărilorn Se obţin apoi modelele cu ASF si RP
Modelul ASF
155
10
vânzare baton 15b
5
201010
55
10
5
vânzare baton 20b
0
Modelul cu RP ordinară (maşină de stare)
510
vânzare baton 15b
10
5
5
10
5
vânzare baton 20b
Modele bazate pe urmeComportarea SDED este in mod naturaldescrisa de înregistrarea sau urma “lăsată” deapariţia unor schimbări discrete, calitative, insistemMicro-schimbările continue, cantitative pot fi pursi simplu ignorateIn afara modelelor bazate pe stare, modelelebazate pe urme, studiate la diferite nivele,sunt foarte utile
Nivele de studiu/ modelare (1)Nivelul logic – “urma” este secvenţa de
evenimente, in ordinea aparitiei lors = e1 e2 e3 ...;
Exemple: Exemple: n reţelele Petri (“cazuri” = urme)n maşinile cu stări finite (Wonham) n procesele recursive finite (Inan-Varaiya) n procesele secvenţiale comunicante (Hoare)
Nivele de studiu/ modelare (2)
Nivelul temporal - urma este secventa de perechi
s = (e1,t1) (e2,t2) (e3,t3) ...
Exemple: Exemple: n reţele Petri temporale n modele algebrice min-maxn grafuri data-flow
Nivele de studiu/ modelare (3)Nivelul statistic - comportarea sistemului e
descrisa de secvenţa perechilor de v.a.s = (e1,t1) (e2,t2) (e3,t3) ...
(unde ei si ti sunt v.a. si pentru orice realizare ω, s(ω)= (e (ω),t (ω)) (e (ω),t (ω)) (e (ω),t (ω)) ... este o= (e1(ω),t1(ω)) (e2(ω),t2(ω)) (e3(ω),t3(ω)) ... este ourma descrisa la nivel temporal)
Exemple:Lanţurile MarkovSistemele cu cozi de aşteptare si reţelele de coziModelele de simulare - având la baza procesele semi-Markov generalizate (GSMP)
Alte tipuri de modele (1)Modele orientate pe activitaten Descriu sistemul ca un set de activităţi
n Activităţile sunt asociate prin dependenţe de date sau de execuţiedate sau de execuţie
n Exemplu: graf al fluxului de date
n Se utilizeaza pentru sisteme dominate de datew Transformă şiruri de date de intrare în şiruri de
date de ieşire → sisteme DSP
Alte tipuri de modele (2)Modele orientate pe daten Reprezintă sistemul ca o colecţie de date
asociate prin atribute, apartenenţă la clase etc.etc.
n Utilizate mai ales pentru sisteme de programen Exemplu: diagramele E/R (entitate – relaţie)
<fig>
Alte tipuri de modele (3)Modele orientate pe structurăn Descriu modulele fizice ale sistemului şi
interconexiunile dintre acestean Nu reprezintă funcţionarea sistemuluin Exemplu: schemă-blocModele eterogenen Integrează caracteristici ale mai multor
modele n Exemplu: graf al fluxului de control/date
Alte clasificăriModele analitice (teoretice)n sistemice, in general deterministe , descrierea se
face la nivel logic sau temporaln operaţionale, in general probabilistice (statistice)
Modele de simularen derivate din modelele operaţionalen adecvate pentru analiza asistata de calculator
Pentru modelarea SDED la nivel statistic (cea mai completa) se pot folosi in tandem: n modele operaţionale + modele de simulare
Utilizarea modelelor statisticeModelele operaţionale - se pot folosi in cazurile când putem obţine prin calcul formule/ rezultate exacte (având modalităţi de a simplifica problemele computaţionale)n Exemple: sisteme cu cozi de aşteptare, reţele de cozin Limitare: cozi simple
reţele de cozi factorizabilereţele de cozi factorizabile
Modelele de simulare - oferă un instrument complet ce aproximează dinamica sistemului prin oferirea de ipostaze non-continue incrementalen Pro:
Dinamica originala a SDED este de acest tip!n Contra:
Dificultăţi computaţionale (există soluţii!)
Modelarea sistemelor de calculModelarea sistemelor de calcul
Modelarea logică şi controlul
Curs, anul III Calculatoare
Modelarea logică şi controlul supervizor al sistemelor dinamice cu
evenimente discrete
Modelare şi control cu automate finiteLimbaje formale şi expresii regulateObţinerea modelelor ASF. Echivalenţa stărilor
Sumar
stărilorControlul supervizor: descrierea problemei şi implementărilorStudiu de caz: Controlul supervizor al unei reţele de calculatoare conectate liniar
Alegerea unui model pp. un compromis între:n Puterea de modelare (generalitatea)w reţelele Petri includ strict clasa automatelor finite şi sunt la
rândul lor strict incluse în clasa algebrelor procesuale
n Complexitatea modelului
Modelare şi control
n Complexitatea modelului w aceasta implică şi complexitatea controlului
De exemplu, o problemă de control poate fi: n indecidabilă (nu se poate găsi un algoritm finit pentru
rezolvare) pentru un model sistem cu reţele Petri sau algebre procesuale
n rezolvabilă în cazul modelării SDED cu automate de stare finite (ASF), ce facilitează sinteza unui controler
Modelul ASF este un model formal bazat pe stare, ce consideră explicit stările unui sistemn Poate apare explozia stărilor (multiplicarea stărilor,
exponenţial, cu depăşirea unui prag de complexitate)! De aceea, majoritatea modelelor SDED nu consideră
Modele ASF pentru control
n De aceea, majoritatea modelelor SDED nu consideră explicit stările - abordare incompletă ce poate oferi doar observarea unui sistem, nu şi controlul !
ASF au o aplicabilitate foarte largă, caracterizată de generalitate, putere analitică şi controlabilitate n Cea mai cunoscută aplicaţie: în teoria compilării, la
recunoaşterea limbajelor regulate
Ideea utilizării ASF în modelarea logică a SDED: orice SDED este “un generator de limbaj”El are un “alfabet” de evenimente asociat şi generează o urmă sau traiectorie
Modelarea SDED cu ASF
Suntem interesaţi de secvenţele de evenimente ce pot fi generate (analogie cu generarea şirurilor de atomi lexicali în limbajele regulate, cf. unui set de reguli)
Asimilarea generatorului cu o structură de tip ASF este utilă pentru aplicarea tehnicilor de control convenţionale
Termenul “generator” este folosit alternativ cu ASF
Definiţie. Un limbaj formal L, definit peste un alfabet (mulţime) de simboluri E, e o mulţime de şiruri (de obicei finite) formate cu simboluri din En Lungimea unui şir este dată de numărul de simboluri alăturate
(concatenate) pentru formarea saŞirul vid, notat ε, ce nu conţine nici un simbol, este considerat
Limbaje formale
n Şirul vid, notat ε, ce nu conţine nici un simbol, este considerat prin convenţie de lungime 0
Dacă evenimentele se consideră ca simboluri din E n “Limbajul” poate fi gândit ca o modalitate formală de a descrie
comportarea unui SDED, ce specifică toate secvenţele admisibile de evenimente pe care SDED e capabil să le “execute”
n O dificultate: simple reprezentări finite ale limbajului nu sunt întotdeauna şi lucrative → sunt necesare modalităţi (expresii) compacte în definiţia sa, manipulabile prin operaţii bine definite
Definiţie. O expresie regulată R este un şir de simboluri construit pe baza alfabetului limbajului (inclusiv şirul vid), folosind doar operaţiile uzuale cu mulţimi (∪, ∩, ¬, etc.), plus operaţiile de concatenare şi închidere (Kleene), definite astfel:
Expresii regulate
concatenare şi închidere (Kleene), definite astfel:n (concatenare) dacă A, B sunt expresii regulate peste E,
atunci AB=cc=ab, a∈A, b∈B e o expresie regulată peste alfabetul E
n (închidere) dacă A este expresie regulată peste E, atunci şi A* = A0 ∪A1∪ ... ∪An-1∪An∪... este o expresie regulată, unde A0=ε şi An=AAn-1, ∀n>0
Definiţie. Un limbaj ce admite doar expresii regulate se numeşte limbaj regulatn Dacă I⊆E* este un limbaj (regulat), se defineşte închiderea lui I,
notată Ī, ca mulţimea tuturor şirurilor ce reprezintă prefixe de şiruri din I, adică: Ī = s s∈E* şi ∃t∈E* a.î. st∈ I
n Dacă limbajul e identic cu închiderea sa, el s.n.închis (prin prefix)
Limbaje regulate
n Dacă limbajul e identic cu închiderea sa, el s.n.închis (prin prefix) Avantajul utilizării expresiilor regulate în descrierea limbajelor este acela că asigură o reprezentare compactă finită, chiar pentru limbaje potenţial infinite (cu număr infinit de şiruri de simboluri)Modelul Ramadge-Wonham: un SDED este asimilat unui limbaj formal (regulat) – sau, mai concret, unui automat generator al acestui limbaj → dar ce fel de automat?Se ştie că ASF generează expresii (deci limbaje) regulate
Teorema lui Kleene. Dacă un limbaj este regulat, există un ASF ce-l genereazăOrice limbaj generat de un ASF este regulat
Definiţia 2.2.3. Un automat (generator) este un 5-tupluG = (X, E, f, x0, Xm)
ASF, limbaje şi expresii regulate
G = (X, E, f, x0, Xm)caracterizat de:n X - mulţimea stărilorn E - alfabetul (mulţimea) de simboluri (evenimente)n f :E×X→X - funcţia de tranziţie - funcţie parţială, în sensul că
pentru o stare x fixată, f(e)=f(e,x) este definită doar pentru o anumită submulţime Γ(x)⊆E, ce depinde de x
n x0 – starea iniţială; n Xm - mulţimea stărilor marcate (se preferă această denumire în
locul celei consacrate ce face referire la aceste stări ca stări finale)
Exemplu
Recunoașterea unei ER folosind generarea sa de către un ASF. Orice expresie regulată E poate fi recunoscută de un
automat finit care recunoaşte orice cuvânt din limbajul descris de E, şi doar acele cuvinte. Starea 1 este starea
iniţială, iar stările 1 şi 2 sunt stări finale
Execuţia ASF când la intrare este prezentat cuvântul ''abbab''. Pentru că după terminarea procesării şirului automatul nu este într-o stare
finală, rezultă că acest cuvânt nu e descris de expresia regulată
Modelul generator pleacă din starea iniţială x0 şi execută tranziţii de stare determinate de secvenţa de evenimenteEvenimentele apărute sunt considerate spontane (nu apar mecanisme de constrângere care să forţeze apariţia lor în sistem), asincrone (fără referire la vreun ceas de timp) şi instantanee (fără durată temporală)Modelul este unul logic ce poate îngloba nedeterminismul:
ASF generator
Modelul este unul logic ce poate îngloba nedeterminismul: mai mult de un eveniment poate fi executabil (validat pentru selecţie) într-o anumită staren Putem adăuga la model o mulţime de evenimente valide în starea
x, Γ(x), dacă ea depinde de stare şi este (în general) diferită de En Nu vom face distincţie între ASF deterministe şi nedeterministe;
definiţia ultimei categorii comportă o singură modificare, a funcţiei de tranziţie a stărilor: f :E×X→2X, unde 2X e mulţimea părţilor lui X
n Deşi, aparent, ASF nedeterministe pot genera un set extins de limbaje, de fapt orice limbaj generat de acesta poate fi generat de un ASF determinist
Notăm E* mulţimea tuturor şirurilor finite de evenimente din E, ce include şirul vid, notat εPutem construi funcţia de tranziţie extinsă, f :E*×X→X definită prin f(ε,x)=x şi f(es,x)=f(e,f(s,x)), ∀x∈X unde f este definită
Funcţia de tranziţie extinsă este tot o funcţie parţială, adică pentru
Funcţia de tranziţie extinsă
n Funcţia de tranziţie extinsă este tot o funcţie parţială, adică pentru o anumită stare x fixată f(s)= =f(s,x) este definită doar pentru o anumită submulţime de secvenţe E*(x)⊆E* ce depinde de x
Trebuie să facem distincţie între: n mulţimea tuturor secvenţelor finite de evenimente ce pot apărean mulţimea tuturor secvenţelor finite de evenimente observabile (de
ex. pentru că ele corespund execuţiei unor procese complete) Este convenabilă de asemenea eliminarea din model a stărilor ce nu pot fi atinse
În evoluţia sa, SDED defineşte: n un limbaj (închis prin prefix) L(G)=s∈E*f(s,x0) definită n un limbaj marcat Lm(G)=s∈L(G)f(s,x0) ∈ Xm
(interpretarea este cea de mai sus, ca mulţime a secvenţelor finite de evenimente ce pot apărea, respectiv ca mulţime a tuturor secvenţelor finite de evenimente ce pot fi observate)
Limbaje generate de ASF
tuturor secvenţelor finite de evenimente ce pot fi observate) Definirea componentelor accesibile se face astfel:n Xac = x∃s∈E* a.î. f(s,x0)=xn Xacm = Xac ∩ Xmn Fac = f E×Xacn Gac = (Xac, E, Fac, x0, Xacm)SDED s.n. accesibil dacă G = Gac şi co-accesibil dacă orice şir (parţial) de evenimente din L(G) se poate completa la un şir din Lm(G): ∀s∈L(G), ∃t∈Lm(G) a.î. st∈Lm(G).
Bazate pe o descriere la nivel logic a unui SDED, se pot găsi mai multe modele ASF n Aparent, ele sunt distincte deoarece au o dimensionalitate diferită
a spaţiului stărilorn De dorit este obţinerea celui cu număr minim de stări, având în
vedere şi explozia spaţiului stărilor, semnalată anterior Reducerea (agregarea) spaţiului stărilor se bazează pe
Echivalenţa stărilor
Reducerea (agregarea) spaţiului stărilor se bazează pe echivalenţa stărilor, a cărei definiţie (cea considerată aici) are în vedere o raportare la stările marcate Definiţia 2.2.4. Fiind dat ASF: (X, E, f, x0, Xm, Γ), dacă X este spaţiul stărilor, R⊆X e un spaţiu de stări echivalentcu X, relativ la Xm, dacă ∀x,y∈R stări distincte şi orice şir u, f(x,u)∈Xm d.d. f(y,u)∈Xmn Altfel spus: orice şir comun aplicat stărilor x şi y conduce la
acelaşi set de stări marcate n Distincţia între x şi y e imposibil de făcut prin observaţia pasivă a
sistemului, iar x şi y pot fi tratate ca o unică stare “agregată”
Evoluţia SDED modelat prin ASF, aşa cum a fost descrisă până acum, este o evoluţie spontană, necontrolatăPentru un sistem dinamic în general şi pentru un SDED în particular:n dacă starea completă a sistemului este observabilă, se poate
Controlul supervizor: Problema
n dacă starea completă a sistemului este observabilă, se poate construi un controler în buclă de reacţie (feedback controler)
n dacă doar evenimentele sunt observabile, implementarea unui controler se face aplicând în prealabil un artificiu ce constă în crearea unei copii a sistemului ce se execută în paralel şi sincron cu sistemul, acţiunea de control necesară fiind decisă prin măsurarea stării copiei sistemului
Controlerul sau copia sistem plus controlerul formează un supervizor
Schema controlului supervizor
SDEDSistem de
observare a evenimentelor
Stare
Evenim.observate
Intrări de control
Copie SDEDFeedback Controler(compensator dina-mic de stare) Stare
(estimată sau exactă)
SUPERVIZOR
Se partiţionează E prin identificarea a 2 submulţimi:n mulţimea evenimentelor controlabile Ec – acelea ce pot fi validate
sau invalidate din exteriorul sistemului datn mulţimea evenimentelor necontrolabile Enc (Ec∩Enc=Φ) – sunt cele
a căror apariţie nu poate fi prevenită şi deci pot fi considerate permanent validate
Controlul supervizor: Implementarea
permanent validate
Un supervizor poate controla SDED prin: n observarea secvenţelor de evenimente generate n dezactivarea, activarea sau forţarea evenimentelor controlabile,
pentru a îndeplini un obiectiv de control, în funcţie de secvenţele observate
Prin aceasta, supervizorul asigură generarea de către sistem a unui sublimbaj a lui L(G)
Formal, supervizorul poate fi introdus ca tuplu S=(S,Ψ): n S=(Y, E, g, y0, Ym) e automat generator, numit şi recunoscător –
recunoaşte un limbaj asupra aceleiaşi mulţimi de evenimente E n Ψ: E×Y→0,1 (sau, echivalent, Ψ: Y→2E) – este o funcţie de
control feed-back cu valori în şablonul de control sau mulţimea de validare a evenimentelor (1-validare, 0-invalidare)
Supervizorul urmăreşte/controlează comportarea SDED-G:
Supervizorul
Supervizorul urmăreşte/controlează comportarea SDED-G:n Îşi schimbă starea conform cu evenimentele generate de G n Aplică Ψ, pentru validarea/invalidarea evenimentelor controlabile
din subsetul ce generează tranziţii în starea corespunzătoare din GPrin această legare, funcţiile de tranziţie atât pentru G, cât şi pentru S, sunt modificateComportarea în buclă deschisă a SDED-generator G (dar închisă prin prefix), aşa cum a fost descrisă ea anterior, este dată de limbajul închis (prin prefix):
L(G)=s s∈E* & f(s,x0) definită
Pentru automatul generator notat S/G, se generează un limbaj L(S/G), caracterizat de faptul că generarea unui şir s din acest limbaj este permisă d.d. s∈L(G) şi s∈L(S), iar fiecare eveniment e∈S este validat de funcţia ΨComportarea marcată a automatului generator e dată prin Lm(S/G)– limbaj ce conţine acele şiruri din L(S/G) marcate atât în G cât şi în SSupervizorul este văzut în acest caz ca o funcţie S : L → Γ⊆2E ce
Comportarea în buclă închisă
Supervizorul este văzut în acest caz ca o funcţie S : L → Γ⊆2E ce specifică pentru fiecare şir de evenimente s∈L intrarea de control ce poate fi aplicată (Γ e notaţia pentru mulţimea intrărilor de control)Limbajul (închis prin prefix) generat de sistemul în buclă închisă, notat L(S/G), este definit de următoarele condiţii:a) ε∈L(S/G);b) şirul st ∈ L(S/G) d.d. s ∈ L(S/G), t ∈ S (s) şi st ∈ L(G).
Se spune că SDED generator G şi supervizorul S se execută în paralelastfel: un eveniment e∈E poate apare atunci când G×S este în starea (x,y) d.d. el este posibil atât în G în starea x, cât şi în S în starea y
Specificaţia globală a unei probleme de control pentru sisteme de calcul, reţele de calculatoare sau sisteme distribuite poate fi foarte generală Exemplu: “controlul tranziţiilor de stare ce pot asigura o funcţionare eficientă, non-blocantă şi rapidă a unei reţele”
Probleme de control globale în sistemele de calcul
funcţionare eficientă, non-blocantă şi rapidă a unei reţele” Rezolvarea problemei pentru această categorie de sisteme se poate face şi global, dar în general, din motive de reducere a complexităţii, ea se face local În sistemele distribuite, se implementează supervizorul ca sistem descentralizat şi localn el este compus dintr-o mulţime de subsisteme supervizor n fiecare dintre acestea observă şi controlează o parte a sistemului
global, prin accesul doar la o parte a evenimentelor controlabile
Se impun: n rafinarea specificaţiei în sub-specificaţii locale, după
descompunerea în subsisteme a sistemului distribuit dat (etapă care în general nu ridică probleme şi admite mai multe soluţii)identificarea subspecificaţiei unei probleme de control
Acţiuni specifice locale
n identificarea subspecificaţiei unei probleme de control este echivalentă de multe ori cu impunerea unor noi reguli locale de operare
n trasarea unei scheme de prioritate în cazul suprapunerii acţiunilor de control, datorată suprapunerii parţiale a subsistemelor controlate w acest lucru este necesar deoarece o soluţia descentralizată
indică doar acţiunile de control ce trebuie luate de fiecare supervizor local
Studiu de caz
Controlul supervizor al unei reţele Controlul supervizor al unei reţele de calculatoare conectate liniar
Descrierea problemeiFormularea unui protocol de control al unei reţele de cozi compusă din N servere aranjate liniar, fiecare având o coadă de intrare de capacitate limitată
S2S1 B1
...
Bn Sn+1
Sistem global(reţea de servere interconectate liniar)
Rafinarea specificaţieiUn mesaj ce intră în sistem este procesat de primul server, transmis apoi pentru a fi procesat în coada următorului server ş.a.m.d., până ce este procesat de toate serverele şi părăseşte sistemul Serverele se pot defecta (căderi de curent), nu înainte însă de a salva starea curentă, pentru a relua procesarea după reparare din exact acelaşi punct după reparare din exact acelaşi punct La intrarea şi ieşirea din reţea, înainte de S1 şi după Sn+1, se află buffere de capacitate pp. nelimitată (nu au influenţă asupra sistemului, de aceea nu au fost figurate)Fiecare server Si se poate afla în una dintre următoarele 3 stări: liber (Idle); ocupat (Working); defect (Defective)Bufferul Bi plasat înaintea serverului Si are tot trei stări posibile: buffer gol (0); buffer ocupat (1); buffer plin (2)
Diagramele de stare pentru Si şi Bi
Stările iniţiale sunt marcate în figura următoare printr-o săgeată incidentă; fiind considerate totodată stări marcate, săgeata e cu dublu sens
Serverul S Bufferul BI
WD
0
1 2
si ei
di
ri
Serverul Si
si+1
ei
ei
si+1
Bufferul Bi
Descrierea formală a sistemuluiConsiderând separat fiecare server şi fiecare buffer ca SDED generatoare de evenimente, comportarea (închisă) în buclă deschisă a fiecărui automat de acest fel poate fi descrisă folosind formalismul expresiilor regulate astfel:
L(Si) = (si(diri)*ei)*(ε+si(di+(diri)*))L(Si) = (si(diri)*ei)*(ε+si(di+(diri)*))L(Bi) = (ei(eisi+1)*si+1)*(ε+ei(ei+(eisi+1)*))
Limbajele marcate, Lm(Si)= (si(diri)*ei)* şi Lm(Bi)= (ei(eisi+1)*si+1)*, subliniate în expresiile anterioare, respectă totodată condiţiile:
Lm(Si) ⊆ L(Si) şi Lm(Bi) ⊆ L(Bi)
Problema localăDescompunem reţeaua în subreţele suprapuse parţial, formate din serverele Si şi Si+1 şi bufferul Bi dintre eleUrmărim determinarea subsistemelor supervizor CSi ce le controlează local Vom impune apoi pentru controlul global constrângeri:Vom impune apoi pentru controlul global constrângeri:n Ex: prioritatea supervizorului de index minim (CSi-1) în cazul
implementării de acţiuni locale conflictuale asupra aceluiaşi server Si
Fără a pierde generalitatea, rezolvăm problema pentru supervizorul CS1 – subsistemul format din serverele S1 şi S2 şi bufferul B1
Subsistemul local controlatAcţiunea supervizorului se poate exercita doar asupra evenimentelor controlabile, “început prelucrare la serverul Si (si)” sau “repararea serverului Si (ri)”, prin variabilele de control validare start (vsi), respectiv validare reparaţie (vri)
I
D
si/vsi
ei
di
ri/vri
Serverul Si
S2S1 B1
validare reparaţie (vri)
Reguli locale de operare1. Serverul S1 nu poate începe servirea dacă B1 plin – pt. a
evita ca evenimentul sfârşit prelucrare la serverul S1 să încerce scrierea într-un buffer plin (e1 necontrolabil)
2. Serverul S2 nu poate începe servirea dacă bufferul B1 gol3. Serverul S1 nu poate începe servirea dacă serverul S2
este defect (pericol de blocaj prin umplerea bufferului)3. Serverul S1 nu poate începe servirea dacă serverul S2
este defect (pericol de blocaj prin umplerea bufferului)4. Dacă S1 şi S2 defecte simultan, S1 trebuie reparat primul
(pentru a preveni blocajul)5. Serverele S1 şi S2 nu pot începe servirea dacă deja
lucrează6. Un server defect nu poate valida începutul servirii (se pp.
că serverele se pot defecta doar în timp ce lucrează), ci doar terminarea reparaţiei
Codificarea stărilor Pentru sistemul local controlat (S1-B1-S2) există 3x3x3(27) stări posibile
Regulile 1-6 permit înlăturarea a 6 stări, cele în care S1
este ocupat sau defect şi B1 plin
Proiectarea controlerului Trebuie făcută astfel încât doar tranziţiile de stare permise să aibă loc
Acţiunea se poate exercita doar asupra evenimentelor controlabile “început prelucrare la serverul Si (si)” şi “repararea serverului S (r )”, prin variabilele de control “repararea serverului Si (ri)”, prin variabilele de control validare start (vsi), respectiv validare reparaţie (vri)
Următoarea tabelă, a stărilor reduse ale controlerului , indică valorile variabilelor de control necesare în fiecare stare a sistemului controlat: 0 – invalidare, 1 – validare, X – valoare indiferentă
Reducerea stărilor controleruluiPutem considera pentru controler acelaşi număr de stări ca pentru sistemul controlat (0, 1, X), sau putem reduce numărul de stări- deci complexitatea controlerului, luând doar combinaţiile distincte pentru variabilele de control
1
2410
3
56
16
1218
e1
s1 e2
s2
e2
e
e2
e2
e1
d2
d1
d1
d1
r1
d2
d2
r2
r2
r2
r1
Diagrama stărilor sistemului local controlat (S1-B1-S2)
56
7
8
9
11 17
1913
14
15
21
20
e1
s1
e1
s2
e2
s1
e1
e1
e2
d1
r1
d1
r1
d1
r1
d2
r2
d1
d2d2 r2
r2
r1d2
r2
s2 s2
1 3e1
s2
2
d2
r2 r2
d2
d2
r2
e2
e2
s1,
s1,
e1
8Diagrama stărilor controlerului
5 7s2
d1d1 r1
r1
6
d1
r1
d2d2
r2
e2e2
4
Modelarea sistemelor de calculModelarea sistemelor de calcul
Modelare dinamică cu reţele Petri.
Curs, anul III Calculatoare
Modelare dinamică cu reţele Petri. Analiza RP
Caracteristici dinamice ale SED/ modelelor cu RPn Elemente constitutive (structurale) ale RPn Dinamica sistemelor cu RPTipuri simple de RP. Exemplen RP ordinare
Sumar
n RP ordinaren RP generalizate
Metode de analiză a RP ordinaren Analiza accesibilităţii
n Determinarea invarianţilor
Alte proprietăţi şi clasificări derivate
Caracteristici dinamice in sistemele cu evenimente discrete
SED sunt inerent dinamice si paralele, pot fi caracterizate prin 3 trăsături esenţiale de comportament,superpozabile:
n Concurenţa: posibilitatea ca mai multe evenimente să aibă loc de o manieră independentă unul faţă de altul
Sincronizarea: se referă la necesitatea ca execuţia n Sincronizarea: se referă la necesitatea ca execuţia anumitor evenimente să aştepte producerea altor evenimente
n Conflictele (interblocajele): o manieră de a ţine cont de competiţia între acţiuni multiple simultane sau de anumite fenomene, precum excluderea mutuală
Reţele Petri (RP)Reţele Petri (RP)Surprinderea unor astfel de trăsături necesită adoptarea unor modele care să înglobeze în cel mai înalt grad dinamica sistemelor modelate:
FSM, DTS (diagrame de tranziţie a stărilor)FSM, DTS (diagrame de tranziţie a stărilor)RPRP, , introduse in 1962 de introduse in 1962 de CC.. AA.. PetriPetrinn Profesor onorific al Universităţii din HamburgProfesor onorific al Universităţii din Hamburg
nn Membru al Academia EuropæMembru al Academia Europæ
nn In 2007 a fost onorat pentru întreaga In 2007 a fost onorat pentru întreaga activitate de către ATLAS ("Academy of activitate de către ATLAS ("Academy of Transdisciplinary Learning and Advanced Transdisciplinary Learning and Advanced Studies“) cu "Academy Gold Medal of Honor“Studies“) cu "Academy Gold Medal of Honor“
ReţeleReţelelele Petri Petri (cont.)(cont.)
Utilizează stări distribuite şi tranziţii localeAu permis iniţial modelarea unor sisteme cu componente concurente în interacţiune, fiind extinse ca instrumente matematice generale ulteriorModelarea dinamică necesita astfel de descrieri de tip Modelarea dinamică necesita astfel de descrieri de tip calitativ (logic) care să poată servi ca bază pentru analiza şi sinteza SDED Accentul este pus pe modelarea dependenţelor cauzale, fără sincronizare globală (doar transmitere de mesaje)Pe lângă anumite proprietăţi analitice, caracterul vizual al RP poate fi un element important în modelare
Elemente constitutive structurale(Logic)n Condiţii
Pot fi îndeplinite sau nu.n Evenimente
Pot avea loc daca anumite condiţii sunt îndeplinite.Relaţii (flux de control) n Relaţii (flux de control) Arata relaţiile intre condiţii si evenimente.
→Condiţiile, evenimentele si relaţiile formează un graf bipartit (graf cu doua tipuri de noduri)
(Grafic)n Locaţii (cercuri)n Tranziţii (dreptunghiuri)n Arce, ce conectează locaţiile cu tranziţii sau tranziţiile
cu locaţii
Concept dinamic cheie: Tranziţia stărilor
Logic, reprezintă apariţia unui eveniment/ o acţiuneGrafic, este mişcarea unor jetoane (token-uri), notate ca puncte negre, din locaţie în locaţie, prin “aprinderea” tranziţiilor Aceasta din urma depinde de condiţiile de intrare simbolizate de disponibilitatea jetoanelorsimbolizate de disponibilitatea jetoanelorSpunem ca o tranziţie este validata daca exista un număr suficient de jetoane in locaţiile sale de intrareO tranziţie validata se poate aprinde oricândDupă aprindere, token-urile vor fi transferate de la locaţiile de intrare (stare veche) către cele de ieşire, fiind astfel un element de identificare si in acelaşi timp o notaţie pentru noua stare
Arce si capacităţiArcele au implicit capacitatea 1; daca este diferita de 1, capacitatea este marcata pe arc Locaţiile au implicit capacitate infinitaO tranziţie este validata daca numărul de jetoane in fiecare din
Locaţie cu token
numărul de jetoane in fiecare din locaţiile sale de intrare este cel puţin egal cu capacitatea arcului ce o uneşte cu o locaţie de intrare
P1
P2
T1
Arc de capacitate 1
TranziţieLocaţie
Exemplul 1Automat de distribuţie (vânzare): n Distribuie două tipuri de batoane, de 20 de
bani si de 15 banin Doar două tipuri de monede pot fi folosite, de n Doar două tipuri de monede pot fi folosite, de
10 bani si de 5bn Nu returnează rest
Reprezentare prin diagrama tranzitiilorde stare, ca automat cu stări finite
5 bani 15 baniDepunere 10b
Ia baton de 15b
0 bani
10 bani 20 baniDepunere 10b
Ia baton de 20b
Reprezentare prin RP
5b
Ia baton de 15b
Depunere 5b
Depunere 10b15b
0b
Depunere 10b
Depunere5b
10b
Depunere5b
Depunere 10b20b
Depunere5b
Ia baton de 20b
Scenarii de evolutie
Scenariul 1: n Depunere 5b, depunere 5b, depunere 5b, depunere
5b, ia baton de 20b.Scenariul 2:n Depunere 10b, depunere 5b, ia baton de 15b.n Depunere 10b, depunere 5b, ia baton de 15b.
Scenariul 3:n Depunere 5b, depunere 10b, depunere 5b, ia baton
de 20b.
Dinamica sistemului
5b
Ia baton de 15b
Depunere 5b
Depunere 10b15b
0b
Depunere 10b
Depunere5b
10b
Depunere5b
Depunere 10b20b
Depunere5b
Ia baton de 20b
Tipuri de reţele PetriTipuri de reţele Petri (crit. structural)
RP ordinare, în care fiecare arc nu poate avea decât capacitatea (funcţia de ponderare) egala cu 1n Maşinile de stare (MS) – RP unde orice tranziţie are exact
o locaţie de intrare şi o locaţie de ieşire:n Grafurile marcate, GM) - orice locaţie are 1! tranziţie de
Tttt ∈∀== •• ,1||||n Grafurile marcate, GM) - orice locaţie are 1! tranziţie de
intrare şi 1! tranziţie de ieşire: n Reţelele cu alegere liberă (AL) – dacă 2 tranziţii au o
locaţie de intrare comuna, atunci au toate locaţiile de intrare comune: (sauechiv. dacă 2 locaţii au o tranziţie comuna de ieşire, vor avea toate tranziţiile de ieşire comune)
n Reţelele cu alegere liberă extinse (ALE) –acele RP ce pot fi transformate in RP AL
Pppp ∈∀== •• ,1||||
'',', ttttTtt •••• =⇒≠∩∈∀ φ
Tipuri Tipuri simple simple de reţele Petride reţele Petri (cont.)n Reţelele cu alegere asimetrică (AA) – RP în care, dacă două
locaţii au o tranziţie comuna de ieşire, atunci una din ele are toate tranziţiile de ieşire ale celeilalte (posibil altele in plus)
RP
PN
RP
AA ALE AL MS GM
RP generalizate, unde pot fi aplicate ponderi generale arcelor
Grafuri marcate
Nu poate exista conflict pe resurse, dar putem avea concurenţă(ramificare, sincronizare)
RP cu AL (“free-choice”)Foarte utilizate in modelarea conceptelor de flux (control)Realizeaza un compromis rezonabil intre puterea descriptiva siposibilitatea de analiza: “rezultatul alegerii intre 2 tranzitii nu poate fi influentat de restul sistemului (alegerile sunt libere)” In exemplul de mai jos, avem alegere libera pentru prima retea; In exemplul de mai jos, avem alegere libera pentru prima retea; pentru cea de-a doua, datorita sincronizarii la t2, tranzitia t3 poate influenta alegerea lui t1 sau t2
Reţele Petri “clasice”
Reţele condiţii/evenimente (C/E)Sunt cele folosite în introducerea RP:o subclasă de reţele Petri in care locaţiile pot avea 1/0 simboluri, ce pot modela atâtcondiţii cât și evenimente:
locaţiile reprezintă condiţii, ce pot avea inscrise valori true/ falsen locaţiile reprezintă condiţii, ce pot avea inscrise valori true/ falsen tranziţiile reprezintă evenimente locale
Un eveniment este validat d.d. n toate pre-condiţiile sale (conectate prin arce incidente) sunt true n toate post-condiţiile sale sunt false
Apariţia unui eveniment neagă pre- și post-condiţiile sale
Reţele C/E (cont.)Evenimentele cu aceleaşi pre- sau post-condiţii sunt in conflict Doar evenimentele non-conflictuale validate pot apărea concurentTerminologie:
Marcajul reţelei = distribuţia token-urilorn Marcajul reţelei = distribuţia token-urilorn Sistem C/E= reţea C/E + marcajn Configuraţii: marcaje posibile ale unei reţele C/En Cazuri ale unui sistem C/E: configuraţii accesibile din
marcajul iniţial (→ case graph)
Automatele sunt o subclasă secvenţiala a sistemelor C/Eexact o condiţie este adevărata,fiecare eveniment are o singura pre- si post-condiţie
Descrieri formaleGrafice (grafuri bipartite)/ matematice: au semanticăformală şi posibilităţi de analizăn Caracteristici importante: stări distribuite şi tranziţii locale
Sistemice: RP = <P, T, Pre, Post, M>P = l0, l1, …, lm setul poziţiilor (locaţiilor)P = l0, l1, …, lm setul poziţiilor (locaţiilor)T = t0, t1, …, tn setul tranziţiilorPre : T → L+, funcţia de intrare, ce defineşte locaţiile care
furnizează intrări unei tranziţiiPost : T → L+, funcţia de ieşire, defineşte locaţiile de ieşire
pentru fiecare tranziţieM : L → 0,1, funcţia de marcaj, defineşte numărul de
simboluri din fiecare locaţie
Condiţii şi resurseReţelele de tip C/E modelează fluxurile de informaţii, la nivel fundamental (true/false)
Aplicaţii: cele in care fluxul de resurse si/sau numarul de resurse disponibile este important (document workflow, data flow, linii de fabricaţie, reţele de comunicaţie, www)data flow, linii de fabricaţie, reţele de comunicaţie, www)
2
3
Reţelele de tip P/T reprezintă o generalizare (extensie) imediata:n Elementele de stare sunt echivalente locaţiilor
unde sunt stocate resurse (jetoanele)n Elementele de acţiune sunt reprezentate de
tranziţiile locale sau transportul resurselorn Poate fi aplicata o descriere matematică
similară cu cea a RP C/E
O reţea PT e o reprezentare de forma (P, T, A, C, w, M0), formată dintr-o parte structurală şi o parte dinamică.Partea structurală este un graf orientat bipartit unde:n P este o mulţime finită de poziţii (locaţii)n T este un set finit de tranziţii
A este o mulţime de arce, o submulţime a mulţimii (P×T)∪(T×P)
Reţele poziţii/tranziţii (P/T)
n A este o mulţime de arce, o submulţime a mulţimii (P×T)∪(T×P) n C: P → (N ∪ ∞) \0 este o funcţie de capacitate a poziţiilor
(capacitatea unei poziţii se consideră implicit nelimitată)n w este o funcţie de ponderare aplicată arcelor, w:A→1,2,3 ...
(ponderea unui arc se consideră implicit unitară)
Prin M0: P → N ∪ ∞ notăm funcţia numită marcaj iniţialPartea dinamică a reţelei PT constă în evidenţierea modalităţilor (legilor) de evoluţie a marcajului iniţial
Starea Starea şşi evoluţia reţelelor PTi evoluţia reţelelor PTStarea unei reţele PT date (definită structural) e complet descrisă de marcajul său M=[M(p1), M(p2),…,M(pn)]Spaţiul stărilor unei RPT marcate este complet definit de marcaje, adică de toţi vectorii n-dimensionali ale căror elemente sunt pozitive, M=0, 1, 2, …n
O tranziţie tj∈T într-o RPT marcată este validată dacă:O tranziţie tj∈T într-o RPT marcată este validată dacă:n M(pi) ≥ w(pi, tj), pentru orice pi∈I(tj);n M(pk) ≤ C(pi)-w(tj, pk), pentru orice pk∈O(tj)- I(tj);n M(p) ≤ C(p)-w(tj, p) + w(p, tj), pentru orice p∈O(tj) ∪ I(tj),
unde I(ti) este mulţimea locaţiilor de intrare în tranziţia tiiar O(ti) mulţimea locaţiilor de ieşire din tranziţia ti
Aprinderea unei tranziţii este echivalentă cu:n M’(pi) = M(pi) - w(pi, tj), pentru orice pi∈I(tj) - O(tj)n M’(pk) = M(pk) + w(tj, pk), pentru orice pk∈O(tj) - I(tj)n M(p) = M(p) - w(p, tj) + w(tj, p), pentru orice p∈O(tj)∩I(tj)
Exemplul 2
p1 t1 p2
2
2 2
În figura de sus, tranziţia nu este validată şi deci nu se poate produce În a doua variantă de marcaj tranziţia este validată În dreapta apare noul marcaj după producerea tranziţiei
p1 t1 p2
2
p1 t1 p2
2
Exemplul 3: Cazuri - configuraţia iniţială
p1
p2
p4 t2
M0 = [2, 0, 0, 1]
În configuraţia iniţială singura tranziţie validă este t1. Când tranziţia t1 se aprinde este eliminat un jeton din locaţia p1 şi se plasează câte un jeton în locaţiile p2 şi p3 (se poate aplica de asemenea formula pentru a se obţine noua stare)
p3 t1
t3
Exemplul 3: pasul 1
p1
p2
p4t2
M1 = [1, 1, 1, 1]
În această stare toate cele trei tranziţii sunt valideDacă se aprinde tranziţia t2, e eliminat un jeton din locaţiile de intrare p2 şi p3 şi plasat în locaţiile de ieşire p2 şi p4
p3t1
t3
Exemplul 3: pasul 2
p1
p2
p4 t2
M2= [1, 1, 0, 2]
S-a eliminat un jeton din locaţiile de intrare p2 şi p3 şi s-a plasat un jeton în locaţiile de ieşire p2 şi p4Dacă însă în starea precedentă s-ar aprinde tranziţia t3, atunci s-ar obţine starea descrisa pe următorul slide
p3 t1
t3
Exemplul 3: pasul 3
p1
p2
p4 t2
M2 = [0, 1, 0, 0]
În această stare nu mai este activată nici o tranziţie şi nu sunt posibile schimbări de stare
p3 t1
t3
Metode de analiză a RP ordinareAnaliza dinamică (analiza accesibilităţii) are ca scop determinarea mulţimii stărilor (accesibile)n Utilizează reguli algebrice ce descriu validarea şi aprinderea
tranziţiilor n Acestea conduc la reprezentarea evoluţiei dinamice a RP
prin formarea unor ecuaţii prin formarea unor ecuaţii Analiza structurală are ca idee de bază eliminarea derivării spaţiului stărilor şi prin aceasta evitarea problemei “exploziei stărilor”. n Această abordare nu poate furniza o informaţie la fel de
bogată ca priman De multe ori o asemenea detaliere nici nu este necesară, ci
sunt dorite doar anumite caracteristici calitative ale RP şi sistemului modelat (de ex. determinarea invarianţilor)
Ecuaţiile de accesibilitateDefinim al k-lea vector de evoluţie uk, un vector m-dim.de forma: uk = [0, 0, .., 0, 1, 0, …, 0], unde 1 apare în poziţia j si arata că tranziţia j este a k-a tranziţie aprinsăTrebuie definită şi matricea de incidenţă I ca matrice mxn, unde m este numărul de tranziţii, n numărul de locaţii, iar intrarea (i, j) este de forma: locaţii, iar intrarea (i, j) este de forma: n Iij = w(tj, pi) - w(pi, tj) → I = Post - Pre
Folosind matricea de incidenţă putem scrie o ecuaţie de stare vectorială Mk = Mk-1+ukI, valabilă pentru orice k∈N, si deduce o condiţie necesară de accesibilitate a unui marcaj:
, ce se poate scrie si ca:
unde:
IuMMd
k
kd )(
10 ∑
=
+= MxI ∆=
∑=
=d
k
kux1
Exemplul 3 (reluare)
p1
p2
p4 t2
Se vor folosi ecuaţiile anterioare pentru exemplul 3Marcajul iniţial este M = [2, 0, 0, 1]
p3 t1
t3
Exemplul 3 (cont.)Matricea de incidenţă pentru această reţea Petri este:
: Iij = w(tj, pi) - w(pi, tj)ePostttt
I
pppp
Pr1101
11000111
2
1
4321
−=
−−−−
−=
Dacă se aprinde tranziţia t1 după marcajul iniţial M0:
M1 = [2 0 0 1] + [1 0 0] = [2 0 0 1]+[-1 1 1 0]= [1 1 1 1]
t1101 3 −−−
−−−−
−
110111000111
Exemplul 3 (cont.)În cazul în care în continuare se aprinde tranziţia t2 vom obţine:
M2 = [1 1 1 1] + [0 1 0] = [1 1 1 1] +
−−−−
−
110111000111
+[0 0 -1 1] = [1 1 0 2]
Având marcajul iniţial M0 se pot genera toate secvenţele de marcaje accesibile → stări accesibileAcordând marcajelor semnificaţia de stare, se observă similaritatea cu o ecuaţie de stare din teoria sistemelor
−−− 1101
Exemplul 4: Calculul algebric (1)p1
p2p3
t2p4t3
p5
t6t1
p8
p5 p6 p7t4 t5
Exemplul 4 (2)p1
p2 p3
t6t1
p8
t2p4t3
7654321
001010100000010000001000100000000100000010000001
Pre
pppppppp
=
p5
p5 p6 p7t4 t5
654321
87
001010tttttt
p
654321
87654321
010100010000001000000001000100000010000001100000
Post
tttttt
pppppppp
=Matricea de incidenţă
−−−
−−
−−
−−
==
011110110000011000001001100100000110000011100001
Pre-PostI
Exemplul 4 (3)p1p2 p3
p5
t6t1 p8
t2p4
p5
p
p7
t3
t t
=
=000014
)()5()4()3()2()1(
pMpMpMpMpMpM
M
=′
000104
Mp6t4 t5
110
)8()7()6(
pMpMpM
p5 p7
p1p2 p3
p5
t6t1 p8
t2p4
p6
t3
t4 t5
010
t2 este validata si se declanseaza
),(),(Post),(Pre'
tIMttMM
⋅+=⋅+⋅−=
Determinarea (P-)invarianţilor
Un invariant este un vector pozitiv definit la dreapta* care anulează matricea de incidenţă
X ≥ 0: XI = 0
* Cu cel putin o componenta pozitiva si celelalte pozitive sau nule
XMi= XM0 + XI →
X ≥ 0: XI = 0
XMi = XM0
Alte proprietăţi şi clasificări derivate Autonomie. O reţea Petri se numeşte autonomă dacă nici timpul şi nici altă constrângere de sincronizare externă nu sunt implicate în modeln O RP autonomă se păstrează ca o descriere pur calitativă a
sistemului observatn Reţeaua din exemplul 3, anterior, este autonomăn Reţeaua din exemplul 3, anterior, este autonomă
Simplitate. O RP se numeşte simplă dacă elementele ei distincte (locaţii sau tranziţii) nu pot avea mulţimi de intrare sau ieşire similaren Reţeaua din exemplul anterior este simplă
Puritate. O RP se numeşte pură dacă nu conţine cicluri n Reţeaua din exemplul 3 nu e pură, deoarece există ciclul (p2,t2)
Accesibilitate. Se referă la posibilitatea de atingere a unei stări, codificate de un marcaj al reţelei, dintr-o altă stare
Alte proprietăţi şi clasificări (2)Mărginire (limitare). O RP se numeşte (n) mărginită dacă numărul de jetoane din fiecare locaţie poate atinge cel mult valoarea n n Reţeaua din exemplul anterior este mărginită
Siguranţă. O RP se numeşte sigură dacă marcajul fiecărei locaţii poate fi doar 0 sau 1 (marcaj boolean), iar arcele au pondere unitarălocaţii poate fi doar 0 sau 1 (marcaj boolean), iar arcele au pondere unitarăViabilitate. O RP se numeşte viabilă dacă, indiferent de marcajul iniţial şi de evoluţia sa, nici o tranziţie nu poate deveni inactivă de o manieră permanentă. n Reţeaua din exemplul anterior eşuează într-o stare terminală şi
deci nu este viabilăInvarianţi. O RP poate prezenta o serie de caracteristici invariante în timpul evoluţiei sale dinamice, în principal referitoare la marcajele sau stările sale
Alte proprietăţi şi clasificări (3)Conservativitate. O RP se numeşte conservativă dacă numărul total de jetoane este constant (un invariant al reţelei)n Reţeaua din exemplul anterior nu este conservativă
Sub-conservativitate. O RP se numeşte sub-conservativădacă numărul total de jetoane este constant sau în dacă numărul total de jetoane este constant sau în descreştere pe parcursul evoluţiei (dinamicii) salen Reţeaua din exemplul anterior nu este sub-conservativă
Reversibilitate. O RP se numeşte reversibilă dacă din fiecare marcaj accesibil se poate ajunge din nou la marcajul iniţialn Reţeaua din exemplul anterior nu este reversibilă
Ex. Este RP de mai jos simplă?Într-o RP simplă 2 tranzitii nu pot avea aceleași seturide locaţii de intrare si iesire
Obs: Reţelele simple fara elemente izolate ce indeplinesc sialte restrictii suplimentare legate de marcaje si capacitateaarcelor sunt reţelele condiţii/evenimente (C/E)
Modelarea sistemelor de calculModelarea sistemelor de calcul
Sinteza modelelor cu reţele Petri
Curs, anul III Calculatoare
Sinteza modelelor cu reţele Petriordinare şi generalizate
Exemple de sinteza a modelelor cu RPn Modelarea conceptelor dinamice în RP
ordinare
Extensii ale modelelor de baza cu RP:
Sumar
Extensii ale modelelor de baza cu RP: n RP temporizaten RP stochasticen RP de nivel inalt
Metode de analiză si sinteza (modelare) folosind RP ordinare si generalizate
Exemplul 5: Un sistem de asteptare(1 server, 1 coada)
No Activitate(Locatie)
Entitate implicata Server Activ
A1 Client.creare Client o
A2 Client.coada Client o
A3 Servire Client, Server þ
A4 Client.terminare Client o
A5 Client.iesire Client o
A6 Server.gol Server o
No Eveniment (Tranzitie) Preconditie PostconditieT1 Sosire A1 A2T2 Inceput servire A2, A6 A3T3 Sfarsit servire A3 A4, A6T4 Plecare A4 A5
Constructia retelei Petri (1)Incepe cu plasarea locatiilor (activitatilor) in succesiune logica
A6Server.gol
A1Client.creare
A2Client.coada
A3servire
A4Client.terminare
A5Client.iesire
Constructia retelei Petri (2)Se figureaza tranzitiile (evenimentele)
sosireT1
inceputT2
sfarsitT3
plecareT4
A1Client.creare
A2Client.coada
A3servire
A4Client.terminare
A5Client.iesire
A6Server.gol
Constructia retelei Petri (3)Arcele indica relatiile logice in RP
sosireT1
inceputT2
sfarsitT3
plecareT4
A1Client.creare
A2Client.coada
A3servire
A4Client.terminare
A5Client.iesire
A6Server.gol
Constructia retelei Petri (4)Token-urile marcheaza starea initiala a RP
sosireT1
inceputT2
sfarsitT3
plecareT4
A1Client.creare
A2Client.coada
A3servire
A4Client.terminare
A5Client.iesire
A6Server.gol
Dinamica sistemului (1)Creare clientClient Sosire Inceput Plecare
1 19,25Server : golCoada : 0
A1 A2 A3 A4 A5
A6
T1 T2 T3 T40
0 0
0
Dinamica sistemului (2)Sosire clientClient Sosire Inceput Plecare
1 19,252 26,50
Server : golCoada : 1
A1 A2 A3 A4 A5
A6
T1 T2 T3 T41
1 0
0
Dinamica sistemului (3)Servire
Client Sosire Inceput Plecare1 19,25 19,25 23,452 26,50
Server : ocupatCoada: 0
A1 A2 A3 A4 A5
A6
T1 T2 T3 T41
0 1
0
Dinamica sistemului (4)Terminare client (in sistem)
Client Sosire Inceput Plecare1 19,25 19,25 23,452 26,50
Server : golCoada: 0
A1 A2 A3 A4 A5
A6
T1 T2 T3 T41
0 0
0
Dinamica sistemului (5)Iesire client (din sistem)
Client Sosire Inceput Plecare1 19,25 19,25 23,452 26,50
Server : golCoada: 0
A1 A2 A3 A4 A5
A6
T1 T2 T3 T41
0 0
1
Dinamica sistemului (6)Sosire client
Client Sosire Inceput Plecare1 19,25 19,25 23,452 26,503 31,40
Server : golCoada: 1
3 31,40
A1 A2 A3 A4 A5
A6
T1 T2 T3 T42
1 0
1
Dinamica sistemului (7)Servir client
Client Sosire Inceput Plecare1 19,25 19,25 23,452 26,50 26,50 31,803 31,40
Server : ocupatCoada: 0
3 31,40
A1 A2 A3 A4 A5
A6
T1 T2 T3 T42
0 1
1
Dinamica sistemului (8)Sosire client
Client Sosire Inceput Plecare1 19,25 19,25 23,452 26,50 26,50 31,803 31,40
Server : ocupatCoada: 1
3 31,404 31,75
A1 A2 A3 A4 A5
A6
T1 T2 T3 T43
1 1
1
Dinamica sistemului (9)Sosire client
Client Sosire Inceput Plecare1 19,25 19,25 23,452 26,50 26,50 31,803 31,40
Server : ocupatCoada: 2
3 31,404 31,755 42,40
A1 A2 A3 A4 A5
A6
T1 T2 T3 T44
2 1
1
Dinamica sistemului (10)Terminare client
Client Sosire Inceput Plecare1 19,25 19,25 23,452 26,50 26,50 31,803 31,40 31,80
Server : golCoada: 2
3 31,40 31,804 31,755 42,40
A1 A2 A3 A4 A5
A6
T1 T2 T3 T44
2 0
1
Dinamica sistemului (11)Servire – Iesire client
Client Sosire Inceput Plecare1 19,25 19,25 23,452 26,50 26,50 31,803 31,40 31,80 44,75
Server : ocupatCoada: 1
3 31,40 31,80 44,754 31,755 42,40
A1 A2 A3 A4 A5
A6
T1 T2 T3 T44
1 1
2
Exersaţi singuri…
Modelarea conceptelor dinamice cu RPModelarea conceptelor dinamice cu RP
Modelarea conceptelor dinamice in RP (1)(C/E si PT)
A B
concurenţă
A B A B
concurenţă sincronizare comunicare
A B
conflict/alegere
A B
resurse/multiplicitate
A B
date/individualitate
Modelarea conceptelor dinamice in RP (2)
(a) secvenţiere; (b) ramificaţie; (c) sincronizare;(d) conflict la resurse; (e) concurenţă
Producător/consumator
Proces de transmitere/recepţie
Semaforrg
green
gy
yr
red
yellow
Doua semafoare
OR
rg
green
rg
green
rg
green
ORgy
yr
red
yellow
gy
yr
red
yellow
gy
yr
red
yellow
Implementarea nedeterminismuluiMai multe tranziţii sunt validate, dar numai una se poate declanşa
Soluţie
rg1
g1
rg2
g2
gy1
yr1
r1
y1
gy2
yr2
r2
y2
x
Trenuri (varianta 1)Consideram un sistem feroviar circular cu 4 linii (unidirecţionale), numerotate (1,2,3,4) si doua trenuri (A,B)n Nu putem avea doua trenuri pe aceeaşi linie in acelaşi
timp; identitatea trenurilor nu este importantatimp; identitatea trenurilor nu este importanta
Trenuri (varianta 2)Consideram un sistem feroviar circular cu 4 linii (unidirecţionale), numerotate (1,2,3,4) si doua trenuri (A,B)n Nu putem avea doua trenuri pe aceeaşi linie in acelaşi
timp; dorim sa distingem insa identitatea trenurilortimp; dorim sa distingem insa identitatea trenurilor
Trenuri (varianta 3)Consideram un sistem feroviar circular cu 4 linii (unidirecţionale), numerotate (1,2,3,4) si doua trenuri (A,B)n Nu putem avea doua trenuri pe aceeaşi linie in acelaşi
timp, dar nici pe linii vecine (condiţie de siguranţa); timp, dar nici pe linii vecine (condiţie de siguranţa); identitatea trenurilor nu este importanta
Trenuri (varianta 4)Consideram un sistem feroviar circular cu 4 linii (unidirecţionale), numerotate (1,2,3,4) si doua trenuri (A,B)n Liniile sunt marcate ca libere, ocupate sau cerute
Un tren va cere linia următoare înainte de a o ocupan Un tren va cere linia următoare înainte de a o ocupa
RP generalizateRP cu arce multiple (sau capacitate a arcelor > 2)n Numărul de arce intre o locaţie de intrare si o tranziţie
determina numărul de jetoane necesare in prima, pentru a o valida pe cea de-a doua
n Numărul de arce determina si numărul de jetoane ce se n Numărul de arce determina si numărul de jetoane ce se consuma/ se produc
wait enter before make_picture after leave gone
free
Exerciţii: Procese de fabricaţie (1)
Modelaţi ca RP procesul de fabricaţie a unui scaun din componente: n 4 picioare
3 bare de susţinere spătarn 3 bare de susţinere spătarn 1 cadru spătarn 1 suport şedere
Atenţie in selectarea ordinii de asamblare
Exerciţii: Procese de fabricaţie (2)Modelaţi procesul de producţie a unui automobil, indicat in diagrama următoare
car
subassembly2engine
subassembly1
subassembly2
wheelchassis
chair2
4
Echivalenţa definiţiilorOrice set de reţele Petri (diagrame) ilustrând un sistem dinamic poate fi transformat in model formal, si invers
Exerciţii:Transformaţi reţelele Petri obţinute anterior in modele formaleÎncercaţi analiza accesibilităţii și analiza dinamicăpe aceste modele
Extensii ale modelului de baza:RP temporizate
Timpul nu este prins in modelul RP de bazaModalităţile de extensie temporizata a lor au in vedere introducerea întârzierilor deterministe atât pentru locaţii, cat si pentru tranziţiiPot fi derivate concepte noi, de ex. timpul de ciclare (τ): pp. reţeaua consistenta, τ este timpul completării unei pp. reţeaua consistenta, τ este timpul completării unei secvenţe de declanşări ce reface marcajul initial:n Întârzieri pentru locatiiw τmin=maxyk
TD (A+) Tx/ykTM0
n Întârzieri pentru tranzitiiw τmin=maxyk
T(A-) TDx/ykTM0
n Rezulta pentru o RP temporizata simpla (GM)w τmin = maxtotal delay in Ck/M0 (Ck)
RP stochasticeAsemănătoare RP temporizate, diferenţa e in intarzierile introduse, care sunt nedeterministe n De ex., putem avea întârzieri de tranzitare modelate ca v.a.
distribuite exponenţialApar proprietăţi noi: n graful de accesibilitate al unei RP stochastice mărginite este n graful de accesibilitate al unei RP stochastice mărginite este
izomorf cu un lanţ Markov finitn O RP stochastica reversibila generează un lanţ Markov ergodic, in
care distribuţiile de probabilitate in starea stabila dau estimatorii de performanta:w Probabilitatea unei condiţii particularew Valoarea aşteptata a numărului de simboluri (jetoane)w Numărul mediu de declanşări in unitatea de timp
RP stochastice generalizate adaugă tranziţii imediate pentru a reduce spaţiul stărilor
RP de nivel inaltIncludem in aceasta categorie:n RP cu predicate/tranziţiin RP coloraten RP cu simboluri individualizate
Orice RPNI poate fi translatată intr-o reţea ordinara:Orice RPNI poate fi translatată intr-o reţea ordinara:n Fiecare locaţie se translatează intr-un set de locaţii,
de ex. cate una pentru fiecare culoare a jetoanelor conţinute
n Fiecare tranziţie se translatează intr-un set de tranziţii, cate una pentru fiecare modalitate de declanşare
RPNI: exemple
a,ad,d
<a,b>
<x,z>2xa
d
<a,c>
<d,b>
2
2
<a,b><b,c><d,a>
e<x,y>+<y,z> <a,b>
<b,c>
<d,a>
e
Aplicabilitatea RPNIProgramare logican Modelarea seturilor de clauze (Horn)
B ← A1, A2, ..., Anunde Ai si B sunt formule “atomice”
Predicat(argumente)Predicat(argumente)n Instructiunea scop (goal statement) se modeleaza ca
tranzitie fara iesiri (sink transition) n Asertiunile de fapte – ca tranzitii sursan Reprezentarea ca RPNIw Fiecare simbol predicat distinct este o locatiew Fiecare clauza este o tranzitie w Ponderile sunt argumente
n La final, trebuie sa existe conditii suficiente pentru a declansa tranzitia scop
Invarianti numerici
In toate cazurile
A“#A < n”
n
A“|A| - #A < n”n
A B “(|A| - #A < n) n m
• pot fi aplicat metode logice pentru retele P/T, folosindinegalitati asupra numarului de resurse ca propozitii elementare
• tehnicile numerice specifice pot fi insa mai eficiente
Evenimente moarte (nevalidabile) Invarianti sistem (fapte)
“(|A| - #A < n) and (|B| - #B < n)”
A
B “(#A < n)or (|B| - #B < n)”
n
m
Invarianţi, tehnici numerice
+−
=altfel,0
la la de arce exista daca, la la de arce exista daca,
:, ptnntpnn
C tp
pnnm p locatiain jetoane exista daca ,:=
• Matricea de incidenta C a unei retele P/T pure (fara cicluri):
•Vectorul marcajelor m al unei retele P/T: t
pn
Contributialui t la ppnnm p locatiain jetoane exista daca ,:=
ori de adeclanseaz se tranzitiadaca ,: ntnf t =•Vectorul de aprindere f al unui multi-set de tranzitii (fara reprezentarea ordinii!):
•Vectorul pondere i al unor locatii: set de locatii cu suma jetoanelor constanta
''**)'(:', mimimimimmmm tp
ppp
pp
t ⋅===⋅⇒∀ ∑∑a
• Conditia necesara, nu si suficienta de accesibilitate:
00)'(' =⋅⇒=−⋅⇔⋅=⋅ Cimmimimi tttt
lui t la p
'mfCm t =⋅+
Propoziţii si predicate
17 x+y=z
P
a Scheme cu conditiibPa Pb
1 7
Retele predicate/tranzitii:• jetoanele individuale sunt extensii de predicate si inlocuiesc conditii propozitionale• cuantificatori si specificatori intr-o logica a predicatelor permit grupari de evenimente la nivel propozitional in scheme cu evenimente la nivel de predicate
P
Q
R
7
2
x
y
z
x+y=z
Scheme cu evenimente
P
QR
7
2
1
2
27
3
9
Concluzii
Modelarea cu reţele Petri ord./ NI se poate utiliza pentru a testa şi valida anumite proprietăţi utile ale sistemelorn Siguranţa: este garantată prin faptul că numărul de
simboluri nu creşte nedefinitsimboluri nu creşte nedefinitn Funcţionalitatea: este garantată prin lipsa blocajelor → va exista întotdeauna cel puţin o tranziţie care poate fi declanşată
Avantaj: modelarea sistemelor concurenteDezavantaj: nu este utilă pentru sisteme complexe
Modelarea sistemelor de calculModelarea sistemelor de calcul
Lanţuri şi procese Markov
Curs, anul III Calculatoare
Lanţuri şi procese Markov şi semi-Markov generalizate
Terminologie şi concepte de bază. Nivele de modelare (rev.)Categorii de modele statisticeSecvenţe şi procese aleatoareLanţuri Markov. Problema ergodicităţii
Sumar
Lanţuri Markov. Problema ergodicităţiiProcese MarkovLanţuri Markov înglobateProcese semi-Markov generalizate (GSMP)Definirea GSMPGenerarea GSMP
Terminologie şi concepte de bazăSistem - o colecţie de entităţi in interacţiune
Model - o reprezentare abstractă a sistemului
Entitate - componentă a sistemului cu reprezentare explicităin model (obiect de interes in sistem)
Atribut - o proprietate a unei entităţi Atribut - o proprietate a unei entităţi
Set - colecţie de entităţi asociate, permanent sau temporar
Eveniment - o apariţie instantanee ce schimbă starea sistemului
Activitate - o perioada de timp de lungime cunoscuta la începutul ei
Întârziere - o perioada de timp nespecificată ca lungime →necunoscută până la terminarea ei
Nivele de studiu/ modelare (1)Comportarea SDED este in mod natural descrisa deînregistrarea (urma) generată de apariţia unorschimbări discrete, calitative, in sistemModelele bazate pe urme sunt studiate la diferitenivele:nivele:
Nivelul logic – “urma” este secvenţa de evenimente, inordinea apariţiei lor
s = e1 e2 e3 ... Exemple: reţelele Petri (“cazuri” = urme); maşinile cu stări finite (Wonham); procesele recursive finite (Inan-Varaiya); procesele secvenţiale comunicante (Hoare)
Nivele de studiu/ modelare (2)Nivelul temporal - urma este secvenţa de perechi
s = (e1,t1) (e2,t2) (e3,t3) ... Exemple: reţelele Petri temporizate, modelele algebrice min-max, grafurile data-flow
Nivelul statistic - comportarea sistemului este descrisă deNivelul statistic - comportarea sistemului este descrisă desecvenţa perechilor de v.a.
s = (e1,t1) (e2,t2) (e3,t3) ...(unde ei si ti sunt v.a. si pentru orice realizare ω, s(ω) =(e1(ω),t1(ω)) (e2(ω),t2(ω)) (e3(ω),t3(ω)) ... este o urmadescrisa la nivel temporal)
Exemple: lanţurile Markov, sistemele cu cozi de aşteptaresi reţelele de cozi, modelele de simulare - având la bazaformalismul GSMP
Categorii de modele statistice (1)I. Modele analitice (teoretice)
n sistemice (improprii), provenite in general din modele deterministe – unde descrierea se face la nivel logic sau temporaloperaţionale, in general probabilistice (statistice); n operaţionale, in general probabilistice (statistice); se pot folosi in cazurile când putem obţine prin calcul formule/ rezultate exacte (având modalităţi de a simplifica problemele computaţionale)w Ex.: sisteme cu cozi de aşteptare, reţele de coziw Limitare: la cozi simple &
reţele de cozi factorizabile
Categorii de modele statistice (2)II. Modele de simulare
n derivate din modelele operaţionalen adecvate pentru analiza asistata de calculatorn oferă un instrument complet ce aproximează
dinamica sistemului prin oferirea de ipostaze non-dinamica sistemului prin oferirea de ipostaze non-continue incrementale
n Pro: Dinamica originala a SDED este de acest tip!n Contra: Dificultăţi computaţionale (exista soluţii!)
Pentru modelarea SDED la nivel statistic (cea mai completa) se pot folosi in tandem: n modele operaţionale + modele de simulare
Lanțuri MarkovSunt procese aleatoare discrete (asociate cu sisteme ce se pot afla în stări diferite, ce se schimbă aleator în pași discreți), cu a.n. “proprietate Markov”Poate fi util să gândim aceste sisteme ca evoluând în pași discreți în timp, deși timpul nu este determinantpași discreți în timp, deși timpul nu este determinantProprietatea Markov: distribuția de probabilitate de trecere a sistemului în starea următoare (și de fapt în toate stările următoare) depinde doar de starea curentă, nu și de stările anterioareConsecință: deși stările următoare sunt aleatoare, nu pot fi prezise, pot fi descrise proprietățile statistice ale sistemului cu mulți pași înainte
Un exempluUn iepure mănâncă doar varză, morcovi sau lăptuci Dacă a mâncat morcovi ieri, nu va mai mânca azi, ci va servi doar varză sau lăptuci cu probabilitate egalăDacă a mâncat varză ieri, va putea mânca azi, cu prob. 10%, dar și morcovi sau lăptuci cu prob. 40%, prob. 10%, dar și morcovi sau lăptuci cu prob. 40%, respectiv 50%Dacă a mâncat lăptuci ieri, nu va mai mânca azi, ci va servi doar varză sau morcovi cu prob. 40%/ 60%Modelul obiceiurilor alimentare ale iepurelui este un lanț Markov, și se pot calcula proprietăți statistice ca de ex. numărul (%) de zile în care iepurele a mâncat morcovi, pe o perioadă lungă de timp → 100 zile
Câmp de evenimente elementare. Variabilă aleatoare(Ω, E, P): câmp (finit sau infinit) de evenimente elementare
n Ω: mulţimea de realizări posibile ale unui experiment aleator (mulţime de evenimente elementare)
n E: mulţimea submulţimilor din Ω (spaţiul evenimentelor)n P: măsura de probabilitate
X:Ω→R este variabilă aleatoare dacă valoarea sa depinde de o realizareX:Ω→R este variabilă aleatoare dacă valoarea sa depinde de o realizaredin Ω si este caracterizata de:Ø desfacerea lui Ω in evenimente elementare, incompatibile:
E1,E2,...,En Ø mulţimea valorilor reale x1,x2, ...,xnØ mulţimea probabilităţilor asociate evenimentelor elementare
p1,p2,...,pn
n O v.a. modelează translatarea mulţimii rezultatelor unui experiment aleator pe o mulţime reală
Secvenţe şi procese aleatoareSecvenţă aleatoare (stochastică):
Un şir de v.a. X1, X2,..., Xn,... indexate printr-o variabilăindependentă (de obicei cu semnificaţie de timp)
Definirea se face prin specificarea funcţiei de distribuţie (deobicei aceeaşi) a componentelor, v.a. X1, X2,..., Xn,...
Proces aleator (stochastic)Definite ca limita unei secvenţe aleatoare când variabila deindexare devine continua; notaţie X(t)
Ne interesează procesele aleatoare a căror comportare este integral caracterizată printr-o unică distribuţien V.a. ale lor sunt i.i.d. (independente şi identic distribuite)
n Ele sunt intuitiv descrise de secvenţe de extrageri aleatoare dintr-o mulţime de bază ce respectă o distribuţie fixă
Probabilităţi condiţionate în secvenţele aleatoare
Fie (Ω, E, P) un câmp finit de evenimente elementare, iar X1, X2,..., Xn,... un şir de v.a. Notăm E1
n, E2n,..., Em
n,... desfacerea corespunzătoarev.a. Xn în evenimente elementare, incompatibileProbabilitatea condiţionată P(Ejnn)|Ej11∩…∩Ejn-1
n-1 este în general dependentă de succesiunea de evenimente, Probabilitatea condiţionată P(Ejn )|Ej1 ∩…∩Ejn-1 este în general dependentă de succesiunea de evenimente, Ej11,…,Ejn-1
n-1,Ejnn
Dacă P(Ejnn)|Ej11∩…∩Ejn-1n-1 = P(Ejnn) pentru ∀n ∈Ν şi
∀şir Ej11,…,Ejnn, atunci acest şir este o simplă succesiune de v.a. independenteDacă P(Ejnn)|Ej11∩…∩Ejn-1
n-1 = P(Ejnn)|Ejn-1n-1 pentru ∀n
∈Ν şi ∀şir Ej11,…,Ejnn, atunci acest şir constituie un lanţ Markov simplu
Lanţuri şi procese MarkovO clasă de modele destul de generale (se aplică cu succes şi în modelarea altor tipuri de sisteme)Procesele Markov se caracterizează prin aceea că:n starea la un moment dat t este suficientă pentru starea la un moment dat t este suficientă pentru
calculul stării la momentele următoare n nu este necesară cunoaşterea stărilor unui sistem
(continuu) la momentele anterioare
Lanţurile Markov păstrează această proprietate, sistemul modelat fiind însă studiat doar la momente discrete de timp
Lanţuri MarkovDefiniţie. Dacă procesul stochastic X descris de secvenţa X=Xnn=0,1,2,... are proprietatea P(Xn+1=j| X0,X1, X2,..., Xn) = P(Xn+1=j| Xn), atunci el se numeşte lanţ MarkovInterpretare: Probabilitatea apariţiei unui eveniment la momentul n+1 depinde doar de starea curentă (n), nu şi momentul n+1 depinde doar de starea curentă (n), nu şi de stările sistemului la momentele anterioareLanţurile Markov multiple de ordinul p se definesc prin dependenţa probabilităţii apariţiei unui eveniment la momentul n+1 de cele p stări ale sistemului la momentele anterioare, generate prin apariţiile altor evenimente la cele p momente anterioare
Modelul Markov simpluNotaţii:n (Ω, E, P) – câmp de evenimente elementaren X=Xnn=0,1,2,... – secvenţă stochastică (şir de v.a. independente)n Ψ – spaţiul stărilor posibile ale procesului, de cardinal numărabil
(simplificat, Ψ e asimilat cu Ν, adică Xn=j arată că procesul descris de variabila aleatoare X este în starea j la momentul n)descris de variabila aleatoare Xn este în starea j la momentul n)
n P(i,j)=P(Xn+1=j|Xn=i) - probabilitatea de tranziţie din starea i în j n P=[P(i,j)]i,j∈Ψ - matricea de tranziţie;n π(i) - probabilitatea stării i∈Ψ
Modelul este caracterizat de 2 tipuri de ecuaţii:
enormalizar de ecuatia - 1=(i)
balans de ecuatiile - ij),P(i,(j)=(i)
i
j
π
ππ
∑
∑
Ψ∈
Ψ∈
Ψ∈⋅
Tipologie şi proprietăţi (1)Dacă la momentul n probabilitatea stării i nu depinde decât de starea considerată, nu şi de variabila aleatoare Xn prin care se concretizează, adică P(Xn=i)=π(i) pentru orice n, lanţul Markov se numeşte staţionar
O mulţime de stări din Ψ se numeşte închisă dacă nici o O mulţime de stări din Ψ se numeşte închisă dacă nici o stare din afara acestei mulţimi nu poate fi atinsă dintr-o stare aflată în mulţime
O mulţime închisă de stări se numeşte nedecompozabilădacă nici o submulţime proprie a sa (strict inclusă în ea) nu este închisă
Tipologie şi proprietăţi (2)Un lanţ Markov este nedecompozabil dacă singura mulţime nedecompozabilă este însuşi spaţiul stărilor, Ψ
n În cazul unui lanţ Markov nedecompozabil, un proces aflat într-o stare i poate trece cu o probabilitate nenulă în orice stare jîn orice stare j
O stare i∈Ψ se numeşte periodică dacă este parcursă periodic de procesul stochastic X; cu alte cuvinte, dacă Xk=i, atunci Xl=i doar dacă l=k+m⋅d, unde d∈Ν este un divizor comun al lui k şi l (numit perioadă), iar m∈Ζ
Dacă nici o stare nu este periodică, lanţul Markov se numeşte aperiodic
Ergodicitatea lanţurilor MarkovÎntr-o accepţiune generală, X=Xnn=0,1,2,... este un lanţ Markov ergodic dacă pentru orice funcţie f:Ψ→R avem:
(i)f(i)=E[f(X)]unde E[f(X)],=a.s.)Xf(
n1
ik
1-n
0=knπ⋅∑∑
Ψ∈∞→lim
f(X). luia stare pe media este i0=kn Ψ∈∞→
Putem considera mai general, ca probabilităţi de trecere de la starea i la momentul l la starea j la momentul m: P(l,m)(i,j), iar prin fixarea momentelor l,m dar menţinerea ca variabile a stărilor i,j formăm matricele de trecere:
P(l,m)=[P(l,m)(i,j)]i,j∈Ψ
Relaţia lui ChapmanMatricele de trecere definite anterior respectă o relaţiederivată direct din definiţia lanţului Markov simplu:
P(l,n)=P(l,m) x P(m,n), unde l<m<n (m stare intermediară)n Pentru determinarea matricelor de trecere este deci necesar şi
suficient să cunoaştem matricele de tranziţie definite anterior: suficient să cunoaştem matricele de tranziţie definite anterior:
P=[P(i,j)]i,j∈Ψ=P(n,n+1)
Un lanţ Markov omogen este caracterizat de faptul că probabilităţile de trecere depind numai de diferenţa n=m-l, între momentele l şi mÎn acest caz relaţia lui Chapman se poate scrie simplu:
P(m+n)=P(m) × P(n)
iar lanţul este determinat doar de matricea de tranziţie P=P(1); evident că P(n)=Pn
Este problema comportării probabilităţilor P(n)(i,j) pentru n→∞, convergenţa către o limită:
Rezultate importante: 1. Dacă limita probabilităţilor de trecere (sau a matricelor
Problema ergodică pentru sisteme nedecompozabile
P=P(n)sauj)P(i,=j)(i,P(n) ji, nnlimlim ,|
∞→∞→Ψ∈
1. Dacă limita probabilităţilor de trecere (sau a matricelor de trecere) există, acest lucru este independent de starea iniţială din care se pleacă n Intuitiv, se poate porni aşa la definirea ergodicităţii
2.Dacă X=Xnn=0,1,2,... este un lanţ Markov ergodic, noullanţ Markov Y=Ynn=0,1,2,... definit prin Yk=Φ(Xk, Xk+1,...), unde Φ:R∞→R e o funcţie măsurabilă, este ergodic3.Dacă un lanţ Markov nedecompozabil este aperiodic şi are un număr finit de stări distincte, el este ergodic
ObservaţiiNoţiunea de proces aleator, sub forma particulară sub care a fost introdusă anterior, constituie o generalizare directă a noţiunii de variabilă aleatoare Un proces aleator este în esenţă o funcţie parametrizată definită pe produsul dintre spaţiul unui parametru t (de obicei o submulţime reală) şi câmpul de probabilitate, cu valori reale; prin fixarea parametrului t, funcţia se reduce valori reale; prin fixarea parametrului t, funcţia se reduce la o variabilă aleatoare în sensul definit anteriorRepartiţiile variabilelor aleatoare obţinute pentru diferite valori ale parametrului t pot fi în general identice sau diferite, în ansamblu ele constituie repartiţiile de probabilitate finit dimensionale ale procesului aleatorÎn cazul lanţurilor Markov am considerat ca spaţiu al parametrului t mulţimea numerelor întregi nenegativeDefiniţia proceselor Markov are în vedere întreaga semidreaptă reală pozitivă
Procese MarkovDefiniţie. Un proces aleator Y=Yt, t∈[0,∞) se numeşte proces Markov, cu un spaţiu numărabil de stări Ψ, dacă
∀s>0 şi j∈Ψ: P(Yt+s=j Yu, u ≤s)=P(Yt+s=j Ys)Prin analogie cu un lanţ Markov, un proces Markov se numeşte omogen dacă P(Yt+s=j|Ys) nu depinde de s
Funcţia de tranziţie pentru un proces Markov se defineşte analog: P(t)(i,j) = P(Yt+s=j|Ys=i); proprietăţi:
n P(t)(i,j) ≥ 0, ∑k∈Ψ P(t)(i,k) = 1, i∈Ψ
n Ec. Chapman-Kolmogorov: ∑k∈Ψ P(t)(i,k) ⋅P(s)(k,j) = P(t+s)(i,j), sau în formă matriceală: P(t+s) = P(t)xP(s)
Lanţ Markov înglobat unui procesDacă:
1) W(t) e intervalul de rămânere a unui proces Markov într-o stare Y(t), măsurat în spaţiul parametrului t: W(t) = infs>0: Y(t+s)≠Y(t), atunci: (W(t>u)| Y(t)=i = e-λ(i)u, unde u>0, iar λ(i) e rata de tranziţie a stării i2) T(n), n=0,1,2,..., este timpul celei de-a n-a tranziţii a procesului, X(n)=Y(T(n)) starea imediat următoare tranziţiei la T(n), notând X(n)=i: X(n)=Y(T(n)) starea imediat următoare tranziţiei la T(n), notând X(n)=i: P(X(n+1)=j,T(n+1)-T(n)>u |X(0),...,X(n); T(0),...T(n) =Q(i,j)⋅e-λ(i)u
3) Q(i,j) – probabilitatea de tranziţie din starea i în starea j, satisface condiţiile: Q(i,j)≥0, Q(i,i)=0 - prin convenţie, şi ∑k∈Ψ Q(i,k) = 1,
atunci:
Procesul stochastic X=X(n), n=0,1,2,... este un lanţ Markov definit de probabilităţile de tranziţie Q(i,j), numit lanţul Markov înglobat procesului Markov Y
ObservaţiiProprietatea evidenţiată anterior pt. lanţurile şi procesele Markov de a fi “lipsite de memorie” (nu impun memorarea evoluţiei trecute), implică două constrângeri importante:(M1) toată informaţia de stare trecută este irelevantă;(M2) timpul petrecut în starea curentă este irelevant
Prima constrângere este definitorie pentru studiul tuturor Prima constrângere este definitorie pentru studiul tuturor aspectelor markoviene şi păstrează destul de largă clasa acestor sisteme A doua restricţionează de fapt natura v.a. ce specifică intervalul de timp între două tranziţii de stare consecutive şi are drept consecinţă importantă faptul că, într-un lanţ Markov, timpii între evenimentele ce determină tranziţiile de stare sunt distribuiţi după o lege exponenţialăn Prin aceasta se determină o anumită restrângere a tipurilor de
sisteme reale ce pot fi încadrate aici
Formalismul GSMPUn lanţ Markov poate fi înglobat şi unui proces stochastic ce nu este proces Markov n De ex., un lanţ Markov înglobat unui proces pentru
care probabilităţile de tranziţie între stări au legea de distribuţie de tip Markov sau exponenţial, în timp ce distribuţie de tip Markov sau exponenţial, în timp ce duratele de timp între tranziţii sunt arbitrar distribuite, se numeşte proces semi-Markov
Analog, se defineşte şi un proces semi-Markov generalizat (GSMP), în cazul unei dependenţe mai generale de comportarea trecutăFormalismul GSMP stă la baza modelelor de simulare, din categoria modelelor statistice
ObservaţiiUn proces semi-Markov este o extensie a unui proces Markov, determinată de relaxarea constrângerii (M2)Timpii între tranziţiile de stare nemaifiind cu necesitate distribuiţi exponenţial, rezultă că un eveniment ce determină o tranziţie de stare poate apărea în orice determină o tranziţie de stare poate apărea în orice moment, impus de orice lege distribuţională Se păstrează însă constrângerea (M1), cea definitorie: când un asemenea eveniment apare, probabilitatea de atingere a noii stări nu depinde de stările trecute, ci doar de starea curentăProcesele semi-Markov pot fi definite direct ca procese aleatoare în câmp borelian de evenimente, sau generate prin evoluţia unui automat de stare temporal stochastic
Care procese aleatoare pot fi GSMP? Considerăm în câmpul de probabilitate (Ω, E, P) procese stochastice continue în timp:
x(ω,t) : (Ω, E, P) × T+ → X, unde X este o mulţime numărabilă (spaţiul stărilor) Pentru fiecare stare x∈X există o mulţime unică Γ(x)⊂N, numită lista de evenimente (active) asociate stării numită lista de evenimente (active) asociate stării Fiecare eveniment are un timp de apariţie asociat; fie Γ=∪x∈XΓ(x) mulţimea tuturor evenimentelor Un astfel de proces constituie un GSMP; traiectoria sa constă din segmente constante pe porţiuni (secvenţe de stare) şi salturi între 2 stări la momente asociate evenim.Lungimea unei secvenţe de stare se mai numeşte şi timp de menţinere a stăriiSecvenţa evenimentelor declanşate se numeşte urmă
GSMP: bază a modelelor de execuţie
Toate evenimentele asociate unei stări sunt competitive (şi pot fi planificate) pentru tranzitarea către starea următoareFiecare eveniment are asociată şi propria sa distribuţie de salt pentru determinarea stării următoare de salt pentru determinarea stării următoare La fiecare tranziţie a sistemului, noi evenimente sunt planificate (activate), şi le sunt asociate durate de viaţă generate conform unor distribuţii de probabilitate Vechile evenimente nedeclanşate pot fi păstrate în noua stare cu timpii asociaţi (GSMP neintreruptibil) sau pot fi abandonate în noua stare (GSMP intreruptibil)
GSMP: procese aleatoare şi structuri temporale stochastice
Formal, fiind date în câmpul de probabilitate (Ω, E, P) mulţimile distribuţiilor Φe, e∈Γ şi probabilităţilor de tranziţie P(x, x’,e), ansamblul (X(ω,t), C(ω,t)) format din procesul aleator X şi structura temporală stochastică C se defineşte astfel: C se defineşte astfel:
n pe de o parte, prin specificarea modului de generare a componentelor structurii temporale, pe baza distribuţiilor Φ
n pe de altă parte prin specificarea legilor de evoluţie dinamică (aleatoare, având în vedere probabilităţile de tranziţie a stărilor P) ale procesului X
GSMP: automate de stare stochasticeşi structuri temporale stochastice
Pentru generarea GSMP se poate utiliza un automat de stare stochastic (ale cărui stări tranzitează probabilistic), cu o structură temporală stochastică asociată
Definiţie. Numim automat de stare stochastic structura (X, E, Γ, p, p0, C), caracterizată de:(X, E, Γ, p, p0, C), caracterizată de:n X – mulţimea stărilor (cel mult numărabilă)n E – mulţimea evenimentelor (numărabilă)n Γ(x) – mulţimea evenimentelor active în starea x (Γ(x)⊆E)n P : X×X×E → [0,1] - funcţia de probabilitate a tranziţiilor
de staren p0(x) – setul de probabilităţi asociate stării iniţiale x0,
p0(x)= p(x0=x);n C=Ce, e∈E - structură temporală stochastică, fiecare
componentă a sa fiind o v.a. distribuită după o anumită lege Φe
ObservaţiiUn automat de stare stochastic se obţine prin extensia multiplă a unui automat de stare temporaln structura temporală nu se mai consideră dată ci se
generează pornind de la distribuţiile Φe date n funcţiile de tranziţie a stărilor, ca şi starea iniţială, nu
mai sunt date univoc, ci probabilisticmai sunt date univoc, ci probabilisticUn automat de stare stochastic generează o secvenţă de stare stochastică x1,x2,...,xk,xk+1,... printr-un mecanism de tranziţie bazat pe probabilităţile tranziţiilor de stare P condus de secvenţa de evenimente e1,e2,...,ek,ek+1,... n dacă xk=x, atunci xk+1=x’ cu probabilitatea p(x,x’,e’),
e’ fiind evenimentul ce declanşează tranziţia, adică intrarea în starea x’
Generarea GSMPMecanismul de alegere al evenimentului declanşator e’ este identic cu cel pentru automatul de stare temporal
re fiind timpii reziduali rezultaţi din structura temporală stochastică C=Ce, e∈E. Calculul noilor timpi reziduali se poate face dacă: rr min*=
;minarg')(
exe
reΓ∈
=
Calculul noilor timpi reziduali se poate face dacă: şi are în vedere doar cazul neintreruptibilităţii evenimentelor nedeclanşate:
Prin next(ce’) s-a notat generarea unei noi durate de activare pentru evenimentul declanşat, pe baza distribuţiei indicate Φe’Secvenţa stărilor generate de un automat de stare stochastic este un proces aleator, care îndeplineşte constrângerea M1 şidefineşte un GSMP
exerr
)(min*
Γ∈=
'.*,);( '' eerrrcnextr eeee ≠−==
Modelarea sistemelor de calculModelarea sistemelor de calcul
Sisteme cu cozi de aşteptare şi
Curs, anul III Calculatoare
Sisteme cu cozi de aşteptare şi reţele de cozi
Modelarea analitică a sistemelor şi reţelelor de aşteptare. Notaţia Kendall generalizatăNotaţia Kendall simplificatăLegea lui Little
Sumar
Legea lui LittleComportare tranzitorie şi permanentă (staţionară,de echilibru statistic)Probabilităţi de tranziţie şi de stareMăsuri de performanţă la echilibru statistic
Sisteme cu cozi de aşteptareCaracterizează un sistem prin:
fluxul de intrare - descrie modul in care sosesc clienţii (unităţile) in sistem n in general sosirile sunt aleatoare si independente;
coada (cozile) de aşteptare, caracterizata(e) printr-o coada (cozile) de aşteptare, caracterizata(e) printr-o anumita disciplina (o regula), care precizează:n modul de formare a cozii n modul de comportare a unităţilor care aşteaptă n ordinea de servire a unităţilor
staţia (staţiile) de serviren putem avea staţii multiserver
fluxul de ieşire, important in sistemele constituite din reţele de cozi de aşteptare
Notaţia Kendall generalizată
(A/B/C):(D/E/F)A - tipul distribuţiei de intrare
(distribuţia timpilor intre sosiri)B - tipul distribuţiei de servire
(distribuţia timpilor de serviciu)(distribuţia timpilor de serviciu)C - numărul de staţii (servere) in sistemD - disciplina de servire din partea staţiilorE - numărul maxim de clienţi admişi in sistem
(cei care aşteaptă + cei in curs de servire)F - sursa apelanta
(populaţia din care pot proveni clienţii, finita sau nu)
Notaţia Kendall simplificată(pentru sisteme cu coada unica de aşteptare, 1+ servere)
A/B/k/mA - tipul distribuţiei de intrare
(distribuţia timpilor intre sosiri)B - tipul distribuţiei de servire B - tipul distribuţiei de servire
(distribuţia timpilor de serviciu)k - numărul de staţii (servere) in sistemm - dimensiunea maxima a cozii
Codificarea tipului distribuţiei(de intrare sau de servire)
M - distribuţia exponenţiala (notaţia M provine de la faptul că succesiunea stărilor sistemului formează un proces Markov, sau Memoryless)U - distribuţia uniformaU - distribuţia uniformaEk - o distribuţie Erlang cu k niveleHh - o distribuţie hiperexponenţială cu h niveleG sau GI - o distribuţie generalăD - o distribuţie deterministă
…
Disciplina de servireFIFO (FCFS): unităţile sunt servite in ordinea sosirii in sistemLIFO (LCFS): unităţile sunt servite in ordinea inversa sosirii in sistemSIRO: unităţile sunt servite in ordine aleatoareSIRO: unităţile sunt servite in ordine aleatoareSPT: prima unitate servita este cea cu timpul minim de servire PS (partajarea procesorului): pentru intervalul de timp in care k unităţi solicita servirea, serverul va asigura servirea fiecăreia pentru un timp proporţional cu 1/k
Disciplina de servire (cont.)PR (scheme pe baza de priorităţi): clienţilor le sunt date priorităţi la intrarea in coada, clientul prioritar este primul servit n Non-preemptive: o unitate aflata in curs de servire n Non-preemptive: o unitate aflata in curs de servire
nu poate fi întrerupta
n Preemptive: o unitate aflata in servire poate fi scoasa de o alta intrata in sistem cu o prioritate mai mare; reintrarea unităţii întrerupte in servire se poate face din punctul in care a fost întrerupta sau de la început
Sisteme de aşteptare cu server unic
Procesele de sosire a unităţilor în sistem si de servire a clienţilor sunt in general modelate ca procese aleatoare Bufferul poate avea capacitate finita sau infinita (un buffer de capacitate finita poate conduce la blocaje în sistem)
Procese Poissonsunt procese stochastice A(t)t≥0 cu valoripozitive, discrete în timppresupunerile (postulatele) pe care se bazeazăteoria acestor procese stochastice (siteoria acestor procese stochastice (sidezvoltarea formulei distribuţionale Poisson)sunt minimale si conforme cu realitateaexperimentalaExemplu: un proces de numărare a sosirilor într-un sistem de aşteptare - atunci când sosirile au loc pe rând si sunt independente)
Postulatele Poisson1. Într-un interval "mic" de mărime Δt, probabilitatea de
a înregistra exact o sosire e proporţionala cu mărimea intervalului:
P(A(t+Δt)-A(t)=1) = λ•Δt2. În acelaşi interval "mic" de mărime Δt, probabilitatea 2. În acelaşi interval "mic" de mărime Δt, probabilitatea
de a înregistra mai mult de o sosire este neglijabila: P(A(t+Δt)-A(t)>1) = o(Δt)
3. Sosirile sunt independente: probabilitatea unei sosiri într-un interval de timp "mic" e independenta de alte sosiri si de timpul scurs de la ultima sosire în sistem
Distribuţia Poisson: ecuaţii (1)Distribuţie discreta ce modelează numărul de sosiri într-un sistem de aşteptare ca variabila aleatoare X=A(t) Daca Pn(t)=P(A(t)=n): probabilitatea de a înregistra n sosiri în sistem în intervalul (0,t)
Atunci P (t)≥0, P (0)=1, P (0)=0 pt. n>0, Σ P (t)=1Atunci Pn(t)≥0, P0(0)=1, Pn(0)=0 pt. n>0, Σn=0,∞ Pn(t)=1
Rezulta imediat ca Pn(Δt) = λ·Δt + o(Δt) pentru n ≥1
Probabilitatea ca în 2 intervale succesive disjuncte (0, t) si (t, t+Δt) sa nu înregistram nici o sosire:
P0(t+Δt) = P0(t)·P0(Δt) = P0(t)·(1 - λ·Δt - o(Δt))
Distribuţia Poisson: ecuaţii (2)(P0(t+Δt) - P0(t)) / Δt = -λ·P0(t) - o(Δt) / ΔtRezulta prin trecerea la limita cu Δt →0 ecuaţiadiferenţiala (cu condiţie iniţiala)P'0(t) = -λ·P0(t), P0(0)=1, cu soluţia P0(t) = e-λtP'0(t) = -λ·P0(t), P0(0)=1, cu soluţia P0(t) = eProbabilitatea ca în cele doua intervalesuccesive sa înregistram una sau mai multesosiri (n>0):
t)o(+t(t)P 1-n+t))o(-t-(1(t)Pn=
t)(Pk(t)P k-n+t)(P1(t)P 1-n+t)(P0(t)Pnt)=+(tPnn
2=k∆∆∆∆
∆∑∆∆∆
••••
•••
λλ
Distribuţia Poisson: soluţia.(' 0>n pentru0 =(0)P 1,=(0)P (t),P(t)+P-=t)P n01-nnn λλ′
Soluţia acestei ecuaţii diferenţiale este distribuţia Poisson generala de parametru λ:
,n!
e)t(=(t)Pt-n
n
λλ
având atât media cât si dispersia egale cu λt
Triunghiul distribuţiilor fara memorie
Următoarele 3 propoziţii sunt echivalente:A. Timpul între sosiri este distribuit exponenţial, după legea
F(x)=P(t≤x)=P(t ≤ T+xt>T)=1-e-λx,având media 1/λ si dispersia 1/λ2 (un proces Poisson de sosire areo distribuţie exponenţiala pentru timpii între sosiri).
B. Probabilitatea de a avea o singura sosire în sistem într-un intervalB. Probabilitatea de a avea o singura sosire în sistem într-un intervalde timp de mărime Δt (mic) este λ·Δt + o(Δt).
C. Probabilitatea de a avea n sosiri în sistem în intervalul (0,t)respecta distribuţia Poisson:
obţinuta prin rezolvarea ecuaţiei diferenţiale
,n!
e)t(=(t)Pt-n
n
λλ
P+P-=dt
(t)dP1-nn
n λλ
Descompunerea si compunereaproceselor Poisson
Daca un proces Poisson cu mediaλ, X=A(t), t≥0, consta dinevenimente de doua tipuri diferite,cu probabilitati de apariţie p,respectiv 1-p, atunci si v.a.X1=A1(t), X2=A2(t) ce număraapariţiile pt. cele 2 tipuri de
λ λp
λapariţiile pt. cele 2 tipuri deevenimente, sunt procese Poissonindependente, cu media λ⋅p,respectiv λ⋅(1-p).
Daca X1=A1(t) si X2=A2(t) suntprocese Poisson cu media λ1,respectiv λ2, atunci siX=A(t)=A1(t)+A2(t) constituie unproces Poisson cu media λ=λ1+λ2.
λ(1-p)
λ
λ
λ
Indicatori de performantanumărul mediu de unităţi in sistem, fie in coada de aşteptare, fie in curs de servire
timpul mediu de aşteptare
timpul mediu de răspuns sau timpul sistem timpul mediu de răspuns sau timpul sistem (timpul de aşteptare + timpul de servire)
lungimea maxima a cozii de aşteptare
coeficientul de utilizare a serverului (fracţiunea de timp în care serverul este efectiv ocupat)
Legea lui Little (formula de conservare)
Daca:N este numărul mediu de unităţi în sistemλ este rata medie de sosire a unităţilor (clienţilor) în sistem(clienţilor) în sistemT este timpul mediu de rămânere a unui client în sistem
Atunci:
N = λ•T
Demonstraţie (grafica)
ε
s(t) - numărul de sosiri în sistem în intervalul [0,t]
p(t) - numărul de plecări din sistem în intervalul [0,t]
⇒ N(t)=s(t)-p(t), numărul de clienţi în sistem la mom. t
Ti - timpul petrecut de clientul i în sistem
Dreptunghiurile ce compun aria haşurata au baza egala cu Ti, iar înălţimea egala cu 1 (sosirile au loc pe rând)
εττ -)T(=)dN( i
s(t)t
∑∫ εττ -)T(=)dN( i1=i0
∑∫
0.=t
dar ;t
-t
s(t)ts
)dN(=
t
)dN(
ttt
t
0
t
t
0
t
εεττττ
limlimlimlimlim )( ∞→∞→∞→∞→∞→
•∫∫
s(t)
T=;
ts(t);
t
dτN(τ=
i
s(t)
i=
tt
t
tTλ=N
∑∫∞→∞→∞→
10 limlimlim)
Aplicaţia 1:Nod de reţea în regim de testare
Un nod de reţea (server) în testare, primeşte/ transmite pachete de date (mesaje) de lungime fixa, la intervale de timp deterministe si fixe
Timpul sistem al unui mesaj are 4 componente:timpul de prelucrare în nod (împachetare, despachetare)timpul de prelucrare în nod (împachetare, despachetare)timpul de aşteptare, înaintea prelucrării sau transmiteriitimpul de transmitere la nodul următor, de la primul bit la ultimul bit (vom considera transmisia seriala)timpul de propagare, între transmisia primului bit de către nodul curent si recepţionarea sa de către nodul următor (≈0)
Condiţii de calcul
(1) timpul (S secunde) între sosirea mesajelor este fix (deci si rata sosirilor în sistem este fixa: λ=1/S)
(2) nodul poate prelucra si transmite simultan câte un mesaj(3) timpii de prelucrare P si de transmitere kS pentru un
mesaj îndeplinesc cerinţele: k ≤ 1, kS+P < 2Smesaj îndeplinesc cerinţele: k ≤ 1, kS+P < 2SRezulta ca:
Timpii de prelucrare P si transmitere kS sunt singuriirelevanţi, deoarece, datorita capacitaţii de prelucrare sitransmisie asincrona a serverului, mesajele nu aşteaptă!Timpul sistem al fiecarui mesaj este acelaşi, egal si cumedia sa: T = kS+P
Aplicarea legii lui Little Numărul mediu de clienţi în sistem:
N = λT = k+P/S
Interpretare:N nu este o limita catre care converge numărul de clienţin sistem, N(t) - de fapt N(t) nu converge, deoareceîn sistem, N(t) - de fapt N(t) nu converge, deoarecesistemul nu atinge o stare de echilibru statistic!Totuşi, aplicarea legii lui Little este riguroasa prininterpretarea lui N ca valoare fixa a mediei temporale anumărului de unitati în sistem, determinat la momentediscrete de timp, în timp (foarte lung):
t)dtNk1=N
k
0k(lim ∫∞→
Aplicaţia 2:Sistem de calcul în time-sharing
Task-urile necesita un timp mediu de pregătire G si de prelucrare P (dar pot fi ţinute în coada de către procesor, în aşteptarea servirii)
Condiţii de calcul Există întotdeauna un utilizator gata sa ia locul altuia care se ridica de la terminal (deoarece suntem interesaţi în estimarea valorii maxime pentru rata de ieşire a unităţilor din sistem) Echivalent, numărul de utilizatori din sistem este constant (N)Echivalent, putem considera reintrarea imediata în sistem a Echivalent, putem considera reintrarea imediata în sistem a oricărui utilizator ce încheie un taskT este timpul sistem mediu pentru un utilizator, cu structura:
T = G+D+P, unde D este timpul de aşteptare al task-ului utilizator, ce ia valori discrete între 0 (intrare directa în execuţie) si (N-1)•P (aşteptare maximala după toţi ceilalţi utilizatori)
Aplicarea legii lui LittleIntre punctele A si C: λ = N/T0 ≤ D ≤ (N-1)•P ⇒ G+P ≤ T ≤ G+N•P ⇒
Intre punctele B si C (intrarea si iesirea serverului):
P+GN
PN+GN
≤≤⋅
λ
N,1 N min≤≤ λ
(rata de procesare a joburilor nu poate depăşi 1/P)
Limitele de variaţie ale timpului mediu de aşteptare per utilizator atunci când sistemul este integral utilizat:
P+G
N,P1
PN+GN min≤≤
⋅λ
PN+G T P+GP,N ⋅≤≤⋅max
Variaţia ratei de prelucrare λ
Variaţia timpului sistem mediu pentru un utilizator
DiscuţieCând N creste:n rata de ieşire tinde spre valoarea maxima 1/Pn timpul mediu de aşteptare pentru un utilizator
creste proporţionalRata de ieşire maximala depinde de parametrii-Rata de ieşire maximala depinde de parametrii-sistem ca:n proporţia între timpii de pregătire si de execuţien disciplina de servire
Limitele obţinute nu depind de parametrii-sistem
InterpretăriCât timp N<1+G/P, N reprezintă un factor deblocaj în sistem, deoarece procesorul rămânenefolosit o fracţiune importanta din timp(corespunzătoare momentelor de angajare simultana atuturor utilizatorilor în pregătirea task-urilor lor)tuturor utilizatorilor în pregătirea task-urilor lor)
Când N>1+G/P, puterea de procesare aserverului este cea care determina blocajul
Reţele de cozi de aşteptareO reţea de cozi este un sistem ce constă din mai multe servere, fiecare având asociat un buffer
Unităţile (clienţii) pot aparţine mai multor clase
Clienţi aparţinând unor clase diferite pot necesita Clienţi aparţinând unor clase diferite pot necesita servicii diferite, chiar de la acelaşi server
După un serviciu, un client poate fi dirijat într-un anumit mod n De ex., pentru a cere efectuarea unui alt serviciu la
un server diferit de primul sau a părăsi sistemul
Clasificarea reţelelor de cozi după modalitatea de dirijare
Reţele deschise - au loc: n sosiri în sistem ale unităţilor din exterior (de obicei
modelate ca procese Poisson) n parasiri ale sistemului de către clienţi după efectuarea
unor serviciiReţele închiseReţele închisen fiecare client circula între servere, pentru serviri, fara a
părăsi sistemul; n din exterior nu pot intra noi clienţi în sistem, deci
numărul total de clienţi este o constanta sistemReţele mixten deschise pentru anumite clase de clienţi si închise
pentru altele
Reţele de cozi factorizabile Distribuţia staţionara a reţelei poate fi descompusa într-un produs de distribuţii ale fiecăruia dintre subsistemele de aşteptare (cozile) componente, analizabile separat n Pentru reţelele deschise ⇒ independenta distribuţiilor staţionare
ale cozilor individuale (distribuţia staţionara e produsulale cozilor individuale (distribuţia staţionara e produsuldistribuţiilor individuale ce se obţin prin analiza separata a fiecăreicozi considerând o rata de sosire adecvata, modificata, ce reflectamodalitatea de dirijare în reţea)
n Pentru reţelele închise ⇒ dependenta dintre cozi poate ficapturata prin normalizarea soluţiei independente peste un spaţiude stare normalizat; în acest caz, pot apare dificultaticomputaţionale în calculul constantei de normalizare
Reţele Jackson deschiseCaracteristici:
M staţii de servire (cu server unic), fiecare având un buffer de capacitate infinitaSosirile din exterior ale clienţilor la fiecare staţie i dintre cele M sunt procese Poisson cu media λ0,icele M sunt procese Poisson cu media λ0,i
După efectuarea unui serviciu de către serverul i, un client poate cere servirea din partea unui alt server j -cu probabilitatea qi,j, sau poate parasi sistemul - cu probabilitatea qi,0 :
q-1=q ji,
M
j=1i,0 ∑
Ecuaţii de fluxDaca:
n timpul de [de]servire al serverului i este exponenţial distribuit cu media si=1/μi
n λi este rata de sosire medie a clienţilor la serverul i (includem atât clienţii ce sosesc din exteriorul (includem atât clienţii ce sosesc din exteriorul sistemului la serverul i, cât si pe cei care sosesc din sistem, după servirea lor de către alt server)
Atunci:
M1,2,...,=iq+= ,ji,j
M
j=1i0,i •∑λλλ
Reţele Gordon-Newell închiseCaracteristici:
Se bazează pe aceleaşi premise ca si o reţea Jackson, exceptând faptul ca λ0,i=0 si qi,0=0, pentru orice i (aceasta exprima faptul ca reţeaua este închisa -numărul total N de clienţi în sistem este fix) numărul total N de clienţi în sistem este fix) Daca notam starea sistem cu n=(n1,n2,...nM), unde ni e numărul de clienţi în bufferul serverului i:
N=n i
M
=1i∑
Modelarea sistemelor de calculModelarea sistemelor de calcul
Simularea sistemelor dinamice cu
Curs, anul III Calculatoare
Simularea sistemelor dinamice cu evenimente discrete (SDED)
Simularea (Shannon): Procesul construirii unui model pentru un sistem/proces real si efectuare de experimente folosind modelul pentru:
intelegerea comportarii sistemului realintelegerea comportarii sistemului realurmarirea evolutiei dinamice a sistemuluievaluarea unor strategii de operare
Modelare și simulareModel: o reprezentare a unui sistemn Modelele matematice folosesc notații simbolice și
ecuații matematice/ modelele de simulare pot fi considerate tipuri particulare de modele matematice:- Deterministe: un set cunoscut de intrări corespunde - Deterministe: un set cunoscut de intrări corespunde
cu un set unic de ieșiri- Stochastice: una sau mai multe intrări sunt v.a.,
fapt ce determină ieșiri aleatoaren Modelele fizice, constructive
Modelare: procesul de construire a unui modelSimulare: imitarea modului de operare al unui sistem sau proces real, de obicei în timp
Modalități de simulare discretă (stochastică)
Statică, de ex. simularea Monte-Carlo1. Se definește un domeniu al intrărilor posibile2. Se generează aleator intrări din domeniu pe baza
unei distribuții de prob. (cel mai adesea uniformă)3. Se fac calcule deterministe folosind aceste intrări3. Se fac calcule deterministe folosind aceste intrări4. Se agregă rezultatele individuale în cel final
n Ex: valoarea lui π/4 este aproximată de raportul între aruncările într-un cerc și cele în pătratul “circumscris”
Dinamică, de ex. simularea sistemelor dinamice cu evenimente discrete
Simularea SDEDmodalitate sistematică de generare a traiectoriilor dinamice ale sistemului producerea unor secvenţe de ipostaze (imagini) ale SDED reprezintă dinamica (evoluţia) in timpale SDED reprezintă dinamica (evoluţia) in timpconcept important: starea, caracterizată prin variabilele de stare ce iau valori discreten variabilele continue (ex. timpul), nu sunt considerate
independent, ci doar în relaţie cu apariţia unor evenimente; ele sunt discretizate si considerate ca variabile-anexa sau deduse
Starea in simularea SDEDstarea fizică – cea uzuala in TS, aici tipic discreta Ex: nr.unităţilor din coada unui server intr-o reţea de cozistarea matematică (ipostaza la mom. t), include:n o informaţie completa asupra stării fizice a sistemului
la momentul tla momentul tn toate elementele necesare pentru determinarea in
mod unic a evoluţiei viitoare a sistemului, n o lista a evenimentelor viitoare (LEV) ce vor determina
tranziţiile de stare n valori curente ale statisticilor cumulative/contorilor ce
vor fi folosite in calculul statisticilor rezumative finale
Dinamica simulării SDEDEste determinata de evenimente, ce pot fi:n externe (ex. sosirea unei unităţi in sistem)
n interne (ex. terminarea servirii unui client la un server)
Apariţia unui eveniment împreuna cu îndeplinireaApariţia unui eveniment împreuna cu îndeplinireaunor condiţii logice (reguli de operare) determina otranziţie de stare
In noua stare noi evenimente pot fi planificateEvenimentele existente continua sau vor fi
terminate conform cu LEV
Evenimenteleapariţii instantanee care schimbă starea sistemdelimitează activităţi in sistempot fi:n endogene: apariţii in interiorul sistemuluin endogene: apariţii in interiorul sistemuluin exogene: apar in mediu (in afara sistemului) dar
afectează sistemul
in simulare, parametrul timp este doar asociatapariţiei evenimentelor, iar progresia temporala asimulării este implicita avansului in procesarea LEV
Simulatoareun simulator este un program de calculator prin care se modeleaza:n comportamentul intern al unui sistem realn procesele de intrare ce dirijeaza sau controleaza
sistemul simulatiesirea unui simulator consta intr-un set de iesirea unui simulator consta intr-un set de masuratori legate de reactiile observabile si performanta sistemului realmasuratorile obtinute sunt doar estimatori ai masurilor reale, deoarece simularea nu are ca suport sistemul real, ci un model al acestuia (mai mult sau mai putin fidel)
Metodologii de simulareConstrucţia unui simulator se face pe baza unei
metodologii de simularesimularea condusa de timp implica existenta unui ceas de timp central avansat cu increment fix n generează algoritmi ineficienţi si este mult mai puţin n generează algoritmi ineficienţi si este mult mai puţin
utilizata n prezintă un anumit interes doar in cazul simulării
paralele (distribuite) metodologia generala de simulare pentru SDED este simularea condusa de evenimenten planificarea corecta a execuţiei evenimentelor impune
cu necesitate includerea lor intr-o lista ordonata după timpii de apariţie ai evenimentelor (LEV)
Abordări in simularea SDEDPlanificarea de evenimenten impune ca atunci când o activitate începe, durata ei
sa fie calculata (sau generata aleator) si evenimentul ei de sfârşit sa fie plasat in LEV
n se definesc schimbări de stare pt. fiecare evenimentmecanismul de avans temporal si garantarea apariţiei n mecanismul de avans temporal si garantarea apariţiei cronologice a evenimentelor e complet bazat pe LEV
Interacţiunea proceselorn se descriu procesele asociate cu entităţile – acestea
pot fi permanente sau temporare n simularea se constituie ca un ansamblu de procesen mai multe procese pot fi simultan active in model si
interacţiunea dintre ele poate fi complexa
Cum decurge simularea dirijată de evenimente...
LEV, menţinuta ordonata, se compune din:n “evenimentul iminent" - cel aflat in fruntea
listei, ce poate fi deja in curs de trataren celelalte evenimente (“potenţiale”), numite n celelalte evenimente (“potenţiale”), numite
astfel deoarece ele pot decalate, modificate sau chiar anulate prin simularea evenimentului iminent
“Activitate" in cadrul simulării - apariţia unui eveniment, urmata de tratarea lui, prin care se modifica starea sistem si (potenţial) LEV
Compus dintr-o coada de dimensiune maxima n=500 si un server
... pentru un sistem simplu de aşteptare
COADA SERVER
Va fi considerat complet stochastic:n Procesul de sosire este aleatorn Timpul de servire este aleator
Sosirea clienţilorClienţi inaşteptare
Client in servire
Plecarea clienţilor
Definire sistem si obiectiveEntităţi: Clienţi, Coada, Servern nu este necesara reprezentarea explicita a clienţilor
(individualizarea lor)
Evenimente: sosire client, plecare clientDate colectateDate colectateêUtilizare serverê Lungimea maxima a coziiêTimp de aşteptare client(i)êTimp de răspuns al sistemuluiêProcentajul clienţilor ce aşteaptă peste o valoare prag
Definirea statica a modeluluiStarea sistem este descrisa de variabilele:n lqt=numărul de clienţi aflaţi in coada de aşteptare la un
moment datn lst=numărul de clienţi aflaţi in servire la un moment dat, 1 sau
0 (sau starea serverului, ocupat sau liber)
Evenimente:Evenimente:n sosirea unui client in sistem;n plecarea unui client din sistem prin terminarea servirii sale;
Activităţi:n timpul între sosiri, definit de o tabela ce se generează aleatorn timpul de servire, definit in acelaşi mod
Întârzieri: aşteptări in coada, pana serverul devine liber
Descrierea dinamica a modeluluiCum afectează fiecare eveniment starea sistem,
atributele entităţilor, conţinutul seturilor?Cum sunt activităţile definite (determinist, probabilistic,
printr-o ecuaţie matematica)?Care sunt evenimentele de început/sfârşit al activităţii?Poate o activitate începe indiferent de starea sistem,Poate o activitate începe indiferent de starea sistem,
sau este condiţionata de starea sistem?Care sunt evenimentele de început/sfârşit al fiecărui tip
de întârziere?Care sunt condiţionările pentru ca o întârziere sa
“înceapă" sau sa se "termine"?Care este starea sistemului la momentul iniţial?Ce evenimente "primare" trebuie generate la momentul
iniţial pentru ca simularea sa poată începe?
Dinamica simulării in interacţiunea proceselor
Se identifica entităţile caracteristice in sistemPot coexista, interacţiona si intra in competiţie multiple copii ale entităţilorCodul de simulare este non-procedural: in mod separat, se descriu entităţile “tipice”separat, se descriu entităţile “tipice”Pot exista multe tipuri de entităţi, inclusiv cele de “excepţie” (de ex. pentru tratarea defectelor)Este de obicei necesar un soft specializatn Altfel, se recurge la serializare si planificare de
evenimenten Oricum, eficienţa este mai scăzuta in cazul execuţiei
secvenţiale
Creare Nod Nod in Coada Terminare Nod
Activitate Servire
Diagrama proceselor asociate entităţilor
18
Activitate Servire
Aceasta tehnica este adecvata când rezolvarea unei probleme este echivalenta cu descrierea unor activităţi relativ independente desfăşurate in paralel, dar care comunica si interacţionează pe parcursul execuţiei lor
Fazele unui studiu de simulare
Faza de planificarea) Specificarea problemei
• intrebari esentiale: “Ce se cere? La ce va folosi?”
• uneori se poate formula doar obiectivul atasat unei descrieri vagi a procesului studiat
b) Estimarea resurselor• implica alegerea modalitatii de abordare, studii de
fezabilitate, evaluarea costurilor de timp si personal, ca si stabilirea graficului de derulare a activitatilor
c) Analiza sistemului si a datelor • se identifica diversele nivele de detaliere necesare
Faza de modelareConsta in:a) Construcţia modelului: pot exista mai multe modele candidate, trebuie ales unul
b) Colectarea datelor: datele reale permit b) Colectarea datelor: datele reale permit identificarea modelului adecvat
c) Translaţia modelului: codificarea intr-un program ("model programat")
Faza de verificare/validare (1)Verificarea consta in depanare si testare programValidarea este mai ampla – la întrebarea “reflecta
programul in mod fidel sistemul?” răspunsul e DA numai daca se respecta câteva principii de lucru
In dezvoltarea unui model valid asociat datelor de In dezvoltarea unui model valid asociat datelor de intrare distingem următorii paşi:
a. colectarea datelor brute din sistemul studiatb. identificarea distribuţiei statistice a datelor, prin:- construirea distribuţiei frecvenţiale a datelor de intrare
(histograma);- asumarea unei presupuneri distribuţionale (in practica apar mai
frecvent doar câteva distribuţii standard)
Faza de verificare/validare (2)Paşi in validare (cont.):
c. estimarea parametrilor distribuţiei asumated. testarea concordantei intre distribuţia asumata (cuparametri estimaţi) si datele de intrare, folosind:§ testul χ2§ testul χ§ testul Kolmogorov-Smirnov
ØDaca testul de concordanta eşuează, ipoteza că dateleurmează legea distribuţionala propusa trebuie respinsasi se încearcă o noua ipoteza distribuţionala (se reia cupasul b)ØDaca mai multe iteraţii ale acestei proceduri eşueazăin găsirea unei concordante intre distribuţia asumata sidatele colectate, trebuie folosita distribuţia empirica
Faza de execuţieConsta in:a) Proiectarea experimentelor: se aleg execuţii genericeb) Experimentare: se executa programul cu date b) Experimentare: se executa programul cu date reale!c) Analiza: se interpretează rezultateled) Implementarea/Documentarea: • cum se implementează deciziile rezultate din simulare?• cum se documentează modelul in vederea reutilizării?
Măsurători de performanţăFundamentale sunt răspunsurile la câteva întrebări:
Ce alternative se simulează (se executa)? Cat de lunga este o execuţie?Ce se măsoară?Maximul, minimul, totalul, media, varianta, momente de Maximul, minimul, totalul, media, varianta, momente de ordin superior, distribuţii specifice de frecventa, timpii intre sosiri, timpii de servire, lungimi ale cozilor, rate de pierdere sau eroare etc.Care sunt proprietăţile (statistice) ale "masurilor" de care suntem interesaţi?Sunt necesare si alte execuţii? Trebuie schimbat modelul? Trebuie schimbaţi parametrii?
Planificarea de evenimenteRămâne cea mai adecvată programării standard, si cea mai eficienta in cazul execuţiei secvenţialeSe utilizează de obicei funcţii de biblioteca pentrun Prelucrarea listelorn Generarea numerelor aleatoaren Generarea numerelor aleatoaren Generarea variabilelor aleatoaren Colectarea statisticilorn Managementul (ordonarea) LEV si ceasului de timp
“Nod de sincronizare" - ansamblul procedurilor ce implica întreţinerea LEV (adăugarea, suprimarea sau modificarea de evenimente)
Ipostaza sistem tipica
Exemplu numeric
UnitTimpi între sosiri
Timp sosire
1 - 0
2 2 2
Unit Timp servire
1 2
2 1
Unit Timp sosire
Încep servire
Timp servire
Termin servire
1 0 0 2 2
2 2 2 1 32 2 2
3 4 6
4 1 7
5 2 9
6 6 15
2 1
3 3
4 2
5 1
6 4
2 2 2 1 3
3 6 6 3 9
4 7 9 2 11
5 9 11 1 12
6 15 15 4 19
Algoritmul de planificare evenimente/ avans al timpului simulării
1) Scoaterea evenimentului iminent din LEV
2) Avansul ceasului sistem (CLOCK) la momentul apariţiei evenimentului
3) Execuţia evenimentului iminent 3) Execuţia evenimentului iminent ⇒actualizarea stării sistemului, a atributelor entităţilor
sistemului, a seturilor
4) Generarea evenimentelor viitoare si plasarea lor in LEV in poziţia corecta
5) Actualizarea rezultatelor cumulative si statistice
Tratare eveniment “sosire client”
Plasează clientul sosit in coada
Planifica următoarea sosire
Server ocupat?DaNu
Plasează clientul sosit in coadaOcupa server
Planifica eveniment de plecare client
Return
Da
Selecteaza client din coadapentru servire
NuCoada vida?
Elibereaza serverul
Tratare eveniment “plecare client”
Actualizeaza statisticile pentru coadasi noul client in servire
Return
Actualizeaza statisticile pentru server
Planifica evenimentul de plecare
Colecteaza datele pentru clientul care pleaca
Programarea modeluluiPoate fi făcuta intr-un limbaj procedural (C)Proiectul C (anexat) e compus din fişierele sursa: n "sp.c“: simulatorul principal, ce conţine rutinele de
iniţializare, avans timp, tratare a evenimentelor si generare a rapoartelor generare a rapoartelor
n "rndevg.c“: conţine rutine pentru generarea distribuţiilor statistice
n "rndevg.h“: fişierul header ce conţine definiţiile de prototipuri si constante
Un număr de 10 execuţii fără modificarea parametrilor modelului permite o analiza simpla
Execuţia modelului programat Valoarea de start (seed)
Utilizarea serverului
(%)
Lungimea maxima a
cozii
Timpul total al simularii
(min.)
% clientilor ramasi > 4 min.în sistem
Timpul de raspuns
mediu (min.)
Numarul plecarilor din
sistem
61011 72.55 13 44095.2 71.47 3.2 10 000
61136 70.65 16 45352.9 70.59 3.2 10 000
61190 71.47 11 44751.2 71.08 3.2 10 000
61209 71.39 20 44774.6 71.07 3.2 10 000
61225 72.11 11 44569.0 71.45 3.2 10 000
61237 70.95 13 45121.3 70.01 3.2 10 000
61249 72.03 11 44461.9 70.73 3.2 10 000
61265 72.25 10 44412.3 71.32 3.2 10 000
61280 71.40 16 44675.1 71.23 3.2 10 000
61299 71.57 14 44909.6 71.07 3.2 10 000
Media 71.64 13.5 44712.3 71.002 3.2 10 000
Abaterea 0.564 2.94 343.1 0.426 0 0
Modelarea sistemelor de calculModelarea sistemelor de calcul
Studiu de simulare secvenţială
Curs, anul III Calculatoare
Studiu de simulare secvenţialădiscretă
Formularea problemei si planului
Colectare date si definire model
Model programat valid?
Proiectarea experimentelor
Da
Nu
Fazele studiului de simulare
Model conceptual valid?
Constructia programului si verificarea
Executii pilot
Executia experimentelor
Analiza rezultatelor simularilor
Interpretare si documentare program
NuDa
Scopul studiuluiDe a relua si aprofunda metodologia de baza a simulării (planificarea de evenimente) si de a identifica unele probleme des întâlnite, evidenţiate de un exemplu simpluExemplu de lucru: acelaşi sistem de procesare Exemplu de lucru: acelaşi sistem de procesare M/M/1/n (poate fi un calculator, o maşina-unealta)Spre deosebire de cursul anterior, vom încerca un studiu pas cu pas (software-independent)Vor fi reexaminaten Terminologia de bazan Câteva probleme statistice importante
Sistemul simplu de aşteptare
Sosirea unitatilor Plecarea unitatilor
Server
Coada (FIFO) Unitate in servire
4567
Se urmăreşte estimarea:§ Capacitaţii de procesare§ Timpului de aşteptare in coada§ Lungimii utile a cozii§ Proporţiei de timp in care serverul este ocupat§ etc.
Specificare si iniţializare modelLa momentul iniţial (t=0) sistemul este golDate de intrare (observate sau generate, nu interesează deocamdată cum), de ex. in minute:
Client (unit) Timp de sosire Timp intre sosiri Timp de servire1 0.00 1.73 2.902 1.73 1.35 1.762 1.73 1.35 1.763 3.08 0.71 3.394 3.79 0.62 4.525 4.41 14.28 4.466 18.69 0.70 4.367 19.39 15.52 2.078 34.91 3.15 3.369 38.06 1.76 2.37
10 39.82 1.00 5.3811 40.82 . .
. . . .
. . . .Condiţie de oprire: t>20
Obiective & Masuri de performantaCapacitatea de procesare totala pe durata simulării (P)Timpul de aşteptare mediu al unităţilor in coada
N = nr. unităţilor ce aşteaptă in coadaWQ
N∑
Timpul de aşteptare maxim al unităţilor in coada
N = nr. unităţilor ce aşteaptă in coadaWQi = timpul de aşteptare in coada al unităţii iŞtim ca: WQ1 = 0 (?)
N > 1 (de ce?)N
WQN
ii∑
=1
iNi
WQmax,...,1=
Măsuri de performanţă (2)Media (in timp) a numărului de unităţi in coada
Numarul maxim de unităţi in coada 20
)(200∫ dttQ Q(t) = numărul de unităţi in coada
la momentul tNumarul maxim de unităţi in coada
Timpul mediu si maxim total in sistem al clienţilor (sau timpul de ciclare)
)(max200
tQt≤≤
iPi
P
ii
TSP
TSmax
,...,11 ,
=
=∑ TSi = timp in sistem al clientului i
Măsuri de performanţă (3)
Gradul de utilizare a serverului (proporţia de timp in care serverul este ocupat)
=∫ ttB
dttB mom. laocupat este serverul daca1)(,
)(20
0
=
ttB
mom. laliber este serverul daca0)(,
20
Validarea consistentei datelor de intrare
Timpul mediu intre sosiri = 4.08 min.Timpul mediu de servire = 3.46 min.Deci unităţile sunt procesate mai repede decât sosesc (in medie), ceea ce înseamnă ca:
Sistemul va opera in regim stabil după un timpn Sistemul va opera in regim stabil după un timpn Daca toţi timpii intre sosiri si cei de servire ar fi exact
pe medie, unităţile nu ar intra in coadan Dar in general datele aleatoare au o anumita
variabilitate - coada se va forman Daca timpul mediu intre sosiri < timpul mediu de
servire, coada va creste “exploziv”
Modelarea analiticaEste aici posibila si utila, ca prima aproximaţie, folosind un model M/M/1Necesita insa presupuneri suplimentare: n Timpii intre sosiri ~ distribuiţi exponenţial
Timpii de servire ~ exponenţial, independent n Timpii de servire ~ exponenţial, independent n Trebuie ca E(servire) < E(inter-sosiri)n Analiza se face doar in starea stabilan Se pot obţine rezultate exacte; de ex., timpul mediu
de aşteptare in coada:
time) E(service time) ivalE(interarr 2
==
− S
A
SA
Sµµ
µµµ ,
Statistici cumulative si contoriNumărul curent de unităţi serviteTotalul timpilor de aşteptare in coadaNumărul curent de unităţi ce au stat in coadaTimpul maxim de aşteptare in coada (curent)Totalul timpilor in sistemTotalul timpilor in sistemTimpul maxim in sistem (curent)Aria de sub curba Q(t) (ce da media lungimii cozii)Maximul curent pentru Q(t)Aria de sub curba B(t) (ce da gradul de ocupare a serverului)
Dinamica simulării in abordarea prin planificarea de evenimente
Se identifica evenimentele caracteristiceSe iniţializează si se menţine un ceas de timp globalSe creează si se menţine LEV Se decide logica fiecărui tip de eveniment pentrun Tranziţiile de staren Actualizarea statisticilorn Actualizarea LEV
Se procesează logic evenimentele pe rând, in ordinea stricta a LEV (numita si calendar de evenimente)Trebuie specificata si o regula de oprire (timp maxim de simulare, număr maxim de unităţi procesate)
Tratarea evenimentelor (1)La sosirea unei noi unităţi in sistem
Actualizează variabilele statistice (acumulatori persistenţi)n Valoarea ariei de subQ(t)n Max Q(t)n Valoarea ariei de sub B(t)
Se aplica unităţii sosite “stampila de timp” curenta (se va Se aplica unităţii sosite “stampila de timp” curenta (se va utiliza ulterior)Daca serverul este liber:n Start procesare (planifica plecarea), pune serverul pe ocupat,
pune timpul de aşteptare in coada pe 0Altfel, daca serverul este ocupat:n Pune unitatea “la coada”, incrementează lungimea cozii
Planifica următorul eveniment de sosire
Tratarea evenimentelor (2)
La plecarea unei unităţi din sistem, după servireIncrementează acumulatorul corespunzătorCalculează timpul in sistem al unităţii (momentul curent –momentul sosirii)Actualizează variabilele statistice (ca la sosire)Actualizează variabilele statistice (ca la sosire)Daca coada este nevidă:n Scoate prima unitate din coada, calculează timpul sau de
aşteptare in coada, începe servirea (planifica evenimentul de plecare)
Altfel (daca coada este vida):n Trece serverul in starea liber (nu se mai planifica vreun
eveniment de plecare in LEV)
Tratarea evenimentelor (3)
La sfârşitul simulării:Se actualizează statisticileSe calculează masurile de performanta folosind valorile curente, care sunt si finale, ale acumulatorilor
Observaţii:La începutul simulării, trebuie făcute iniţializări (de ex. in LEV se pune primul eveniment de sosire si evenimentul de sfârşit)După tratarea fiecărui eveniment, se continua cu primul eveniment din LEV (eveniment iminent)
System
Clock
B(t)
Q(t)
Arrival times of custs. in queue
Event calendar
Number of completed waiting times in queue
Total of waiting times in queue
Area under Q(t)
Area under B(t)
Simularea pas cu pas: set-up
Q(t) graph B(t) graph
Time (Minutes) Interarrival times 1.73, 1.35, 0.71, 0.62, 14.28, 0.70, 15.52, 3.15, 1.76, 1.00, ... Service times 2.90, 1.76, 3.39, 4.52, 4.46, 4.36, 2.07, 3.36, 2.37, 5.38, ...
01
23
4
0 5 10 15 20
012
0 5 10 15 20
System
Clock 0.00
B(t) 0
Q(t) 0
Arrival times of custs. in queue
<empty>
Event calendar [1, 0.00, Arr] [–, 20.00, End]
Number of completed waiting times in queue 0
Total of waiting times in queue 0.00
Area under Q(t) 0.00
Area under B(t) 0.00
Iniţializări la t = 0.00
Q(t) graph B(t) graph
Time (Minutes) Interarrival times 1.73, 1.35, 0.71, 0.62, 14.28, 0.70, 15.52, 3.15, 1.76, 1.00, ... Service times 2.90, 1.76, 3.39, 4.52, 4.46, 4.36, 2.07, 3.36, 2.37, 5.38, ...
01
23
4
0 5 10 15 20
012
0 5 10 15 20
System
Clock 0.00
B(t) 1
Q(t) 0
Arrival times of custs. in queue
<empty>
Event calendar [2, 1.73, Arr] [1, 2.90, Dep] [–, 20.00, End]
Number of completed waiting times in queue 1
Total of waiting times in queue 0.00
Area under Q(t) 0.00
Area under B(t) 0.00
t = 0.00, sosirea unităţii 1
1
Q(t) graph B(t) graph
Time (Minutes) Interarrival times 1.73, 1.35, 0.71, 0.62, 14.28, 0.70, 15.52, 3.15, 1.76, 1.00, ... Service times 2.90, 1.76, 3.39, 4.52, 4.46, 4.36, 2.07, 3.36, 2.37, 5.38, ...
01
23
4
0 5 10 15 20
012
0 5 10 15 20
System
Clock 1.73
B(t) 1
Q(t) 1
Arrival times of custs. in queue
(1.73)
Event calendar [1, 2.90, Dep] [3, 3.08, Arr] [–, 20.00, End]
Number of completed waiting times in queue 1
Total of waiting times in queue 0.00
Area under Q(t) 0.00
Area under B(t) 1.73
t = 1.73, sosirea unităţii 2
12
Q(t) graph B(t) graph
Time (Minutes) Interarrival times 1.73, 1.35, 0.71, 0.62, 14.28, 0.70, 15.52, 3.15, 1.76, 1.00, ... Service times 2.90, 1.76, 3.39, 4.52, 4.46, 4.36, 2.07, 3.36, 2.37, 5.38, ...
01
23
4
0 5 10 15 20
012
0 5 10 15 20
System
Clock 2.90
B(t) 1
Q(t) 0
Arrival times of custs. in queue
<empty>
Event calendar [3, 3.08, Arr] [2, 4.66, Dep] [–, 20.00, End]
Number of completed waiting times in queue 2
Total of waiting times in queue 1.17
Area under Q(t) 1.17
Area under B(t) 2.90
t = 2.90, plecarea unităţii 1
2
Q(t) graph B(t) graph
Time (Minutes) Interarrival times 1.73, 1.35, 0.71, 0.62, 14.28, 0.70, 15.52, 3.15, 1.76, 1.00, ... Service times 2.90, 1.76, 3.39, 4.52, 4.46, 4.36, 2.07, 3.36, 2.37, 5.38, ...
01
23
4
0 5 10 15 20
012
0 5 10 15 20
System
Clock 3.08
B(t) 1
Q(t) 1
Arrival times of custs. in queue
(3.08)
Event calendar [4, 3.79, Arr] [2, 4.66, Dep] [–, 20.00, End]
Number of completed waiting times in queue 2
Total of waiting times in queue 1.17
Area under Q(t) 1.17
Area under B(t) 3.08
t = 3.08, sosirea unităţii 3
23
Q(t) graph B(t) graph
Time (Minutes) Interarrival times 1.73, 1.35, 0.71, 0.62, 14.28, 0.70, 15.52, 3.15, 1.76, 1.00, ... Service times 2.90, 1.76, 3.39, 4.52, 4.46, 4.36, 2.07, 3.36, 2.37, 5.38, ...
01
23
4
0 5 10 15 20
012
0 5 10 15 20
System
Clock 3.79
B(t) 1
Q(t) 2
Arrival times of custs. in queue
(3.79, 3.08)
Event calendar [5, 4.41, Arr] [2, 4.66, Dep] [–, 20.00, End]
Number of completed waiting times in queue 2
Total of waiting times in queue 1.17
Area under Q(t) 1.88
Area under B(t) 3.79
t = 3.79, sosirea unităţii 4
234
Q(t) graph B(t) graph
Time (Minutes) Interarrival times 1.73, 1.35, 0.71, 0.62, 14.28, 0.70, 15.52, 3.15, 1.76, 1.00, ... Service times 2.90, 1.76, 3.39, 4.52, 4.46, 4.36, 2.07, 3.36, 2.37, 5.38, ...
01
23
4
0 5 10 15 20
012
0 5 10 15 20
System
Clock 4.41
B(t) 1
Q(t) 3
Arrival times of custs. in queue
(4.41, 3.79, 3.08)
Event calendar [2, 4.66, Dep] [6, 18.69, Arr] [–, 20.00, End]
Number of completed waiting times in queue 2
Total of waiting times in queue 1.17
Area under Q(t) 3.12
Area under B(t) 4.41
t = 4.41, sosirea unităţii 5
2345
Q(t) graph B(t) graph
Time (Minutes) Interarrival times 1.73, 1.35, 0.71, 0.62, 14.28, 0.70, 15.52, 3.15, 1.76, 1.00, ... Service times 2.90, 1.76, 3.39, 4.52, 4.46, 4.36, 2.07, 3.36, 2.37, 5.38, ...
01
23
4
0 5 10 15 20
012
0 5 10 15 20
System
Clock 4.66
B(t) 1
Q(t) 2
Arrival times of custs. in queue
(4.41, 3.79)
Event calendar [3, 8.05, Dep] [6, 18.69, Arr] [–, 20.00, End]
Number of completed waiting times in queue 3
Total of waiting times in queue 2.75
Area under Q(t) 3.87
Area under B(t) 4.66
t = 4.66, plecarea unităţii 2
345
Q(t) graph B(t) graph
Time (Minutes) Interarrival times 1.73, 1.35, 0.71, 0.62, 14.28, 0.70, 15.52, 3.15, 1.76, 1.00, ... Service times 2.90, 1.76, 3.39, 4.52, 4.46, 4.36, 2.07, 3.36, 2.37, 5.38, ...
01
23
4
0 5 10 15 20
012
0 5 10 15 20
System
Clock 8.05
B(t) 1
Q(t) 1
Arrival times of custs. in queue
(4.41)
Event calendar [4, 12.57, Dep] [6, 18.69, Arr] [–, 20.00, End]
Number of completed waiting times in queue 4
Total of waiting times in queue 7.01
Area under Q(t) 10.65
Area under B(t) 8.05
t = 8.05, plecarea unităţii 3
45
Q(t) graph B(t) graph
Time (Minutes) Interarrival times 1.73, 1.35, 0.71, 0.62, 14.28, 0.70, 15.52, 3.15, 1.76, 1.00, ... Service times 2.90, 1.76, 3.39, 4.52, 4.46, 4.36, 2.07, 3.36, 2.37, 5.38, ...
01
23
4
0 5 10 15 20
012
0 5 10 15 20
System
Clock 12.57
B(t) 1
Q(t) 0
Arrival times of custs. in queue
()
Event calendar [5, 17.03, Dep] [6, 18.69, Arr] [–, 20.00, End]
Number of completed waiting times in queue 5
Total of waiting times in queue 15.17
Area under Q(t) 15.17
Area under B(t) 12.57
t = 12.57, plecarea unităţii 4
5
Q(t) graph B(t) graph
Time (Minutes) Interarrival times 1.73, 1.35, 0.71, 0.62, 14.28, 0.70, 15.52, 3.15, 1.76, 1.00, ... Service times 2.90, 1.76, 3.39, 4.52, 4.46, 4.36, 2.07, 3.36, 2.37, 5.38, ...
01
23
4
0 5 10 15 20
012
0 5 10 15 20
System
Clock 17.03
B(t) 0
Q(t) 0
Arrival times of custs. in queue ()
Event calendar [6, 18.69, Arr] [–, 20.00, End]
Number of completed waiting times in queue 5
Total of waiting times in queue 15.17
Area under Q(t) 15.17
Area under B(t) 17.03
t = 17.03, plecarea unităţii 5
Q(t) graph B(t) graph
Time (Minutes) Interarrival times 1.73, 1.35, 0.71, 0.62, 14.28, 0.70, 15.52, 3.15, 1.76, 1.00, ... Service times 2.90, 1.76, 3.39, 4.52, 4.46, 4.36, 2.07, 3.36, 2.37, 5.38, ...
01
23
4
0 5 10 15 20
012
0 5 10 15 20
System
Clock 18.69
B(t) 1
Q(t) 0
Arrival times of custs. in queue ()
Event calendar [7, 19.39, Arr] [–, 20.00, End] [6, 23.05, Dep]
Number of completed waiting times in queue 6
Total of waiting times in queue 15.17
Area under Q(t) 15.17
Area under B(t) 17.03
t = 18.69, sosirea unităţii 6
6
Q(t) graph B(t) graph
Time (Minutes) Interarrival times 1.73, 1.35, 0.71, 0.62, 14.28, 0.70, 15.52, 3.15, 1.76, 1.00, ... Service times 2.90, 1.76, 3.39, 4.52, 4.46, 4.36, 2.07, 3.36, 2.37, 5.38, ...
01
23
4
0 5 10 15 20
012
0 5 10 15 20
System
Clock 19.39
B(t) 1
Q(t) 1
Arrival times of custs. in queue
(19.39)
Event calendar [–, 20.00, End] [6, 23.05, Dep] [8, 34.91, Arr]
Number of completed waiting times in queue 6
Total of waiting times in queue 15.17
Area under Q(t) 15.17
Area under B(t) 17.73
t = 19.39, sosirea unităţii 7
67
Q(t) graph B(t) graph
Time (Minutes) Interarrival times 1.73, 1.35, 0.71, 0.62, 14.28, 0.70, 15.52, 3.15, 1.76, 1.00, ... Service times 2.90, 1.76, 3.39, 4.52, 4.46, 4.36, 2.07, 3.36, 2.37, 5.38, ...
01
23
4
0 5 10 15 20
012
0 5 10 15 20
t = 20.00, sfârşitul simulării
67
System
Clock 20.00
B(t) 1
Q(t) 1
Arrival times of custs. in queue
(19.39)
Event calendar [6, 23.05, Dep] [8, 34.91, Arr]
Number of completed waiting times in queue 6
Total of waiting times in queue 15.17
Area under Q(t) 15.78
Area under B(t) 18.34
01
23
4
0 5 10 15 20
012
0 5 10 15 20
Q(t) graph B(t) graph
Time (Minutes) Interarrival times 1.73, 1.35, 0.71, 0.62, 14.28, 0.70, 15.52, 3.15, 1.76, 1.00, ... Service times 2.90, 1.76, 3.39, 4.52, 4.46, 4.36, 2.07, 3.36, 2.37, 5.38, ...
Timpul mediu de aşteptare in coada:
Media in timp a numărului de unităţi in coada:
Operaţii la sfârşitul simulării
min./unit. 53.2617.15
unitati Nr.decoadain totalTimpul
==
Media in timp a numărului de unităţi in coada:
Utilizarea serverului:
unitati 79.020
78.15ceas de finala Valoarea
)( curba sub de Aria==
tQ
92.020
34.18ceas de finala Valoarea
)( curba sub de Aria==
tB
Replicarea simulăriiValoarea unei singure simulări (“replicări”) nu este foarte
semnificativa dpdv statisticTabelul următor permite compararea a 5 replicări:
Se poate observa variabilitatea mare intre replicări
Modificarea parametrilorIn mod uzual, simularea se aplica in mod repetat nu doar prin simpla replicare, ci pentru diferite configuraţii ale modelului, cu parametri modificaţiIn acest fel se face acordarea si optimizarea modelului (după anumite criterii)modelului (după anumite criterii)Exemplu: ce se întâmpla daca se dublează rata sosirilor?n Datele de intrare se obţin prin înjumătăţirea timpilor
intre sosirin Se va relua execuţia modelului pentru configuraţia
modificatan Se vor executa 5 replici ale simulării
Modelarea sistemelor de calculModelarea sistemelor de calcul
Verificarea si validarea simularilor.
Curs, anul III Calculatoare
Verificarea si validarea simularilor. Analiza iesirilor
SumarCorectitudinea estimatorilor. Rolul etapelor de validare si verificareTipuri de estimatorin Estimatori (ne)balansatin Estimatori consistentin Estimatori consistentin Estimator interval si grad de incredere
Analiza iesirilor. Determinarea intervalelor de incredereClasificarea simularilorSimulari complete si de stare stabila
O practica uzualaSe construieste modelul, se executa simulareaSe obtin estimari ale masurilor de performanta relevante ale sistemului , de ex.n Timpul mediu in coada
Timpul mediu in sistemn Timpul mediu in sistemn Rata de iesire a clientilorn % clientilor ce asteapta in coada (eventual raportand
timpul de asteptare la o valoare prag), etc.Se utilizeaza aceste estimari pentru a se lua unele decizii, sau a se trage anumite concluzii privind sistemul
... Dar deficitara!Exista 2 probleme majore in aceasta abordare; pentru ca estimarile sunt si ele v.a., nu stim:n Cata incredere putem avea in ele si care este
eroarea maxima de obtinere a lor (pentru a o compara eventual cu eroarea admisibila)?compara eventual cu eroarea admisibila)?Principiu (foarte important in statistica!):“O estimare nu are valoare decat insotita de o indicatie asupra acuratetei estimarii“
n Cat de mare este influenta asupra estimarilor a comportarii initiale (tranzitorii) a sistemului, sicat de corecta este includerea acesteia?
Validare si verificareO simulare este valida daca modelul de simulare reprezinta cu acuratete sistemul realn Validarea raspunde la intrebarea “A fost construit
modelul adecvat?”O simulare este verificata daca programul de O simulare este verificata daca programul de simulare reprezinta translatia corecta a modelului (modelul programat)n Verificarea raspunde la intrebarea “A fost construit in
mod adecvat (corect) modelul?”Doar un model valid si verificat poate permite analiza diverselor scenarii de functionare (“what-if analysis”)
Iesiri deterministe si stochasticeSimularea este un instrument puternic, orientat dinamic, ce permite obtinerea unui set larg de rezultate (date de iesire)Pentru un model determinist, exista un set unic de date de iesire pentru fiecare set dat de date de date de iesire pentru fiecare set dat de date de intrare Pentru un model stochastic (si) datele de iesire sunt aleatoare, ele fiind deci doar estimari ale parametrilor reali ai sistemuluin De aceea o singura executie a unui model
stochastic nu este niciodata suficienta
Acuratetea estimariiPoate fi data sub forma:n unui prag (interval, probabilitate) de increderen erorii standard a estimarii (la randul ei o estimare
a deviatiei standard a estimarii)Estimarea erorii nu se poate face pe baza unei singure simulari (nu avem posibilitatea de a compara mai multe valori)Este necesara repetarea simularii si “replicarea” estimatorului
Estimatori si inferenta statisticaInferenta statistica este o metoda de analiza a unui sistem caracterizata prin utilizarea datelor experimentale ca baza a diferitelor concluziiUn estimator punctual al unui parametru sistem θ este un numar calculat pe baza datelor experimentale, notat Uneori termenul de estimator desemneaza statistica
θUneori termenul de estimator desemneaza statistica folosita pentru a calcula un rezultatDe exemplu:
arata atat ca estimatorul punctual al mediei unei populatii are valoarea 31.75, cat si ca acest estimator a fost calculat folosind media esantionului ca estimator
75.31ˆ == xµ
Estimatori si statisticiDualitatea terminologica se justifica prin aceea ca un estimator punctual este de obicei obtinut prin selectarea unei statistici adecvate si calculul unei valori pentru un set de date experimentaleDe exemplu,De exemplu,Ø statistica naturala pentru estimarea mediei
unei populatii, µ, este media esantionului de date,
Ø statistica naturala pentru estimarea variantei σ2 este varianta esantionului de date, s2
x
ExempluO metoda des folosita de biologi pentru estimarea unei populatii este un experiment de captura/recaptura; daca se doreste de ex. estimarea numarului de pesti dintr-un lac – parametrul de estimat este marimea populatiei, N:n Se captureaza mai intai un numar mic de pesti, de exemplu 100,
care se marcheaza si se elibereaza in laccare se marcheaza si se elibereaza in lacn Dupa un timp suficient pentru a permite pestilor marcati sa se
amestece cu ceilalti, se re-captureaza un numar mai mare de pesti, de exemplu 500
n Daca intre acestia se gasesc de ex. 20 marcati (adica 4%) este rezonabila estimarea ca 4% din totalul pestilor sunt marcati!?
n Aceasta sugereaza ca putem folosi 100:(4/100) = 2500 ca estimator punctual pentru marimea populatiei de pesti, N
Prin repetarea re-capturarii precizia metodei creste !Repetarea permite si estimarea erorii estimatorului
Tipuri de estimatori
Estimatori (ne)balansatiUn estimator al unui parametru θ s.n. nebalansatdaca:Altfel, s.n. balansat, iar cantitatea s.n. balansul lui θ (bias) Cele mai importante statistici (media, abaterea
θθµ
θ=ˆ
θ θµθ
−ˆ
Cele mai importante statistici (media, abatereapatratica medie s2) sunt estimatori nebalansatiO exceptie importanta este deviatia standard a esantionului, s - estimator “usor” balansat al deviatiei standardn Balansul este neglijabil pentru esantioane largin Pentru esantioane mici, poate fi aplicat un factor de
corectie
Estimatori consistentiDaca, prin cresterea marimii esantionului (n), n un estimator poate fi facut oricat de apropiat de un
parametru θn sau, echivalent, probabilitatea ca el sa fie oricat de
apropiat de parametru poate fi oricat de apropiata de 1
θ
apropiat de parametru poate fi oricat de apropiata de 1 s.n. estimator consistent al parametrului θ
Metoda cea mai simpla prin care se poate arataca un estimator este consistent este aceea de a arata ca eroarea standard descreste pe masurace marimea esantionului creste
θ
Eroarea standard (a mediei)E un estimator al deviatiei standard a distributieide esantionare asociate cu metoda de estimare(de obicei, distributia normala)
, unde: σ este deviatia standard a esantionuluin este marimea esantionuluinx
σσ =
n este marimea esantionuluiFormula se deduce usor:n Fie v.a. X1, X2, ..., Xn - n observatii independente dintr-o
populatie cu media μ si deviatia standard σ
n Atunci varianţa sumei T = (X1 + X2 + ... + Xn) este nσ2
n Varianţa mediei esantionului, T/n, este (1/n2). nσ2, de unde se deduce deviatia standard a lui T/n (radicalul)
n
Estimator interval si grad de incredere
Un estimator punctual, doar el, nu furnizeaza informatii despre precizia si gradul de incredere intr-o estimareAlternativa la raportarea unei singure valori (cea mai plauzibila) este de a calcula si furniza un interval in care se poate gasi parametrul estimat, cu un grad de incredere foarte mare, acesta se numesteincredere foarte mare, acesta se numesten Estimator interval, sau n Interval de incredere
Doar daca gradul de incredere (notat de obicei prin psau α) este mare (apropiat de 1, sau 100%) si intervalul rezultat este (destul de) ingust, in jurul mediei, precizia estimarii valorii parametrului este rezonabila
Determinarea intervalului de incredere (1)
Metoda, ilustrata pentru o populatie sau un proces cu media µ, se bazeaza pe o proprietate importanta a distributiei esantionateCand n este mare, distributia lui este aprox. normala (Teorema de limita centrala) si se poate
xx
normala (Teorema de limita centrala) si se poate standardiza prin
sau
tinand cont de faptul ca deviatia standard a populatiei sau procesului (σ) nu este cunoscuta si trebuie inlocuita prin cea a esantionului (s)
nxz
/σµ−
=ns
xz µ−=
Determinarea intervalului de incredere (2)
V.a. z are aproximativ o distributie normala standard
Cele mai folosite valori pentru pragul de incredere p (sau α) sunt 90%, 95%, si 99%, si ele conduc la obtinerea valorilor critice pentru z de1.645, 1.96, si respectiv 2.575
1.96From Wikipedia, the free encyclopedia
1.96 este valoarea aprox. a valorii percentile de 97.5% pentru distributia normale avand interpretarea: 95% din aria de sub curba normala se afla sub cca 1.96 deviatiistandard ale medieiPe baza teoremei de limitaPe baza teoremei de limitacentrala, acest numar poate fifolosit in constructia pragurilor(intervalelor) de incredere de 95% Ubicuitatea acestui parametru se datoreaza uneiconventii arbitrare dar comune de utilizare a intervalelorde 95% in dauna celor de 90% sau 99%
Comportare tranzitorie vs. permanenta
In simularea unui sistem putem fi interesati:n In estimarea parametrilor de performanta doar in
regim permanentw In acest caz nu este corecta includerea comportarii
tranzitorii a sistemului; includerea ei produce balansarea estimatorilor si trebuie aplicate corectii
n In estimarea parametrilor de performanta incluzand si regimul tranzitoriu al sistemuluiw In acest caz se considera influenta comportarii
tranzitorii a sistemului asupra estimatorilor
Simulare completa si de stare stabila
Distinctia intre cele 2 cazuri este caracterizata ca simulare completa, respectiv pentru stare stabila(“Terminating vs. Steady State Simulations”)Exista multe sisteme ce ar putea fi simulate atat complet, sau doar pentru starea stabilacomplet, sau doar pentru starea stabilaDecizia de a face simularea complet, sau doar pentru starea stabila, se ia pe baza:n tipului de sistem modelatn tipului de parametri ce sunt urmariti si ale
caror valori se vor obtine prin simulare
Clasificarea simularilor (dupa analiza iesirilor)
Simulari ce includ regimul tranzitoriu (complete)
Nu se doreste eliminarea regimurilor tranzitorii, deoarece sistemul nu ar fi opera corect fara eleExemplu:n Simularea activitatii unei banci, pentru a
determina numarul de personaldetermina numarul de personalw Banca deschide la 9, initial nu sunt clientiwOpereaza “normal” pana la ora 16w La ora 16 se inchid usile, nu se mai admit clienti in
banca; cei aflati inauntru isi termina operatiunile si parasesc banca
Simulare completaO simulare ce include regimul tranzitoriu, pentru care masurile dorite de performanta se definesc relativ la intervalul complet [0, TF], unde TF este momentul la care apare evenimentul final EF
T este de obicei variabila aleatoaren TF este de obicei variabila aleatoaren TF este predeterminat la inceputul simulariin Sau se specifica evenimentul final EF
Trebuie de asemenea definite conditiile initiale la momentul 0
Simulare de stare stabilaO simulare ce nu include regimul tranzitoriu si pentru care masurile dorite de performanta (de obicei formule derivate din variabilele de stare) se definesc ca limite pe masura ce lungimea simularii creste la infinitsimularii creste la infinitn Starea sistem este independenta de conditiile initialen Exista o perioada de “Warm-Up” initiala (posibil si o
perioada finala similara) - un interval de timp in care simularea progreseaza fara a se colecta date statistice
ATENTIE: Exista sisteme care nu ajung in starea stabila!
Analiza simularilor completeSe foloseste metoda replicarilor independente n Simularea se executa de un anumit numar de
ori, de fiecare data bazata pe:w un sir diferit de numere aleatoare (scos de acelasi
generator, samanta diferita)generator, samanta diferita)w conditii initiale diferite, independent alese
n Fiecare executie s.n. replicareIn mod tipic, caracteristicile si comportamentul de iesire al modelului difera mai mult in faza initiala decat in finalul simularilor replicate
Colectarea statisticilor intermediareDaca avem n replici ale simularilor, m observatii intermediare pentru fiecare simulare, fie:
xij = cea de j-a observatie din replica iyi = un parametru de performanta calculat in replica i
Atunci, pentru i=1,2,...n si j=1,2,...,m:Atunci, pentru i=1,2,...n si j=1,2,...,m:
Determinarea intervalelor de incredere
Aceste valori constituie estimatori nebalansati: n (si in plus independenti) ai mediei (valorii asteptate) si
dispersiei (abaterii patratice) la m momente diferiten ai mediei si dispersiei ca masuri globale de performanta
Desi nu putem concluziona ca seturile x si valorile Desi nu putem concluziona ca seturile xij si valorile yi sunt independente, putem determina intervale de incredere aproximative pentru E(xij) si E(yi) folosind:
ExempluSe considera un sistem M/M/1Se doreste ca prin simulare sa fie estimati urmatorii parametri:n Rata de utilizare a serverului, ρn Timpul mediu petrecut de un client in sistem, ωn Timpul mediu petrecut de un client in sistem, ω
Se executa patru simulari distincte (cu 4 fluxuri diferite de numere aleatoare) pentru a genera:n Timpii intre sosirin Timpii de servire
Rezultatele simularilor pentru aceeasi durata de timp sunt date de tabelul urmator:
Rezultate si prelucrariNr.executie (n) Utilizarea server
(ρn)Timp mediu in
sistem (ωn)1 0,808 3,74
2 0,875 4,532 0,875 4,53
3 0,708 3,84
4 0,842 3,98
•Sa se estimeze utilizarea serverului cu un interval de incredere dat (de ex., 95%)
•Sa se testeze daca utilizarea serverului verifica un prag standard dat (de exemplu, daca ρ≥0.9)
Concluzii (1)Simularile nu pot lua decizii: ele doar furnizeaza informatii si date ce pot ajuta pe cei ce iau deciziiDoar dupa validarea siverificarea ei, o simulare poate constitui baza luarii unor decizii corecten Validarea ne asigura ca modelul de simulare reprezinta cu n Validarea ne asigura ca modelul de simulare reprezinta cu
acuratete sistemul realn Verificarea ne asigura ca programul de simulare (modelul
programat) reprezinta translatia corecta a modelului de simulare
Simularea nu poate fi “mai buna” decat datele pe baza carora a fost construitaSimularile nu produc date sau valori reale ale parametrilor sistem, ci doar estimatori ai lor Estimatorii sunt variabile aleatoare
Concluzii (2)Pentru a putea lua decizii valide trebuie sa stim si:n care este acuratetea estimatorilorn care sunt tipurile de estimatori ce pot fi folositi
Cele mai importante statistici (media, abaterea patratica medie s2) sunt estimatori nebalansatimedie s ) sunt estimatori nebalansatiAsigurarea preciziei reprezentarii datelor se face prin metode statistice: erori standard, intervale de incredere, replicari independente ale simularii n Determinarea intervalelor de incredere se bazeaza pe apropierea
distributiei esantionate a mediilor de distributia normala (n mare)n Estimarea acuratetei unei simulari necesita date obtinute din
cateva repetari (replici) ale simularii
Concluzii (3)In simularea unui sistem putem fi interesati:n In estimarea parametrilor de performanta doar in regim
permanent; in acest caz nu este corecta includerea comportarii tranzitorii a sistemului, ce ar produce balansarea estimatorilor
n In estimarea parametrilor de performanta incluzand si regimul tranzitoriu al sistemului, caz in care se considera influenta comportarii tranzitorii a sistemului asupra estimatorilor
Decizia de a face simularea doar pentru starea stabila sau completa se ia pe baza:n tipului de sistem modelat
n tipului de parametri ce sunt urmariti si ale caror valori se vor obtine prin simulare
Modelarea sistemelor de calculModelarea sistemelor de calcul
Accelerarea execu iei simulărilor.
Curs, anul III Calculatoare
Accelerarea execu iei simulărilor. Simularea paralelă (distribuită)
SumarCaracteristici și dificultățiNivele de paralelism/ distribuţie în simulareSimularea paralelă prin interacţiunea proceselor. Partajarea domeniului spaţiu-timp între PLProblema timpului simulăriiAbordări conservative și optimisteConcluzii
ProblemaPentru a fi semnificativă statistic, o simulare de SDED trebuie să fie lungă sau repetatăSimulările secvenţiale, uneori repetate, durează aproape întotdeauna prea multProblema reducerii timpului de execuţie, se poate soluţiona pe două căi:n prin paralelizare sau distribuţia sarcinilor de
prelucrare, vizând execuţia simultană a unora dintre ele şi pe ansamblu scăderea timpului de simulare;
n prin utilizarea metodelor statistice pentru reducerea duratei sau numărului de simulări necesare.
Argumente pt. paralelizarea (distribuția) prelucrărilor
Multe sisteme constau din subsisteme "operând" în paralel → paralelismul inerent unui sistem poate fi exploatat prin simularea sa paralelăExecuţii independente ale simulării sunt necesare dpdv statistic şi acest lucru poate fi făcut în mod dpdv statistic şi acest lucru poate fi făcut în mod eficient în paralelUnele sarcini ale simulării, precum colectarea statisticilor cumulative, sunt independente şi pot avea loc în paralel în raport cu celelalte sarcini,
etc.
DificultăţiSimularea paralelă este o aplicaţie cu paralelism neregulat, cu grad mare de dependenţă între date, grad redus de similitudine a operaţiilor şi asincronism
n spre deosebire de alte aplicaţii uşor paralelizabile ce se caracterizează prin regularitate (problemele numerice caracterizează prin regularitate (problemele numerice ce implică structuri de date mari de tip matricial)
În simularea paralelă (distribuită), deşi se pot pune în evidenţă relativ uşor componente distincte ale modelului de simulare, există interacţiuni şi deci interdependenţe.
n spre deosebire de prelucrarea în ordine strictă a evenimentelor în relaţie cauzală din simularea secvenţială - o aplicaţie cu o bază formală solidă!
Exemplu Există (şi) în simularea secvenţială a SDED situaţii în care LEV conţine în primele sale poziţii mai multe evenimente având asociate momente de timp identice
Trebuie făcută însă distincţia între:a) evenimente ce au (potenţial) acelaşi timp de apariţie a) evenimente ce au (potenţial) acelaşi timp de apariţie dar se exclud reciproc din punct de vedere logic (apariţia unuia dintre ele anulează apariţia celorlalte) şi deci nu pot fi practic simultane – evenimente mutual exclusiveb) evenimente ce au acelaşi timp de apariţie, dar apariţia unuia dintre ele poate modifica (decala, întârzia) apariţia celorlalte - evenimente intercondiţionatec) evenimente ce au acelaşi timp de apariţie dar execuţii independente una de alta - evenimente concurente
Nivele de paralelism/ distribuţie în cadrul unei simulări (1)La nivelul aplicaţiei:
Copii (replici) independente ale aceluiaşi model, cu parametri de intrare diferiţi, se execută pe diferite procesoare; nu este necesară nici un fel de coordonare sau sincronizare între procesoare în timpul simulării, ceee ce permite un înalt nivel de eficienţăTotodată codul secvenţial al programului de simulare poate fi reutilizat, evitându-se astfel o paralelizare costisitoare a programului
Nu există limitări importante în scalabilitatea rezolvării unei asemenea probleme compuse din mai multe experimente de simulare (mărirea numărului de procesoare)
Totuși, este posibil ca uneori o singură execuţie a unei simulări lungi, echivalentă cu mai multe execuţii scurte, să fie preferabilă din motive legate de incapacitatea sistemului simulat de a-şi atinge rapid starea de echilibru
Nivele de paralelism/ distribuţie în cadrul unei simulări (2)La nivelul componentelor (srutinelor) programului:
Pot fi programate pentru execuţia paralelă o serie de sarcini independente în cadrul unei simulări, precum generarea numerelor aleatoare, tratarea evenimentelor, colectarea statisticilor cumulative, manipularea i/e şi a colectarea statisticilor cumulative, manipularea i/e şi a fişierelor, generarea de rapoarte grafice etc. Datorită numărului relativ mic de sarcini independente în cadrul unei simulări, scalabilitatea şi deci accelerarea sunt limitate în acest caz S-au raportat rezultate bune în privinţa eficienţei simulărilor (45-60%) atunci când numărul de procesoare rămâne mic (3-5), aceasta scăzând însă rapid cu creşterea numărului de procesoare.
Nivele de paralelism/ distribuţie în cadrul unei simulări (3)La nivelul componentelor sistemului fizic modelat:
În modelul de simulare pot fi evidenţiate sub-modele Pentru sistemele fizice cu topologie fixă, ca de exemplu reţelele de cozi, modalitatea naturală de decompoziţie constă în asignarea unui proces pentru fiecare server constă în asignarea unui proces pentru fiecare server (împreună cu coada aferentă), modelând deplasarea clienţilor în reţea prin mesaje între proceseÎn simularea unui sistem cu topologie dinamică, ca de ex. un joc de biliard sau un scenariu militar, procesele pot reprezenta componentele ce interacţionează, iar mesajele între procese chiar aceste interacţiuni
Nivele de paralelism/ distribuţie în cadrul unei simulări (3)La nivelul componentelor sistemului fizic (cont.):
Pot fi programate pentru execuţia paralelă o serie de sarcini independente în cadrul unei simulări, precum generarea numerelor aleatoare, tratarea evenimentelor, colectarea statisticilor cumulative, manipularea i/e şi a colectarea statisticilor cumulative, manipularea i/e şi a fişierelor, generarea de rapoarte grafice etc. Datorită numărului relativ mic de sarcini independente în cadrul unei simulări, scalabilitatea şi deci accelerarea sunt limitate în acest caz S-au raportat rezultate bune în privinţa eficienţei simulărilor (45-60%) atunci când numărul de procesoare rămâne mic (3-5), aceasta scăzând însă rapid cu creşterea numărului de procesoare.
Nivele de paralelism/ distribuţie în cadrul unei simulări (4)La nivelul evenimentelor în cazul menţinerii LEV centralizate:
Gestionarea LEV este asigurată de către un procesor master, accelerarea poate fi atinsă prin distribuirea evenimentelor simultane către o mulţime de procesoare slave în vederea execuţiei concurenteslave în vederea execuţiei concurenteSarcina păstrării consistenţei în structura evenimentelor revine procesorului master ce trebuie să prevină execuţia distribuită a evenimentelor simultane (mutual exclusive sau intercondiţionate) cu potenţial efect de violare a cauzalităţii în LEVAceastă posibilitate este adecvată pentru execuţia pe o maşină multiprocesor cu memorie partajată unde LEV poate fi implementată printr-o structură de date comună
Nivele de paralelism/ distribuţie în cadrul unei simulări (5)La nivelul evenimentelor în cazul menţinerii descentralizate
a LEV:
se menţin mai multe sub-liste cf. unei împărţiri pe grupe de evenimente (pt. asignări regulate a evenimentelor la procesoare, fiind posibilă şi o asignare nestructurată)procesoare, fiind posibilă şi o asignare nestructurată)este de aşteptat obţinerea unor viteze de simulare mult mai mari datorită faptului că se permite execuţia concurentă a evenimentelor cu timpii asociaţi diferiţischemele de implementare a paralelismului /distribuţiei la acest nivel necesită protocoale pentru sincronizare locală, ce pot creşte costurile de comunicaţie, în funcţie de dispersia evenimentelor în spaţiu (între procesoare) şi timp în cadrul modelului de simulare
Simularea paralelă/distribuită prin interacţiunea proceselor
Poate fi privită ca o partajare a domeniului spaţiu - timp între procesele logice
Modalităţi de simulare paralelă: a) spaţială; b) temporală
var. var. var.
stare
timp
var. stare
timp
Principii generale (1)Este necesară mai întâi identificarea şi implementarea unui set de procese logice (PL), capabile să trateze în paralel apariţia diferitelor evenimenteTrebuie creat și un sistem de comunicaţie (SC), care să asigure PL posibilitatea de a schimba date locale, dar şi asigure PL posibilitatea de a schimba date locale, dar şi de a-şi sincroniza activităţile localeFiecărui PLi i se alocă o regiune Ri a domeniului spaţiu -timp, ca sub-model sau parte a modelului de simulare; în cadrul regiunii Ri, o implementare a PLi operează secvenţial:
n planifică şi execută evenimente localen generează evenimente locale sau pentru alte PLn avansează un ceas de simulare local etc.
Principii generale (2)Fiecare PLi poate avea acces doar la un subset partiţionat static de variabile de stare Si ⊂ S, în general disjunct faţă de variabilele de stare asignate altor PL;În fiecare PLi pot fi procesate două tipuri de evenimente:n interne, ce pot afecta cauzal doar Si ;n interne, ce pot afecta cauzal doar Si ;n externe, ce pot afecta cauzal şi alte subseturi Sj ⊂ S (i≠j);
O interfaţă de comunicare (IC) ataşată unui PL, compusă din canale de intrare/ieşire ale unui PL, are rol de urmărire a efectelor evenimentelor, atât externe generate asupra altora, cât şi externe generate de alte PL asupra luiMecanismul de bază al IC este trimiterea, primirea şi prelucrarea de mesaje eveniment având înglobat un marcaj desemnând timpul local de emitere (timestamp).
Partajarea domeniului spaţiu-timp între PLi
Spaţial: modelul este împărţit între procesoare, iar fiecare dintre acestea avansează simultan în timp cu celelalte în simularea unei componente a modelului stocată localn Problema sincronizării: constrângerea de cauzalitate locală
impune ca procesarea evenimentelor de către un PL să se facă în ordinea crescătoare a timpilor asociaţi fiecărui eveniment în PL
Temporal: intervalul de timp al simulării e împărţit în subintervale, fiecare dintre procesoare realizând simularea într-un subinterval a întregului model
Timpul (virtual al) simulării
Simularea sincronă implementează timpul virtual printr-un ceas de timp global: n fie reprezentat explicit, central, printr-o structură de date n fie implicit într-o procedură ce se execută în paşi
Caracteristic este faptul că toate PL, la fiecare moment Caracteristic este faptul că toate PL, la fiecare moment de timp real, se conduc după valori de timp identice Simularea asincronă relaxează total restricţia de sincronizare: n fiecare PL se conduce după valori proprii ale ceasului de
timp virtual (local) n deci la un moment dat al timpului real, timpul local virtual
în diferitele PL este diferit
Abordări asincrone (1)Conservativă : execuţia unui eveniment în fiecare PL are loc d.d. se respectă strict regula de cauzalitate locală De ex., un criteriu suficient, nu şi necesar, de procesare a evenimentului iminent într-un PL, este ca valoarea ceasului de simulare asociat PL să fie mai mică decât toţi ceasului de simulare asociat PL să fie mai mică decât toţi timpii asociaţi celorlalte PL Metodele conservative au caracteristic faptul că evită ab initio orice eroare datorată nerespectării cauzalităţii Un eveniment E dintr-un PL este tratat numai dacă există certitudinea că orice eveniment viitor Ev, generat de PL respectiv sau primit printr-un canal de intrare de la alt PL, nu va anula corectitudinea rezultatelor obţinute prin tratarea evenimentului E
Abordări asincrone (2)Optimistă: un PL poate procesa evenimentul iminent din LEV locală, fără a se asigura de respectarea strictă a constrângerii de cauzalitate locală În acelaşi timp, un istoric al simulării este păstratDacă se constată ulterior încălcarea constrângerii de Dacă se constată ulterior încălcarea constrângerii de cauzalitate locală (de exemplu, PL respectiv primeşte ca urmare a activităţii altor procese un eveniment cu timpul virtual asociat mai mic decât ceasul local al simulării), PL trebuie să poată reveni şi reface în mod corect simularea din punctul în care a apărut problema
Comparaţie între protocoaleleconservative şi optimiste (1)
Cel mai mare dezavantaj al simulărilor conservative este că nu exploatează complet paralelismul sistemului: n dacă există cea mai mică posibilitate ca un eveniment E1 să
afecteze un alt eveniment E2, simularea conservativă este practic o execuţie cvasisecvenţialăo abordare conservativă se dovedeşte a fi excesiv de defetistă, n o abordare conservativă se dovedeşte a fi excesiv de defetistă, prin plasarea întotdeauna în cea mai nefavorabilă situaţie.
O problemă este și întoarcerea, către metodele de simulare condusă de timp, prin avansul ceasurilor de timp locale în incremenţi mici (pt.evitarea interblocajelor) Pentru a determina dacă un mesaj poate fi tratat de o manieră sigură, metodele conservative se bazează profund pe structura sistemului de simulat (dacă există mai mult de o singură intrare viteza simulării scade rapid)
Comparaţie între protocoaleleconservative şi optimiste (2)
În cazul aplicării mecanismului optimist (time warp), ptr. cazul anumitor sisteme, timpul unei simulări poate fi consumat mai mult în efectuarea de calcule incorecte şi reveniri (roll-backs) neproductive Necesitatea salvării periodice a stării sistemului pentru a Necesitatea salvării periodice a stării sistemului pentru a putea face recuperarea unei erori, cere şi timp şi mai ales spaţiu de memorie, iar această informaţie de stare nu este întotdeauna utilizată Implementarea sa este mai complicată, algoritmii fiind şi foarte dificil de validat Chiar o implementare corectă poate avea performanţe foarte slabe dacă programarea nu s-a făcut suficient de atent ţinând cont de anumite caracteristici ale sistemului
Criteriu Metode conservative Metode optimiste
Principiuoperaţional.
Regulile de cauzalitate locală sunt strict respectate;sunt tratate doar evenimentele sigure.
Este posibilă violarea temporară a regulilor de cauzalitate locală, dar la detectarea unei erori de acest fel se revine.
Spaţiul stărilor.
Utilizarea tuturor modelelor conservative este compatibilă cu modele de simulare având spaţii
Sunt eficiente atunci când, în model, spaţiul stărilor şi necesa- rul de spaţiu de modele de simulare având spaţii
de stări arbitrar de mari.necesa- rul de spaţiu de memorie per stare sunt mici.
Consumul dememorie.
Conservativ, consecinţă a metodei aplicate, dar nu optimal [Jef85].
Excesiv, datorită overhead-ului necesar pentru salvarea stărilor. Sunt necesare scheme complexe de administrare a memoriei pt.a preveni epuizarea memoriei.
Reprezentarea timpului
Se execută implicit în TGV; nu sunt necesare calcule explicite legate de TGV.
Se bazează pe calculul explicit şi dificil (fără suport hardware) al TGV.
Exploatareparalelism
Paralelismul sistemului nu este bine exploatat; dacă apar rar constrângeri cauzale, protocolul este prea pesimist.
Paralelismul sistemului este bine exploatat; dacă constrângerile cauzale apar rar, protocolul aduce câştiguri de timp
Sincronizarea.
Mecanismul de sincronizare este interblocant; consecinţe:
Mecanismul sincronizării este recuperatoriu; deci. interblocant; consecinţe:
-prevenirea interblocajelor bazată pe mesaje nule adaugă overhead de comunicare;-detectarea/elim.interblocajelor pp. de obicei un proces central;-programatorul trebuie să fie familiarizat cu mecanismele de sincronizare pentru a obţine performanţe de vârf.
este recuperatoriu; deci-anulările introduc de asemenea un overhead de comunicare;-programatorul nu trebuie să fie familiarizat cu mecanismele de sincronizare; -recuperarea în lanţ degradează puternic performanţele.
Comunicaţia.
În general intensă. E necesară sosirea şi procesarea în ordine cronologică a mesajelor, stricta separare a canalelor de intrare.
Nu foarte intensă. Mesajele pot veni în orice ordine, dar trebuie executate în ordine cronologică; se poate menţine o singură coadă de intrare; nu e nevoie ca mesajele să fie primite în ordinea în care au fost trimise.care au fost trimise.
Configurare Majoritatea tehnicilor necesită interconectarea statică a proceselor.
Admit configurarea dinamică a proceselor.
Lookahead-prospectare
Necesar pentru a face operabil protocolul, esenţial pentru performanţă.
Nu este esenţial, dar poate fi utilizat pentru optimizarea performanţelor.
Balansareaîncărcărilor.
Bună, cât timp toate canalele statice sunt utilizate egal; dis-persia mare a evenimentelor în timp şi spaţiu nu deranjează.
Bună, cât timp progresia TLV este apropiată între PL;dispersia mare a evenimentelor în timp şi spaţiu degradează performanţa.
Agresivitate. Redusă. Ridicată.
Risc. Nu există. Potenţial ridicat, dar poate fi redus prin aplicarea fi redus prin aplicarea unor tehnici specifice [Lub89].
Overhead (sarcină suplimentară)
Introdus mai ales de mecanismele de detectare şi recuperare a deadlock-ului.
Introdus mai ales de mecanismele de salvare a stării şi rollback.
Granularitate Poate fi mare (fină). Mărirea ei poate conduce la mărirea raportului overhead/calcul
Suport hardware.
Nu este obligatoriu. De dorit, nu atât pentru calcule, cât pentru salvarea stării/ detecţia erorilor (“rollback chip”).
Implementare.
Uşor de implementat; structuri de control şi de date simple.
Dificil de implementat şi depanat; structuri de date simple,dar manipulări şi structuri de control complexe. E esenţială complexe. E esenţială organizarea memoriei. Se pot face optimizări ce influenţează performanţa.
Preprocesarea.
Este necesară pentru a evita creşterea overheadului de comunicaţie.
Nu este necesară, procesele rulează relativ independent, comunică şi se sincronizează rar.
Detecţia erorilor şi recuperarea lor.
Erori puţine şi detectabile. Erori frecvente, dificil de detectat (pot fi şterse prin rollback) fără ajutorul suportului hardware pentru întreruperi şi protecţia memoriei.
Depanarea. Relativ uşor de realizat. Consumatoare de timp şi dificilă, pentru că implică analiza detaliată a unor scenarii complexe de scenarii complexe de rollback.
Robusteţe. Schimbări minore ale aplicaţiei pot avea efecte catastrofice asupra performanţei.
Comportarea este stabilă; automat, sistemele TW tind să încetinească propagarea erorilor, prin acordarea de priorităţi mai mari calculelor ce implică evenimente cu timp mai mic.
ConcluziiProblema “paralelizării” simulărilor nu este deloc o problemă trivială Indiferent ce componentă a simulatorului considerăm, descompunerea şi exec. în paralel trebuie analizată atentn pe de o parte sub aspectul eliminării unor probleme n pe de o parte sub aspectul eliminării unor probleme
de inconsistenţă/ greşeli de simulare n pe de altă parte în vederea obţinerii unei accelerări
semnificative faţă de tratarea secvenţială