Martin Thoma A blog about Code, Politics, and my life

TI-Klausur (DT & RO)

· by

Inhalt
Dieser Artikel beschäftigt sich mit den Vorlesungen „Digitaltechnik und Entwurfsverfahren“ sowie „Rechnerorganisation“ des Moduls „Technische Informatik“ am KIT. Er dient als Prüfungsvorbereitung. Ich habe die Vorlesungen bei Herrn Prof. Dr. Asfour gehört.

Vorbereitung DT

Themen:

  • Zahlensysteme: Horner-Schema, euklidischer Algorithmus
  • Zahlendarstellungen: Wie wandle ich eine Zahl vom 10er-System ins Zahlensystem xy um und umgekehrt?
    • Vorzeichen
      • Betrags-Vorzeichen → Antwort
      • Einerkomplement → Antwort
      • Zweierkomplement → Antwort
      • Exzess-q → Antwort
    • Komma
      • Festkomma → Beispiele
      • Gleitkomma → Beispiele ($\pm \text{Mantisse} \cdot b^\text{Exponent}$)
  • IEEE 754 Format
    • A practical approach to floats
    • Wie wird NaN dargestellt? Wie wird $-\infty$ und $+\infty$ dargestellt?
    • Was ist eine normalisierte Zahl, was eine denormalisierte?
  • Was ist BCD, AIKEN und STIBITZ? Wie werden die Ziffern von 0-9 dort dargestellt?
  • Was sind Hamming-Codes? → Antwort
  • Wie lauten die Huntingtonschen Axiome? → Antwort
  • Nenne 3 verschiedene vollständige Operatorensysteme. → Antwort
  • Was sind Primterme, Primimplikanten, Primimplikate, Minterme und Maxterme?
  • Was sind DMF, DNF, KMF, KNF?
  • Wie wende ich die Shannon-Zerlegung an? → Antwort
  • Wie minimiere ich Funktionen mit KV-Diagrammen?
  • Wie funktioniert das Quine-McCluskey-Verfahren? → Antwort
  • Was macht das Consensus-Verfahren? → Antwort
  • Wie funktioniert das Nelson-Verfahren?
  • Was bedeutet selbstleitend und selbstsperrend?
  • Was ist ein MOSFET? → Aufbau
  • CMOS, N-MOS, P-MOS
  • Was ist der Unterschied zwischen einem Hazard und einem Hazard-Fehler?
  • Woran erkennt man Funktionshazards, woran Strukturhazards?
  • Wie lauten die Ansteuertabellen von D-, T-, JK- und RS-Flipflops? → Antwort
  • Was macht ein Carry-Ripple-Addierer? → Antwort
  • Inwiefern stellt der Carry-Lookahead-Addierer eine Verbesserung des Carry-Ripple-Addierers dar? → Antwort
  • Was macht man, wenn bei der Addition zweier BCD-Zahlen eine Pseudotetrade auftritt? → Antwort
  • Was macht man, wenn bei der Addition zweier BCD-Zahlen ein Übertrag in die nächste BCD-Ziffer auftritt? → Antwort
  • Was macht man, wenn bei der Addition zweier BCD-Zahlen bei der Korrekturaddition ein Übertrag auftrat? → Antwort
  • Was ist die PPS-Methode? → Antwort

Vorbereitung RO

Themen:

  • Y-Diagramm
  • Aufbau eines Mikroprozessors
  • Umrechnen von Zahlensystemen
  • RAM-Typen (DRAM, FPM-DRAM, EDO-RAM, SDRAM, DDRAM, DDR-SDRAM, RDRAM)
  • Cache-Speicher

Begriffe

  • Was sind Tristate-Treiber? → Antwort
  • Was ist der Unterschied zwischen Assembler, Maschinensprache und Mikrobefehlen?
  • Wofür stehen RISC und CISC und was sind Beispiele? → Antwort
  • Was ist ein User/System-Bit, was ein Trace-Bit und was ein Decimal-Bit? → Antwort
  • Welche Informationen können im Statusregister des Rechenwerkes stehen? → Antwort
  • Welche Informationen können im Akkumulator stehen? → Antwort
  • Warum benötigt die ALU Hilfsregister? → Antwort
  • Entspricht das logische Rechtsschieben der Division durch zwei? → Antwort
  • Was ist ein superskalarer Prozessor? → Antwort
  • Was ist Little-Endian und was ist Big-Endian? → Antwort
  • Was versteht man unter dem Nulladressformat? → Antwort
  • Was ist eine „effektive Adresse“? → Antwort
  • Was bedeutet ZF, CF, SF, OF und wozu sind sie jeweils gut?
  • Was ist eine Load/Store-Architektur? → Antwort
  • Was sind die fünf Schritte in der DLX-Pipeline-Verarbeitung? → Antwort
  • In welcher Pipeline-Phase werden die Operanden aus dem memory geholt? → Antwort
  • Durch welche Abhängigkeiten entstehen Verzögerungen in der DLX-Pipeline und wann treten diese auf? → Antwort
  • Was ist eine echte Datenabhängigkeit, was eine Gegenabhängigkeit und was eine Ausgabeabhängigkeit? → Antwort
  • Was ist eine falsche Abhängigkeit? → Antwort
  • Treten bei echten Abhängigkeiten immer Konflikte auf? → Antwort
  • Welche Konflikte gibt es und wann können sie auftreten? → Antwort
  • Welche Abhängigkeiten können bei der DLX-Pipeline zu Konflikten führen? → Antwort
  • Wie kann man Datenkonflikte durch Software lösen? → Antwort
  • Wie kann man Datenkonflikte durch Hardware lösen? → Antwort
  • Nennen Sie ein Beispiel für einen Konflikt, der nicht durch Forwarding lösbar ist. → Antwort
  • Wie kann man Ressourcenkonflikte lösen? → Antwort
  • Was bedeutet tRAC, tRC, tCAC und tPC?
  • Was versteht man unter Bus-Schnüffeln? → Antwort

MIPS

Befehlsformate

MIPS Befehlsformate
MIPS Befehlsformate
Quelle: Folien von Prof. Dr. Asfour

Typ-R-Befehle sind arithmetisch-logische Befehle wie add, sub, and, or sowie Vergleichsbefehle wie slt.

Typ-I-Befehle sind Lade- und Speicherbefehle sowie Verzweigungsbefehle: lw $rt, imm($rs)
sw $rt, imm($rs)
beq $rs, $rt, immediate: Hier wird immediate als 16-Bit-vorzeichenbehaftete Zahl interpretiert und als Offset in Wörtern (4 Byte) benutzt. Die Basisadresse ist dabei im PC. Also lautet die Zieladresse: (PC zum Zeitpunkt des Befehls + 4) + 4 · immediate

Grundlegende Befehle

Syntax Erklärung
li $t0, 9 load immediate: Lädt eine Konstante in ein Register
sll $rd, $rs, shamt shift left logical: $rd = $rs << shamt
ble Rsrc1, Src2, label Branch on Less Than Equal: Rsrc1 ≤ Src2
bne $rs, $rt, imm Branch on not equal: if($rs!=$rt) PC = PC + 4 + 4 · imm (imm could also be a label)
slti $rt, $rs, imm Set on less than immediate: if($rs < imm) {$rt = 1;} else {$rt = 0}
la Rdest, address Load computed address, not the contents of the location, into register Rdest

MiMa

Mikrobefehlsformat der MiMa
Mikrobefehlsformat der MiMa
Quelle: Folien von Prof. Dr. Asfour

Fetch-Phase

In der Fetch-Phase muss die neue Instruktion ins IR geladen werden und der PC (bei der MiMa: IAR) um eins erhöht werden:

  1. Takt: IAR → SAR; IAR → X; R = 1
  2. Takt: Eins → Y; R = 1
  3. Takt: ALU auf addieren; R = 1
  4. Takt: Z → IAR
  5. Takt: SDR → IR

Das zugehörige Mikroprogramm ist:

0010 0001 0000 1000 1000 0000 0001
0001 0100 0000 0000 1000 0000 0010
0000 0000 0000 0001 1000 0000 0011
0000 1010 0000 0000 0000 0000 0100
0000 0000 1001 0000 0000 0000 0101

Fragen

Zeichnen Sie ein Y-Diagramm.
Y-Diagramm
Y-Diagramm
Quelle: Folien von Prof. Dr. Asfour
Wie ist ein Von-Neumann-Rechner aufgebaut?
Von-Neumann-Architektur
Von-Neumann-Architektur
Das Steuerwerk wird auch „Leitwerk“ genannt, das Rechenwerk auch „Arithmetic Logic Unit“. Der Bus beinhaltet Adress-, Daten- und Steuerleitungen. Im Gegensatz zur Harvard-Architektur wird beim Speicher in der Von-Neumann-Architektur nicht zwischen Daten und Programmen unterschieden.
Wie ist ein Mikroprozessor aufgebaut?
Aufbau eines Mikroprozessors
Aufbau eines Mikroprozessors
Quelle: Folien von Prof. Dr. Asfour
Aus welchen Phasen besteht die Befehlsausführung?
  • Holphase
  • Dekodierphase
  • Ausführungsphase
Warum gibt es mehr als ein Befehlsregister?
  • Die Befehlsformate sind unterschiedlich lang
  • Opcode-Prefetching
Was ist der Unterschied zwischen BCD in gepackter Darstellung und BCD in ungepackter Darstellung?
Bei BCD in gepackter Darstellung werden in einem Byte (8 Bit) zwei BCD-Ziffern dargestellt. In der ungepackten Darstellung wird in einem Byte nur eine BCD-Ziffer dargestellt.
Pipeline-Konflikte: Welche Forwarding-Techniken gibt es und wie werden sie umgesetzt?
Forwarding-Techniken
Forwarding-Techniken
Quelle: Folien von Prof. Dr. Asfour
Welche Halbleiterspeichertypen gibt es?
Klassifizierung von Halbleiterspeichern
Klassifizierung von Halbleiterspeichern
Skizzieren Sie eine SRAM-Zelle.
CMOS SRAM Zelle
CMOS SRAM Zelle
Wie unterscheiden sich RISC- und CISC-Architekturen?
CISC RISC
Komplexe Befehle, die in mehreren Taktzyklen ausgeführt werden Einfache Befehle, die in einem Taktzyklus ausgeführt werden
Jeder Befehl kann auf den Speicher zugreifen Nur Lade- und Speicherbefehle greifen auf den Speicher zu
Wenig Pipelining Intensives Pipelining
Befehle werden von einem Mikroprogramm interpretiert Befehle werden durch festverdrahtete Hardware ausgeführt
Befehlsformat variabler Länge Befehlsformat fester Länge
Die Komplexität liegt im Mikroprogramm Die Komplexität liegt im Compiler
Einfacher Registersatz Mehrere Registersätze
Wie sieht das Schaltsymbol eines Halbaddierers aus?
Schaltsymbol eines Halbaddierers
Schaltsymbol eines Halbaddierers
Wie kann man die Datenabhängigkeiten einer Pipeline spezifizieren und erkennen?
Datenabhängigkeiten in einer Pipeline
Datenabhängigkeiten in einer Pipeline
Erkennen kann man sie sehr schnell, indem man eine Tabelle mit den Spalten Befehl, Ziel-Register und Operanden-Register macht. Dabei muss man insbesondere bei der Multiplikation, sw und lw aufpassen. Folgendes (sehr gekritzelte) Beispiel für die Klausur vom 26. Juli 2012:
Datenabhängigkeiten schnell erkennen
Datenabhängigkeiten schnell erkennen

Material

StackOverflow:

Aufbau der Klausur

Die Klausuren sind alle sehr ähnlich aufgebaut. Eine typische Klausur hat 10 Aufgaben zu diesen Themen:

  1. Schaltfunktionen
  2. Spezielle Bausteine
  3. Laufzeiteffekte
  4. Schaltwerke
  5. Rechnerarithmetik und Codes
  6. Allgemeines: Ankreuzaufgaben
  7. MIPS-Assembler: C-Code in MIPS umwandeln und umgekehrt
  8. Pipelining: Datenkonflikte erkennen und mit NOPs beheben, eventuell gibt's noch Forwarding
  9. Cache-Speicher
  10. Speicher

Termine und Klausurablauf

Datum: Mittwoch, den 3. April 2013 von 14:00 bis 16:00 Uhr
Ort: Gaede (bei mir; siehe Hörsaaleinteilung, die seit dem 2. April 2013 draußen ist)
Dauer: 1 h DT, 1 h RO
Punkte: (vermutlich) 90
Bestehensgrenze: (vermutlich) 40
Übungsschein: Wird nicht ins Studierendenportal eingetragen
Bonuspunkte:

  • Übungsschein RO: 1 Bonuspunkt
  • Übungsschein DT: 1 Bonuspunkt
  • Für die Probeklausuren jeweils:
    • Note „Sehr gut“: 2 Bonuspunkte
    • Note „Gut“: 1,5 Bonuspunkte
    • Note „Befriedigend“: 1 Bonuspunkt
    • Note „Ausreichend“: 0,5 Bonuspunkte

Nicht vergessen

  • Studentenausweis
  • Kugelschreiber

Ergebnisse

Die Klausureinsicht ist am Montag, den 29. April 2013. Für die Einsicht muss man sich hier anmelden.