C-Programme und CPU

Tobiking2

Was habt ihr denn unter "einfache Sprungvorhersage" definiert? Ich würde jetzt auf Anhieb eine einstufige History vermuten. Wenn ein Sprungbefehl ausgeführt wird, merkt man sich ob der Sprung genommen wurde oder nicht. Möchte man nun eine Voraussage treffen, ob der Sprung beim nächsten Mal genommen wird, schaut man sich an was beim letzten mal war. Das klappt gut bei Schleifen mit vielen Iterationen, da man immer wieder davon ausgeht das der Schleifenrumpf ausgeführt wird und damit richtig liegt.´

Den Rest solltest du selber herausfinden.

knivil

Zu 4.) Nun, Programm A wird mehr Fehler bei Sprungvorhersage machen, da die Alternative von (i & 1) genauso wahrscheinlich ist.
Zu 5.) Wahrscheinlich Programm B, da die Kosten fuer Cachemisses (alle 31 Schleifendurchlaeufe 5 Zyklen mehr) im Vergleich zu 20 Zyklen pro Schleifendurchlauf wesentlich geringer ist.

PS: Was in deinem Fall Sprungvorhersage und Pipline bedeutet, weiss ich nicht. Unklar ist ebenfalls, ob ein Cache von 500 KByte relevant ist.

Also erstmal dazu, warum der Cache von 500 KB relevant ist.

500 KB sind 512.000 Byte. Da eine Zeile 64 Byte lang ist gibt es 8000 Zeilen.

x hat 1mio. Byte.
Programm A: Es werden 8000 mal 64 Byte geladen dann habe ich knapp die Hälfte und es fängt wieder von vorne an. Ich habe also insgesamt 15.625 Ladevorgänge = Misses

Programm B: Nach dem ersten Durchlauf gab es 500.000 Aufrufe. Dann stehen im Cache die letzten 8000 * 64 Byte = 512.000 Byte von x und ich habe bis dahin schon 500.000 / 32 = 15.625 Ladevorgänge = Misses gehabt.

Beim zweiten Durchlauf muss also wieder jede Zeile neu geladen werden uns es kommen weitere Misses dazu. Wenn der Cache so groß gewesen wäre, dass ganz x Platz gehabt hätte dann müsste beim zweiten Durchlauf nichts mehr geladen werden und die Anzahl der Misses und Hits wäre bei Programm A und B gleich gewesen.

Pipeline bedeutet, dass der Prozessor für jede Instruktion beispielsweise 5 Schritte braucht.
Hat er dann Schritt 1 für Instruktion 1 erledigt macht er mit Schritt 2 weiter und beginnt gleichzeitig mit Schritt 1 für Instruktion 2.

Was mit einfacher Sprungvorhersage gemeint ist weiß ich auch nicht. Das Wort kam in der gesamten Vorlesung nicht vor

knivil

Also erstmal dazu, warum der Cache von 500 KB relevant ist.

Rechnen kann ich alleine. Aber macht es einen Unterschied, ob ich 500K oder nur 64K habe. Natuerlich aendern sich die Zahlwerte, aber nach diesen wird nicht gefragt, zumal die exakte Anzahl noch von mehreren Faktoren abhaengt, bspw. Hilfsvariablen, Schleifenindex etc. muessen auch in den Cache.
Btw. wird hier Assembler/Maschinencode mit C-Code verglichen, wahrscheinlich wuerde der Compiler sowas generieren:

for(i=0;i<1000000;i+=2) { 
    gerade += x[i]; 
    ungerade += x[i+1]; 
}

knivil schrieb:

Zu 4.) Nun, Programm A wird mehr Fehler bei Sprungvorhersage machen, da die Alternative von (i & 1) genauso wahrscheinlich ist.
Zu 5.) Wahrscheinlich Programm B, da die Kosten fuer Cachemisses (alle 31 Schleifendurchlaeufe 5 Zyklen mehr) im Vergleich zu 20 Zyklen pro Schleifendurchlauf wesentlich geringer ist.

PS: Was in deinem Fall Sprungvorhersage und Pipline bedeutet, weiss ich nicht. Unklar ist ebenfalls, ob ein Cache von 500 KByte relevant ist.

Zu 4.) Das verstehe ich noch nicht ganz.
Nachdem ich mich im Netz ein bisschen eingelesen habe vermute ich, dass es sich um eine statische Vorhersage handelt. Bei Programm A könnte er zwar immer zurückspringen und den Befehl nehmen, aber es wäre immer falsch. Wenn er vorwärtsspringen würde dann wüsste er nie welchen Befehl er nehmen muss weil die Wahrscheinlichkeit für if und else gleich ist.

Bei Programm B könnte er durch die Gleichheit der Befehle in den einzelnen for-Schreiben sehr gut entweder den letzten oder nächsten Befehl nehmen.

Deswegen würde A mehr Fehler verursachen und zwar vermutlich im Wechsel bei den Anweisungen
gerade += x[i] und
ungerade += x[i]
weil er immer das jeweils andere vorhersagen würde.

Ist das richtig?

knivil

Ist das richtig? Keine Ahnung, vielleicht sagst du mir einfach worin der Unterschied zwischen deiner und meiner Begruendung ist.

Bei Programm A könnte er zwar immer zurückspringen und den Befehl nehmen, aber es wäre immer falsch. Wenn er vorwärtsspringen würde dann wüsste er nie welchen Befehl er nehmen muss weil die Wahrscheinlichkeit für if und else gleich ist.

Was ist bei dir vor bzw. zurueck?

knivil schrieb:

Also erstmal dazu, warum der Cache von 500 KB relevant ist.

Rechnen kann ich alleine. Aber macht es einen Unterschied, ob ich 500K oder nur 64K habe. Natuerlich aendern sich die Zahlwerte, aber nach diesen wird nicht gefragt, zumal die exakte Anzahl noch von mehreren Faktoren abhaengt, bspw. Hilfsvariablen, Schleifenindex etc. muessen auch in den Cache.

Vermutlich ist die Information nur für Frage 3 relevant. Und da macht es einen Unterschied ob ich 500 KB oder 1024 KB habe. Für andere Werte ist es natürlich nicht so relevant.

knivil schrieb:

Btw. wird hier Assembler/Maschinencode mit C-Code verglichen, wahrscheinlich wuerde der Compiler sowas generieren:
for(i=0;i<1000000;i+=2) { 
    gerade += x[i]; 
    ungerade += x[i+1]; 
}

Ähh...wie meinst du das, dass der Compiler sowas generieren würde?

knivil schrieb:

Ist das richtig? Keine Ahnung, vielleicht sagst du mir einfach worin der Unterschied zwischen deiner und meiner Begruendung ist.

Bei Programm A könnte er zwar immer zurückspringen und den Befehl nehmen, aber es wäre immer falsch. Wenn er vorwärtsspringen würde dann wüsste er nie welchen Befehl er nehmen muss weil die Wahrscheinlichkeit für if und else gleich ist.

Was ist bei dir vor bzw. zurueck?

Ich habe meine ausführlicher geschrieben um sicherzugehen, dass ich das was du geschrieben hast richtig verstanden habe.

Mit zurück und vorspringen meine ich, dass der Compiler so tut, als würde entweder der zuletzt ausgeführte Befehl nochmal kommen oder eine Vermutung darüber anstellt welcher der nächsten Programmteile und damit welcher Befehl als nächstes kommt. An dieser Stelle kommt dann die Wahrscheinlichkeit bei if/else ins Spiel.

SeppJ

Gedizen schrieb:

knivil schrieb:
Btw. wird hier Assembler/Maschinencode mit C-Code verglichen, wahrscheinlich wuerde der Compiler sowas generieren:
for(i=0;i<1000000;i+=2) { 
    gerade += x[i]; 
    ungerade += x[i+1]; 
}
Ähh...wie meinst du das, dass der Compiler sowas generieren würde?

Compiler haben viel Freiheit bei der Erzeugung von Code, so lange das Programm hinterher das gleiche Verhalten zeigt. Dazu gehört auch das heraus oder hinein ziehen von Code aus Schleifen, das Zusammenfassen redundanter Schleifen oder gar das vollständige Wegoptimieren von Schleifen.

Wobei die Optimierung, die knivil hier vorschlägt schon recht komplex wäre. Der GCC 4.8 bekommt sie auch tatsächlich nicht hin. Was er aber macht, ist einen Teil der Schleife abzurollen.

Und was bedeutet, dass der Compiler einen Teil der Schleife abrollt? Ich denke wir sollen schon davon ausgehen, dass der Compiler den Code so lässt, da wir uns in der Vorlesung nicht mit solchen Compiler-Interpretationen beschäftigt haben.

Ist dir Duff's Device ein Begriff? Wenn die Anzahl der Schleifendurchläufe vor Eintritt in die Schleife bekannt ist, kann der Compiler so etwas daraus bauen. Nennt sich "partial loop unrolling."

Btw: Das hat jetzt mit der Frage weniger zu tun, weil klar ist, dass Compileroptimierungen da nicht berücksichtigt werden sollen, aber es ist trotzdem ganz interessant, dass clang an dieser Stelle deutlich besser vorgeht als gcc. Clang kriegt knivils Umformung mit -O2 hin, mit -O3 erzeugt er sogar SSE-Instructions, was mich grad etwas beeindruckt.