Es ist jetzt soweit und dann können wir hier mit der Vorlesung
anfangen.
Also mit der Übung, Thema Cache Speicher.
Wir haben in der Vorlesung gesehen, dass ein Cache Speicher im Prinzip
aus zwei Bereichen besteht.
Einmal ein Adressspeicher, einmal ein Datenspeicher.
Zusätzlich dazu gibt es zur Verwaltung oder existieren zur Verwaltung
von jedem Cache Eintrag, also von jedem Cache Block oder Cache Zeile,
existieren zwei Status-Bits.
Das ist einmal das Gültigkeits-Bit V und das Dirty-Bit.
Und die Arbeitsweise vom Cache Speicher lässt sich wie folgt
zusammenfassen.
Der Cache Controller oder die Cache Steuerung prüft bei einem Zugriff
auf ein Datum, also wenn ein Datum adressiert wird, eine Adresse auf
den Adressbus gelegt wird, dann wird gleichzeitig der Cache Speicher
adressiert und die Cache Steuerung prüft, ob der zur
Hauptspeicheradresse, zur angesprochenen Hauptspeicheradresse,
gehörende Hauptspeicherinhalt als Kopie im Cache steht.
Das ist die erste Bedienung.
Das heißt, das adressierte Datum muss, eine Kopie von dem adressierten
Datum muss im Cache Speicher vorhanden sein.
Die zweite Bedienung, falls dieser Eintrag im Cache Speicher vorhanden
ist, muss dieser Eintrag als gültig gekennzeichnet sein.
Das heißt, das Gültigkeits-Bit muss zum Beispiel gesetzt sein, wenn
das die Situation gültige Einträge bezeichnet.
So, die Prüfung beider Bedienungen führt zu einem Cache-Treffer oder
zu einem Cache-Fehlzugriff, also nicht Cache-Fehlzugriff, sondern zu
einem Fehlzugriff, das heißt auf Englisch zu einem Hit oder zu einem
Miss.
Und die Cache-Misses, die treten dann auf, wenn eine dieser
Bedienungen, die hier erwähnt sind, verletzt ist.
Das heißt, auch wenn der Eintrag im Cache vorhanden ist, das heißt,
die Bedienung 1 erfüllt ist, die Bedienung 2 aber nicht, dann haben
wir ja einen Cache-Miss.
So, wie funktioniert das Ganze bei Cache-Misses oder bei
Fehlzugriffen?
Bei Lazy-Zugriffen wissen wir, also Read-Miss, dass man hier das Datum
aus dem Hauptspeicher lesen muss und auch das Datum in den Cache
-Speicher lädt.
In dem Fall, der geladene Eintrag in den Cache-Speicher, der wird
natürlich in dem Fall auch als gültig markiert, weil das hat man ja
gerade aus dem Hauptspeicher geholt.
Und zusätzlich zu dem geholtenen oder geladenen Datum aus dem
Hauptspeicher, wird die zu diesem Datum gehörende Adressinformation,
die unterschiedlich lang ist, je nachdem welche Organisationsform der
Cache -Speicher ist, auch im Cache-Speicher abgelegt.
Das heißt, das ist der Tag, was wir ja zur Block-Identifikation oder
zur Findung von einem Block im Cache-Speicher verwenden werden.
So, nun geht es weiter und zwar, wie sieht es aus bei
Schreibzugriffen?
Also, wenn jetzt ein Write-Miss vorliegt, dann wissen wir, dass die
Aktualisierungsstrategie entscheidend ist und die bestimmt, ob jetzt
der entsprechende Block in den Cache geladen wird und dann mit dem zu
schreibenden Datum aktualisiert wird oder nur der Cache aktualisiert
wird und der Hauptspeicher unverändert bleibt.
Gut, das heißt, Write-Miss bedeutet, dass der Prozessor auf einen
Eintrag zugreift und diesen Eintrag, dieses Datum innerhalb von einem
Block verändern will.
Das Datum ist aber im Cache-Speicher nicht vorhanden.
Write-Miss bedeutet, dass man den entsprechenden Block, in dem dieses
Datum vorhanden ist, in den Speicher lädt und das entsprechende Datum,
also der Block kann ja 16 Byte groß sein und wir greifen auf ein Wort,
also auf 4 Byte innerhalb von diesem Block.
Das heißt, hier wird der entsprechende Block, alle 16 Byte zum
Beispiel, in den Cache geladen und drin wird der zu schreibende Datum
aktualisiert.
Wir haben hier ja die zwei unterschiedlichen Aktualisierungsstrategien
kennengelernt.
Ich werde hier nicht nochmal drauf eingehen, sondern wir betrachten
den Fall, dass wir ein Write-Hit oder ein Write-Miss haben.
Das heißt, beide Bedienungen treffen zu oder sind erfüllt.
In dem Fall erfolgt eigentlich der Zugriff auf den Cache-Speicher und
im Fall von einem Read-Hit wird das Datum aus dem Cache geholt und dem
Prozessor zugeführt.
Im Fall von einem Write-Hit wird das Datum von der CPU in den Cache
geschrieben an der entsprechenden Stelle im Block.
Gibt es Fragen dazu?
Hat jemand irgendwas hier bis hierher nicht verstanden?
Nein?
Dann fangen wir an und zwar mit Aufgabe 1.
In einem Mikroprozessor-System mit 32-Bit-Datenzugriff.
Was bedeutet das, 32-Bit-Datenzugriff?
Man greift auf den Hauptspeicher und holt Daten, die 32-Bit-breit
sind.
Ist ein Daten-Cache-Speicher vorhanden?
Was ist zum Beispiel eine andere Art statt Daten-Cache-Speicher, was
hat man noch?
Befehls-Cache-Speicher.
Was ist dir lieber, ein Daten-Cache-Speicher als Aufgabe in der
Klausur oder ein Befehls-Cache-Speicher?
Machen wir eine Abstimmung.
Wer ist für ein Daten-Cache-Speicher?
Das werde ich wirklich halten, diese Versprechung.
Also, wer ist für ein Daten-Cache-Speicher?
Wer ist für Befehls-Cache-Speicher?
Also dann machen wir Daten, oder?
Gut, also ein Befehl, ein Daten-Cache-Speicher, das heißt auf dem
können sowohl Lese- als auch Schreibe-Zugriffe ausgeführt werden.
Jetzt kommt die Information, das Laden des Cache-Speichers erfolgt in
Blöcken von je 8 Byte.
So, denken wir an den Aufbau von dem Cache-Speicher.
Wir haben hier den Adress-Speicher, wir haben hier den Datenspeicher
innerhalb des Cache.
Wir haben hier zwei Status-Bits.
Und diese Information besagt, dass der Cache-Speicher mit Blöcken von
je 8 Bytes geladen wird.
Das heißt, jede Zeile hier kann 8 Bytes aufnehmen.
Das sind hier 4 Byte und das sind hier 4 Byte.
Die Hauptspeicher-Adresse umfasst 24 Bit.
Warum ist diese Information wichtig?
Wie breit ist die Hauptspeicher-Adresse?
Muss diese Information bei der Aufgabe angegeben werden?
Genau, damit man weiß, wie breit ist der Tag und wie viel Speicher
-Kapazität oder Speicherplatz in diesem Adress-Speicher vorsehen muss,
um diesen Speicher überhaupt realisieren zu können.
Also die Hauptspeicher-Adresse umfasst 24 Bit.
Die Cache-Kapazität beträgt 256 Bytes.
Mit Cache-Kapazität wird normalerweise die Speichermenge bezeichnet
für reine Daten.
Das heißt, man kann hier wirklich 256 Bytes in diesem Cache-Speicher
ablegen.
Das heißt, diese Information hier, die beinhaltet nicht den
Speicherbedarf, den man braucht zur Speicherung von dem Tag und zur
Speicherung von den beiden Status-Bits.
Haben wir das verstanden?
Das heißt, wenn wir von 128 Kilobyte Cache-Speicher sprechen, dann
meinen wir damit, dass der Datenbereich 128 Kilobyte groß ist.
Gut.
Im ersten Aufgabenteil wollen wir angeben, wie viele Zeilen hat der
Cache -Speicher und wir sollen die Unterteilung der Hauptspeicher
-Adresse angeben für einen direkt abgebildeten Cache-Speicher, also
Direct -Mapped-Cache für einen voll-assoziativen Cache-Speicher und
für einen 4-fach-Satz-assoziativen Cache-Speicher, also 4-Way-Set
-Associative -Cache.
Wie viele Zeilen hat der Cache-Speicher?
Diese Information entnimmt man aus der Speicher-Kapazität, also aus
der Cache-Kapazität und aus der Anzahl oder der Größe der Blöcke, die
man im Cache-Speicher ablegen kann.
Also hier, jeder Block ist 8 Byte, die gesamte Kapazität hier von dem
ist 256 Byte, das heißt 256 durch 8, also 8 Zeilen, oder?
Also die Cache-Kapazität 2 hoch 8, die Blöckgröße ist 2 hoch 3, also
insgesamt 2 hoch 5, also 32 Zeilen.
Also Cache-Kapazität durch Blöckgröße bekommt man Anzahl der Zeilen im
Cache -Speicher.
Egal wie der Cache-Speicher organisiert ist, ob das ein Direct-Mapped
-Cache oder ein Voll-Assoziativ-Cache oder ein Satz-Assoziativ-Cache,
da hat man immer 32 Einträge bzw.
32 Zeilen.
In jeder Zeile hat man einen Block der Breite von 8 Bytes,
in jeder Zeile.
Und dann in jeder Zeile muss zu jedem Block hier ein Tag abgelegt
werden in diesem Cache-Speicher, ein Dirty-Bit und ein Gültigkeits
-Bit.
Das ist der Datenspeicher mit der Kapazität 256, also Summe der
Kapazität ist 256 Bytes, in jeder Zeile 8 Bytes, also insgesamt 32
Zeilen.
Gut, die Unterteilung der Hauptspeicher-Adresse ist deshalb notwendig,
damit wir wissen, wie viel eigentlich aus der Adresse, aus der 24-Bit
-Adresse, wie viele Bits erforderlich oder müssen als Tag im Cache
-Speicher hier abgelegt werden.
Wir wissen ja, dass wir unterschiedliche Organisationsformen von Cache
-Speichern haben.
Das heißt einmal die ortsorientierten Cache-Speicher, wo man von
vornherein weiß, dass ein Block aus dem Hauptspeicher nur in einer
bestimmten Zeile im Cache-Speicher abgelegt werden kann und nur dort
zu finden ist.
Und wir haben aber vollassoziative Cache-Speicher, wo ein Block aus
dem Hauptspeicher überall in jeder dieser 32 Zeilen vom Cache-Speicher
vorhanden sein kann.
Und deshalb müssen wir den auch überall suchen in diesen 32 Zeilen.
Und deshalb, um das realisieren zu können, haben wir bei den DirectMap
-Caches einen Teil von der Hauptspeicher-Adresse dazu genommen, um
praktisch die Nummer der Zeile im Cache festzulegen.
Und das heißt hier, wenn wir eine Zeile von 32 wählen müssen, dann
brauchen wir 5 Bits, um das machen zu können.
Und diese 5 Bits müssen wir von den 24 Bits der Adresse wegnehmen.
Das heißt, wir haben mindestens 24 minus 5 und dann noch irgendetwas,
was wir eigentlich als Tag-Länge angeben können.
So, das heißt, die Unterteilung der Hauptspeicher-Adresse bei dem
Vollassoziativ -Cache brauchen wir fast die gesamte Adresse bis auf
die ersten Bits, die zuständig sind, um ein Wort innerhalb von diesem
Block und ein Byte innerhalb von einem Wort auswählen zu können.
Also, ein Block ist 8 Byte groß und wir wollen ja einzelne Bytes hier
adressieren.
Das heißt, wir müssen hier irgendwie ein Wort innerhalb von diesen 8
Bytes selektieren, entweder das Wort hier oder das Wort.
Und dann müssen wir innerhalb von dem Wort bzw.
von dem Wort zum Beispiel das Byte hier oder das Byte hier
selektieren.
Das heißt, insgesamt hier die ganze Geschichte, um ein einzelnes Byte
innerhalb von einem Block selektieren zu können, brauche ich wie viele
Bits?
Bei einer Blockgröße von 8 Byte 3 Bits.
Das heißt, die ersten 3 Bits, die 3 niedrigwertigen Bits der Adresse
dienen eigentlich nur dazu, um die Adresse eines Wortes im Block oder
eines Bytes im Wort festzulegen.
Der Rest, wie wir in der Vorlesung gesehen haben, ist der Eintag bei
dem vollassoziativen Cache.
Das heißt, hier haben wir bei dem vollassoziativen Cache die Adresse
von 24 Bits.
Die zwei niedrigwertigen Bits dienen zur Byteauswahl im Wort.
Dann haben wir hier mit 0,0 hier zum Beispiel das 0.0 Byte hier in dem
ersten Wort adressiert.
Das heißt, die ersten 3 Bits hier dienen praktisch dazu, ein Byte im
Block zu adressieren.
Der Rest hier ist nichts anderes als der Tag.
Und das ist die Information, die man dann in diesem Adressspeicher zu
jedem Block ablegen muss, wenn man diesen Cache-Speicher als
vollassoziativen Speicher realisiert.
So, das heißt, Tag haben wir hier 24 Bits minus die 3, also insgesamt
21 Bits.
So, wie sieht es aus bei dem Direct Map Cache, also bei dem direkt
abgebildeten Cache?
Wir müssen nach wie vor ein Byte innerhalb vom Block adressieren.
Das heißt, wir brauchen auf jeden Fall diese ersten 3 Bits.
Und dann zusätzlich müssen wir eine Zeile aus 32 wählen.
Um dies machen zu können, brauchen wir weitere 5 Bits.
Das heißt, die Bits 3, 4, 5, 6 und 7 bilden hier nichts anderes als
den Zeilenindex.
Der Rest ist hier Tag und der Tag ist in dem Fall 24 minus 3 minus 5,
also 24 minus 8, insgesamt 16 Bits.
So, wie sieht es aus bei dem 4-fach-assoziativen Cache-Speicher?
Was heißt 4-fach-assoziativer Cache-Speicher?
Das heißt, je 4 Zeilen werden zusammengefasst zu einem Satz.
Und man selektiert dann keine einzige Zeile, sondern einen Satz.
Das heißt, wenn wir hier 32 Zeilen haben, 4-fach-assoziativ, das
bedeutet, alle 4 fassen wir zu einem Satz.
Also insgesamt haben wir 8 Sätze und wir müssen einen Satz auswählen
von diesen 8 Sätzen.
Dazu brauchen wir 3 Bits, also das heißt, die Bits 3, 4 und 5 aus der
Hauptspeicheradresse sind hier Satzindex.
Die Tag-Länge ist in dem Fall hier 24 minus 3 minus 3, also 24 minus
6, 18.
So, abgesehen davon,
wie viele Vergleiche man bei den unterschiedlichen Cache-Speichern
braucht, um dieses Suchen nach dem Datum in einem einzigen Tag-Zyklus
garantieren zu können, sieht man hier vielleicht nochmal die Vor- und
Nachteile von den Direct-Mapped und Voll-Assoziativen Cache-Speichern.
Gehen wir davon aus, wir wollen den gleichen Speicher realisieren,
lächerliche 256 Bytes.
Und wir würden hier uns für einen Voll-Assoziativen Cache-Speicher
entscheiden.
Dann brauchen wir zu jedem Block zusätzlich 21 Bits, die wir noch
irgendwo zwischenspeichern müssen, in dem Adress-Speicher.
Bei dem Direct-Mapped brauchen wir nur 16, das heißt für jeden Block 5
Bits weniger.
Gut, also bei den Vierfach-Assoziativen brauchen wir eine Anzahl von
Bits, die zwischen den beiden hier liegt.
Das heißt, man sieht hier, dass die Hardware-Kosten zur Realisierung
von den Voll-Assoziativen Cache-Speichern, zusätzlich zu der
Vielanzahl von Vergleichern, die man braucht, also man braucht, wie
wir wissen, für jede Zeile einen einzigen Vergleicher.
Zusätzlich zu dieser erhöhten Vergleicher-Anzahl braucht man hier mehr
Speicherbedarf zur Speicherung von der Adress-Information, von den
Tags, die zu den jeweiligen Blöcken hier gehören.
So, haben wir das verstanden?
Gibt es Fragen dazu?
Gut, dann machen wir weiter mit dem zweiten Teil, und zwar geben Sie
für die drei Cache-Speicher die Anzahl der benötigten Vergleicher und
die zu vergleichende Bitzahl an.
Wollen wir das gemeinsam mal erledigen, diese Angelegenheit, oder soll
ich hier schnell auf den nächsten Schritt gehen und die Tabelle
auflegen?
Wer ist für Tabelle auflegen?
Wer weiß nicht, was mit der Aufgabenstellung hier gemeint ist?
Einige ehrliche Menschen haben wir auch hier, ja?
Gut.
So, wir wissen ja, dass der Cache-Speicher im Wesentlichen so
aussieht.
Status -Bits, Tag-Information, Daten.
Und wir wissen bei einem voll assoziativen Cache-Speicher, dass ein
Datum, ein adressiertes Datum, überall hier in diesem Cache-Speicher
landen kann.
Das heißt, wenn wir dieses Datum suchen und diese Information in einem
einzigen Taktzyklus haben wollen, ob das Datum im Cache ist oder
nicht, dann können wir es uns nicht erlauben, durch die einzelnen
Zahlen des Cache-Speichers durchzugehen und nacheinander die Tag
-Information mit der Tag-Information des gesuchten Datums zu
vergleichen.
Deshalb muss man bei dieser inhaltsorientierten Adressierung, das
heißt, wo das Datum überall im Cache sein kann, zu jeder Zeile hier
einen Vergleicher vorsehen, der immer die Tag-Information aus der
Adresse des gesuchten Datums mit der hier gespeicherten Information
vergleicht.
Und das gleichzeitig.
Das heißt, beim voll assoziativen Cache-Speicher braucht man oder muss
in jeder Zeile ein Vergleicher vorhanden sein.
Bei unserem Cache-Speicher mit 32 Zeilen brauchen wir dann 32
Vergleicher.
Bei dem Direct-Mapped-Cache weiß man schon anhand von der Adresse hier
des gesuchten Datums, dass das Datum, wenn überhaupt, nur in der Zeile
25 im Cache vorhanden sein kann oder darf oder sogar muss.
Das heißt, anhand von der Information hier und von dem Zeilenindex
weiß man, aha, wenn das Datum überhaupt im Cache vorhanden ist, dann
kann der nur an der Stelle 25 im Cache sein.
Deshalb braucht man nur einen einzigen Vergleicher, weil anhand von
dem Zeilenindex man schon halt diesen Tag hier rausholt und den hier
mit der Adressinformation des gesuchten Datums vergleichen muss.
Ja, bei den Satz-Assoziativen Cache-Speicher, es ist klar, ein Datum
kann anhand von dem Satzindex, weiß man, okay, das Datum kann nur in
diesem Satz sein, bestehend aus vier Zeilen.
Wir haben hier 32 Zeilen, vierfach assoziativer Cache, also insgesamt
acht Sätze.
Das heißt, unser Satzindex, wie wir gesehen haben, ist drei Bit breit.
Anhand von dem Satzindex, von der Adresse hier, wissen wir, wir müssen
nur hier in der Zeile suchen, in dem Satz suchen.
Aber in diesem Satz hier, in diesem blauen Satz, kann ja das Datum
wiederum überall sein.
Das heißt, entweder in der ersten oder in der zweiten oder dritten
oder vierten Zeile in diesem Satz.
Das heißt, wie viele Vergleiche brauchen wir hier in dem Fall?
Ja, vier Vergleiche.
Das heißt, das ist ja ein teilassoziativer Cache-Speicher.
Und das heißt, jeder Satz ist für sich vergleichbar mit einem
vollassoziativen Cache-Speicher.
Das heißt, für jeden Satz brauchen wir so viele Vergleiche, wie der
Satz Zeilen umfasst.
Und diese Vergleiche, die sind nicht immer gleichzeitig aktiv, weil
wir durch den Satzindex immer festlegen, überhaupt welcher Satz
eingesprochen wird.
Gut, das heißt, die Anzahl der Vergleiche haben wir erledigt.
Die Anzahl der zu vergleichenden Bits ist eigentlich die Tag-Länge,
weil das ist die Adressinformation, die im Cache-Speicher zu jedem
Block, also die zu jedem Block gehören, die Adressinformation, die im
Cache -Speicher abgelegt wird.
Und die Tag-Länge haben wir vorher berechnet.
Das heißt hier, die Anzahl der Vergleiche bei einem vollassoziativen
Cache -Speicher mit 32 Zeilen
32 Vergleiche, die Tag-Länge ist 24, das ist die Breite von der
Hauptspeicheradresse, minus die drei Bits, die wir brauchen, um einen
Byte innerhalb des Blocks zu adressieren, bei einer Blockgröße von
acht Bytes.
Beim DirectMap-Cache brauchen wir einen einzigen Vergleich.
Die Tag-Länge ist 24 minus die drei, die wir für die Byte-Adressierung
im Block brauchen und minus die fünf, die wir als Zeilen-Index gesehen
haben.
Das heißt insgesamt 16.
Und bei dem vierfach-assoziativen Cache brauchen wir als Satz-Index
drei statt Zeilen-Index fünf beim DirectMap-Cache.
Also das heißt hier haben wir eine Tag-Länge, die um zwei größer ist
als die beim DirectMap-Cache.
So, haben wir alles verstanden?
Gut, dann machen wir weiter.
Und zwar, welche Zeilen sind bei diesen Cache-Speichern hinsichtlich
der Block-Ersetzung als zusammengefasst zu betrachten?
Zum Beispiel für einen Alterungsmechanismus nach dem Least-Recently
-Used -Prinzip.
Ja, das ist klar, das heißt, diese Alterungsmechanismen, die haben wir
ja kennengelernt, die geben an bei einem vollen Cache-Speicher, wenn
der Cache-Speicher voll und ein neues Datum in den Cache-Speicher
geladen werden muss, welches Datum und welcher Block aus dem Cache
-Speicher verdrängt werden soll.
So, das heißt, welche Zeilen muss man hier berücksichtigen, wenn es
darum geht, irgendwas aus dem Cache-Speicher zu verdrängen?
Das ist klar, beim voll-assoziativen Cache muss man den gesamten Cache
berücksichtigen, das heißt die Zeilen 0 bis 31.
Bei dem DirectMap-Cache, gibt es dort eine Ersetzungsstrategie oder
eine Aktualisierungsstrategie oder braucht man sowas überhaupt bei dem
DirectMap -Cache?
Das braucht man überhaupt nicht, weil auch wenn der Cache leer ist
oder wenn der Cache nur ein Datum in Zeile 3 zum Beispiel enthält und
jetzt ein neues Datum geladen werden soll in den Cache und dieses neue
zu ladende Datum wird durch diese direkte Abbildung auch auf Zeile 3
abgebildet, dann wird das alte Datum in Zeile 3 überschrieben, obwohl
der Rest des Cache-Speichers leer ist.
Das heißt eigentlich beim DirectMap-Cache ist das Schwachsinn hier.
So, bei A4-Cache-Speicher müssen wir natürlich immer die Zeilen, die
durch den Satzindex ausgewählt sind, also die innerhalb von dem
jeweiligen Satz vorhanden sind, zusammengefasst betrachten und die
Ersetzungsstrategie dort gucken.
Das heißt hier nach dem LRU-Prinzip müssen wir innerhalb von dem
jeweiligen Satz gucken, auf welches Datum wurde jetzt seit langem
nicht mehr zugriffen.
Also auf welchen oder welcher Datum wurde, wie sagt man das, also der
am längsten im Cache vorhandene Datum, ohne dass es darauf zugegriffen
wurde, das wird halt ersetzt.
Okay, wenn es keine Fragen dazu gibt, dann gehen wir weiter zu Aufgabe
2 mit dem Hinweis für die Leute, die hinzugekommen sind.
Die Übung zur Vorlesung Technische Informatik II wurde gewählt, um an
der universitätsweiten Befragung und Bewertung der Lehre teilzunehmen.
Das Ganze erfolgt online hier und wird organisiert vom Institut für
Soziologie.
Ich möchte diejenigen, die jetzt später in die Vorlesung oder in die
Übung gekommen sind, hier nochmal diese Zettel zu holen, wo der
Zugang, Passwort und so weiter und so fort eingegeben ist.
Ich würde mich freuen, wenn so viele wie möglich an dieser Befragung
teilnehmen würden, weil nur anhand von solchen Befragungen können wir
wissen, wie schlecht unsere Vorlesungen sind oder wie gut sie sind,
beziehungsweise was man noch hier verbessern muss.
Also diejenigen, die hinzugekommen sind, können am Ende der Vorlesung
hier noch Passwörter holen und mitmachen.
Bei der Aufgabe 2 wollen wir jetzt eine Folge von Zugriffen auf die
drei Cache-Speicher, die wir auseinandergenommen haben, in Aufgabe 1
mal betrachten.
Das heißt, für die drei Cache-Speicher, Direct-Mapped-Voll-Assoziativ
-A4 -Cache-Speicher von der Aufgabe 1,
werden drei Hauptspeicherblöcke geladen und zwar mit den Adressen, die
hier in hexadezimaler Schreibweise angegeben sind.
Wir nehmen an, also wir wissen ja von diesen drei Cache-Speicher, wir
wissen alles über diese Cache-Speicher.
Wir wissen, dass bei dem Voll-Assoziativen-Cache-Speicher wir eine Tag
-Länge von 21 Bit haben.
Wir wissen, dass bei dem Direct-Mapped-Cache wir eine Tag-Länge von 24
minus 8 von 16, bei dem A4 24 minus 6, also von 18.
Und wir wissen, wie viele Zeilen wir haben, wie viele Sätze und so
weiter und so fort.
Jetzt haben wir die Aufgabe, dass diese Blöcke hier mit den Adressen
in den Speicher geladen werden sollen.
Wir sollen zunächst mal annehmen, dass die Cache-Speicher leer sind
zunächst und das Laden soll jeweils in die Zeile mit der niedrigst
verfügbaren, also mit der niedrigst, das klingt besser, verfügbaren
Zeilennummer erfolgen.
Was bedeutet das eigentlich?
Diese Aussage, die bezieht sich jetzt nur auf den Voll-Assoziativen-
und Sätze-Assoziativen-Cache-Speicher.
Das heißt, wenn der Voll-Assoziativen-Cache-Speicher leer ist und das
erste Datum geladen werden soll, dann soll das Datum die Zeile mit der
Nummer 0 und nicht 31 geladen werden.
Bei dem Sätze-Assoziativen-Cache bedeutet das, wenn das ein Zugriff
auf Satz 7 ist, dass jetzt der Cache-Speicher oder das Datum nicht zum
Beispiel auf Satz 7, nicht in Zeile 31, sondern in Zeile 28 erfolgen
soll.
Für den Direct-Map-Cache ist diese Aussage eigentlich bedeutungslos,
weil wir wissen ja halt, dass ein Datum oder ein entsprechender Block
hier definitiv in einer bestimmten Zeile, die durch eine direkte
Abbildung vorgegeben ist, erfolgen muss.
Geben Sie bei der Zuordnung von Blöcken zu Zeilen nicht die Adressen,
sondern die Blocknummern an.
Gut, was ist die Blocknummer eigentlich?
Was ist die Blocknummer oder die Blockadresse?
Weiß es jemand?
Hallo?
Aufwachen, aufwachen.
Richtig eingeschlafen.
So, was ist die Blocknummer?
Wie kriegen wir die Blocknummer raus?
Also hier haben wir ja Zugriffe auf Hauptspeicher-Blöcke mit den
Adressen so und so und so.
Das heißt, das sind jetzt hier Zugriffe auf die Adresse so und so, die
Adresse so und so und die Adresse so und so.
Und wir sollen bei der Zuordnung hier, wir sollen nicht sagen, die
Adresse 8 wird abgebildet z.B.
bei dem DirectMappedCache auf Zeile 2, sondern wir sollen halt sagen,
dass die Block mit der Nummer so und so in Zeilen so und so abgebildet
wird.
Ja, du hast die Hand hochgehoben.
Oder du?
Wie bitte?
Durch Modulo-Rechnung.
Wo hast du das her?
Es kam gestern in der Vorlesung vor.
Ja, warum ist es so?
Modulo oder Diff?
Modulo.
Aha.
Also Modulo, Zeilen, Anzahl.
Aber was ist Modulo, Zeilen, Anzahl?
Also was ist das?
Hauptspeicheradresse Modulo, Zeilen, Anzahl.
Wer ist damit einverstanden?
Das ist dann die Blocknummer.
Wie bitte?
Sätze, Anzahl.
Das ist ein neuer Vorschlag.
Also Hauptspeicheradresse Modulo, Satz, Anzahl.
Sagst du.
Noch andere?
Also das hat bestimmt einen Wahrheitswert, diese beiden Aussagen.
Aber das stimmt noch nicht ganz.
Was ist die Blockadresse?
Also wenn wir jetzt hier eine Adresse haben, 24 Bits, warum haben wir
die ersten drei Bits rausgeschmissen?
Also wir haben gesagt immer byte im Wort und Wort im Block.
Ja, damit wir ein einzelnes byte adressieren.
Das heißt, wenn wir ein Block adressieren wollen, dann brauchen wir
diese drei nicht.
Also, das heißt, das ist die Hauptspeicheradresse abgeschnitten davon,
was man braucht, um ein byte innerhalb eines Blocks zu adressieren.
Und was wäre das für eine Operation?
Wie bitte?
Ein Shift, Right und Right, ganz genau.
Arithmetisch gesehen, was ist Shift, Right und Right?
Das ist doch eine Division, oder?
Durch was?
Durch 8.
Und was ist 8?
Die Blockgröße.
Das ist also die Hauptspeicheradresse, dividiert durch die Blockgröße.
Die Modulo-Sachen, die kommen noch später.
Aber die haben damit noch nichts zu tun.
So, das ist eine der Sachen, in die viele Leute reintappen in der
Klausur.
So, das heißt, hier haben wir ein Block von zwei Wörtern, das heißt 8
byte.
Und wir wissen, das sind hier unsere Adressen in hexadezimaler
Schreibweise.
Die Hauptspeicherunterteilung kennen wir.
Zunächst mal haben wir bei jedem der Cache-Speicher die ersten zwei
Bits, um ein byte innerhalb eines Wortes auszuwählen.
Und dann haben wir das dritte Bit, um ein Wort innerhalb eines Blocks
auszuwählen.
Bei einem Block der Breite 8 byte.
Ja, ist das klar oder ist das langweilig?
Also ich kann viel schneller machen, aber ich will sicher sein, dass
alle diese Punkte hier verstanden sind.
Wird noch diskutiert?
Gut, das heißt, die ersten drei Bits, die sind da, um letztendlich ein
byte im Block zu adressieren.
So, der Rest ist nichts anderes als die Blocknummer.
Tag oder natürlich bei den Direct-Mapped und nicht vollassoziativen
Cache -Speicher auch Index.
So, das heißt, die Blocknummer, die ist halt der Tag bei dem
vollassoziativen Cache-Speicher.
Und die ist immer 21 Bit breit.
Und das heißt, die Adresse 8 gehört ja zum Block 1, die Adresse F8 zum
Block 1F bzw.
31 Dezimal.
Die Adresse 108 Hexadezimal liegt im Block mit der Adresse 21
Hexadezimal bzw.
33 Dezimal.
Woher haben wir das?
Das ist eigentlich der Rest, was man hier hat.
Also diese 21 Bits, die man hier hat, die sind hier ausgeschrieben.
Und daraus entnimmt man, dass die Blocknummer hier 1 ist, dass die
Blocknummer hier 31, wie man sieht, und dass die Blocknummer hier 33.
Also auswerten von dem, was hier steht.
So, was war die Aufgabenstellung?
Die Aufgabenstellung war, dass wir hier die Zugriffe auf diesen drei
Daten halt betrachten müssen.
So, jetzt wollen wir mal diesen Satz- und Zeilenindex bestimmen.
Das war jetzt, was wir gemacht haben, die Informationen, die wir
brauchen für den vollassoziativen Cache-Speicher.
Jetzt betrachten wir mal den Direct-Mapped-Cache.
Wir wissen anhand der Unterteilung der Hauptspeicheradresse, dass die
Bits 3 bis 7 den Zeilenindex bilden.
Das heißt, wir wissen hier, dass die Adresse hier auf Zeile 1
abgebildet ist, die nächste Adresse auf Zeile 31 und die dritte
Adresse wiederum auf Zeile 1.
Das heißt, Zeilennummer 5 Bit lang, die Bits 3 bis 7.
Das heißt, die Adresse 8 auf Zeile 1, die Adresse F8 auf Zeile 31 und
die Adresse 108 auf Zeile 1.
So, wie sieht es aus bei dem A4-Cache-Speicher?
Nochmal die Hauptspeicheradresse berücksichtigen.
Das heißt hier, das war der Satzindex mit drei Bits.
Und das heißt, das sind die Bits 3, 4 und 5.
Das heißt, bei der Adresse 1 wird das Datum in Satz 1 geladen, bei der
Adresse hier Satz 7 und bei der Adresse hier Satz auch 1.
Und wenn wir das Ganze immer in die Zeile mit der niedrigsten
Zeilennummer laden sollen, dann wird das Datum hier natürlich in
Zeilennummer 1.
Zeilennummern fangen bei 0 an und Satznummern auch.
Das heißt in Zeile 4.
Hier Satz 7, das ist der letzte Satz, 28.
Und die 1 hier, wiederum in Satz 1, aber in Zeile 5.
So, das heißt, hier nochmal das Ganze ausgeschrieben, die Zuordnung
dieser Adressen hier zu den Sätzen in dem vierfach assoziativen Cache
-Speicher und wie das Ganze hier funktioniert, werden wir hier sehen.
Das heißt, hier haben wir unser Cache-Speicher bestehend aus 32
Zeilen.
Tag und Formation Block aus 8 Bytes, der Hauptspeicher.
Und der Block 1 mit der Nummer 1, das war mit der Adresse 8, der wird
ja hier in Zeile 0 in den Cache geladen.
Der Block mit der Nummer 31 in die nächste freie Zeile, das heißt
Zeile 1 und 33 in Zeile 2.
Das heißt, der Zustand von dem Cache-Speicher nach dem Zugriff auf
diesen drei Adressen, auf diesen drei Blocken sieht wie hier
dargestellt aus.
Ja, wie sieht es aus bei dem DirectMap-Cache?
Block 1 wird in Zeile 1 geladen.
Block 31 in Zeile 31, haben wir ja vorher festgestellt.
Und Block 33 wiederum in Zeile 1.
Das heißt, wir sehen hier, der ganze Cache-Speicher ist fast leer, nur
zwei Einträge sind vorhanden und trotzdem wird der Block 3 hier, weil
der Block 3 laut Abbildungsvorschrift auf Zeile 1 abgebildet wird, den
dort vorhandenen Datum überschreiben.
Das heißt, der Zustand von dem Cache-Speicher nach diesen drei Lazy
-Zugriffen oder LADY-Vorgänge in den Cache-Speicher sieht wie folgt
aus.
Das heißt, Block mit der Nummer 1 wurde hier durch den Block mit der
Nummer 33 überschrieben, durch diesen starren Abbildungsmechanismus
von dem direkt abgebildeten Cache-Speicher.
Ja, wie sieht es aus bei dem A4-Cache-Speicher?
Wir wissen, die ersten Blocke 1 und 31 werden, 1 wird auf Satz 1 und
31 auch auf Satz 1, äh, 33 auch auf Satz 1, aber 31 auf Satz 7.
Das heißt, 1 wird in Satz 1 kommen, das ist die Zeile Nummer 4, wenn
wir hier mit 0 anfangen, 0, 1, 2, 3, also 4 hier, dann kommt der Block
31 in Satz 7, das heißt hier Zeile Nummer 28, und der Block 33, der
bei dem DirectMap-Cache den Block 1 hier in Zeile 1 überschrieben hat,
der hat natürlich hier Platz im Satz 1, weil es ist nicht jetzt die
Abbildung auf diese einzige Zeile, sondern auf den ganzen Satz, und im
Satz sind noch, oder waren, nachdem der Block 1 dorthin geladen wurde,
drei Plätze frei, das heißt hier kommt es, oder durch diesen
Mechanismus, vermindert man hier diese Erscheinung von dem Cache
-Flattern, was man bei dem DirectMap-Cache hat, wenn man immer
Zugriffe auf Daten hat, die auf die gleiche Zeile im Cache abgebildet
werden.
Das heißt, hier wird dieser Nachteil von dem DirectMap-Cache ein
bisschen vermindert.
Gibt es Fragen dazu?
Ist alles klar?
Gut, vielleicht kommen wir jetzt zu dem, was wir vorher hier hatten,
die Diskussion, das heißt, wie ermittelt man ja die Block-Adresse, wir
haben gesehen, dass die Block-Adresse ist die Hauptspeicher-Adresse,
davon abgeschnitten die Bits, die notwendig sind, um ein Byte
innerhalb von diesem Block adressieren zu können, das heißt die
Abbildung Hauptspeicher-Adresse, die Blockgröße, die Zeilennummer,
erhält man wiederum aus der Block-Adresse Modulo Zeilenanzahl und
Satznummer wiederum aus der Block-Adresse Modulo Satzanzahl.
Das heißt, in unserem Beispiel können wir diese Vorschriften hier auch
anwenden und sehen wir, die Blocknummer hier ist Diff 8, ist 1,
Zeilennummer 1 und Satznummer 1 für die Adresse 8, die Adresse F8, das
Gleiche, Blocknummer 31, Zeilennummer 31 und Satznummer 7 und für die
Adresse 108, Blocknummer 33, Zeilennummer und Satznummer 1.
So, das wollen wir anhand von einer Aufgabe auch konkret machen, und
zwar anhand von einem Cache-Speicher, ich glaube, das ist der
einfachste Cache-Speicher, den es gibt.
Es sind drei Cache-Speicher eingegeben, wiederum Direct-Mapped,
zweifach -assoziativer Cache-Speicher, voll-assoziativer Cache
-Speicher, die jeweils vier Cache-Blöcke besitzen und jeder Cache
-Blöck ein Byte groß ist.
Das heißt, wir haben hier vier Cache-Blöcke, das heißt, der Cache
-Speicher besteht aus vier Zeilen, 0, 1, 2, 3 und jeder Block ist ein
Byte groß, so groß.
Ein ganzes Byte, nicht 16, 32, ein Byte.
Also, einfacher wäre es noch, wenn wir einen Cache-Speicher mit nur
zwei Zeilen haben vielleicht, oder eine einzige Zeile.
Was wäre das?
So ein Cache-Speicher zum Beispiel mit von mir aus vier Bytes, aber
eine einzige Zeile.
Lohnt es sich, sowas zu machen?
Hinten?
Guck mal in Google, ob das...
Kannst du mal vielleicht gucken, ob man sowas bauen kann oder ob es
sinnvoll ist, das zu machen?
Ob man einen Cache-Speicher mit einer einzigen Cache-Zeile, zum
Beispiel vier Bytes...
Wie bitte?
Das weiß Google nicht, oder?
Weißt du es vielleicht?
Nein, okay.
Gut, also, das ist hier die Erklärung.
Es gibt immer viel Text dabei.
Also, DM ist Direct-Mapped-Cache, A2 Zweifach-Assoziativ, AV ist Voll
-Assoziativ und bei den Cache-Speichern A2 und AV soll die LRU
-Ersetzungsstrategie verwendet werden.
Nehmen Sie an, die Cache-Speicher seien zu Beginn leer und es soll
eine Serie von einzelnen Bytes mit den folgenden 32-Bit-Adressen
gelesen werden.
So, die Adressen sind hier in dezimaler Schreibweise angegeben und wir
müssen wissen, wo diese Adressen in den Cache-Speichern abgebildet
werden.
Zum Beispiel bei dem Direct-Mapped-Cache, auf welche Zeile die 9, die
32, die 13 usw.
kommt oder bei dem A2-Cache, in welchem Satz praktisch die 9, die 42,
die 13 usw.
kommt.
Geben Sie für alle drei Cache-Speicher an, wie viele Bits zur
Verwaltung eines Cache-Blocks benötigt werden.
Dabei sollen für den Zustand des Cache-Blocks zwei Status-Bits
verwendet werden.
Das ist klar, die Bits, die man braucht, um einen Block verwalten zu
können, ist immer die Länge von dem Tag plus die Anzahl der Status
-Bits.
Das heißt, wir müssen ermitteln, wie viele Bits aus dem 32-Bit-Adresse
tagged sind bei den einzelnen Cache-Speichern.
Das machen wir ganz schnell, voll assoziativer Cache.
Alle 32 Bits sind eigentlich hier tagged, weil wir nichts brauchen, um
einen Byte innerhalb eines Blocks zu adressieren.
Der ganze Block ist nur ein Byte.
Bei dem Direct-Mapped-Cache haben wir vier Zeilen.
Um eine Zeile auswählen zu können, brauchen wir zwei Bits.
Also der Tag ist dann 32 minus 2.
Und bei dem A2-Cache werden je zwei Zeilen zu einem Satz gewählt.
Bei vier Zeilen haben wir also zwei Sätze.
Das heißt, wir brauchen ein einziges Bit als Satzindex.
Und somit haben wir die Anzahl der Bits hier 32 plus 2.
Also tagged die Anzahl der Bits, die zur Verwaltung notwendig sind.
Tagged plus 2 Status-Bits.
Also in dem einen Fall haben wir 34, dann 32 und dann 33.
Anzahl der Vergleicher, die man hier braucht.
Beim Voll-Assoziativ so viele Vergleicher wie Zeilen.
Also 4 beim Direct-Mapped 1, bei A2 2.
So.
Geben Sie für die drei Cache-Speicher die Anzahl der erforderlichen
Vergleicher und jeweils zu vergleichen die Bit-Anzahl.
Anzahl der Vergleicher habe ich ja schon gesagt.
Also die Bit-Anzahl, die ist immer die Tag-Länge.
Also 32, 30 und 31.
Geben Sie nun tabellarisch für jeden Cache-Speicher an, ob es sich
beim Lesezugriff auf die jeweiligen Adressen, auf die jeweilige
Adresse um einen Cache-Hit oder um einen Cache-Miss handelt.
So, das heißt, wir müssen hier zunächst mal, fangen wir mal mit dem
Direct -Mapped Cache, und wir müssen halt hier wissen, wo wird jetzt
hier das Datum mit der Adresse 9 in den Cache landen.
Wo kann das sein?
Also auf welcher Zeile wird das Datum mit der Adresse 9 abgebildet?
Auf welcher Zeile das Datum mit 42?
Und hier haben wir ja unsere Blocknummern eigentlich.
Die Blocknummern, die sind ja die Adresse.
Das ist immer der Tag bei dem vollassoziativen Cache, weil da müssen
wir ja nichts davon abschneiden.
Das heißt, diese Blocknummern sind identisch mit der Adresse, und die
Zeilennummern können wir über diese Vorschrift Blocknummer Modulo
Zeilenanzahl bestimmen.
Das heißt, wir haben vier Zeilen im Cache.
Wir nehmen die Adressen, also unter der Bedienung hier, dass die
Adresse hier gleich mit Blocknummer ist.
Was funktioniert bei AV?
Das funktioniert bei allen.
Es geht darum, dass ich die Blocknummer zunächst mal bestimme.
Und die Blocknummer, die ist unabhängig von dem Cache.
Die hängt davon ab, wie viele Bytes innerhalb von diesem Block sind.
Das heißt, wenn der Cache mit Blöcken der Größe von 16 Bytes geladen
wird.
So, was bedeutet das?
Das bedeutet, die ersten vier Bits der Adresse, die dienen
letztendlich dazu, um ein Byte von diesen 16 auszuwählen.
Und der Rest ist immer die Blocknummer.
Und hier haben wir, das ist meine Befurchtung, dadurch, dass wir nur
ein einziges Byte haben im Block, haben wir die gesamte Adresse, die
ist der Blocknummer.
Wir können nichts davon abschneiden, weil, das habe ich ja vorher
schon erzählt.
Das heißt, wir können hier die Zeilennummern bestimmen.
Die 9 wird auf Zeile 1 abgebildet, 42 auf 4, 13 auf 1, 9 auf 1 und so
weiter und so fort.
Und nun gucken wir mal, wie das Ganze hier funktioniert bei dem Direct
Map Cache.
Das heißt, die 9 kommt zunächst mal in Zeile 1, 42 in 2, 13 in 1, da
wird die 9 überschrieben.
Klar, obwohl noch Platz da ist, aber so muss es ja sein.
Dann kommt der Zugriff wiederum auf 9.
Das heißt, 9 wird in den Cache wieder geholt, die 13 wird
überschrieben.
Dann kommt die 23 auf Zeile 3, die 12 in Zeile 0, dann die 13 wiederum
in Zeile 1 und überschreibt die 9 von vorher.
Und anschließend die 42 in Zeile 2, die 42 ist aber dort.
Das heißt, hier hat man bei diesem Zugriff einen Hit.
Das heißt, insgesamt haben wir hier bei den ersten Zugriffen immer
einen Miss, bis auf den letzten, wo wir halt einen Hit bei dem Zugriff
auf die Adresse 42 haben.
Wie sieht das Ganze bei dem vollassoziativen Cache aus?
Naja, hier ist nichts zu ermitteln.
Keine Zeilennummer, keine Satznummer.
Das heißt, die 9, die Datum mit der Adresse 9 wird in Zeile 0 geladen.
Zeile 0, der Speicher ist noch leer, das heißt, da wird noch nichts
dort überschrieben oder so.
Dann kommt die 42 in Zeile 1.
Anschließend die 13, ja, im nächsten freien Platz, also 13.
Und dann kommt die 9 jetzt.
Die 9 ist aber im Cache vorhanden.
Das heißt, hier hat man einen Hit.
Und nach der 9 kommt jetzt die 23 in den nächsten freien Platz im
Speicher.
So, was kommt jetzt?
Die 42.
Jetzt haben wir das Problem, dass der Cache-Speicher voll ist.
Das heißt, hier muss die Entscheidung jetzt gefällt werden, welcher
Block bei einem neu in den Cache zu ladenden Block aus dem Cache
verdrängt werden muss.
Also wenn es bei dem nächsten Zugriff keinen Hit gibt, also wenn es
einen Hit gibt bei dem nächsten Zugriff, wenn das zum Beispiel ein
Zugriff auf 13 und 13 ist im Cache, dann muss nichts verdrängt werden.
Aber wenn es jetzt ein anderes Datum wie 42 zum Beispiel oder wie
12...
12 muss jetzt in den Cache, ist noch nicht im Cache, das heißt, wir
müssen etwas...
Das war doch zu schnell, oder?
Moment, Entschuldigung.
Nee, das war richtig.
So, die 12, die muss jetzt in den Cache rein.
Und es handelt sich bei diesem Zugriff nicht um ein Hit.
Das heißt, irgendwas muss aus dem Cache rausfliegen.
Und nach dem LRU-Ersetzungsstrategie fliegt jetzt was raus, fliegt das
Datum raus, auf dem der Zugriff am längsten in der Vergangenheit
zurückliegt.
Das heißt, zuletzt hatten wir Zugriff auf 23, dann vorher auf 9,
vorher auf 13, also die 42 muss raus.
Und die 42 fliegt raus, dann kommt der Zugriff auf 13.
13 ist aber hier vorhanden, das heißt, wir haben hier ein Hit.
Anschließend Zugriff auf 42.
Und hier muss natürlich entschieden werden, was verdrängt werden soll.
Also, das war noch am aktuellsten, das war davor, das war davor.
Das heißt, hier in dem Fall muss die 9 hier rausfliegen in der Zeile 0
und die 42 muss dorthin geladen werden.
So, wie sieht es aus bei dem A2-Cache?
Bei dem A2-Cache müssen wir die Satznummer bestimmen.
Satznummer ist Blocknummer Modulo 2 bei zwei Sätzen.
Blocknummer ist identisch mit der Adresse, das heißt, die Satznummern
sind hier dargestellt.
Das heißt, 9 kommt in Satz 1, das heißt auf Zeile 2, 42 in Satz 0,
dann 13 in Satz 1, überschreibt die 9 nicht, weil es gibt noch hier
Platz in Satz 1.
Die 9 kommt, Entschuldigung, 9 in Satz 1.
Jetzt haben wir einen vollen Satz.
Der Satz 1 ist voll.
Wenn jetzt ein neuer Zugriff kommt, und zwar, das ist der Zugriff auf
9, und da muss irgendetwas aus Satz 1 verdrängt werden.
Eventuell, wenn es kein Hit ist, dann müssen wir entscheiden, welches
Datum.
9 oder 13, dann können wir gucken, zuletzt wurde er auf 13, 42, nee,
42 nicht, 13 und vorher auf 9, dann ist es klar, dass die 9
rausfliegen muss, aber wir haben bei dem nächsten Zugriff hier einen
Hit auf die 9, das heißt, noch nicht so dramatisch, aber bei der 32,
nee, 42, das wird auf Satz 0 oder kommt in Satz 0, das war jetzt ein
bisschen zu schnell, so, die 9,
also, nochmal.
So, 9, 42, 13, Hit 9.
Dann, 23 überschreibt die 13 in Satz 1, 12 kommt in Satz 0, 13 wird
jetzt in Satz 1 geladen, in Satz 1 müssen wir jetzt etwas verdrängen,
wir haben ja hier zuletzt auf die 23 zugriffen und vorher auf die 9,
das heißt, wir müssen die 9 rausschmeißen und da kommt die 13 rein und
jetzt die 42 in Satz 0, 42 ist dort vorhanden, das heißt, wird nichts
verdrängt und deshalb haben wir hier auch ein Hit, das heißt,
insgesamt haben wir zwei Hits.
Ist das klar?
Gut, dann geht es jetzt noch schneller.
Aufgabe 4.
Gegeben sei eine Programmschleife zur Multiplikation von 512 Zahlen,
die jeweils 16 Bit breit sind, also von 512 16 Bit Zahlen, vor 0
gleich 1, j gleich 0, j kleiner als 512, j plus plus 0 ist gleich
Stern 0 mal g von j.
So, ein vollassoziativer Daten-Cache-Speicher sei zunächst leer, mit
64 Bytes pro Cache-Zeile.
Okay?
Wir wollen hier, das bedeutet, wenn wir jetzt ein Datum, eine Zahl in
den Cache-Speicher laden, eine Zahl ist 16 Bit breit, also 2 Bytes,
dann wissen wir, dass der Cache nicht nur mit dem Datum geladen wird,
sondern mit dem ganzen Block, in dem dieses Datum liegt.
Das heißt, wenn wir jetzt auf die Zahl g0 zugreifen, auf die erste
Zahl, die wir mit 0,1 multiplizieren wollen, dann laden wir nicht nur
die erste Zahl, sondern wir laden insgesamt 64 Bytes in den Cache
-Speicher, in die erste Zeile von dem vollassoziativen Cache-Speicher
und somit haben wir die nächsten 32 Zahlen im Cache-Speicher.
So, ist das klar?
Das heißt, um alle Zahlen, um auf alle 512 Zahlen zugreifen zu können,
brauchen wir eigentlich, wie oft auf den Hauptspeicher zuzugreifen.
Beim ersten Mal, wenn wir die erste Zahl geladen haben, haben wir ja
die nächsten 31 Zahlen schon drin.
So, wir haben 512, also 512 durch 32, das ist 2 hoch 9 durch 2 hoch 5,
also das ist 2 hoch 4, insgesamt 16 Mal.
Das heißt, mit 16 Zugriffen haben wir eigentlich alle Zahlen, die
multipliziert werden müssen, in den Cache-Speicher geladen.
Nehmen wir mal an, dass die Ausführung von dieser Schleife auf diese
Art und Weise erfolgt.
Das heißt, hier werden die Variablen initialisiert, dann hat man
irgendeine Schleife, wo diese Zählvariable gelesen werden, dann wird
eine Zahl hier gelesen, also g von 0 zunächst mal, dann wird diese
Variable gelesen, multipliziert, Ergebnis geschrieben, nochmal j
gelesen, inkrementiert, geschrieben und dann hier gesprungen.
Dann ist es klar, dass man zunächst mal hier zwei Fehlzugriffe hat,
anschließend hat man hier ein Hit, weil j ja schon in den Cache
geladen wurde, und dann hat man hier bei dem ersten Zugriff auf die
Zahlen, die miteinander zu multiplizieren sind, ein Miss.
0 ist schon im Cache-Speicher, das heißt, bei dem nächsten Lesezugriff
hat man ein Hit, Multiplikation wird ausgeführt, es wird hier
geschrieben, also ein Right Hit, dann wird j gelesen, j ist da, also
ein Read Hit, hier wird j nochmal geschrieben, also auch ein Right
Hit, und dann springt man wieder dorthin.
Was passiert beim zweiten Durchlauf?
Eigentlich hat man hier nochmal ein Hit, hier hat man kein Miss, weil
nicht nur die Zahl g 0, sondern g 1 und g 2 bis g 31 ist schon im
Cache, das heißt, hier hat man auch ein Hit und die restlichen Sachen
sind auch Hits.
Und wenn man das Ganze hier dritter, vierter, fünfter, das heißt, hier
beim 31.
Durchlauf wird man nochmal auf eine Zahl, die im Cache vorhanden ist,
zugreifen.
Beim 32.
Durchlauf wird man einen neuen Block aus dem Hauptspeicher holen und
insgesamt muss man halt bei 512, also bei 512 Zahlen Blöcke von 64
Bytes insgesamt 16 Mal eigentlich auf den Speicher wie wir das
berechnet haben, zugreifen, um alle Zahlen in den Cache Speicher zu
laden.
Wenn man das Ganze hier auswertet, dann bekommt man hier also Anzahl
der Miss-Zugriffe, Hits und Misses, Fehlzugriffe und erfolgreiche
Zugriffe, dann kommt man hier auf diese Raten, die angegeben sind.
Gut, Aufgabe 5.
Bei einem Cache Speicher mit einer Speicherkapazität von 128 Kilobyte
ist die Hauptspeicheradresse in ein 16-Bit-Tag-Feld, ein 12-Bit-Index
-Feld und ein 4-Bit-Byte-Offset-Feld unterteilt.
Bestimmen Sie die Blockgröße in Bytes.
Wie viele Einträge besitzt der Cache Speicher?
Wie ist der Cache Speicher organisiert?
Das heißt, wir wissen nicht, ob der Cache Speicher jetzt
vollassoziativer Cache Speicher ist oder Direct-Mapped A2, A8, A4, A16
und so weiter und so fort.
Was hat man hier an Informationen?
Man hat hier die Speicherkapazität 128 Kilobyte.
Die Hauptspeicheradresse ist unterteilt in einem Tag-Feld.
Das sind 16-Bit-Tag.
Ein Index 12-Bit.
Wir wissen nicht, ob das ein Zeilen- oder ein Satzindex ist.
Aber alleine, dass es hier einen Index gibt, besagt, dass der Cache
Speicher auf gar keinen Fall als vollassoziativer Speicher organisiert
sein kann.
Das heißt, es ist entweder ein Direct-Mapped-Cache oder ein
teilassoziativer Cache Speicher.
Und 4-Bit hier sind Offset.
Die erste Frage, bestimmen Sie die Blockgröße in Bytes.
Vorschläge?
16.
Wer ist vor 32?
Wie berechnet sich die 16?
Woher kam die Wortmeldung jetzt?
16.
8 plus 8?
2 hoch 4, ganz genau.
Also Byte-Offset, das ist, was wir heute gesehen haben in den
Aufgaben, das waren immer diese 2-Bit z.B.
bei unseren Aufgaben, um ein Byte im Wort zu wählen und 1-Bit, um ein
Wort in diesem 8-Byte-großen Block auszuwählen.
In dem Fall haben wir hier ein Byte-Offset von 4-Bit.
Das heißt, die Blockgröße ist 2 hoch 4, ist gleich 16 Bytes.
So, die 4 hier ist die.
Okay.
Wie viele Einträge besitzt der Cache-Speicher?
So, ja.
8 Kilo.
Andere Vorschläge?
Wie bitte?
4096, das ist wie viel?
Das ist 2 hoch 12.
Das gefällt mir.
Das gefällt mir, weil das ist genau, worauf ich hinaus wollte.
Das ist falsch nämlich.
So.
Warum ist das falsch?
Euer Kollege hat diese 12-Bits genommen, hat gesagt, ich habe ein
Index -Welt von 12, also wie viele Einträge, 2 hoch 12, wollte das
Leben ein bisschen für mich schwieriger machen, hat gesagt 4096.
Okay.
Was hat er hier missachtet bei seiner Vorgehensweise?
Ja?
Genau, er hat angenommen, dass der Cache als Direct-Map-Cache
organisiert ist.
Und dann würde das stimmen.
Aber, ich werde dir zeigen, dass das nicht der Fall ist, weil die
Anzahl der Einträge im Cache ist letztendlich Cache-Kapazität durch
Blockgröße.
Das heißt, die Cache-Kapazität ist
128 Kilobyte.
Die Blockgröße ist 16 Byte.
Das heißt, hier haben wir, kürzen wir mal Byte und Byte, dann haben
wir 2 hoch 7 durch 2 hoch 4, also 2 hoch 3.
Das sind 8 K.
8 K sind also 2 hoch 13.
Und 2 hoch 13 ist, soweit ich weiß, ungleich 2 hoch 12, was du da
gemeint hast.
So, das heißt, wir haben 2 hoch 13 Einträge, wir können 2 hoch 13
Blöcke in den Cache laden, die jeweils 16 Byte groß sind, aber wir
haben eigentlich ein Indexfeld, mit dem wir nur 2 hoch 12 adressieren
oder auswählen können.
Also, wie ist der Cache organisiert?
Zweifach-Assoziativer Cache-Speicher.
So, haben das alle verstanden?
So, das haben wir erledigt, also Blöckgröße 16 Byte.
128 Kilobyte durch 16 Byte.
Und dann, was hatten wir noch hier?
Anzahl der Cache-Einträge ist 128 Kilobyte, also durch Blöckgröße 16
Byte.
Ist gleich 2 hoch 13.
Und die Organisation, wir haben ja ein Indexfeld von 12 Bits, das
heißt, damit können wir 2 hoch 12 Sätze eigentlich, weil Zeile ist ja
ein Spezialfall von Satz, nehmen wir mal so.
Das heißt, hier haben wir 2 hoch 13 Einträge und 2 hoch 12 Sätze, also
das heißt, es ist 2, daraus folgt, wir haben ein A2-Cache.
Nächste Aufgabe.
Es soll ein dreifach-assoziativer Cache-Speicher mit 128 Sätzen.
Was bedeutet dreifach-assoziativ?
Gibt es sowas?
Oder sind das immer 2-fach, 4-fach, 8-fach?
Also gibt es oder gibt es nicht?
Nee, gibt es nicht.
Wer meint, es gibt sowas?
Kennst du einen?
Wie bitte?
Es braucht keinen Mensch.
Also ich kann dir Beispiele für ein 7-fach-assoziativer Cache-Speicher
nennen.
So, also, dreifach bedeutet, dass wir Sätze haben und in jedem Satz
haben wir 3 Zeilen.
Wir haben 128 Sätze, Blockgröße von 8 Bytes.
Nehmen Sie an, die Hauptspeicheradresse sei 32 Bit breit.
Zur Verwaltung von einem Cache-Block werden zusätzliche 2 Status-Bits
benötigt.
Und bestimmen Sie den insgesamt erforderlichen Speicherbedarf zur
Realisierung dieses Cache-Speichers.
Nochmal hier die Bemerkung, ein Cache-Speicher besteht aus einem
Adressteil, 2 Status-Bits und einem Datenteil.
Der Datenteil,
wissen wir nicht, wie groß, was uns interessiert, ist der insgesamt
erforderliche Speicherplatz, um alles hier zu realisieren.
Das heißt, um diesen Adressspeicher, die Status-Bits und den Datenteil
hier zu realisieren.
Wir wissen, dass wir hier 128 Sätze haben.
Jeder Satz hat 3 Zeilen, also insgesamt haben wir 128 mal 3 Zeilen und
jede Zeile ist 8 Bytes groß.
Das heißt, dieser Datenbereich ist dieser Datenbereich hier
dieser Datenbereich ist wie groß?
128 Sätze mal 3 das sind dann die Anzahl der Zeilen mal 8 weil jede
Zeile 8 Bytes groß ist.
Das heißt 8 Bytes.
Was wir noch ermitteln müssen, ist, wie viel Platz, wie viel
Speicherbedarf brauchen wir für diesen anderen Teil.
Wir wissen, dass hier der Tag gespeichert wird.
32-Bit-Hauptspeicheradresse
Blockgröße 8 Byte das heißt, 0, 1 und 2 sind für die Byte-Adressierung
zuständig 128 Sätze, das heißt, wie viele Bits brauchen wir, um einen
Satz auszuwählen?
7 das heißt, 3, 4, 5 6, 7, 1, 2, 3, 4, 7 8, 9, das ist hier Satz-Index
das ist Byte-Offset und der Tag ist dann in dem Fall also Tag-Länge
ist wie viel?
Schreiben wir mal hier Tag ist gleich 30, 32-10 also 22 Bits So, wie
viel brauchen wir davon?
Also wir brauchen 22 Bits Tag plus pro Zeile, plus 2 Bits für Valid
und Derity also 24 Bits das sind 3 Bytes pro Zeile und wie viele
Zeilen haben wir?
Also 3 mal 128 mal 3 also 128 Sätze haben wir und in jedem Satz haben
wir 3 Zeilen Byte Das ist der Speicherbedarf, der notwendig ist um den
Teil hier zu realisieren und der insgesamt erforderliche
Speicherbereich, den man hier braucht, ist die Summe von der beiden.
Gut, ich bedanke mich für die Aufmerksamkeit das war es für heute, ne,
ne, ne doch schon, das war die Folie die ich vorbereitet habe, bedanke
mich doch für die Aufmerksamkeit und möchte die Leute bitten, die
keinen Zettel haben für diese Befragung, nochmal hier einzunehmen.