TGI 7 Cache and Co Flashcards
Virtueller Speicher ist unabhängig vom
physikalisch vorhandenen Arbeitsspeicher
Paging ist …. für Programmierer
Paging ist transparent für Programmierer (muss keine
Rücksicht nehmen, ob Adressen im real vorhandenen
physikalischen Arbeitsspeicher wirklich existieren)
Virtuelle Adresse Vs Physische Adressen
Virtuelle Adressen bieten Flexibilität und Schutz, während physische Adressen den direkten Zugriff auf den physischen Speicher ermöglichen.
Where Logical Address Space are implemented?
On Hard Disk, in RAM
Paging ist
Paging hilft dem Computerprogramm, mit mehr Daten zu arbeiten, indem es den Speicher clever organisiert.
Vorteile und Nachteile von Paging
Vorteile:
Ermöglicht die Ausführung von Programmen, die größer sind als der physische Speicher.
Speicherschutz: Verhindert den Zugriff von Prozessen auf fremden Speicher.
Vereinfachte Speicherverwaltung: einfache Speicherverwaltung durch Einteilung in Blöcke.
Flexible Speicherzuweisung: Dynamische Zuweisung und Freigabe von Speicherplatz.
Nachteile:
Overhead: Zusätzlicher Verarbeitungsaufwand für die Adressübersetzung.
Externe Fragmentierung: Ungenutzter Speicherplatz innerhalb einer Seite.
Demanding paging
werden nur die virtuellen Seiten, die Ihr Programm gerade verwendet laden, in den physischen Speicher (RAM).
Dirty bit
Das Dirty Bit zeigt an, welche virtuellen Seiten im Speicher (RAM) geändert wurden, seit sie das letzte Mal von der Festplatte geladen wurden.
Page fault
Page wird gebraucht, wurde aber ausgelagert
Was passiert wenn physikalischer Speicher voll ist?
Wenn physikalischer Speicher voll ist, muss vor dem
Einlagern einer angeforderten Page (Page-In) eine andere
Page ausgelagert (Page-out) werden.
Trashing ist
System ist (fast) nur mit Einlagerung und Auslagerung beschäftigt und kann kaum (gar nicht) Programm abarbeiten
Welche Pages werden ausgelagert?
Diejenige, die möglichst lange nicht mehr gebraucht wird
Was ist CPU-Designziel?
in jedem Takt Befehl abarbeiten
Speicher-Latenzzeit ist
Wartezeit, bis Speicherzugriff anläuft
Caches sind
kleine, schnelle Zwischenspeicher
Räumliche Lokalität
Häufig Zugriffe auf Adressen, die in der Nähe kürzlich benutzter Adressen liegen
Zeitliche Lokalität
Folgezugriffe auf kürzliche benutzte
Adressen
Welche Daten kann lange im Cache halten?
Kürzlich benutzte Daten möglichst lange im Cache
halten
Was ist Cache-Hit?
findet was er sucht
Cache-Miss
findet nicht
Hit-Rate
Wahrscheinlichkeit für Cache Hit
Lesezugriff auf Hauptspeicher:
Cache auf Kopie prüfen
Was ist Datum?
eine kleine Datenmenge im Cache
Look-Through-Cache.
Zwischen.. und …?
Cache und Hauptspeicher?
Bei guter Hit-Rate?
Bei schlechter Hit-Rate?
Zwischen CPU und Hauptspeicher
Schnell an CPU angebunden (höherer Bustakt als
Hauptspeicher)
Cache und Hauptspeicher nicht gleichzeitig aktivierbar
(Hauptspeicherzugriff erfolgt erst, wenn Daten im Cache
nicht gefunden wurden)
Bei guter Hit-Rate fast nur Zugriffszeit des Caches
entscheidend
Bei schlechter Hit-Rate hohe Wartezeiten
Look-Aside-Cache.
Bei Fehltreffer im Cache?
Cache-Zugriff und Hauptspeicher-Zugriff?
Parallel zum Hauptspeicher
Cache-Zugriff und Hauptspeicher-Zugriff werden
gleichzeitig aktiviert
Kein Zeitverlust bei Fehltreffer im Cache
Aber: Cache wird durch langsamen Speicherbus getaktet
First-Level Cache
Kleinste und schnellste Cache-Ebene direkt im oder neben dem Prozessor.
Zugriff am schnellsten, aber auch am wenigsten Speicherplatz.
Speichert häufig verwendete Daten und Befehle für die CPU.
gleichzeitiger Zugriff möglich
L2-Cache
Größer und etwas langsamer als der L1-Cache.
Speichert Daten, die nicht ganz so häufig benötigt werden wie im L1-Cache.
Meist in Prozessorchip integriert
L3-Cache
Größte und langsamste Cache-Ebene auf dem Prozessor oder einem separaten Chip.
Speichert Daten, die seltener benötigt werden, aber immer noch schneller aus dem L3-Cache abgerufen werden können als aus dem Hauptspeicher.
Memory Stall Cycles
Anzahl der Zyklen, die CPU auf Speicherzugriff warten muss
MSC= Anzahl der Misses * MP
Wovon hängt Memory Stall Cycles?
von der Anzahl der Cache Misses und Kosten (Wartezeit) pro Cache Miss (Miss Penalty)
Hit Time
Zeit um Treffer im Cache zu erziehen
Miss Rate
Wahrscheinlichkeit für Cache Miss
Je mehr Level , desto…
größer kosten
Misses pro Instruction, MPI
so viele Zyklen warten bis Cache finden
Miss Penalty, MP
Extra-Aufwand bei Cache Miss (zb, L2, RAM)
AMSPI
Average Memory Stalls per Instruction.
Durchschnittliche Anzahl an Zyklen pro Instruktion, in
denen auf Daten aus dem Speicher gewartet wird
Annahme: L1-Cache wird mit vollem Prozessortakt
betrieben =>erfolgreicher L1-Cache Zugriff braucht also
keinen Extra-Takt (Zyklus)
Welche Cache - Optimierung gibt es?
1)Miss Penalty (MP) senken
Mehrstufige Caches
2) Miss Rate (MR) senken
Blockgröße erhöhen, nutzt räumliche Lokalität, erhöht MP
3) Hit Time (HT) senken
Kleiner, einfacher, schneller Cache; On-chip, CPU-Takt,
direct mapped
Bestandteile eines Caches:
Datenbereich, Identifikationsbereich, Verwaltungsbereich
Datenbereich besteht…., was alle Linien haben, immer ganze Cache Line…
Besteht aus Anzahl von Cache-Zeilen (Cache Lines)
Alle Lines haben einheitliche Blocklänge (block/line size)
Immer ganze Cache Line laden/ersetzen
Indentifikationsbereich enthält…., stellt fest, ob
Enthält tags (Etikett): Aus welchem Abschnitt des
Hauptspeichers wurde Cache-Zeile geladen
Stellt fest, ob ein Datum im Cache ist oder nicht
Verwaltungsbereich: wie viele Bits, Valid Bit, Dirty Bit
Mindestens zwei Bits
Valid bit: Ist Cache-Line ungültig (veraltet, 0) oder gültig (1)
Dirty bit: Wurde auf Cache-Line geschrieben (1) oder nicht
(0) – für Copy-Back-Ersetzungsstrategie wichtig
Welche Organisationsformen es gibt?
Vollassoziativ, direkt abbildend, mehrfach assoziativer Cache(n-way set associative, teilassoziativ), am häufigsten zu finden
Vollassoziativ
Wo und was abspeicherbar?
Hardwareafuwand?
Einschränkungen?
Trefferquote?
Datenblock in beliebiger Cache-Zeile abspeicherbar
=> alle Tags mit angefragter Adresse zu vergleichen
Muss aus Performance-Gründen gleichzeitig erfolgen
=>Vergleichereinheit für jede Cache-Zeile
=>sehr hoher Hardwareaufwand
Dafür keine Einschränkungen bei Ersetzung!
=>höchste Trefferquote aller Organisationen
Direct mapped
Wo und was zuzuordnet?
Ersatzungsstrategie?
Trashing?
Aufabu?
Trefferquote?
Teil der Speicheradresse wird als Index benutzt, um
dem Datenblock eine Cache-Zeile zuzuordnen.
=>Block kann nur dort gespeichert werden
=>es gibt keine Ersetzungsstrategie
Kann zu Thrashing führen = schlechter als gar kein Cache
Aus Index sofort klar, wo Block stehen muss (falls im
Cache)
Einfacher Aufbau, nur ein Vergleicher notwendig
=>schlechteste Trefferquote aller Organisationen
n-way set associative
was wird zum was zusammengefasst?
Was wird als Index benutzt?
Trefferbestimmung?
Kompromiss zw. fully associativ und direct mapped
Cache-Zeilen werden zu einem Satz zusammengefasst
Satznummer wird als Index benutzt:
=> aus Adresse ergibt sich nur Nummer des Satzes
=> innerhalb des Satzes kann frei gewählt werden
=> Ersetzungsstrategien möglich
Trefferbestimmung:
=> Index verweist auf Satz, wo Datum stehen könnte
=> innerhalb von Satz kann Datum in n Einträgen liegen
=> n Vergleicher: parallel Tags der n Einträge vergleichen
Aktualisierungsstrategien: wichtige Begriffe
Konsistenz: Alle Kopien eines Datums inhaltsgleich
Kohärenz: Korrektes Fortschreiten des Systemzustands
Inkohärenz, wenn Dateninkonsistenz nicht bereinigt wird
Lesen vs. Schreiben
Aktualisierungsstrategien: Lesen
Lese-Treffer: Daten zeitsparend aus Cache nehmen; keine
weiteren Aktionen
Lese-Fehltreffer: Block, der Datum enthält, in Cache laden;
angefordertes Datum in CPU laden
Aktualisierungsstrategien: Schreiben. Schreib-Treffer
1) Write-Through-Strategie: Datum wird in Cache und in
Hauptspeicher geschrieben: Einfach, garantiert Konsistenz
2) Copy-Back (Write-Later)-Strategie: Datum wird nur im
Cache aktualisiert und betroffene Cache-Zeile als
verändert markiert (Dirty Bit wird auf 1 gesetzt).
Spätestens vor Ersetzung muss Datum in Hauptspeicher
zurückgeschrieben werden (write back, copy back)
Vorteilhaft z.B. bei viel benutzter Variable (z.B.
Schleifencounter)
System jedoch teilweise inkonsistent
Aktualisierungsstrategien: Schreiben. Schreib-Fehltreffer
1)No-Write-Allocate-Strategie: Datum nur in Hauptspeicher
schreiben, liegt danach nicht im Cache vor
2)Write-Allocate-Strategie: Datum in Hauptspeicher
schreiben und zusätzlich den entsprechenden Block in
Cache laden
Sekundärspeicher
Speichermedien mit persistenter (dauerhafter)
Speicherung
Festplatten: Schreiben
Bewegte Ladungen (=Strom) erzeugen ein Magnetfeld
Definierter Bereich der Oberfläche wird magnetisiert
Richtung des Stroms bestimmt Richtung der
Magnetisierung (logisch 0/1)
Festplatten: Lesen
Veränderliches Magnetfeld induziert Strom in einem
Leiter
Was soll Aktuator auf jewellige ….
Aktuator (Lese/Schreibkopf) muss auf jeweilige Spur
bewegt werden
Fragmentierung
Fragmentierung ist die Streuung von logisch zusammengehörigen Datenblöcken eines Dateisystems auf einem Datenträger.
Defragmentierung:
was kann beschleunigen?
Neuordnung von fragmentierten Datenblöcken
Logisch zusammengehörende Datenblöcken sollten
aufeinander folgen
Kann den sequentiellen Zugriff beschleunigen
Welche Disk Scheduling gibt es? Auf was dividieren wir?
FIFO/FCFS, SSTF, SCAN, C-SCAn, LOOK, C-LOOK. Auf immer gleiche Anzahl (Spuren)
FIFO/FCFS
First In First Out (по порядку).
Vorteile: Faire Abarbeitung
Nachteile: Gesamtanzahl an überquerten Spuren sehr hoch
SSTF
Shortest Seek Time First (усі, які менше- від початкового до найбільшого)
Vorteil: jeweilige Seek Time wird verringert
Nachteil: durchscnittliche Seek Time nicht garantiert minimal
SCAN
від початкового до найбільшого + найбільше- від початкового до найменшого
C-SCAN
reduziert Verzögerung für neu eintreffende Anfragen
від початкового до найбільшого + найбільше + найменше і від найменшого до найбліьшого (але яке менше початкового)
LOOK
intelligenter als SCAN
від початковго до найбільшого - від початковго до найменшого
C-LOOK
від початкового до найбільшого - від найменшого до найбільшого (яке менше за початкове)
