= Datum der Prüfung
18.07.2011
= Benötigte Lernzeit als Empfehlung
Skript, Aufzeichnungen
= Verwendete Materialien (Bücher, Skripte etc...)
= \"Atmosphäre\" der Prüfung / Verhalten der Beisitzer
= Prüfungsfragen
1) Kombinatorische Rechenschaltung entwerfen. A, B seien zwei 4-Bit Zahlen im Zweierkomplement und die umzusetzenden Gleichung ist D=A-B.
a) Rechenbeispiel-Tabelle ausfüllen
b) Schaltbelegungstabelle ausfüllen
c) Schaltfunktion angeben
d) Schaltfunktion für Berechnung der Übertrages
e) Funktion für Carry-Look-Ahead für Übertrag 

2) Ein Automat ist als Zustandsgraph gegeben.
a) Zustandsübergangstabelle aufstellen
b) Minimalisierte Gleichung angeben
c) vollständigen Logik Plan angeben

3) (14 Punkte) Befehlsformat entwerfen.
 - 16 Mega Worte (Wort-adressierbarer Speicher)
 - Adress-Arten: Mem-Direkt, Reg-Direkt, Reg-Indirekt, Reg-Indirekt-Pos.-inkrement, Reg-index (16 Bit Index)
 - 2-Adressmaschine
 a) Befehlsformat (10P)
b) 0-,1-,2-,3- Adressmaschinen beschreiben

4) (14P) Register-, Speicherinhalt gegeben, wie verhält sich der Inhalt bei ein paar Assemblerbefehlen.

5) (14P) Prozessorarchitektur als Grafik gegeben.
a) Mikro-Befehle für SUB (R2)+, X(R3), R1 angeben
b) Ausführungzeit gesucht. (pro Mikroprogrammbefehl 1ms, Memzugriff=50ms)

6) (10P) Multiple Choice
a) Das Betriebssystem verwaltet...
b) Superskalarität...
c) Carry Look-Ahead....
d) DMA für IO-Operation...
e) eine Fließkommazahl....

7) (10P) Cache
a) Länge des Tag für eine Cache-line
b) Größe für Zusatztinfo + Tag insgesamt?
c) Durchschnittszugriffszeit (HS: 10Takte, Bit Ratio H= 0,98; HD: 2000 Takte)

8) (10P) Speicherverwaltung
a) Größe der Seitentabelle
b) Größe der Inversen Seitentabelle

= Note (Optional)
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Ich empfand die Prüfung als zu schwer, besonders Logik-Teil war zu anspruchsvoll unter dem Umstand das die Prüfungsthemen nicht eingegrenzt wurden. Die letzten beiden Aufgaben wurden gut in den Übungen durchgesprochen, das war gut machbar. 

Fazit:
Wenig Zeit, viele Aufgaben => viel Wissen, wenig Denken. 

23.7.14 = Datum der Prüfung ca. 2 Wochen mit je 3-4 Stunden täglich = Benötigte Lernzeit als Empfehlung Erst die Folien durchgearbeitet, dann die Übungsaufgaben gelöst (Altklausur hilft sehr!), Wichtig: Fragt ob ihr Taschenrechner in die Klausur mitnehmen dürft. = Verwendete Materialien (Bücher, Skripte etc...) Normale Atmosphäre = \"Atmosphäre\" der Prüfung / Verhalten der Beisitzer = Prüfungsfragen 1. Aufgabe: Rechne Binärzahlen um a) normal b) Zweierkomplement c) Festkommazahl (2 Nachkommastellen) d) mit Vorzeichenbit 2. Aufgabe: Vergleicher für 2 Binärzahlen c_i = 1 bei A > B a) Tabelle ausfüllen (oben 3,2,1,0 / Seite: A, B, c_i, c_(i-1)) b) Schaltbelegungstabelle ausfüllen (a,b, ci-1 als Eingänge, c_i als Ausgang.) c) Minimierung (generate, propagate aus vorheriger Schaltbelegungstabelle ablesen.) c_i = g_i v p_i c_(i-1) + c_4 mit generate und propagate ohne Klammern darstellen. Aufgabe 3: Beweise! Gegeben: A = (a_n, ..., a_1, a_0), B = (b_n, ... , b_1, b_0) (Sei -x als \"nicht x\" zur Lesbarkeit hier definiert) q_i = ( s3 ai bi v s2 ai -bi v s1 -ai bi v s0 -ai -bi ) EQU (BA v ci-1) [ALU Steuervektor] a) B = Q bei S = 1010, BA =1 b) ai EQU -bi EQU ci-1 bei S=0110, BA=0 Aufgabe 4: ALU a) Tabelle ausfüllen x1,x0 für Mux um zwischen vier Befehlen zu wählen: LOAD, AND, SUB, JMP (relativ) [diese links] Oben: x1, x0, S(3:0) A_in BA PC_in PC_next [[gab in der Fragestunde ein Bild dazu wie 0en und 1en ein Mikroprogramm steuer, das war sehr hilfreich]] b) Vereinfachung von Schaltgleichungen: A_in, BA, PC_in, PC_next Aufgabe 5: Sprungvorhersage a) 3 Beschleunigungsarten moderner CPUs nennen b) Warum gibt es einen Zeitverlust bei relativen Sprüngen? Aufgabe 6: Assembleranalyse (Intel X-86) kommentieren des folgenden Programms, f(x) allgemein und bei x = 4 angeben. (sal shiftet die Bits im gegebenen Register um n nach links) x, z seien Speicheradressen. mov ax, [x] sal ax, 3 add ax, [x] sal ax, 2 mov [z], ax Aufgabe 7: Microcode für SUB [R1], 5[R2] entwerfen a) Fetch & Decode (Befehl fürs Decoden: DECODE) b) Execute (Nutzen des Zeitschattens von Lese/Schreibzugriffen. [[Tipp: Ideale Lösung vermutlich in genau der gegebenen Zeilenanzahl]] Aufgabe 8: Cache -32kB Cachelinegröße, - 16 gB Hauptspeicher (byteadressierbar), - Write-Back-Cache, - 8 fach set assoziativ - der Tag-RAM darf höchstens 16 bit je Zeile groß sein! a) Anzahl der Blöcke? b) Wie viele Steuerbits? c) Wie lang ist der Tag? d) Wieviele Sets? e) wie groß ist der Cache? (in mB) Aufgabe 9: Paging - 12 Bit Adressen - 8 virtuelle Seiten - 4 physiche Seiten - 512Byte Seitengröße a) Angabe von Länge der virtuellen und physichen Adressräume b) Tabelle ausfüllen (Adresse | virtuelle Seite | Offset) [Alles in Dezimal angeben!] c) Tabelle für pyhsiche Seitenbelegung ausfüllen = Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...) Viel Wissen in wenig Zeit wiedergeben. Vor allem in praktischen Anwendungen. Nicht zu lange an einer Aufgabe aufhalten, vor allem die späteren Themen nicht unterschätzen, Schwerpunkte aus VL mitnehmen.

= Datum der Prüfung
23.07.2014
= Verwendete Materialien (Bücher, Skripte etc...)
Skript und Wikipedia
= Prüfungsfragen
Zu finden unter:
http://www.directupload.net/file/d/3709/4qywjyna_pdf.htm

= Datum der Prüfung
22.07.15

= Benötigte Lernzeit als Empfehlung
1 Woche, wenn man die Übungsblätter lösen konnte und die VL regelmäßig besucht hat

= Verwendete Materialien (Bücher, Skripte etc...)
Übungsaufgaben und Vorlesungsfolien

= Prüfungsfragen

----------------------------------------------------------------------------

AUFGABE 1

Die Zahl 50,3125 (Basis Zehn) in Binärdarstellung (als Festkommazahl
und unter Verwendung des Zweierkomplements) ist 0110 0100 1010.

a) Wie viele Nachkommastellen hat dieses Festkommaformat?
b) Stellen sie die Zahl 9,5 in diesem Format da.
c) Stellen sie die Zahl -29,875 in diesem Format da.
d) Stellen sie die Zahl 50,3125 als IEEE 754 mit einfacher Genauigkeit dar.

----------------------------------------------------------------------------

AUFGABE 2

Im Folgenden sollen sie einen Mux-4 entwerfen, der mit einer Steuerleitung
S(1:0) von vier eingehenden Signalen x(0), x(1), x(2), x(3) eines auswählt.

S = 00  ->  q = x(0)
S = 01  ->  q = x(1)
S = 10  ->  q = x(2)
S = 11  ->  q = x(3)

Dieses Problem soll auf ein kleineres reduziert werden, deshalb soll zunächst
ein Mux-2 entwurfen werden.

Der Mux zwei erhält ein Signal S als Eingabe und wählt zwischen zwei Symbolen
x(0) und x(1) aus.

S = 0  ->  q = x(0)
S = 1  ->  q = x(1)

a) Füllen sie die Tabelle für den Mux-2 aus:

S x0 x1  | q
---------|---
0  0  0  |
0  0  1  |
0  1  0  |
0  1  1  |
1  0  0  |
1  0  1  |
1  1  0  |
1  1  1  |

b) Geben sie eine minimale Schaltfunktion für den Mux-2 an.

c) Entwerfen sie einen Mux-2 (Gatter) und denken sie sich ein Symbol für ihren
Mux-2 aus.

d) Entwerfen sie nun mit Hilfe ihrer Mux-2 Symbole einen Mux-4.

----------------------------------------------------------------------------

AUFGABE 3

Gegeben war ein Schaltwerk (eine Art Shifter).

a) In wenigen Worten: Was tut die Schaltung?

b) Unten sehen sie einen Signalverlauf für die Eingänge A, C und E. Ergänzen sie
die beiden Ausgangssignale X und Y.

c) Wie könnte man die obige Schaltung auch realisieren, wenn keine Flip-Flops mit
Enable zur Verfügung stehen?

----------------------------------------------------------------------------

AUFGABE 4

Gegeben war unsere ALU mit der Funktion

q = ( (s3ab v s2a-b v s1-ab v s0-a-b) <-> (BA v C-1) )

und dem Steuervektor (s3, s2, s1, s0).

Zeigen sie:

Wenn BA = 0 und S = 0110 dann führt die ALU eine Subtraktion aus, also

Q = A - B - 1 + C-1.

Dazu dürfen sie benutzen, dass diese Gleichung auch der folgenden entspricht:

q = (a <-> b <-> c)

----------------------------------------------------------------------------

AUFGABE 5

Ein Computer hat die Folgende Speicherhierarchie:

Cache: 1 Takt, 0.97 Hitrate
RAM: 30 Takte, 0.91 Hitrate
HS: 2 000 000 Takte

Wie viele Takte braucht ein Speicherzugriff durchschnittlich?

----------------------------------------------------------------------------

AUFGABE 6

mov eax, [ebx+8]
add eax, 1
add ebx, 8
mov [ebx], eax

Wie könnte man diese Befehlsfolge alternativ realisieren, wenn registerindizierte
Adressierung nicht zur Verfügung steht. Verwenden sie nicht mehr Befehle als vier.

----------------------------------------------------------------------------

AUFGABE 7

Gegen war unsere Prozessorarchitektur.

a) Schreiben Sie ein Mikroprogramm, was den nächsten Befehl holt und dekodiert.

b) Gegeben ein kurzes Mikroprogramm. Finden Sie heraus, auf welche Art Operand 1
und Operand 2 adressiert werden.

----------------------------------------------------------------------------

AUFGABE 8

Gegeben ein Write-Back Cache, der 4-Wege-Setassoziativ ist und als Ersetzungs-
strategie LRU benutzt.

Der Cache ist 8 Blöcke groß.
Jeder Block ist 4 Byte groß.
Der Hauptspeicher ist 256 Byte (oder so) groß.
(Byteweise adressiert)

a) Wie viele Sets hat der Cache.

b) Welche Bits werden für Steuerinformationen gebraucht?

c) Wie lang ist das Tag.

Die Hauptspeicherbytes haben die Adressen 0, 1, 2, ...
Die Blöcke werden nummeriert 0, 1, 2, ...

d) Gegeben eine Tabelle:

Byte (dezimale Adresse) | Block
--------------------------------
0                       |
--------------------------------
9                       |
--------------------------------
32                      |
--------------------------------
...                     |


In welchem Block (dezimal) liegen die Adressen?

e) Unten zu sehen war der Cache (Tabellarisch). Kennzeichnen sie, welche Cachelines
zu welchem Set gehören und schreiben sie auf, wie der Cache nach den oben genannten
Zugriffen auf den Hauptspeicher aussieht.

Cacheline   Set   Tag (binär)   Block-Nummer (dezimal)

----------------------------------------------------------------------------

AUFGABE 9

Standart Aufgabe zu virtuellen Speicher und Pages.

----------------------------------------------------------------------------

= Note (Optional)
1.3

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Mehr Wissen als Lernen, aber eigentlich gut zu schaffen.
Viele Aufgaben waren angelehnt an die auf den Übungsblättern,
mit der ALU und dem Steuerwerk sollte man sich auch beschäftigt haben :)

hugo.png
Fachschaft Informatik
Humboldt-Universität zu Berlin

    Prüfungsprotokolle
    Lesen
    Erstellen

Navigation

    Hauptseite
    Die Fachschaft
    Erstsemester
    Service
    Kontakt
    Links

Vorhandene Protokolle
Protokolle (5 gefunden)
Nr. 	Prüfer 	Fach
608 	Leser Prof. 	Algorithmen und Datenstrukturen

Protokoll

Datum der Prüfung:
16.7.2013
Benötigte Lernzeit als Empfehlung:
2 Wochen
Aufgaben:
Das Gedächnisprotokoll der Klausur mit allen Aufgaben und dazugehörigen Puntzahlen liegt als .pdf vor. Ich habe keine Möglichkeit gefunden, diese auf eine Fachschaftsseite hochzuladen, deshalb liegt sie vorrübergehend in der Dropbox:

https://www.dropbox.com/s/888q80fnhalseir/Klausurprotokoll.pdf

Falls der Link nicht mehr funktioniert, oder jemand eine bessere Idee als Dropbox hat bitte eine kurze Email an jonas.marasus@cms.hu-berlin.de schicken, dann lade ich die datei anderswo hoch.

Nr. 	Prüfer 	Fach
689 	Reinhardt, Klaus Prof. Dr. 	Algorithmen und Datenstrukturen

Protokoll

= Datum der Prüfung
25.9.14

= Prüfungsfragen

O-Notation
a) Funktionen ordnen (mit Beweis) n^4/(sqrt(n)*log n); 4^(log n) * log n; n^3 -10n^2 +200
b) (ohne Begründung) je eine Funktion angeben, die
- \in o(n^3) und \in klein-Omega(log n^3) ist
- nicht \in Omega(n log n) und nicht \in O(log n) ist
- \in o(n^4) und \in Theta(n^2-\sqrt(n) +10) ist
c) Zeigen oder widerlegen: f \in Theta (g) und g \in o(h) => f \in O(h)

Sortieren
a) Idee von Countingsort erklären
b) entscheiden und begründen, ob b1) Mergesort und b2) Quicksort Vorsortierung ausnutzen
c) Gegeben sei eine Folge a_1,..,a_n. Dabei wird (a_i, a_j) mit i<j, aber a_i>a_j als sog. falsches Paar definiert. Es sollte ein Algorithmus entworfen werden, der in O(n) alle falschen Paare beseitigt, sofern nur O(n) falsche Paare vorliegen (mit Laufzeitbeweis)

BB[alpha]-Bäume
a) in gegebenem BB[alpha]-Baum für alle Knoten die Balancen angeben
b) Sei alpha zwischen 0 und 1/2 gegeben. Was muss binärer Suchbaum erfüllen, um BB[alpha]-Baum zu sein?
c) für 3 verschiedene alpha-Werte entscheiden, ob der Baum aus a) legitimer BB[alpha]-Baum ist

B-Bäume
a) ein Element in einen gegebenen B-Baum einfügen
b) ein Element aus einem gegebenen B-Baum löschen
c) Wann/warum sind B-Bäume AVL- und BB[alpha] vorzuziehen?

Hashing
a) mit linearem Sondieren
b) mit double Hashing
keine weiterführenden Fragen

Schreibtischtest zu Prim, auch ohne weiterführende Fragen

Heaps und Bäume
a) aus gegebener Zahlenfolge nach Algorithmus aus der VL einen maxHeap aufbauen
b) Hier war die Inorder- und die Preorder-Traversierung eines binären Baumes (kein Suchbaum) gegeben und man sollte daraus den Baum auslesen (Pseudocode zu Inorder- und Preorder-Traversierung war mit angegeben)
c) zwei verschiedene Bäume mit derselben Preorder-Traversierung angeben
d) Beweisen oder widerlegen: Wenn Preorder-Traversierung eines binären Suchbaumes vorliegt, lässt sich daraus eindeutig der Baum bestimmen.

Beweisaufgabe zu Bäumen und einem gegebenen Pseudocode-Algorithmus - hatte leider keine Zeit, mich hiermit zu beschäftigen

Graphalgorithmen
Hier war (verbalisiert) ein All-pairs-shortest-path-Algorithmus gegeben, der u. a. Bellman-Ford und Dijkstra als Teilschritte benutzte
a) Schreibtischtest zu gegebenem Graph
b) Laufzeiten der Teilschritte und Gesamtlaufzeit angeben
c) und d) kleinere Beweise zu Zwischenergebnissen des Algorithmus
e) mit Hilfe der Erkenntnisse aus c) und d) Korrektheit des Gesamtalgorithmus zeigen

= Note (Optional)
2.x

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Die Küraufgaben waren zeitlich kaum zu schaffen (letzlich wurden dann aber auch 10 Punkte aus der Wertung rausgenommen). 


Nr. 	Prüfer 	Fach
690 	Reinhardt, Klaus Prof. Dr. 	Algorithmen und Datenstrukturen

Protokoll

= Datum der Prüfung
25.9.14

= Prüfungsfragen

O-Notation
a) Funktionen ordnen (mit Beweis) n^4/(sqrt(n)*log n); 4^(log n) * log n; n^3 -10n^2 +200
b) (ohne Begründung) je eine Funktion angeben, die
- \in o(n^3) und \in klein-Omega(log n^3) ist
- nicht \in Omega(n log n) und nicht \in O(log n) ist
- \in o(n^4) und \in Theta(n^2-\sqrt(n) +10) ist
c) Zeigen oder widerlegen: f \in Theta (g) und g \in o(h) => f \in O(h)

Sortieren
a) Idee von Countingsort erklären
b) entscheiden und begründen, ob b1) Mergesort und b2) Quicksort Vorsortierung ausnutzen
c) Gegeben sei eine Folge a_1,..,a_n. Dabei wird (a_i, a_j) mit i<j, aber a_i>a_j als sog. falsches Paar definiert. Es sollte ein Algorithmus entworfen werden, der in O(n) alle falschen Paare beseitigt, sofern nur O(n) falsche Paare vorliegen (mit Laufzeitbeweis)

BB[alpha]-Bäume
a) in gegebenem BB[alpha]-Baum für alle Knoten die Balancen angeben
b) Sei alpha zwischen 0 und 1/2 gegeben. Was muss binärer Suchbaum erfüllen, um BB[alpha]-Baum zu sein?
c) für 3 verschiedene alpha-Werte entscheiden, ob der Baum aus a) legitimer BB[alpha]-Baum ist

B-Bäume
a) ein Element in einen gegebenen B-Baum einfügen
b) ein Element aus einem gegebenen B-Baum löschen
c) Wann/warum sind B-Bäume AVL- und BB[alpha] vorzuziehen?

Hashing
a) mit linearem Sondieren
b) mit double Hashing
keine weiterführenden Fragen

Schreibtischtest zu Prim, auch ohne weiterführende Fragen

Heaps und Bäume
a) aus gegebener Zahlenfolge nach Algorithmus aus der VL einen maxHeap aufbauen
b) Hier war die Inorder- und die Preorder-Traversierung eines binären Baumes (kein Suchbaum) gegeben und man sollte daraus den Baum auslesen (Pseudocode zu Inorder- und Preorder-Traversierung war mit angegeben)
c) zwei verschiedene Bäume mit derselben Preorder-Traversierung angeben
d) Beweisen oder widerlegen: Wenn Preorder-Traversierung eines binären Suchbaumes vorliegt, lässt sich daraus eindeutig der Baum bestimmen.

Beweisaufgabe zu Bäumen und einem gegebenen Pseudocode-Algorithmus - hatte leider keine Zeit, mich hiermit zu beschäftigen

Graphalgorithmen
Hier war (verbalisiert) ein All-pairs-shortest-path-Algorithmus gegeben, der u. a. Bellman-Ford und Dijkstra als Teilschritte benutzte
a) Schreibtischtest zu gegebenem Graph
b) Laufzeiten der Teilschritte und Gesamtlaufzeit angeben
c) und d) kleinere Beweise zu Zwischenergebnissen des Algorithmus
e) mit Hilfe der Erkenntnisse aus c) und d) Korrektheit des Gesamtalgorithmus zeigen

= Note (Optional)
2.x

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Die Küraufgaben waren zeitlich kaum zu schaffen (letzlich wurden dann aber auch 10 Punkte aus der Wertung rausgenommen). 

Nr. 	Prüfer 	Fach
733 	Leser Prof. 	Algorithmen und Datenstrukturen

Protokoll

= Datum der Prüfung
10.9.15
= Benötigte Lernzeit als Empfehlung
4 Wochen
= Verwendete Materialien (Bücher, Skripte etc...)
Folien aus Vorlesung, Übung, Tutorium; Internet; Ottmann/Widmayer
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
dritter Prüfungsversuch -> starke Nervosität
Leser beginnt mit etwas Smalltalk (Wie läuft das Studium? Warum 2 mal durchgefallen), Beisitzer waren A. Nonym und ein Protokollant, Stift und Papier wird gestellt
Beisitzer sagen nichts
= Prüfungsfragen
Quick Sort --- wie funktioniert es genau? Komplexität von Worst/Average/Best-Case herleiten - kein genauer Beweis aber gut argumentieren können
Merge Sort --- wie funktioniert es genau? Komplexität von Worst/Average/Best-Case herleiten - kein genauer Beweis aber gut argumentieren können
Suchbäume --- Definition, Wie groß?, Kosten von Einfügen/Löschen, wie funktioniert das Löschen
Starke/schwache Zusammenhangskomponenten --- Was ist das? Wie berechnet man das? Kosaraju-Algorithmus ausführen
= Note (Optional)
bestanden ;)
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Die behandelten Themen werden sehr detailliert behandelt, Leser hilft bei Unsicherheiten weiter, Prüfung ist eher schlecht gelaufen

Nr. 	Prüfer 	Fach
734 	A. Nonym,Susanne 	Algorithmen und Datenstrukturen

Protokoll

= Datum der Prüfung
22.07.15

= Benötigte Lernzeit als Empfehlung
1 Woche, wenn man die Übungsblätter lösen konnte und die VL regelmäßig besucht hat

= Verwendete Materialien (Bücher, Skripte etc...)
Übungsaufgaben und Vorlesungsfolien

= Prüfungsfragen

----------------------------------------------------------------------------

AUFGABE 1

Die Zahl 50,3125 (Basis Zehn) in Binärdarstellung (als Festkommazahl
und unter Verwendung des Zweierkomplements) ist 0110 0100 1010.

a) Wie viele Nachkommastellen hat dieses Festkommaformat?
b) Stellen sie die Zahl 9,5 in diesem Format da.
c) Stellen sie die Zahl -29,875 in diesem Format da.
d) Stellen sie die Zahl 50,3125 als IEEE 754 mit einfacher Genauigkeit dar.

----------------------------------------------------------------------------

AUFGABE 2

Im Folgenden sollen sie einen Mux-4 entwerfen, der mit einer Steuerleitung
S(1:0) von vier eingehenden Signalen x(0), x(1), x(2), x(3) eines auswählt.

S = 00  ->  q = x(0)
S = 01  ->  q = x(1)
S = 10  ->  q = x(2)
S = 11  ->  q = x(3)

Dieses Problem soll auf ein kleineres reduziert werden, deshalb soll zunächst
ein Mux-2 entwurfen werden.

Der Mux zwei erhält ein Signal S als Eingabe und wählt zwischen zwei Symbolen
x(0) und x(1) aus.

S = 0  ->  q = x(0)
S = 1  ->  q = x(1)

a) Füllen sie die Tabelle für den Mux-2 aus:

S x0 x1  | q
---------|---
0  0  0  |
0  0  1  |
0  1  0  |
0  1  1  |
1  0  0  |
1  0  1  |
1  1  0  |
1  1  1  |

b) Geben sie eine minimale Schaltfunktion für den Mux-2 an.

c) Entwerfen sie einen Mux-2 (Gatter) und denken sie sich ein Symbol für ihren
Mux-2 aus.

d) Entwerfen sie nun mit Hilfe ihrer Mux-2 Symbole einen Mux-4.

----------------------------------------------------------------------------

AUFGABE 3

Gegeben war ein Schaltwerk (eine Art Shifter).

a) In wenigen Worten: Was tut die Schaltung?

b) Unten sehen sie einen Signalverlauf für die Eingänge A, C und E. Ergänzen sie
die beiden Ausgangssignale X und Y.

c) Wie könnte man die obige Schaltung auch realisieren, wenn keine Flip-Flops mit
Enable zur Verfügung stehen?

----------------------------------------------------------------------------

AUFGABE 4

Gegeben war unsere ALU mit der Funktion

q = ( (s3ab v s2a-b v s1-ab v s0-a-b) <-> (BA v C-1) )

und dem Steuervektor (s3, s2, s1, s0).

Zeigen sie:

Wenn BA = 0 und S = 0110 dann führt die ALU eine Subtraktion aus, also

Q = A - B - 1 + C-1.

Dazu dürfen sie benutzen, dass diese Gleichung auch der folgenden entspricht:

q = (a <-> b <-> c)

----------------------------------------------------------------------------

AUFGABE 5

Ein Computer hat die Folgende Speicherhierarchie:

Cache: 1 Takt, 0.97 Hitrate
RAM: 30 Takte, 0.91 Hitrate
HS: 2 000 000 Takte

Wie viele Takte braucht ein Speicherzugriff durchschnittlich?

----------------------------------------------------------------------------

AUFGABE 6

mov eax, [ebx+8]
add eax, 1
add ebx, 8
mov [ebx], eax

Wie könnte man diese Befehlsfolge alternativ realisieren, wenn registerindizierte
Adressierung nicht zur Verfügung steht. Verwenden sie nicht mehr Befehle als vier.

----------------------------------------------------------------------------

AUFGABE 7

Gegen war unsere Prozessorarchitektur.

a) Schreiben Sie ein Mikroprogramm, was den nächsten Befehl holt und dekodiert.

b) Gegeben ein kurzes Mikroprogramm. Finden Sie heraus, auf welche Art Operand 1
und Operand 2 adressiert werden.

----------------------------------------------------------------------------

AUFGABE 8

Gegeben ein Write-Back Cache, der 4-Wege-Setassoziativ ist und als Ersetzungs-
strategie LRU benutzt.

Der Cache ist 8 Blöcke groß.
Jeder Block ist 4 Byte groß.
Der Hauptspeicher ist 256 Byte (oder so) groß.
(Byteweise adressiert)

a) Wie viele Sets hat der Cache.

b) Welche Bits werden für Steuerinformationen gebraucht?

c) Wie lang ist das Tag.

Die Hauptspeicherbytes haben die Adressen 0, 1, 2, ...
Die Blöcke werden nummeriert 0, 1, 2, ...

d) Gegeben eine Tabelle:

Byte (dezimale Adresse) | Block
--------------------------------
0                       |
--------------------------------
9                       |
--------------------------------
32                      |
--------------------------------
...                     |


In welchem Block (dezimal) liegen die Adressen?

e) Unten zu sehen war der Cache (Tabellarisch). Kennzeichnen sie, welche Cachelines
zu welchem Set gehören und schreiben sie auf, wie der Cache nach den oben genannten
Zugriffen auf den Hauptspeicher aussieht.

Cacheline   Set   Tag (binär)   Block-Nummer (dezimal)

----------------------------------------------------------------------------

AUFGABE 9

Standart Aufgabe zu virtuellen Speicher und Pages.

----------------------------------------------------------------------------

= Note (Optional)
1.3

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Mehr Wissen als Lernen, aber eigentlich gut zu schaffen.
Viele Aufgaben waren angelehnt an die auf den Übungsblättern,
mit der ALU und dem Steuerwerk sollte man sich auch beschäftigt haben :)

    Datenschutz Über Fachschaft Informatik Impressum 

Inhalt:

1. Binärzahlen:
a)Festkommazahl ist in Dezimal und Zweierkomplement gegeben.
Wie viele Nachkommastellen hat die Zahl?
b)Dezimal zu Fließkommazahl in Zweierkomplement umwandeln
c)Dezimalzahl gegeben. Stelle diese in IEEE 754 Single Precision dar
d)Nenne 3 Möglichkeiten, moderne CPUs zu beschleunigen

2. ALU:
a)Schaltungstabelle ausfüllen: A wird inkrementiert,
setze das Carry sinnvol selber
b)Lies aus der erstellten Tabelle Generate und Propagate ab
c)Erstelle mithilfe der Tabelle einen Logikplan
(also das Teil mit Gattern zeichnen..)

3. Irgendwas anderes zu ALU:
a)Gleichung gegeben (mit S=XXXX und BA = Y), minimiere sie
b)Wie muss S und BA gewählt werden, dass eine Addition
ausgeführt wird?
c)Wie muss S und BA gewählt werden, dass ... ausgeführt wird?
d)Gleichung aus einer Tabelle ablesen

4. Assembler
Assembler-Code gegeben (4 Zeilen).
Stelle den Code anders dar (es wurde register-indiziert
verwendet. Ihr sollt es ohne register-indiziert
darstellen, auch mit maximal nur 4 Zeilen)

5. Pipeline:
Tabelle ausfüllen: Belegung der Pipelinestufen

6. Ausführungszeit:
Irgendwas mit Takten... Berechne durchschnittliche blabla

7. Konflikte durch Abhängigkeiten:
Befehle sind gegeben.
Markiere, wo es Konflikte gibt und nenne die Art
des Konflikts (WAR, RAW, ..)

8. Mikroprogramm
Prozessorarchitektur gegeben (das gleiche wie aus VL und Übung).
Kurze Assembler-Mnemonik gegeben (2 Zeilen).
Schreibe Mikroprogramm dazu

9. Befehlsformat entwerfen.
1. Wort: ..
2. Wort: ..

10. Assembler
Kruzer Assembler-Befehl (4 Zeilen) gegeben.
Beschreibe, was der Code tut und gib die Anzahl der Speicherzugriffe an

11. Virtueller Speicher;
Virtuelle Adressen sind in Dezimal gegeben,
Anzahl virtueller Seiten gegeben, Anzahl physischer
Pages gegeben, Seitengröße gegeben.
a)Berechne Adresslänge von virtuell und physisch
b)Tabelle ausfüllen: Gib die Seite und das Offset
der jeweiligen virtuellen Adresse an
c)physische Seitentabelle ausfüllen

Motivation und Tipp:
Aus meinem Gedankenprotokoll könnt ihr folgern, dass ich ein Lappen bin.
Trotzdem hat ein Lappen wie ich die Prüfung bestanden (Note: 3.X).
Habe die gesamten Semesterferien gelernt, jeden Tag locker
1-2 Stunden.
Geht auf jedenfall ALLE Übungsaufgaben + Musterlösungen durch,
Vorlesungsskript komplett und auch andere, etwas ältere Protokolle auf jeden
reinziehn.
Die sind glücklicherweise nicht so chaotisch wie meins, doch auch nicht fehlerfrei!

1. Binärzahlen:
a)Festkommazahl ist in Dezimal und Zweierkomplement gegeben.
Wie viele Nachkommastellen hat die Zahl?
b)Dezimal zu Fließkommazahl in Zweierkomplement umwandeln
c)Dezimalzahl gegeben. Stelle diese in IEEE 754 Single Precision dar
d)Nenne 3 Möglichkeiten, moderne CPUs zu beschleunigen

2. ALU:
a)Schaltungstabelle ausfüllen: A wird inkrementiert,
setze das Carry sinnvol selber
b)Lies aus der erstellten Tabelle Generate und Propagate ab
c)Erstelle mithilfe der Tabelle einen Logikplan
(also das Teil mit Gattern zeichnen..)

3. Irgendwas anderes zu ALU:
a)Gleichung gegeben (mit S=XXXX und BA = Y), minimiere sie
b)Wie muss S und BA gewählt werden, dass eine Addition
ausgeführt wird?
c)Wie muss S und BA gewählt werden, dass ... ausgeführt wird?
d)Gleichung aus einer Tabelle ablesen

4. Assembler
Assembler-Code gegeben (4 Zeilen).
Stelle den Code anders dar (es wurde register-indiziert
verwendet. Ihr sollt es ohne register-indiziert
darstellen, auch mit maximal nur 4 Zeilen)

5. Pipeline:
Tabelle ausfüllen: Belegung der Pipelinestufen

6. Ausführungszeit:
Irgendwas mit Takten... Berechne durchschnittliche blabla

7. Konflikte durch Abhängigkeiten:
Befehle sind gegeben.
Markiere, wo es Konflikte gibt und nenne die Art
des Konflikts (WAR, RAW, ..)

8. Mikroprogramm
Prozessorarchitektur gegeben (das gleiche wie aus VL und Übung).
Kurze Assembler-Mnemonik gegeben (2 Zeilen).
Schreibe Mikroprogramm dazu

9. Befehlsformat entwerfen.
1. Wort: ..
2. Wort: ..

10. Assembler
Kruzer Assembler-Befehl (4 Zeilen) gegeben.
Beschreibe, was der Code tut und gib die Anzahl der Speicherzugriffe an

11. Virtueller Speicher;
Virtuelle Adressen sind in Dezimal gegeben,
Anzahl virtueller Seiten gegeben, Anzahl physischer
Pages gegeben, Seitengröße gegeben.
a)Berechne Adresslänge von virtuell und physisch
b)Tabelle ausfüllen: Gib die Seite und das Offset
der jeweiligen virtuellen Adresse an
c)physische Seitentabelle ausfüllen

Motivation und Tipp:
Aus meinem Gedankenprotokoll könnt ihr folgern, dass ich ein Lappen bin.
Trotzdem hat ein Lappen wie ich die Prüfung bestanden (Note: 3.X).
Habe die gesamten Semesterferien gelernt, jeden Tag locker
1-2 Stunden.
Geht auf jedenfall ALLE Übungsaufgaben + Musterlösungen durch,
Vorlesungsskript komplett und auch andere, etwas ältere Protokolle auf jeden
reinziehn.
Die sind glücklicherweise nicht so chaotisch wie meins, doch auch nicht fehlerfrei!

= Datum der Prüfung
27.06.2022
= Benötigte Lernzeit als Empfehlung
wenn Hausaufgaben und Praktikum voll(80-90% Punkte) verstanden wurden, 1 Woche
= Verwendete Materialien (Bücher, Skripte etc...)
Folien vom Sommer
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Freundliches. Sehr kleine Schrift an der Tafel. Es gab 2 Klausurtypen A und B mit unterschiedlichen Aufgaben
= Prüfungsfragen

(evtl Unvollständig)
1. -32.25 als 32-bit IEE Fließkommazahl schreiben.
2. 3 Arten nennen, auf die moderne CPUs schneller werden (z.B. Pipelining, Branch Prediction, Register Renaming)
3. Schaltung bauen, die 2 bit eingang hat und zu diesen 1 addiert. (d.h. 2 Bit Ausgang + Overflow Anzeiger Ausgang), DNF((!) (nicht KNF)) Gleichungen für die Ausgänge angeben. Minimieren des jeweiligen Ausgangs mit 2x2 KV Diagrammen. Zeichnen der minimierten Schaltung. 
4. Eine Schaltung bauen, die due Folge (0,1), (1,0), (1, 1) , (1,0) ausgibt, immer wenn ein Takteingang "gedrückt/betätigt" wird (mit D Flipflops), davor Boolsche Gleichungen Minimieren
5. Microcode zur Subtraktion einer Zahl im Hauptspeicher von einer anderen in einen Register
6. Erkennen eines Befehlsformats (Wieviele Bit Opcode, Registeroperanden, Register ?) anhand von 2 Beispielbefehlen (siehe 2016 Altklausur, identisch)
7. Caches: Größe von Tag ausrechnen (mit Set-Assoz. Cache), in welchem Set wird die Adresse 7193 (?) im Set gespeichert (8 Sets gab es insgesamt)? Angegeben in der Aufgabenstellung war Hauptspeichergröße, 4-Fach Set-Assoz. und vieles mehr.
8. Paging: Offset und Seite zu Beispieladressen ausrechnen. Adressraumgröße (Virtuell und physisch) ausrechnen.
9. Page Table ausfüllen (mit LRU strategie)


= Note (Optional)
zufrieden, wurde ~4 Tage später bei Agnes hochgeladen.
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
einfacher als die Altklausuren von 2016.

= Datum der Prüfung: 26.07.2023
= Benötigte Lernzeit als Empfehlung
= Verwendete Materialien (Bücher, Skripte etc...): Hausaufgaben, Altklausuren..
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer: Alles easy, nur war ein Fehler in der Klausur bei Aufgabe 1 (falsche Binärfolge gegeben) was einen verwirrte, aber dafür sind die Studenten dann ja nicht verantwortlich :)
= Prüfungsfragen:
-> x,y,z,xyz,abc sind Variablen, weil ich die genauen Zahlen und Binärfolgen nicht mehr kenne xD

1. Festkommaformat

- Die Zahl x wird im 2er-Komplement als Binärfolge y dargestellt. Wie viele Nachkommastellen hat es?

- Stellen Sie die Zahl z im Festkommaformat(9-bit) 2er-Komplement dar, wovon 4 bit für Nachkommastellen reserviert sind.

- Irgendeine (Rechen-)Frage zu Sprungfehlen

2. 2bit mit 2 multiplizieren und Übertrag

- Schalttabelle, der Übertrag wird genau dann 1 wenn beide Bits/Ausgänge 1 sind

- Schaltfunktion in DNF angeben

- Minimieren mit KV-Diagramm und minimierte Schaltfunktion angeben

3. D-Flip-Flops

- Schalttabelle: Ausgänge waren gegeben, auszufüllen waren die Eingänge

- Minimieren

- Schaltnetz zeichnen

4. Assembler

- Geben Sie für folgenden Befehl xyz die Abfolge an (gegeben war eine Tabelle zum ankreuzen, zB 1. Operand, Befehl holen, Operanden adressieren, Addition durchführen..)

5. Assembler

- Befehlsfolge umschreiben ohne Registerindizierung zu nutzen

-

6. Mikroprogramm

- Mikrobefehle Fehler finden und korrigieren

- Assembler Befehl dazu angeben

7. CPU

- Berechnen Sie die durchschnittliche Zugriffszeit in Takten in einem hierarchischen Speichersystem, das aus x (CPU- Cache, Hauptspeicher...)Ebenen besteht.

-

8. Paging 
(Parameter der Hauptspeicherverwaltung: Seitengröße=, Länge physischer= und virtueller Adressen=)
(Parameter der Cache- Verwaltung: arbeitet mit physischen Adressen, Blockgröße=, Cachegröße=)
Außerdem gegeben Seitentabelle und Tag-RAM des CPU- Caches

- Größe des physischen/virtuellen Speichers (in KiByte) angeben

- Wie viele Einträge passen in die Seitentabelle?

- Geben Sie die physische Adresse an unter der das durch die virtuelle Adresse xyz adressierte Byte erreichbar ist

- Befindet sich die Adresse abc im Cache? Wenn ja, in welcher line?



= Note (Optional): noch unbekannt
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...): Die meisten Aufgaben sind in Altklausuren oder Hausaufgaben zu finden. Wenn das allgemeine Verständnis da ist, gibt es keine bösen Überraschungen.