Prozessorarchitektur
Speicher
M. Schölzel
Inhalt
Aufbau von Speicher
Organisation der Speicherhierarchie
Inhalt
Aufbau von Speicher
Organisation der Speicherhierarchie
Prozessor-Memory-Gap
Processor-Memory Gap: ~+50% / year
µProc 60%/yr. (2X/1.5yr)
DRAM 9%/yr. (2X/10 yrs)
Speicherverwendung typische Speichergröße
Ungefähre Zugriffszeiten
Form der Implementierung
Eigenschaft
CPU-Register ~500 Byte ~250 ps D-Flip-Flop, D-Latch
Flüchtig
1L-Cache ~8 – 64 KByte ~1 ns SRAM Flüchtig
2L-Cache ~256 KByte ~5 ns SRAM Flüchtig
3L-Cache ~1 – 16 MByte ~25 ns SRAM Flüchtig
Hauptspeicher ~4 – 32 GByte ~50 ns DRAM Flüchtig
Disk ~1-2 TByte Millisekunden Festplatte/Flash Nicht flüchtig
Speicherhierarchie in einem Computer
Eigenschaften − Bei 1 GHz vergeht pro Takt 1 ns − In 1 ns legt Licht im Vakuum ca. 30 cm zurück − Typische Taktraten 1 bis 4 GHz
Physisch ist der Speicher hierarchisch organisiert Logisch ein Adressraum
On-Chip
Off-Chip
Speicherhierarchie in einem Mikrocontroller
Typische Taktraten − Wenige MHz – 100 MHz
Organisation des Speichers
− Flache Hierachie − Unterschiedliche Speichertypen in verschiedenen Adressbereichen
Speicherverwendung typische Speichergröße
Ungefähre Zugriffszeiten
Form der Implementierung
Eigenschaft
CPU-Register ~100 Byte ~1 ns D-Flip-Flop, D-Latch flüchtig
Datenspeicher 1 Kbyte – 2 MByte ~1-10 ns SRAM flüchtig
Programmspeicher ~64 KByte – 1 MB ~1-10 ns Flash, ROM (nicht) flüchtig
Programm-/Datenspeicher
1 – 4 MB ~50 ns Flash, DRAM (nicht) flüchtig
On-Chip
Off-Chip
Organisationsformen von Speicher
Flüchtige Speicher Flip-Flops SRAM DRAM Festwertspeicher Masken-ROM OTP-ROM (one-time programmable) Nicht-Flüchtige Speicher EPROM EEPROM Flash
Verwendung als Massenspeicher Organisation in Speicherfeldern
Kleine Speichergröße (wenige Byte) Organisation als Register
Organisation Speicherfelder (1)
Speicherfelder dienen der Speicherung großer Datenmengen Organisation als zweidimensionales Feld mit
− 2n Zeilen − jede Zeile enthält ein Datenwort mit m-Bit
Speicherkapazität 2n × m Bits
2n-word ´ m-bit Speicherfeld Adresse
Daten
n
m
0 0 1 0 1 0 1 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0
000 001 010 011 100 101 110 111
Adresse Daten
Organisation Speicherfelder (2)
Physischer Aufbau aus Bitzellen Jede Bitzelle speichert ein Bit Adressierung der Bitzellen einer Zeile über Wortleitung Auslesen/Schreiben der Daten einer aktivierten Zeile über Datenleitung
0 0 1 0 R
1 1 1 0 R
0 0 1 0 R
1 1 0 0 R
…
3:8
Deco
der
Adresse 3
Data In
Data Out
Write Enable
…
…
…
…
Gnd
Tri-State-Elemente
Wortleitung
Bitleitung (Datenleitung)
Tri-State-Element in CMOS-Logic
Data Out
Data In
Write Enable
p2
p3
n2
n3
p1
n1
Vdd
Gnd
Lesen einer Zeile
Zum Lesen wird write enable auf 0 gesetzt ® Datenleitungen werden von Data In getrennt Durch Decoder wird eine Wortleitung auf 1 gesetzt Angeschlossene Bitzellen werden aktiviert und treiben die angeschlossenen Datenleitungen mit
dem gespeicherten Wert
0 0 1 0 R
1 1 1 0 R
0 0 1 0 R
1 1 0 0 R
…
3:8
Deco
der
001 3
Data In
0
…
…
…
…
Gnd
1
0
0
0
1 1 1 0
Schreiben einer Zeile
Zum Schreiben wird write enable auf 1 gesetzt ® Datenleitungen werden von Data In getrieben Durch Decoder wird eine Wortleitung auf 1 gesetzt Angeschlossene Bitzellen werden aktiviert und speichern den Wert der jeweils angeschlossenen
Datenleitung
0 0 1 0 R
1 0 1 0 R
0 0 1 0 R
1 1 0 0 R
…
3:8
Deco
der
001 3
1
…
…
…
…
Gnd
1
0
0
0
1 0 1 0
1 0 1 0 Data In
Aufbau Static Ram (SRAM) Zelle
Speichert ein Bit in einem bistabilen Speicherelement
Zustand wird von selbst gehalten, solange Versorgungsspannung anliegt
Aufbau einer SRAM-Zelle aus 6 Transistoren
Wortleitung
Bitleitung Bitleitung
Transistor
M6 M5
CMOS Inverter
bistabiles Speicherelement
SRAM auslesen
Eingänge der Bitleitungen werden hochohmig (Z) gesetzt Durch aktivierte Wortleitung (=1) werden Pass-Transistoren leitend Zustand des bistabilen Speicherelements kann über Bitleitungen
ausgelesen werden
Wortleitung
Bitleitung Bitleitung Z
Pass- Transistor
Z
1
Pass- Transistor
1 0
1 0
SRAM schreiben
Eingänge der Bitleitungen werden auf zu schreibende Werte gesetzt Durch aktivierte Wortleitung werden Pass-Transistoren leitend Zustand des bistabilen Speicherelements wird überschrieben
Wortleitung
Bitleitung Bitleitung 0
Pass- Transistor
1
0
Pass- Transistor
1 0
Bitleitung Bitleitung 0
Pass- Transistor
1
1
Pass- Transistor
0 1
Masken ROM
Festwertspeicher, dessen Werte bei der Fertigung durch die Masken bestimmt werden
Keine nachträgliche Änderung der Speicherwerte möglich
Bitleitungen liegt auf Gnd (=0)
Wortleitung auf 1 setzen: − Bei vorhandener Verbindung zur Bitleitung wird
Bitleitung auf 1 gesetzt (Spannung fällt über Widerstand ab)
− Bei fehlender Verbindung bleibt Bitleitung auf 0
Diode verhindert auf 1 setzen einer Wortleitung durch Rückkopplung von Bitleitung
Wortleitung 2
Gnd
…
Wortleitung 1
Bitleitung
Widerstand
Diode
One Time Programmable (OTP) ROM
Festwertspeicher, dessen Werte nach der Fertigung durch einmalige Programmierung festgelegt werden
Zur Programmierung wird deutlich höhere Spannung an Wortleitungen angelegt und Bitleitungen können gezielt von Gnd getrennt werden
Hoher Strom lässt Verbindungen (Fuses) verdampfen
Es können nur 1en zu 0en geändert werden
Wortleitung 2
Gnd
…
Wortleitung 1
Bitleitung
Widerstand
Fuse
program
EPROM
Erasable and Programmable ROM
Bitzelle ist aus Transistor mit einem Floating Gate (FG) aufgebaut
Programmierung durch Anlegen einer hohen Spannung; dadurch sammeln sich Ladungsträger im Floating Gate und bleiben dort (FG ist isoliert)
Auslesen durch Anlegen der normalen Versorgungsspannung am Gate: − Keine Ladungsträger im FG: Transistor wird leitend und zieht Bitleitung auf Gnd (=0) − Ladungsträger im FG: Ladungsträger „verringern“ angelegte Gate-Spannung; Transistor wird nicht leitend
und Bitleitung bleibt auf 1
Wortleitung
Bitleitung
Gnd
Floating Gate
Transistor
Vdd
Löschen durch Bestrahlung mit UV-Licht: − UV-Licht verringert Widerstand des Isolators
zwischen FG und Substrat − Ladungsträger können vom FG in das Substrat
abfließen
EEPROM und Flash
Electrical Erasable and Programmable ROM − Aufbau wie beim EPROM − Dünnere Isolierschichten erlauben das Entladen des FG duch Anlegen
einer elektr. Spannung − Zusätzlicher Transistor wird zur Adressierung einer Bitzelle benötigt
Flash-Speicher
− Aufbau wie beim EEPROM − Nicht mehr jede Bitzelle ist einzeln löschbar − Zusammenfassen zu Pages zum Löschen − Dadurch wird zweiter Transistor nicht mehr benötigt und eine höhere
Speicherdichte erreicht
Dynamic RAM (DRAM) Zelle
Speichert ein Bit in einem Kondensator − Ladung vorhanden ® Bit = 1 − Ladung nicht vorhanden ® Bit = 0
Aufbau einer Bitzelle aus:
− Einem Transistor − Einem Kondensator
Ladung geht durch Leckströme verloren
Wert muss deshalb in regelmäßigen Abstand neu geschrieben werden (Refresh)
Wortleitung
Bitleitung
Gnd
Transistor
Kondensator
Organisation mit Zeilen- und Spaltenadressierung
Bei einstufiger Adressierung werden für große Speicher sehr viele Zeilen benötigt
Gatteranzahl im Zeilendekoder: n*2n
Gatteranzahl bei
quadratischer Matrix: 2*(n/2)*2n/2+3*(n/2)
0 0 1 0 R
1 0 1 0 R
0 0 1 0 R
1 1 0 0 R
…
Zeile
n-De
code
r
n
DataIn
…
…
…
…
Gnd
0
0
0
0
Spalten-Decoder
m
n Ad
ress
bits
m
Adr
essb
its
Mux 1
wrEnbl
n+m
Adr
esse
Lesen bei Zeilen- und Spaltenadressierung
Zeilendekoder aktiviert eine Zeile
Spalten-Dekoder hält alle Dateneingänge auf hochohmig
Mux wählt anhand der Spaltenadresse ein Bit aus
0 0 1 0 R
1 0 1 0 R
0 0 1 0 R
1 1 0 0 R
…
Zeile
n-De
code
r
n
DataIn
…
…
…
…
Gnd
1
0
0
0
Spalten-Decoder
m
n Ad
ress
bits
m
Adr
essb
its
Mux 1
wrEnbl
n+m
Adr
esse
0
z z z z
1 1 0 0
Schreiben bei Zeilen- und Spaltenadressierung
Zeilendekoder aktiviert eine Zeile
Spalten-Dekoder aktiviert eine Spalte und hält alle anderen Dateneingänge auf hochohmig
0 0 1 0 R
1 1 1 0 R
0 0 1 0 R
1 1 0 0 R
…
Zeile
n-De
code
r
n
DataIn
…
…
…
…
Gnd
1
0
0
0
Spalten-Decoder
m
n Ad
ress
bits
m
Adr
essb
its
Mux 1
wrEnbl
n+m
Adr
esse
1
z 1 z z
1 1 1 0
1
Blockorganisation bei Zeilen-/Spaltenadressierung
Durch Organisation in Blöcken kann die Datenwortbreite n des Speicher bestimmt werden
Block i speichert Bit i des Datenwortes von Adresse (n,m) Ze
ilen-
Deco
der
n
DataIn_0
…
m
n Ad
ress
bits
m
Adr
essb
its
1
wrEnbl
n+m
Adr
esse
Speichermatrix (Block 0)
Spalten-Decoder
Mux
DataIn_n
…
1
Speichermatrix (Block n)
Mux
… …
DataOut_0 DataOut_n
…
Multi-Ported SRAM
Lesen bzw. Schreiben von mehreren Bitzellen gleichzeitig
Im Beispiel: − Gleichzeitiges auslesen zweier Bitzellen oder − gleichzeitiges Schreiben zweier Bitzellen oder − Lesen einer Bitzelle und Schreiben einer zweiten Bitzelle
Anwendung unter Anderem zur Implementierung
großer Registerbänke
Wort- leitung 1
BL1
Wort- leitung 2
BL2 BL2 BL1
Zeile
n-De
code
r
Spalten-Decoder
Mux BL2
Zeile
n-De
code
r
Zeile
n-De
code
r
Mux BL1
read
Addr
1 read
Addr
2 writ
eAdd
r
Matrixorganisation für SDRAM
Adresse wird oft gemultiplext, um Anzahl der Adressleitungen kleiner zu halten − Zeilenteil speichern (RAS = 1) − Spaltenteil speichern (CAS = 1)
Leseverstärker (= SRAM Zelle) dient der
Speicherung des ausgelesenen Wertes
Zeile
n-De
code
r
n …
2m
Speichermatrix (Block 0)
Leseverstärker/Schreiblogik
… … Pu
ffer Z
eile
nadr
esse
Pu
ffer S
palte
nadr
esse
Spalten-MUX/DEMUX wrEnbl m
Data
1
A0 A1
An
Bitleitung Bitleitung
Leseverstärker
RAS
CAS
…
… … …
WL1
WL2
WL3
…
…
…
…
…
SDRAM lesen (1)
Zeilenadresse übernehmen − Zeilenadresse auf Adressbus legen − RAS-Signal aktivieren
Alle Leseverstärker übernehmen Werte der Bitzellen
aus aktivierter Wortzeile (Kondensator entlädt sich)
Übernommene Werte im Leseverstärker werden damit auch in die Zellen zurückgeschrieben (Kondensator wieder aufgeladen)
Zeile
n-De
code
r
Puffe
r Spa
ltena
dres
se
Spalten-MUX/DEMUX wrEnbl m
Data 1
Leseverstärker
RAS = 1
CAS
1 …
…
…
…
…
Puffe
r Zei
lena
dres
se
1 0
clk
RAS
CAS
addr row
data
cmd
SDRAM lesen (2)
Spaltenadresse übernehmen − Wert auf Adressbus legen − CAS-Signal aktivieren nach tRCD Takten
Spalten-Mux wählt zugehörige Bitleitung aus
Daten werden auf Datenbus gelegt (nach tCL
Takten)
Zeile
n-De
code
r
Puffe
r Spa
ltena
dres
se
Spalten-MUX/DEMUX wrEnbl m
Data
1
Leseverstärker
RAS = 0
CAS
1 …
…
…
…
…
Puffe
r Zei
lena
dres
se
1 0
clk
RAS
CAS
addr
RAS to CAS Delay (tRCD)
row col
data data
CAS Latency (tCL)
cmd read
SDRAM schreiben (1)
Zeilenadresse übernehmen − Zeilenadresse auf Adressbus legen − RAS-Signal aktivieren
Alle Leseverstärker übernehmen Werte der Bitzellen
aus aktivierter Wortzeile (Kondensator entlädt sich)
Übernommene Werte im Leseverstärker werden damit auch in die Zellen zurückgeschrieben (Kondensator wieder aufgeladen)
Leseverstärker enthält den aktuellen Wert der zu beschreibenden Zeile
Zeile
n-De
code
r
Puffe
r Spa
ltena
dres
se
Spalten-MUX/DEMUX wrEnbl m
Data 1
Leseverstärker
RAS = 1
CAS
1 …
…
…
…
…
Puffe
r Zei
lena
dres
se
1 0
clk
RAS
CAS
addr row
data
cmd
SDRAM schreiben (2)
Spaltenadresse in Puffer übernehmen
Datum an Dateneingang anlegen
WrEnbl-Signal aktivieren
DeMux überschreibt Wert im Leseverstärker
Aktivierte Zeile übernimmt geänderte(n) Wert(e) Zeile
n-De
code
r
Puffe
r Spa
ltena
dres
se
Spalten-MUX/DEMUX wrEnbl m
Data
0
Leseverstärker
RAS = 0
CAS
0 …
…
…
…
…
Puffe
r Zei
lena
dres
se
0 1
clk
RAS
CAS
addr
RAS to CAS Delay (tRCD)
row col
data data
CAS Latency (tCL)
cmd write
SDRAM Timing
Bezeichnung bei SDRAMs: PCxxx tCL-tRCD-tRP
xxx gibt die maximale Taktfrequenz des Speicherbusses an (clk)
tRCD: Anzahl Takte zwischen Anlegen der Zeilenadresse (Aktivierung des Speichers) und Anlegen der Spaltenadresse (Übertragen eines Kommandos (read/write))
tCL: Anzahl der Takte vom Anlegen der Spaltenadresse (und starten eines Kommandos (read/write)) bis zum Abschluss des Kommandos (Daten liefern bei read, Daten geschrieben bei write)
tRP: RAS-Vorladezeit (RAS Precharge Time), d.h. die Anzahl der Takte vom Beenden des letzten Zugriffszyklus bis zum Beginn des nächsten Zugriffszyklus
clk
RAS
CAS
addr
RAS to CAS Delay (tRCD)
row
data
CAS Latency (tCL)
cmd write precharge
col
data
row
RAS Precharge Time (tRP)
DRAM Refresh
DRAM Refresh DRAM-Zelle verliert Ladung durch Leckströme auch ohne ausgelesen zu werden
Auffrischen des gespeicherten Wertes erforderlich (ca. alle 8 bis 64 ms)
Auffrischen mittels Schreib-/Leseverstärker an Datenleitungen einfach durch Auslesen
einer Zeile möglich (wird dadurch mit gleichen Werten aufgefrischt)
Organisation Refresh Jede Zeile wird in regelmäßigen Abständen von 8 bis 64 ms gelesen
Es wird ein Zähler in den SDRAM integriert, der die aufzufrischende Zeilennummer
enthält
Memory-Controller erzeugt periodisch ein Kommando (Kombination von Steuersignalen die sonst nicht benötigt wird (z.B. CAS-before-RAS), wodurch im DRAM ausgelöst wird: − Lesen der im Zähler gespeicherten Zeile − Inkrementieren des Zählers
Fallstudie Speicherorgansiation
Unterschiedliche Ausführungen von Speichermodulen möglich: − Single Inline Memory Module (SIMM)
• 72 Kontaktpins auf einer Seite • 32 Bit pro Takt können übertragen werden
− Double Inline Memory Module (DIMM) • Kontaktreihen (insgesamt 240) und Speicherchips auf beiden Seiten • 64 Bit je Takt können übertragen werden
Kontaktreihe
Speicherchip (z.B. 512 MBit) ergibt eine Gesamtkapazität von 1 Gyte)
Speichermodul
4096K x 1 Speicherchip
(4 Mbit)
4096K x 1 Speicherchip
(4 Mbit)
Fallstudie Speicherorganisation (1)
Jeder Chip hat einen Datenausgang 32 Chips werden benötigt für einen Speicher mit 32-Bit Datenworten (eher
unhandlich)
4096K x 1 Speicherchip
(4 Mbit)
A0 A1 A2 A3 A4 A5 A6 A7 A8 A9
A10
\RAS \CAS
D0
\CS \WE \OE
D6
D31
Intern ist der Chip als 2048 x 2048 Matrix organisiert
Fallstudie Speicherorganisation (2)
Eher üblich: Chips mit 4, 8 oder 16 Bit Datenausgängen Dann nur 2, 4 oder 8 Chips pro Modul für 32-Bit Datenworte
erforderlich
32M x 16 Speicherchip
(512 Mbit)
A0 A1 A2 A3 A4 A5 A6 A7 A8 A9
A10 A11 A12
\RAS \CAS
Bank 0 Bank 1
D0
D1
D2
D3
D4
D6
D7
D5
\CS \WE \OE
D8
D9
D10
D11
D12
D14
D15
D13
Im Beispiel links: Ein Chip hat 4 interne Speicherbänke mit je
128 MBit Jede Speicherbank ist aus 16 8192 x 1024
Matrizen organisiert (8192 Zeilen, 1024 Spalten)
Zeile
n-De
code
r
13 …
1
8192 x 1024 Speichermatrix
Spalten-Decoder
10
1
8192 x 1024 Speichermatrix
Spalten-Decoder 1
8192 x 1024 Speichermatrix
Spalten-Decoder
16
Anbindung des Speichers an den Prozessor
Prozessor Memory Controller
Speicher- module 1
Speicher- module k
Adress- und Datenbus physikalische Adresse
Chip-Select-Signal
…
Aufbau Speichercontroller
Anforderungspuffer nehmen physikalische Adressen (+Daten) von verschiedenen Quellen auf
Adressabbildung erzeugt aus physikalischen Adressen (Zeilenadresse, Spaltenadresse, Bank, Modul)
Arbiter plant die Reihenfolge der Speicherzugriffe und initiiert Refresh-Zyklen
Kommandogenerierung kommuniziert mit dem Speichermodul unter Beachtung des Timings
Anforderungspuffer
Adress- abbildung Kommandogenerierung Arbiter
Ausgabepuffer
Zusammenfassung Speicherimplementierung
Aufbau und Arbeitsweise verschiedener Speicherzellen
Matrix-Organisationsformen − mit Zeilendecoder − mit Zeilen- und Spaltendecoder − Blöcke − Multi-Ported − Adressmultiplexing
Organisation von SDRAM in Speicherchips und -modulen
− Timing − Speichercontroller
Inhalt
Aufbau von Speicher
Organisation der Speicherhierarchie
Cache
Cache: Kleiner aber schneller Pufferspeicher
Zugriff auf den Cache um Faktor 10 bis 40 schneller als auf den Hauptspeicher
Zum Glück trifft meistens das Lokalitätsprinzip zu: − in kurzer Zeit (zeitliche Lokalität) greift ein Programm auf nah beieinander liegende Daten zu (räumliche
Lokalität)
Cache-Controller − liest/schreibt Daten aus dem/in den Cache falls Daten im Cache gepuffert − Wenn nicht, dann über Memory-Controller benötigten Adressbereich in den Cache holen
Chip
Core Adresse
Cache Cache Controller
Daten
Adresse
Daten
Memory Controller
Speicher- module
Speicher- module
Adre
sse Daten
…
Organisationsprinzip eines Caches
Hauptspeicher ist in Blöcke der Größe 2n eingeteilt Datenaustausch zwischen Cache und Hauptspeicher nur blockweise Cache besteht aus 2m Cache-Lines Jede Cache-Line enthält einen Block Gruppierung von je 2k Cache-Lines zu einem Set; 2k-fach assoziativer Cache 2k = 1: Cache mit direkter Abbildung 2k = 2m: vollassoziativer Cache
Cache Line Wort 1 Wort 2 Wort n …
Wort n+1 Wort n+2 Wort 2n …
Wort 1 Wort 2 Wort 2n …
Wort 1 Wort 2 Wort 2n …
Wort 2n+1 Wort 2n+2 Wort 3n …
Wort 3n+1 Wort 3n+2 Wort 4n …
Set 1
Wort 1 Wort 2 Wort 2n …
Wort 1 Wort 2 Wort 2n …
Wort 1
Wort 2a
Wort 2n
Hauptspeicher mit 2a Datenworten Cache (hier 4-fach assoziativ)
Wort 2n+1
…
…
Block 1
Block 2a-n
Wort 2a-2n+1
…
Set 2m-k
Wie werden Hauptspeicher-
adressen auf Cache-Adressen
abgebildet?
Daten Adresse
0
2n-1
2n
2a-1
…
Daten Adresse
0
1
2
3
2m-4
2m-3
2m-2
2m-1
Adressierung des Caches (1)
Hauptspeicheradresse wird aufgeteilt in Blockoffset-Bits:
− Adressieren Datenwort innerhalb eines Blocks (Cacheline) Set-Bits (oder Indexbits):
− Kodieren die Nummer des Sets, in dem der Block der das Datenwort enthält abgelegt wird
− In einem k-fach assoziativen Cache (k > 1) kann dieser Block in einer beliebigen Cache-Line innerhalb des Sets abgelegt werden
Tag-Bits: − Zur Identifizierung eines Blocks im Cache
Adresse im Hauptspeicher (a Bits)
Blockoffset Set-Adresse Tag-Bits
0 n-1 n n+m-k-1 n+m-k a-1
n Bits m-k Bits a-(m-k)-n Bits
Cache-Line Cache-Line Cache-Line Cache-Line
Tag Tag Tag Tag
Cache-Line Tag Cache-Line Tag Cache-Line Tag
Set 0
Set 1
Set 2
Set 3
…
V V V V V V V
Set- Adresse
0
1
2
3
valid
-bit
Aufbau Cache mit direkter Abbildung
Direkt abgebildeter Cache für 32-Bit Adressen mit 1024 Cache-Lines
(10 Indexbits erforderlich)
Blockgröße: 16 Byte (4 Offsetbits erforderlich)
Sehr gute Hit-Time: Takte bis das Datum bei einem Treffer geliefert wird
Tag <18> Index <10>
Valid 1 <1> Tag 1 <18> Daten 1 <16 Byte>
Valid 2 <1> Tag 2 <18> Daten 2 <16 Byte>
Valid 3 <1> Tag 3 <18> Daten 3 <16 Byte>
Valid 4 <1> Tag 4 <18> Daten 4 <16 Byte>
… …
Valid 1024 <1> Tag 1024 <18> Daten 1024 <16 Byte>
Offset <4>
=
18 10 4
16:1 Mux
Data Hit
Aufbau 4-fach assoziativer Cache
4-fach assoziativer Cache für 32-Bit Adressen mit 1024 Cache-Lines und 4 Cache-Lines je Set (8 Indexbits erforderlich) Blockgröße: 16 Byte (4 Offsetbits erforderlich) Hit-Time etwas schlechter wegen 4:1-Mux
Tag <20> Index <8> Offset <4>
25 9 3
hit
V1 Tag 1 Daten 1
V2 Tag 2 Daten 2
V3 Tag 3 Daten 3
V4 Tag 4 Daten 4
… …
V256 Tag 256 Daten 256
V1 Tag 1 Daten 1
V2 Tag 2 Daten 2
V3 Tag 3 Daten 3
V4 Tag 4 Daten 4
… …
V256 Tag 256 Daten 256
V1 Tag 1 Daten 1
V2 Tag 2 Daten 2
V3 Tag 3 Daten 3
V4 Tag 4 Daten 4
… …
V256 Tag 256 Daten 256
V1 Tag 1 Daten 1
V2 Tag 2 Daten 2
V3 Tag 3 Daten 3
V4 Tag 4 Daten 4
… …
V256 Tag 256 Daten 256
= = = =
OR
16:1 Mux
4:1 Mux
data
Was passiert bei Cache-Miss
Cache-Miss: Datum liegt nicht im Cache vor − Miss-Rate: Anzahl Cache-Misses / Gesamtanzahl der Cachezugriffe − Miss-Penalty: Anzahl Takte, bis das Datum nach einem Cache-Miss geliefert wird
Block, der das Datum enthält, wird aus dem Hauptspeicher geholt und ersetzt
einen Block im Cache
Für direkt abgebildete Caches ist der ersetzte Block eindeutig
Für assoziative Caches ist eine Auswahl innerhalb des Sets möglich − Zufällig − Least-Recently Used: Ersetze den Block, der die längste Zeit ungenutzt war − First-In, First-Out: Ersetze den ältesten Block
Vor dem Ersetzen muss der alte Block evtl. in den Speicher zurückgeschrieben
werden; hängt vom Verhalten bei Schreiboperationen ab
Was passiert bei Schreiboperationen?
Prüfen, ob zu schreibende Adresse im Cache
Falls ja (Write-Hit), dann − Write-Through:
• Daten werden in Cache und darunterliegende Speicherebenen geschrieben • Kohärenz der Daten ist dadurch gegeben • Oft werden write-buffer verwendet, damit der Prozessor weiterarbeiten kann
− Write-Back: • Daten werden nur in den Cache geschrieben • Geht schnell und erfordert geringere Speicherbandbreite • Bei Ersetzung muss Block in darunterliegende Speicherebenen geschrieben werden
Falls nein (Write-Miss), dann
− Write Allocate: • Block wird in den Cache geholt und anschließend wird die Schreiboperationen wie bei einem
Write-Hit ausgeführt − No-Write Allocate:
• Daten werden nur in den Hauptspeicher geschrieben
Beispiel: AMD Opteron Daten-Cache
64KByte Cache, 64 Bytes je Cache-Line, 2-fach assoziativ mit LRU, write-back und write-allocate
Hit-Time: 2 Takte
Bei einem Read-Miss werden 64-Byte aus dem L2-Cache geholt − 7 Takte braucht das Lesen der ersten 8 Byte − jeweils 2 weitere Takte die darauf folgenden 8 Byte-Gruppen − zu überschreibende Cache-Line wird an einen Victim-Buffer gesendet
(write-buffer); dieser kann bis zu acht Cache-Lines aufnehmen − Aus dem Victim-Buffer werden die Daten in den L2-Cache geschrieben
Opteron L1-Cache
Tag <25> Index <9>
Valid 1 <1> Tag 1 <25>
… …
Valid 512 <1> Tag 512 <25>
CPU
Adresse
Data In Data Out
Offset <6>
Data 1 <64>
…
Data 512 <64>
Valid 1 <1> Tag 1 <25>
… …
Valid 512 <1> Tag 512 <25>
Data 1 <64>
…
Data 512 <64>
=
=
25 9 3
2:1 Mux Victim Buffer
L2 Cache
Maßnahmen zur Verbesserung der Cache-Leistung (1)
Größere Blöcke: − Reduzieren Miss-Rate durch Nutzung räumlicher Lokalität − Erhöhen aber Miss-Penalty, weil mehr Daten nachgeladen werden müssen
Größere Caches:
− Reduzieren Miss-Rate; − Erhöhen aber die Hit-Time − L1-Cache wird i. Allg. klein gehalten, damit er schnell ist (L1-Cache Größe ist im K6,
Athlon und Opteron gleich geblieben)
Höhere Assoziativität: − Verringert die Miss-Rate − Erhöht aber die Hit-Time
Multi-Level-Caches:
− Reduzieren Miss-Penalty
Maßnahmen zur Verbesserung der Cache-Leistung (2)
Cache-Line-Vorhersage: − In einem assoziativen Cache wird zu jedem Set ein Predictor hinzugefügt, der vorhersagt, welche Cache-Line
beim nächsten Zugriff angesprochen wird (z.B. im P4 verwendet) − Multiplexer kann schon die Tag-Bits der vorhergesagten Cache-Line auswählen für den Vergleich
Pipelined Cache-Zugriff:
− Holen einer Instruktion ist auf mehrere Takte aufgeteilt (im Pentium 1 Takt pro Befehls-Cache-Zugriff, im P4 4 Takte)
Nicht blockierende Caches:
− Nach einem Cache-Miss kann der Cache weitere Anfrage bedienen (in der Regel solange ein Cache-Hit vorliegt)
Critical-Word-First:
− Beim Nachladen eines Blocks aus einer niedrigeren Speicherebene wird das benötigte Wort sofort an den Prozessor geliefert, sobald es im Cache vorliegt
− Restliche Worte des Blocks werden danach aufgefüllt
Prefetching: − Es werden spekulativ Blöcke nachgeladen − Hardware-basiert: nächster Speicherblock für Befehlscache wird angefordert − Compiler-basiert: Der Compiler fügt geeignete Prefetch-Operationen ein
Zusammenfassung Caches
Direkt abgebildeter Cache Vorteile
− Effizientere Speicherung, d.h. weniger Overhead durch Tags und Valid Bits − Effizienterer Datentransfer
Nachteile
− Größere Miss-Rate Assoziativer Cache Vorteil
− Miss Rate wird reduziert, weil mehrere Blöcke mit gleicher Set-Adresse im Cache gehalten werden können
Nachteile − Hit Time wird durch erhöhten Vergleichsaufwand etwas vergrößert − Bei hoher Assoziativität wird der Hardwareaufwand beträchtlich
Weitere Methoden zur Verbesserung der Cache-Leistung Multi-Level-Caches, Cache-Line-Vorhersage, …
Virtuelle Speicherverwaltung
Jeder Task hat seinen eigenen virtuellen Adressraum
Virtueller Adressraum kann größer sein als physisch vorhandener Speicher
Virtueller Adressraum ist in Seiten unterteilt
Seiten können beliebig auf die Seitenrahmen im physischen Speicher verteilt sein oder auf HDD ausgelagert
Page 1 Page 2 Page 3 Page 4
Page n
…
0x00000000
0xFFFFFFFF
~4KByte 0x00001000
…
virtuelle Adresse
…
0x000000
0xFFFFFF
0x001000
physische Adresse
Seiten Seiten- rahmen
HDD
Organisation der virtuellen Speicherverwaltung
MMU bildet virtuelle Adressen auf physische Adressen ab
Rest des Systems arbeitet mit physischen Adressen
Chip
Core virt.
Adresse
Cache Cache Controller
Daten
phys. Adresse
Daten
Memory Controller
Speicher- module
Speicher- module
Adre
sse Daten
…
Memory Management
Unit (MMU)
Daten
phys. Adresse
Paging: Adressabbildung
Eine virtuelle Adresse wird aufgeteilt in eine virtuelle Seitennummer, die auf eine physikalische Rahmennummer abgebildet wird
einen Seitenoffset, der die Adresse innerhalb einer Seite darstellt
− Anzahl der Bits im Seitenoffset bestimmt die Größe einer Seite
Virtuelle Seitennummer Seitenoffset
Virtuelle Adresse
Physikalische Rahmennummer Seitenoffset
Physische Adresse
Abbildung
Finden von Pages Finden von Pages wird durch Seitentabelle (Page Table) realisiert:
− Für jede virtuelle Seitennummer wird die dazugehörige physische Rahmenadresse gespeichert − Valid Bit zeigt an, ob sich die gesuchte Page im Hauptspeicher befindet − Seitentabelle ist selbst im Speicher abgelegt − Seitentabellenregister (z.B. CR3 bei x86-Prozessoren) speichert physische Startadresse der Seitentabelle
Beispiel
− 48-Bit virtueller Adressraum, 4 KByte Page Size, 8 Byte pro Eintrag in der Seitentabelle − Größe der Seitentabelle ~550 GB
Virtuelle Seitennummer Seitenoffset
Virtuelle Adresse
Seitentabelle
Hauptspeicher
+ physikalische Adresse des
Rahmens (Rahmennummer)
HDD
phys. Addr. Attributes
CR3
present?
+
Data
ja
Betriebssystem
nein
Daten lesen
Aktionen des OS bei Seitenfehler
Seite i ist nicht im Speicher: Virtuelle Adresse, die den Fehler verursachte wird in Register CR2 geschrieben und Page-Fault-Exception ausgelöst
OS überprüft, ob ein Seitenrahmen x im Hauptspeicher leer ist
Falls nicht, dann wird eine Seite aus einem Rahmen x aus dem Hauptspeicher auf HDD ausgelagert und Seitentabelle aktualisiert
OS holt Seite i von HDD, schreibt diese in Rahmen x und aktualisiert die Seitentabelle
Speicherzugriff, der die Exception verursachte, kann ausgeführt werden
Paging im AMD Opteron
Seitenoffset
0 11
Seitentabelle
12 20
Seitendirectory
21 29
Seiten-dir.-zeiger
30 38
Seitenkarte
39 47
0‘en oder 1‘en
48 63
+ CR3-Register
Seitentabelle Seitentabelle
Seitentabelle Seitentabelle
Tabelleneintrag + Tabelleneintrag +
Tabelleneintrag + Tabelleneintrag
Rahmennummer (28 Bit) Offset (12 Bit)
Physikalische Adresse (40 Bit) 1 TByte adressierbar
Virtuelle Adresse
physikalische Startadresse der nächsten Tabelle Index in die nächsten Tabelle
Eigenschaften des Pagings im Opteron
Jede Tabelle hat 512 Einträge mit 8 Byte pro Eintrag (= 4KByte; entspricht Seitengröße)
Alle Tabellen befinden sich im Speicher; Adressberechnung findet aber in HW statt; Adressen der Tabellen müssen deswegen physikalische Adressen sein
Bei Prozesswechsel wird auch CR3 umgeschaltet; jeder Prozess hat seine eigenen Seitentabellen
Zugriff auf gemeinsam genutzten Speicher von Prozessen durch Verweise auf gleiche physikalische Adressen in den verschiedenen Tabellen
Ein Speicherzugriff erfordert 4 weitere Speicherzugriffe (auch Programmspeicherzugriffe in der Befehlsholphase)
Beschleunigung durch Translation Lookaside Buffer (TLB)
TLB
TLB ist ein Cache für die schnelle Abbildung virtueller Seitennummern auf physikalische Rahmenadresse
Virtuelle Adresse wird zuerst im TLB gesucht
Bei Treffer im TLB kann sofort die Rahmenadresse genutzt werden
Sonst muss in Seitentabellen gesucht werden − Gefundene Rahmennummer verdrängt ältesten Eintrag aus dem TLB
Aufbau TLB
Beispiel AMD Opteron TLB für Daten − Vollassoziativ − 40 Einträge
Seitenoffset
0 11 12
Seitenkarte + Seiten-dir.-zeiger + Seitendirectory + Seitentabelle
47
Physikalische Rahmenadresse Tag
…
…
= =
= 40:1 Mux De
code
r
Eigenschaften TLB
TLB ist transparent für die Software
Änderungen an der Seitentabelle führen zu einer veränderten Abbildung virtueller auf physikalische Adressen
Diese Änderungen können dem TLB nicht mitgeteilt werden
Bei Änderungen an den Seitentabellen (Taskwechsel oder Ein-/Auslagern von Seiten) muss der TLB deshalb gelöscht werden
Jeder Prozess benötigt eigenen TLB (oder gemeinsamer TLB muss vor Prozesswechsel geleert werden)
Mit welchen Adressen arbeitet der Cache?
Cache arbeitet mit virtuellen Adressen (VIVT)
Tagbits im Cache gehören zur virtuellen
Adresse
Indexbits für Cache-Zugriff stammen aus der virtuellen Adresse
Erst bei einem Cache-Miss werden virtuelle in physikalische Adressen übersetzt
Cache arbeitet mit physikalischen Adressen (PIPT) Es werden erst virtuelle Adressen in
physikalische Adressen übersetzt
Indexbits für Cachezugriff stammen aus physikalischer Adresse
Tagbits stammen aus physikalischer Adresse
CPU
virt.
Adresse Cach
e
Cach
e Co
ntro
ller Daten
phys. Adresse
Daten
Übrige Speicherebenen
Adresse Daten
Memory Management
Unit (MMU)
Daten
phys. Adresse
CPU
virt. Adresse Ca
che
Cach
e Co
ntro
ller Daten
virt. Adresse
Daten
Memory Management Unit (MMU)
Daten virt. Adresse
phys. Adresse
Daten
Übrige Speicherebenen
VIVT
Schneller Zugriff auf den Cache (keine Adressübersetzung erforderlich)
Verschiedene Prozesse arbeiten mit gleichen virtuellen Adressen − Gleiche virtuelle Adressen beziehen sich auf verschiedene physikalische Adressen
(Homonyms) − Cache muss vor Prozesswechsel geleert werden, sonst werden falsche Daten geliefert
Mehrere virtuelle Adressen beziehen sich auf dieselbe physikalische Adresse
(Alias) − Dadurch können Kohärenz-Probleme im Cache entstehen, weil mehrere Kopien der
gleichen physikalischen Adresse gespeichert werden können
CPU
virt. Adresse Ca
che
Cach
e Co
ntro
ller Daten
virt. Adresse
Daten
Memory Management Unit (MMU)
Daten virt. Adresse
phys. Adresse
Daten
Übrige Speicherebenen
PIPT
Cache arbeitet mit physikalischen Adressen Zuerst Adressübersetzung erforderlich bevor auf den Cache zugegriffen
werden kann
Dadurch längere Zugriffszeiten
Prozesswechsel unproblemtisch − Keine Homonyms − Keine Aliase
CPU
virt. Adresse Ca
che
Cach
e Co
ntro
ller Daten
phys. Adresse
Daten
Übrige Speicherebenen
Adresse Daten
Memory Management
Unit (MMU)
Daten
phys. Adresse
Mischform VIPT
Virtuell indizierter Cache, Physikalische Tagbits (VIPT)
Schneller Zugriff auf den Cache möglich (ohne Adressübersetzung)
Parallel dazu wird virtuelle Adresse in physikalische Adresse umgewandelt
Physikalische Tagbits werden mit Tagbits im Cache abgeglichen
Anwendung für L1-Cache
L2- und L3-Cache üblicherweise PIPT
Aufbau bei VIPT
Seitenoffset <13> Virtuelle Seitennummer <51>
Virtuelle Adresse <64>
TLB Tag <43> TLB Index <8>
TLB Tag 1 <43> TLB Daten 1 <28>
… …
TLB Tag 256 <43> TLB Daten 256 <28>
L1 Cache Index <7> Offset <6>
L1 Cache Tag 1 <28> L1 Cache Daten 128 <512>
… …
L1 Cache Tag 128 <28> L1 Cache Daten 128 <512>
Phys Frame Addr <28> = ja, dann Cache Treffer zur CPU
zur Auswahl des Datenworts
Physikalische Adresse <41>
L2 Tag <19> L2 Index <16> L2 Offset <6>
TLB Tag 1 <43> TLB Daten 1 <27>
… …
TLB Tag 256 <43> TLB Daten 256 <27>
=
ja, dann Cache Treffer
um Cache Index erweitert
Eigenschaften
Zugriff auf TLB und L1 Cache kann parallel erfolgen − Adressübersetzungszeit des TLB kann versteckt werden
Wird Eintrag im TLB nicht gefunden, dann bremst Übersetzung in
physikalische Adressen den L1 Cache aus
Homonyms werden vermieden − Tagbits repräsentieren Physikalische Rahmennummer − Damit lässt sich die physikalische Adresse bilden und abgleichen
Aliase können auftreten, wenn Cache-Index unteren Teil der virtuellen
Seitennummer verwendet
Verwendung VIPT in vielen aktuellen Prozessoren − z.B. Opteron
Opteron Speicherhierarchie
Virtuelle Seitennummer Offset
ITLB L1
Vollassoziativ 40 Einträge
ITLB L2
128-fach-assozitativ 4 Blöcke
ICache L1
2-fach assoziativ 512 Sets 64 Byte je Cacheline
phys. Rahmen
phys. Rahmen
Instruction
ICache L2
16-fach assoziativ 1024 Sets
Instruction
Virtuelle Seitennummer Offset
DTLB L1
Vollassoziativ 40 Einträge
DTLB L2
128-fach-assozitativ 4 Blöcke
DCache L1
2-fach assoziativ 512 Sets 64 Byte je Cacheline
phys. Rahmen
phys. Rahmen
Data
Victim Buffer
8 Plätze für je 64 Byte
System Chip memory crossbar
Data Off-Chip Speicher
Instruction Data
miss
Zusammenfassung
Speicherimplementierung − SRAM, DRAM, ROM
Caches
− einfach-, mehrfach-assoziativ
Virtuelle Speicherverwaltung mit Seiten − Mehrstufige Adressabbildung − TLBs
Reale Speicherhierarchie mit virtueller Adressierung
− Multi-Level Caches − Mehreren TLBs