Pamět ová hierarchie, návrh skryté paměti 2. doc. Ing. Róbert Lórencz, CSc

Architektura poˇcítaˇcových systému˚ ˇ ˇ 2 Pamet’ová hierarchie, návrh skryté pameti

doc. Ing. Róbert Lórencz, CSc.

ˇ Ceské vysoké uˇcení technické v Praze Fakulta informaˇcních technologií Katedra poˇcítaˇcových systému˚

ˇ Pˇríprava studijních programu˚ Informatika pro novou fakultu CVUT je spolufinancována Evropským sociálním fondem ˇ a rozpoˇctem Hlavního mesta Prahy v rámci Operaˇcního programu Praha — adaptabilita (OPPA) projektem ˇ CZ.2.17/3.1.00/31952 – „Pˇríprava a zavedení nových studijních programu˚ Informatika na CVUT v Praze“. Praha & EU: Investujeme do vaší budoucnosti

ˇ R. Lórencz (CVUT FIT)

ˇ ˇ 2 Pamet’ová hierarchie, návrh skryté pameti

BI-APS, 2011, Pˇredn. 6.-7.

1 / 20

Obsah pˇrednášky

zpusoby ˚ zápisu velikost bloku typy výpadku˚ ˇ (fully associative cache) plneˇ asociativní skrytá pamet’ ˇ asociativity cache s omezeným stupnem ˇ obeti ˇ strategie výberu redukce výpadku˚




2 / 20

Pˇrímo mapovaná cache - zpusob ˚ zápisu 1

Pˇrímý zápis – Write-through ˇ souˇcasný zápis slova do pamet’ového bloku cache a na ˇ odpovídající místo v pameti ˇ souˇcasný zápis do cache a do hlavní pameti ˇ vždy je prováden jednoduchý, ale pomalý zpusob ˚ udržování shodného obsahu ˇ cache a pameti ˇ ˇ vyžaduje zapisovací buffer – write zatežuje komunikaci s pametí, buffer




3 / 20

Pˇrímo mapovaná cache - zpusob ˚ zápisu 2 Odložený zápis – Write-back (copy back) obnovit obsah slova jen v cache a na odpovídajícim místeˇ v ˇ ponechat puvodní pameti ˚ slovo I

I

pˇridat dirty bit každé ˇrádce cache, který indikuje potˇrebu zápisu ˇ v pˇrípade, ˇ že blok slova z cache na odpovídajíci místo v pameti obsahující slovo bude z cache nahrazen jiným slovem ˇ obsahem OS musí pˇred operací I/O aktualizovat obsah pameti cache!!

zápis dat jen do cache, zápis hodnoty slova z bloku cache do ˇ se provádí jen když je dany blok, který je oznaˇcený drity pameti ˇ bitem, z cache odstranovaný rychlý, ale implementaˇcní složitejší, než write-through ˇ prolém konzistence obsahu cache a hlavní pameti




4 / 20

Pˇrímo mapovaná cache - velikost bloku 1 ˇ Výhody vetších bloku˚ ⇒ využití peostorové lokality ˇ blok obsahuj více slov v blízkostí požadovaného slova vetší ˇ blok ⇒ víc instrukcí po sobeˇ jdoucích nbo víc dat jednoho vetší pole ˇ Nevýhody vetších bloku˚ ˇ blok zpusobuje ˇ miss penalty vetší ˚ více výpadku, ˚ vetší ˇ k naˇctení vetšího bloku z nižší úrovneˇ potˇrebujem více cˇ asu, než k ˇ naˇctení menešího bloku pro velké velikosti bloku˚ vzhledem k velikosti cache existuje jen málo bloku˚ v cache a tak roste miss rate Miss Penalty

+ Velikost bloku


Miss Vyu ¡ ití prost. lokality Rate Vyuz Ménì blokù: Ménì blokù: ¡ menší vyuzití využití èas. lokality Velikost bloku

=


Prùmìrná doba pøístupu Miss Penalty & Miss Rate Velikost bloku


5 / 20

Pˇrímo mapovaná cache - velikost bloku 2 Extrémní pˇrípad: jeden velký blok Bit platnosti

Cache data

Klíè W3

W2

W1 W0

velikost cache = 4 slová = 16 B

Proè nemáme index?

velikost bloku = 16 B jenom jeden vstup do cache! ˇ je pravdepodobné, že zpracovávaná položka bude znovu žádaná ˇ ˇ je ale méneˇ pravdepodobné, že bude žádaná bezprostˇredne! ˇ potom je prevdepodobné, že další pˇrístup do cache bude výpadek (miss) musí se naˇcíst požadovaných data a nahradit puvodní ˚ blok novým nahrazená data mužou ˚ být, ale požadovaná v dalších krocích: noˇcní mura ˚ navrháˇru˚ cache: ping pong efekt. ˇ R. Lórencz (CVUT FIT)



6 / 20

Pˇrímo mapovaná cache - AMAT ˇ ˇ Prum ˚ erná doba pˇrístupu do pameti Average Memory Access Time – AMAT AMAT = HT + MP × MR HT = Hit Time cˇ as potˇrebný pro nalezení a získaní hledané položky v cache ˇ MP = Miss Penalty prum ˚ erný cˇ as získaní dat z nižší úrovneˇ ˇ pamet’ové hierarchie pˇri nenalezení hledané položky v ˇ cache(zahrnuje také detekci MR a pˇredání dat procesoru) ˇ ˇ HR = Hit Rate pomerná úspešnost nalezení dat v cache k ˇ celkovému poˇctu˚ pˇrístupu˚ do pameti MR = 1 - HR = Miss Rate




7 / 20

Pˇrímo mapovaná cache - typy výpadku˚ Studené výpadky – Compulsory misses vyskytují se po startu poˇcítaˇce cache po startu neobsahuje žádná data ⇒ výskyt studených ˇ cache výpadku˚ až do naplnení Konfliktní výpadky – Conflict misses Výpadky, které se vyskytují z duvod ˚ u, ˚ že 2 a více rozdílných adres ˇ jsou mapováná na stené místo v cache pameti 2 a víc bloku˚ jsou mapované do toho samého místa v cache (stejný index), pˇrítomnost jedného bloku v cache vyluˇcuje pˇrítomnost jiného bloku s tím samým indexem Problém u DM cache, ˇrešení jak zmenšit konfliktní výpadky: 1

ˇ ˇ zvetšit velikost cache, zvetšení je ale limitováná

2

ˇ bloku˚ pro ten samý index mít vícenásobné umístení ˇ R. Lórencz (CVUT FIT)



8 / 20

Plneˇ asociatívní cache – popis Fully Associative Cache ˇ Pamet’ové adresní pole: Klíˇc & Offset: stejné jako u DM a FA cache Index: neexistuje ⇒ ˇ kdekoliv v cache neexistují ˇrádky, každý blok muže ˚ být umíten hledat se musí podle Klíˇce v celé cache, jestli se požadováná data ˇ nekde nenacházejí Výhoda: neexistují konfliktní výpadky (s definice), protože data mužou ˚ být kdekoliv Neýhoda:potˇreba množství HW komparátoru˚ pro každý jednotlivý blok Kapacitní výpadky – Capacity misses: základní typ výpadku˚ pro plneˇ asociatívní cache výpadký zpusobené ˚ omezenou kapacitou plneˇ asociatívní cache ˇ zmenšení kapacitních výpadku˚ dosáhneme zvetšením velikosti cache (limitováno) ˇ R. Lórencz (CVUT FIT)



9 / 20

Plneˇ asociatívní cache – pˇríklad Pˇríklad: 64 KB cache, 32 bit adresa, velikost bloku = 32 B Potˇrebujeme: 2 K x 27-bit komparátoru˚ – nereálné! Klíè (27 b) Data Byte 31

=

Byte 63

=

:

Klíè

Byte 1 Byte 0

:

Platnost

Offset (5 b)

Byte 33 Byte 32

= = :

:

:

=




10 / 20

ˇ asociativity – popis 1 Cache s omezeným stupnem N-Way Set Associative Cache ˇ Pamet’ové adresní pole: Klíˇc & Offset: stejné jako u DM cache Index: Ukazuje na ˇrádek, který obsahuje tzv. set ˇ každý set: obsahuje nekolik bloku! ˚ když chceme najít hledané slovo v blocích jednoho setu (ukazuje ˇ index), musíme porovnat všechný klíˇce pˇrísluchající blocím na nej s klíˇcem adresy požadovaného slova Shrnutí: ˇ cache s omezeným stupnem asociativity je pˇrímo mapovaná s ohledem na sety každý set je plneˇ asociatívní ˇ tj. v podstateˇ N pˇrímo mapovaných caches pracuje paralelne, každý blok má svuj ˚ bit platnosti a data ˇ R. Lórencz (CVUT FIT)



11 / 20

ˇ asociativity – popis 2 Cache s omezeným stupnem ˇ Cinnost cache je daná adresa požadovaného slova adresuje se set odpovídající indexu porovná se klíˇc žádaného slova s klíˇcí bloku˚ v setu výpadek pokud neni nalezena shoda ani s jedním klíˇcem pokud hit potom použití offsetu k adresaci hledaného slova v daném bloku ˇ asociativity: Výhoda cache s omezeným stupnem již cache s N=2 vylouˇcí množství konfliktních výpadku˚ ˇ HW není o moc složitejší, vyžaduje jen N komparátoru˚ navíc atd. ˇ N ⇒ vetší ˇ hir rate, protože víc bloku˚ pameti ˇ se stejným vetší indexem muže ˚ být pamatováno v cache Cache s omezeným stupenˇ asociativity N a s M bloky v sete je: DM cache ⇔ N = 1 plneˇ asociatívní cache ⇔ N = M ˇ R. Lórencz (CVUT FIT)



12 / 20

ˇ asociativity – popis 3 Cache s omezeným stupnem Blok 12 je umíst’ován v 8 blokové cache: plneˇ asociatívní pˇrímo mapované ˇ asociativity N=2 s omezeným stupnem èíslo setu = èíslo bloku % # setù Plnì asociativní: blok 12 umístìn kdekoliv Èíslo bloku

01234567

Pøímo mapovaná: blok 12 umístìn jen do bloku 4 (12 mod 8) Èíslo 0 1 2 3 4 5 6 7 bloku

Omezený stupeò: blok 12 umístìn do setu 0 (12 mod 4) Èíslo 01234567 bloku

Set Set Set Set 0 1 2 3




13 / 20

ˇ asociativity – popis 4 Cache s omezeným stupnem Pøíklad organizace cache 8 bloková cache

# blokù = N




14 / 20

ˇ asociativity – popis 5 Cache s omezeným stupnem Example: 4 KB N=4 cache, 4 × 1024 B, velikost bloku = 4 B (1 slovo)




15 / 20

ˇ obeti ˇ – prinipy Strategie výberu Pˇrímo mapovaná cache: ˇ en. ˇ úplneˇ specifikuje blok, který má být vymen ˇ asociativity: Cache s omezením stupnem index specifikuje set, ale blok muže ˚ obsadit, kteroukoliv pozici uvnítˇr setu. Plneˇ asociatívní cache: blok muže ˚ obsadit kterýkoliv blok v cache. ˇ kam zapsat nový blok, pak jak vybrat místo? Pokud máme na výber, ˇ Rešení: když je bit platnosti nula potom nový blok na dané místo když dané místo obsahuje blok s platným bitem platnosti, potom se musí urˇcit pravidlo, které urˇci blok, který má být nahrazen novým blokem ˇ R. Lórencz (CVUT FIT)



16 / 20

ˇ obeti ˇ – LRU Strategie výberu Nejméneˇ používaná položka – LRU (Least Recently Used): ˇ blok v setu, kterého slova byla nejméneˇ cˇ tena/zapisovana vymenit Výhoda: využíva cˇ asovou lokalitu ⇒ zvyšuje hit rate pˇri N=2 je velmi jednoduché udržovat informaci o nejméneˇ používané položce v setu (1 LRU bit) Neýhoda: ˇ pˇri N>2 je HW komplikovanejší, cˇ asová složitost pro udržení LRU informace také roste Pˇríklad: Máme cache s N=2, která má kapacitu 4 slov a bloky velikosti jednoho slova. Budeme vykonávat cˇ tení slov na adresách: 0, 2, 0, 1, 4, 0, 2, 3, 5, 4. Kolik hitu˚ a kolik výpadku˚ bude pˇripadat pro stratégii ˇ obeti ˇ ppomocí LRU? výberu ˇ R. Lórencz (CVUT FIT)



17 / 20

ˇ obeti ˇ – LRU 2 Strategie výberu Adresesa: 0, 2, 0, 1, 4, 0, ...

loc 0 loc 1 0 lru

• 0: miss, zápis do set 0 (loc 0)

set 0 set 1


set 0 set 1

• 0: hit

set 0 set 1

0 lru 2


set 0 set 1

0 lru 2 1 lru

• 4: miss, zápis do set 0 (loc 1, replace 2)

set 0 set 1

• 0: hit

set 0 set 1



lru 0

lru

2

4 0 lru 1 0 lru 4 1 lru


18 / 20

ˇ obeti ˇ – LRU vs. Random Strategie výberu ˇ obeti ˇ Miss rates v porovnání LRU ) versus Random strategie výberu

Asociativita Velikost 16 KB 64 KB 256 KB

N=2 LRU Random 5.2% 5.7% 1.9% 2.0% 1.15% 1.17%

N=4 LRU Random 4.7% 5.3% 1.5% 1.7% 1.13% 1.13%

N=8 LRU Random 4.4% 5.0% 1.4% 1.5% 1.12% 1.12%

Je jen malý rozdíl Miss rate pro LRU a Random v pˇrípadeˇ velkých caches




19 / 20

Rešdukce Miss rate 1 Doposud známe Redukci Miss rate: ˇ zvetšení velikosti bloku ˇ zvetšení N (stupneˇ asociativity) ˇ cache Vetší limitováno cenou a technologii Hit time L1 cache < doba taktu ˇ obeti ˇ Miss rates v porovnání LRU ) versus Random strategie výberu

Asociativita Velikost 16 KB 64 KB 256 KB

N=2 LRU Random 5.2% 5.7% 1.9% 2.0% 1.15% 1.17%


N=4 LRU Random 4.7% 5.3% 1.5% 1.7% 1.13% 1.13%


N=8 LRU Random 4.4% 5.0% 1.4% 1.5% 1.12% 1.12%


20 / 20

Pamět ová hierarchie, návrh skryté paměti 2. doc. Ing. Róbert Lórencz, CSc

Recommend Documents