Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
klausur-gra-2010-02-15 Aufgabe 9!
Bei der letzten Klausur, Aufgabe 9, Unteraufgaben 3 und 4:
Verständnisfrage:
Aufgabe 3) ohne Caches
Ein Befehl soll 1 Nanosekunde zur Bearbeitung benötigen. Ein Hauptspeicher- zugriff dauert 100 Nanosekunden. Jeder Befehl soll mit einem Speicherzugriff geladen werden ko ̈nnen.
Beispiel 1:
movl $0, %eax => t=201, da Befehl laden = Speicherzugriff, %eax = Speicherzugriff (zählt, dass auch als Speicherzugriff, obwohl Register?) + Ausführung
Beispiel 2:
addl 4(%ebx), %ecx => t=401, Befehl laden, Indirekter Speicherzugriff=200 4(%ebx), Speicherzugriff %ecx + Ausführung
Aufgabe 4) mit Caches
DerProzessor soll nun über einen ausreichend großen Primär-Cacheverfügen, um sämtliche Befehle und Daten des Programms zwischenzuspeichern. Ein Zugriff auf diesen Cache benötigt 5 Nanosekunden. Urspru ̈nglich sei der Cache leer. Die Schreib-Strategie sei ,Write-Through”. Wie lange beno ̈tigt das Programm nun?
(alles erster durchlauf der Schleife)
Beispiel 1:
ändert sich nicht
Beispiel 2:
4(%ebx) = 10ns, %ecx 5 ns, 1ns Ausführung + 100ns Befehl holen
Also stimmt der Ansatz?
Und was genau bedeutet Write-Through:
Ich veränder eine Variable, die wird automatisch auch
im Speicher (+cache) geändert!
Muss ich warten mit dem nächsten Befehl, bis es im Speicher
geschrieben worden ist, oder geschieht das “im Hintergrund”?
Also erstmal gibt es bei einem Register keinen Speicherzugriff, also hast du für die Befehle 1-4:
4xBefehl holen (=Speicherzugriff), 4xBefehl ausführen (1 ns) und 2x Speicherzugriff (zusätzlich, da du auch die Adressen 2000 und 2004 zugreifst)
Bei dem addl 4(%ebx), %ecx schaut das meiner Meinung nach so aus:
Also wie oben erstmal 1x BH und 1xBA
Du greifst einmal auf den Speicher zu, um zu sehen, was bei der Adresse in %ebx steht (+ 1x100ns), was dann 100+1+100 macht.
Bei movl %ecx, 8(%ebx) hättest du dann ganz am Schluss z.B. nochmal einen Speicherzurgiff zusätzlich, um das Ergebnis wieder in die Speicherstelle zurückzuschreiben (Bei AT&T steht ja das Ziel rechts)
Beim Cache ist das denk ich so:
Zeilen 1-4 und der erste Schleifendurchlauf gleich (muss ja erstmal alles rein geschrieben werden)
Bei den nächsten ändert sich folgendes:
du holst jeweils den Befehl diesmal aus dem Cache und hast normal dein Befehl ausführen. Dann hast du aber noch in der ersten Zeile einen Speicherzugriff, da sich der Inhalt von %ebx in Zeile 4 des loops verändert hat. In Zeile 3 des loops wird jeweils (write-through) der neue Wert sofort in die Speicherstelle bei %ebx+8 reingeschrieben, was wieder einen Speicherzurgiff ausmachen müsste.
Also so versteh ich das, wie gesagt, verbessert mich, wenn das Unsinn ist ^^
Dann hab ich gleich noch ne Frage: weiß jemand, wie die Aufgabe 5 gehen soll:
Ein ,Direct mapped"-Cache habe die Größe 2^20 Bytes. Die Adressen im Rechner seinen 32 Bit groß. wie groß müssen die Tag-Felder im Cache sein?
Zugriffe auf Register sind keine Speicherzugriffe, das würde ja dann den Witz des schnellen Registers versauen 
Also ist Beispiel 1: 100 (BH) + 1(BA) = 101ns
und Beispiel 2: 100(BH) + 1(BA) + 100(OH) = 201ns
Mit Cache:
- is klar
- Wenn du den Wert an 4(%ebx) schon mal benutzt hast, dann kommen hier 100(BH) + 1(BA) + 5(OH-Cache) = 106ns raus
Write-Through bedeutet, dass du wenn ein Wert sich ändert, diese Änderung nicht nur im Cache schreibst, sondern gleich auch in die nächste Hierarchiestufe → hier den Speicher.
Also hast du (wahrscheinlich) 105ns für’s Zurückschreiben, 100 wegen Speicher, 5 für Cache.
Hier wird ja eh nie “Hintergrund” angenommen, also denke ich schon, dass man warten muss, also diese 105 eben als Zeit draufaddieren muss
Die Antwort auf Bommls Frage ist ab hier schon diskutiert worden 
Oh thx, das hab ich voll übersehen 
Ich hab mal noch ne Frage zur Teilaufgabe 3.4)
An sich ist das Alignment schon alles klar, nur hab ich (wieder mal ^^) ein Problem mit der Formulierung.
Hier steht ja “Wieviel Speicherplatz braucht ein Datensatz mit korrektem Alignment auf einem 32-Bit-Rechner, der folgende Daten (in dieser Reihenfolge) enthält.
*3 16-bit Zahlen
*2 32-bit Zahlen
*1 8-bit Zeichen
Wieviel Speicherplatz benötigt ein Array bestehend aus 10 solcher Datensätze?
Die erste Zahl des Datensatzes liege jeweils an einer durch 4 teilbaren Adresse.”
Bezieht sich das nun auf jeden Datensatz innerhalb des Arrays, oder beginnt der eine Datensatz an einer solchen Adresse, und das Array (nicht aber jeder einzelne Datensatz im Array)?
Je nachdem, wie man es auffasst, kommt was anderes raus
Das bezieht sich auf jeden Datensatz im Array, nicht nur auf den allerersten.
hab hier mal ne Lösung zu der Cache Aufgabe
[color=limegreen]vor der Schleife:
101ns
201ns
201ns
101ns
1.Durchlauf:
106ns - Befehl 100 Speicherstelle 2000 ist im Cache von “vor der Schleife” ->5ns + ausführen
106ns - wie oben nur mit 2004
311ns - Befehl 100 + aus Speicher holen 100 ausführen 1 + zurückschreiben + Cache (105??? evtl auch nur 100, aber geh jetzt davon aus, dass der Wert im Cache und im Speicher nicht nebenläufig geändert werden)
101ns
101ns
101ns
101ns - jeweils befehl holen und ausführen
andren 10durchläufe:
11ns - befehl + speicherstelle aus cache 10 + 1ausführen
11ns
211ns - befehl aus cache 5 + ausführen 1+ speicherzugriff lesen 100 + rückschreiben 105
6
6
6
6 - befehl aus cache + ausführen[/color]
was sagt ihr dazu? Ich hoffe ich blamier mich mit dem Vorschlag hier nicht
Fast richtig, nur beim [m]movl %ecx, 8(%ebx)[/m] vertust du dich: Die [m]mov[/m]-Instruktion mit einer Speicheradresse als Zieloperand schreibt immer in diese Speicherzelle, ohne sie vorher zu lesen (wozu auch?).
Und wenn wie von dir vorgeschlagen beim “Write-Through” der Cache-Zugriff und der Speicherzugriff sequenziell erfolgen, musst du die 5 ns auch bei allen anderen Schreiboperationen draufschlagen. Wobei die Aufgabenstellung meiner Meinung nach offen lässt, wie das zu interpretieren ist.
okay, leuchtet mir ein. Ich glaub ich ging iwie von einem add %… aus. Hoffe nur sowas passiert mir Mittwoch nicht :nuts:
Hab ne Frage zur Aufgabe 7:
Aufgabe 7: Zwei-Adress-Code (10 Punkte)
Vereinfachen Sie das folgende Code-Stuck fur eine Zwei-Adress-CPU!
Benutzen Sie nur
� if-then-goto-Anweisungen mit einfachen Bedingungen
� goto-Anweisungen
� Funktionsaufrufe der Form result = function(param1, …, paramN);
� Zuweisungen der Form
{ var = operand;
{ var = var operand;
(binop ist Element von f+;???; �; =; <; >; :::g, var ist eine Variable, operand
kann eine Variable oder eine Konstante sein).
val = 0;
c = fgetc(fp);
while (‘0’ <= c && c <= ‘9’) {
val = val * 10 + c - ‘0’;
c = fgetc(fp);
}
Meine Lösung wäre jetzt:
val=0;
c=fgetc(fp);
goto loop_condition;
loop_body:
val =val*10+c-´0´
c=fgetc(fp);
loop_condition:
if(´0´>c) goto end;
if(c<=´9´) goto loop_body;
end:
…
Aber ich denke, dass ich da irgendwas übersehen hab, immerhin gibts da ja 10 Punkte auf die Aufgabe. Muss ich da noch irgendwas besonders auflösen, oder so?
[color=limegreen]val = val * 10
val = val + c
val = val - ‘0’[/color]
var = var operand;
Ah ok, danke (wobei ich trotzdem finde, dass 10 Punkte ziemlich viel dafür sind ^^)
Dachte ich mir auch ^^ ~1 Punkt pro Zeile … das haut schon irgendwie hin xD
Na da kann man dann schön Punkte sammeln
Noch eine Verständnisfrage!
movl $1, 2000
klar, 100 BH, 1ns zum Ausführen
damit ich weiß was in 2000 ist (also wenn es in den Cache geschrieben worden ist) muss
ich doch noch 5 ns draufschlagen um es in den Cache zu schreiben oder nicht?
Nö, der Wert wurde schon vor der Schleife in den Cache geschrieben → Du musst nur noch auslesen
movl $1, 2000 100 Befehl holen
+ 1 ausführen
+ 100 Ergebnis in Speicher schreiben
+ 5 Ergebnis in Cache schreiben
-----
= 206Kann sein, dass du dich in der Zeile vertan hast.
ja der movl befehl war gemeint vor der schleife
nur innerhalb greif ich ja auf die speicherzelle 2000, deshalb das zitat!
Aufgabe 9.5) Ein “Direct-Mapped”-Cache habe die Größe 2^20 Bytes. Die Adressen im Rechner seien 32 Bit groß. Wie groß müssen die Tag-Felder im Cache sein?
Ich versuch’s mal:
[Eine Cache-Zeile sei 2^X Bytes lang, damit ergeben sich 2^20 / 2^X Zeilen bzw. 2^Y mit Y = 20 - X.
D.h. mit den hintersten X bits einer Adresse adressiert man die Bytes innerhalb einer Zeile,
mit den nächsten Y bits einer Adresse wählt man die Zeile aus (“Index”-Teil der Adresse)]
Unabhängig von der Länge einer Cache-Zeile sind somit die letzten 20 Bit einer Adresse implizit allein durch die Position der Daten im Cache gegeben und es reichen die verbleibenden 12 Bit der Adresse aus um die zugehörige Speicheradresse der Daten zu ermitteln
Länge Tag-Felder: 12 Bit