TU Wien:Digital Design and Computer Architecture LU (Polzer)/Ausarbeitung der Theoriefragen
DDCA Theoriefragen Ausarbeitung vom 16.0.2015
README: Wenn jemanden ein Fehler auffaellt soll er den doch bitte ausbessern! Danke schon mal an alle!
1.) ALU
Q: A general comparison between two values for less-than/greater-than requires a subtraction and an appropriate evaluation of the most significant bits of the result. How many logic elements does the critical path for a comparison of two n-bitvalues contain asymptotically (i.e.,O(n2),O(n),O(logn),...)? What about comparing for equality/inequality? Why is a comparison for less-than-zero cheap when using a two’s complement representation?
A: Ein Subtrahierer ist ein Addierer, in dem der zweite Operand negiert ist und Carry_in auf 1 gesetzt ist. Sind also >O(n)< logische Elemente. Für den Vergleich von Gleich / Ungleich, braucht man XOR-Gatter, deren Ausgaenge alle mit einem OR verknüpft sind. Das kann man effizient in >O(n log n)< lösen. Im Zweiterkomplement sind "Less-Than-Zero" vergleiche billig da man nur das Neg Bit (MSbit) abfragen muss.
2.) Jump Unit
Q: Table 6 does not contain operations for all boolean combinations of N and Z. Would an operation for N and Z make sense? If so, what would be the high-level comparison? If not, explain why.
A: Im Zweierkomplement koennen N und Z nicht gleichzeitig auftreten, -0 existiert in diesem System nicht. (Bei Float / Einerkomplement waere es natuerlich moeglich). Bei unserer MIPS schließen sich N und Z aus, weil N nur dann '1' ist, wenn das höchste Bit '1' ist. Z ist aber nur dann eins, wenn alle Bits '0' sind, inkl. dem höchsten Bit.
3.) Memory Unit
Q: The memory unit uses big-endian addressing, where the most significant byte of a word is stored at the lowest address. After storing the word 0x12345678 at address 4, what value should be returned when loading a byte from address 5? Which value should be returned for the half-word at address 6?
A: Byte an der Addresse 5 ist 0x34, das Halfword an der Addresse 6 ist 0x5678.
Für Leute mit Brainhänger:
4 | 12
5 | 34
6 | 56
7 | 78
4.) Register File
Q: Given memory blocks with one write- and one read-port, how can a memory with one write- and two read-ports be implemented efficiently? What is the overhead, compared to a memory with one write- and one read-port?
A: Man benoetigt zwei Memory Blocks. Strom- und Platzverbrauch ist hoeher. Wie das auf unserem FPGA synthetisiert wird ist etwas unklar (realer Hardwareverbrauch).
Schreiben immer auf beide Blocks, zum Lesen extra Logik benötigt die die Last auf beide gleichmäßig aufteilt.
5.) Fetch
Q: Sketch a fetch stage with variable-length instructions, where the value for the next program counter depends on the instruction that is currently fetched. Which sub-components would be on the critical path in such a fetch stage?
A: Fetch muss den gesamten Befehl laden (worst case Größe beachten), davor ist keine Aussage ueber die naechsten Schritte fuer den PC moeglich. Bestimmt der OPCODE die Größe des Befehls kann diese zum Beispiel ueber eine LUT nachgeschlagen werden. Kann aber auch ueber mehrere MUX und LUTs passieren, dementsprechend verlaengert sich der kritische Pfad.
6.) Decode
Q: Explain why it is beneficial to have source registers in the same position for all instruction formats, and why this is less of an issue for destination registers.
A: Es wird nicht immer ein Destination Register gebraucht (z.B.: Bei Branches). Das Source Register wird hingegen fast immer gebraucht. Man kann sich dadurch also einen MUX zur richtigen Selektion des Registers sparen da es ohnehin immer an der selben Stelle steht.
Der Wert des Source Registers wird des Weiteren schon zur Berechnung benötigt, während das Destination Register erst später gebraucht wird. Extra Logik würde also die Berechnung verlangsamen.
7.) Execute
Q: Explain why it is beneficial to multiplex the operands for a single adder over using several adders and multiplex their results. Does the benefit concern rather the performance or the size of the resulting hardware?
A: Ein MUX ist deutlich billiger (Anzahl Bauteile) und stromsparender zu implementieren als Adder fuer saemtliche Rechenkombinationen. Dementsprechend kann man eine geringere groesze Hardware mit nur einem Adder und einem multiplexen der Operanden erzielen.
In der Realitaet muss eine Abschaetzung zwischen Perfomance und Platz gemacht werden.
Wenn man die Muxer vor dem Addierer durch einen Muxer nach den Addierer ersetzt, müsste man soviel Addierer benutzen, wie es mögliche Kombinationen durch Muxereingänge gibt. Also zwei Muxer mit zwei Eingängen vor dem Addierer kann durch vier Addierer und einem Muxer mit vier Eingängen ersetzt werden.
8.) Pipeline
Q: Listing 1 contains seven nop-instructions. How many of these instructions can be removed by reordering instructions, without changing the semantics of the program?
A: Ein NOP kann auf zwei Weisen neu angeordnet werden.
loop: addi nop j loop sw $1, 16 nop nop ODER loop: addi j loop nop sw $1, 16 nop nop
9.) Forwarding
Q: Explain why forwarding to an instruction immediately after a memory load is infeasible. Where would the critical path be if one would try to forward the result of a memory load to the ALU?
A: Wenn gleich nach einem Load eine Instruction mit dem Ergebnis (rd) des Loads als Operator (rs, rt) kommt, dann würde aber das Ergebnis der ALU vom vorigen Zyklus genommen werden, welches nicht dem gewünschten Ergebnis aus dem Memory Load ist.
Wenn aber das Ergebnis des Memory Loads (memresult) an die Execute stage weitergeleitet werden würde (zB.: fwd_type mit FWD_MEM erweitern und memresult an die exec stage weiter reichen), dann würde folgender Pfad entstehen:
- Die Memory legt das Ergebnis auf ihren Ausgang.
- Das selbe Signal kommt in die Memory Stage,
- durch die Memu,
- aus der Memory Stage raus,
- durchs Forwarding in die Exec Stage rein,
- durch die ALU,
- bis zu den Eingängen der Memory Stage.
Das Signal würde so durch den viel zu langen Pfad wandern und es schlussendlich nicht schaffen bei der nächsten Taktflanke als aluresult am Memory Stage Eingang bereit zu stehen.
10.) Branch Hazards
Q: A branch delay slot is a means to keep the hardware simple while reducing the cost of branches, but may increase the code size. How much is the code size increased with one-cycle branch delay slots, if 15% of the instructions are branches, and 30% of the branch delay slots can be filled by the compiler with useful instructions?
A: Fabjans Super Rechnung.
Alle Delay Slots mit NOP auffuellen: 0,85 * 1 + 0,15 * 2 (85% brauchen fuer eine Instruction eine Zeile Code, 15% der Instructions brauchen zwei Zeilen, ein Branchbefehl und das NOP danach).
Mit auffuellen von NOPs durch Befehle: 0,85 * 1 + 0,15 * 0,3 *1 + 0,15 * 0,7 * 2 ~ 10,5% mehr Zeilen Code (Zeile Code = Befehl)
Oder noch einfacher:
15% sind branches
30% der branches brauchen keinen branch del slot => also brauchen 70% einen
0,15 * 0,7 = 0,105 => 10,5%