memoria-hierarkia memoria-sistemaren diseinua · cache memoria – cma: tarteko memoria, txikia eta...
TRANSCRIPT
CACHE MEMORIA
•Sarrera: memoria-hierarkia, ingurutasuna.•Cache memoriaren ezaugarri orokorrak:
tamainaedukiablokea
•Diseinu-parametroakegokitzapena (kokapena)ordezkapen-algoritmoa idazketa-politika
2
Sarrera
• Arazoa: – CPU eta Memoria-sistemaren arteko abiadura– Prozesadoreari informazioa azkar pasa behar zaio
• Helburua: – Memoria-sistemako atzipen-denbora azkartu
• memoriaren egitura: moduluen arteko elkarloturak• cache memoria: memoria azkarrak
– Teknologia– Informazio egokia
3
SarreraMemoriaren egitura:
–Helbidea, posizioa, edukia–Busak: @, datuak, kontrola–Prozesadorearen hitza (32, 64 bit)
•Helbideratze-unitatea: –Byte: helbide-busak byte guztiak helbideratzen ditu–Hitza: helbide-busak hitzak helbideratzen ditu–Oro har: byte
•hitza = @ fisikoa div hitzaren-tamaina (byte)•byte = @ fisikoa mod hitzaren-tamaina (byte)
bytehitza @ fisikoa (byte)
4
Sarrera
Memoria-moduluen egitura: –Memoria N byteko moduluez osatzen da.–Memoriako atzipen-denbora txikitu–Aukerak:
–Ondoz-ondoko moduluak–Atzipen sekuentziala
–Elkarlotutako moduluak–Aldi bereko atzipenak (n hitz)
–Elkarlotutako moduluen ondoz-ondoko bankuak
5
Cache memoria– CMa: tarteko memoria, txikia eta azkarra– prozesadoreak gehien erabiltzen duen informazioa
CPUErreg.
CM-L1
Kanpo-memoria
ms70ns
+- atzipen-denboratamaina+ -
MN
CML2
2/15ns256Kb-32Mb1-2ns
16kb-128Kb
Blok(32B)
Blok(128B) Orria
(2-4KB)
kostua
6
Cache memoria
• Programaren portaera: ingurutasuna– denborazko ingurutasuna: begiztak
t → @t+∆t → @
– lekuzko ingurutasuna: exekuzio sekuentziala, bektoreak, …
t → @t+∆t → @+1
• Dena den, apostu bat egiten da
7
Cache memoria
Prozesadoreak bidalitako helbidea
CMa aztertu: direktorioaAsmatzea (h) Hutsegitea
CMa atzituHitza bidali
MNa atzituBlokea transferituCMa eguneratuHitza bidali
atzipen azkarraatzipen motela
8
Cache memoria
ThThT CMa *)1(* −+=• Atzipen-denbora (h, hit ratio):
Asmatzea = hit h > %90Hutsegitea (1-h)TCM = CMaren atzipen-denbora T = Hutsegite-denbora (CM+MN)
9
Cache memoria
• MNaren eta CMren arteko transferentzia– Blokeak (CMn (L1 eta L2) eta MNan)– Blokea = 2n hitz
• CM atzitzeko helbide fisiko bera beste era batean interpretatua:
@ fisikoa (byte)byteaMNko blokea hitza/blokea
@fisikoa (hitza)
10
Cache memoria
• CMaren osagaiak: direktorioa + SRAM– Direktorioa (M. Asoziatiboa / SRAM):
• helbide markak • kontrol-bitak
– SRAM• Edukiak
– Konparagailuak, multiplexoreak, kodegailuak,...
11
Cache memoriaren ezaugarriak
• Tamaina• Edukia: bateratuak, banatuak• Blokearen tamaina• Egokitzapenak:
– guztiz elkargarria– zuzenekoa– multzokako elkargarria
• Ordezkapen-algoritmoak: random, FIFO, LRU• Idazketa-politika: write-back, write-through• Helburua: h altuena, TCM minimoa
12
Tamaina• Zenbat eta handiagoa:
– asmatze-tasa altuagoa– kostu handiagoa (atzipen-denbora mantentzeko)
• Eraginkortasuna/kostua• Gaur egun:
– bi mailako cacheak:• on-chip: azkarra, 64 kB // 1 MB // 9 MB• off-chip: 32 Mbyte
– Itanium2: 16+16 kB + 256 kB + 9 MB (on-chip)– Opteron: 64+64 kB + 1 MB (on-chip)
13
Edukia
• Cache bateratuak:– datuak eta aginduak memoria berean– cachea txikia bada hobeto aprobetxatzen da
• Cache banatuak:– Datu-cachea eta agindu-cachea– bakoitzari dagozkion parametroak optimizatu– atzipen-paraleloak: prozesadore segmentatuak
14
Blokearen tamaina• Blokea: transferentzia-unitatea • Blokearen tamaina handitzen bada:
– lekuzko ingurutasuna hobetzen da ⇒ h↑– CMn bloke gutxiago ⇒ h↓
• denborazko ingurutasuna behera– transferentzia denbora altuagoa– kutsadura: ekarritako informazioa erabiliko da?
• Tamaina: 4-128byte (32 byte)• Blokearen tamaina ⇔ tartekatze-maila
15
Egokitzapenak• MNtik ekartzen den blokea, CMko zein
bloketan kokatu?• Hiru aukera:
– guztiz elkargarria: edozein bloketan– zuzenekoa: bloke jakin batean (eta beti bera)– multzokako elkargarria:
• cache memoriako blokeak multzotan banatzen dira• multzo jakin batean (eta beti bera)• multzo horretan edozein bloketan
Egokitzapen guztiz elkargarria
• CMko edozein bloketanMNko blokea
@ marka
16
@ fisikoa (byte)byteah/b
@fisikoa (hitza)
• Direktorio osoa aztertu behar da ⇒ memoria elkarkorra ⇒ egokitasun garestia
• Bi atzipen sekuentzialak: direktorioa + RAM• Asmatze-tasa handiena eskaintzen du
17
Egokitzapen zuzenekoa
• Bilaketa azkartzeko, MNko i blokeari CMko bloke jakin bat dagokio (beti bera):
CMko blokea = i mod CMko bloke-kopurua
MNko blokea@ marka CM_blokea @ fisikoa (byte)byteah/b
@fisikoa (hitza)
• Atzipen paraleloa: direktorioa / RAM• Asmatze-tasa txikiagoa
18
Egokitzapen multzokako elkargarria
• Tarteko bidea:– CMko blokeak multzotan banatzen dira– MNko i blokea multzo jakin batean kokatzen da
CMko multzoa = i mod CMko multzo-kopurua– Multzo horretan, edozein bloketan
•Elkargarritasuna A = bloke/multzo
MNko blokea@ marka CM_multzo @ fisikoa (byte)byteah/b
@fisikoa (hitza)
19
Egokitzapen multzokako elkargarria
• Tarteko bidea:– Multzo-kopurua = 1 ⇒ guztiz elkargarria– Multzo-kopurua = CMko bloke kopurua ⇒ zuzenekoa
• Horregatik:– atzipen-denbora, egokitasun zuzenekoaren antzekoa– asmatze-tasa, egokitasun guztiz elkargarriarena
• Gaur egun:– multzokako elkargarria (A=2,4)– zuzenekoa
20
Ordezkapen-algoritmoa
• Hutsegitean, CMa beteta badago, CMko zein bloke ordezkatu?– Zuzenekoan, dagokiona– Guztiz elkargarrian, CMko bloke bat aukeratu– Multzokako elkargarrian, dagokion multzoan
bloke bat aukeratu• Bi motako algoritmoak:
– Programaren portaera kontuan izaten ez dutenak– Programaren portaera kontuan izaten dutenak
21
Ordezkapen-algoritmoa
• Programaren portaera kontuan izaten ez dutenak:– Ausazkoa (random): edozein
• errazena, hutsegite-tasa handiena– FIFO: CMn denbora gehien daramana
• gauzatzeko kontagailuak erabiltzen dira
• Programaren portaera kontuan izaten dutenak:– LRU: CMn denbora gehien erabili gabe daramana
• gauzatzeko zaila (A=2 ez bada), hutsegite-tasa txikiena
• Gaur egun: LRU (A=2 bada), pseudo-LRU
22
Idazketa-politika
• CMn aldaketaren bat egiten bada, noiz islatu aldaketa MNn?
• Write-back (idazketa atzeratua):– CMko blokea ordezkatzen denean idazten da MNan
– aldaketa-bita (dirty)– Idazketa/asmatzean: bakarrik CMan idazten da– Idazketa/hutsegitean: blokea transferitzen da MNtik
eta idazketa CMan bakarrik egiten da– Koherentzia-arazoak (multiprozesadoretan)
23
Idazketa-politika
• Write-through (idazketa zuzena):– Prozesadoreak beti MNa eguneratzen du (hitza)– Trafiko gehiago MNra (idazketa-bufferra)1. MNa eta CMa eguneratuz
Idazketa/asmatzean:• CMa eguneratu• Hitza eguneratu MNanIdazketa/hutsegitean:• Hitza eguneratu MNan• Blokea CMra transferitu
24
Idazketa-politika
• Write-through (idazketa zuzena):2. Bakarrik MNa eguneratuz (CMa baliogabetu)– Idazketa/asmatzean:
• CM-ko blokea baliogabetu (baliogarritasun bita)• Hitza eguneratu MNan
– Idazketa/hutsegitean:• Hitza eguneratu MNan
Atzipen-denboraTcm: Cache memoriako atzitzeko denbora (irakurri/idatzi/direktoria aztertu eta aldatu)Tmn: Memoria nagusia atzitzeko denbora (hitz bat irakurri edo idazteko)Tbt: Bloke transferentzia egiteko denbora (bloke bat MNtik CMra edo alderantziz)Irakurketa
Asmatzea: T = Tcm Hutsegitea: T = Tcm + TbtIdazketa WB
Asmatzea: T = Tcm Hutsegitea: T = Tcm + Tbt
Hutsegitea + ordezkapena: T = Tcm + Tbt + TbtIdazketa WTa) Bakarrik MNa eguneratu:
Asmatzea: T = Tcm + Tmn Hutsegitea: T = Tcm + Tmn
b) MNa eta CMa eguneratu:Asmatzea: T = Tcm + Tmn Hutsegite: T = Tcm + Tmn + Tbt
26
Bilaketa-algoritmoa
• Prefetch (aurreratutako bilaketa)– Prozesadoreak i blokea erabiltzen duen
bitartean, i+1 blokea transferitu trafikoa!!!– Apostu bat egiten da kutsadura!!!– Noiz aurreratu blokea?
• Prefetch always: i blokea atzitzen denean beti aurreratzen da i+1 blokea, CMan ez badago
• Prefecth on-miss: i blokearen atzipena hutsegiteabada, orduan i blokeaz gain i+1 ere transferitzen da (CMan ez badago)
– Asmatze-tasa igo egiten da: %40 - %80
27
Bi mailatako cache-hierarkia
CPU
MN
CML2CM-L1
blokeablokea
2*)
11(
1*
1T
Lh
LT
Lh
aT −+=
ThThTLLL
*)1(*2 222
−+=non
28
Egungo prozesadoreakL1 (on-chip)AC + DC
L2 (on-chip)AC + DC
Bestelakoak
AMD Athlon 64 KB + 64 KBA=2 // 3 ziklo
1 MB // A=16(1) on-die, 11 z.
(2) on-chip, 8 z. 256
Blokea = 64 bytewrite-back, LRU
L3 cachea off-chip 4 MBZuzena // 12z. // WB
Blokea = 32 edo 64 byte(21164 ean 32 byte)
IBM POWER4 32 kB + 64 kB //A=4 1,875 MB // A=10 L3: 36MB off-chip // A=12 // 80z
Intel Pentium 4 96 kB+16 kB // A=4 WT//3 z.//B=64 byte
512 kB // WB // A=87 z.
LRU, L3 (on-chip): 2 MB //B=128 byte
LRU, L3 (on): 9 MB // 12 z.Itanium2: 16+16 // 256 // 3MB
Blokea = 32 byte//LRU
Blokea = 128 byte
Alpha 21164 8 KB + 8 KBZuzena //2z. //WT
96 KBA=3 // 7z.// WB
Alpha 21264 64 KB + 64 KBA=2 // 3 ziklo
8 MB off-chipZuzena //16z.//WB
HP PA-RISC 8600 1,5MB + 1,5MB A=4 // 2z.
32 MB off-chip
Intel Itanium IA-64 16 KB + 16 KBA=4 // 1z.
256 kBA=8 // 5 z.
Intel Pentium III 16 KB + 16 KBA=2 // 3 ziklo//WT
256/2048 KB(on-die)A=8 // 7 ziklo //WB
MIPS R14000 32 KB + 32 KB//A=2 16 MB off-chip// A=2
Sun UltraSPARC III 32 KB + 64 KBA=4 // 2 ziklo
8 MB off-chipZuzena // 15 ziklo