T03-ReTI-Befehlssatz-und-Maschinencode

ReTI Befehlssatz & Maschinencode

Zusammenfassung

ReTI (Rechner Technische Informatik) ist der in der Vorlesung verwendete Beispielrechner. Er wurde ursprünglich unter dem Namen ReSa ("Rechner Saarbrücken") in [Keller,Paul] eingeführt. ReTI dient als Illustrator und Anwendungsbeispiel für alle vorgestellten Konzepte der Vorlesung — von Kodierung über Datenpfade bis hin zur Kontrolllogik.

Die abstrakte ReTI-Maschine besitzt zwei unendlich große Speicher und vier Register. In der realen Implementierung werden Speicher und Register auf 32-Bit-Wörter () beschränkt, und Befehle werden als 32-Bit-Maschinencode kodiert. Der Befehlssatz umfasst Load/Store-, Compute- und Jump-Befehle.

Exam-Relevanz

  • Aufgabe 2 (A2) in der Klausur: 16 Punkte — "ReTI Machine Code Quiz"
  • Sowohl in der Exam-Klausur (WS 2024/25) als auch in der probeklausur (SoSe 2026) ist A2 identisch aufgebaut
  • Gegeben: Ein ReTI-Programm mit 16 Instruktionen, bei denen jeweils ein Hex-Ziffer fehlt (_), sowie die Befehlstabelle auf der nächsten Seite
  • Gefragt: Vervollständigung des Maschinencodes — eine Hex-Ziffer pro _
  • Die Befehlstabelle wird in der Klausur mitgegeben — man muss also nicht auswendig wissen, welche Bits welchen Befehl kodieren, aber man muss schnell und korrekt encode/decode können
  • Zeitbudget: ~15 Minuten für 16 Fragen (90 min / 6 Aufgaben)
  • Tool zum Üben: retiquiz <matrikelnummer> aus dem reticode Repository

Die ReTI Maschine

Architektur (abstrakt)

Komponente Beschreibung
Datenspeicher Unendlich viele Zellen, = Inhalt von Zelle ,
Programmspeicher Unendlich viele Zellen mit Maschinenbefehlen, = Befehl an Adresse
PC Program Counter (Befehlszähler)
ACC Akkumulator
IN1 Indexregister 1
IN2 Indexregister 2

Architektur (real, 32-Bit)

  • Ein gemeinsamer Speicher der Größe für Daten und Befehle
  • — jedes Element ist ein Wort (32-Bit-Bitvektor)
  • Register PC, ACC, IN1, IN2 nehmen jeweils auf
  • Ein Wort kann interpretiert werden als:
    • Binärzahl (z. B. Adresse in ) — Notation
    • Zweierkomplementzahl — Notation
    • Bitstring (für Bitoperationen)

Notation

wobei als Zweierkomplementzahl interpretiert wird.

Programmablauf

  • Beim Start: Programm in , Daten in ,
  • Inhalt von wird nicht geändert
  • In jedem Schritt : wird als Befehl interpretiert und ausgeführt
  • PC erhält neuen Wert (abhängig vom Befehl — meist )

Befehlssatz

Der Befehlssatz umfasst vier Gruppen: Load, Store, Compute und Jump. Alle Befehle werden als 32-Bit-Wörter kodiert.

Register-Kodierung

S / D Register
00 PC
01 IN1
10 IN2
11 ACC

Load-Befehle —

Befehl Wirkung
0100 LOAD D i
0101 LOADIN1 D i
0110 LOADIN2 D i
0111 LOADI D i

Für alle Load-Befehle: , falls .

Store-Befehle — MOVE: ,

Befehl Wirkung
1000 STORE i
1001 STOREIN1 i
1010 STOREIN2 i
1011 MOVE S D

Für alle Store-Befehle: , falls .

Compute-Befehle —

Immediate-Befehle (MI = 0)

Befehl Wirkung
000010 SUBI D i
000011 ADDI D i
000100 OPLUSI D i
000101 ORI D i
000110 ANDI D i

Memory-Befehle (MI = 1)

Befehl Wirkung
001010 SUB D i
001011 ADD D i
001100 OPLUS D i
001101 OR D i
001110 AND D i

Für alle Compute-Befehle: , falls .

Jump-Befehle —

Befehl Bedingung
11000 NOP nie (nur )
11001 JUMP> i
11010 JUMP= i
11011 JUMP>= i
11100 JUMP< i
11101 JUMP!= i
11110 JUMP<= i
11111 JUMP i immer (unbedingt)

Bedingte Sprungbefehle:

Unbedingter Sprung (JUMP i, ):

NOP (): — keine andere Wirkung.

Condition-Kodierung

Die 3-Bit-Bedingung kodiert Vergleiche von mit :

Bit Bedeutung wenn gesetzt
() wird abgefragt
() wird abgefragt
() wird abgefragt

Kombinationen: → ( oder ), → ( oder ), etc.

Instruktionsformate

Allgemeines Format

Sei . Die Notation für .

Bits 31–30 29–28 27–26 25–24 23–0
Feld Typ Modus/Funktion/Compare/Source Destination Immediate

Typ-Kodierung (Bits 31–30)

T Typ
01 Load
10 Store
00 Compute
11 Jump

Spezifische Formate

Load

31–30 29–28 27–26 25–24 23–0
Load 01 M ** D i
  • M — Modus: 00=LOAD, 01=LOADIN1, 10=LOADIN2, 11=LOADI
  • ** — irrelevant (kein Source-Register bei Load)
  • D — Destination Register
  • i — 24-Bit-Immediate (Adresse, Offset oder Konstante)

Store

31–30 29–28 27–26 25–24 23–0
Store 10 M S D i
  • M — Modus: 00=STORE, 01=STOREIN1, 10=STOREIN2, 11=MOVE
  • S — Source Register (nur bei MOVE relevant)
  • D — Destination Register (nur bei MOVE relevant)
  • i — absolute Adresse oder Indexregister-Offset

Compute

31–30 29 28–26 25–24 23–0
Compute 00 MI F D i
  • MI — Memory/Immediate: 0=Immediate, 1=Memory
  • F — Funktion (3 Bits): 010=SUB, 011=ADD, 100=OPLUS, 101=OR, 110=AND
  • D — Destination Register (Source implizit )
  • i — Immediate-Konstante oder Speicheradresse

Jump

31–30 29–27 26–24 23–0
Jump 11 C *** i
  • C — Condition (3 Bits, siehe Jump-Tabelle oben)
  • *** — irrelevant
  • i — 24-Bit-Sprungweite als Zweierkomplementzahl

Sign Extension bei Immediate

  • LOADI: — die oberen 8 Bits werden mit 0 gefüllt (Zero-Extension)
  • OPLUSI, ORI, ANDI: — ebenfalls Zero-Extension auf 32 Bit
  • ADDI, SUBI: — wird als Zweierkomplement interpretiert (Sign-Extension)
  • JUMP: — als Zweierkomplement (kann negativ sein für Rückwärts-Sprünge)

Encode/Decode

Encode: Instruktion → Maschinencode (Hex)

Vorgehen:

  1. Befehlstyp bestimmen → Bits 31–30
  2. Modus/Funktion/Condition bestimmen → Bits 29–26 (je nach Typ)
  3. Source/Destination-Register kodieren → Bits 27–24
  4. Immediate als 24-Bit-Zweierkomplement → Bits 23–0
  5. Alle Bits zusammenfassen → 32-Bit-Wort → als Hex darstellen

Beispiel 1: LOADI IN2 42

  • Typ: Load → 01
  • Modus: LOADI → 11
  • Irrelevant: 00 (wird 0)
  • D = IN2 → 10
  • → 0000000000000000000000101010 (24 Bit)

Hex: 0111 0010 0000 0000 0000 0000 0010 1010 = 7200002A

Beispiel 2: MOVE IN2 ACC

  • Typ: Store → 10
  • Modus: MOVE → 11
  • S = IN2 → 10
  • D = ACC → 11
  • (irrelevant)

Hex: 1011 1011 0000 0000 0000 0000 0000 0000 = BB000000

Beispiel 3: JUMP 0 (unbedingt)

  • Typ: Jump → 11
  • C = immer → 111
  • Irrelevant: 000

Hex: 1111 1000 0000 0000 0000 0000 0000 0000 = F8000000

Beispiel 4: ADD ACC -9

  • Typ: Compute → 00
  • MI = Memory → 1
  • F = ADD → 011
  • D = ACC → 11
  • als 24-Bit-Zweierkomplement: FFFFFF7

Hex: 0011 1011 1111 1111 1111 1111 1111 0111 = 3BFFFFFF7

Achtung: Das obige Beispiel zeigt die Struktur. Tatsächlich ergibt 00 1 011 11 + 24-Bit--9 = 0011 1011 1111 1111 1111 1111 1111 0111 = 3BFFFFFF7. In der Klausur (A2) steht ADD ACC -9 mit Code _ffffff7 — die fehlende Ziffer ist 3 (Bits 31–28 = 0011).

Decode: Maschinencode → Instruktion

Vorgehen:

  1. Bits 31–30 lesen → Typ bestimmen
  2. Je nach Typ weitere Bits lesen:
    • Load (01): Bits 29–28 = M, Bits 25–24 = D
    • Store (10): Bits 29–28 = M, Bits 27–26 = S, Bits 25–24 = D
    • Compute (00): Bit 29 = MI, Bits 28–26 = F, Bits 25–24 = D
    • Jump (11): Bits 29–27 = C
  3. Bits 23–0 = Immediate
  4. Register und Befehlsname aus Tabellen ablesen

Beispiel: 9100000A dekodieren

  • Binär: 1001 0001 0000 0000 0000 0000 0000 1010
  • Bits 31–30 = 10 → Store
  • Bits 29–28 = 01 → Modus = STOREIN1
  • Bits 27–26 = 00 → S = PC (irrelevant bei STOREIN1)
  • Bits 25–24 = 01 → D = IN1 (irrelevant bei STOREIN1)
  • Bits 23–0 = 000000000000000000001010 = 10

→ STOREIN1 10

Klausur-Strategie für A2

Bei der Klausuraufgabe fehlt jeweils eine Hex-Ziffer (4 Bits) im Maschinencode. Vorgehen:

  1. Instruktion und ggf. Register und Immediate aus der linken Spalte ablesen
  2. Bestimmen, welche 4 Bits fehlen (welche Nibble-Position im 32-Bit-Wort)
  3. Diese Bits aus Befehlstabelle + Register-Kodierung + Immediate ableiten
  4. Als Hex-Ziffer eintragen

Wichtig: Für irrelevante Bits (* in der Befehlstabelle) wird 0 eingetragen!

Kontrolllogik

Die Kontrolllogik von ReTI wird als endlicher Automat realisiert. Die Befehlsabarbeitung ist in Fetch-Phase und Execute-Phase unterteilt, jede Phase besteht aus 4 Takten.

Phasensignale

Signal Bedeutung
Fetch-Phase
Execute-Phase
Binärkodierung der Taktnummer (0–3) innerhalb der Phase
  • Steigende Flanken (Taktbeginn):
  • Fallende Flanken (Taktmitte):
  • ck, werden Phasensignale genannt

Kontrollsignale

Signal Typ Beschreibung
rcken Clock-Enable Für Register
/XYdoe Output-Enable (active low) Für Treiber XYd
Funktions-Select ALU-Funktionsauswahl
/PCclear, /PCload PC-Steuerung Clear/Load des PC
sext Sign-Extension Füllbits bei 24-Bit-Immediate
/SMDdoe Output-Enable (active low) Speicher-Ausgangstreiber
SMw Memory Write Schreibsignal für Speicher

Fetch-Phase (, 4 Takte –)

  1. : PC-Adresse auf Adressbus legen (PCAd enabled)
  2. : Befehl aus Speicher lesen (/SMDdoe aktiv), in Instruktionsregister laden (Icken)
  3. –: Befehl dekodieren, Vorbereitung der Execute-Phase
  4. : PC auf Bus legen für eventuelle PC-Modifikation (PCLdoe)

Execute-Phase (, 4 Takte –)

  1. –: Operanden laden, ALU-Operation ausführen
  2. –: Ergebnis in Zielregister schreiben (rcken aktiv)
  3. –: Bei Store-Befehlen: Speicher schreiben (SMw aktiv)

Beispiel: Icken (Instruktionsregister Clock-Enable)

Aktiv im Takt der Fetch-Phase ().

Beispiel: ACCcken (ACC Clock-Enable)

Aktiv im Takt der Execute-Phase, aber nur bei Befehlen, die ACC als Ziel haben.

Speicheransteuerung

  • /SMDdoe (Lesen): aktiviert von bis (nächster Takt) bei Fetch, Compute-Memory, LOAD, LOADINj
  • SMw (Schreiben): aktiviert von bis der Execute-Phase bei STORE, STOREINj

Siehe k460-Kontrolllogik_von_ReTI für Details.

Typische Klausuraufgabe

A2 — ReTI Machine Code Quiz (16 Punkte)

Format (identisch in Exam und probeklausur):

$ ./retiquiz 202502260900
ReTI Machine Code Quiz Version 0.0.3-rc.3
retiquiz 202502260900 16
...
INSTRUCTION                    ; PC        CODE
STOREIN1 10                    ; 00000000  900000_a
JUMP>= 1                       ; 00000001  _8000001
JUMP 0                         ; 00000002  f_000000
...
  • 16 Instruktionen, jeweils eine fehlende Hex-Ziffer (_)
  • Gegeben: Instruktion (Assembler-Mnemonic + Operanden), PC, unvollständiger Maschinencode
  • Befehlstabelle wird mitgeliefert (siehe oben)
  • Für irrelevante Bits (*): 0 eintragen

Lösungsschritte am Beispiel

STOREIN1 10 ; 900000_a — fehlt das letzte Nibble (Bits 3–0):

  • STOREIN1: Typ=10, Modus=01 → Bits 31–28 = 1001 = 9 ✓
  • → Bits 23–0 = 00000A
  • Letztes Nibble = A → Lösung: 9000000A

JUMP>= 1 ; _8000001 — fehlt Bit 31–28 (erstes Nibble):

  • JUMP>=: Typ=11, C=011 → Bits 31–27 = 11011
  • Bits 31–28 = 1101 = D... aber Wait: Bits 31–30 = 11, Bits 29–27 = 011 → Bit 28 = 0
  • Bits 31–28 = 1100 → D? Nein: 11 0 (Bit 29) 1 (Bit 28) → 1101 = D
  • Korrekt: JUMP>= hat (Bits 29–27), Typ = 11 (Bits 31–30)
  • Bits 31–28 = 1 1 0 1 → Hmm, Bit 29 ist Teil von C. C = 011 →
  • Bits 31–28 = = D
  • Lösung: D8000001

Tipp: Immer zuerst die Bits 31–30 (Typ) bestimmen, dann je nach Typ die weiteren Felder. Die Hex-Ziffern entsprechen jeweils 4 Bits.

Beispiel-Programme

Swap:

Vertauscht die Inhalte von Speicherzelle 0 und 1 über Hilfszelle 2.

LOAD 0       ; ACC := S(0) = x
STORE 2      ; S(2) := ACC = x  (x sichern)
LOAD 1       ; ACC := S(1) = y
STORE 0      ; S(0) := ACC = y  (y nach S(0))
LOAD 2       ; ACC := S(2) = x
STORE 1      ; S(1) := ACC = x  (x nach S(1))

Indirekte Adressierung: Kopiere nach 

LOAD 0        ; ACC := S(0) = x
MOVE ACC IN1  ; IN1 := ACC = x
LOAD 1        ; ACC := S(1) = y
STOREIN1 0    ; S(x) = S(IN1+0) := ACC = y

Multiplikation durch wiederholte Addition:

, , . Berechnet durch -fache Addition von .

LOADI 0       ; ACC := 0
STORE 2       ; S(2) := 0  (Ergebnis)
LOAD 1        ; ACC := S(1) = y
SUBI 1        ; ACC := ACC - 1
STORE 1       ; S(1) := ACC  (y dekrementieren)
JUMP< 5       ; falls ACC < 0: PC := PC + 5 (Schleife verlassen)
LOAD 2        ; ACC := S(2)  (aktuelles Ergebnis)
ADD 0         ; ACC := ACC + S(0) = ACC + x
STORE 2       ; S(2) := ACC  (Ergebnis aktualisieren)
JUMP -7       ; PC := PC - 7 (zurück zum Schleifenanfang)
JUMP 0        ; PC := PC + 0 (Endlosschleife = Halt)

GGT (Größter gemeinsamer Teiler)

Berechnet mit , , Ergebnis in .
Methode: , .

; Initial: M(40) = x, M(41) = y, M(42) = 0 (Ergebnis)
LOAD 41       ; ACC := y
JUMP= 10      ; falls y == 0: Sprung zum Ende
LOAD 40       ; ACC := x
SUB 41        ; ACC := x - y
JUMP> 4       ; falls x > y: x > y, also x durch Differenz ersetzen
; hier: x <= y, also y durch y - x ersetzen
LOAD 41       ; ACC := y
SUB 40        ; ACC := y - x
STORE 41      ; M(41) := y - x
JUMP 2        ; zurück zum Schleifenanfang
; hier: x > y
STORE 40      ; M(40) := x - y
JUMP -8       ; zurück zum Schleifenanfang (LOAD 41)
; Ende: y == 0, Ergebnis ist x
LOAD 40       ; ACC := x (= ggt)
STORE 42      ; M(42) := ggt
JUMP 0        ; Halt

Siehe Blatt02 Aufgabe 3 für die ursprüngliche Aufgabenstellung.

Fibonacci (iterativ)

Berechnet und speichert in .
Eingabe: in .

; Pseudocode:
; f0 := 0, f1 := 1
; for i := 0 to n:
;   M(100+i) := f0
;   temp := f0 + f1
;   f0 := f1
;   f1 := temp

LOADI 0       ; ACC := 0
STORE 100     ; M(100) := f(0) = 0
LOADI 1       ; ACC := 1
STORE 101     ; M(101) := f(1) = 1 (wird überschrieben in Schleife)
; Hauptschleife
LOAD 99       ; ACC := n
SUBI 1        ; ACC := n - 1
JUMP< 20      ; falls n-1 < 0 (d.h. n=0): fertig
STORE 99      ; n := n - 1 (Zähler)
LOAD 100      ; ACC := f0
ADD 101       ; ACC := f0 + f1
STORE 102     ; temp := f0 + f1
LOAD 101      ; ACC := f1
STORE 100     ; f0 := f1
LOAD 102      ; ACC := temp
STORE 101     ; f1 := temp
JUMP -10      ; zurück zum Schleifenanfang
JUMP 0        ; Halt

Siehe Blatt02 Aufgabe 2c und Blatt11 Aufgabe 6 für die vollständigen Aufgaben.

Übungsblätter

Blatt Aufgabe Thema Wikilink
2 2c Fibonacci in ReTI Blatt02
2 3 GGT in ReTI Blatt02
4 2 retiquiz Machine Code Quiz Blatt04
11 2 Treiber in Execute-Phase Blatt11
11 3 Minimale Befehlsmenge für alle Treiber Blatt11
11 6 Fibonacci in ReTI (mit Pseudocode) Blatt11

Quellen

Quelle Titel Wikilink
Folie 1.2 Beispielrechner ReTI k120-Beispielrechner_ReTI
Folie 2.3 Anwendung ReTI (32-Bit, Formate) k230-Anwendung_ReTI
Folie 4.6 Kontrolllogik von ReTI k460-Kontrolllogik_von_ReTI
Zusatzmaterial Befehlstabelle der ReTI Befehlssatz-ReTI
Klausur A2 — ReTI Machine Code Quiz Exam
Probeklausur A2 — ReTI Machine Code Quiz probeklausur

Priorität

CRITICAL — 16 Punkte in der Klausur (A2). Die Aufgabe ist rein mechanisch (Encode/Decode), erfordert aber Übung für Geschwindigkeit. Die Befehlstabelle wird mitgeliefert, daher ist weniger Auswendigwissen nötig als oft angenommen — entscheidend ist:

  1. Register-Kodierung auswendig: 00=PC, 01=IN1, 10=IN2, 11=ACC
  2. Typ-Bits auswendig: 01=Load, 10=Store, 00=Compute, 11=Jump
  3. Schnelles Encode/Decode üben mit retiquiz
  4. Zweierkomplement für negative Immediates beherrschen
  5. Irrelevante Bits (*) → immer 0 eintragen

Mindestens 3–4 Durchgänge mit retiquiz <matrikelnummer> vor der Klausur empfohlen.