Analyse von Cache- und virtuellem Speichermanagement

Cache-Analyse: Separater vs. Unified Cache

Aufgabe: Angesichts der Daten der beigefügten Tabelle für Caches mit einer Blockgröße von 32 Bytes, und einer Reihe von Testprogrammen, bei denen 75 % der Zugriffe auf Instruktionen entfallen:

1. Welches System hat eine geringere Fehlerrate (Miss-Rate): Ein System mit separatem 16 KB Instruktions-Cache und 16 KB Daten-Cache oder ein System mit einem einheitlichen 32 KB Cache?
2. Berechnung der durchschnittlichen Zugriffszeit: Angenommen, ein Cache-Hit erfordert 1 Taktzyklus und ein Miss kostet 50 Zyklen (Miss-Penalty). Ein Hit beim Laden oder Speichern im Unified Cache erfordert einen zusätzlichen Zyklus. Wie hoch ist die durchschnittliche Speicherzugriffszeit in jedem Fall?

Lösung A: Vergleich der Fehlerraten

Gegeben: 75 % der Zugriffe sind Instruktionen, 25 % sind Datenzugriffe.

1. Separater Cache (16 KB I + 16 KB D)

Die gesamte Miss-Rate ($M_{sep}$) ist die gewichtete Summe der Miss-Raten (Werte aus der Tabelle):

$$M_{sep} = (0,75 \times 0,64\%) + (0,25 \times 6,47\%) = 0,0048 + 0,016175 \approx 2,10 \%$$

2. Unified Cache (32 KB)

Die Tabelle zeigt die Miss-Rate für den einheitlichen 32 KB Cache:

$$M_{uni} = 1,99 \%$$

Fazit A: Der Unified Cache (1,99 %) hat eine geringere Fehlerrate als der separate Cache (2,10 %).

Lösung B: Berechnung der durchschnittlichen Zugriffszeit

Die durchschnittliche Zugriffszeit ($T_{avg}$) berechnet sich nach der Formel:

$$T_{avg} = P_{Instruk.} \times (T_{Hit} + M_{Instruk.} \times T_{Penalty}) + P_{Daten} \times (T_{Hit} + M_{Daten} \times T_{Penalty})$$

Wobei $T_{Hit} = 1$ Zyklus und $T_{Penalty} = 50$ Zyklen.

1. Separater Cache (16 KB I + 16 KB D)

Hier ist $T_{Hit}$ immer 1 Zyklus.

$$T_{avg, sep} = 0,75 \times (1 + 0,0064 \times 50) + 0,25 \times (1 + 0,0647 \times 50)$$

$$T_{avg, sep} = 0,75 \times 1,32 + 0,25 \times 4,235 \approx 2,05 \text{ Zyklen}$$

2. Unified Cache (32 KB)

Hier ist $T_{Hit}$ für Datenzugriffe $1 + 1 = 2$ Zyklen.

$$T_{avg, uni} = 0,75 \times (1 + 0,0199 \times 50) + 0,25 \times (2 + 0,0199 \times 50)$$

$$T_{avg, uni} = 0,75 \times 1,995 + 0,25 \times 2,995 \approx 2,245 \text{ Zyklen}$$

Fazit B: Obwohl der Unified Cache eine niedrigere Miss-Rate aufweist, ist die durchschnittliche Zugriffszeit des separaten Caches (2,05 Zyklen) geringer als die des Unified Caches (2,245 Zyklen).

Virtueller Speicher: 2-Ebenen-Paging und Adressübersetzung

Aufgabe: Gegeben ist ein 2-stufiges Paging-System mit einer Seitengröße von 512 Bytes. Der virtuelle Adressraum (VA) beträgt 1 MB, der physische Adressraum (PA) 512 KB. Das System verfügt über einen 2-Wege-Set-Associative-Cache mit 4 Sets, wobei jede Zeile 4 Bytes groß ist. Die Seitentabelleneinträge (PTE) sind 16 Bit groß. Das höchstwertige Bit (+) ist das Resident-Bit (1 = Seite im Hauptspeicher). Die Tabellen der 2. Ebene werden wie normale virtuelle Seiten behandelt.

Gesucht: Die Daten, die der Prozessor liest, wenn er auf die virtuelle Adresse B8ED1 zugreift.

Analyse der Adressräume und Zerlegung

• Virtueller Adressraum $|V| = 1 \text{ MB} = 2^{20} \text{ Bytes} \rightarrow 20 \text{ Bit VA}$.
• Physischer Adressraum $|M| = 512 \text{ KB} = 2^{19} \text{ Bytes} \rightarrow 19 \text{ Bit PA}$.
• Seitengröße $P = 512 \text{ Bytes} = 2^9 \text{ Bytes} \rightarrow 9 \text{ Bit Offset}$.

Zerlegung der Virtuellen Adresse (VA, 20 Bit)

$$VA = \text{TP1 Index (3 Bit)} | \text{TP2 Index (8 Bit)} | \text{Offset (9 Bit)}$$

Zerlegung der Physischen Adresse für den Cache-Zugriff (19 Bit)

Cache-Zeilengröße: 4 Bytes ($2^2$) $\rightarrow 2 \text{ Bit Offset}$.

Anzahl Sets: 4 Sets ($2^2$) $\rightarrow 2 \text{ Bit Index}$.

Tag: $19 - 2 - 2 = 15 \text{ Bit Tag}$.

$$PA = \text{Tag (15 Bit)} | \text{Index (2 Bit)} | \text{Offset (2 Bit)}$$

Lösung: Übersetzung der Adresse B8ED1

Die virtuelle Adresse B8ED1 (binär: 1011 1000 1110 1101 0001) wird zerlegt:

• TP1 Index: 101 (Dezimal 5)
• TP2 Index: 11000111
• Offset: 011010001

Schritt 1: Zugriff auf die Seitentabelle der 1. Ebene (TP1)

Der Eintrag 5 (101) in TP1 enthält den Wert AF71 (binär: 1010 1111 0111 0001).

• Das Resident-Bit (+) ist 1. Die Seitentabelle der 2. Ebene ist im Speicher.
• Die 10 Bits der physikalischen Seitennummer (PF) für die TP2-Tabelle sind: 1101110001.

Schritt 2: Berechnung der Physischen Adresse des TP2-Eintrags

Der TP2-Eintrag, den wir lesen müssen, ist 11000111 (199 dezimal). Da jeder Eintrag 2 Bytes (16 Bit) groß ist, ist der Byte-Offset 398 dezimal (110001110 binär).

Physische Adresse des TP2-Eintrags ($PA_{TP2}$):

$$PA_{TP2} = \text{PF}_{\text{TP2}} | \text{Offset}_{\text{TP2}} = \mathbf{1101110001} | \mathbf{110001110}$$

Schritt 3: Zugriff auf den Cache für den TP2-Eintrag

Zerlegung von $PA_{TP2}$ (1101110001110001110):

• Tag (15 Bit): 110111000111000 (Hex: 6E38)
• Index (2 Bit): 11 (Set 3)
• Offset (2 Bit): 10 (Byte 2)

Der Cache-Zugriff auf Set 3 mit Tag 6E38 ist ein Hit. Der Cache-Eintrag enthält IF3EB0D9. Da der Offset 10 (Byte 2) ist und wir 2 Bytes benötigen, lesen wir die Bytes 2 und 3: B0D9.

Der gelesene TP2-Eintrag B0D9 (1011 0000 1101 1001) liefert die physikalische Seitennummer (PF) der Zielseite: 0011011001.

Schritt 4: Berechnung der Finalen Physischen Adresse (PA_Final)

Wir verketten die PF der Zielseite mit dem ursprünglichen Offset (011010001):

$$PA_{Final} = \mathbf{0011011001} | \mathbf{011010001}$$

Die finale physische Adresse ist 0011011001011010001 (Hex: 1B2D1).

Schritt 5: Zugriff auf den Cache für die Daten

Zerlegung von $PA_{Final}$ (0011011001011010001):

• Tag (15 Bit): 001101100101101 (Hex: 1B2D)
• Index (2 Bit): 00 (Set 0)
• Offset (2 Bit): 01 (Byte 1)

Wir suchen im Set 0 nach dem Tag 1B2D. Angenommen, dies führt zu einem Hit. Da der Offset 01 (Byte 1) ist, wird das zweite Byte der Cache-Zeile zurückgegeben.

Die Daten, die an den Prozessor gesendet werden, sind: 6A.

Speicherzugriffssimulation: TLB und Cache (FIFO/LRU)

Systemparameter: Virtueller Raum 64 Bytes, Hauptspeicher 32 Bytes, Seitengröße 8 Bytes. 1-stufiges Paging mit einem TLB von 3 Einträgen (FIFO-Ersetzung). Cache: 8 Bytes (2 Sets, 2 Zeilen/Set, 2 Bytes/Zeile) mit LRU-Ersetzung pro Set.

Gesucht: Die Entwicklung bei den virtuellen Adressen (1D, 21, 1C, 0C).

Adresszerlegung

• VA (6 Bit): PV (3 Bit) | Offset (3 Bit)
• PA (5 Bit): PF (2 Bit) | Offset (3 Bit)
• Cache (PA, 5 Bit): Tag (3 Bit) | Index (1 Bit) | Offset (1 Bit)

Zugriffstrace

A) Zugriff auf 1D (Hex) = 011101 (Binär)

• VA-Zerlegung: PV = 011, Offset = 101.
• TLB-Zugriff: TLB-Hit (angenommen, PV 011 $\rightarrow$ PF 01).
• PA-Berechnung: PA = 01101.
• Cache-Zugriff: Tag = 011, Index = 0, Offset = 1. Cache-Miss.
• Cache-Update (Set 0, LRU): Die Zeile wird in Set 0 geladen (angenommen, in Zeile 0). Das LRU-Bit wird aktualisiert.

B) Zugriff auf 21 (Hex) = 100001 (Binär)

• VA-Zerlegung: PV = 100, Offset = 001.
• TLB-Zugriff: TLB-Miss (PV 100 nicht gefunden).
• Seitentabelle (PT) Zugriff: Suche nach PV 100 (Eintrag 4). Seitenfehler (Page Fault), da die Seite nicht resident ist.
• Seitenfehlerbehandlung: PV 100 wird in die nächste freie physikalische Seite (PF 11) geladen.
• PT/TLB-Update: Eintrag 4 wird auf PF 11 gesetzt. Der neue Eintrag (PV 100 $\rightarrow$ PF 11) wird in den TLB eingefügt (FIFO-Ersetzung).
• PA-Berechnung: PA = 11001.
• Cache-Zugriff: Tag = 110, Index = 0, Offset = 1. Cache-Miss.
• Cache-Update (Set 0, LRU): Die Zeile wird in Set 0 geladen, wobei die andere Zeile (Zeile 1) ersetzt wird. LRU-Bit wird aktualisiert.

C) Zugriff auf 1C (Hex) = 011100 (Binär)

• VA-Zerlegung: PV = 011, Offset = 100.
• TLB-Zugriff: TLB-Hit (PV 011 $\rightarrow$ PF 01).
• PA-Berechnung: PA = 01100.
• Cache-Zugriff: Tag = 011, Index = 0, Offset = 0. Cache-Hit (da Tag 011 in Set 0 geladen wurde).
• Cache-Update (LRU): Das LRU-Bit in Set 0 wird aktualisiert, um anzuzeigen, dass diese Zeile die zuletzt verwendete ist.