paměti základní pojmy i

F. Paměti • • • • • • • • • •

základní pojmy permanentní a semipermanentní paměti uspořádání adresovatelné paměti statická paměť dynamická paměť organizace pamětí z hlediska výběru paměťových míst adresovatelné paměti paměti LIFO paměti FIFO paměti CAM (asociativní paměti) – plně asociativní – LRU – omezený stupeň asociativity – strategie uvolňování položek

JPO 2005/6

c A. Pluháček 18.4.2006

základní pojmy

i

paměti

• vnitřní – registry – zápisníková paměť (angl. scratch-pad memory) – skrytá paměť (též rychlá vyrovnávací paměť), angl. cache – hlavní paměť (angl. main memory) = operační paměť • vnější ∈ periferní zařízení

nejdůležitější charakteristiky: • doba čtení a zápisu, popř. vybavovací doba, cyklus paměti • kapacita — v bitech bit, ve slabikách (B), popř. ve slovech (specifikované délky) odvozené jednotky: (i ∼ binary) Ki = ×210 , Mi = ×220 , Gi = ×230 , Ti = ×240 K = ×103 , M = ×106 , G = ×109 , T = ×1012 např. 4Kibit = 4069 bitů, 4Kbit = bitů, 1KiB = 8192 bitů • cena JPO 2005/6

F1

c A. Pluháček 2.5.2006 (opraveno)

základní pojmy

ii

paměti

• měnitelné – RWM (read–write memory) častěji označované RAM (random access memory) ∗ SRAM (static RAM) ∗ DRAM (dynamic RAM) • permanentní – ROM (read only memory) – PROM (programable ROM) • semipermanentní – EPROM (erasable PROM) – EEPROM, E2 PROM, E2 (electrically EPROM) – flash •

paměti energeticky nezávislé (angl. non-volatile)

(obsah paměti se zachová i po odpojení napájení): permanentní a semipermanentní paměti (polovodičové) • paměti energeticky závislé: měnitelné paměti (polovod.) JPO 2005/6

F2

c A. Pluháček 27.4.2006 (opraveno)

permanentní a semipermanentní paměti základní princip realizace (příklad):

N = 2n n=3 ⇒ N = adresa data 0 0 0 ... 1 0 0 0 1 ... 0 1 .. .. .. .. .. .. . . . . . . 1 1 0 ... 1 1 1 1 1 ... 1 0 JPO 2005/6

F3

8 1 0 .. . 0 1 c A. Pluháček 18.4.2006

uspořádání adresovatelné paměti !!! 3D — pro představu, ale(!) skutečnost — 2D !!! n=m+k N =2n adres M =2m řádků K =2k sloupců ri . . . i-tý řádek sj . . . j-tý sloupec dq . . . bit dat v řádu q

(an−1 , . . . , a0 ) — nbitová adresa ⇒ N = 2n adres kapacita paměti (v uvedeném příkladu): N × 4 bity JPO 2005/6

F4


statická paměť - paměťová buňka (1 bit) základní princip:

typické řídicí signály: W E (write enable) zápis OE (output enable) čtení CS (chip selection) výběr čipu ↑ „aktivní nulaÿ ↑ out = OE · CS = = OE + CS in

JPO 2005/6

F5

= W E · CS = = W E + CS c A. Pluháček 18.4.2006

časové diagramy řídicích signálů čtení z paměti:

zápis do paměti:

JPO 2005/6

F6


rozšíření slova v paměti slovo na čipu = 4 bity

→

slovo v paměti = 8 bitů

CS = 0 ( oba čipy trvale vybrány )

JPO 2005/6

F7


zvětšení adresového prostoru 3bitová adresa pro čip → 5bitová adresa pro paměť (4× větší adresový prostor)

JPO 2005/6

F8


dynamická paměť

i

základní princip:

JPO 2005/6

F9


dynamická paměť

ii

• nutné periodické obnovování obsahu (viz dále) • adresa je časově multiplexována (posílá se nadvakrát): ◦ RAS = 0 ... 1. část adresy = číslo řádku ◦ CAS = 0 ... 2. část adresy = číslo sloupce • dílčí čtení — přečte se a vymaže se celý řádek a uloží se do vyrovnávací paměti • dílčí zápis — zapíše se celý řádek z vyrovnávací paměti • ČTENÍ = dílčí čtení + dílčí zápis dílčím zápisem se obnoví přečtená (a vymazaná) informace • ZÁPIS = dílčí čtení + dílčí zápis dílčím čtením se vymaže řádek (a uloží se do vyr. pam.) před dílčím zápisem (a obnovením) nutno změnit bit v příslušném řádu, popř. v bity v příslušných řádech

JPO 2005/6

F 10


organizace pamětí z hlediska výběru paměťových míst

paměť:

• adresovatelná, s adresním (adresovým) výběrem — paměťové místo určeno adresou • s postupným výběrem — paměťová místa se vybírají postupně (jak za sebou následují) — příklad: magnetická pásková paměť — těmito paměťmi se nebudeme blíže zabývat • LIFO, [Last-In First-Out] zásobníková, sklípková [stack, push-down] — čte se posledně zapsaná položka • FIFO [First-In First-Out] fronta — čte se nejdéle zapsaná položka • asociativní CAM [Content Addressed Memory] — paměťové místo určeno svým obsahem

JPO 2005/6

F 11


výběr paměťového místa pro zápis a čtení paměť: adresovatelná

LIFO, FIFO, s postupným výběrem

„univerzálníÿ CAM

„speciálníÿ CAM

JPO 2005/6

F 12


adresovatelné paměti

i

• jednobránová paměť • vícebránová paměť nbránová paměť: n adresových vstupů n (popř. méně) datových vstupů n (popř. méně) datových výstupů příklad – 2bránová paměť:

JPO 2005/6

F 13



ii

2bránová paměť tvořená registry: vysvětlivky (registry):

zápis A

zápis B jinak: pamatuje se

JPO 2005/6

F 14



iii

příklad použití 2bránové paměti tvořené registry: zápisníková paměť

JPO 2005/6

[scratch-pad]

F 15



iv

Hlavní paměť • vícebránová — umožňuje připojení několika procesorů nebo jiných jednotek (např. kanálů pro vstup/výstup) – řízení: řadič hlavní paměti neboli organizátor – kolize požadavků — vyšší priorita V/V ⇒ odebrání cyklu [cycle stealing] – připojení: přímé sběrnice propojovací sítě • jednobránová připojení — přes sběrnici obvykle umožňuje připojení několika jednotek kolize požadavků — řešena režimem přidělování sběrnice podsběrnice: adresová datová řídicí JPO 2005/6

F 16



v

vícebránová hlavní paměť s autonomními paměťovými bloky

BP0, BP1, . . . — bloky paměti P1, P2, . . . — procesory (popř. jiné jednotky)

umožňuje paralelní (současnou) práci různých bloků, pokud se požadavky týkají různých bloků (týkají se různých částí paměťového prostoru) JPO 2005/6

F 17


LIFO

i

LIFO — sériově řazené registry

TOP = vrchol zásobníku

JPO 2005/6

F 18


LIFO

ii

LIFO — registry určené ukazovátkem

JPO 2005/6

F 19


LIFO

iii

realizace ukazovátka:

JPO 2005/6

F 20


LIFO

iv

LIFO — jádro = adresovatelná paměť

zápis (PUSH) — pre-inkrementace čtení (POP) — post-dekrementace nebo naopak: zápis (PUSH) — pre-dekrementace čtení (POP) — post-inkrementace JPO 2005/6

F 21


LIFO

v

použití paměti LIFO • návratové adresy: podprogramy a mikropodprogramy • registry aritmetické jednotky (zápisníková p.)

JPO 2005/6

F 22


FIFO

i

FIFO

použití: vyrovnávací paměť

[buffer]

sériově řazené registry:

← Pi . . . bity platnosti

Pi = 1 & Pi+1 = 0 zápis: 1 → P1 čtení: 0 → Pn JPO 2005/6

⇒

i = 1,. . . ,n Pn+1 = 1 hodinový puls pro danou pozici

F 23


FIFO

ii

FIFO — sériově řazené registry — příklad (2 zápisy + 1 čtení)

? 0

? 0

? 0

← data ← platnost

A→

A 1

? 0

? 0

A 0

A 1

? 0

B→

B 1

A 0

A 1

B 0

B 1

A 1

←A

B 0

B 1

A 0

B 0

B 0

B 1

JPO 2005/6

F 24

A 0

A 0

A 1


FIFO

iii

FIFO — registry určené ukazovátkem

JPO 2005/6

F 25


FIFO

iv

realizace ukazovátka:

JPO 2005/6

F 26


FIFO

v

paměť prázdná stejné obsahy čítačů =⇒ paměť plná přidat klopný obvod: • shoda čítačů po čtení =⇒ nulovat • zápis =⇒ nastavit (zapsat 1)

JPO 2005/6

F 27


FIFO

vi

FIFO — jádro = adresovatelná paměť

JPO 2005/6

F 28


CAM – plně asociativní

i

Plně asociativní paměť: Ki . . . klíč di . . . vstupní data Di . . . výstupní data Zj . . . zápis Sj . . . nalezena shoda P K D

JPO 2005/6

F 29

. . . platnost . . . klíč . . . data


CAM – plně asociativní

ii

plně asociativní paměť — značky:

JPO 2005/6

F 30


CAM – LRU

LRU

i

[Least Recently Used]

strategie nalezení nejdéle nepoužité položky (pro uvolnění z paměti) základní princip: matice M — ignorují se prvky na hlavní diagonále ⇒ 1 1 · · · 1 → i-tý řádek použita položka i ⇒ ⇒ 0 0 · · · 0 → i-tý sloupec nejdéle nepoužitá položka i:

0 0 · · · 0 — i-tý řádek 1 1 · · · 1 — i-tý sloupec

příklad: postupně použity položky 2, 3, 1, 2, 4 JPO 2005/6

F 31


CAM – LRU

1 2 3 4

1 X ? ? ?

↓ → X 0 0 0

2 ? X ? ? 1 X 1 0

3 ? ? X ? 1 0 X 0

4 ? ? ? X 1 1 1 X

Mij = Mji

JPO 2005/6

X → 1 ? ?

↓ 0 X 0 0

X → 1 0 0

↓ 0 X 0 0

? 1 X ? 1 1 X 0

ii

? 1 ? X

X 1 → 1 ?

1 1 1 X

X 1 0 → 1

0 X 1 0 0 X 0 1

↓ 0 0 X 0

? 1 1 X

1 1 X 1

↓ 0 0 0 X

⇒ stačí prvky nad diagonálou: 1 0 1 0 2 1 0 3← 0 ↓ 2 3 4 F 32


CAM – LRU

iii

LRU:

JPO 2005/6

F 33


CAM – LRU

iv

časový diagram čtení / zápisu: hodiny čtení/zápis Z1 ÷ Z4 změna LRU Předpokládá se, že zápis do synchronních klopných obvodů typu D se provádí při závěrné hraně hodin.

JPO 2005/6

F 34


CAM - omezený stupeň asociativity

1 ⇛

i

stupeň asociativity s = 1

paměť přímo mapovaná

[direct mapped]

• Jádrem je adresovatelná paměť AP. • Klíč K je rozdělen na 2 části : 1. P K (podklíč), 2. adr. • Položka s klíčem K je vždy ukládána na adresu adr v AP; tvoří ji: podklíč P K, vlastní data D a bit platnosti P . • V paměti nemohou být dvě položky, jejichž klíče mají stejnou část adr. • Při čtení se zadává klíč K; zjišťuje se, zda na adrese adr je uložen podklíč P K, a zda je nastaven bit platnosti P adr.

JPO 2005/6

F 35



ii

stupeň asociativity s = 1 (paměť přímo mapovaná)

JPO 2005/6

F 36



2

stupeň asociativity s > 1

iii

[direct mapped]

• Jádrem je adresovatelná paměť AP. • Klíč K je rozdělen na 2 části : 1. P K (podklíč), 2. adr. • Na jednu adresu se může uložit až s položek (jejichž klíče mají stejnou část adr). • Položka: podklíč P K, vlastní data D, bit platnosti P . • Při čtení se zadává klíč K; zjišťuje se, zda na některá položka na adrese adr obsahuje podklíč P K, a zda je nastaven její bit platnosti P . • Paměť dále obsahuje informace pro výběr položky, která má být uvolněna z paměti, aby se do ní dala zapsat jiná položka — LRU. řádek . . . údaje na jedné adrese JPO 2005/6

F 37



iv

stupeň asociativity s > 1

JPO 2005/6

F 38


CAM - strategie uvolňování položek • LRU [Least Recently Used] nejdéle nepoužitá položka s bitů v každém řádku pole „LRUÿ — 2 • FIFO nejstarší položka pole „LRUÿ — čítač ⌈log2 s⌉ bitů v každém řádku

• „náhodněÿ společný čítač pro všechny položky ⌈log2 s⌉ bitů pro celou paměť

[First-In First-Out]

[random]

• pseudo – LRU – FIFO + ochrana posledně použité položky pole „LRUÿ — čítač & číslo posledně použité položky 2 · ⌈log2 s⌉ bitů v každém řádku – nějak „ošizenéÿ LRU př.: cache I486 (s = 4) — 3 bity v každém řádku JPO 2005/6

F 39


paměti základní pojmy i

Recommend Documents