New PRS3.ppt · 2009. 3. 24. · 3.2 iskorišćenje kod sistema sa Dinamičkim particijama za...
Transcript of New PRS3.ppt · 2009. 3. 24. · 3.2 iskorišćenje kod sistema sa Dinamičkim particijama za...
3.2 iskorišćenje kod sistema sa Dinamičkim particijama za memoriju sa dve jedinice(Dinamičke i relokativne particije)
NeNe postojipostoji fiksnafiksna granicagranica izmedjuizmedju particijaparticijaNe Ne postojipostoji fiksnafiksna granicagranica izmedjuizmedju particijaparticija. .
S1 S2 H1 S3 S4 H2 Sn Hk0 memorija 1(normalizovana na 1)
H:=HH:=H11+H+H22+…++…+HHkk –– ukupanukupan slobodanslobodan prostorprostor ((slobodnaslobodnamemorijamemorija))DaDa bi se bi se ubacioubacio sledećisledeći posaoposao trebatreba dada postojipostoji ruparupa ne ne manjamanja ododaa b seb se ubac oubac o s edećs edeć posaoposao ebaeba dada pos ojpos oj upaupa ee a jaa ja ododveliveličine čine tog tog poslaposlaAlgoritmiAlgoritmi zaza punjenjepunjenje: FIRST FIT : FIRST FIT ii BEST FIT. BEST FIT. Po BEST FITPo BEST FIT algoritmualgoritmu sese posaoposao smesmešštata uu najmanjunajmanju rupurupu uu kojukojuPo BEST FIT Po BEST FIT algoritmualgoritmu se se posaoposao smesmešštata u u najmanjunajmanju rupurupu u u kojukojumožemože dada stanestane, du, dužž memorijememorije ravnomernoravnomerno razbacanirazbacani posloviposlovi((stvarastvara se se ravnomernaravnomerna raspodelaraspodela ššupljinaupljina). ).
ETF-Beograd Performanse Računarskih Sistema
1
3.2 iskorišćenje kod sistema sa Dinamičkim particijama za memoriju sa dve jedinice(Dinamičke i relokativne particije)
Po FIRST FITPo FIRST FIT algoritmualgoritmu krenemokrenemo redomredom ii posaoposao sese smesmešštata uu prviprviPo FIRST FIT Po FIRST FIT algoritmualgoritmu krenemokrenemo redomredom ii posaoposao se se smesmešštata u u prviprviodgovarajuodgovarajućću u zonuzonu ((posloviposlovi susu koncentrisanikoncentrisani nana popoččetkuetku).).KnuthKnuth--ovoovo pravilopravilo:: brojbroj zauzetihzauzetih segmenatasegmenata u u memorijimemoriji je 2x je 2x većivećiodod brojabroja ruparupa ⇒⇒ k /2 utvrđeno posmatranjem a neodod brojabroja ruparupa ⇒⇒
DDolaolazazak k novognovog poslaposla javljajavlja se se sasa jednakomjednakom verovatnoćomverovatnoćom kaokao iid dj jd dj j dl kdl k ll ii ijij R lt tR lt t jj dd 50%50%
k ≈ n/2 utvrđeno posmatranjem, a ne analitički
dogadjajdogadjaj odlaskaodlaska poslaposla iziz memorijememorije. . RezultatRezultat je je dada se u 50% se u 50% slučajevaslučajeva desnodesno odod posmatranog posmatranog poslaposla nalazinalazi ruparupa,, a u a u drugihdrugih
50% 50% desnodesno odod poslaposla je je posaoposao..
ETF-Beograd Performanse Računarskih Sistema
2
3.2 iskorišćenje kod sistema sa Dinamičkim particijama za memoriju sa dve jedinice(Dinamičke i relokativne particije)
K kK k jj čč liličiči (j b(j b )) P čP č ličiličiKakoKako je je pprosečnarosečna veliveličina čina programaprograma (job(job--a) a) , a , a ProsečnProsečnaa veličinaveličina
““ruparupa”” , , imamoimamo dada je: je: H n s k H 1⋅ + ⋅ =s
/1=U=2/(2+c)k/n=1/2 (Knuth)
Ū(c)=2/(2+c) 0<c<1
n s (1 k H / n s) 1⋅ ⋅ + ⋅ ⋅ = n s⋅
iskorišćenje, tj veličina zauzete memorije u memoriji veličine 1
Ū(c) 2/(2+c) ,0 c 1n·s (1+c/2)=1
n s⋅ - ukupno iskorišćeni deo memorije
memorije u memoriji veličine 1.c H / s= - odnos veličina rupa i posla, 0<c<1
ETF-Beograd Performanse RačunarskihSistema
3
3.2 iskorišćenje kod sistema sa Dinamičkim particijama za memoriju sa dve jedinice(Dinamičke i relokativne particije)
Idealan slučaj bi bio c 0 (nema rupa) 100%Idealan slučaj bi bio c=0 (nema rupa) ⇒ 100% iskorišćenje, a mora biti 0 < c < 1 inače bi rupe veće od poslova bile popunjene.
Za c=1 ⇒ Ū(c)=2/3=0.667 , za c=0.5 ⇒Ū( ) 2/2 5 0 8 t k d j 0 5< <1Ū(c)=2/2.5=0.8 , tako da je za 0.5<c<1⇒0.667< Ū<0.8 => gubitak memorije je između 1/5 i 1/31/3
ETF-Beograd Performanse Računarskih Sistema
4
3.2 iskorišćenje kod sistema sa Dinamičkim particijama za memoriju sa dve jedinice(Dinamičke i relokativne particije)
A liA li Di ičkihDi ičkih ti ijti ijAnalizaAnaliza DinamičkihDinamičkih particijaparticija(T.(T. BetteridgeBetteridge && B.B. RandellRandell))
PretpostavkePretpostavke::PretpostavkePretpostavke::memorijamemorija je je podeljenapodeljena nana blokoveblokove ((memorijskememorijske jedinicejedinice) ) isteisteveliveličičine ne kojihkojih imaima MM
ličiliči ll ll ll ll dd (( ))veličinaveličina programaprograma je 1 je 1 iliili 2 2 iliili 3 3 iliili … … iliili M M jedinicajedinica ( ( 1 1 ≤≤ S S ≤≤ MM ))i svaka veličina je podjednako verovatna. i svaka veličina je podjednako verovatna. Program se Program se smesmešta šta isključivo u uzastopne jedinice.isključivo u uzastopne jedinice.
b kb k ll k lk lvremevreme boravkaboravka posla posla u u memorijimemoriji je je eksponencijalnoeksponencijalnorasporaspodeljenodeljeno: : PPrr[t [t ≤≤x]=1 x]=1 -- ℮¯℮¯ccˣ,ˣ, cc=const=const⇒⇒ 2 2 poslaposlanikadanikada ne ne završavajuzavršavaju iistovremenostovremeno, , nikadanikada se ne dse ne dešavaješavaju 2 u 2 dd đđ jj dl kdl k ii ijij ii
ETF-Beograd Performanse Računarskih Sistema
5
dogadogađđajaaja odlaskaodlaska iziz memorijememorije u isto vremeu isto vreme
3.2 iskorišćenje kod sistema sa Dinamičkim particijama za memoriju sa dve jedinice(Dinamičke i relokativne particije)
OObradabrada sese vrvrššii popo FCFSFCFS algoritmualgoritmu particijeparticije nisunisu relokatibilnerelokatibilne((ninišštataOObradabrada se se vrvrššii popo FCFSFCFS algoritmualgoritmu, , particijeparticije nisunisu relokatibilnerelokatibilne((ninišštatase se odod programaprograma ne ne pomerapomera,, stanjestanje se ne se ne menjamenja) )
1 2 3Svaka od veličina programa je podjednako
broj
(1)
(2)
- veličina 1Svaka od veličina programa je podjednako verovatna
U pitanju je slučaj do M blokova (veličina memorije):
- vel. 2
stanj
(3)
(4)
j )M=1, 2, 3, 4, 5, 6, 7, 8 –vel. memn= 1, 4, 12, 33, 88,232,609,1596 -br stanja
Događaj u sistemu je odlazak/dolazak,nja
ovo analiziramo
. . . vel. 3
g j j ,stanja su 1,2,3,4 za slučaj 2 bloka
Ako je veličina memorije=1 onda je program veličine 1
ETF-Beograd Performanse RačunarskihSistema
6
p g
3.2 iskorišćenje kod sistema sa Dinamičkim particijama za memoriju sa dve jedinice(Dinamičke i relokativne particije)
Broj stanja n u slučaju memorije sa M blokova je n=f2M -1 ~ Fibonačijevi brojevi: f0=f1=1, fk=fk-1 + fk-2
M0.72 (2.6)⋅
Veličina memorije=2 ⇒ 4 stanja; veličina memorije=3 ⇒ 12 stanjaPosmatramo slučaj sa dva bloka (4 stanja).Stanja 1 i 3 su stanja u kojima je jedna particija prazna a to znači da čeka
liki B (bi ) j bi li S ( ll) b il l b d ti ijveliki posao B (big), jer bi se mali S (small) ubacilo u slobodnu particiju.S S ii B B susu jednakojednako verovatniverovatni..
U stanje 1 se prelazi:U stanje 1 se prelazi:• iz 2 ode drugi posao a sledeći posao koji dolazi je B• iz 4 ode B, zatim dolazi S
ETF-Beograd Performanse Računarskih Sistema
7
3.2 iskorišćenje kod sistema sa Dinamičkim particijama za memoriju sa dve jedinice(Dinamičke i relokativne particije)
U stanje 2 se prelazi:• iz 1 i 3 ne može jer posle završetka posla čekaju B• iz 2 može jer ako ode S i dodje S opet je u 2
ž• iz 4 može ako ode B a dolaze za redom dva S posla
U stanje 3 se prelazi:U stanje 3 se prelazi: •iz 2 ode prvi a dolazi B
U stanje 4 se prelazi: j p• iz 4 u 4 ako dolaze B pa B• iz 1 i 3 kad S završi upada B koji čeka (bezuslovno)
ETF-Beograd Performanse Računarskih Sistema
8
3.2 iskorišćenje kod sistema sa Dinamičkim particijama za memoriju sa dve jedinice(Dinamičke i relokativne particije)
½=¼+¼ Verovatnoća pojave svake veličine
1 321
¼
¼ ¼Verovatnoća pojave svake veličine posla je podjednaka i iznosi 1/M
p1=¼ p2 +¼p4; p2=½ p2 +¼p4; p =¼ p ; p =p + p +½p
4
¼+¼=½
1¼
¼ p3=¼ p2; p4=p1+ p3 +½p4
p1 + p2 + p3 +p4=1
p1=3/16 p2 =1/4¼ ¼ ½ p1=3/16 p2 =1/4
p3 =1/16 p4=1/2
ETF-Beograd Performanse Računarskih Sistema
9
3.2 iskorišćenje kod sistema sa Dinamičkim particijama za memoriju sa dve jedinice(Dinamičke i relokativne particije)
iskorišćenje može biti ½ ili 1 pa je srednje iskorišćenje:iskorišćenje može biti ½ ili 1 pa je srednje iskorišćenje:iskorišćenje može biti ½ ili 1 pa je srednje iskorišćenje:iskorišćenje može biti ½ ili 1 pa je srednje iskorišćenje:M=2 : Ū=p1·U1+p2·U2+p3·U3+p4·U4=½p1+p2+½p3+p4=7/8=0.875M=8, za dinamičke particije uniformne veličine, istom računicom dobija se: Ū=0 739 što je manje nego sa dve particijedobija se: Ū=0.739, što je manje nego sa dve particijeM=8 (za relokatibilne particije, po Betteridge-ovoj analizi):
Ū= 0.762 1
Funkcija srednjeg iskorišćenja u zavisnosti od M→
Za relokatibilne particije uniformne dužinepostoji konačna formula (Betteridge):
1
0.718
M 1U (1 1/ M) 2 1/ M+= + − −
p j ( g )
Mlim U e 2 0.718→∞
= − ≈
1
ETF-Beograd Performanse Računarskih Sistema
10
M→∞
3.3 iskorišćenje kod sistema sa statičkim stranicama
MetodaMetoda sasa statistatiččkimkim stranicamastranicama (Page Partition)(Page Partition)MetodaMetoda sasa statistatiččkimkim stranicamastranicama (Page Partition) (Page Partition) ((NevirtuelnaNevirtuelna tehnikatehnika))
Ne spada u virtuelne tehnike. Ceo program mora biti u memoriji da bi se program izvršavao, raspored stranica može biti različit i zbog toga su efekti ovetehnike slični relokatibilnim particijama, jedino što u odnosutehnike slični relokatibilnim particijama, jedino što u odnosurelokatibilne particije postoji dodatni gubitak na polupopunjenu (u proseku) poslednju stranu (interna fragmentacija).N - broj stranica, M - veličina memorije,
navr - srednji stepen multiprogramiranja – prosečan broj procesa u operativnoj memoriji
ETF-Beograd Performanse Računarskih Sistema
11
u operativnoj memoriji
3.3 iskorišćenje kod sistema sa statičkim stranicama
M/N veličina jedne straniceM/N - veličina jedne stranice,
M/(2·N) - veličina polovine stranice,
navr·M/(2·N) - gubitak na polovini stranice (ovo je razlika u odnosu na relokativne particije gde nema interne fragmentacije).nema interne fragmentacije).
Primer: N≥100, navr<10,
gubitak: W=0.5 · navr · M/N ≤ 5%·M ili manje, i toliko treba odbiti od slučaja relokatibilne particije
ETF-Beograd Performanse Računarskih Sistema
12
3.4 Model jednakih veličina
Neka je veličina memorije normalizovana na 1Neka je veličina memorije normalizovana na 1
Ako iskorišćeni deo memorije u proseku iznosi Mkor (Mkor<1) i ako je p kor ( kor ) jprosečan stepen multiprogramiranja k, tada je prosečna veličina programa x=Mkor/k
Ovaj model pretpostavlja dasu svi programi iste (prosečne)
ličiveličine
ETF-Beograd Performanse Računarskih Sistema
13
3.4 Model jednakih veličina
ETF-Beograd Performanse Računarskih Sistema
14
3.4 Model jednakih veličina
1 1 1( ) ,1
1 1
S d j li ij k d t i i
U x x k x xx k k
k
⎢ ⎥= ⋅ = ⋅ ≤ ≤⎢ ⎥ +⎣ ⎦⎛ ⎞1 1
2 11 1 1 1 1, 1
1 2 1 1
Srednja linija svakog od trapeza iznosi
Visina svakog trapeza iznosi a površina
kk
kk k k k k
⎛ ⎞⋅ +⎜ ⎟+⎝ ⎠⎛ ⎞ ⎛ ⎞ ⎛ ⎞− ⋅ + ⋅ −⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠
1 1
0 0
1 2 1 1
1( ) ( ) 12 1
k k k k k
kU U x dx U x dxk
⎜ ⎟ ⎜ ⎟ ⎜ ⎟+ + +⎝ ⎠ ⎝ ⎠ ⎝ ⎠
= = = ⋅ ++∫ ∫
1 1
1 1 1 111 2 1 ( 1)k k
kk k k k k
∞ ∞
= =
⎛ ⎞ ⎛ ⎞ ⎛ ⎞⋅ − = ⋅ + ⋅ =⎜ ⎟ ⎜ ⎟ ⎜ ⎟+ + ⋅ +⎝ ⎠ ⎝ ⎠ ⎝ ⎠∑ ∑
0 0
2 2
21 1
1 1 1 1... 1 1 0.82252 ( 1) ( 1) 2 6 12k kk k k
π π∞ ∞
= =
⎛ ⎞⎛ ⎞⎛ ⎞= ⋅ + = = ⋅ + − = =⎜ ⎟⎜ ⎟⎜ ⎟⋅ + +⎝ ⎠ ⎝ ⎠⎝ ⎠
∑ ∑
ETF-Beograd Performanse Računarskih Sistema
15
3.5 Iskorišćenje memorije za slučaj virtuelne memorije organizovane u stranice(Virtuelna memorija – Straničenje na zahtev – Demand Paging)
KorisniKorisniččkiki programiprogrami ssu podeljeni uu podeljeni uKorisniKorisniččkiki programiprogrami ssu podeljeni uu podeljeni ustranicstranicee. PMT(Page Map Table). PMT(Page Map Table)––tabeletabele preslikavanjapreslikavanja, , smesmešštenetene u u deodeo rezervisanrezervisan zaza O SO SPMT 1 deodeo rezervisanrezervisan zaza O.S. O.S. NN –– ukupanukupan brojbroj stranicastranica u u fizifiziččkojkojoperativnojoperativnoj memorijimemoriji. . ZaZa svakusvakustranicustranicu postojipostoji popo jedanjedan ulazulaz uu
PMT 1
PMT2
…
O.S
MPMT
k
stranicustranicu postojipostoji popo jedanjedan ulazulaz u u tabelutabelu..Blok u Blok u kojikoji se se možemože smestitismestiti jednajednastranicastranica sese nazivanaziva page framepage frame
PMTN
PAGE0
PAGE 1x stranicastranica se se nazivanaziva page frame.page frame.PAGE 1
PAGE 2
...
Korisnički
programiMPROG
x
ETF-Beograd Performanse Računarskih Sistema
16
PAGE N
3.5 Iskorišćenje memorije za slučaj virtuelne memorije organizovane u stranice(Virtuelna memorija – Straničenje na zahtev – Demand Paging)
MM dd O SO S tt č ij d ij k ji štč ij d ij k ji št PMTPMTMMPMTPMT deodeo O.S. , O.S. , tatačnije deo memorije u koji se smeštačnije deo memorije u koji se smešta PMTPMTtabela preslikavanja stranicatabela preslikavanja stranicakk je je zauzezauzećće e memorijememorije zaza jedanjedan ulazulaz u PMT, u PMT, veličinaveličina jednogjednogl tl t PMTPMT MM jj ll žžii ijij jj ličiliči j dj delementaelementa u PMTu PMT;; MM je je raspoloraspoložživaiva memorijamemorija, , xx je je veličinaveličina jednejedne
stranicestranicennavravr -- srednjisrednji stepenstepen multiprogramiranjamultiprogramiranja, , p p -- prosečnaprosečna veličinaveličina aktivnogaktivnog deladela programaprograma u u memorijimemoriji: : pp==MMPROGPROG//nnavravr
W W -- ““izgubljeniizgubljeni””,, neiskorišćenineiskorišćeni deodeo memorijememorije ((deodeo poslednjeposlednjestranicestranice ii PMT)PMT)W= W= MMPMTPMT++nnavravr· · x/x/22 ,, gde jegde je MMPMTPMT gubitakgubitak nana tabeletabele, , nnavravr· · x/x/22gubitakgubitak nana popunjenostpopunjenost poslednjeposlednje stranicestranice ((svakisvaki program program imaima popo
ETF-Beograd Performanse RačunarskihSistema
17
1 1 polupopunjenupolupopunjenu stranicustranicu na kojoj se gubi u proseku xna kojoj se gubi u proseku x/2/2))
3.5 Iskorišćenje memorije za slučaj virtuelne memorije organizovane u stranice(Virtuelna memorija – Straničenje na zahtev – Demand Paging)
• Šta ako se poslednja stranicaŠta ako se poslednja stranica (polupopunjena) ne nalazi u memoriji?
Poslednji izraz treba korigovati uključujući verovatnoću dastranica bude u memoriji.1/R - verovatnoću da je stranica u memoriji.Gubitak sa korekcijom:WW MM ++ //22 1/R1/RW= W= MMPMTPMT++nnavravr· · x/x/2 ·2 ·1/R1/R
ETF-Beograd Performanse Računarskih Sistema
18
3.5 Iskorišćenje memorije za slučaj virtuelne memorije organizovane u stranice(Virtuelna memorija – Straničenje na zahtev – Demand Paging)
MM N·kN·k dd jj NN b jb j tt kk ličiliči ll PMTPMTMMPMTPMT==N·kN·k gdegde je je NN brojbroj stranastrana , a , a kk veličinaveličina ulaza ulaza u PMTu PMTMMPROGPROG==N·xN·x , , gdegde je x je x velveličinaičina jednejedne stanicestanice
M= MM= MPMTPMT+M+MPROGPROG=(=(k+xk+x)·N)·N ⇒⇒ MMPMTPMT==k·Nk·N==k·Mk·M/(/(k+xk+x) ) iiPMTPMT PROGPROG (( )) PMTPMT /(/( ))sadasada imamoimamo::W= W= k·Mk·M/(/(k+xk+x))++nnavravr· · x/x/22 · · 1/R1/R≈≈k·Mk·M//xx++nnavravr· · x/x/22RRdWdW//dxdx== --k·Mk·M/x²/x²++nnavravr//22RRTraTražžimoimo minimalnuminimalnu vrednostvrednost WWminmin zaza xxoptopt ((dWdW//dxdx=0)=0) : :
optavr
MX 2 R k n= ⋅ ⋅ ⋅min avrW 2 k M n / R= ⋅ ⋅ ⋅
ETF-Beograd Performanse Računarskih Sistema
19
3.5 Iskorišćenje memorije za slučaj virtuelne memorije organizovane u stranice(Virtuelna memorija – Straničenje na zahtev – Demand Paging)
Ukupan gUkupan gubitakubitak jeje minimalanminimalan kada jekada je gubitakgubitak nana ½½ stranicestraniceUkupan gUkupan gubitakubitak je je minimalanminimalan kada jekada je gubitak gubitak nana ½ ½ stranicestranice((internainterna fragmentacijafragmentacija) ) jednakjednak gubitkugubitku nana PMTPMT ..kk··MM//xxoptopt== nnavravr ··xoptxopt/2/2RR ⇒⇒ gubicigubici nana polovinamapolovinama stranicastranica ii nanaPMTPMT susu jednakijednaki ZaZa x= 0 5 1 2 4x= 0 5 1 2 4 kBkB k=4Bk=4B ii M=200M=200 kBkB imamoimamo::PMT PMT susu jednakijednaki.. ZaZa x= 0.5, 1, 2, 4 x= 0.5, 1, 2, 4 kBkB, k=4B , k=4B ii M=200 M=200 kBkB imamoimamo::
x[B]navr
2 4 6 8 10 12 Globalno512 0.99 0.987 0.985 0.982 0.98 0.9771024 0.987 0.982 0.977 0.976 0.976 0.9622048 0.982 0.972 0.962 0.952 0.942 0.932
Globalno iskorišćenje je oko 95%
4096 0.972 0.952 0.932 0.912 0.892 0.872
U=(M-W)/M=1 - k/x - (navr ·x)/(2·M·R)Iskorišćenost:
ETF-Beograd Performanse Računarskih Sistema
20
( ) ( avr ) ( )Iskorišćenost:
3.6 Pregled iskorišćenja memorije za različite tehnike
Globalno iskorišćenje memorijeGlobalno iskorišćenje memorijeGlobalno iskorišćenje memorijeGlobalno iskorišćenje memorije
monoprogramski sistemi Globalno iskorišćenje memorije (GMU)
50 60 70 80 90 100l l l l l l 50%
statičke particije
dinamičke particije
relokativne particije
75%
85%
60%
p j
statičke stranice
DEMAND PAGING (virtuelna memorija)
80%
95%
DEMAND SEGMENTATION
DEMAND - PAGED SEGMENTATION
( )
90%
95%
ETF-Beograd Performanse Računarskih Sistema
21
Tehnika upravljanja memorijom (MMT)
4. Performanse operativne memorije (iskorišćenost i brzina)
11 veličinaveličina memorijememorije (size)(size) jedinicejedinice: Bytes/Words/Bits (B/w/b): Bytes/Words/Bits (B/w/b)1.1. veličinaveličina memorijememorije (size), (size), jedinicejedinice: Bytes/Words/Bits (B/w/b): Bytes/Words/Bits (B/w/b)2.2. vremevreme pristupapristupa (access time): (access time):
a) a) TTrr (read time)(read time)--vremevreme čitanjačitanja –– vreme koje protekne od trenutka vreme koje protekne od trenutka idavanja zahteva za čitanje do trenutka raspoloživosti podatka u baferuidavanja zahteva za čitanje do trenutka raspoloživosti podatka u baferuidavanja zahteva za čitanje do trenutka raspoloživosti podatka u baferuidavanja zahteva za čitanje do trenutka raspoloživosti podatka u baferu
b) b) TTww(write time)(write time)--vremevreme upisivanjaupisivanja vreme koje protekne od vreme koje protekne od trenutka idavanja zahteva za upis do trenutka sledeće moguće operacije trenutka idavanja zahteva za upis do trenutka sledeće moguće operacije procesoraprocesora
3.3. alternativnoalternativno: : TTrr –– najkracinajkraci vremenskivremenski interval interval izmedjuizmedju 2 2 uzastopnauzastopna čitanjačitanja jednejedne isteistememorijskememorijske lokacijelokacije. . NajveciNajveci deodeo vremenavremena TTrr predstavljapredstavlja interval interval odod
dd ll dd š kš k l kl k b fb fzadavanjazadavanja impulsaimpulsa do do završetkazavršetka prenosaprenosa iziz lokacijelokacije u u baferbafer registraregistra((znaznaččajnijeajnije zbogzbog mogumoguććnostinosti ponavljanjaponavljanja istogistog čitanjačitanja). ). TTww –– najkranajkraććii mogućimogući vremenskivremenski interval interval izmeizmeđđu 2 u 2 uzastopnauzastopna upisaupisa u u istuistumemorijskumemorijsku lokacijulokaciju
ETF-Beograd Performanse Računarskih Sistema
22
memorijskumemorijsku lokacijulokaciju..
4. Performanse operativne memorije (iskorišćenost i brzina)
44 memorijskimemorijski ciklusciklus (cycle time) je(cycle time) je najkranajkraććee vremevreme izmeizmeđđu 2u 2 uzastopnauzastopna čitanjačitanja iliili4.4. memorijskimemorijski ciklusciklus (cycle time) je (cycle time) je najkranajkraćće e vremevreme izmeizmeđđu 2 u 2 uzastopnauzastopna čitanjačitanja iliilipisanjapisanja u u istuistu memorijskumemorijsku lokacijulokaciju. Ne mo. Ne možžemoemo gaga koristitikoristiti zaza porepoređđenjeenje različitihrazličitihmemorijamemorija zbogzbog različiterazličite dužinedužine podatakapodataka. .
Tc=(Tr+Tw)/2
5.5. dužinadužina podatkapodatka kojikoji se se dohvatidohvati u u jednomjednom pristupupristupu WW (Width)(Width):: brojbroj bajtova bajtova ((BB)), , reči (reči (ww) ili bitova () ili bitova (bb)) kojikoji se se dohvatidohvati u u jednomjednom pristupupristupu..
66 širinaširina opsegaopsega memorijememorije BB ((BandWidthBandWidth) Ne) Ne možemože sese koristitikoristiti zaza porepoređđenjeenje kodkod
c r w
6.6. širinaširina opsegaopsega memorijememorije BB ((BandWidthBandWidth). Ne ). Ne možemože se se koristitikoristiti zaza porepoređđenjeenje kodkodviviššestrukuhestrukuh pristupapristupa. .
Na primer: Na primer: WW=32 b =32 b ii TTcc=0.4 =0.4 μμss ((mikromikro sekundisekundi) ) ⇒⇒ BB=80 =80 bb//μμss
Bmem=W/Tc [b/μs]
pp cc μμ (( )) μμ
7.7. brzinabrzina memorijememorije vvmemmem (memory transfer rate) (memory transfer rate) predstavljapredstavlja nana drugidrugi načinnačinzapisanzapisanu širinu opsegau širinu opsega: :
vmem = W/Tc[MB/s] = Bmem/8
ETF-Beograd Performanse Računarskih Sistema
23
mem c[ ] mem
4.1 Sistem sa više memorijskih modula
PretpostavkaPretpostavka:: sistem jesistem je sasa jednomjednom magistralommagistralom::PretpostavkaPretpostavka:: sistem jesistem je sasa jednomjednom magistralommagistralom::
Adresna magistralaEfektivna Adresa
Memorijski
Mar 1 Mar 2 Mar 3 Mar 4
Adresa
BlokMemorijski
KontrolerBlok #2 Blok #3 Blok #4Blok #1
Mbr 4Mbr 3Mbr 2Mbr 1Selektor Adrese Modula
Blok Memorije
CPUdužina podataka w brzina protoka v
Modula
upravljanje
ETF-Beograd Performanse Računarskih Sistema
24
dužina podataka w, brzina protoka vmem
4.2 Paralelni pristup memoriji
DelimoDelimo memorijumemoriju nana blokoveblokove UU slučajuslučaju dada visevise procesoraprocesora tratražžiiDelimoDelimo memorijumemoriju nana blokoveblokove. U . U slučajuslučaju dada visevise procesoraprocesora tratražžiipristuppristup istomistom blokubloku javljajujavljaju se se redoviredovi čekanjačekanja. . S(m)S(m) je je faktorfaktorsimultanostisimultanosti, , tjtj. . brojbroj memorijskihmemorijskih blokovablokova kojikoji susu istovremenoistovremenoaktivniaktivni.. S(m)mm--brojbroj memorijskihmemorijskih blokovablokova
•• EfektivnaEfektivna širinaširina opsegaopsega memorijememorije: :
S(m)
p gp g jjB=S(m)B=S(m) ·W/·W/TTcc ,, 11≤≤S(m) S(m) ≤≤m m
•• Neka se gNeka se generienerišše e sledećisledeći nizniz adresaadresa, , odnosnoodnosno njihovihnjihovih blokovablokova((pretpostavkapretpostavka je je dada susu generisanegenerisane adreseadrese nezavisnenezavisne ii dada se se
m
((p pp p jj ggsvakomsvakom odod blokovablokova sasa pristupapristupa ravnomernoravnomerno):):bb11, b, b22, … , , … , bbmm, b, bm+1m+1, …, … , b, bi i je je iziz skupaskupa {1,…,m}{1,…,m}
ETF-Beograd Performanse Računarskih Sistema
25
4.2 Paralelni pristup memoriji
Blok#3 Blok#4Blok#2Blok#1
MAR 1 MBR 4MAR 4MBR 3MAR 3MBR 2MAR 2MBR 1
m=4
CPU 1adresa
podatak
CPU 2
IOP 1
p
adresaKomutaciono
polje
IOP 2
podatakadresa
podatak
polje
ETF-Beograd Performanse Računarskih Sistema
26
4.3 Helermanova Formula
2 CPU2 CPU ii 2 IOP2 IOP (npr DMA)(npr DMA) generigeneriššuu nizniz blokovablokova bb:=:= bb11 bb222 CPU 2 CPU ii 2 IOP2 IOP (npr. DMA)(npr. DMA) generigeneriššu u nizniz blokovablokova bb:= := bb11, , bb22, … , , … , bbmm, , bbm+1, m+1, bbm+2 m+2 ,…,… pripri ččemu emu bbii ∈∈ {1,2,…,m} , {1,2,…,m} , ii=1, 2, 3, … =1, 2, 3, … ((mm--brojbroj memorijskihmemorijskih blokovablokova, n, n--brojbroj procesoraprocesora)). . PretpostavkaPretpostavka je je dada susu adreseadrese memeđđusobnousobno nezavisnenezavisne pa je pa je pristupanjepristupanje blokovimablokovima ravnomernoravnomerno..verovatnoćaverovatnoća dada sledećasledeća adresaadresa ne ne budebude istaista kaokao prethodnaprethodna: : PPrr[b[b22≠≠bb11]=(m]=(m--1)/m,1)/m, bb11-- prvaprva generisanagenerisana adresaadresa, , bb22--druga druga generisanagenerisana adresaadresa. . AnalognoAnalogno imamoimamo::
PP [b[b ≠≠bb bb ≠≠bb || bb ≠≠bb ]=(m]=(m--2)/m2)/mPPrr[b[b33≠≠bb22,, bb33≠≠bb1 1 | | bb22≠≠bb11]=(m]=(m--2)/m2)/mPPrr[[bbkk≠≠bbii ; ; za svako i, za svako i, 11≤≤i<k i<k ,, 11≤≤kk≤≤mm]=(m]=(m--(k(k--1))/m1))/mPPrr[[bbkk+1+1≠≠bbii ;; za svako i,za svako i, 11≤≤ii ≤≤ kk ,, 11≤≤kk≤≤m]=(mm]=(m--kk)/m)/m
ETF-Beograd Performanse RačunarskihSistema
27
PPrr[[bbkk+1+1≠≠bbii ; ; za svako i, za svako i, 11≤≤ii ≤≤ k k ,, 11≤≤kk≤≤m] (mm] (m kk)/m)/m
4.3 Helermanova Formula
verovatnoćaverovatnoća suprotnogsuprotnog dogadogađđajaaja (k+1(k+1 va adresa je već generisanava adresa je već generisanaverovatnoćaverovatnoća suprotnogsuprotnog dogadogađđajaaja (k+1(k+1--va adresa je već generisana va adresa je već generisana ranije)ranije):: PPrr[[bbk+1k+1∈∈ {{bb11,,bb22,…,,…,bbkk}] = }] = k/m k/m , , kk=1, 2, ..., =1, 2, ..., mmverovatnoćaverovatnoća dada ssee posleposle kk pristupa naredni ponovio, tj. da je kpristupa naredni ponovio, tj. da je k
ij kihij kih bl kbl k ktikti (( i lt ii lt i i ti t kk bl kbl kmemorijskihmemorijskih blokovablokova aktivnoaktivno ((simultanisimultani pristuppristup u k u k blokovablokovaistovremenoistovremeno):):
pp(k)= (m(k)= (m--1)/m· (m1)/m· (m--2)/m·…· (m2)/m·…· (m--(k(k--1))/m·1))/m·k/mk/m== k
k (m 1)!m (m k)!
−
SrednjiSrednji faktorfaktor simultanostisimultanosti,, tj.tj. srednjisrednji brojbroj modulamodula kojikojiistovremenoistovremeno raderade::
m (m k)!−
istovremenoistovremeno raderade::m m
2 k
k 1 k 1
S(m) k p(k) (m 1)! k /(m (m k)!)= =
= ⋅ = − ⋅ −∑ ∑
ETF-Beograd Performanse Računarskih Sistema
28
k 1 k 1= =
4.3 Helermanova Formula
Hele manHele man daodao p iblip ibližžanan ob a acob a acHelermanHelerman daodao priblipribližžan an obrazacobrazac: :
S(m) S(m) ≈≈ mm0.560.56
PrimerPrimer izračunavanjaizračunavanja S(m)S(m) popo tatačnojčnoj ii priblipribližžnojnoj formuliformuli::Primer Primer izračunavanjaizračunavanja S(m) S(m) popo tatačnoj čnoj ii priblipribližžnojnoj formuliformuli: : S(2)=1·1/2+2·1/2=S(2)=1·1/2+2·1/2=1.51.5 ; S(4)=71/32=; S(4)=71/32=2.222.22 ; ;
220.56 0.56 ==1.471.47 ; 4; 40.560.56 ==2.172.17AproksimacijaAproksimacija je je relativnorelativno grubagruba, , aliali je je obrazacobrazac jednostavanjednostavanZa Za 4 4 memorijskamemorijska blokabloka je je pod pod ovimovim uslovimauslovima okooko 22 putaputa brbržžii pristuppristup
Knuth (Donald ErvinKnuth (Donald Ervin KnuthKnuth)) :(( ))S(m) 1.253 m 0.28;≈ ⋅ −
3/4S(m) ( m) / 2 1/ 3 1/12 / (2 m) 4 / (135 m) o(m )−= π ⋅ − + ⋅ π ⋅ − ⋅ +
prva aproksimacija
d k i ij
ETF-Beograd Performanse Računarskih Sistema
29
druga aproksimacija
4.3 Helermanova Formula
MM t č f l i l d j k i tit č f l i l d j k i tiManManaa tačne formule i poslednjeg aproksimativnog tačne formule i poslednjeg aproksimativnog obrasca jeobrasca je prevelikaprevelika slosložženostenost..DDolazimoolazimo dodo efekti neefekti ne ši ineši ine opsegaopsega memo ijememo ijeDDolazimoolazimo do do efektivneefektivne širineširine opsegaopsega memorijememorije(EŠOM)(EŠOM)::
B =m0 56 W/T m≥1
HELERMANOVA FORMULAHELERMANOVA FORMULA
Bmem=m0.56 ·W/Tc, m≥1
ETF-Beograd Performanse Računarskih Sistema
30
4.4 Barnet-Kofmanova formula
OvoOvo je proje prošširenjeirenje HelermanoveHelermanove formuleformule kojekoje uzimauzima uu obzirobzir svojstvasvojstvaOvoOvo je proje prošširenjeirenje HelermanoveHelermanove formuleformule koje koje uzimauzima u u obzirobzir svojstvasvojstvaizvrizvrššenjaenja programaprograma na nivou bazičnih blokovana nivou bazičnih blokova ((posmatraposmatra slučajslučajeveevekadakada postojepostoje skokoviskokovi u u programuprogramu) ) OOdnosidnosi sese nana brojbroj instrukcijainstrukcija kojekoje sese istovremenoistovremeno mogumogu čitati izčitati izOOdnosidnosi se se nana brojbroj instrukcijainstrukcija kojekoje se se istovremenoistovremeno mogumogu čitati iz čitati iz memorijememorije. . U U slučajuslučaju instrukcijinstrukcijaa bezbez skokovaskokova,, zahvatazahvata se se onolikoonoliko reči reči kolikokoliko imaimablokovablokova (mo(možžemoemo istovremenoistovremeno zahvatatizahvatati razlirazliččiteite instrukcijeinstrukcije iziz 44blokovablokova (mo(možžemoemo istovremenoistovremeno zahvatatizahvatati razlirazliččiteite instrukcijeinstrukcije iziz 4 4 blokabloka u našem slučajuu našem slučaju). ). U U slučajuslučaju pojavepojave skokovaskokova efektivnaefektivna širinaširina operativneoperativne memorijememorije se se smanjujesmanjuje,, tj.tj. smanjujesmanjuje sese brojbroj jednovremenojednovremeno zahvazahvaććenihenihsmanjujesmanjuje, , tj. tj. smanjujesmanjuje se se brojbroj jednovremenojednovremeno zahvazahvaććenihenihinstrukcijainstrukcija. . IstoIsto je je ii u u slučajuslučaju grananjagrananja (uslovnih skokova)(uslovnih skokova), , smanjujesmanjuje se se srednjisrednjifaktorfaktor simultanostisimultanosti. EŠOM je f. EŠOM je funkciunkcijaja brojabroja instrukcijainstrukcija sasa skokovimaskokovima
ETF-Beograd Performanse Računarskih Sistema
31
faktorfaktor simultanostisimultanosti. EŠOM je f. EŠOM je funkciunkcijaja brojabroja instrukcijainstrukcija sasa skokovimaskokovimanana neuzastopnuneuzastopnu adresuadresu..
4.4 Barnet-Kofmanova formula
q jeq je verovatnoćaverovatnoća skokaskoka nana neuzastopnuneuzastopnu adresuadresu ((qq==brojbrojq je q je verovatnoćaverovatnoća skokaskoka nana neuzastopnuneuzastopnu adresuadresu ((qq==brojbrojinstrukcijainstrukcija sasa skokovimaskokovima//ukupanukupan brojbroj mamaššinskihinskih instrukcijainstrukcija). ). Npr, Npr, aakoko je q=0.1 je q=0.1 imamoimamo skokskok u u svakojsvakoj desetojdesetoj adresiadresi..ImamoImamo sekvencusekvencu uzastopnihuzastopnih adresaadresa b1 b2b1 b2 memorijskihmemorijskihImamoImamo sekvencusekvencu uzastopnihuzastopnih adresaadresa b1, b2, … b1, b2, … memorijskihmemorijskihblokovablokova kojimakojima se se pristupapristupa, , sasa pprosečnomrosečnom dužinomdužinom 1/q 1/q stosto je je proseproseččan an brojbroj uzastopnihuzastopnih adresaadresa ((srednjasrednja dužinadužina linearnoglinearnog deladelaprogramaprograma bezbez skokovaskokova))programaprograma, , bezbez skokovaskokova).).r=1r=1--qq -- verovatnoćaverovatnoća instrukcijainstrukcija kojekoje ne ne dovodedovode do do skokaskoka((gustinagustina instrukcijeinstrukcije bezbez skokovaskokova). ). PosmatramoPosmatramo verovatnoćverovatnoćuu dada nizniz instrukcijainstrukcija kojekoje sese mogumoguPosmatramo Posmatramo verovatnoćverovatnoćuu dada nizniz instrukcijainstrukcija kojekoje se se mogumoguparalelnoparalelno izvršavatiizvršavati imaima dužinudužinu kk, što znači da, što znači da imamoimamo kk--1 1 instrukcijuinstrukciju bezbez skokaskoka,, a a da da kk--tata izazivaizaziva skokskok: :
ETF-Beograd Performanse Računarskih Sistema
32
4.4 Barnet-Kofmanova formula
p(k) rp(k) rkk--11q 1q 1 ≤≤ kk ≤≤ mm 1 ; p(m) r1 ; p(m) rmm--11 ( j iš( j iš 11 i t k iji t k ijp(k)=rp(k)=rkk--11q , 1 q , 1 ≤≤ k k ≤≤ mm--1 ; p(m)=r1 ; p(m)=rmm--11 (najviše (najviše mm--11 instrukcijainstrukcijabezbez skokaskoka,, a a zaza mm--tutu nijenije bitnobitno ukolikoukoliko imamoimamo m m blokovablokova))
m2 m 2 m 1S(m ) k p(k ) q 2rq 3r q (m 1) r q mr− −= ⋅ = + + + + − ⋅ ⋅ +∑
uvodimo smenu q=1-rk 1
S(m ) k p(k ) q 2rq 3r q ... (m 1) r q mr=
= = + + + + +∑
2 2 3 m 2 m 1 m 1 2 m 1S( ) 1 2( ) 3( ) ( 1)( ) 1− − − −
S(m)=(1-rm )/(1-r)=(1-(1-q) m )/(1-(1-q))= (1-(1-q) m )/qEŠOM: W(bits) širina instrukcije Tc(μs) trajanje memorijskog ciklusa
2 2 3 m 2 m 1 m 1 2 m 1S(m) 1 r 2(r r ) 3(r r ) ... (m 1)(r r ) m r 1 r r ... r= − + − + − + + − − + ⋅ = + + + +
EŠOM: W(bits) - širina instrukcije, Tc(μs) – trajanje memorijskog ciklusa
1-(1-q)m WBmem = ——— · — BARNET-KOFMANOVA FORMULA
ETF-Beograd Performanse Računarskih Sistema
33
q Tc Burnett - Coffman
4.4 Barnet-Kofmanova formula
Primer: q=0 1Primer: q=0 1:: S(2)=1 9 S(4)=3 44 S(8)=5 7 S(16)=8 15 ;S(2)=1 9 S(4)=3 44 S(8)=5 7 S(16)=8 15 ;Primer: q 0.1Primer: q 0.1: : S(2) 1.9, S(4) 3.44, S(8) 5.7, S(16) 8.15 ; S(2) 1.9, S(4) 3.44, S(8) 5.7, S(16) 8.15 ; GraniGraniččnini slučajevislučajevi: S(1)=1 ; ; 1 : S(1)=1 ; ; 1 ≤≤ S(m) S(m) ≤≤ mm
OdOd BB CC f lf l ii H lH l f lf l
q 0limS(m) m
→=
OdnosOdnos BB--C C formuleformule ii HelermanHelerman--oveove formuleformule::
qq=?=?1-(1-q)m
m0.56 = ———
BB--C jeC je preciznijapreciznija,, boljebolje sagledavasagledava realnostrealnost.. HelermanovaHelermanova jeje
m = ———q
BB C je C je preciznijapreciznija, , boljebolje sagledavasagledava realnostrealnost. . HelermanovaHelermanova je je jednostavnijajednostavnija ii ne ne zahtevazahteva poznavanjepoznavanje programaprograma..BB--CC je pogodna za primenu u instrukcijskim memorijama (one je pogodna za primenu u instrukcijskim memorijama (one koje sadrže samo kod), npr. cache memorija za instrukcije.koje sadrže samo kod), npr. cache memorija za instrukcije.
ETF-Beograd Performanse Računarskih Sistema
34
koje sadrže samo kod), npr. cache memorija za instrukcije.koje sadrže samo kod), npr. cache memorija za instrukcije.
4.5 Strekerova formula (procena brzine memorije)
PretpostavkePretpostavke susu dada imamoimamo nn procesoraprocesora kojikoji pristupajupristupajuPretpostavkePretpostavke susu dada imamoimamo nn procesoraprocesora kojikoji pristupajupristupajumemorijskimmemorijskim blokovimablokovima kojihkojih imaima mmSvakomSvakom odod blokovablokova pristupapristupa se se nezavisnonezavisno ii ravnopravnoravnopravno ((sasajednakomjednakom veroverovvatnoatnoććee uniformnauniformna raspodelaraspodela verovatnoverovatnoćeće zazajednakomjednakom veroverovvatnoatnoćće e –– uniformnauniformna raspodelaraspodela verovatnoverovatnoće će zazapristupepristupe blokovimablokovima). ). VerovatnoćaVerovatnoća dada ii--titi procesorprocesor pristupapristupa jj--tom tom memorijskommemorijskom blokubloku: : PP [[ii titi i ti t jj tt bl kbl k ] 1/] 1/PPrr[[ii--titi proc.proc. pristupapristupa jj--tom tom memmem.. blokubloku]=1/m]=1/m, , 1 1 ≤≤ ii ≤≤ n , 1 n , 1 ≤≤ j j ≤≤ mmverovatnoćaverovatnoća suprotnogsuprotnog dogadogađđajaaja, , dada ii--titi procesorprocesor ne ne pristupapristupa jj--tom tom blokubloku: : PPrr=1=1--1/m1/m..verovatnoćaverovatnoća dada je jje j--titi blokblok slobodanslobodan, , tjtj. . dada mu mu nikoniko ne ne pristupapristupa: : PPr[r[jj--titi blokblok slobodanslobodan]=(1]=(1--1/m)1/m)nn
ETF-Beograd Performanse Računarskih Sistema
35
PPr[r[jj titi blokblok slobodanslobodan] (1] (1 1/m)1/m)
4.5 Strekerova Formula (procena brzine memorije)
VerovatnoćaVerovatnoća dada je jje j--titi blokblok zauzetzauzet, , tjtj. . vverovatnoerovatnoća ća suprotnogsuprotnogj jj j ,, jj p gp gdogadogađđajaaja: :
PPr[jr[j--titi blokblok zauzetzauzet]=1]=1--(1(1--1/m)1/m)nn
SFS: SFS: S(m)=[1-(1-1/m)n ] ·m
EŠOM :EŠOM :
Primer: n=4 Primer: n=4 procesoraprocesora , m=2,4,6,8, m=2,4,6,8 memmemorijskih orijskih blokovablokova
Bmem=m·[1-(1-1/m)n ] · W/Tc Strecker-ova formula
pp , , , ,, , , , jjS(2)=1.875, S(8)=3.31, S(2)=1.875, S(8)=3.31, S(4)=2.73, S(4)=2.73, S(16)=3.64 S(16)=3.64
mlimS(m) n→∞
=nlimS(m) m→∞
=
ETF-Beograd Performanse RačunarskihSistema
36
4.5 Strekerova Formula (procena brzine memorije)
OdnosOdnos StrekeroveStrekerove formuleformule ii HelermanoveHelermanove formuleformule::OdnosOdnos StrekeroveStrekerove formuleformule ii HelermanoveHelermanove formuleformule::
m0.56= m·[1-(1-1/m)n] i ako je n(m)=Log(1-m-0.44)/Log(1-m-1) f l i t t
Primer: Primer: pronaćipronaći n(2),n(2), n(4),n(4), n(6),n(6), n(8) n(8) dada postojipostoji ekvivalentnostekvivalentnost
⇒ formule su istovetne
pp ( ),( ), ( ),( ), ( ),( ), ( )( ) p jp jStrekerova Strekerova ii Helermanove Helermanove formuleformule::mm==2 => n=1.932 => n=1.93m=4 => n=2 72m=4 => n=2 72m 4 > n 2.72m 4 > n 2.72m=8 => n=3.83 m=8 => n=3.83 m=16 => n=5.42m=16 => n=5.42
ETF-Beograd Performanse RačunarskihSistema
37
4.6 Hijerarhijska organizacija memorije
Izračunavanje efektivne adresne
-registri
-cache
Page# Adresa unutar stranice
Page Map Table PMT
logička adresastranica nije u memoriji
-operativna mem.
-disk
Table PMT
Block# Adresa unutar bloka
MAR
fizička adresa1-ff- verovatnoća (page fault)
-CD-ROM
-magnetne trakeAsocijativna memorija
Cache
strana
(page)
1-h cache hith
• Po smeštajnoj jedinici cena opada, a raste kapacitet
Operativna memorija
Cache memorija
tm
tb
ETF-Beograd Performanse Računarskih Sistema
38MBRtf
cpu
4.6 Hijerarhijska organizacija memorije
TT d jd j i ti t t i kt i k hij hijhij hijTTcc3 3 -- ssrednjerednje vremevreme pristupapristupa zaza tronivoovskutronivoovsku hijerarhijuhijerarhiju::TTcc33==f·tf·tff+(1+(1--f)·f)·TTcc ,, gdegde je je TTcc srednjesrednje vremevreme pristupapristupa zaza22--nivovsku nivovsku hijerarhijuhijerarhiju
Tc=h·tb+(1-h)·tm =tm·[1-h·(1-tb/tm)] , tb<tm<tf
W W 1 WBmem = ——————— = — · ————— = — · H
tm·[1-h·(1-tb/tm)] tm 1-h·(1-tb/tm) tm
W/tm je polazna širina memorijskog opsega bez keš memorije
ETF-Beograd Performanse Računarskih Sistema
39
4.6 Hijerarhijska organizacija memorije
Ti iTi i l k l til k l tiTipoviTipovi lokalnostilokalnosti::•• vremenskavremenska –– velikavelika verovatnoćaverovatnoća dada cece se u se u
odreodređđenomenom vremenskomvremenskom intervaluintervalu pristupatipristupati podacimapodacimaodreodređđenomenom vremenskomvremenskom intervaluintervalu pristupatipristupati podacimapodacimakojimakojima smosmo vevećć pristupalipristupali u tom u tom vremenskomvremenskom intervaluintervalu
•• prostornaprostorna –– velikavelika verovatnoćaverovatnoća dada akoako smosmo pristupilipristupiliććnekomnekom podatkupodatku brzobrzo ććemoemo pristupitipristupiti podatkupodatku kojikoji mu mu
je je blizakblizak popo adresiadresi (u (u istomistom blokubloku))•• procesorskaprocesorska –– odnosiodnosi sese nana multiprocesorskemultiprocesorske sistemesisteme•• procesorskaprocesorska odnosiodnosi se se nana multiprocesorskemultiprocesorske sistemesisteme
ETF-Beograd Performanse Računarskih Sistema
40
4.6 Hijerarhijska organizacija memorije
PresekPresek tipitipiččnihnih vremenavremena pristupapristupa ii kapacitetakapaciteta::PresekPresek tipitipiččnihnih vremenavremena pristupapristupa ii kapacitetakapaciteta::
Vreme: Kapacitet:11--2 ns 322 ns 32--512 B512 B
33--10 ns 110 ns 1--512512 kBkB
2525--50 ns 6450 ns 64--22048048 kBkB
RegistriCache (on chip)Cache (off chip)
Vreme: Kapacitet:
6060--250 ns 1MB 250 ns 1MB –– 22GBGB
55--20 ms 100MB 20 ms 100MB –– 1TB1TB
100100--500 ms 600 MB+500 ms 600 MB+
Cache (off chip)Operativna memorija
DiskTercijarna memorija (CD DVD)100100--500 ms 600 MB+500 ms 600 MB+
1s1s--10 min 10 min nijenije limitiranolimitirano
Tercijarna memorija (CD, DVD)Trake
ETF-Beograd Performanse Računarskih Sistema
41