Übung 10

Institut für
Technische Informatik und
Kommunikationsnetze
Prof. L. Thiele
Technische Informatik 1 - HS 2015
Übung 10
Datum:
17. – 18. 12. 2015
Virtueller Speicher
1
Performanz
Gehen Sie von einem virtuellen Speichersystem mit TLB aber ohne Cache aus. Falls ein Datenzugriff
zu einem TLB-Miss führt, wird die entsprechende Instruktion unterbrochen (eine TLB-Miss-Ausnahme
wird ausgelöst) und der TLB-Miss behoben. Dann erfolgt eine Wiederholung der Instruktion. Falls eine
Instruktion zu einem Seitenfehler führt, wird sie unterbrochen (eine Page-Fault-Ausnahme wird ausgelöst)
und die Bearbeitung des Seitenfehlers wird durchgeführt, die auch den entsprechenden Eintrag im TLB
anpasst. Anschliessend wird die Instruktion wiederholt.
Es sind folgende Variablen und Daten gegeben:
• Zugriffs- und Suchzeit im TLB: s = 5ns
• TLB-Missrate: m = 0.02
• Mittlere Zugriffszeit zum Hauptspeicher: h = 10ns
• Mittlere TLB-Miss-Bearbeitungszeit: o = 100ns
• Seitenfehlerrate: p = 10−6
• Mittlere Seitenfehler-Bearbeitungszeit: f = 1ms
(a) Bestimmen Sie zunächst allgemein die effektive Speicherzugriffszeit. Setzen Sie dann die gegebenen
Parameterwerte ein.
(b) Gehen Sie jetzt davon aus, dass aufeinanderfolgende Zugriffe auf den virtuellen Speicher unabhängig
voneinander sind und zufällig auf eine der möglichen Adressen erfolgen. Die Seitengröße ist 212
Byte, der physikalische Adressraum beträgt 229 Byte und der virtuelle Adressraum beträgt 232
Byte. Der TLB enthält 212 Seiteneinträge.
Bestimmen Sie die TLB-Missrate, die Seitenfehlerrate und die effektive Speicherzugriffszeit in diesem Fall.
1
2
Seitenfehler
Betrachten Sie das folgende 2-dimensionale Array int X[32][32], wobei eine Integer-Variable 8 Byte
belegt. Gehen Sie weiterhin davon aus, dass das Array X so gespeichert ist, dass X[0][1] im virtuellen
Adressraum direkt auf X[0][0] folgt.
Die Ersetzungsstrategie für fehlende Seiten ist LRU. Der physikalische Speicher enthält 4 Seiten mit einer
Grösse von je 512 Byte. Zu Beginn enthält der physikalische Speicher keine gültigen Seiten.
Weiteris sind die folgende zwei Code-Fragmente gegeben:
/* Fragment 2: */
for (int i=0; i < 32; i++)
for (int j=0; j < 32; j++)
X[i][j]++;
/* Fragment 1: */
for (int j=0; j < 32; j++)
for (int i=0; i < 32; i++)
X[i][j]++;
Welches Code-Fragment liefert die wenigsten Seitenfehler? Bestimmen Sie die Zahl der Seitenfehler für
jedes Code-Fragment.
3
TLB, Seitentabelle und Cache
Ein Speichersystem hat die folgenden Eigenschaften:
• Es existiert nur ein Prozess.
• Der Speicher ist byteadressiert, jeder Zugriff liefert ein einzelnes Byte.
• Die virtuelle Adresse hat eine Länge von 32 Bit. Der physikalische Speicher ist 226 Byte gross. Eine
Seite enthält 212 Byte.
• Der Cache hat 210 Zeilen und ist 4-fach assoziativ (4-way set associative) mit einer Blockgrösse
von 8 Byte.
(a) Wie viele Bytes Nutzdaten kann der Cache speichern?
(b) Betrachten Sie, wie die 32 Bit Adressen die CPU mit Hilfe von Seitentabelle und Cache verarbeitet
werden. i Welche Bits der virtuellen Adresse werden benutzt um die Seitennummer zu bestimmen,
welche für den Seitenoffset? Welche Bits der physikalischen Adresse werden benutzt um die Seitennummer zu bestimmen, welche für den Seitenoffset? Wie werden die Bits der physikalischen
Adresse für die Cacheadressierung aufgeteilt?
(c) Wieviele virtuellen Seiten sind in der Seitentabelle enthalten? Wie viele Bits hat eine Seitentabelle
mindestens?
(d) Was ist die grösste Zahl von Tabelleneinträgen, die zu irgendeinem Zeitpunkt ihr Valid-Bit auf 1
gesetzt haben können?
(e) Wieviele Blöcke des virtuellen Adressraums konkurrieren um die Blöcke in einer Cache-Zeile?
(f) Betrachten Sie die virtuelle Adresse 0x510861. In wie vielen unterschiedlichen Orten im Cache
könnten die Daten gespeichert sein (geben Sie auch die entsprechende(n) Cachezeile(n) an)?
2
4
TLB, Seitentabelle und Cache
Wir betrachten ein Speichersystem mit einem TLB und einem L1 Datencache:
• Der Speicher wird byteweise adressiert, jeder Zugriff erfolgt also auf ein einziges Byte.
• Die virtuelle Adresse umfasst 14 Bit, die physikalische Adresse umfasst 12 Bit.
• Die Grösse einer Seite beträgt 64 Byte.
• Der TLB is 2-fach assoziativ (two-way set associative) mit insgesamt 4 Zeilen.
• Der L1 Datencache ist direkt abgebildet (direct mapped) mit 16 Zeilen und eine Blockgrösse von
4 Byte.
Zu einem bestimmte Zeitpunkt im Ablauf haben die Seitentabelle (nur die ersten 16 Einträge sind
gezeigt), der TLB und der Cache die folgenden Inhalte. PPN bedeutet die physikalische Seitennummer
(physical page number), VPN bedeutet die virtuelle Seitennummer (virtual page number) und alle Zahlen
sind in hexadezimaler Schreibweise angegeben. Leere Einträge bedeuten, dass der Inhalt nicht relevant
für die Aufgabenstellung ist.
TLB:
Index
0
1
2
3
Tag
05
02
01
01
Seitentabelle:
VPN PPN
00
01
02
02
03
03
04
05
06
22
07
22
PPN
20
22
22
Valid
1
1
1
1
Valid
0
1
1
1
Tag
12
04
07
02
PPN
42
32
VPN
08
09
0a
0b
0c
0d
0e
0f
Valid
1
1
0
0
PPN
Valid
20
1
04
1
3
Cache:
Index
0
1
2
3
4
5
6
7
8
9
a
b
c
d
e
f
Tag
00
31
24
22
21
22
18
22
20
22
20
3a
3f
24
23
22
Valid
1
Block[0]
de
Block[1]
ad
Block[2]
fa
Block[3]
ce
1
1
02
22
13
23
e1
e2
de
2e
1
9a
01
00
de
1
1
83
0d
1a
1f
09
f1
ce
d0
1
be
fb
57
02
1
cf
7a
9b
a0
Für jeweils gegebene virtuelle Adressen sollen Sie die folgenden Tabellen ergänzen. Beachten Sie, dass
sich nicht alle Einträge mit den vorliegenden Angaben ermitteln lassen.
(a) Als Vorbereitung bestimmen Sie zunächst, wie die virtuelle Adresse in die virtuelle Seitennummer
und den Seitenoffset aufgeteilt wird. Bestimmen Sie zudem, welche Bits den TLB-Index bilden und
welche den TLB-Tag. Für die physikalische Adresse bestimmen Sie die Aufteilung in die physikalische Seitennummer und den Seitenoffset. Bestimmen Sie zudem, welche Bits den Blockoffset, den
Cacheindex und den Cachetag bilden.
(b) Virtuelle Adresse: 0x0268 Virtuelle Adresse:
13
12
11
10
9
8
7
6
5
4
3
1
0
Übersetzung der virtuellen Adresse:
Parameter
Wert
VPN
TLB-Index
TLB-Tag
TLB-Hit (j/n)
Seitenfehler (j/n)
PPN
Physikalische Adresse:
11
10
9
8
Daten:
Parameter
Blockoffset
Cacheindex
Cachetag
Cachehit (j/n)
resultierendes Datenbyte
7
6
5
4
Wert
4
3
2
2
1
0
(c) Virtuelle Adresse: 0x0197 Virtuelle Adresse:
13
12
11
10
9
8
7
6
5
4
3
1
0
4
3
1
0
4
3
2
1
0
2
1
0
2
1
0
Übersetzung der virtuellen Adresse:
Parameter
Wert
VPN
TLB-Index
TLB-Tag
TLB-Hit (j/n)
Seitenfehler (j/n)
PPN
Physikalische Adresse:
11
10
9
8
7
Daten:
Parameter
Blockoffset
Cacheindex
Cachetag
Cachehit (j/n)
resultierendes Datenbyte
6
5
4
3
2
Wert
(d) Virtuelle Adresse: 0x035e Virtuelle Adresse:
13
12
11
10
9
8
7
6
5
Übersetzung der virtuellen Adresse:
Parameter
Wert
VPN
TLB-Index
TLB-Tag
TLB-Hit (j/n)
Seitenfehler (j/n)
PPN
Physikalische Adresse:
11
10
9
8
7
Daten:
Parameter
Blockoffset
Cacheindex
Cachetag
Cachehit (j/n)
resultierendes Datenbyte
6
5
4
3
2
Wert
(e) Virtuelle Adresse: 0x021a Virtuelle Adresse:
13
12
11
10
9
8
7
6
5
5
Übersetzung der virtuellen Adresse:
Parameter
Wert
VPN
TLB-Index
TLB-Tag
TLB-Hit (j/n)
Seitenfehler (j/n)
PPN
Physikalische Adresse:
11
10
9
8
Daten:
Parameter
Blockoffset
Cacheindex
Cachetag
Cachehit (j/n)
resultierendes Datenbyte
7
6
5
4
Wert
6
3
2
1
0

Download Report