Speicherorganisation
Hauptspeicher
Cache-Speicher und -Organisation
Virtuelle Speicherverwaltung
Anbindung des Hauptspeichers und von Ein- und Ausgabekomponenten
Speicherorganisation
Hauptspeicher
Technologische Grundlagen
Static Random Access Memory
Dynamic Random Access Memory
Flash-Speicher
Cache-Speicher und -Organisation
Vorraussetzungen und Begriffsdefinition
Vollassoziativer Cache-Speicher
Direkt abgebildeter Cache-Speicher
n-Wege-Satzassoziativer Cache-Speicher
Platzierung des Caches in Bezug auf die virtuelle Speicherverwaltung
Verdrängungsstrategien, Schreibzugriffe
Cache Kohärenzprotokolle
Virtuelle Speicherverwaltung
Segmentierung
Seitenwechselverfahren
Anbindung des Hauptspeichers und von Ein- und Ausgabekomponenten
DRAM-Speichercontroller
Memory Mapped I/O
Vollassoziativer Cache-Speicher
Direkt abgebildeter Cache-Speicher
n-Wege-Satzassoziativer Cache-Speicher
1.) Speicher
2.) Organisation
3.) Anbindung
1.) Cache
2.) Virtuell
3.) Hauptspeicher
4.) Ein und Ausgabekomponenten
Speicher
Personal Computer
von Neumann Architektur
DRAM Dynamic Random Access Memory
eingebettete Systeme, Server
Harvard Architektur: Daten und Programmspeicher getrennt
SRAM Static Random Access Memory
Nur-Lese Speicher, häufig: Flash basierter Speicher
1.) Personal Computer
2.) Eingebettete Systeme
3.) Server
Von-Neumann
CPU <-> Programm und Datenspeicher
Addressbus
Datenbus
Steuerbus
Harvard
CPU <-> Programmspeicher
Adressbus
Datenbus
CPU <-> Datenspeicher
Addressbus
Datenbus
CPU <-> Gemeinsam
Steuerbus
Multi-Port Speicher
Multi-Port Speicher: mehrere Operanden
Speicherhierarchie
1.) Register
2.) Level-1-Cache
3.) Level-2-Cache
4.) Hauptspeicher
5.) Festplattenspeicher (magnetisch, Flash)
6.) Optische Wechselmedien
Speicherhierarchie:
Von unten Nach oben : Zugriffsgeschwindigkeit steigt
Von oben nach unten: Kapazität steigt, Kosten pro Bits sinken
1.) Register
2.) Level-1-Cache ^= L1-Cache
Wenige Taktzyklen
SRAM-Speicher
Harvard: Daten und Instruktionscache
2.) Level-2-Cache
Grösser als L1
Unified Cache: Daten und Programm werden häufig gemischt abgelegt
3.) Hauptspeicher
DRAM
4.) Festplatte
SSD
flüchtiger Speicher
Technologische Grundlagen
MOSFET - Metal Oxid Semiconductor Field Effect Transistor
Source
Drain
Gate
Bulk
Gate: Steuerung des Transistors
Betriebsspannung U_B
GND: 0V
Strom fliesst zwischen Source und Drain
Substrat: B: Häufig mit Source Kurzgeschlossen
1.) Transistor Selbstleitend
2.) Transistor Selbstsperrend
U_GS (Spannung)
Schwellenspannung: U_th
n-Kanal
p-Kanal
n-Kanal-Transistor: 0 < U_th < U_B
Ist U_GS < U_th
Widerstand zwischen Source und Drain ist gross
Widerstand zwischen Source und Drain: R_DS
I_DS: Strom zwischen Drain und Source
Transistor sperrt: I_DS
U_GS wird erhöht: U_th wird überschritten: Transistor leitet
Widerstand von Transistor: R_DS ~ 0 Ohm
Das war n-Kanal Transistor
p-Kanal-Transistor
Spannung: U_B
U_B am Gate Eingang -> U_GS = 0, Transistor sperrt
Bei Spannung U_GS < U_th Transistor leitet: R_DS ~ 0 Ohm
Strom I_DS > 0A fliesst
U_B als logische Variable 0 und 1 vorgestellt
Complementary-MOS-Schaltung
Beim n-Kanal-Transistor:
Anlegen einer 1 führt dazu Transistor leitet, bei 0, sperrt
Beim p-Kanal-Transistor:
Beim Anlegen von 1 sperrt der Transistor
0: Transistor leitet
CMOS: Complementary-MOS-Schaltung
SRAM
- Six Device Zelle
6 Transistoren: T0 bis T5
FET zeichnen, Schaltzeichen üben
DRAM
FET mit Kondensator
Refresh: 60 Milisekunden
Flash:
blitzartig löschen
NAND-Flash-Speicher
NOR-Flash Speicher
Flash-Zelle
Floating Gate MOS Transistor
FG-MOSFET
Erweiternug des klassischen n-Kanal-MOS FET
Untergebracht sind Floating Gate
Elektrode zwischen Isolator und Gate
Floating Gate: Zwei Isolatoren, Floating Gate
Das ganze wie MOS-FET aber mit zwei isolatoren
Auf das Floating Gate lässt sich Ladungen durch physikalische Effekte angebracht werden
Über Gate anschluss wird ein leitender Kanal zwischen Source und Drain etabliert
Solange Elektronen im Floating gate sind, verhält sich das FGMOSFET wie ein üblicher MOSFET
Die Ladung im Floating Gate, bleibt dauerhaft
Voll assoziativer Cache Speicher: Full associative Cache
Direkt Abgebildeter Cache: Direct Mapped Cache
n-Wege Satzassoziativer Cache: n-Way Set-Associative Cache
Cache
Trefferrate
Trefferrate muss entsprechend hoch sein
Trefferrate hängt von Lokalität ab
1.) Trefferrate
2.) Lokalität
Trefferrate
Trefferrate muss entsprechend hoch sein
Trefferrate hängt von Lokalität ab
Zeitliche Lokalität
Örtliche Lokalität
1.) Trefferrate
2.) Lokalität
2.1.) Zeitliche Lokalität
2.2.) Örtliche Lokalität
Zeitliche Lokalität: Temporale Lokalität
Örtliche: Spaziale Lokalität
Zeitliche Lokalität: Temporale Lokalität: Der Zugriff auf die gleichen Daten bzw. Programmcode wiederholt sich
Örtliche: Spaziale Lokalität: Daten werden in gewisser Ordnung im Speicher abgelegt: Beispiel Matrix
Hauptspeicher: Ortsaddressiert
Cache-Speicher: Inhaltsaddressiert
Trefferrate
Trefferrate muss entsprechend hoch sein
Trefferrate hängt von Lokalität ab
Zeitliche Lokalität
Örtliche Lokalität
Ortsaddressiert
Inhaltsaddressiert
Tag
Inhaltsaddressiert: Tag
Tag: um fest zu stellen, ob das gesuchte Datum im Cache
Kann an beliebiger Stelle hinterlegt werden
Vollassoziativ: Kann an beliebiger Stelle hinterlegt werden
An einer Teilweise vorgegebenenen Addresse liegen (n-Wege- Satzassoziativ oder direkt abgebildet)
Diese Art des Zugriffs wird Assoziativ-Speicher genannt
Trefferrate
Trefferrate muss entsprechend hoch sein
Trefferrate hängt von Lokalität ab
Zeitliche Lokalität
Örtliche Lokalität
Ortsaddressiert
Inhaltsaddressiert
Tag
Assoziativspeicher
Assoziativspeicher: Inhaltsaddressiert
Cache-Block
Cache-Zeile
In einen Cache-Block passt genau eine Cache-Zeile (Cache Line)
Trefferrate
Trefferrate muss entsprechend hoch sein
Trefferrate hängt von Lokalität ab
Zeitliche Lokalität
Örtliche Lokalität
Ortsaddressiert
Inhaltsaddressiert
Tag
Assoziativspeicher
Cache-Block
Cache-Zeile
Cache Zeile wird zwischen Hautpspeicher und Cache-Speicher hin und her kopiert
In einer Cache-Zeile werden mehrere Speicherwörter hinterlegt: 16 bis 128 Byte
Tag: Identifizierung: des Eintrags
Tag
Identifizierung des Eintrags
Prüfen ob vorhanden
Zugriffs und Verwaltungsinformationen
Gültigkeit: V-Bit (Valid-Bit)
Zeile wurde verändert: D-Bit (Dirty Bit)
1.) Wird ein Datum ein einer Bestimmten Addresse angefragt
2.) Erfolgt zunöchst eine Anfrage an den Cache
3.) Der Tag-Teil der Addresse wird mit dem Gespeicherten Tag verglichen
4.) Die Gültigkeit des Eintrags über die Verwaltungsinformationen wird geprüft
Kein Eintrag: Cache Zeile muss im Cache Speicher eingelagert werden
Trefferrate
Trefferrate muss entsprechend hoch sein
Trefferrate hängt von Lokalität ab
Zeitliche Lokalität
Örtliche Lokalität
Ortsaddressiert
Inhaltsaddressiert
Tag
Assoziativspeicher
Cache-Block
Cache-Zeile
Cache-Zeile Einlagern
Verdrängen von Cache-Einträgen
Sätze
Cache-Blöcke werden zu Sätzen zusammengefasst
1.) Cache-Block
2.) Cache-Zeile
3.) Sätze
Ein Satz ist für eine bestimmte Addresse zuständig
m: Anzahl der Cache-Blöcke
n: Anzahl der Cache-Blöcke pro Satz
Der Cache Speicher besteht aus
m/n Sätzen.
Vollassoziativ: Ein Satz der alle Cache-Blöcke enthält m=n: Der inhalt kann an jeder beliebigen Addresse ablegt werden
Cache-Speicher, besteht aus 16 Cache-Blöcken
Vollassoziativ: An jeder Zeile von 0 .. 15
Direkt Abgebildet: Jeder Satz enthält einen Block
n = 1
Es gibt so viele Sätze wie Blöcke
Ein Datum kann nur an einer einzigen Stelle abgelegt werden, entweder an
0, 1, ..., 15
aber nicht gleichzeitig an 2 und 7. Immer nur an einer.
n-Wege-Satz Assoziativ
n üblicherweise zwischen 2 und 8, m/2 (max)
In jedem Satz (Satz beliebig) kann eine Cache-Zeile in einem bestimmten Block abgelegt werden, also
1.) An Block 0, 1, 2, 3, ... (oder)
2.) In Satz entweder 0, 1, 2, 3,
Also: Block ist kleinere Einheit
Satz: ist grössere Einheit
Blöcke zu Satz zusammen gesetzt, zu Sätzen oder einem Satz
Bei Vollassoziativ: 16 Blöcke in einem Satz
Bei n-wege Satz Assoziativ: 4 Blöcke in Vier Sätzen
Merke: da bei Vollassoziativ in jedem Block, bei n-Wege Satzassoziativ: in einem beliebigen Block in einem bestimmten Satz
Also: Satz geht nur ein bestimmter
Block egal welcher
Der Satz: ist fest vorgeschrieben
Der Block ist beliebig
Gewagtes Gedankenexpirment: Die Physiker rufen: Herr Einstein, alles ist Relativ
Wenn ich einen Vollassoziativen Cache habe, habe ich - nur Blöcke und einen Satz. Satz ist eine Industrielle Zusammenfassung. Ich habe einen Satz von diesem Getränk
Aber: Wenn ich viele Blöcke habe, und zu einem Satz zusammenfasse. Ich habe nur einen Satz, kann das Datum in jedem Block stehen
Ein vollassoziativer Cache ist ein Cache, der aus einem Satz besteht. Damals hatten wir nicht genug. Jetzt kaufen wir noch einen Satz dazu. Jetzt haben wir 2 Sätze ...
Anzahl der Sätze Assoziativität
Vollassoziativ 1 m(=n)
Direkt Abgebildet m 1
n-wege-Satzassoziativ m/n n
Assoziativität steht für das Assoziieren. Ich assoziere steht es da oder da. Kann es nur an einer Stelle stehen, kann ich nicht assoziieren. Es muss da stehen. Dann ist Assoziativität = 1
Cache-Flattern
Cache-Thrashing: Hierbei wird immer im schnellen Wechsel immer wieder auf die Addressen mit gleichem Index-Anteil zugegriffen
Führt zu ständigen Verdrängen
Ein Datum wird an einer bestimmten Speicheraddresse angefragt
Cache-Treffer (Cache-Hit)
Cache-Fehlzugriff (Cache Miss)
Treffer Rate (Hit Rate)
Fehlzugriffsrate (Miss Rate)
T = 0,9 ^= 90%
M = 1-T
Konflikt: Weitere Zeile soll nachgeladen werden, dieser ist aber bereits belegt
Vollassoziativer Cache
Einteilung der Addresse in zwei Felder
1.) Das Tag
2.) Teil für die Byteauswahl
1.) Das Tag: 27 Bits
2.) Teil für die Byteauswahl: 5 Bit
Das Tag wird verwendet, um im Cache-Speicher zu prüfen, ob die entsprechende Cache-Zeile mit dem identischen Tag bereits in den Cache-Speicher geladen wurde
Byte Auswahl: 2^5 = 32 Bytes, 8 32 Bit Wörter
1.) Tag-RAM
2.) Tag-Lines
Tag-RAM: Tag Random Access Memory
Bei einem vollassoziativen Cache-Speicher muss das Tag, der in der Addresse übergeben wird, gleichzeitig mit allen Tags im Tag-RAM verglichen werden
Bei einem Zugriff auf den Cache-Speicher werden zunächst sämtliche gespeicherten Tags aus dem Tag-RAM mit dem Tag der angefragten Addresse verglichen
Entsprechend aufwändig ist auch die vorgeschaltete Logik
Direkt abgebildeter Cache-Speicher
1.) Tag
2.) Index
3.) Byte
Byte-Auswahl: 5 Bit
Tag: Auf 16 Bit verkürzt
Index: 11 Bit, 2^11 = 2048 Cache-Einträge
1.) Es wird mit dem Index-Teil der Satz ausgewählt der die Cache-Zeile enthält
2.) Zeiigleich wird die Gültigkeit geprüft
3.) Stimmt das Tag überein und ist der Eintrag gültig
4.) Byte Auswahl
n-Wege Satzassoziativ
1.) FIFO
2.) LRU
3.) LFU
4.) RND
1.) FIFO -- First In First Out - der älteste Eintrag wird verdrängt
2.) LRU -- Least Recently Used: der am längsten nicht genutzte Eintrag wird verdrängt
3.) LFU -- Least Frequently Used: Der am seltenste Genutzte Eintrag wird verdrängt
4.) RND: Zufälliger Eintrag wird verdrängt
1.) Ältester
2.) Am Längsten nicht genutzt
3.) Seltenste genutzte
4.) Zufälliger
LRU
Pseudo-LRU
Bisher: Lesend
1.) Lesend
2.) Schreibend
Cache-Fehlzugriff
1.) Mit Bereitstellung: With Allocation
2.) Ohne Bereitstellung: Without Allocation
1.) With Allocation
2.) Without Allocation
1.) Der zu schreibende nicht im Cache vorhandene Eintrag wird aus dem Speicher in den Cache geladen, um ihn zu verändern
2.) Nicht in den Cache laden, sondern Datum wird im Hauptsspeicher verändert
1.) Bei Cache-Fehlzugriff
2.) Bei Cache-Treffer
Cache-Treffer
1.) Durchschreibeverfahren - Write Trough
2.) Umschreibeverfahren
3.) Rückschreibeverfahren
1.) Bei Cache Fehlzugriff
1.1.) Mit Bereitstellung
1.2.) Ohne Bereitstellung
2.) Bei Cache Treffer
2.1.) Durchschreibeverfahren
2.2.) Umschreibeverfahren
2.3.) Rückschreibeverfahren
Durchschreibeverfahren: Sowohl im RAM wie auch im Cache
Vorteil: Erhaltung der Speicherkonsistenz
Vorteil: Erhaltung der Speicherkonsistenz über mehrere Stufen hinweg
Nachteil: Langsame Zugriffszeiten auf den Hauptspeicher, Belastung des Hauptsspeichers mit vielen Zugriffen
Entschärfung: Verwendung eines Schreibpuffers
Vorteil/Nachteil=Problematik
Problematik/Lösung=Entschärfung
Durchschreibeverfahren: Sowohl im RAM wie auch im Cache
Umschreibeverfahren: Cache Speicher wird nicht aktualisiert, sondern in den Hauptsspeicher geschrieben
Rückschreibeverfahren: Der Cache aber nicht die da runter liegenden
1.) Cache: Ja und RAM: Ja
2.) Cache: Nein und RAM: Ja
3.) Cache: Ja und RAM: Nein
1.) Durchschreibeverfahren
2.) Umschreibeverfahren
3.) Rückschreibeverfahren
Probleme
Andere Probleme:
1.) Verschiedene Cores
2.) Multicores
3.) DMA - DirecT Memory Access
1.) Konsistenz
2.) Kohärenz
1.) Konsistenz: Alle Daten im Hauptspeicher und den verschiedenen Cache-Speichern sind immer identisch
2.) Kohärenz: Ein Lesezugriff liefert immer den Wert des zeitlich letzten Schreibzugriffs auf das entsprechende Speicherwort
Allgemeiner ausgedrückt bezeichnet Kohärenz das korrekte Voranschreiten des Systemzustands durch ein abgestimmtes Zusammenwirken der Einzelzustände
Write-Update-Protokoll: Wird eine Kopie im Cache-Speicher verändert müssen alle Kopien aktualisiert werden
Write-Invalid-Protokoll: Alle Kopien in anderen Cache-Speichern werden als ungültig markiert
Multiprozessor: MESI
MESI-Prozessor:
Modified,
Exclusive,
Shared,
Invalid
Bus-Schnüffeln: Bus Snooping: Prozessoren können erkennen, welcher andere Prozessor auf den Hauptspeicher zugreift
1.) Schreibzugriff: Cache Line ungültig erklärt: V-Bit
2.) Lesezugriff oder Schreibzugriff:
MESI - Cache Zeile hat eine von vier Möglichkeite
1.) Exclusive Modified
2.) Exclusive Unmodified
3.) Shared unmodified
4.) Invalid
1.) Exclusive Modified: M
2.) Exclusive Unmodified: E
3.) Shared unmodified: S
4.) Invalid: I
Zustand I:
Zutsand S:
Zustand M:
Zustand E:
Wie Zustände
z0, z1, z2, z3
Übergänge:
SHW
RMS
SHR
RH
WM
RME
WH
Übergänge:
I RMS S
S SHW I
S SHR S
S RH S
I WM M
M SHW I
I RME E
E SHW I
E SHR S
E RH E
M WH M
M RH M
RH: Read Hit
RMS: Read Miss, shared
RME: Read Miss, exclusive
WH: Write Hit
WM: Write Miss
SHR: Snoop Hit on Read
SHW: Snoop Hit on Write oder lesen einer Cache-Line zum Ändern
Pfeil nach Unten: Veränderte Cache-Line zurückschreiben
x Kreuz: Andere Cache-Lines ungültig markieren
+ Plus: Lesen einer Cache-Line zum Ändern
^| Pfeil nach oben: Cache-Line laden
(I): Cache Zeile ist ungültig
1.) Cache-Zeile ist noch nicht in den Speicher geladen
2.) Cache-Zeile ist zwischenzeitlich ersetzt
3.) Cache-Zeile wurde als ungültig markiert
(S): Cache-Zeile ist unverändert enthalten
(E): Cache-Zeile liegt nur im aktuellen Cache des Prozessors
(M): Liegt nur im Cache des aktuellen Prozessors ist aber verändert
