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 11.04.2013
Da es zu dieser Klausur noch kein Thema gibt starte ich einfach mal eins.
Ich schreib auch gleich mal dazu, was ich mir so an Gedanken gemacht habe.
Freue mich über Korrekturen!
1) Assemblerprogrammierung
-
Stack malen
To be continued. -
Befehlssatzarchitektur-Klassen
a) Reg-Reg oder Reg-Mem | beliebig unterstreichen
b) Stack | sub unterstreichen
c) Reg-Mem | add R1, B unterstreichen
d) Akku | add #2 unterstreichen
2) Mikroprogrammierung
-
Wozu?
Schließung der Semantischen Lücke -
Bezug
Ein Makrobefehl besteht aus mehreren Mikrobefehlen. -
Alternative
Befehle fest in der Hardware verdrahtet. (?) -
Vorteile
Mikroprogrammierung: Speicher veränderbar
Fest verdrahtet: Schneller -
Programm Aufsummieren
Edit: Zeilen 0-indexed, A+B->D ALU auswählen
0 Eingabe → D | 9, 11
1 D → A, B | 14, 1, 2
2 A-1 → C | 5, 7
3 C → A | 13, 1
4 A+B → D | 3, 8, 11
5 A-1 → C, D->E, B | 5, 7, 12, 14, 2
6 if C>= 0 goto 3 | 17, 20, 21
7 E → Ausgabe | 16
3) Speicherverwaltung
12 Bit Offset, 10 Bit pro Tabellenhierarchie
TLB nach dem lesenden Zugriff auf die 4 Adressen. Alle sind present.
Da man nur die ersten 20 Bit zur „Page-Findung“ braucht, hab ich auch nur diese umgewandelt und dann in der Hälfte getrennt.
0x00 00 7(1 2C) => 0000 0000 00|00 0000 0111
Daran sieht man 0. Eintrag in Page Directory (1. Hierarchie-Stufe) und 7. Eintrag in der zugehörigen Page Table (2. Hierarchie-Stufe). Also auf die Page mit dem Code. Im TLB wird dann die virtuelle Adresse 0x00 00 7 und die physikalische Adresse für die Page 0x00 00 3 (und Flags 0x001) gespeichert. Im Übrigen wird nochmal auf diese Page an einer anderen Adresse zugegriffen, deshalb steht sie nur einmal im TLB.
0x00 40 3(1 F0) => 0000 0000 01|00 0000 0011
- Eintrag Page Directory und 3. Eintrag in zugehöriger Page Table. Hier muss man immer 0x1000 (4KiB = 1 Page) addieren bis man beim 3. Eintrag ist (oder gleich 0x3000 einmal addieren) dann kommt man bei 0x00 0B B0 07 raus.
Valid | Virtuelle Adresse | Adresse auf Page im Speicher | Flags
1 | 0x00 00 7 | 0x00 00 3 | 0x00 1
1 | 0x00 40 3 | 0x00 0B B | 0x00 7
1 | 0x00 AC C | 0x00 01 2 | 0x00 3
-
Zugriff auf 0x00 00 68 88
Es wird ein Page Fault ausgelöst, da das Present Bit vor dem 7. Eintrag in der Page Table überall auf 0 gesetzt ist. -
Prozesswechsel
TLB muss geleert werden und die aktuelle Page Table muss mit der Page Table des neuen Prozesses ausgetauscht werden, da jeder Prozess seine eigene Page Table hat. -
Warum mehrstufige Hierarchie?
Um Platz zu sparen! Veranschaulichung wie groß wäre eine Page Table mit nur einer Hierarchiestufe:
Bei 4KiB großen Pages hat man 12Bit Offset. (Beim Beispiel in den Vorlesungsfolien 5.2.1 Folie 20 war der Speicher auf 30Bit eingeschränkt, hier wurde nichts eingeschränkt also gehe ich mal von einem mit 32Bit voll adressierbaren Speicher aus. Soll das Beispiel ja nur veranschaulichen.) Damit Bleiben noch 20 Bit übrig, um einen Eintrag in einer Page Table auszuwählen. Pro Eintrag wird wie oben auch eine 20Bit Tag-Feld gespeichert plus 1 valid Bit. Damit hat man 2^20 Einträge á 21 Bit, das macht 21MiBit und geteilt durch 8 ergibt ungefähr 2,7MiByte. Das ist für einen Prozess vielleicht noch in Ordnung, aber wenn 100 Prozesse laufen braucht man 270MB allein Verwaltungsinformationen, auch wenn die Prozesse momentan kaum Speicher brauchen. Bei mehrstufiger Hierarchie hat man dagegen bei 100 Prozessen erstmal nur 400KiB Verwaltungsinformationen von vornherein und dann je nachdem wie viel ein Prozess benötigt halt zusätzliche Pages. -
Gemeinsamer Speicher. (nicht sicher ob das stimmt)
Ja, indem die Prozesse die gleiche Segmentnummer in ihrer Segmenttabelle eingetragen bekommen. Bei Paging auch möglich mit gleichem Eintrag in der Page Table.
4) Umformung
- Code in leicht assemblierbares if-goto Konstrukt umwandeln
1 len = LENGHT -1
2 i = -LIMIT
3 posi = pos + i
4 if i == 0 goto 8
5 if posi < 0 goto 8
6 if posi > len goto 10
7 ids[posi] = ids[posi] - 1
8 i = i + 1
9 if i <= LIMIT goto 3
10 nop
- Warum „switch case“ schneller langsamer als „if else if else“?
(Edit: ich hatte hier irgendwie hohe Laufzeiteffizienz oder sowas gelesen :nuts: )
Die case Anweisungen können leichter echt parallel und damit im Allgemeinen schneller ausgeführt werden.
Ist irgendwie ein zweischneidiges Schwert: Man kann eine „gute“ switch case Anweisung haben, ebenso wie eine „schlechte“ (ausführungstechnisch gesehen). Sagen wir mal O(n) Vergleiche. Aber das ist doch mit „if else if else“ Konstrukten genauso…
5) Arbeitsspeicher
-
DRAM ↔ SRAM
DRAM: Transistor + Kondensator | (-) zerstörendes Lesen
SRAM: 4 Transistoren | (-) verbraucht mehr Platz -
Speicherbank braucht Zykluszeit in dem die gelesenen Daten refreshed werden. Nächste Speicherbank kann sofort gelesen werden. Interleaving.
-
SDRAM … DDR3-SDRAM
SDRAM → DDR-SDRAM: Lesen bei steigender und fallender Taktflanke von 2 aufeinander folgenden Adressen (2-fach Prefetch). Verdoppelung des IO-Takts
DDR → DDR2: 4 aufeinander folgende Adressen (4-fach Prefetch). Weitere Verdoppelung des IO-Taktes
DDR2 → DDR3: 8 aufeinander folgedne Adressen (8-fach Prefetch). Weitere Verdoppelung des IO-Taktes
Der Prefetch wird durch Zwischenpufferung ermöglicht.
Der Speichertakt ist immer gleich geblieben.
- DDR doch nicht so gut?
Also wenn man zufällig auf der Bank verteilt zugreift und immer nur eine Adresse braucht, brints nix…?
- DDR doch wieder besser?
Der Cache wird in jedem Fall mehr als eine Adresse anfordern, um einen Cache-Block zu füllen.
6) Parallelverarbeitung
-
Def: Pipelining?
Befehle werden in Teilaufgaben zerlegt, welche dann nach dem Fließbandprinzip für mehrere Befehle gleichzeitig abgearbeitet werden. -
Arten von Multithreading
(hier bin ich mit den Anzahlen nich sicher)
Simultanes MT | bei n logischen Prozessoren: n Befehlszähler, n Universalregistersatz, n Flags-Register
Ereignisgesteuertes MT | 1 Befehlszähler, 1 Universalregistersatz, 1 Flags-Register
Zeitscheiben MT | 1 Befehlszähler, 1 Universalregistersatz, 1 Flags-Register
- Pipeline in Aktion
Takt;BH;BD;OH;BA1;Ba2;ES;eax;ecx
0;xorl;;;;;;?;?
1;movl;xorl;;;;;?;?
2;addl;movl;xorl;;;;?;?
3;subl;addl;movl;xorl;;;?;?
4;subl;addl;nop;movl;xorl;;?;?
5;subl;addl;nop;nop;movl;xorl;?;?
6;subl;addl;nop;nop;nop;movl;0;?
7;cmpl;subl;addl;nop;nop;nop;0;1
8;jg;cmpl;subl;addl;nop;nop;0;1
9;jg;cmpl;nop;subl;addl;nop;0;1
10;jg;cmpl;nop;nop;subl;addl;0;1
11;jg;cmpl;nop;nop;nop;subl;0;1
12;xorl;jg;cmpl;nop;nop;nop;1;1
13;xorl;jg;nop;cmpl;nop;nop;1;0
14;xorl;jg;nop;nop;cmpl;nop;1;0
15;xorl;jg;nop;nop;nop;cmpl;1;0
16;xorl;nop;jg;nop;nop;nop;1;0
17;nop;xorl;nop;jg;nop;nop;1;0
18;nop;nop;xorl;nop;jg;nop;1;0
19;nop;nop;nop;xorl;nop;jg;1;0
20;nop;nop;nop;nop;xorl;nop;1;0
21;nop;nop;nop;nop;nop;xorl;1;0
22;nop;nop;nop;nop;nop;nop;1;3
7) Cache
- Adressbereich der Arrays im Speicher.
1024 = Anzahl Ints in einem Array
4 * 1024 = 4096 = 0x1000 => Größe eines Arrays in Byte
a: 0x00 10 00 00 - 0x00 10 0F FF
b: 0x00 10 10 00 - 0x00 10 1F FF
c: 0x00 10 20 00 - 0x00 10 2F FF
-
Index der Cache-Blöcke
512 Blöcke => 9 Bit Index
8Byte pro Block => 3 Bit Byte-Adresse
9Bit + 3 Bit = 12 Bit
In allen Arrays sind jeweils beim der Adresse des ersten Eintrags die letzten 12 Bit 0. Also landen alle im ersten Cache-Block. -
Unter 50% Hits
a(i) wird in Cache geladen, b(i) verdrängt a(i), c(i) verdrängt b(i)
Im nächsten Durchlauf war a[i+1] zwar schon drin, wurde aber bereits verdrängt. Also das nochmal von vorne.
Bekommt man da überhaupt Hits oder hab ich was vergessen? -
-
-
-
- Cache Rechenaufgabe
(Edit: Rechenfehler!)
6Bit Byte-Adresse => 64Byte pro Block (=2^6 Byte pro Block)
256KiB = 2^18 Byte; 2^18 Byte / ( 2^6 Byte pro Block) = 2^12 Block => 4096 Blöcke
2-fach 4-fach assoziativer Cache, da mit 10 Bit Index nur 1024 und damit die Hälfte ein Viertel aller Blöcke adressiert werden kann.
Hierbei werden 1024 direktabbildende Mengen zu je 4 voll-assoziativen Blöcken (damit 4096 Blöcke) verwendet.
- Cache Rechenaufgabe
-
-
-
Edit1: Fehler ausgebessert.
Edit2: Speicherverwaltung hinzugefügt.
Danke erstmal, dass du dir die Mühe gemacht hast, hat mir geholfen wenigstens ein paar Sachen zu verstehen 
Ein paar Anmerkungen (die auch falsch sein könnten, weil ich selbst kein Profi bin^^):
Aufgabe 2
Allgemein: da du bei 1 anfängst zu zählen stimmt natürlich das goto 4(100) | 20, 21 nicht, müsste halt goto 3(11) sein und du fängst die Zeilen bei 0 an zu zählen
5. Zeile: reicht das was du hast oder muss es nicht 3, 8, 11 heißen?
Aufgabe 4
Abgesehen davon, dass ich den Code eh ganz anders geschrieben hab, ist deiner glaub ich falsch, weil du Zeile 7 nur erreichst, wenn alle ifs falsch sind, und eigentlich sollte die Zeile doch immer ausgeführt werden, oder?
Aufgabe 7
5. Wenn ich mich nicht verrechnet habe sind 256 KiB = 2^18 Byte → 2^12 Blöcke
→ 6. 4-fach assoziativer Cache
Ansonsten würde es mich freuen, wenn du auch noch den Rest machen würdest 
Bei Aufgabe 4.2 ist die Frage doch ne ganz andere oder?
Das Konstrukt switch…case kann analog zu if…else if…else auf Assemblerinstruktionen abgebildet werden.
Warum kann dadurch die Laufzeit eines Programms sehr hoch werden?
Antwort: Wegen den vielen compares die dann durchgeführt werden müssen.
Purer Eigennutzen, hier werden schließlich meine Fehler korrigiert. Also muss ich dir schonmal danken 
Du hast vollkommen Recht. Ich hatte mir nicht die Mühe gemacht die einzelnen Bits noch in die Tabelle einzutragen, damit ist es dann bei 1 als ersten Index geblieben. Vergessene ALU ist auch ausgebessert.
Also wenn ein if zu true auswertet, dann wird entweder ein break oder ein continue ausgeführt. Bei break wird die Schleife sofort verlassen und bei continue wird (zumindest nach meinem Verständnis der for-Schleife) der Zähler erhöht und die Bedingung erneut ausgeführt, also die Schleife am Anfang fortgesetzt. In beiden Fällen wird das Decrementieren in Zeile 7 nicht ausgeführt.
Ist ausgebessert, danke!
Ist in Arbeit.
Ups, ja die Frage ist durchaus ne ganz andere…
Ich habs oben geschrieben. Ist irgendwie mit deiner Antwort ein Zweischneidiges Schwert. Bei switch case müssen ja nicht alle compares ausgeführt werden (wenn breaks mit eingebaut sind) genauso kann es auch bei if-else-if-else sein, dass erst in der letzten if-abfrage die Bedingung erfüllt ist, also auch viele Vergleiche ausgeführt.
Gedanke, der mir gerade kommt: Kann es sein, dass bei switch case wesentlich mehr goto’s eingebaut werden beim assemblieren? Ich muss mir mal anschaun, wie ein switch case in Assembler ausschaut. Ansonsten danke für die Korrektur!
Normalerweiße erzeugt der compiler bei switch-case eine Sprungtabelle, so dass nur das Sprungziel aus der Tabelle geholt werden muss ohne einen compare.
Ich hab die Frage in der Klausur so verstanden, dass die switch-case als if-else schachtelung umgesetzt werden soll. Wodurch sich eine hohe laufzeit ergibt, weil dann eben für jeden case ein compare gemacht werden muss.
Du meinst so?
switch
case a: switch case 1: break; case 2: break; case 3 break;
case b: switch case 4: switch…
…
Okay also wenn man schlecht programmiert bekommt man eine hohe Laufzeit…
Irgendwie ist mir die Erklärung noch nicht so ganz einleuchtend. Ich hab in den Folien nichts zu einer Sprungtabelle gefunden. Nur bei 3.4.2 Folie 34 Sprungvorhersage mit EPIC.
Zu der Stackaufgabe:
Da häng ich irgendwie. Mir fällt nichtmehr ein, wie das ging und finde auch kein Beispiel dazu…
nein sowas hier
switch(a) {
case 1: break;
case 2: break;
case 3: break;
default: break;
}kannst auch so schreiben:
if(a == 1) { // do something
} else if (a == 2) {
// nochmal
} else if(a == 3) {
// yeah
} else {
// winner winner
}Hoffe damit ist es klarer.
[quote=kronos]Normalerweiße erzeugt der compiler bei switch-case eine Sprungtabelle, so dass nur das Sprungziel aus der Tabelle geholt werden muss ohne einen compare.[/quote]Jein. Compiler haben Heuristiken, die entscheiden, ab wann sich das lohnt und schneller ist. Sprungtabellen werden erst bei vergleichsweise vielen Einträgen ohne größere Lücken benutzt, darunter sind if-Kaskaden schneller.
[quote=kronos]Ich hab die Frage in der Klausur so verstanden, dass die switch-case als if-else schachtelung umgesetzt werden soll. Wodurch sich eine hohe laufzeit ergibt, weil dann eben für jeden case ein compare gemacht werden muss.[/quote]Bei den Problemgrößen, die aus Zeitgründen in Klausuren drankommen ist mit hoher Wahrscheinlichkeit die if-Kaskade die schnellere Lösung.
Solche Sachen lassen sich aber wunderbar selbst mit einem C-Compiler ausprobieren, wenn man sich mal den Assembler-Output anschaut. Tipp: Zum einfachen auffinden im Dump mit Inline-Assembler vor der Anweisung im C-Code ein Label platzieren:
asm volatile ("watch_this:");
switch (argc) {
// …
}Das ist die Frage aus der Klausur:
Was wäre da deine Antwort drauf? (aka. hab ich jetzt die Frage richtig verstanden oder nicht?)
Bei sehr vielen switch cases gibts dann viele Vergleiche (cmp) und bedingte Spruenge (jgt/jlt). Ist das laufende Program erst beim 1024ten Vergleich positiv, muss es vorher 1023 Vergleiche und 1023 bedingte Spruenge durchlaufen.
Deshalb gibts diese Sprungtabellen.
Aka. ja ich glaube du hast es verstanden
Ist die Rücksprungadresse nicht die Adresse des nächsten Befehls in der aktuellen Funktion?
Des müsste doch so aussehen, oder?
| … |
----- ← esp
| 0x17 | 0x ff ff d2 c8
-----
| ? ? ? | 0x ff ff d2 cc
-----
| … |
(2) call 10
| … |
----- ← esp
| 0x05 | 0x ff ff d2 c4
-----
| 0x17 | 0x ff ff d2 c8
-----
| ? ? ? | 0x ff ff d2 cc
-----
| … |
Wie ist das, wird nicht nur gesprungen, wenn S (also der Wert in C) == 0 ist?
Ansonsten addiert der Multiplexer ja bloß 1 auf den bisherigen Befehlszähler…
Mein Vorschlag unter der Annahme, dass nur bei C == 0 gesprungen wird und man von der Eingabe eine natürliche Zahl erwarten kann:
-
Eingabe → D
-
D → A // Zahl n von Eingabe nach A
-
A + B → C // Bisherige Summe und A aufsummieren
-
C → B // Summe in B aktualisieren
-
A - 1 → C // n dekrementieren
-
Springe zur Ausgabe in Takt 11, sollte n jetzt 0 erreicht haben
-
C → A // Endsumme offensichtlich noch nicht erreicht. n in A aktualisieren
-
B → C; C → B // Zwischensumme in C sichern, gleiches n wie in A nach B schreiben
-
A - B → C; C → B // 0 in C erzeugen, Zwischensumme zurück nach B schreiben
-
Springe zu Takt 3 und wiederhole, da C == 0 ist
-
B → D // Endsumme zur Ausgabe
-
D → E
-
E → Ausgabe
Darf das addl in Takt 4 nicht noch bis in die Operandenholphase vorrücken und dort verharren, bis [m]movl [/m]das Ergebnis zurückgeschrieben hat?
S ist soweit ich das verstanden habe nicht der Wert C, sondern das Vorzeichenbit von C und das 17. Bit in deinem Mikrobefehl ver-und-et (unter der Annahme, dass 1 für das Vorzeichen negativ bedeutet). Auf jeden Fall ist S nicht dasselbe wie C und S==0 unten ist quasi nur die Steuerung für den Multiplexer. Das was links in der Spalte steht zählt.
Meine Frage an Franz Richter: In welcher Befehlsphase bleiben die Befehle dann stehen? In Dekodieren oder Operanden holen?
Meine Meinung: Wenn man sie in Dekodieren stehen lässt, kann es einem nicht passieren, dass man den Befehl gleich weiter schiebt.