Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Parallelverarbeitung > Basics > Flashcards

Basics Flashcards

1
Q

Was ist Parallelismus?

A

Zu einem Zeitpunkt wird mehr als ein Befehl ausgeführt und/oder mehr als ein Paar Operanden verknüpft

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Was ist das Ziel von Parallelismus?

A

Ziel ist es die zu bearbeitende Aufgabe möglichst schnell zu lösen

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Was sind mögliche Probleme bei Parallelismus?

A

Die Unterteilung der Aufgabe, sowie Overhead für Koordination und Kommunikation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Warum nutzt man Parallelverarbeitung?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Was besagt Moores Law?

A

Die Rechenleistung von Prozessoren verdoppelt sich alle 18 Monate

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Was sind parallele Programme?

A

Ein paralleles Programm kann als eine teilweise geordnete Menge von Anweisungen betrachtet werden, deren Reihenfolge sich aus den Abhängigkeiten zwischen den Anweisungen ergibt

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Wann können Anweisungen parallel ausgeführt werden?

A

Wenn es zwischen den Anweisungen keine Abhängigkeiten gibt

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Was ist Nebenläufigkeit?

A

Die Anweisungen werden gleichzeitig in mehreren Verarbeitungseinheiten ausgeführt

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Was ist Pipelining?

A

Die Aufgabe ist in sequentielle Phasen zerlegt und unterschiedliche Phasen verschiedener Befehle werden gleichzeitig ausgeführt

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Auf welchen Programmierebenen kann Parallelismus angewendet werden?

A

Es gibt keine konsistente Klassifikation aber mögliche Beispiele sind Maschinenbefehle, Anweisungen und Schleifen, sowie Datenstrukturen

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Was ist Datenparallelismus?

A

Datenparallelismus beschreibt eine Gebietsaufteilung, wie z.B. die sequentielle Berechnung der Kraft aller Sterne in einem gewissen Gebiet

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Was ist Taskparallelismus?

A

Taskparallelismus beschreibt eine Aufgabenaufteilung. Zum Beispiel die zeitgleiche Berechnung von Vorverarbeitung, Berechnung, Nachbearbeitung und Visualisierung

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Was ist explicit parallelism?

A

Datenaustausch, Kommunikation und Synchronisation werden explizit vom Programmierer programmiert. Dieser hat volle Kontrolle

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Was ist implicit parallelism?

A

Implicit parallelism erfolgt durch den Compiler, automatisch oder durch Direktive. Der Compiler generiert Kommunikationscode

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Welche Ebenen hat die Systemsicht zur Parallelität?

A 
Programm Level (Job Level)
Process Level (Task Level)
Block Level
Instruction Level
Sub-operation Level
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Wie wird die Granularität festgelegt und wozu dient sie?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Welche Granularitäten gibt es und auf welchem Level finden diese statt?

A
  • Coarse-grainded: Programm und Prozess Level
  • Mid-grained: Block Level
  • Fine-grained: Instruction Level
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Welche Abhängigkeiten gibt es?

A

True/Flow Dependence
Anti Dependence
Output Dependence

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Wann besteht eine True/Flow Dependence?

A

Eine True/Flow Dependence besteht, wenn eine Anweisung lesend auf das Ergebnis einer vorangegangenen Anweisung zugreift, die dort geschrieben wurde

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Wann besteht eine Anti Dependence?

A

Eine Anti Dependence besteht, wenn eine Anweisungen einen Wert schreibt, auf den in der vorangegangenen Anweisung lesend zugegriffen wurde

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Wann besteht eine Output Dependence?

A

Wenn beide Anweisungen in die gleiche Variable schreiben

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Welche Dependences können umgangen werden und wie?

A

Die Anti und Output Dependence können immer durch konsequente Umbenennung von Variablen beseitigt werden

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Was ist der Zusammenhang zwischen Datenabhängigkeiten und Synchronisation?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Welche Kriterien sind nötig für die Klassifikation von Rechnerarchitekturen nach Flynn?

A

Wie viele instruction streams und wie viele data streams bearbeitet der Rechner zu einem bestimmten Zeitpunkt

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Welche möglichen Klassen gibt es nach Flynn?

A

SISD: Einprozessorrechner
MIMD: Mehrprozessorrechner
SIMD: Vektorrechner, GPUs
MISD: Existiert nicht

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Welche MIMD Computer Klassen gibt es?

A

NORMA: No Remote Memory Access
UMA: Uniform Memory Access
NUMA: Nonuniform Memory Access

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Was sind die Eigenschaften von NORMA?

A
  • Nachrichtengekoppelte Systeme
  • Verteilter Speicher, verteilter Adressraum
  • Kommunikation über Nachrichten
  • Distributed Memory Systeme (DMM)
  • Gute Skalierbarkeit
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Was sind die Eigenschaften von UMA?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Was sind die Eigenschaften von NUMA?

A
  • Speichergekoppelte Systeme
  • Verteilter Speicher, gemeinsamer Adressraum
  • Zugriff auf lokalen Speicher schneller als auf entfernten
  • Distributed Shared Memory Systeme (DSM)
  • Kombiniert gemeinsamen Speicher mit Skalierbarkeit
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Was ist ein Cache?

A

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

31
Q

Warum sind Caches in Multiprozessor-Systemen wichtig?

A

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

32
Q

Was gibt es für Probleme mit Caches?

A

Die Existenz mehrfacher Kopien kann zu Inkonsistenzen in den Daten führen

33
Q

Wie kann Cache-Kohärenz sichergestellt werden?

A

Bei einem Schreibzugriff müssen alle Caches mit Kopien benachrichtigt werden.

34
Q

Wie kann Cache-Kohärenz in UMA Systemen sichergestellt werden?

A

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

35
Q

Wie kann Cache-Kohärenz in NUMA Systemen sichergestellt werden?

A

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

36
Q

Was kann zu unmöglichen Ausgaben trotz Cache-Kohärenz führen?

A

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

37
Q

Wann liegt eine sequentielle Konsistenz vor?

A

Eine sequentielle Konsistenz liegt vor, wenn Prozessoren die Speicheroperationen eines parallelen Programms in Programmordnung ausführen

38
Q

Wozu dienen abgeschwächte Konsistenzmodelle?

A

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

39
Q

Was sind die vier Design Schritte?

A
  1. Partitioning
  2. Communication
  3. Agglomeration
  4. Mapping
40
Q

Was ist data partitioning?

A

Die Tasks beschreiben identische Aufgaben für einen Teil der Daten und es ist ein hoher Parallelitätsgrad möglich

41
Q

Was ist task partitioning?

A

Tasks beschreiben unterschiedliche Teilaufgaben des Problems und können nebenläufig oder als pipeline arbeiten. Der maximale Gewinn entspricht der Zahl der Teilaufgaben

42
Q

Welche zwei Stufen zur Definition der Kommunikation gibt es?

A

Die Definition der Kommunikationsstruktur und der zu versendenden Nachrichten

43
Q

Welche Kommunikationsmuster gibt es?

A

local vs. global
structured vs. unstructured
static vs. dynamic
synchronous vs. asynchronous

44
Q

Was sind die Ziele der Agglomeration?

A

Die Ziele der Agglomeration sind die Reduktion der Kommunikationskosten und die Beibehaltung der Flexibilität

45
Q

Welche Strategien gibt es beim Mapping?

A
  1. Nebenläufige Tasks auf unterschiedliche Prozessoren

2. Kommunizierende Tasks auf einen Prozessor

46
Q

Welche Mapping Varianten gibt es?

A

Static Mapping (Feste Zuweisung von Tasks zu Prozessoren zum Programmstart) vs. Dynamic Mapping ( Zuweisung erfolgt zur Laufzeit)

47
Q

Welche Modelle gibt es für parallele Programme?

A
  • Embarassingly Parallel
  • Manager/ Worker Modell
  • Work Pool Model
  • Divide and Conquer
  • Data Parallel Modell SPMD
  • Fork/ Join Modell
  • Task-Graph Modell
  • Pipeline Modell
48
Q

Was sind Eigenschaften des Embarassingly Parallel Model?

A

Die zu lösende Aufgabe kann in eine Menge vollständig unabhängiger Teilaufgaben zerlegt werden, die keinen Datenaustausch oder Kommunikation benötigen

49
Q

Was sind Eigenschaften des Manager/Worker Models?

A

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

50
Q

Was sind die Eigenschaften vom Work Pool Modell?

A

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

51
Q

Was sind Eigenschaften von Divide and Conquer?

A

Es erfolgt eine rekursive Aufteilung der Aufgabe in unabhängige Teilaufgaben. Problem ist dabei die begrenzte Anzahl an Threads.

52
Q

Was sind die Eigenschaften des Data parallel Modell SPMD?

A

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

53
Q

Was sind Eigenschaften des Fork/Join Modell?

A

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)

54
Q

Was sind die Eigenschaften des Task-Graph Modells?

A

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

55
Q

Was sind die Eigenschaften des Pipeline Modells?

A

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

56
Q

Welche Leistungsmetriken gibt es?

A

Laufzeit, Durchsatz, Speicherbedarf,

Prozessorauslastung, Entwicklungskosten, Wartungskosten

57
Q

Wie ist die Laufzeit eines Programmes definiert?

A

Die Laufzeit eines Programmes ist die Zeit zwischen dem Start des Programms und dem Ende der Berechnung auf dem letzten Prozessor

58
Q

Was ist der Speedup und wie wird er berechnet?

A

Speedup ist der Laufzeit-Gewinn durch Parallelausführung

S(p) = Ts/T(p)

59
Q

Wie berechnet man den relativen Speedup?

A

S(p) = T(1)/T(p)

60
Q

Wozu dient Amdahls Gesetz?

A

Amdahls Gesetz liefert eine obere Schranke für den Speedup, denn in der Regel können nicht alle Teile des Programms parallelisiert werden

61
Q

Was ist Effizienz und wie wird sie berechnet?

A

Die Effizienz ist ein Maß für die Ausnutzung des Parallelrechners
E(p) = S(p)/p

62
Q

Was sind Gründe für Leistungsverluste?

A 
Zugriffsverluste
Auslastungsverluste
Konfliktverluste
Komplexitätsverluste
Algorithmische Verluste
Wegwerfverluste
Bremsverluste
63
Q

Was ist Load Balancing?

A

Für eine optimale Leistung sollten Prozessoren zwischen zwei (globalen) Synchronisationen gleich lange rechnen

64
Q

Was sind Gründe für einen Lastungleichgewicht?

A
  • Ungleiche Rechenlast der Tasks (statisch)
  • Heterogene Ausführungsplattform (statisch)
  • Rechenlast der Tasks ändern sich dynamisch (dynamisch)
  • Hintergrundlast auf den Prozessoren (dynamisch)
65
Q

Welche Vorgehensweisen gibt es beim statischen Lastenausgleich?

A

Das Ziel beim statischen Lastenausgleich ist die Tasks bei/vor Programmstart so auf die Prozessoren zu verteilen, dass die Rechenlast der Prozessoren identisch ist

66
Q

Welche Vorgehensweisen gibt es beim dynamischen Lastenausgleich?

A

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

67
Q

Was sind Metriken für die Leistungsanalyse?

A 
CPU-Zeit (Enthält keine Wartezeiten)
Wall Clock Zeit (Mit Blockierungszeiten)
Kommunikationszeit und -Volumen
Metriken des Betriebssystems
Hardware-Metriken
68
Q

Welche Leistungsanalyse Methoden gibt es?

A

Sampling
Profiling
Tracing

69
Q

Was ist Sampling?

A

Sampling ist eine Leistungsanalyse Methode, bei der regelmäßige Unterbrechungen des Programms zum Auslesen des aktuellen Befehlszählerstandes verwendet werden

70
Q

Was ist Profiling?

A

Profiling ist eine Leistungsanalyse Methode, bei der die Auswertung der Ergebnisse während der Erfassung erfolgt

71
Q

Was ist Tracing?

A

Tracing ist eine Leistungsanalyse Methode, bei der die Auswertung der Ergebnisse nach Ende des Programmablaufs erfolgt

72
Q

Was sind Vor- und Nachteile von Sampling?

A

+ niedrige, vorhersagbare Rückwirkung; Quellcode Bezug

- Begrenzte Genauigkeit, keine Zeitauflösung

73
Q

Was sind Vor- und Nachteile von Profiling?

A

+ Reduzierte Datenmenge

- Wenig flexibel

74
Q

Was sind Vor- und Nachteile von Tracing?

A

+ Erfassung aller relevanter Daten mit hoher Zeitauflösung

- relativ große Rückwirkungen, große Datenmengen

Parallelverarbeitung (4 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions