TU Wien:Technische Grundlagen der Informatik VU (Kastner)/Kapitel Speichermanagement

• 01 Zahlendarstellung
• 02 Numerik
• 03 Codierung
• 04 Informationstheorie
• 05 Boolesche Algebra
• 06 KV-Diagramme und BDD
• 07 Moore- & Mealy-AutomatenTGI+GDS

  ---

• 08 Digitalschaltungen, KominatorikTGI
• 09 Sequentielle Logik
• 10 Speicher
• 14 Micro16
• 15 Befehlssatz
• 16 Pipelining
• 17 Speichermanagement
• 18 Chipsatz
• 19 Multi-Core
• 20 Netzwerke

Rechnerarchitekturen

Von-Neumann-Architektur

Speicher enthält Programme und Daten

Harvard-Architektur

getrennter Programm- und Datenspeicher

Einheiten

KiB	Kibibyte	$2^{10}$
MiB	Mebibyte	$2^{20}$
GiB	Gibibyte	$2^{30}$
TiB	Tebibyte	$2^{40}$
PiB	Pebibyte	$2^{50}$

Caches

Siehe auch de.Wikipedia:Cache und Folien der University of Washington.

Cache-Arten

Caches sind in Blöcke aufgeteilt.

	Direct-mapped	Set associative	Fully associative
Index	Blockposition	Setposition	—
Tag	restliche Adressbits		ganze Adresse
Ways	1	N	Blockanzahl

• Index wird durch Teil der Adresse bestimmt (z.B. niederwertige Bits).
• Suchzeit und Hit-Rate steigen mit Way-Anzahl.

Direct-Mapped Cache

Direct-Mapped kann man auch als einen 1-Way Associative Cache betrachten. Hier werden die Sets als Index bezeichnet. Der Index ist für die Auflistung der Zeilen zuständig.

Eigenschaften:

• jede Speicheradresse hat genau eine Position im Cache (1 Block / Zeile)
• einfache Cache Verwaltung
• kein Multiplexer im Datenpfad
• mäßige Hit-Rate

2-Way Associative Cache

Beim 2- und N-Way Associative Cache wird der Index als Sets bezeichnet.

Eigenschaften:

• 2 Blöcke / Zeile
• Verwaltung: Set beschränkt, Ersetzungsregeln, handbarer MUX
• vernünftige Hit-Rate

Fully Associative Cache

Eigenschaften:

• nur 1 Cache Zeile (1 Set) -> kein Index
• jeder Block darf auf jede Position gelegt werden
• komplizierte Verwaltung: Ersetzungsregeln, Suche im gesamten Cache, "großer" Multiplexer
• optimale Hit-Rate

Adresse

Adresslänge

Adresslänge = Tag - Index - Offset

Merkhilfe: Adresslänge = T(R)IO

Tag

Tag = Adresslänge - Index - Offset

Index

Index = log2(Cachegröße / Blockgröße)

Anzahl der Sets = log2(Cachegröße / Blockgröße * Ways)

Offset

Anzahl der Wörter = Blockgröße / Datenwortlänge

Offset = log2(Anzahl der Wörter)

Cachegröße (Nutzdaten)

Nutzdaten = Datenwort * 2^Index * 2^Offset * Ways

Locality

Temporal Locality

Bei einem kürzlichen Zugriff auf den Speicherinhalt, ist es sehr wahrscheinlich, dass der nächte Zugriff wieder auf diesen Speicherinhalt erfolgt.

Spatial Locality

Wird gerade auf den Speicherinhalt zugegriffen, ist es sehr wahrscheinlich, dass der nächste Zugriff in der Nachbarschaft von dem gerade zugegriffenen Speicherinhalt erfolgt.

Siehe auch Wikipedia:cache placement policies.

Schreibstrategie

• bei Hit
  • write-through
  • write-back
  • write-buffer
• bei Miss
  • write-around
  • fetch-on-write

Replacement-Strategien

• Least Recently Used (LRU)
• Least Frequently Used (LFU)
• random
• FIFO (first-in first-out)