04 - Hierarchie pamětí v počítači

vyplňuje nám mezeru mezi procesorem a pamětí

v počítači máme základní úrovně pamětí:

vnitřní paměť procesoru - registry, registrové, zásobníky, fronty, tabulky, …

hlavní pamět (RAM) včetně rychlých vyrovnávacích pamětí

vnější paměti (disky) včetně vyrovnávacích pamětí

Paměti v počítači

snažíme se mít co nejlepší parametr výkon/cena

chceme vykonat co nejvíce instrukcí za časovou jednotku

potřebujeme paměti, které udrží informace i po vypnutí počítače

procesor je rychlý → potřebujeme mít paměť, která mu dodá rychle data

chceme, aby paměť byla levná

je složité docílit všech podmínek najednou → vzniká více druhů pamětí, kde každý druh má nějaká specifika (výhody/nevýhody) → jednotlivé paměti nám pak tvoří hierarchii

Hierarchie pamětí

Zkoumáním se zjistily tyto poznatky

časová lokalita

pokud procesor používá nějakou položku často, je vhodné ji mít uchovanou co nejblíže procesoru

proměnná i v cyklu for ⇒ budeme ji často používat

prostorová lokalita

položky, které jsou uloženy v paměti blízko zmiňované položky budou s vysokou pravděpodobností také často používány

procházíme položky v poli ⇒ používáme i sousední položky

Základní pojmy

stálost obsahu

volatnilní - potřebuje k uchování informací napájecí napětí

nevolatilní - nepotřebuje k uchování informací napájecí napětí

destruktivní - po cyklu čtení se data vymažou - je třeba udělat cyklus zpětného zápisu

doba uchování informace

SRAM - statická - uchová si informace dlouho při dodržení jistých parametrů

DRAM - dynamická - rychle informace zapomene - třeba udělat refresh

rychlost

přístupová doba - doba od zahájení čtení po získání obashu paměťového místa

doba cyklu - doba od zahájění čtení/zápisu do skončení operace, kdy je možno spustit další operaci

přenosová rychlost - data/čas

kapacita - N x n bitů (16K x 1bit)

reprezentuje strukturu paměti

64 K x 1 B

šířka datové sběrnice ⇒ 1 Byte

máme 64 K položek, kde každá položka má 1 Byte šířku

výkonnost - souhrn kapacity, přístupové doby a rychlosti

chybovost - např. počet chyb/1000 hodin

poruchovost

střední doba mezi poruchami

např flashku s velkou kapacitou nelze vyrobit tak, aby všechny položky byly bezchybové ⇒ je tam více bloků, než je kapacita a poté co se otestují, tak se zapojí ty, co fungují (levnější)

přístup k datům

s libovolným přístupem - přístupová doba nezávisí na umístění položky, (RAM - random access memory)

se sériovým přístupem - závisí na umístění (přisunutí čtecí hlavy), (SAM - serial access memory)

se smíšeným přístupem - několik (RAM) záznamových povrchů (SAM)

výběr z paměti

adresový

adresový prostor je uspořádaný a souvislý

koncept RAM ⇒ adresový dekodér → 10b adresa → 2^10 vodičů z adresového dekodéru do datové části

asociativní

není tak častá

vyhledáváme podle obsahu (klíčů) (ve všech řádcích musí být komparátor adres - klíčů)

např. vyhledáváme podle příjmení lidí (nemusí být podle abecedy)

paměť v daný čas porovná (neg(XOR)) paralelně se všemi klíči každý bit (zabírá hodně místa na chipu - N * n XOR členů)

pamět dobře umí za krátkou dobu najít data podle dané informace (např. z interentu proudí data ⇒ vyextrahujeme určité části a porovnáváme, jestli nesou charakteristiku viru) ⇒ softwarově by se to řešilo složitým algoritmem a bylo by to pomalé

Výběr z paměti

fyzikální vlastnosti pamětí

polovodičové - tato kapitola

bipolární

unipolární MOS resp. CMOS

magnetické - viz PZ

optické

molekulární

měnitelnost obsahu paměti

RWM - Read/Write Memory

RAM - (SRAM, SSRAM)

DRAM

ROM - Read Only Memory

PROM - pouze jedno naprogramování (čisté naprogramování)

EPROM - dá se vymazat (UV záření) a znovu naprogramovat

EEPROM - elektricky vymazatelná paměť (různé modifikace - Flash EEPROM, …)

Další téma, které se zabývá pamětmi naleznete zde. Konkrétně se jedná o správu pamětí.

Jednotlivé typy pamětí

ROM

Read Only Memory

jako příklad je uvedený typ ROM 16 x 4b

máme 16 adres ⇒ pro adresování jsou třeba 4 vodiče (2^4)

dekodér vybere podle adresy právě jeden řádek (položka o velikosti 4 bity) ⇒ do datového registru se uloží dané aktivní 4 bity

paměť tedy tvoří matici 16 x 4

požívá unipolární MOS tranzistory (funguje jako rezistor - odpor) ⇒ tranzistor zabere menší místo na chipu ⇒ gate je připojeno na nějaké napětí (adresový vodič)

při zápisu se přepálí spojení mezi adresovým vodičem a gate u těch položek, kde má být log 1

při čtení se na daný adresový vodič přijde log 1 ⇒ tranzistor se otevře ⇒ uzemní se ⇒ přečte se log 0 (pokud je přepálený vodič, přečte se 1)

Struktura ROM

RWM

Read/Write Memory

podobná základní struktura jako u ROM

máme navíc i zápisové zesilovače

Struktura RWM

konkrétní paměťová buňka

pomocí bipolárních paměťových členů - SRAM

struktura, který umí držet log 1 nebo log 0 (dva stabilní stavy ⇒ bistabilní)

stav se mění napěťovým pulzem

k vedení se používají elektrony i díry (CMOS)

viz bipolární tranzistory

pomocí unipolárních paměťových členů

k vedení se používají buď elektrony nebo díry (PMOS, NMOS)

viz unipolární tranzistory

statický

dynamický - DRAM - výrazně menší

Bipolární a unipolární tranzistory

SRAM

static RAM

jedna paměťová buňka stojí 6 tranzistorů

přibyly 2 tranzistory - kvůli adresovému vodiči

rychlé ⇒ díky klopným obvodům

využití: cache, paměti blízké procesoru,

rozhraní

adresová a datová sběrnice

chip enable - říká, zda je chip připojen

write enable

output enable

Struktura SRAM

Čtení a zápis asynchronní SRAM

acces time - ta - říká nám, za jak dlouho můžeme vyzvednout data na datové sběrnici ⇒ nesmíme do paměti posílat data moc rychle

SRAM - čtení

address setup time - čas, za jaký bude adresa na sběrnici stabilizovaná ⇒ až pak můžeme dát Write Enable (WE)

data setup time - čas, po který musí být dostupná platná data, aby se stihlo zapsat

data hold time - po zrušení čtení musí být data ještě nějakou dobu platná

address hold time - čas po ukončení zípisu, kdy musí být ještě dostupná adresa

SRAM - zápis

tyto časy jsou uvedeny v katalogu ke konkrétní součástce a musíme je zásadně dodržovat (nesmíme posílat data příliš často)

Adresování dvou a více pamětí

musíme zajistit, aby se v daném okamžiku používala pouze jedna paměť

v počítači máme různé druhy pamětí (RWM/ROM)

Adresování pamětí

všechny paměti musí být připojeny na datovou sběrnici

každá paměť musí mít připojeny příslušné řídící signály (v závislosti na typu)

všechny paměti musí být připojeny k adresovému dekodéru, který bude určovat, která paměť bude aktivní v daném čase (vytvoří nám adresový prostor)

pokud budeme mít např 16 bitové adresy, např:

nejvyšší tři bity použijeme pro adresový dekodér ⇒ určí nám paměť (bank ⇒ v tomto případě jich může být 8)

ostatní bity se použijí pro zvolenou paměť ⇒ pro adresování v ní

DRAM

levnější než SRAM ⇒ na jednotku plochy lze realizovat více paměťových buněk

technologie zavedena v 70. letech

realizace hlavní paměti počítače - RAM

princip

informace není uložena jako 0 nebo 1 v klopném obvodu, ale ve formě náboje na kondenzátoru ⇒ vyčtení informace z kondezátoru je zajištěno jedním tranzistorem ⇒ pokud je nabitý - log 1

data se dají vyčíst z určité doby, jelikož kondenzátor se vybíjí ⇒ zajímá nás hodnota kondenzátoru nad určitou úroveň napětí (1/2) ⇒ zajistíme rozdílovým zesilovačem (detekuje rozdíl mezi tím, co je na kondenzátoru a 1/2U)

poté, co se informace vyčte, je znova nahrána do kondenzátoru (nabijeme ho) ⇒ data se musí pravidelně obnovovat ⇒ vždy dřív, než klesne pod 1/2

Struktura prvku DRAM

opět maticová struktura - např 16K x 1bit ⇒ potřebuji 14 vodičů (2^16 = 16348)

oproti SRAM adresa se dává nadvakrát (adresujeme řádek a sloupec - multiplexní adresování ⇒ na průniku je zmiňovaný prvek ⇒ kondenzátor)

pokud bychom chteli mít N x 2bity ⇒ museli bychom mít celou matici 2x, atd… (více níže)

Struktura DRAM

čtecí zesilovač

v každém sloupci jeden

obsahuje zmiňovaný rozdílový zesilovače ⇒ s referenčním kondenzátorem, který se nabíjí na 1/2U porovnává hodnotu napětí na kondenzátoru čtené buňky

z paměťové buňky umí vyčíst informaci, rozhodnout, jestli bude log 0 nebo log 1 a následně provést zápis (obnovit položku ⇒ zajistit refresh)

ne vždy je potřeba číst ⇒ musíme mít řízení obnovy dat ⇒ zajišťuje to řadič obnovy dat

rozložená obnova - RNNNNNNRN…. - refreshuju postupně po částech

dávková obnova - RRRRRRRNN…. - refreshuju najednou 7 řádků

v obou případech musí být načasováno tak, aby se refresh provedl všude

spomaluje nám to výpočet ⇒ musíme naplánovat co nejefektivněj

ve video paměti se čte všechno ⇒ obnoví se samo

je vidět, že čtení už není tak jednoduché jak u SRAM

Obnovování položek

bloková struktura

adresa bloku - zhora prvních n bitů (např. 3)

opět máme adresový dekodér (1 z n) ⇒ 8 bloků ⇒ 16K (14 vodičů)x 8bit (8 bloků)

v daném bloku můžeme mít více pamětí ⇒ to, kterou paměť vybereme, určujeme adresou RAS

adresa sloupce - zhora druhých n bitů (např. 7) - CAS

adresa řádku - zhora posledních n bitů (např. 7) - RAS

x x x | x x x x x x x | x x x x x x x

rozdělování do bloků (16 x 1M x 1b) je mnohem rychlejší než základní struktura bez bloků (16M x 1b) ⇒ nastavím RAS a CAS a pouze pak přepínám bloky, což stojí menší režii, jak kdybych musel znova nastavovat RAS a CAS ⇒ prokládání paměťových operací

myšlenka je taková, že prioriou je vytáhnout co nejvíce dat na dané adrese a přitom neměnit RAS a CAS

BEDO - obsahuje interní čítač ⇒ adresu řekneme jednou a paměť si už pak inkremetuje ⇒ procesor pak dostane např 4x víc dat ⇒ natáhne si blok

synchronní DRAM - zavedl se dávkový režim BURST - paměti se posílají kódy a sama se už stará o určení přesné adresy ⇒ můžeme přečíst různý počet položek, který stanovíme a zašleme příkazem do paměti

DDR SDRAM - náběžná i sestupná hrana (2x zrychlení)

DDR2, DDR3 - zvyšuje se frekvence (2x)

Flash

nevolatilní paměť

od roku 1980

vylepšení paměti EEPROM ⇒ pouze jeden tranzistor na uchování jednoho bitu místo dvou (někdy i méně)

vysoká kapacita

když do paměti chceme něco zapsat, tak ji musíme nejdřív smazat (nahrají se všude jedničky) a tam, kde chceme zapisovat se pak nahrají nuly (lze mazat pouze po blocích)

dva typy:

NOR

podobné jako RAM (adresové a datové vodiče)

používá se jako náhrada PROM, EEPROM

NAND

nemá specializované adresové vodiče

ovládá se pomocí příkazů

lze realizovat extrémně velké kapacity na malé ploše

používá se unipolární tranzistor s plovoucím hradlem

NAND a NOR Flash nesouvisí s NAND a NOR u polovodičů. Název je odvozen pouze od podobné struktury

Hierarchie

Výkonová mezera mezi DRAM a CPU

problém neúměrného růstu rychlosti procesoru oproti růstu rychlosti DRAM

rychlost procesorů se zvyšuje cca 2x za 1,5 roku ⇒ Moorův zákon („složitost součástek se každý rok zdvojnásobí při zachování stejné ceny.“ )

doba přístupu u DRAM se zkrátí na polovinu zhruba za 10 let

DRAM tedy nelze připojit přímo k procesoru ⇒ procesor by musel stále čekat na data ⇒ mezi procesor a hlavní paměť se staví paměť cache - RVP = rychlá vyrovnávací paměť

Cache

rychlá vyrovnávací paměť umístěná mezi procesorem a hlavní pamětí ⇒ vyrovnává velký rozdíl rychlostí těchto dvou komponent

může být více RVP ⇒ L1, L2, …

rychlost SRAM roste rychleji jak u DRAM ⇒ proto se u pamětí cache používají SRAM ⇒ kapacita ovšem u nich roste znatelně pomaleji, jak u DRAM, proto mají cache mnohem menší kapacitu jak hlavní paměti ⇒ problém rychlost/kapacita == cena

procesor tedy pracuje pouze s RVP, až když nenajde, hledá se dál v hierarchii

Hierarchie

problém koherence ⇒ pokud se něco změní blízko procesoru, je třeba to pak pozměňovat i dál v hierarchii

přímý zápis ⇒ po změně okamžitě zapisuji do bloku v paměti (trvá dlouho)

zápis s mezipamětí ⇒ kapacita až deset opravných zápisů (také se moc nepoužívá)

zpětný zápis vždy ⇒ když přemazávám, vždy nahraji zpět původní ⇒ nepraktické (bloky pro čtení)

zpětný zápis podle příznaku změny ⇒ když přemazávám, kouknu na příznak změny (dirty bit/flag) a podle toho rozhodnu (používá se)

problém velikosti bloku

příliš malý ⇒ je jich tam hodně

příliš velký ⇒ často se musí vyměňovat (narůstá pravděpodobnost výpadku)

je rozdělena do bloků stanovené velikosti ⇒ ideálně velikost, kterou můžeme z DRAM načíst jedním načtením (v jedné dávce ⇒ zvýší rychlost)

základní parametr je pravděpodobnost úspěchu (hit rate) ⇒ v praxi 95-99% ⇒ 95-99% instrukcí se najde v paměti cache, ve zbytku (neúspěch - miss rate / miss penalty) je třeba hledat dál v hierarchii

existují programy, pro které bude hit rate vysoký a programy, pro který bude hit rate nízký ⇒ záleží tedy na programátorovi, jak efektivně program napíše

aby nedocházelo ke strukturním konfliktům, máme:

datovou cache

instrukční cache

RVP s přímým mapováním

RVP - přímé mapování

v tomto případě nemůžou být v paměti cache položky, které jsou od sebe v hlavní paměti vzdáleny o 8 bitů

vyřeší se stupněm asociativity cache (asociativita 2 ⇒ můžu mít dvě položky, které končí stejně ⇒ dvoucestná cache)

aby byla plně asociativní, potřeboval bych osmicestnou cache

informace uložené v RVP:

data

adresový příznak - tag - aby se rozpoznalo, jaká data jsou v RVP (pokud procesor žádá data na adrese 10110, tak tag je 10)

příznak platnosti - zda jsou data platná

příklad máme cache o velikosti 1024 položek máme paměť 32 bit kde každá položka má 4 Byty (berme, že se budou chtít adresovat jednotlivé Byty) máme 32-bit adresování Jakou kapacitu je třeba vyhradit pro paměť cache?

RVP - přímé mapování - 32 bit

na adresování v položce budeme potřebovat 2 bity, protože položka má 4 Byty (pro každý Byte) na adresování v RVP budeme potřebovat 10 bitů (adresujeme 1024 položek) zbylých 20 bitů bude vymezeno pro tag paměť tedy bude muset mít 20 bitů pro tag mít 20 bitů pro tag ⇒ 1024 položek * (20 + 32 + 1 bit platnosti) práce procesoru, když hledá data: vezme 10 bitů a naadresuje se příslušná položka porovná 20 bit tag s horními 20 bity adresy pokud OK, zkontroluje se bit platnosti, zda je nastaven na log 1 pokud je nastaven do log 1 ⇒ generuje se hit pokud je nastaven na log 0 ⇒ musí se nahrát do paměti nový blok a starý blok se musí nahrát zpět, pokud byl měněn celkový počet bloků o velikosti 32 bit je 230 ⇒ do RVP se vejde takových bloků 210 ⇒ dolní odhad pravděpodobnosti úspěchu je phit = 210/230 = 2-20 ⇒ díky lokalitě odkazů se v praxi dosahuje hodnot phit 0,9 až 0,98

Vícecestné RVP

RVP - přímé mapování - 32 bit

pokud máme plno ve všech čtyřech položkách a potřebujeme nahrát novou položku ⇒ musíme vybrat oběť

LRU - Last recently used

MFU - Most frequently used

FIFO - First IN First OUT

RAND - Random

⇒ je třeba přidat další HW ⇒ dá se optimalizovat, pokud budeme používat jeden specifický program

Virtuální paměť

podobná problematika ja u pamětí cache

dalo by se říci je to něco jako cache pro disk

proč chceme virtuální paměť? (otázka na státnice)

chceme udělat efektivní sdílení paměti M pro mnoho programů

odstranit omezení fyzikální velikosti paměti M

vychází z poznatku, že pouze malá část programů je současně aktivních

pracuje se s pojmy

fyzický adresový prostor - v HW

logický (virtuální) adresový prostor - v OS

Toto už předpokládám, že je v IOSu.

Zdroj

Při tvorbě tohoto tématu jsem čerpal především ze slajdů INP - inp2010_13pameti.pdf a inp2010_14pam_hier.pdf. K pochopení slajdů mi pomohly příslušné záznamy - INP_2009-11-10.avi a INP_2009-11-24.avi

Potvrzení