Praktikum 4: Ausgabe vergleichen

levitin
Kernelcompilierer
Kernelcompilierer
Beiträge: 435
Registriert: 7. Okt 2007 15:36
Wohnort: Darmstadt

Re: Praktikum 4: Ausgabe vergleichen

Beitrag von levitin »

Auf dem Blatt mit der Aufgabenstellung steht Beispielausgabe für Testroutine1 (Direct Mapped Cache)
Sie scheint aber fehlerhaft zu sein, weil die Anzahl der Zugriffe mit der Wirklichkeit nicht übereinstimmen.

Zugriff auf Speicherzelle 220.
Zugriff auf Speicherzelle 221.
Zugriff auf Speicherzelle 222.
Zugriff auf Speicherzelle 223. <- fehlt auf dem Praktikumsblatt
Zugriff auf Speicherzelle 732.
Zugriff auf Speicherzelle 733.
Zugriff auf Speicherzelle 734.
Zugriff auf Speicherzelle 735. <- fehlt auf dem Praktikumsblatt
...................................................................................

mki
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 9. Jul 2008 14:30

Re: Praktikum 4: Ausgabe vergleichen

Beitrag von mki »

Siehe: http://d120.de/forum/viewtopic.php?f=180&t=14142

Zugelassen werden auch die "veralteten" Testroutinen, schließlich war es unser Fehler.

thomas.stollberg
Neuling
Neuling
Beiträge: 3
Registriert: 19. Dez 2008 11:45

Re: Praktikum 4: Ausgabe vergleichen

Beitrag von thomas.stollberg »

Für alle Zugriffe ergibt sich der gleiche Index, nämlich 2. Somit wird der 168er Block in dem auch die 169 ist von der 041 gekickt und an der 169 muss daher ein Miss stehen...
Meiner Meinung nach stimmt das nicht, oder ich habe etwas nicht richtig verstanden...

Es gibt doch zu jedem CacheIndex zwei CacheBlöcke mit je 4 Byte (also zwei sets). (siehe kapitel4_speicher_0809_Teil2 Folie 4)
Zu beginn sind alle leer und valid = 0.
So jetzt lade ich Speicheradresse 40 in den Cache ( Index = 2 => set = 0 | set0.valid = 1 )
Als nächste lade ich Speicheradresse 168 in den Cache aber doch in das zweite Set da indem doch noch nie etwas drin gestanden hat.
(Index = 2 => set = 1 | set1.valid = 1)

So - Speicheradresse 680 schreibe ich jetzt aber wieder in das erste Set (bei Index 2) in den Cache , und überschreibe somit den Block der die Speicheradresse 40 beinhaltet (Index = 2 => set = 0). Der Block der die Speicheradresse 168 beinhaltet ist weiterhin vorhanden und zwar im zweiten Set vom Index 2.

Deshalb finde ich die Speicheradresse 169 wieder im Cache wie gesagt bei Index = 2 => set = 1

Ober habe ich den mengenassoziativer Cache total falsch verstanden? Ansonten stimmen meine Ergebnisse überein.

mki
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 9. Jul 2008 14:30

Re: Praktikum 4: Ausgabe vergleichen

Beitrag von mki »

Das ist soweit richtig, Du hast lediglich übersehen, dass vor dem Zugriff auf die 169 auf die 41 zugegriffen wird. Du sagst ja selbst, dass der Block mit den Einträgen 40, 41, 42, 43 überschrieben worden ist. Also wird gemäß der LRU-Strategie der zweite Block von Set 2 neu belegt, das heißt der Block mit den Einträgen 168, 169, 170, 171 wird überschrieben.

Die Routine ist so designed, dass genau dies passiert. Sie soll demonstrieren, dass die Performance der verschiedenen Cachetypen sehr stark von den Zugriffsmustern abhängen.

Nochmal etwas zur korrekten Terminologie: Ich habe es eben auch falsch gemacht und musste diesen Eintrag editieren: Sowohl 40, 168 als auch 680 bilden auf denselben Set ab (Pro Set können aber zwei Blöcke gespeichert werden!). Deine Terminologie bringt da etwas durcheinander.

Benutzeravatar
Demmi
Kernelcompilierer
Kernelcompilierer
Beiträge: 423
Registriert: 1. Okt 2007 12:56
Wohnort: Darmstadt

Re: Praktikum 4: Ausgabe vergleichen

Beitrag von Demmi »

Edit: Hab im Patterson/Hennesy nachgeschaut und mir die Frage selbst beantwortet...
Edit2: Mein 250. Beitrag xD
Edit3: So, bin fertig. Ich kann die Ergebnisse der ersten Beiträge bestätigen.
Saying that Java is nice because it works on all Plattforms is like saying that anal sex is nice because it works on all genders.

levitin
Kernelcompilierer
Kernelcompilierer
Beiträge: 435
Registriert: 7. Okt 2007 15:36
Wohnort: Darmstadt

Re: Praktikum 4: Ausgabe vergleichen

Beitrag von levitin »

ich entschuldige mich im Voraus für eine wahrscheinlich dumme frage, aber bei dem Mengenassoziativen Cache braucht man doch nicht mehr 4 sonder nur 3 Bits für den Index, oder? Dadurch wächst der Tag um 1 und der Offset bleibt immer noch auf 2.. Stimmt das soweit?

TAG(5 Bits) | Index(3 Bits) | Offset(2 Bits)

Benutzeravatar
Krümelmonster
Geek
Geek
Beiträge: 767
Registriert: 17. Okt 2007 13:58
Wohnort: Jossgrund

Re: Praktikum 4: Ausgabe vergleichen

Beitrag von Krümelmonster »

Stimmt so.
Stell deinen Fuß auf einen hohen Sockel
Mach dir ein Haar aus tausend Locken
Du bleibst doch immer, was du bist!

Schalli
Mausschubser
Mausschubser
Beiträge: 97
Registriert: 24. Okt 2006 21:50
Wohnort: Bayern

Re: Praktikum 4: Ausgabe vergleichen

Beitrag von Schalli »

Kann es sein das alle obig genannten Ausgaben einen Fehler bei Testroutine 2 Mengenassoziativ und Testroutine 3 Mengenassoziativ haben?
Hier mal meine Ausgabe zum vergleich:

Code: Alles auswählen

Test:		Testroutine 2
Cache Type:	Mengenassoziativ
-------------------------------------------
Zugriff auf Speicherzelle 040. Cache Miss.
Zugriff auf Speicherzelle 168. Cache Miss.
Zugriff auf Speicherzelle 680. Cache Miss.
Zugriff auf Speicherzelle 041. Cache Hit.
Zugriff auf Speicherzelle 169. Cache Hit.
Zugriff auf Speicherzelle 681. Cache Hit.
Zugriff auf Speicherzelle 042. Cache Hit.
Zugriff auf Speicherzelle 170. Cache Hit.
Zugriff auf Speicherzelle 682. Cache Hit.
Zugriff auf Speicherzelle 043. Cache Hit.
Zugriff auf Speicherzelle 171. Cache Hit.
Zugriff auf Speicherzelle 683. Cache Hit.
Zugriff auf Speicherzelle 044. Cache Miss.
Zugriff auf Speicherzelle 172. Cache Miss.
Zugriff auf Speicherzelle 684. Cache Miss.
Zugriff auf Speicherzelle 045. Cache Hit.
Zugriff auf Speicherzelle 173. Cache Hit.
Zugriff auf Speicherzelle 685. Cache Hit.
Zugriff auf Speicherzelle 046. Cache Hit.
Zugriff auf Speicherzelle 174. Cache Hit.
Zugriff auf Speicherzelle 686. Cache Hit.
Zugriff auf Speicherzelle 047. Cache Hit.
Zugriff auf Speicherzelle 175. Cache Hit.
Zugriff auf Speicherzelle 687. Cache Hit.

Hits: 18	Misses: 6

Test:		Testroutine 3
Cache Type:	Mengenassoziativ
-------------------------------------------
Zugriff auf Speicherzelle 003. Cache Miss.
Zugriff auf Speicherzelle 064. Cache Miss.
Zugriff auf Speicherzelle 086. Cache Miss.
Zugriff auf Speicherzelle 173. Cache Miss.
Zugriff auf Speicherzelle 122. Cache Miss.
Zugriff auf Speicherzelle 181. Cache Miss.
Zugriff auf Speicherzelle 143. Cache Miss.
Zugriff auf Speicherzelle 040. Cache Miss.
Zugriff auf Speicherzelle 070. Cache Miss.
Zugriff auf Speicherzelle 068. Cache Hit.
Zugriff auf Speicherzelle 111. Cache Miss.
Zugriff auf Speicherzelle 072. Cache Miss.
Zugriff auf Speicherzelle 009. Cache Miss.
Zugriff auf Speicherzelle 148. Cache Miss.
Zugriff auf Speicherzelle 044. Cache Miss.
Zugriff auf Speicherzelle 206. Cache Miss.
Zugriff auf Speicherzelle 122. Cache Hit.
Zugriff auf Speicherzelle 181. Cache Hit.
Zugriff auf Speicherzelle 143. Cache Hit.
Zugriff auf Speicherzelle 040. Cache Hit.
Zugriff auf Speicherzelle 070. Cache Hit.
Zugriff auf Speicherzelle 068. Cache Hit.
Zugriff auf Speicherzelle 111. Cache Hit.
Zugriff auf Speicherzelle 072. Cache Hit.

Hits: 9	Misses: 15

levitin
Kernelcompilierer
Kernelcompilierer
Beiträge: 435
Registriert: 7. Okt 2007 15:36
Wohnort: Darmstadt

Re: Praktikum 4: Ausgabe vergleichen

Beitrag von levitin »

Schalli hat geschrieben:Kann es sein das alle obig genannten Ausgaben einen Fehler bei Testroutine 2 Mengenassoziativ und Testroutine 3 Mengenassoziativ haben?
Hier mal meine Ausgabe zum vergleich:
Die Ausgaben sind ja bei Vielen vollkommen identisch und zwar, genau wie oben beschrieben..
Überleg dir mal, ob es möglich sein kann, dass alle Soldaten nicht im Gleichschritt marschieren, sondern nur ein Einzige es tut? ;-)

Schalli
Mausschubser
Mausschubser
Beiträge: 97
Registriert: 24. Okt 2006 21:50
Wohnort: Bayern

Re: Praktikum 4: Ausgabe vergleichen

Beitrag von Schalli »

Mir ist bewusst das die Wahrscheinlichkeit, dass ich als einziger mich irre, größer ist.
Aber erklär mir doch mal, warum bei Test 2 der Zugriff auf Speicherzelle 041 ein Miss sein soll.
Sollte der nicht wie bei mir ein Hit sein da er schon beim Zugriff auf Speicherzelle 040 eingelesen wurde?

FeG
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 182
Registriert: 6. Dez 2007 07:01

Re: Praktikum 4: Ausgabe vergleichen

Beitrag von FeG »

Hi,
Schalli hat geschrieben:Aber erklär mir doch mal, warum bei Test 2 der Zugriff auf Speicherzelle 041 ein Miss sein soll.
Sollte der nicht wie bei mir ein Hit sein da er schon beim Zugriff auf Speicherzelle 040 eingelesen wurde?
nein, da

41 = 0b101000
168 = 0b10101000
640 = 0b1010101000

(der Index der Adresse ist jeweils fett markiert). D.h. die Adressen werden alle auf den gleichen Index abgebildet. Also verdrängt die Adresse 640 die Adresse 40 aus dem Cache und 41 ist damit wieder ein Miss.

Gruß
FeG

Benutzeravatar
Jan Schejbal
Mausschubser
Mausschubser
Beiträge: 64
Registriert: 1. Nov 2007 00:17

Re: Praktikum 4: Ausgabe vergleichen

Beitrag von Jan Schejbal »

Aus dem Ergebnis von der letzten Seite, was alle für richtig halten, für Testfile 2, Testroutine 3, Set Associative:
Zugriff auf Speicherzelle 208. Cache Miss.
Zugriff auf Speicherzelle 81. Cache Miss.
Zugriff auf Speicherzelle 188. Cache Miss.
Zugriff auf Speicherzelle 22. Cache Hit.
Wie kann das sein - 208 und 81 werden doch aufs Set 2 (blöcke 4 und 5) abgebildet - ebenso wie 22, oder?

208 ist binär zum beispiel 11010000. letzte zwei bits sind offset: 110100__ und die mittleren vier 0100 würden dann die Blocknummer bedeuten. Da wir einen 2er set-associative cache haben, sind die blöcke 0100 und 0101 in einem Set, oder?
\(a = \sum\limits_{i=0}^{\infty} a_i \cdot 10^i\) mit \(a_0 = 2 \wedge a_1 = 4 \wedge \forall n \in \mathbb N^+\setminus\{1\} ~~ a_n = 0\)

Das Schlimmste an Zensur ist ████████████████████████

mki
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 9. Jul 2008 14:30

Re: Praktikum 4: Ausgabe vergleichen

Beitrag von mki »

Wir haben einen 64 Byte großen Cache. Die Blockgröße ist 4 Byte. Maximal können also 16 Blöcke gespeichert werden. In unserem mengenassoziativen Cache werden pro Set 2 Blöcke gespeichert. Also gibt es insgesamt 8 verschiedene Sets. Hierfür reichen 3 Bit aus, um den Set eindeutig über den Index zu identifizieren.

Die Adresse 22 ist binär und in tag | index | offset zerlegt

00000|101|10

die Adresse 208

00110|100|00

Beide haben einen unterschiedlichen Index. Da der Index eindeutig (!) den Set identifiziert, werden die Adressen auf unterschiedliche Sets abgebildet.

Ich hoffe, das Problem ist klar geworden: Dadurch, dass wir mehrere Sets haben, wird das Tagfeld länger.

Nochmal was Allgemeines:

1. Es gibt keine (naja, ok: kaum) dumme Fragen und man braucht sich nicht für Fragen entschuldigen.
2. Es ist richtig, dass Ihr die Lösungen hinterfragt, wenn Ihr sie nicht nachvollziehen können. Es kann immer mal sein, dass die Mehrheit falsch liegt. Das schließt auch Mehrheiten nicht aus, die WiMis enthalten. Zweitens, falls ihr selbst falsch liegt, können die Mißverständnisse nur durch eure Fragen ausgeräumt werden.

jan-o-sch
Neuling
Neuling
Beiträge: 1
Registriert: 13. Jan 2009 11:30

Re: Praktikum 4: Ausgabe vergleichen

Beitrag von jan-o-sch »

(Beitrag gelöscht ... hat sich erledigt!)

Antworten

Zurück zu „Archiv“