All Coursesas [PDF]

Zitiervorschau

Modelarea sistemelor de calcul Curs, anul III Calculatoare Instructori: Prof.dr.ing. Mihai Mocanu Conf.dr.ing.Ileana Nicolae E-mail: [email protected] Ore curs: Joi 16:00-18:00 Ore consultatie (la cerere): Joi 14:00-16:00 Pagina curs: http://software.ucv.ro/~mocanu_mihai/

(pe intrarea corespunzătoare cursului, introduceţi user/pasw)

Obiectul cursului Domeniul distinct de studiu/cercetare al modelarii si simularii (M&S) face parte din zona disciplinelor ingineresti generale (management ingineresc) n

Termenii “modelare” si “simulare” sunt deseori utilizati alternativ → conceptualizarea si implementarea (M&S) sunt activitati mutual dependente – ce pot fi conduse insa 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, simulatoare etc, fie static sau in timp, pentru a dezvolta date si a le folosi apoi ca baza pentru luarea unor decizii (tehnice sau manageriale)”

Locul cursului Mathematics Operations Research*

Physics

Control Theory

Software Engineering Artificial Intelligence

Numerical and Symbolic Computation

Modeling & Simulation

Graphics & Visualization

Computer Science Systems Engineering

Zone de cunostinte conexe

Fundamente necesare Programarea calculatoarelor Tehnici de programare Metode numerice Algoritmi şi structuri de date Teoria generală a sistemelor dinamice Teoria probabilităţilor şi statistica matematică Programarea orientată pe obiecte Medii de programare vizuală

Obiective Introducerea 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 cozi Introducerea tehnicilor de modelare, simulare şi analiza performantelor pentru sisteme cu evenimente discrete complexe Identificarea posibilităţilor şi limitărilor modelelor matematice, extinderea lor prin simulare Utilizarea unor pachete şi biblioteci de programe specializate pentru modelare şi simulare Dezvoltarea abilităţilor de modelare/ simulare a unui sistem nu doar prin exerciţii şi probleme, ci şi prin realizarea unui proiect

Structura cursului Modelarea analitică a sistemelor discrete Probabilităţi şi procese aleatoare (review) Teoria elementară a cozilor de aşteptare Reţele de cozi de aşteptare Reţele Petri Tehnici de aproximare Modele de simulare pentru SED Limbaje si medii de simulare Topici avansate n n

Simularea paralelă si distribuită Analiza perturbaţiilor

Conţinutul cursului pe larg Sisteme dinamice n

Sisteme cu evenimente discrete (SED, SDED)

Modelarea analitică a SED n n n n

Categorii de modele şi nivele de studiu Modele algebrice şi logice Modele dinamice: reţele Petri Modele temporale: reţele Petri temporizate

Modelarea operaţională a SED n n n n

Statistica in modelare Lanţuri şi procese Markov şi semi-Markov generalizate Formalismul GSMP ca bază a modelelor de simulare Sisteme cu cozi de aşteptare şi reţele de cozi

Conţinutul cursului (cont.) Modele de simulare pentru SED n n n n

Generarea numerelor şi variabilelor aleatoare Construcţia şi verificarea modelului de simulare Execuţia secvenţiala şi analiza simulărilor (ieşirilor) Validarea simulărilor. Estimatori şi inferenţa statistica

Limbaje şi medii de simulare n n n

Limbaje de simulare Construcţia unui simulator. Biblioteci de componente Metode de accelerare a execuţiei simulărilor: simularea paralela (distribuita), tehnici de gradient

Aplicaţii ale modelarii şi simulării pentru: n n n

Sisteme cu cozi de aşteptare şi reţele de cozi Sisteme de calcul şi reţele de calculatoare Sisteme şi reţele de comunicaţii

Referințe bibliografice Banks J., Carson J.S., Nelson A., Nicol D., Discrete-Event System Simulation, 3rd Ed., Prentice-Hall, 2000 Cassandras C.G., Discrete Event Systems: Modeling and Performance Analysis, Irwin & Aksen, Boston, 1993 Lazowska E.D., Zahorjan J., Scott-Graham G., Sevcik K. C.: Quantitative System Performance - Computer System Analysis Using Queueing Network Models, 1984 Sadiku M., Ilyas M.: Simulation of Local Area Networks, CRC Press, 1995 Mocanu M., Principii, concepte şi instrumente de modelare şi simulare in studiul sistemelor dinamice discrete, Ed. Sitech, 2004

Notarea Se 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) 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 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: n n

n

un sistem constă din “componente” in interacţiune un sistem este complet descris de “funcţia” asociată, pe care o îndeplineşte prezumptiv [Cas93] 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; 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ăsurabile variabile 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) = [u1(t), u2(t), ..., um(t)]T y(t) = [y1(t), y2(t), ..., yn(t)]T Modelul matematic general al sistemului, din punct de vedere 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ţiile funcţionale intrare-ieşire pe care le putem construi sunt descrise simplu prin ecuaţii algebrice, in care ieşirea y(t) este, pentru orice t, independenta de valorile trecute ale intrării u(τ), τu)| Y(t)=i} = e-λ(i)u, unde u>0, iar λ(i) e rata de tranziţie a stării i 2) 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: 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ţii Proprietatea 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 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 GSMP Un 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 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ţii Un 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 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 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ării Secvenţ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ătoare Fiecare eveniment are asociată şi propria sa distribuţie 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: n

n

pe de o parte, prin specificarea modului de generare a componentelor structurii temporale, pe baza distribuţiilor Φ 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: n n n n n n

X – mulţimea stărilor (cel mult numărabilă) E – mulţimea evenimentelor (numărabilă) Γ(x) – mulţimea evenimentelor active în starea x (Γ(x)⊆E) P : X×X×E → [0,1] - funcţia de probabilitate a tranziţiilor de stare p0(x) – setul de probabilităţi asociate stării iniţiale x0, p0(x)= p(x0=x); C={Ce, e∈E} - structură temporală stochastică, fiecare componentă a sa fiind o v.a. distribuită după o anumită lege Φe

Observaţii Un automat de stare stochastic se obţine prin extensia multiplă a unui automat de stare temporal n 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 probabilistic Un 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 GSMP Mecanismul de alegere al evenimentului declanşator e’ este identic cu cel pentru automatul de stare temporal

e '= arg min {re }; e∈Γ ( x )

re fiind timpii reziduali rezultaţi din structura temporală stochastică C={Ce, e∈E}. Calculul noilor timpi reziduali se poate face dacă: r * = min re e∈Γ ( x ) şi are în vedere doar cazul neintreruptibilităţii evenimentelor nedeclanşate:

re ' = next ( c e ' ); re = re − r *, e ≠ e '.

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 şi defineşte un GSMP

Modelarea sistemelor de calcul Curs, anul III Calculatoare

Sisteme cu cozi de aşteptare şi reţele de cozi

Sumar Modelarea analitică a sistemelor şi reţelelor de aşteptare. Notaţia Kendall generalizată Notaţia Kendall simplificată Legea lui Little Comportare tranzitorie şi permanentă (staţionară, de echilibru statistic) Probabilităţi de tranziţie şi de stare Măsuri de performanţă la echilibru statistic

Sisteme cu cozi de aşteptare Caracterizează 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 anumita disciplina (o regula), care precizează: n n n

modul de formare a cozii modul de comportare a unităţilor care aşteaptă ordinea de servire a unităţilor

staţia (staţiile) de servire n

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) C - numărul de staţii (servere) in sistem D - disciplina de servire din partea staţiilor E - 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/m A - tipul distribuţiei de intrare (distribuţia timpilor intre sosiri) B - tipul distribuţiei de servire (distribuţia timpilor de serviciu) k - numărul de staţii (servere) in sistem m - 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 uniforma Ek - o distribuţie Erlang cu k nivele Hh - o distribuţie hiperexponenţială cu h nivele G sau GI - o distribuţie generală D - o distribuţie deterministă …

Disciplina de servire FIFO (FCFS): unităţile sunt servite in ordinea sosirii in sistem LIFO (LCFS): unităţile sunt servite in ordinea inversa sosirii in sistem SIRO: unităţile sunt servite in ordine aleatoare SPT: 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

n

Non-preemptive: o unitate aflata in curs de servire nu poate fi întrerupta 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 Poisson sunt procese stochastice {A(t)│t≥0} cu valori pozitive, discrete în timp presupunerile (postulatele) pe care se bazează teoria acestor procese stochastice (si dezvoltarea formulei distribuţionale Poisson) sunt minimale si conforme cu realitatea experimentala Exemplu: un proces de numărare a sosirilor întrun sistem de aşteptare - atunci când sosirile au loc pe rând si sunt independente)

Postulatele Poisson 1. Î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) = λ•Δt 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 întrun 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 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) / Δt Rezulta prin trecerea la limita cu Δt →0 ecuaţia diferenţiala (cu condiţie iniţiala) P'0(t) = -λ·P0(t), P0(0)=1, cu soluţia P0(t) = e-λt Probabilitatea ca în cele doua intervale succesive sa înregistram una sau mai multe sosiri (n>0): n

P n (t + ∆ t)= P n (t) • P 0 ( ∆ t)+ P n -1(t) • P 1( ∆ t)+ ∑ P n - k (t) • P k ( ∆ t) k=2

= P n(t) •(1 - λ • ∆ t - o( ∆ t))+ P n -1(t) • λ • ∆ t + o( ∆ t)

Distribuţia Poisson: soluţia P n′'(t) = -λ P n(t)+ λ P n-1(t), P 0 (0) = 1, P n(0) = 0 pentru n > 0.

Soluţia acestei ecuaţii diferenţiale este distribuţia Poisson generala de parametru λ:

( λt ) e- λt , P n (t) = 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+xt>T)=1-e-λx, având media 1/λ si dispersia 1/λ2 (un proces Poisson de sosire are o distribuţie exponenţiala pentru timpii între sosiri). B. Probabilitatea de a avea o singura sosire în sistem într-un interval de 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:

( λ t )n e - λ t , P n (t) = n!

obţinuta prin rezolvarea ecuaţiei diferenţiale

dP n (t) = - λ P n + λ P n -1 dt

Descompunerea si compunerea proceselor Poisson Daca un proces Poisson cu media λ, X=A(t), t≥0, consta din evenimente 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ăra apariţiile pt. cele 2 tipuri de evenimente, sunt procese Poisson independente, cu media λ⋅p, respectiv λ⋅(1-p). Daca X1=A1(t) si X2=A2(t) sunt procese Poisson cu media λ1, respectiv λ2, atunci si X=A(t)=A1(t)+A2(t) constituie un proces Poisson cu media λ=λ1+λ2.

λp

λ

λ λ(1-p)

λ λ λ

Indicatori de performanta numă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 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 T 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

∫ N( τ 0

t

lim t →∞

∫ N(τ )dτ 0

t

)d τ = ( ∑ T i ) - ε s(t)

i=1

t

∫ N(τ )dτ

= lim 0

s(t )

t →∞

• lim t →∞

s(t) ε ε - lim ; dar lim = 0. t t →∞ t t →∞ t

t

N = lim t→∞

∫ N( τ ) dτ 0

t

s(t)

;

λ= lim t→∞

s(t) ; t

T = lim t→∞

∑T i= 1

s(t)

i

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 aşteptare, înaintea prelucrării sau transmiterii timpul 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 < 2S Rezulta ca: Timpii de prelucrare P si transmitere kS sunt singurii relevanţi, deoarece, datorita capacitaţii de prelucrare si transmisie asincrona a serverului, mesajele nu aşteaptă! Timpul sistem al fiecarui mesaj este acelaşi, egal si cu media 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ţi în n sistem, N(t) - de fapt N(t) nu converge, deoarece sistemul nu atinge o stare de echilibru statistic! Totuşi, aplicarea legii lui Little este riguroasa prin interpretarea lui N ca valoare fixa a mediei temporale a numărului de unitati în sistem, determinat la momente discrete de timp, în timp (foarte lung): k

1 N = lim ∫ N (t)dt k →∞ k 0

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 oricărui utilizator ce încheie un task T 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 Little Intre punctele A si C: λ = N/T 0 ≤ D ≤ (N-1)•P ⇒ G+P ≤ T ≤ G+N•P ⇒

N N ≤λ ≤ G+N ⋅ P G+P

Intre punctele B si C (intrarea si iesirea serverului): N 1 N ≤ λ ≤ min{ , } G+ N ⋅ P P G+P (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:

max{N ⋅ P,G + P} ≤ T ≤ G + N ⋅ P

Variaţia ratei de prelucrare λ

Variaţia timpului sistem mediu pentru un utilizator

Discuţie Când N creste: n n

rata de ieşire tinde spre valoarea maxima 1/P timpul mediu de aşteptare pentru un utilizator creste proporţional

Rata de ieşire maximala depinde de parametriisistem ca: n n

proporţia între timpii de pregătire si de execuţie disciplina de servire

Limitele obţinute nu depind de parametriisistem

Interpretări Cât timp N1+G/P, puterea de procesare a serverului este cea care determina blocajul

Reţele de cozi de aşteptare O 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 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 n

sosiri în sistem ale unităţilor din exterior (de obicei modelate ca procese Poisson) parasiri ale sistemului de către clienţi după efectuarea unor servicii

Reţele închise n n

fiecare client circula între servere, pentru serviri, fara a părăsi sistemul; din exterior nu pot intra noi clienţi în sistem, deci numărul total de clienţi este o constanta sistem

Reţele mixte n

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

n

Pentru reţelele deschise ⇒ independenta distribuţiilor staţionare ale cozilor individuale (distribuţia staţionara e produsul distribuţiilor individuale ce se obţin prin analiza separata a fiecărei cozi considerând o rata de sosire adecvata, modificata, ce reflecta modalitatea de dirijare în reţea) Pentru reţelele închise ⇒ dependenta dintre cozi poate fi capturata prin normalizarea soluţiei independente peste un spaţiu de stare normalizat; în acest caz, pot apare dificultati computaţionale în calculul constantei de normalizare

Reţele Jackson deschise Caracteristici: M staţii de servire (cu server unic), fiecare având un buffer de capacitate infinita Sosirile din exterior ale clienţilor la fiecare staţie i dintre cele 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 : M

q i,0 = 1 - ∑ q i, j j=1

Ecuaţii de flux Daca: n

n

timpul de [de]servire al serverului i este exponenţial distribuit cu media si=1/μi λi este rata de sosire medie a clienţilor la serverul i (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: M

λ i = λ 0,i + ∑ λ j • qi, j , i = 1,2,..., M j=1

Reţele Gordon-Newell închise Caracteristici: 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) Daca notam starea sistem cu n=(n1,n2,...nM), unde ni e numărul de clienţi în bufferul serverului i: M

∑n= N i

i=1

Modelarea sistemelor de calcul 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 real urmarirea evolutiei dinamice a sistemului evaluarea unor strategii de operare

Modelare și simulare Model: o reprezentare a unui sistem n

n

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 cu un set unic de ieșiri - Stochastice: una sau mai multe intrări sunt v.a., fapt ce determină ieșiri aleatoare Modelele fizice, constructive

Modelare: procesul de construire a unui model Simulare: 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-Carlo 1. Se definește un domeniu al intrărilor posibile 2. 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ări 4. 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 SDED modalitate sistematică de generare a traiectoriilor dinamice ale sistemului producerea unor secvenţe de ipostaze (imagini) ale SDED reprezintă dinamica (evoluţia) in timp concept important: starea, caracterizată prin variabilele de stare ce iau valori discrete n

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 SDED starea fizică – cea uzuala in TS, aici tipic discreta Ex: nr.unităţilor din coada unui server intr-o reţea de cozi

starea matematică (ipostaza la mom. t), include: n

n

n

n

o informaţie completa asupra stării fizice a sistemului la momentul t toate elementele necesare pentru determinarea in mod unic a evoluţiei viitoare a sistemului, o lista a evenimentelor viitoare (LEV) ce vor determina tranziţiile de stare valori curente ale statisticilor cumulative/contorilor ce vor fi folosite in calculul statisticilor rezumative finale

Dinamica simulării SDED Este 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 îndeplinirea unor condiţii logice (reguli de operare) determina o tranziţie de stare In noua stare noi evenimente pot fi planificate Evenimentele existente continua sau vor fi terminate conform cu LEV

Evenimentele apariţii instantanee care schimbă starea sistem delimitează activităţi in sistem pot fi: n n

endogene: apariţii in interiorul sistemului exogene: apar in mediu (in afara sistemului) dar afectează sistemul

in simulare, parametrul timp este doar asociat apariţiei evenimentelor, iar progresia temporala a simulării este implicita avansului in procesarea LEV

Simulatoare un simulator este un program de calculator prin care se modeleaza: n n

comportamentul intern al unui sistem real procesele de intrare ce dirijeaza sau controleaza sistemul simulat

iesirea unui simulator consta intr-un set de masuratori legate de reactiile observabile si performanta sistemului real masuratorile 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 simulare Construcţia unui simulator se face pe baza unei metodologii de simulare simularea condusa de timp implica existenta unui ceas de timp central avansat cu increment fix n

n

generează algoritmi ineficienţi si este mult mai puţin utilizata prezintă un anumit interes doar in cazul simulării paralele (distribuite)

metodologia generala de simulare pentru SDED este simularea condusa de evenimente n

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 SDED Planificarea de evenimente

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 eveniment n mecanismul de avans temporal si garantarea apariţiei cronologice a evenimentelor e complet bazat pe LEV n

Interacţiunea proceselor

se descriu procesele asociate cu entităţile – acestea pot fi permanente sau temporare n simularea se constituie ca un ansamblu de procese n mai multe procese pot fi simultan active in model si interacţiunea dintre ele poate fi complexa n

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 tratare 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

... pentru un sistem simplu de aşteptare Compus dintr-o coada de dimensiune maxima n=500 si un server

Sosirea clienţilor

COADA

SERVER

Clienţi in aşteptare

Client in servire

Plecarea clienţilor

Va fi considerat complet stochastic: Procesul de sosire este aleator n Timpul de servire este aleator n

Definire sistem si obiective Entităţi: Clienţi, Coada, Server n

nu este necesara reprezentarea explicita a clienţilor (individualizarea lor)

Evenimente: sosire client, plecare client Date 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 modelului Starea sistem este descrisa de variabilele: n

n

lqt=numărul de clienţi aflaţi in coada de aşteptare la un moment dat lst=numărul de clienţi aflaţi in servire la un moment dat, 1 sau 0 (sau starea serverului, ocupat sau liber)

Evenimente: n n

sosirea unui client in sistem; plecarea unui client din sistem prin terminarea servirii sale;

Activităţi: n n

timpul între sosiri, definit de o tabela ce se generează aleator timpul de servire, definit in acelaşi mod

Întârzieri: aşteptări in coada, pana serverul devine liber

Descrierea dinamica a modelului Cum 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, 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 sistem Pot coexista, interacţiona si intra in competiţie multiple copii ale entităţilor Codul de simulare este non-procedural: in mod 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 specializat n

n

Altfel, se recurge la serializare si planificare de evenimente Oricum, eficienţa este mai scăzuta in cazul execuţiei secvenţiale

Diagrama proceselor asociate entităţilor

Creare Nod

Nod in Coada

Terminare Nod 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 18

Fazele unui studiu de simulare

Faza de planificare a) 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 modelare Consta in: a) Construcţia modelului: pot exista mai multe modele candidate, trebuie ales unul 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 program Validarea 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 intrare distingem următorii paşi: a. colectarea datelor brute din sistemul studiat b. 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 asumate d. testarea concordantei intre distribuţia asumata (cu parametri estimaţi) si datele de intrare, folosind: § testul χ2 § testul Kolmogorov-Smirnov

ØDaca testul de concordanta eşuează, ipoteza că datele urmează legea distribuţionala propusa trebuie respinsa si se încearcă o noua ipoteza distribuţionala (se reia cu pasul b) ØDaca mai multe iteraţii ale acestei proceduri eşuează in găsirea unei concordante intre distribuţia asumata si datele colectate, trebuie folosita distribuţia empirica

Faza de execuţie Consta in: a) Proiectarea experimentelor: se aleg execuţii generice b) Experimentare: se executa programul cu date reale! c) Analiza: se interpretează rezultatele d) 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 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 evenimente Rămâne cea mai adecvată programării standard, si cea mai eficienta in cazul execuţiei secvenţiale Se utilizează de obicei funcţii de biblioteca pentru n n n n n

Prelucrarea listelor Generarea numerelor aleatoare Generarea variabilelor aleatoare Colectarea statisticilor 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 Timpi Timp Unit între sosire sosiri

Unit

Timp servire

Unit Timp Încep Timp Termin sosire servire servire servire

1

-

0

1

2

1

0

0

2

2

2

2

2

2

1

2

2

2

1

3

3

4

6

3

3

3

6

6

3

9

4

1

7

4

2

4

7

9

2

11

5

2

9

5

1

5

9

11

1

12

6

6

15

6

4

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 ⇒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” Planifica următoarea sosire

Server ocupat? Nu

Da Plasează clientul sosit in coada

Ocupa server

Planifica eveniment de plecare client

Return

Tratare eveniment “plecare client” Coada vida? Nu

Da Elibereaza serverul

Selecteaza client din coada pentru servire

Actualizeaza statisticile pentru server Actualizeaza statisticile pentru coada si noul client in servire Colecteaza datele pentru clientul care pleaca

Planifica evenimentul de plecare

Return

Programarea modelului Poate fi făcuta intr-un limbaj procedural (C) Proiectul C (anexat) e compus din fişierele sursa: n

n

n

"sp.c“: simulatorul principal, ce conţine rutinele de iniţializare, avans timp, tratare a evenimentelor si generare a rapoartelor "rndevg.c“: conţine rutine pentru generarea distribuţiilor statistice "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 calcul Curs, anul III Calculatoare Studiu de simulare secvenţială discretă

Fazele studiului de simulare Formularea problemei si planului

Nu Model programat valid? Da

Colectare date si definire model Proiectarea experimentelor

Model conceptual valid? Da Constructia programului si verificarea

Executii pilot

Nu

Executia experimentelor

Analiza rezultatelor simularilor

Interpretare si documentare program

Scopul studiului De 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 simplu 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 reexaminate n n

Terminologia de baza Câteva probleme statistice importante

Sistemul simplu de aşteptare Server

Sosirea unitatilor

7

6

5

Coada (FIFO)

4

Plecarea unitatilor Unitate in servire

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 model La momentul iniţial (t=0) sistemul este gol Date de intrare (observate sau generate, nu interesează deocamdată cum), de ex. in minute: Client (unit) Timp de sosire 1 0.00 2 1.73 3 3.08 4 3.79 5 4.41 6 18.69 7 19.39 8 34.91 9 38.06 10 39.82 11 40.82 . . . .

Condiţie de oprire: t>20

Timp intre sosiri 1.73 1.35 0.71 0.62 14.28 0.70 15.52 3.15 1.76 1.00 . . .

Timp de servire 2.90 1.76 3.39 4.52 4.46 4.36 2.07 3.36 2.37 5.38 . . .

Obiective & Masuri de performanta Capacitatea de procesare totala pe durata simulării (P) Timpul de aşteptare mediu al unităţilor in coada N

∑ WQi

i =1

N = nr. unităţilor ce aşteaptă in coada WQi = timpul de aşteptare in coada al unităţii i Ştim ca: WQ1 = 0 (?) N > 1 (de ce?)

N Timpul de aşteptare maxim al unităţilor in coada max WQi i =1,...,N

Măsuri de performanţă (2) Media (in timp) a numărului de unităţi in coada 20 ∫0 Q (t ) dt

Q(t) = numărul de unităţi in coada la momentul t 20 Numarul maxim de unităţi in coada

max Q (t )

0≤t ≤20

Timpul mediu si maxim total in sistem al clienţilor (sau timpul de ciclare) P ∑TSi

i =1

P

,

max TSi

i =1,...,P

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)

∫

20

0

B(t ) dt 20

1 daca serveruleste ocupat la mom.t , B(t ) =  0 daca serveruleste liber la mom.t

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: n n

n

n

Sistemul va opera in regim stabil după un timp Daca toţi timpii intre sosiri si cei de servire ar fi exact pe medie, unităţile nu ar intra in coada Dar in general datele aleatoare au o anumita variabilitate - coada se va forma Daca timpul mediu intre sosiri < timpul mediu de servire, coada va creste “exploziv”

Modelarea analitica Este aici posibila si utila, ca prima aproximaţie, folosind un model M/M/1 Necesita insa presupuneri suplimentare: n n n n n

Timpii intre sosiri ~ distribuiţi exponenţial Timpii de servire ~ exponenţial, independent Trebuie ca E(servire) < E(inter-sosiri) Analiza se face doar in starea stabila Se pot obţine rezultate exacte; de ex., timpul mediu de aşteptare in coada: µS2 , µ A − µS

µ A = E(interarrival time) µS = E(service time)

Statistici cumulative si contori Numărul curent de unităţi servite Totalul timpilor de aşteptare in coada Numărul curent de unităţi ce au stat in coada Timpul maxim de aşteptare in coada (curent) Totalul timpilor in sistem Timpul 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 Se Se Se n n n

identifica evenimentele caracteristice iniţializează si se menţine un ceas de timp global creează si se menţine LEV decide logica fiecărui tip de eveniment pentru Tranziţiile de stare Actualizarea statisticilor 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 n n

Valoarea ariei de subQ(t) Max {Q(t)} Valoarea ariei de sub B(t)

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 0

Altfel, 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ă servire Incrementează acumulatorul corespunzător Calculează timpul in sistem al unităţii (momentul curent – momentul sosirii) 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ă statisticile Se 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)

Simularea pas cu pas: set-up System

Clock

Number of completed waiting times in queue

Total of waiting times in queue

B(t)

Q(t)

Arrival times of custs. in queue

Area under Q(t)

Event calendar

Area under B(t)

4 3

Q(t) graph

2 1 0

B(t) graph

0

5

10

15

20

0

5

10

15

20

2 1 0

Interarrival times

Time (Minutes) 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, ...

Iniţializări la t = 0.00 System

Number of completed waiting times in queue 0

Clock

B(t)

Q(t)

0.00

0

0

Arrival times of Event calendar custs. in queue [1, 0.00, Arr] [–, 20.00, End]

Total of waiting times in queue

Area under Q(t)

Area under B(t)

0.00

0.00

0.00

4

Q(t) graph

3 2 1 0

B(t) graph

0

5

10

15

20

0

5

10

15

20

2 1 0

Interarrival times

Time (Minutes) 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, ...

t = 0.00, sosirea unităţii 1 System

1 Number of completed waiting times in queue 1

Clock

B(t)

Q(t)

Total of waiting times in queue

Arrival times of Event calendar custs. in queue [2, 1.73, Arr] [1, 2.90, Dep] [–, 20.00, End] Area under Area under Q(t) B(t)

0.00

1

0

0.00

0.00

0.00

4

Q(t) graph

3 2 1 0

B(t) graph

0

5

10

15

20

0

5

10

15

20

2 1 0

Interarrival times

Time (Minutes) 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, ...

t = 1.73, sosirea unităţii 2 System

2

1

Number of completed waiting times in queue 1

Clock

B(t)

Q(t)

Total of waiting times in queue

Arrival times of Event calendar custs. in queue [1, 2.90, Dep] (1.73) [3, 3.08, Arr] [–, 20.00, End] Area under Area under Q(t) B(t)

1.73

1

1

0.00

0.00

1.73

4

Q(t) graph

3 2 1 0

B(t) graph

0

5

10

15

20

0

5

10

15

20

2 1 0

Interarrival times

Time (Minutes) 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, ...

t = 2.90, plecarea unităţii 1 System

2 Number of completed waiting times in queue 2

Clock

B(t)

Q(t)

Total of waiting times in queue

Arrival times of Event calendar custs. in queue [3, 3.08, Arr] [2, 4.66, Dep] [–, 20.00, End] Area under Area under Q(t) B(t)

2.90

1

0

1.17

1.17

2.90

4

Q(t) graph

3 2 1 0

B(t) graph

0

5

10

15

20

0

5

10

15

20

2 1 0

Interarrival times

Time (Minutes) 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, ...

t = 3.08, sosirea unităţii 3 System

3

2

Number of completed waiting times in queue 2

Clock

B(t)

Q(t)

Total of waiting times in queue

Arrival times of Event calendar custs. in queue [4, 3.79, Arr] (3.08) [2, 4.66, Dep] [–, 20.00, End] Area under Area under Q(t) B(t)

3.08

1

1

1.17

1.17

3.08

4

Q(t) graph

3 2 1 0

B(t) graph

0

5

10

15

20

0

5

10

15

20

2 1 0

Interarrival times

Time (Minutes) 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, ...

t = 3.79, sosirea unităţii 4 System

4

3

2

Number of completed waiting times in queue 2

Clock

B(t)

Q(t)

Total of waiting times in queue

Arrival times of Event calendar custs. in queue [5, 4.41, Arr] (3.79, 3.08) [2, 4.66, Dep] [–, 20.00, End] Area under Area under Q(t) B(t)

3.79

1

2

1.17

1.88

3.79

4

Q(t) graph

3 2 1 0

B(t) graph

0

5

10

15

20

0

5

10

15

20

2 1 0

Interarrival times

Time (Minutes) 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, ...

t = 4.41, sosirea unităţii 5 System

5

4

3

2

Number of completed waiting times in queue 2

Clock

B(t)

Q(t)

Total of waiting times in queue

Arrival times of Event calendar custs. in queue [2, 4.66, Dep] (4.41, 3.79, 3.08) [6, 18.69, Arr] [–, 20.00, End] Area under Area under B(t) Q(t)

4.41

1

3

1.17

3.12

4.41

4

Q(t) graph

3 2 1 0

B(t) graph

0

5

10

15

20

0

5

10

15

20

2 1 0

Interarrival times

Time (Minutes) 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, ...

t = 4.66, plecarea unităţii 2 System

5

4

3

Number of completed waiting times in queue 3

Clock

B(t)

Q(t)

Total of waiting times in queue

Arrival times of Event calendar custs. in queue [3, 8.05, Dep] (4.41, 3.79) [6, 18.69, Arr] [–, 20.00, End] Area under Area under B(t) Q(t)

4.66

1

2

2.75

3.87

4.66

4

Q(t) graph

3 2 1 0

B(t) graph

0

5

10

15

20

0

5

10

15

20

2 1 0

Interarrival times

Time (Minutes) 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, ...

t = 8.05, plecarea unităţii 3 System

5

4

Number of completed waiting times in queue 4

Total of waiting times in queue

Arrival times of Event calendar custs. in queue [4, 12.57, Dep] (4.41) [6, 18.69, Arr] [–, 20.00, End] Area under Area under B(t) Q(t)

7.01

10.65

Clock

B(t)

Q(t)

8.05

1

1

8.05

4

Q(t) graph

3 2 1 0

B(t) graph

0

5

10

15

20

0

5

10

15

20

2 1 0

Interarrival times

Time (Minutes) 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, ...

t = 12.57, plecarea unităţii 4 System

5 Number of completed waiting times in queue 5

Clock

B(t)

Q(t)

12.57

1

0

Arrival times of custs. in queue

Total of waiting times in queue

Area under Q(t)

15.17

15.17

Event calendar [5, 17.03, Dep] () [6, 18.69, Arr] [–, 20.00, End] Area under B(t) 12.57

4

Q(t) graph

3 2 1 0

B(t) graph

0

5

10

15

20

0

5

10

15

20

2 1 0

Interarrival times

Time (Minutes) 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, ...

t = 17.03, plecarea unităţii 5 System

Number of completed waiting times in queue 5

Clock

B(t)

Q(t)

17.03

0

0

Arrival times of custs. in queue ()

Event calendar [6, 18.69, Arr] [–, 20.00, End]

Total of waiting times in queue

Area under Q(t)

Area under B(t)

15.17

15.17

17.03

4

Q(t) graph

3 2 1 0

B(t) graph

0

5

10

15

20

0

5

10

15

20

2 1 0

Interarrival times

Time (Minutes) 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, ...

t = 18.69, sosirea unităţii 6 System

6 Number of completed waiting times in queue 6

Total of waiting times in queue

Area under Q(t)

Event calendar [7, 19.39, Arr] [–, 20.00, End] [6, 23.05, Dep] Area under B(t)

15.17

15.17

17.03

Clock

B(t)

Q(t)

18.69

1

0

Arrival times of custs. in queue ()

4

Q(t) graph

3 2 1 0

B(t) graph

0

5

10

15

20

0

5

10

15

20

2 1 0

Interarrival times

Time (Minutes) 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, ...

t = 19.39, sosirea unităţii 7 System

7

6

Number of completed waiting times in queue 6

Total of waiting times in queue

Arrival times of Event calendar custs. in queue [–, 20.00, End] (19.39) [6, 23.05, Dep] [8, 34.91, Arr] Area under Area under B(t) Q(t)

15.17

15.17

Clock

B(t)

Q(t)

19.39

1

1

17.73

4

Q(t) graph

3 2 1 0

B(t) graph

0

5

10

15

20

0

5

10

15

20

2 1 0

Interarrival times

Time (Minutes) 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, ...

t = 20.00, sfârşitul simulării System

7

6

Number of completed waiting times in queue 6

Clock

B(t)

Q(t)

20.00

1

1

Arrival times of Event calendar custs. in queue [6, 23.05, Dep] (19.39) [8, 34.91, Arr]

Total of waiting times in queue

Area under Q(t)

Area under B(t)

15.17

15.78

18.34

4

Q(t) graph

3 2 1 0

B(t) graph

0

5

10

15

20

0

5

10

15

20

2 1 0

Interarrival times

Time (Minutes) 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, ...

Operaţii la sfârşitul simulării Timpul mediu de aşteptare in coada: Timpul total in coada 15 .17 = = 2.53 min./unit. Nr.de unitati 6

Media in timp a numărului de unităţi in coada: Aria de sub curba Q(t ) 15.78 = = 0.79 unitati Valoarea finala de ceas 20

Utilizarea serverului: Aria de sub curba B(t ) 18.34 = = 0.92 Valoarea finala de ceas 20

Replicarea simulării Valoarea unei singure simulări (“replicări”) nu este foarte semnificativa dpdv statistic Tabelul următor permite compararea a 5 replicări:

Se poate observa variabilitatea mare intre replicări

Modificarea parametrilor In mod uzual, simularea se aplica in mod repetat nu doar prin simpla replicare, ci pentru diferite configuraţii ale modelului, cu parametri modificaţi In acest fel se face acordarea si optimizarea modelului (după anumite criterii) Exemplu: ce se întâmpla daca se dublează rata sosirilor? n

n

n

Datele de intrare se obţin prin înjumătăţirea timpilor intre sosiri Se va relua execuţia modelului pentru configuraţia modificata Se vor executa 5 replici ale simulării

Modelarea sistemelor de calcul Curs, anul III Calculatoare Verificarea si validarea simularilor. Analiza iesirilor

Sumar Corectitudinea estimatorilor. Rolul etapelor de validare si verificare Tipuri de estimatori n n n

Estimatori (ne)balansati Estimatori consistenti Estimator interval si grad de incredere

Analiza iesirilor. Determinarea intervalelor de incredere Clasificarea simularilor Simulari complete si de stare stabila

O practica uzuala Se construieste modelul, se executa simularea Se obtin estimari ale masurilor de performanta relevante ale sistemului , de ex. n n n n

Timpul mediu in coada Timpul mediu in sistem Rata de iesire a clientilor % 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)? 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, si cat de corecta este includerea acesteia?

Validare si verificare O simulare este valida daca modelul de simulare reprezinta cu acuratete sistemul real n

Validarea raspunde la intrebarea “A fost construit modelul adecvat?”

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 (“whatif analysis”)

Iesiri deterministe si stochastice Simularea 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 intrare Pentru un model stochastic (si) datele de iesire sunt aleatoare, ele fiind deci doar estimari ale parametrilor reali ai sistemului n De aceea o singura executie a unui model stochastic nu este niciodata suficienta

Acuratetea estimarii Poate fi data sub forma: n n

unui prag (interval, probabilitate) de incredere 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 statistica Inferenta statistica este o metoda de analiza a unui sistem caracterizata prin utilizarea datelor experimentale ca baza a diferitelor concluzii Un estimator punctual al unui parametru sistem θ este un numar calculat pe baza datelor experimentale, notat θˆ Uneori termenul de estimator desemneaza statistica folosita pentru a calcula un rezultat De exemplu:

µˆ = x = 31 . 75

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

Estimatori si statistici Dualitatea 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 experimentale De exemplu, Ø statistica naturala pentru estimarea mediei unei populatii, µ, este media esantionului de date, x Ø statistica naturala pentru estimarea variantei σ2 este varianta esantionului de date, s2

Exemplu O 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

n

n

n

Se captureaza mai intai un numar mic de pesti, de exemplu 100, care se marcheaza si se elibereaza in lac 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 Daca intre acestia se gasesc de ex. 20 marcati (adica 4%) este rezonabila estimarea ca 4% din totalul pestilor sunt marcati!? 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)balansati Un estimator θˆ al unui parametru θ s.n. nebalansat daca: µ θˆ = θ Altfel, θˆ s.n. balansat, iar cantitatea µθˆ − θ s.n. balansul lui θ (bias) Cele mai importante statistici (media, abaterea patratica medie s2) sunt estimatori nebalansati O exceptie importanta este deviatia standard a esantionului, s - estimator “usor” balansat al deviatiei standard n n

Balansul este neglijabil pentru esantioane largi Pentru esantioane mici, poate fi aplicat un factor de corectie

Estimatori consistenti Daca, prin cresterea marimii esantionului (n), n

n

un estimator θˆ poate fi facut oricat de apropiat de un parametru θ sau, echivalent, probabilitatea ca el sa fie oricat de apropiat de parametru poate fi oricat de apropiata de 1

θˆ s.n. estimator consistent al parametrului θ

Metoda cea mai simpla prin care se poate arata ca un estimator este consistent este aceea de a arata ca eroarea standard descreste pe masura ce marimea esantionului creste

Eroarea standard (a mediei) E un estimator al deviatiei standard a distributiei de esantionare asociate cu metoda de estimare (de obicei, distributia normala) σ , unde: σ este deviatia standard a esantionului σx = n este marimea esantionului n Formula 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)

Estimator interval si grad de incredere Un estimator punctual, doar el, nu furnizeaza informatii despre precizia si gradul de incredere intr-o estimare Alternativa 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 numeste n Estimator interval, sau n Interval de incredere Doar daca gradul de incredere (notat de obicei prin p sau α) 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 esantionate x Cand n este mare, distributia lui x este aprox. normala (Teorema de limita centrala) si se poate standardiza prin x−µ x − µ sau z = z = s n σ / n tinand cont de faptul ca deviatia standard a populatiei sau procesului (σ) nu este cunoscuta si trebuie inlocuita prin cea a esantionului (s)

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.96

From 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 deviatii standard ale mediei Pe baza teoremei de limita centrala, acest numar poate fi folosit in constructia pragurilor (intervalelor) de incredere de 95% Ubicuitatea acestui parametru se datoreaza unei conventii arbitrare dar comune de utilizare a intervalelor de 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 permanent w 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 sistemului w 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 stabila Decizia de a face simularea complet, sau doar pentru starea stabila, 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

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 ele Exemplu: n

Simularea activitatii unei banci, pentru a determina numarul de personal w Banca deschide la 9, initial nu sunt clienti w Opereaza “normal” pana la ora 16 w La ora 16 se inchid usile, nu se mai admit clienti in

banca; cei aflati inauntru isi termina operatiunile si parasesc banca

Simulare completa O 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 n TF este de obicei variabila aleatoare n TF este predeterminat la inceputul simularii n Sau se specifica evenimentul final EF Trebuie de asemenea definite conditiile initiale la momentul 0

Simulare de stare stabila O 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 infinit n n

Starea sistem este independenta de conditiile initiale 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 complete Se 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) w conditii initiale diferite, independent alese

Fiecare executie s.n. replicare In mod tipic, caracteristicile si comportamentul de iesire al modelului difera mai mult in faza initiala decat in finalul simularilor replicate n

Colectarea statisticilor intermediare Daca avem n replici ale simularilor, m observatii intermediare pentru fiecare simulare, fie: xij = cea de j-a observatie din replica i yi = un parametru de performanta calculat in replica i

Atunci, pentru i=1,2,...n si j=1,2,...,m:

Determinarea intervalelor de incredere Aceste valori constituie estimatori nebalansati: n

n

(si in plus independenti) ai mediei (valorii asteptate) si dispersiei (abaterii patratice) la m momente diferite ai mediei si dispersiei ca masuri globale de performanta

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:

Exemplu Se considera un sistem M/M/1 Se doreste ca prin simulare sa fie estimati urmatorii parametri: n n

Rata de utilizare a serverului, ρ Timpul mediu petrecut de un client in sistem, ω

Se executa patru simulari distincte (cu 4 fluxuri diferite de numere aleatoare) pentru a genera: n n

Timpii intre sosiri Timpii de servire

Rezultatele simularilor pentru aceeasi durata de timp sunt date de tabelul urmator:

Rezultate si prelucrari Nr.executie (n) Utilizarea server (ρn) 1 0,808

Timp mediu in sistem (ωn) 3,74

2

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 decizii Doar dupa validarea siverificarea ei, o simulare poate constitui baza luarii unor decizii corecte n

n

Validarea ne asigura ca modelul de simulare reprezinta cu acuratete sistemul real 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 construita Simularile 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 n

care este acuratetea estimatorilor care sunt tipurile de estimatori ce pot fi folositi

Cele mai importante statistici (media, abaterea patratica medie s2) sunt estimatori nebalansati Asigurarea preciziei reprezentarii datelor se face prin metode statistice: erori standard, intervale de incredere, replicari independente ale simularii n

n

Determinarea intervalelor de incredere se bazeaza pe apropierea distributiei esantionate a mediilor de distributia normala (n mare) Estimarea acuratetei unei simulari necesita date obtinute din cateva repetari (replici) ale simularii

Concluzii (3) In simularea unui sistem putem fi interesati: n

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 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 n

tipului de sistem modelat tipului de parametri ce sunt urmariti si ale caror valori se vor obtine prin simulare

Modelarea sistemelor de calcul Curs, anul III Calculatoare Accelerarea execu iei simulărilor. Simularea paralelă (distribuită)

Sumar Caracteristici și dificultăți Nivele de paralelism/ distribuţie în simulare Simularea paralelă prin interacţiunea proceselor. Partajarea domeniului spaţiu-timp între PL Problema timpului simulării Abordări conservative și optimiste Concluzii

Problema Pentru a fi semnificativă statistic, o simulare de SDED trebuie să fie lungă sau repetată Simulările secvenţiale, uneori repetate, durează aproape întotdeauna prea mult Problema reducerii timpului de execuţie, se poate soluţiona pe două căi: n

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; 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 eficient în paralel Unele sarcini ale simulării, precum colectarea statisticilor cumulative, sunt independente şi pot avea loc în paralel în raport cu celelalte sarcini, etc.

Dificultăţi Simularea 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 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 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 exclusive b) 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ţionate c) 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 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 (î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 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 concurente Sarcina 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 LEV Această 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ă) 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ţi schemele 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. stare

var. stare

timp

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 evenimente Trebuie creat și un sistem de comunicaţie (SC), care să asigure PL posibilitatea de a schimba date locale, dar şi de a-şi sincroniza activităţile locale Fiecă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 n n

planifică şi execută evenimente locale generează evenimente locale sau pentru alte PL 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 n

interne, ce pot afecta cauzal doar Si ; 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 lui Mecanismul 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ă local n

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 n

fie reprezentat explicit, central, printr-o structură de date fie implicit într-o procedură ce se execută în paşi

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

n

fiecare PL se conduce după valori proprii ale ceasului de timp virtual (local) 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 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ăstrat 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 protocoalele conservative şi optimiste (1) Cel mai mare dezavantaj al simulărilor conservative este că nu exploatează complet paralelismul sistemului: n

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ă, 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 protocoalele conservative ş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 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

Principiu operaţ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 de stări arbitrar de mari.

Sunt eficiente atunci când, în model, spaţiul stărilor şi necesa- rul de spaţiu de memorie per stare sunt mici.

Consumul de memorie.

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.

Reprezentare a timpului Exploatare paralelism

Sincronizarea .

Se execută implicit în TGV; nu sunt necesare calcule explicite legate de TGV. Paralelismul sistemului nu este bine exploatat; dacă apar rar constrângeri cauzale, protocolul este prea pesimist.

Se bazează pe calculul explicit şi dificil (fără suport hardware) al TGV. Paralelismul sistemului este bine exploatat; dacă constrângerile cauzale apar rar, protocolul aduce câştiguri de timp

Mecanismul de sincronizare este 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.

Mecanismul sincronizării 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.

Configurare

Majoritatea tehnicilor necesită interconectarea statică a proceselor.

Admit configurarea dinamică a proceselor.

Lookaheadprospectare

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; dispersia 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 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ă 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 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.

Concluzii Problema “paralelizării” simulărilor nu este deloc o problemă trivială Indiferent ce componentă a simulatorului considerăm, descompunerea şi exec. în paralel trebuie analizată atent 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ă