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
Wann verwenden Sie den Jakobialgorithmus zum Lösen von LGS?
Bei dünn besetzten Matrizen
Welche Bits gibt es bei Cacheeinträgen und wozu werden diese verwendet?
Valid Bit: Prüft, ob Eintrag gültig ist (z B wurde er durch DMA oder andere Prozessoren ungültig gemacht). Dieses Bit wird zwingend beim Prozessor-Reset benötigt (alle V-Bit = 0)
Dirty Bit: Gibt an, ob Eintrag in Speicher zurückgeschrieben werden muss, wenn er durch einen anderen ersetzt wird
Was bedeutet Bisectional Bandwidth?
A bisection is the separation of the network in two equal parts by «cutting» the links
The bisectional bandwidth is the minimum bandwidth through the cut links (often expressed in bandwidth per PE)
Was ist UMA? Was ist CC-UMA?
(Cache Coherent) Uniform Memory Access
Was ist NUMA? Was ist CC-NUMA?
(Cache Coherent) Non-Uniform Memory Access
Zeichnen Sie ein CC-UMA System
Siehe Bild
Was ist das Bottleneck von UMA? Was ist die Lösung dafür?
Zugriff auf den gemeinsamen Speicher / Lösung: Caches
Wo wird SIMD eingesetzt?
Bei GPUs, audio/image processing, usw. Im Allgemeinen, überall wo man dieselbe Instruktion auf verschiedenen Daten ausführen muss.
Was passiert wenn bei Cut-Through ein Paket nicht korrekt weitergeleitet wurde?
Falls man einen vollständig zustandslosen Switch hat (kein Buffer) muss der End-Empfänger sich darum kümmern wie er ein korrektes Paket kriegt (Retransmission)
Bei Switches mit Zustand werden aber Prüfsummen berechnet und so können Fehler schon bemerkt und behoben werden bevor das Paket am Ziel ankommt. Das Paket wird vom vorherigen Node wieder angefordert, indem das Retransmission Signal über den Backchannel gesendet wird. Der vorherige Transmitter sendet das Paket erneut vom Buffer.
https://www.techopedia.com/definition/18641/cut-through-switching
https://en.wikipedia.org/wiki/Cut-through_switching
Wofür steht SMP?
SMP: Symmetric Multiprocessing
SMP beschreibt ein Multiprozessorsystem, in dem mehrere Prozessoren auf einzigen Speicher zugreifen. Die Prozessoren sind dabei jeweils identisch
Wo ist der Bottleneck bei SMP? Wie umgehen?
Bei dem Zugriff auf das Memory.
Durch die Verwendung von Caches. Das Einfachste ist ein write-through Cache mit Snooping.
Was passiert wenn bei Cut-through ein Paket korrekt übermittelt wurde?
Es wird ein Acknowledgement über den Backchannel versendet, und der vorherige Switch kann seine Kopie der Nachricht im Buffer löschen.
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
