Basics Flashcards
Was ist Parallelismus?
Zu einem Zeitpunkt wird mehr als ein Befehl ausgeführt und/oder mehr als ein Paar Operanden verknüpft
Was ist das Ziel von Parallelismus?
Ziel ist es die zu bearbeitende Aufgabe möglichst schnell zu lösen
Was sind mögliche Probleme bei Parallelismus?
Die Unterteilung der Aufgabe, sowie Overhead für Koordination und Kommunikation
Warum nutzt man Parallelverarbeitung?
Für Anwendungen mit hohen Anforderungen an die Rechenleistung, insbesondere bei Simulationen und wirtschaftlich ist es besser billige standard CPUs zu verwenden anstatt speziell entwickelte
Was besagt Moores Law?
Die Rechenleistung von Prozessoren verdoppelt sich alle 18 Monate
Was sind parallele Programme?
Ein paralleles Programm kann als eine teilweise geordnete Menge von Anweisungen betrachtet werden, deren Reihenfolge sich aus den Abhängigkeiten zwischen den Anweisungen ergibt
Wann können Anweisungen parallel ausgeführt werden?
Wenn es zwischen den Anweisungen keine Abhängigkeiten gibt
Was ist Nebenläufigkeit?
Die Anweisungen werden gleichzeitig in mehreren Verarbeitungseinheiten ausgeführt
Was ist Pipelining?
Die Aufgabe ist in sequentielle Phasen zerlegt und unterschiedliche Phasen verschiedener Befehle werden gleichzeitig ausgeführt
Auf welchen Programmierebenen kann Parallelismus angewendet werden?
Es gibt keine konsistente Klassifikation aber mögliche Beispiele sind Maschinenbefehle, Anweisungen und Schleifen, sowie Datenstrukturen
Was ist Datenparallelismus?
Datenparallelismus beschreibt eine Gebietsaufteilung, wie z.B. die sequentielle Berechnung der Kraft aller Sterne in einem gewissen Gebiet
Was ist Taskparallelismus?
Taskparallelismus beschreibt eine Aufgabenaufteilung. Zum Beispiel die zeitgleiche Berechnung von Vorverarbeitung, Berechnung, Nachbearbeitung und Visualisierung
Was ist explicit parallelism?
Datenaustausch, Kommunikation und Synchronisation werden explizit vom Programmierer programmiert. Dieser hat volle Kontrolle
Was ist implicit parallelism?
Implicit parallelism erfolgt durch den Compiler, automatisch oder durch Direktive. Der Compiler generiert Kommunikationscode
Welche Ebenen hat die Systemsicht zur Parallelität?
Programm Level (Job Level) Process Level (Task Level) Block Level Instruction Level Sub-operation Level
Wie wird die Granularität festgelegt und wozu dient sie?
Die Granularität ist festgelegt durch das Verhältnis zwischen Berechnung und Kommunikation. Sie entspricht der Länge der parallelen Aufgabe in einer Teilreihenfolge und beeinflusst den erreichbaren Speedup. Darüber hinaus bestimmt sie die Anforderungen an den Parallelrechner
Welche Granularitäten gibt es und auf welchem Level finden diese statt?
- Coarse-grainded: Programm und Prozess Level
- Mid-grained: Block Level
- Fine-grained: Instruction Level
Welche Abhängigkeiten gibt es?
True/Flow Dependence
Anti Dependence
Output Dependence
Wann besteht eine True/Flow Dependence?
Eine True/Flow Dependence besteht, wenn eine Anweisung lesend auf das Ergebnis einer vorangegangenen Anweisung zugreift, die dort geschrieben wurde
Wann besteht eine Anti Dependence?
Eine Anti Dependence besteht, wenn eine Anweisungen einen Wert schreibt, auf den in der vorangegangenen Anweisung lesend zugegriffen wurde
Wann besteht eine Output Dependence?
Wenn beide Anweisungen in die gleiche Variable schreiben
Welche Dependences können umgangen werden und wie?
Die Anti und Output Dependence können immer durch konsequente Umbenennung von Variablen beseitigt werden
Was ist der Zusammenhang zwischen Datenabhängigkeiten und Synchronisation?
Zwei Anweisungen mit einer Datenabhängigkeit können auf verschiedene Threads verteilt werden, wenn eine korrekte Synchronisation (z.B. durch signal/wait oder Nachrichtenaustausch) durchgeführt wird
Welche Kriterien sind nötig für die Klassifikation von Rechnerarchitekturen nach Flynn?
Wie viele instruction streams und wie viele data streams bearbeitet der Rechner zu einem bestimmten Zeitpunkt
Welche möglichen Klassen gibt es nach Flynn?
SISD: Einprozessorrechner
MIMD: Mehrprozessorrechner
SIMD: Vektorrechner, GPUs
MISD: Existiert nicht
Welche MIMD Computer Klassen gibt es?
NORMA: No Remote Memory Access
UMA: Uniform Memory Access
NUMA: Nonuniform Memory Access
Was sind die Eigenschaften von NORMA?
- Nachrichtengekoppelte Systeme
- Verteilter Speicher, verteilter Adressraum
- Kommunikation über Nachrichten
- Distributed Memory Systeme (DMM)
- Gute Skalierbarkeit
Was sind die Eigenschaften von UMA?
- Speichergekoppelte Systeme
- Globaler Speicher, gemeinsamer Adressraum
- Alle Prozessoren greifen in gleicher Weise und in gleicher Zeit auf den Speicher zu
- Kommunikation und Synchronisation über gemeinsamen Speicher
- Symmetrische Multiprozessoren (SMP), Multicore-CPUs
- Begrenzte Skalierbarkeit
Was sind die Eigenschaften von NUMA?
- Speichergekoppelte Systeme
- Verteilter Speicher, gemeinsamer Adressraum
- Zugriff auf lokalen Speicher schneller als auf entfernten
- Distributed Shared Memory Systeme (DSM)
- Kombiniert gemeinsamen Speicher mit Skalierbarkeit
Was ist ein Cache?
Ein schnelle Zwischenspeicher, in der Nähe der CPU. Er speichert Kopien der zuletzt verwendeten Daten aus dem Hauptspeicher. Wenn sich die Daten im Cache befinden ist kein Zugriff auf den Hauptspeicher erforderlich
Warum sind Caches in Multiprozessor-Systemen wichtig?
Caches sind in Multiprozessor-Systemen unerlässlich, denn sonst können Speicher und Verbindungsnetz schnell zu einem Engpass werden. So wird die Eigenschaft der Lokalität ausgenutzt und jeder Prozess arbeitet meist auf seinen “eigenen” Daten
Was gibt es für Probleme mit Caches?
Die Existenz mehrfacher Kopien kann zu Inkonsistenzen in den Daten führen
Wie kann Cache-Kohärenz sichergestellt werden?
Bei einem Schreibzugriff müssen alle Caches mit Kopien benachrichtigt werden.
Wie kann Cache-Kohärenz in UMA Systemen sichergestellt werden?
Bus dient als Verbindungsnetz, somit ist jeder Zugriff auf den Hauptspeicher für alle sichtbar. Einfache Cache-Kohärenzprotokolle aber schlechte Skalierbarkeit, da der Bus eine gemeinsame, zentrale Ressource ist
Wie kann Cache-Kohärenz in NUMA Systemen sichergestellt werden?
Zugriffe auf den Hauptspeicher sind in der Regel nicht für andere Prozesse sichtbar. Daher müssen die betroffenen Caches explizit benachrichtigt werden. Die Cache-Kohärenzprotokolle werden sehr komplex aber man hat eine gute Skalierbarkeit
Was kann zu unmöglichen Ausgaben trotz Cache-Kohärenz führen?
Bei SMPs und DSMs können CPUs mit dynamischem Befehlsscheduling oder Schreibpuffern zu scheinbar unmöglichen Ausgaben einen Programms führen -> Programmzeilen werden in einer anderen Reihenfolge ausgeführt
Wann liegt eine sequentielle Konsistenz vor?
Eine sequentielle Konsistenz liegt vor, wenn Prozessoren die Speicheroperationen eines parallelen Programms in Programmordnung ausführen
Wozu dienen abgeschwächte Konsistenzmodelle?
Eine sequentielle Konsistenz bedeutet starke Einschränkungen für die Rechnerarchitektur, daher nutzen Parallelrechner mit gemeinsamen Speicher abgeschwächte Konsistenzmodelle. Jeder Prozessor sieht seine eigenen Speicheroperationen, jedoch immer in Programmordnung
Was sind die vier Design Schritte?
- Partitioning
- Communication
- Agglomeration
- Mapping
Was ist data partitioning?
Die Tasks beschreiben identische Aufgaben für einen Teil der Daten und es ist ein hoher Parallelitätsgrad möglich
Was ist task partitioning?
Tasks beschreiben unterschiedliche Teilaufgaben des Problems und können nebenläufig oder als pipeline arbeiten. Der maximale Gewinn entspricht der Zahl der Teilaufgaben
Welche zwei Stufen zur Definition der Kommunikation gibt es?
Die Definition der Kommunikationsstruktur und der zu versendenden Nachrichten
Welche Kommunikationsmuster gibt es?
local vs. global
structured vs. unstructured
static vs. dynamic
synchronous vs. asynchronous
Was sind die Ziele der Agglomeration?
Die Ziele der Agglomeration sind die Reduktion der Kommunikationskosten und die Beibehaltung der Flexibilität
Welche Strategien gibt es beim Mapping?
- Nebenläufige Tasks auf unterschiedliche Prozessoren
2. Kommunizierende Tasks auf einen Prozessor
Welche Mapping Varianten gibt es?
Static Mapping (Feste Zuweisung von Tasks zu Prozessoren zum Programmstart) vs. Dynamic Mapping ( Zuweisung erfolgt zur Laufzeit)
Welche Modelle gibt es für parallele Programme?
- Embarassingly Parallel
- Manager/ Worker Modell
- Work Pool Model
- Divide and Conquer
- Data Parallel Modell SPMD
- Fork/ Join Modell
- Task-Graph Modell
- Pipeline Modell
Was sind Eigenschaften des Embarassingly Parallel Model?
Die zu lösende Aufgabe kann in eine Menge vollständig unabhängiger Teilaufgaben zerlegt werden, die keinen Datenaustausch oder Kommunikation benötigen
Was sind Eigenschaften des Manager/Worker Models?
Es gibt einen Manager, der Tasks erzeugt und diese den Workern zuteilt. Es sind mehrere Manager und sogar eine Hierarchie möglich. Der Manager kann weitere Tasks erzeugen während die Worker arbeiten. Ein mögliches Problem ist, dass der Manager zum Bottleneck werden kann
Was sind die Eigenschaften vom Work Pool Modell?
Es existiert ein zentraler oder verteilter Pool mit einer Liste von zu bearbeiteten Tasks. Die einzelnen Prozesse holen sich die Tasks aus dem Pool. Wichtig ist, dass diese Zugriffe synchronisiert werden müssen und die Prozesse können ggf. auch neue Tasks in den Pool legen
Was sind Eigenschaften von Divide and Conquer?
Es erfolgt eine rekursive Aufteilung der Aufgabe in unabhängige Teilaufgaben. Problem ist dabei die begrenzte Anzahl an Threads.
Was sind die Eigenschaften des Data parallel Modell SPMD?
Man hat eine feste, konstante Anzahl von Prozessoren und eine 1 zu 1 Zuordnung von Tasks zu Prozessoren. Alle Prozesse arbeiten denselben Programmcode ab und man hat meist einen losen synchronen Ablauf bei dem abwechselnde Phasen unabhängiger Berechnungen und Kommunikation/Synchronisation stattfinden
Was sind Eigenschaften des Fork/Join Modell?
Das Programm besteht aus sequentiellen und parallelen Phasen. Für die parallelen Phasen werden die Threads zur Laufzeit erzeugt (Fork) und am Ende der parallelen Phasen erfolgt eine Synchronisation und Beendigung der Threads (Join)
Was sind die Eigenschaften des Task-Graph Modells?
Die Tasks und deren Abhängigkeiten werden als Graph dargestellt. Jede Kante im Graph repräsentiert einen Datenaustausch und die Zuordnung von Tasks zu Prozessoren erfolgt in der Regel so, dass möglichst wenig Kommunikation notwendig wird
Was sind die Eigenschaften des Pipeline Modells?
Ein Strom von Daten wird durch eine Folge von Prozessen geleitet. Die Bearbeitung einer Task startet, sobald ein Datenelement ankommt. Die Pipeline muss nicht notwendigerweise linear sein und zwischen den Prozessen hat man eine Erzeuger-Verbraucher-Synchronisation
Welche Leistungsmetriken gibt es?
Laufzeit, Durchsatz, Speicherbedarf,
Prozessorauslastung, Entwicklungskosten, Wartungskosten
Wie ist die Laufzeit eines Programmes definiert?
Die Laufzeit eines Programmes ist die Zeit zwischen dem Start des Programms und dem Ende der Berechnung auf dem letzten Prozessor
Was ist der Speedup und wie wird er berechnet?
Speedup ist der Laufzeit-Gewinn durch Parallelausführung
S(p) = Ts/T(p)
Wie berechnet man den relativen Speedup?
S(p) = T(1)/T(p)
Wozu dient Amdahls Gesetz?
Amdahls Gesetz liefert eine obere Schranke für den Speedup, denn in der Regel können nicht alle Teile des Programms parallelisiert werden
Was ist Effizienz und wie wird sie berechnet?
Die Effizienz ist ein Maß für die Ausnutzung des Parallelrechners
E(p) = S(p)/p
Was sind Gründe für Leistungsverluste?
Zugriffsverluste Auslastungsverluste Konfliktverluste Komplexitätsverluste Algorithmische Verluste Wegwerfverluste Bremsverluste
Was ist Load Balancing?
Für eine optimale Leistung sollten Prozessoren zwischen zwei (globalen) Synchronisationen gleich lange rechnen
Was sind Gründe für einen Lastungleichgewicht?
- Ungleiche Rechenlast der Tasks (statisch)
- Heterogene Ausführungsplattform (statisch)
- Rechenlast der Tasks ändern sich dynamisch (dynamisch)
- Hintergrundlast auf den Prozessoren (dynamisch)
Welche Vorgehensweisen gibt es beim statischen Lastenausgleich?
Das Ziel beim statischen Lastenausgleich ist die Tasks bei/vor Programmstart so auf die Prozessoren zu verteilen, dass die Rechenlast der Prozessoren identisch ist
Welche Vorgehensweisen gibt es beim dynamischen Lastenausgleich?
Unabhängige Tasks werden dynamisch Prozessoren zugeteilt und bleiben dort bis zum Ende ihrer Bearbeitung mit dem Ziel, dass die Prozessoren nicht untätig werden.
Kommunizierende Tasks werden ggf. zwischen den Prozessen verschoben, um eine gleiche Rechenzeit zwischen Synchronisationen zu gewährleisten
Was sind Metriken für die Leistungsanalyse?
CPU-Zeit (Enthält keine Wartezeiten) Wall Clock Zeit (Mit Blockierungszeiten) Kommunikationszeit und -Volumen Metriken des Betriebssystems Hardware-Metriken
Welche Leistungsanalyse Methoden gibt es?
Sampling
Profiling
Tracing
Was ist Sampling?
Sampling ist eine Leistungsanalyse Methode, bei der regelmäßige Unterbrechungen des Programms zum Auslesen des aktuellen Befehlszählerstandes verwendet werden
Was ist Profiling?
Profiling ist eine Leistungsanalyse Methode, bei der die Auswertung der Ergebnisse während der Erfassung erfolgt
Was ist Tracing?
Tracing ist eine Leistungsanalyse Methode, bei der die Auswertung der Ergebnisse nach Ende des Programmablaufs erfolgt
Was sind Vor- und Nachteile von Sampling?
+ niedrige, vorhersagbare Rückwirkung; Quellcode Bezug
- Begrenzte Genauigkeit, keine Zeitauflösung
Was sind Vor- und Nachteile von Profiling?
+ Reduzierte Datenmenge
- Wenig flexibel
Was sind Vor- und Nachteile von Tracing?
+ Erfassung aller relevanter Daten mit hoher Zeitauflösung
- relativ große Rückwirkungen, große Datenmengen
