Fragen zum Cache

onbes
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 30. Jul 2011 18:43

Fragen zum Cache

Beitrag von onbes »

Moin moin,

das Thema ist mir noch etwas schwammig, deshalb habe ich FrageN zum Cache gewähl, sodass ich nach und nach weitere Unklarheiten hier in dem Thread fragen kann und keine neuen Threads erstellen muss.

1. Vorlesung 12 Folie 38:
In dem Bild wird jeder Cache Line 4 Adressen zugewiesen. Ist das Zufall,
dass jedem der Cashe lines in dem Bild genau bzw. maximal 4 Adresse
zugeordnet werden?

s53.In Formel auf Seite 51 wird von Blocknummer gesprochen, aber auf S. 53
Wird für die Blocknummer einfach die 12 eingesetzt. WIeso?

2. Übung 6 b)
die 3 Index Bit sind mir klar. Die 5 Bit für den Tag haben anscheinend die
Begründung, dass man (wohl) kein(e) Offset Bit(s) braucht, weil weil in jedem
Set nur eine Cache Line enthalten ist. Ist aber nicht Offset bit dazu da um
die entsprechende Daten"Zelle" in der Cache line anzusprechen?

Vielen Dank

Benutzeravatar
der Interpeter
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 30. Okt 2007 22:24

Re: Fragen zum Cache

Beitrag von der Interpeter »

zu Punkt1:
Bei Direct Mapped Cache legst du ja die Index Bits nach der Anzahl der Einträge des Cache fest, bei 8 Einträgen sind das dann 3 Index Bits (8 Einträge = 2^3 Einträge => 3 Index Bits).
Jede Adresse des Hauptspeichers endet mit den 3 Index Bits, also werden alle Hauptspeicheradressen die mit 101 enden im Cache Eintrag 5 abgelegt.

zu Punkt2:
Weil auf Seite 52 als Beispiel einfach mal Adresse 12 in die verschiedenen Cache-Organisationsformen eingefügt wird.

zu Ü6 Aufgabe 3b:
Ich bin davon ausgegangen dass ohne Informationen aus denen man die Blockgröße schließen kann der Block halt einfach mit 1Byte angenommen wird. Und da mit dem Block Offset ja nur die Bytes im Block angesprochen werden sollen und man für 1 Byte keine Offset-Bits braucht ( dieses Byte oder das selbe, das ist hier die Frage :D ) hab ichs weggelassen.
I never comment my sourcecode. What's HARD to write must be HARD to read!

ez22
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 28. Mär 2011 14:52

Re: Fragen zum Cache

Beitrag von ez22 »

Hallo,

ich habe eine Frage zum Cache Hit und Cache Miss.
Es heißt:
Bei den Zugriffen auf den Speicher prüft der Cache-Controller, ob sich das angeforderte Word im Cache befindet. Ist das Wort nicht im Cache vorhanden, wird ein betimmter Zeileneintrag aus dem Cache entfernt und die benötigte Zeile von einer darunter liegenden Ebene geholt.

Dann habe ich die Beschreibung der wie Cache-Hit funktioniert gelesen (da werden die TAG´s Felder verglichen, wenn keine Übereinstimmung kommt ist es ein Cache Miss)

Trotz mehreren Lesen dieses Kapitels habe ich Verständnisproblem bezüglich Cache Hit und Cache Miss.
Prüft der Cache-Controller jedes angeforderte Wort im Cache (ist der TAG´s Felder-Vergleich beim jeden Wort?)?
und ich verstehe dieses Prüfen/Suchen nicht ganz... es hört sich etwas unordentlich an. Muss das System nicht wissen wo die benötigten Daten liegen?

Ich hoffe die Fragen sind berechtigt :)

Großen Dank!

Toa
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 121
Registriert: 16. Feb 2011 23:58

Re: Fragen zum Cache

Beitrag von Toa »

3 Unterscheidungen musst du beachten:

1. Direct-Mapped Cache

Jedem Block im Hauptspeicher ist genau ein Set(Cacheline, Block) im Cache zugeteilt. D.h hier wird nur überprüft in welchem Set müsste mein Eintrag liegen, und ob er auch wirklich dort liegt (wegen genauer Zuordnung) außerdem muss auch hier der tag überprüft werden, denn es könnte ja ein Eintrag sein der an die gleiche Position geschrieben wird. Merke du hast soviele Sets wie Blöcke.

2. m - Satzassoziativer Cache

Jeder Satz im Cache hat m Cachelines (Blöcke ..) und jedem Block im Hauptspeicher kann genau ein Set im Cache zugeordnet werden. Dieser Block kann sich aber innerhalb des Sets in jeder Cacheline befinden. Daher braucht man zusätzlich einen Tag um den Block innerhalb des Sets zu identifizieren.

3. Vollassoziativer Cache

Was eigentlich ein Spezialfall von 2 ist. Hier hast du 1 Set in dem sich alle Cachelines befinden. Daher muss das komplette Set anhand des Tags abgesucht werden.

Ich hoffe dadurch konnte sich ein wenig mehr Verständnis aufbaun :) Grüße T0a

Markus1189
Erstie
Erstie
Beiträge: 22
Registriert: 12. Apr 2011 21:14

Re: Fragen zum Cache

Beitrag von Markus1189 »

Ich habe irgendwie Verständnisschwierigkeiten bei Übung 6 Aufabe 1 (Multiple Choice) Frage 5:
Gegeben sei ein vollassoziativer 32 Byte-Cache mit 4 Wort Blöcken und 32 Bit Wortgröße.
Auf die Daten im Hauptspeicher wird in folgenderSequenz zugegriffen:

1) 0x001
2) 0x004
3) 0x008
4) 0x004
5) 0x01E
6) 0x004
7) 0x0FF

Die Ersetzungsstrategie soll LRU sein. Welcher Block wird beim letzten Zugriff der Sequenz ersetzt?
32 Byte Größe -> C = 32 -> C = B * E * S -> E = 8
4 Wort Blöcke -> B = 4, b = 2
32 Bit Wortgröße -> m = 32

Dann hätten wir ja 30 tag bits und 2 block bits

Wenn man sich jetzt aber die Zugriffsaddressen anschaut, dann sind die tags eigentlich immer unterschiedlich und insgesamt sind es auch nicht mehr als 8 verschiedene.

Ich verstehe 1. nicht, warum die Blöcke, aus denen man die Antwort wählen soll immer 16bit haben und zweitens, warum die richtige Antwort Block 2 ist.

Benutzeravatar
der Interpeter
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 30. Okt 2007 22:24

Re: Fragen zum Cache

Beitrag von der Interpeter »

Einmal korrigiert :roll:

4 Blöcke á 32 Bit -> 4 * 32Bit -> 128 Bit je Block -> 16 Byte je Block -> 2^4 Byte je Block -> 4 Bit Block Offset
Da die Blöcke 16 Bit groß sind haben wir 2 Blöcke.
Die Adressen mit denen auf den Speicher zugegriffen wird haben 3 hex Zahlen, bestehen also binär aus 12 Bit.
12 Bit minus die 4 Bit Offset macht 8 Bit für den Tag.

Damit muss man nur noch die Adressen durchgehen

1) 0x001 -> 0000.0000 | 0001 -> miss, Einlagerung in Block 1
2) 0x004 -> 0000.0000 | 0100 -> hit in Block 1
3) 0x008 -> 0000.0000 | 1000 -> hit in Block 1
4) 0x004 -> 0000.0000 | 0100 -> hit in Block 1
5) 0x01E -> 0000.0001 | 1110 -> miss, Einlagerung in Block 2
6) 0x004 -> 0000.0000 | 0100 -> hit in Block 1
7) 0x0FF -> 0000.1111 | 1111 -> miss, Einlagerung in Block 2 der Zugriff auf Block 2 am längsten her ist (LRU)
Zuletzt geändert von der Interpeter am 18. Mär 2012 16:12, insgesamt 1-mal geändert.
I never comment my sourcecode. What's HARD to write must be HARD to read!

Markus1189
Erstie
Erstie
Beiträge: 22
Registriert: 12. Apr 2011 21:14

Re: Fragen zum Cache

Beitrag von Markus1189 »

So wie ich es im Moment verstehe, werden im Datenblock die Anzahl der Bytes per bits addressiert.

Foliensatz 12 Folie 37
B = Block Größe (Bytes)
b = log2(b)

Wir haben doch dann eigentlich B = 4 * 32bits = 4 * 4 Bytes = 16 Bytes
danach wäre dann also b = 4 und wir hätten 8 tag bits

32 Byte durch die 16 Bytes sind genau wie du gesagt hast dann 2 Cache Lines (Eintrag 1 & 2)

Ich würde es dann so sehen:

1) 0x001 -> 0000.0000 | 0001 -> miss, Einlagerung in Eintrag 1
2) 0x004 -> 0000.0000 | 0100 -> hit in Eintrag 1, Byte 4
3) 0x008 -> 0000.0000 | 1000 -> hit in Eintrag 1, Byte 8
4) 0x004 -> 0000.0000 | 0100 -> hit in Eintrag 1, Byte 4
5) 0x01E -> 0000.0001 | 1110 -> miss, Einlagerung in Eintrag 2
6) 0x004 -> 0000.0000 | 0100 -> hit, in Eintrag 1, Byte 4
7) 0x0FF -> 0000.1111 | 1111 -> miss, LRU ist Eintrag 2

wie man auf die Antwort kommt ist mir dann aber schleierhaft, vor allem wie
man dann auf die 0x10 - 0x01F als Bereich kommen soll

Benutzeravatar
der Interpeter
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 30. Okt 2007 22:24

Re: Fragen zum Cache

Beitrag von der Interpeter »

:shock: Ui, was hab ich denn oben verhackstückt. Korrigier ich gleich...
I never comment my sourcecode. What's HARD to write must be HARD to read!

Markus1189
Erstie
Erstie
Beiträge: 22
Registriert: 12. Apr 2011 21:14

Re: Fragen zum Cache

Beitrag von Markus1189 »

Leider klärt das noch nicht ganz mein Problem: warum ist die 3. Antwort die richtige?
Gegeben sei ein vollassoziativer 32 Byte-Cache mit 4 Wort Blöcken und 32 Bit Wortgröße.
Auf die Daten im Hauptspeicher wird in folgender Sequenz zugegriffen:
0x001, 0x004, 0x008, 0x004, 0x01E, 0x004, 0x0FF.
Die Ersetzungsstrategie soll LRU sein. Welcher Block wird beim letzten
Zugriff der Sequenz ersetzt?
  • Keiner
  • 0x000 - 0x00F
  • 0x010 - 0x01F
  • 0x0F0 - 0x0FF
  • 0x100 - 0x10F

Drno
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 236
Registriert: 10. Feb 2005 20:16

Re: Fragen zum Cache

Beitrag von Drno »

Es ist länger her, dass der Block zum Zugriff 5) benutzt wurde als der für 6) Daher lagerst du 5) aus wenn du 7) lesen willst. LRU halt.
Programming today is a race between software engineers striving to build bigger and better idiot proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning.

SirtobeD
Mausschubser
Mausschubser
Beiträge: 68
Registriert: 28. Okt 2010 18:56

Re: Fragen zum Cache

Beitrag von SirtobeD »

Seh ich das richtig das die Optionen "0x0F0 - 0x0FF" und "0x100 - 0x10F" nur zur Verwirrung dienen und wir nur 2 Cache-Lines haben und nicht 4?

Und zur Multiple-Choice-Frage Nr. 7: Da wäre die Antwort doch immer 128 Bytes (32 Blöcke mal 32 Bits), also egal ob Direct-Mapped, 4fach-assoziativer oder vollassoziativer Cache, richtig?

onbes
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 30. Jul 2011 18:43

Re: Fragen zum Cache

Beitrag von onbes »

hm ich verstehe die Multiple-Choice-Frage Nr. 7 nicht:

4-fach satzassoziativ bed. doch, dass ich pro Set 4 Cache lines habe. Dann nehme ich an, dass mit Wortgröße 32 die Größe des Datenblocks in einer Cacheline gemeint ist (falls ja, mit oder ohne Verwaltungsinfo?).

Wie muss ich denn nun die 32 Blöcke einordnen?????
Wie ist das Vorgehen bei dieser Aufgabe?

Ankou
Mausschubser
Mausschubser
Beiträge: 85
Registriert: 15. Mai 2011 18:23

Re: Fragen zum Cache

Beitrag von Ankou »

1 Block pro Cache Line. Der ganze Cache besteht aus 32 Blöcken und jeder Block hat 32 Bit = 4Byte, also 4*32=128 - assoziativität ist mE egal.

John_Silver
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 18. Okt 2009 23:27

Re: Fragen zum Cache

Beitrag von John_Silver »

Es ist sehr verwirrend, aber schau dir mal Vorlesung 12 Seite 35 an.
Dort ist es egal wieviele Sets und Cache Lines du hast. Da die Blockgröße die Datenmenge pro Cacheline angibt.
Ein Direct Mapped Cache hätte 32 Sets * 1 Cache Line / Set = 32 Cache Lines
Ein Vollassoziativer Cache hätte 1 Set * 32 Cache Lines / Set = 32 Cache Lines
Und der 4 Fach Assoziative Cache hat 8 Sets * 4 Cache Lines / Set = 32 Cache Lines

Antworten

Zurück zu „Archiv“