Angewandte Computer Architektur - Prüfungsfragen
Karteikarten auf Basis der Prüfungsfragen der Vorlesung Angewandte Computer Architektur
Karteikarten auf Basis der Prüfungsfragen der Vorlesung Angewandte Computer Architektur
Was gibt es für Hazards?
Data Hazard / Structural Hazards / Control Hazards
Was ist ein Data Hazard? Wie verhindern? Zeichne Register Bypass
?
Was ist ein Structural Hazard genau? Wie verhindern? Wie heissen die zwei bekannte Architekturen? Wie die werden heute verwendet?
?
Was ist ein Control Hazard? Wie verhindern? Was ist die einfachste Prediction-Methode? Was für Prediction-Methoden gibt es sonst noch? Reicht 1-bit local Predictor? 2-bit pro branch ist teuer, was kann man dagegen tun?
?
Wie lautet die Formel für die optimale Anzahl Prozessoren für seq. Anteil und Kommunikation?
VL9 Slide 20
Wie funktioniert eine Pipeline?
Man teilt die CPU in einzelne Stufen auf, in denen ein Teil des Befehls ausgeführt wird. Diese Stufen "überlagert" man dann so das jede Stufe bei jedem Zyklus verwendet wird. Es werden dann immer mehrere Befehle gleichzeitig abgearbeitet, aber jeder Befehl ist alleine in einer Stage, deshalb ist es nicht wirklich parallel.
Was gibt es für Stages?
Klassische RISC CPUs haben folgende Stages:
Instruction Fetch -> Instruction Decode -> Operands Fetch -> Execution / (zum Teil) MEM -> Write Back
CISC Architekturen wie x86 verwenden bis zu 20 Stages. (Kann ich aber nicht auswendig, offensichtlich)
Sie als Elektrotechniker kennen bestimmt elektrische Gründe warum man oft langsamer ist als linear, oder?
Keine Ahnung, weil man Transistoren nicht noch kleiner machen kann?
Was ist der Unterschied von ts und ks, tp und kp, tc und kc?
tx = Effektive Zeit für X , kx = Effektive Zeit im Verhältnis zu Ausführung auf einem Prozessor tx / (ts+tp)
Für was wird SIMD verwendet? Wo hat SIMD ihren Ursprung? Für welche neue Technologie wird SIMD jetzt auch noch Verwendet?
Rechenvorgänge für komplexe Video-, Grafik- und 3D-Darstellungen.
Neuerdings wird SIMD (Grafikkartenprozessoren) auch für Deep Learning / Machine Learning (und Computer Vision) verwendet
https://www.quora.com/Why-is-GPU-and-SIMD-useful-in-deep-learning
Wie funktionieren die zwei Arten von Switching, die in der Vorlesung angeschaut wurden?
Bei Store-and-Forward wird die Nachricht solange aufbewahrt bis sie komplett angekommen ist und wird dann weitergeleitet. Bei Cut-Through wird die Nachricht sofort weitergeleitet, wenn die Destination bekannt ist. Es wird die CRC Summe überprüft. Falls diese nicht korrekt ist muss die Nachricht vom vorherigen Transmitter retransmitted werden. Es wird eine Kopie der Nachricht im Buer aufbewahrt.
Wo im Switch wird der Buer integriert?
Input, Output oder Switch Matrix -> eigentlich überall möglich
Sie haben ein Multilayer Perceptron . . ., Laufzeit?
O(n^2)
Welche Arten von Data Hazards gibt es?
WAR, RAW und WAW
Wie kann man RAW Hazards lösen?
Stalling kann man, wie bei jedem Hazard, verwenden. Aber am Besten ist ein Register Bypass
Einfachster Branch predictor?
Immer Taken oder Not Taken, vielleicht auch Random
Advanced Branch Prediction Fragen:
Keine Ahnung was da noch kam.. → Er wollte die Begriffe Tournament Branch Predictor, Local und Global History hören
Wie gross sind solche Histories?
→ 4K reichen und schneiden fast wie ∞ ab.
Keine Antwort
Wie funktioniren Write-Back, Write-Through, Snooping?
Write-Back: Memory erhält ein Dirty Bit = 1 wenn der Inhalt im Cache verändert wird und wird zurückgeschrieben, wenn die Line aus dem Cache ersetzt wird.
Write through: Änderungen im Cache werden gleich in der Memory ergänzt
Snooping: Alle Cache-Controller "hören" auf dem Bus Addressen verwendet werden, die sie selbst im Cache haben. Snoop-Hit on a Write: Stille Invalidierung / Snoop-Hit on a Read: Intervention bei ausstehendem write back.
What does network latency consist of?
- Overhead for sending and receiving a message
- Number of intermediate components and their delay
- Message length
- bandwidth between the source and destination
Ich will ein Gleichungssystem der Ordnung 100'000 mit meinem Laptop, der 1 GFLOPS hat berechnen. Wie lange geht das?
n = 105
Komplexität zum Lösen von Linearen Gleichungsystemen: 2/3 * n3 (Gauss Elimination)
-> n * O(n) / Performance = 2/3 * n^15 / 10^9 = 2/3 * 10^6 Sekunden
Wieviel Speicher wird für die Matrix eines LGS mit Ordnung 105 benötigt? (Datentyp: 8 Byte Float)
Eine Matrix hat n^2 Einträge.
-> 105*2 * 8 Byte = 80GB
Was ist der optimale Speedup für Parallel Processing mit p Prozessoren?
Optimal ist p-facher Speedup
Wie nennt man es man bei Parallelisierung eine Speedup hat der grösser ist als p (= Anzahl Prozessoren) ? Wie ist das möglich?
Das Ist Hyperspeedup.
Passiert, wenn die benötigten Daten in schnelleren Speichern platziert werden können, da mehr Platz da ist.
zBsp. Hauptspeicher statt swap / Cache statt Hauptspeicher.
Was führt dazu, dass man den optimalen Speedupfaktor meist nicht erreichen kann?
Dafür gibt es vier Hauptgründe:
- Serieller Anteil des Codes (Amdahl's Law)
- Kommunikationsanteil (Datentransfers zwischen Prozessoren oder Speicher zu Prozessor)
- Synchronisation und Koordination
- Verteilung des Rechenaufwands (Computation) (Balancieren des Jobs)
Zeichne einen Graphen der aufzeigt, wie sich der Speedup (y-Achse) im Vergleich zur Anzahl Prozessoren (x-Achse) entwickelt. Was wäre ideal? Wie sieht der Graph aus, wenn der Job folgendes enthält: Seriellen Anteil / Synchronisationsanteil / Loadbalancing?
Gibt es einen Begriff für die Sättigung im Seriellen Anteil beim Speedup?
Heisst Amdahl's Law.
Falls man Glänzen möchte: https://de.wikipedia.org/wiki/Amdahlsches_Gesetz
Schreibe die Formel für den Speedup bei Kommunikations-/Synchronisationsanteil auf. (Folgefrage zum Speedupgraph)
VL9 Slide 12
Zur Formel für den Speedup bei Kommunikations-/Synchronisationsanteil: Welche Anzahl von Prozessoren optimiert/maximiert die Formel?
Man nehme die Ableitung und setze sie gleich null.
Vergleiche die Formel für Speedup mit der für den Effekt von Loadbalancing. Was sind die Unterschiede?
Die gesamte parallele Anteil wird durch die n0 Tasks geteilt, statt durch die Anzahl Prozessoren. Der Ceiling Term mit dem dann die Zeit pro Task multipliziert wird, ist für die Berücksichtigung der Tatsache, dass ein Task pro Prozessor gleichzeitig ausgeführt werden kann.
zBsp bei 10 Tasks und 7 Prozessoren wird es immer zweimal die zeit pro Task dauern, da in einem Durchgang nicht alle Tasks erledigt werden können. In dieser Situation ist ein System mit 5 Prozessoren gleich schnell.
Was für Netzwerkarten wurden in der Vorlesung behandelt?
Es wurden Standard LAN (Local Area Network) Technologien wie Ethernet und High-Speed SAN (System Area Network) Technologien angeschaut.
Was gibt es für Topologien für SAN Netzwerke?
- Mesh
- Torus
- 2-Dimensional 2-Torus («k-Ring»)
- Tree
- Fat Tree
- Fully Connected
- Bus
- Hypercube
- Multi Stage Network
- Omega/Shuffle Network
Wie sieht der einfachste Switch aus den man haben kann?
Lösung für unidirektional ist im Bild. (Unidirectional 2-way switch)
Zeichnen Sie ein Multistagenetzwerk mit 3 Layern und solchen (einfachsten) Switches.
Vorl 10 Folie 76
Zeichnen Sie einen Fat Tree mit 2 Layers und 4down/4up.
"Single Switch: 4 Down/4 Up, Layers: 2" (Vorl 10 Folie 68)
Wieviele Prozessoren kann ich mit einem Multistagenetzwerk von k Switches und L Layer verbinden?
k^L
Wieviele Switches braucht man in einem Multistagenetzwerk von k Switches und L Layer?
L* (k^(L-1))
Wieviele Kabel braucht man in einem Multistagenetzwerk von k Switches und L Layer?
(L+1) ꞏ k^L
Zeichnen Sie einen Hypercube 0, 1, 2, 3, 4 Ordnung.
Wichtig! Die Struktur nicht jedes mal neuzeichnen, sondern von Dimension zu Dimension ergänzen
Wie kommt ein Paket in einem Netzwerk an sein Ziel?
Das Paket beinhaltet die notwendigen Informationen, um es an sein Ziel "routen" zu können. In der Vorlesung haben wir Source-based und Destination-based Routing behandelt.
Bei Source-based Routing ist der gesamte Pfad zum Ziel in den Metadaten des Pakets enthalten. Die Switches verwenden diese Daten, um das Paket weiterzuleiten.
Bei Destination-based Routing enthält das Paket nur die Zielinformation und die Switches verwenden ihre eigenen Routing-Infos zum weiterleiten des Pakets.
-
- 1 / 72
-
Lernkarten
Ich will ein Gleichungssystem der Ordnung 100'000 mit meinem Laptop, der 1 GFLOPS hat berechnen. Wie lange geht das?
n = 105
Komplexität zum Lösen von Linearen Gleichungsystemen: 2/3 * n3 (Gauss Elimination)
-> n * O(n) / Performance = 2/3 * n^15 / 10^9 = 2/3 * 10^6 Sekunden
Wieviel Speicher wird für die Matrix eines LGS mit Ordnung 105 benötigt? (Datentyp: 8 Byte Float)
Eine Matrix hat n^2 Einträge.
-> 105*2 * 8 Byte = 80GB
Was ist der optimale Speedup für Parallel Processing mit p Prozessoren?
Optimal ist p-facher Speedup
Wie nennt man es man bei Parallelisierung eine Speedup hat der grösser ist als p (= Anzahl Prozessoren) ? Wie ist das möglich?
Das Ist Hyperspeedup.
Passiert, wenn die benötigten Daten in schnelleren Speichern platziert werden können, da mehr Platz da ist.
zBsp. Hauptspeicher statt swap / Cache statt Hauptspeicher.
Was führt dazu, dass man den optimalen Speedupfaktor meist nicht erreichen kann?
Dafür gibt es vier Hauptgründe:
- Serieller Anteil des Codes (Amdahl's Law)
- Kommunikationsanteil (Datentransfers zwischen Prozessoren oder Speicher zu Prozessor)
- Synchronisation und Koordination
- Verteilung des Rechenaufwands (Computation) (Balancieren des Jobs)
Zeichne einen Graphen der aufzeigt, wie sich der Speedup (y-Achse) im Vergleich zur Anzahl Prozessoren (x-Achse) entwickelt. Was wäre ideal? Wie sieht der Graph aus, wenn der Job folgendes enthält: Seriellen Anteil / Synchronisationsanteil / Loadbalancing?
Gibt es einen Begriff für die Sättigung im Seriellen Anteil beim Speedup?
Heisst Amdahl's Law.
Falls man Glänzen möchte: https://de.wikipedia.org/wiki/Amdahlsches_Gesetz
Schreibe die Formel für den Speedup bei Kommunikations-/Synchronisationsanteil auf. (Folgefrage zum Speedupgraph)
VL9 Slide 12
Zur Formel für den Speedup bei Kommunikations-/Synchronisationsanteil: Welche Anzahl von Prozessoren optimiert/maximiert die Formel?
Man nehme die Ableitung und setze sie gleich null.
Vergleiche die Formel für Speedup mit der für den Effekt von Loadbalancing. Was sind die Unterschiede?
Die gesamte parallele Anteil wird durch die n0 Tasks geteilt, statt durch die Anzahl Prozessoren. Der Ceiling Term mit dem dann die Zeit pro Task multipliziert wird, ist für die Berücksichtigung der Tatsache, dass ein Task pro Prozessor gleichzeitig ausgeführt werden kann.
zBsp bei 10 Tasks und 7 Prozessoren wird es immer zweimal die zeit pro Task dauern, da in einem Durchgang nicht alle Tasks erledigt werden können. In dieser Situation ist ein System mit 5 Prozessoren gleich schnell.
Was für Netzwerkarten wurden in der Vorlesung behandelt?
Es wurden Standard LAN (Local Area Network) Technologien wie Ethernet und High-Speed SAN (System Area Network) Technologien angeschaut.
Was gibt es für Topologien für SAN Netzwerke?
- Mesh
- Torus
- 2-Dimensional 2-Torus («k-Ring»)
- Tree
- Fat Tree
- Fully Connected
- Bus
- Hypercube
- Multi Stage Network
- Omega/Shuffle Network
Wie sieht der einfachste Switch aus den man haben kann?
Lösung für unidirektional ist im Bild. (Unidirectional 2-way switch)
Zeichnen Sie ein Multistagenetzwerk mit 3 Layern und solchen (einfachsten) Switches.
Vorl 10 Folie 76
Zeichnen Sie einen Fat Tree mit 2 Layers und 4down/4up.
"Single Switch: 4 Down/4 Up, Layers: 2" (Vorl 10 Folie 68)
Wieviele Prozessoren kann ich mit einem Multistagenetzwerk von k Switches und L Layer verbinden?
k^L
Wieviele Switches braucht man in einem Multistagenetzwerk von k Switches und L Layer?
L* (k^(L-1))
Wieviele Kabel braucht man in einem Multistagenetzwerk von k Switches und L Layer?
(L+1) ꞏ k^L
Zeichnen Sie einen Hypercube 0, 1, 2, 3, 4 Ordnung.
Wichtig! Die Struktur nicht jedes mal neuzeichnen, sondern von Dimension zu Dimension ergänzen
Wie kommt ein Paket in einem Netzwerk an sein Ziel?
Das Paket beinhaltet die notwendigen Informationen, um es an sein Ziel "routen" zu können. In der Vorlesung haben wir Source-based und Destination-based Routing behandelt.
Bei Source-based Routing ist der gesamte Pfad zum Ziel in den Metadaten des Pakets enthalten. Die Switches verwenden diese Daten, um das Paket weiterzuleiten.
Bei Destination-based Routing enthält das Paket nur die Zielinformation und die Switches verwenden ihre eigenen Routing-Infos zum weiterleiten des Pakets.
Vor / Nachteile von Source-based Routing?
+ Simple switch hardware
+ Simple routing
+ No configuration necessary
- No broad- and multicasts
- No adaptive routing
- Source nodes must know the topology and the distribution of the nodes
- Faults force node reconfiguration
Vor / Nachteile von Destination-Based Routing?
+ Broad- and multicasts possible
+ Adaptive routing possible
+ Nodes must not know anything about the topology
+ Faults are handled by switch management only
+ No processing on source node
- Complex hardware with per-switch routing table
- Per-switch configuration
Welche Arten zum Lösen eines LGS gibt es?
Pivoting, Gauss-Verfahren, Jacobi-Verfahren (für dünn besetzte Matrizen)
Was sind die Laufzeiten von der Verfahren zur Lösung von LGS?
Pivoting: O (2*n3),
Gauss: O (2/3*n3),
Jacobi: O (2n2) pro Iteration
Wenn Sie ein LGS mit n = 10 ′ 000 Unbekannten haben, wie lange braucht ein Prozessor mit 10 GFlops, um dieses LGS mit dem Pivoting-Verfahren zu lösen?
2* (10^4)^3 / 10^10 = 2 * 10^2 = 200
Was ist SIMD? Zeichne eine Skizze von einem SIMD System.
SIMD = Single input , Multiple Data
SIMD ist ein Architektur Modell bei der ein einzelner Befehl auf Hardware-Ebene parallel auf mehrere Datensätze und Prozessoren angewendet wird.
Was ist die Funktion des Enable-Bits bei einer SIMD Architektur?
Das Enable-Bit wird verwendet um die Abläufe zu synchronisieren. Gibt dem Prozessor an, wann er weiter rechnen darf (z.B. bei einem If-Else Branch)
Bsp. Ray Tracing. Wenn alle Strahlen auf der Oberfläche angekommen sind, können wir Pixel berechnen.
Welche wichtigen Charakteristiken eines Netzwerkes interessieren Sie?
Bandbreite, Latenz, Kosten (Design/Implementation/Production), Fehleranfälligkeit, Skalierbarkeit, Bisectional Bandbreite, mögliche Topologien, Features und Qualität des Designs und Implementation.
Zeichnen Sie ein k-Ring mit 8 Knoten und Hop-Distanz 2
Vorsicht! Bei K-Ring verbindet man alle knoten in mehreren Ringen, Zeichnung ist nicht vollständig.
https://www.startpage.com/do/dsearch?query=K-ring+topologie
Given a single processor computer, how to accelerate it?
Caches, Pipelining, Out of Order Execution, Branch Prediction, Increase Clock Frequency, Improve Architecture/Micro-Architecture
What are the three types of caches?
direct mapped, set-associative, fully associative
Which type of cache offers the highest hit rate? What are the drawbacks? (direct mapped, set-associative, fully associative)
Fully associative. Drawback: requires more comparators
How many comparators needed for type of cache? (direct mapped, set-associative, fully associative)
Same number as the number of entries per set
What strategies do we have to evict cache lines?
LRU, FIFO, random
Round-Robin - Nicht in VL behandelt.
https://ieeexplore.ieee.org/document/4484893
What strategy to adopt on a big fully associative cache? (LRU, FIFO, random)
One uses LRU (along with prefetching cache lines / exploit spacial locality and probably other improvements) but comparing plain LRU to Random yields almost the same hit rate.
What replacement strategy for a direct mapped cache?
Not needed, since only one spot is possible for each line of memory.
One can use: \(Replace\ Block = Memory\ Address\ mod\ Number\ of\ Blocks\)
What problems do we have with caches and how to solve them?
The problem is cache coherence (in multi processor or multi application systems).
Use Snoop Logic with Valid Bits
For what is snooping being used apart from CPU Cache Coherence in Multiprocesssor Systems ?
Also used for DMA
https://de.wikipedia.org/wiki/Bus_snooping
What does a switch do when receiving the packet?
The header contains the information how to handle the packet. The packet can either be forwarded before complete reception (wormhole routing) or must be received before forwarding (store-and-forward routing), depending on the switch design
Which one is being used in supercomputers and why? (wormhole routing / store-and-forward routing)
Wormhole because network is very reliable and we target low latency
