/media/sda-magnetic/david/Dok-15-2023-11-27/fernuni-hagen/cs-i-ii/2023-12-31/csii3.txt

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