Patterns for parallel programming
Advanced Patterns and Frameworks
Advanced Patterns and Frameworks
UE
Units of Execution sind Threads oder Prozesse
PE
Processing Elements sind Prozessoren oder Cores, UE >= PE (es hat mindestens so viele UEs wie PEs)
Vector Unit
Eine Vektor Unit erlaubt das Durchführen von Vektorberechnungen. Beispielsweise kann auf einer Vector-Unit eine Vektoraddition in einem Schritt erfolgen. Ansonsten sind für die Addition eines Vektors n (n= Dimension des Vektors) Schritte notwendig.
Akronyme (SISD, SIMD, MISD, MIMD)
Bei der Verarbeitung von Daten mittels Instruktionen gibt es unterschiedliche Kombinationen, wie die Instruktionen auf die Daten angewandt werden können. Hierbei geht es darum, was in einem CPU-Zyklus verarbeitet wird.
- SISD (Single Instruction, Single Data)
Bei einem SISD wird eine Instruktion auf ein Datenelement angewandt. Ein solches System erlaubt keine parallele Verarbeitung. - SIMD (Single Instruction, Multiple Data)
Bei SIMD wird eine Instruktion parallel auf mehrere Datenelemente angewendet. Dies ist häufig bei GPUs der Fall, welche einen ganzen Vektor mit einer Instruktion verarbeiten können. - MISD (Multiple Instructions, Single Data)
Bei MISD wird auf ein Datenelement mehrere Instruktionen ausgeführt. Dies ist sehr selten, kann jedoch bei trigonometrischen Funktionen sinnvoll sein. - MIMD (Multiple Instructions, Multiple Data)
Bei MIMD werden auf verschiedene Datenelemente verschiedene Instruktionen angewandt. Dies ist der Normalfall bei mehreren Cores/ Prozessoren.
Zähle die Decomposition Patterns mit Ihren Zusammenhang auf
In der Abbildung sind die bei der Decomposition involvierten Patterns mit deren Zusammenhängen illustriert.
Decomposition Strategy
Wie soll ein Problem aufgeteilt werden, damit dieses concurrent ausgeführt werden kann? Dies lohnt sich nur, wenn das Problem gross genug ist und eine Parallelisierung eine signifikante Steigerung der Performance bringt. Hierfür müssen die wichtigsten Datenstrukturen verstanden werden und welche Teile rechenintensiv sind.
Für die Decomposition kann Task- oder Data-Decomposition oder eine Mischung davon verwendet werden.
KURZ: dieses Pattern beschreibt ob ein Problem aufgeteilt werden soll (für die Parallalelisierung) und wie es aufgeteilt werden soll.
Task Decomposition
Bei der Task-Decomposition wird ein Problem in Teilaufgaben geteilt, welche dann parallel ausgeführt werden können.
Hierfür wird das Problem als eine Menge von (nahezu) unabhängigen Tasks betrachtet.
Hierfür müssen die Aktivitäten identifiziert werden, welche individuell und relativ unabhängig sind. Beispiele sind Web-Server, Worker-Pools oder Processing-Pipelines mit asynchronen Filter.
Task Decomposition Pattern - Strategien für die Aufteilung in Tasks
Functional-Splitting Die Aufteilung erfolgt anhand der Funktionen im Programm. Jede Ausführungseinheit (z.B. Thread) ruft eine andere Funktion auf.
Loop-Splitting Jeder einzelne unabhängige Loop oder einzelne Iterationen davon in eigene Tasks splitten (z.B. Summenbildung).
Data-driven decomposition Unterschiedliche Tasks aktualisieren unterschiedliche Dateneinheiten.
Data Decomposition
Bei Rechenintensiven Operationen wird aus einer relativ grossen Menge ähnliche Funktionen auf unterschiedliche Teile angewandt. Beispielsweise bei rekursiven Daten oder Arrays (Matrizen), Matrizen-Multiplikation, Video oder Signalverarbeitung.
Dependency Analysis Patterns
Um die Abhängigkeiten der Tasks zu identifizieren sollten die Tasks zuerst gruppiert, dann sortiert und dann kann das Data-Sharing bestimmt werden.
Group Tasks (Dependency Analysis Patterns)
Durch die zeitliche Gruppierung von Tasks werden deren Zusammenhänge ersichtlich. Hierfür soll die zeitliche Abhängigkeiten der Tasks untereinander festgestellt werden (Abenötigt Daten von B, B → A, Task A muss zum selben Zeitpunkt ausgeführt werden wie Task B.
Aus dieser Gruppierung werden die Abhängigkeiten beim Datenfluss ersichtlich.
Order Tasks (Dependency Analysis Patterns)
Die Tasks sollten in diesem Schritt so sortiert werden, so dass sie die Data-Flow (zeitlichen Anforderungen) erfüllen. Das Ziel ist die Reihenfolge mit den wenigst restriktiven Regeln. Dadurch kann mehr und einfacher parallelisiert werden.
Data Sharing (Dependency Analysis Patterns)
Bei diesem Schritt wird analysiert, wie die Daten über die verschiedenen Tasks verteilt benötigt werden. Das Ziel sollte sein, dass möglichst viele Tasks zusammen gefasst werden können, jedoch auf unterschiedlichen Daten arbeiten.
Allgemein ist darauf zu achten, dass race conditions vermieden werden, jedoch auch nicht unnötig synchronisiert wird. Zudem sollte der Kommunikationsoverhead so tief wie möglich gehalten werden. Die Daten sollten daher in die Gruppen read-only, local to one task und read-write.
Die Read-Write Gruppe muss dann gesondert betrachtet werden, da bei dieser Synchronisationen notwendig sind und Raceconditions entstehen können.
Design Evaluation
Nun ist die Frage, ob mit dem Design Prozess begonnen werden kann. Vorher sollte nochmal geprüft werden, ob das Konzept für die Zielplatform geeignet ist und die Design-Qualitäten simplicity, flexibility und efficancy erfüllt. Hierbei ist auch zu prüfen, ob der Kommunikations-Overhead nicht grösser als der Nutzen sei.
Algorithm Desing Space
In der Abbildung ist der Algorithm Design Space ersichtlich. Der Design-Space hilft einem zu entscheiden, welches Design optimal ist, abhängig von der Reihenfolge die man wählen möchte.
Organize By Tasks (Algorithm Desing Space)
Wenn die Tasks abhängig nach deren Struktur (Logik) ausgeführt werden sollen, dann ist es relevant ob es sich um einen rekursiven Task handelt oder nicht. Bei einem rekursiven Task sollte Divide and Conquer verwendet werden, ansonsten Task parallelism.
Task Parallelism Die Tasks werden so verteilt, dass jede Gruppe von unabhängigen Tasks auf einer eigenen UE ausgeführt wird. Abhängige Tasks werden auf der selben UE ausgeführt um die Abhängigkeiten zu garantieren. Dadurch haben die Tasks auf verschiedenen UE’s keine Abhängigkeiten. Bei der Verteilung auf die UEs sollte darauf geachtet werden, dass die Tasks gleichmässig verteilt werden um eine gute Auslastung über sämtliche UEs zu erreichen.
Divide and Conquer Bei Divide and Conquer wird jedes Teilproblem auf einer eigenen UE ausgeführt. Bei einem Merge-Sort kann z.B. jede Hälfte von einer eigenen UE sortiert werden. Am Ende wird das Resultat vom aufgerufenen Thread gemerged. Dadurch können die Teilprobleme jeweils parallel berechnet werden.
Organize by Data (Algorithm Desing Space)
Sollte die Ausführung anhand der Datenstrukturen organisiert werden, dann ist es relevant, ob es sich um eine rekursive Datenstruktur handelt oder nicht. Wenn die Datenstruktur rekursiv ist, sollte Recursive Data verwendet werden, ansonsten Geometric Decomposition.
Recursive Data (Organize by Data)
Recursive Data Ein Beispiel ist in Abbildung 8.4 sowie Abbildung 8.5 illustriert. In einem ersten Schritt werden die benachbarten Elemente berechnet (also Schritt xi = xi−1 + xi). Hierfür werden n − 1 UEs benötigt. Ist diese Berechnung komplett, dann werden die Elemente im Abstand von 3-Elementen zusammen berechnet xi = xi−2 + xi
Hierfür werden n − 2 UEs benötigt. Für die Addition sämtlicher Werte sind log(n) Runde notwendig, wobei mit jeder Runde eine UE weniger benötigt wird, die Sprünge jedoch grösser werden.
Geometric Decomposition (Organize by Data)
Geometrische Aufteilung der Tätigkeiten in Häpchen, welche dann einzeln gerechnet werden. Siehe Abbildung
Organize by Ordering
Soll die Ausführung anhand der definierten Reihenfolge der Tasks ausgeführt werden, dann ist es relevant, ob die Ausführung sequentiell erfolgt oder ob die Koordination Event basiert erfolgt. Bei sequentieller Abarbeitung sollten die Tasks gemäss dem Pipeline Pattern organisiert werden, ansonst gemäss Event Based Coordination.
Pipeline Processing
Beim Pipeline-processing werden die Tasks in einer definierten Reihenfolge ausgeführt. Das Resultat des vorhergehenden Tasks dient als Input für den folge Task. Jeder einzelne Task wird in einem separaten Thread ausgeführt. Dadurch können sämtliche Schritte zu einem Zeitpunkt ihre Tätigkeit ausführen, wobei die Ausführung auf unterschiedlichen Daten erfolgt (z.B. Task 1 berechnet die Werte E, Task 2 die Werte von D, Task 3 die Werte von C. . . ). Bei den pipes wird zwischen Linearen und nicht linearen Pipes unterschieden. Bei linearen Pipes erfolgt die Verarbeitung ohne Verzweigungen. Enthält die Pipe Verzweigungen handelt es sich um eine nicht-lineare-Pipe.
Event Based Coordination
Beim Event-Based-Coordination erfolgt die Koordination über Events. Dies ist z.B. ein Anwendungsfall bei HTTP-Server, wo die Anfragen event basiert eintreffen.
Der Server verwendet einen Event-Loop und wartet auf Ereignisse. Tritt ein Ereignis auf, dispatched der Server das Ereignis an den konkreten Handler. Der Handler selbst kann wiederum Ereignisse auslösen.
-
- 1 / 22
-
Lernkarten
UE
Units of Execution sind Threads oder Prozesse
PE
Processing Elements sind Prozessoren oder Cores, UE >= PE (es hat mindestens so viele UEs wie PEs)
Vector Unit
Eine Vektor Unit erlaubt das Durchführen von Vektorberechnungen. Beispielsweise kann auf einer Vector-Unit eine Vektoraddition in einem Schritt erfolgen. Ansonsten sind für die Addition eines Vektors n (n= Dimension des Vektors) Schritte notwendig.
Akronyme (SISD, SIMD, MISD, MIMD)
Bei der Verarbeitung von Daten mittels Instruktionen gibt es unterschiedliche Kombinationen, wie die Instruktionen auf die Daten angewandt werden können. Hierbei geht es darum, was in einem CPU-Zyklus verarbeitet wird.
- SISD (Single Instruction, Single Data)
Bei einem SISD wird eine Instruktion auf ein Datenelement angewandt. Ein solches System erlaubt keine parallele Verarbeitung. - SIMD (Single Instruction, Multiple Data)
Bei SIMD wird eine Instruktion parallel auf mehrere Datenelemente angewendet. Dies ist häufig bei GPUs der Fall, welche einen ganzen Vektor mit einer Instruktion verarbeiten können. - MISD (Multiple Instructions, Single Data)
Bei MISD wird auf ein Datenelement mehrere Instruktionen ausgeführt. Dies ist sehr selten, kann jedoch bei trigonometrischen Funktionen sinnvoll sein. - MIMD (Multiple Instructions, Multiple Data)
Bei MIMD werden auf verschiedene Datenelemente verschiedene Instruktionen angewandt. Dies ist der Normalfall bei mehreren Cores/ Prozessoren.
Zähle die Decomposition Patterns mit Ihren Zusammenhang auf
In der Abbildung sind die bei der Decomposition involvierten Patterns mit deren Zusammenhängen illustriert.
Decomposition Strategy
Wie soll ein Problem aufgeteilt werden, damit dieses concurrent ausgeführt werden kann? Dies lohnt sich nur, wenn das Problem gross genug ist und eine Parallelisierung eine signifikante Steigerung der Performance bringt. Hierfür müssen die wichtigsten Datenstrukturen verstanden werden und welche Teile rechenintensiv sind.
Für die Decomposition kann Task- oder Data-Decomposition oder eine Mischung davon verwendet werden.
KURZ: dieses Pattern beschreibt ob ein Problem aufgeteilt werden soll (für die Parallalelisierung) und wie es aufgeteilt werden soll.
Task Decomposition
Bei der Task-Decomposition wird ein Problem in Teilaufgaben geteilt, welche dann parallel ausgeführt werden können.
Hierfür wird das Problem als eine Menge von (nahezu) unabhängigen Tasks betrachtet.
Hierfür müssen die Aktivitäten identifiziert werden, welche individuell und relativ unabhängig sind. Beispiele sind Web-Server, Worker-Pools oder Processing-Pipelines mit asynchronen Filter.
Task Decomposition Pattern - Strategien für die Aufteilung in Tasks
Functional-Splitting Die Aufteilung erfolgt anhand der Funktionen im Programm. Jede Ausführungseinheit (z.B. Thread) ruft eine andere Funktion auf.
Loop-Splitting Jeder einzelne unabhängige Loop oder einzelne Iterationen davon in eigene Tasks splitten (z.B. Summenbildung).
Data-driven decomposition Unterschiedliche Tasks aktualisieren unterschiedliche Dateneinheiten.
Data Decomposition
Bei Rechenintensiven Operationen wird aus einer relativ grossen Menge ähnliche Funktionen auf unterschiedliche Teile angewandt. Beispielsweise bei rekursiven Daten oder Arrays (Matrizen), Matrizen-Multiplikation, Video oder Signalverarbeitung.
Dependency Analysis Patterns
Um die Abhängigkeiten der Tasks zu identifizieren sollten die Tasks zuerst gruppiert, dann sortiert und dann kann das Data-Sharing bestimmt werden.
Group Tasks (Dependency Analysis Patterns)
Durch die zeitliche Gruppierung von Tasks werden deren Zusammenhänge ersichtlich. Hierfür soll die zeitliche Abhängigkeiten der Tasks untereinander festgestellt werden (Abenötigt Daten von B, B → A, Task A muss zum selben Zeitpunkt ausgeführt werden wie Task B.
Aus dieser Gruppierung werden die Abhängigkeiten beim Datenfluss ersichtlich.
Order Tasks (Dependency Analysis Patterns)
Die Tasks sollten in diesem Schritt so sortiert werden, so dass sie die Data-Flow (zeitlichen Anforderungen) erfüllen. Das Ziel ist die Reihenfolge mit den wenigst restriktiven Regeln. Dadurch kann mehr und einfacher parallelisiert werden.
Data Sharing (Dependency Analysis Patterns)
Bei diesem Schritt wird analysiert, wie die Daten über die verschiedenen Tasks verteilt benötigt werden. Das Ziel sollte sein, dass möglichst viele Tasks zusammen gefasst werden können, jedoch auf unterschiedlichen Daten arbeiten.
Allgemein ist darauf zu achten, dass race conditions vermieden werden, jedoch auch nicht unnötig synchronisiert wird. Zudem sollte der Kommunikationsoverhead so tief wie möglich gehalten werden. Die Daten sollten daher in die Gruppen read-only, local to one task und read-write.
Die Read-Write Gruppe muss dann gesondert betrachtet werden, da bei dieser Synchronisationen notwendig sind und Raceconditions entstehen können.
Design Evaluation
Nun ist die Frage, ob mit dem Design Prozess begonnen werden kann. Vorher sollte nochmal geprüft werden, ob das Konzept für die Zielplatform geeignet ist und die Design-Qualitäten simplicity, flexibility und efficancy erfüllt. Hierbei ist auch zu prüfen, ob der Kommunikations-Overhead nicht grösser als der Nutzen sei.
Algorithm Desing Space
In der Abbildung ist der Algorithm Design Space ersichtlich. Der Design-Space hilft einem zu entscheiden, welches Design optimal ist, abhängig von der Reihenfolge die man wählen möchte.
Organize By Tasks (Algorithm Desing Space)
Wenn die Tasks abhängig nach deren Struktur (Logik) ausgeführt werden sollen, dann ist es relevant ob es sich um einen rekursiven Task handelt oder nicht. Bei einem rekursiven Task sollte Divide and Conquer verwendet werden, ansonsten Task parallelism.
Task Parallelism Die Tasks werden so verteilt, dass jede Gruppe von unabhängigen Tasks auf einer eigenen UE ausgeführt wird. Abhängige Tasks werden auf der selben UE ausgeführt um die Abhängigkeiten zu garantieren. Dadurch haben die Tasks auf verschiedenen UE’s keine Abhängigkeiten. Bei der Verteilung auf die UEs sollte darauf geachtet werden, dass die Tasks gleichmässig verteilt werden um eine gute Auslastung über sämtliche UEs zu erreichen.
Divide and Conquer Bei Divide and Conquer wird jedes Teilproblem auf einer eigenen UE ausgeführt. Bei einem Merge-Sort kann z.B. jede Hälfte von einer eigenen UE sortiert werden. Am Ende wird das Resultat vom aufgerufenen Thread gemerged. Dadurch können die Teilprobleme jeweils parallel berechnet werden.
Organize by Data (Algorithm Desing Space)
Sollte die Ausführung anhand der Datenstrukturen organisiert werden, dann ist es relevant, ob es sich um eine rekursive Datenstruktur handelt oder nicht. Wenn die Datenstruktur rekursiv ist, sollte Recursive Data verwendet werden, ansonsten Geometric Decomposition.
Recursive Data (Organize by Data)
Recursive Data Ein Beispiel ist in Abbildung 8.4 sowie Abbildung 8.5 illustriert. In einem ersten Schritt werden die benachbarten Elemente berechnet (also Schritt xi = xi−1 + xi). Hierfür werden n − 1 UEs benötigt. Ist diese Berechnung komplett, dann werden die Elemente im Abstand von 3-Elementen zusammen berechnet xi = xi−2 + xi
Hierfür werden n − 2 UEs benötigt. Für die Addition sämtlicher Werte sind log(n) Runde notwendig, wobei mit jeder Runde eine UE weniger benötigt wird, die Sprünge jedoch grösser werden.
Geometric Decomposition (Organize by Data)
Geometrische Aufteilung der Tätigkeiten in Häpchen, welche dann einzeln gerechnet werden. Siehe Abbildung
Organize by Ordering
Soll die Ausführung anhand der definierten Reihenfolge der Tasks ausgeführt werden, dann ist es relevant, ob die Ausführung sequentiell erfolgt oder ob die Koordination Event basiert erfolgt. Bei sequentieller Abarbeitung sollten die Tasks gemäss dem Pipeline Pattern organisiert werden, ansonst gemäss Event Based Coordination.
Pipeline Processing
Beim Pipeline-processing werden die Tasks in einer definierten Reihenfolge ausgeführt. Das Resultat des vorhergehenden Tasks dient als Input für den folge Task. Jeder einzelne Task wird in einem separaten Thread ausgeführt. Dadurch können sämtliche Schritte zu einem Zeitpunkt ihre Tätigkeit ausführen, wobei die Ausführung auf unterschiedlichen Daten erfolgt (z.B. Task 1 berechnet die Werte E, Task 2 die Werte von D, Task 3 die Werte von C. . . ). Bei den pipes wird zwischen Linearen und nicht linearen Pipes unterschieden. Bei linearen Pipes erfolgt die Verarbeitung ohne Verzweigungen. Enthält die Pipe Verzweigungen handelt es sich um eine nicht-lineare-Pipe.
Event Based Coordination
Beim Event-Based-Coordination erfolgt die Koordination über Events. Dies ist z.B. ein Anwendungsfall bei HTTP-Server, wo die Anfragen event basiert eintreffen.
Der Server verwendet einen Event-Loop und wartet auf Ereignisse. Tritt ein Ereignis auf, dispatched der Server das Ereignis an den konkreten Handler. Der Handler selbst kann wiederum Ereignisse auslösen.
