Kapitel 4.0-4.2

• Startproblem: welche Programmabläufe werden parallelisiert (bzw. lassen sich überhaupt parallelisieren)?

• Lösung sollte (idealerweise) aus dem Problem entwickelt werden, so dass auch ungewöhnliche, neue parallele Grundstrukturen entstehen

• Aber: häufig wird auf gewisse, bekannte Grundstrukturen zurückgegriffen

• Manuell : explizit durch den Programmierer

• Halbautomatisch : unterstützt durch geeignete Werkzeuge, die eng mit dem Programmierer kooperieren und diesem Lösungen vorschlagen

• Automatisch : parallelisierende Compiler

• In einem parallelen Programm sollte die Datenverteilung derart vorgenommen werden, dass Datenzugriffe zum überwiegenden Teil (oder nach Möglichkeit fast ausschließlich) als lokale Speicherzugriffe stattfinden

• Die Notwendigkeit der Lokalität ermisst sich aus der Architektur und dem tatsächlichen, technischen Verhältnis von lokaler zu entfernter Zugriffszeit, die teilweise signifikant unterschiedlich sein kann (Faktor 100 10.000)

• Verhältnis von Berechnungs zu Kommunikationsschritten (computation communication ratio) lässt sich daraus ableiten

• Wie viele Befehle sollten mindestens sequentiell in den parallelen ausgeführten Programmteilen ausgeführt werden, bis der nächste Synchronisations oder Kommunikationsschritt durchgeführt wird

Heuristische Vorgehensweise in 4 Phasen von der Problemspezifikation zum parallelen Programm

1. Partitionierungsphase

• Berechnungsschritte und Daten, auf denen die Berechnungen ausgeführt werden, werden in kleine Aufgaben aufgeteilt

• Systemspezifika werden ignoriert

• Hauptziel: möglichst viel Parallelität entfalten

2. Kommunikationsphase

• Kommunikationsanforderungen festlegen, d.h. die zur

• Aufgabenkoordination notwendige Kommunikation wird festgestellt und es werden geeignete Kommunikationsstrukturen und Algorithmen definiert

Fokus von Phase 1 und 2:

• Entfaltung von Parallelität und guter Skalierbarkeit; Suche nach einem Algorithmus mit diesen Eigenschaften

3. Bündelungsphase (Aggregation, agglomeration)

• Aufgaben und Kommunikationsstrukturen werden bezüglich der Leistungsanforderungen und ihren Implementierungskosten evaluiert

• Falls notwendig, Aufgaben zu umfassenderen Aufgabenbereichen zusammenfassen, um die Leistung zu erhöhen oder Entwicklungskosten zu sparen

4. Abbildungsphase

• Zuordnung der Aufgaben zu den Prozessoren unter Berücksichtigung von maximaler Prozessorauslastung bei minimalen Kommunikationskosten

• Prozessorzuteilung statisch vom Compiler oder dynamisch zur Laufzeit durch Lastbalancierungsalgorithmen

Fokus von Phase 3 und 4:

• Berücksichtigung von Aspekten der Lokalität und weiterer leistungsorientierter Eigenschaften

• Soll Möglichkeiten der parallelen Ausführung aufzeigen

• Suche nach feingranularer Aufteilung, mit möglichst vielen kleinen

• Tasks -> größtmögliche Flexibilität für nachfolgende Stufen des Entwurfsprozesses

• Gute Partitionierung unterteilt sowohl die Berechnungsschritte als auch die zugehörigen Daten

• Gebietszerlegung domain decomposition

  • Ausgehend von Datenpartitionierung, danach werden zugehörige Berechnungsschritte hinzugenommen

• Funktionszerlegung functional decomposition

• Ausgehend von Berechnungsschritten, danach werden die davon abhängigen Daten partitioniert

• Komplementäre Techniken, die aber auf unterschiedliche Teile eines Programm gleichermaßen angewendet werden können

  • Oder zur Gewinnung alternativer Partitionierungen

Domain decomposition (o.a. Datenparallelität)

• Daten werden in Datenbereiche, die minimale Kommunikation und eine gute Lastbalance erwarten lassen, unterteilt

• Anweisungsblock, Funktion oder ganzes Programm (SPMD) wird gleichzeitig auf den unterteilten Datenpartitionen angewendet

• Operation kann auch Daten mehrerer Task benötigen -> Kommunikation erforderlich, um Daten zwischen den Tasks zu transportieren

• Zu zerlegende Datenmenge kann die Eingabedaten, die Ausgabedaten oder die Daten, die während der Berechnung anfallen, betreffen

• Statische Struktur: Compiler bzw. Programmierer legt die Aufteilung fest; kann nicht auf unterschiedlich lange Aktivitäten reagieren

• Dynamische Struktur: Zur Laufzeit vom Programm durchgeführte Last Balancierung sorgt für gleichmäßig Datenzerlegung (i. S. d. Zeitbedarfs zur Bearbeitung)

Daumenregel

• Konzentration entweder auf die größte Datenstruktur oder auf die Datenstruktur, auf die am häufigsten zugegriffen wird

Functional decomposition (o.a. Funktionsparallelität)

• Primäre Betrachtung der notwendigen Berechnungsschritte

• Zusammenfassung dieser zu Programmkomponenten (Funktionen, Prozeduren, Anweisungsblöcke), die parallel zueinander auf unterschiedlichen Prozessoren ausgeführt werden

• Für jede Komponente muss ein eignes Programm , eine eigene Funktion oder ein eigener Anweisungsblock geschrieben werden

• Häufig eingeschränkter Parallelitätsgrad und Skalierbarkeit

• Anschließend werden die Datenanforderungen der Tasks betrachtet

• Idealfall: Daten können disjunkt den Tasks zugeordnet werden

• Häufig werden Daten von mehreren Tasks benötigt -> Kommunikation

  • Z.B. mit Makro Pipeling auf Software --/Programmkomponenten Ebene

  • Fällt sehr viel Kommunikation an -> ggf. domain decomposition besser

• Funktionszerlegung wird seltener angewendet als Gebietszerlegung

• Führt oft zu einer guten Problemzerlegung, die bei der Modularisierung der Programme hilft

• Typischerweise wird die Berechnung, die von einem Task ausgeführt wird, Daten von anderen Tasks benötigen

  • Dieser Informationsfluss wird in der Kommunikationsphase bestimmt

• Kommunikation zwischen Tasks durch einen Kanal abstrahieren, der die beiden Tasks entweder gerichtet oder ungerichtet verbindet und über den ein Task einem anderen Task Nachrichten senden kann

• Kommunikation kann im Algorithmus so spezifiziert werden, dass zunächst die Kanäle festgelegt werden und anschließend die Nachrichten, die über die Kanäle fließen, bestimmt werden

  • Kommunikationsstruktur lässt sich durch Verwendung von Tasks und Kanälen auch grafisch gut veranschaulichen

Bei Gebietszerlegung:

• Kommunikationsanforderungen sind häufig schwer zu bestimmen

Bei Funktionszerlegung:

• Kommunikationsanforderungen entsprechen meist einem natürlichen Datenfluss zwischen den Tasks

Lokale Kommunikation

• Jeder Task kommuniziert nur mit direkten (d.h. wenigen) Nachbarn

• Beispiel: Gebietszerlegung von matrixstrukturieren Daten

Globale Kommunikation

• Jeder Task kommuniziert mit jedem anderen oder mit einer Anzahl nicht benachbarter Tasks

• Beispiel: zentralisierter Algorithmus (Master Worker)

Strukturierte Kommunikation

• Kommunikationsanforderungen erzeugen ein regelmäßig angeordnetes Muster der Kanäle zwischen den Tasks, z.B. eine Netz --, eine Baum --, eine Ring oder eine Kettenstruktur

Unstrukturierte Kommunikation

• Erzeugt einen beliebigen Graphen

• Verkompliziert meist die Bündelungsphase

Statische Kommunikation

• Kommunikationspartner bleiben für die gesamte Berechnung immer die gleichen

Dynamische Kommunikation

• Kommunikationspartner werden von Berechnungsergebnissen zur Laufzeit bestimmt und können sich ändern

Synchrones Kommunikationsmuster

• Produzierende und konsumierende Tasks arbeiten in koordinierter Weise

• Die Kommunikation geschieht zwischen allen produzierenden und allen

konsumierenden Tasks gleichzeitig

• Asynchrones Kommunikationsmuster

• Kommunikationsanforderungen entstehen unregelmäßig

• Tasks können nicht erkennen, wann andere Tasks ihre Daten benötigen

• Konkrete Entscheidungen unter Berücksichtigung der Zielarchitektur

  • Tasks verschmelzen?

  • Daten replizieren?

  • Berechnungsschritte mehrfach ausführen?

• Abhängig von der Zielarchitektur kann die Anzahl der Tasks, welche durch die Bündelung erreicht werden soll, genau der Anzahl der Prozessoren der Zielmaschine entsprechen oder größer sein

1. Reduzieren der Kommunikationskosten durch Erhöhen der Berechnungs und Kommunikationsgranularität

2. Beibehalten der Flexibilität bezüglich Skalierbarkeit und für die Abbildungsphase

3. Reduzieren der Kosten des Softwareengineering

Bei Verschmelzen von Tasks steht die Reduktion der Kommunikations häufigkeit im Vordergrund

• Hohe Kosten durch Warten auf Empfang von Nachrichten

• Senkung durch weniger und weniger häufiges Übertragen von Daten

• Senkung durch Verschmelzen von Daten

Oberfläche versus Volumen Effekt (Surface to Volume Effect)

• Kommunikationsanforderungen eines Tasks sind proportional zu der Oberfläche des Teilbereichs, auf der er arbeitet, während die Berechnungsanforderungen proportional dem Volumen des Teilbereichs sind

Replizierte Berechnungen

• Kommunikationskosten können eingespart werden, wenn dafür Berechnungen von verschiedenen Tasks mehrfach ausgeführt werden

Verschmelzen nacheinander auszuführender Tasks

• Kommunikationskosten können eingespart werden, wenn eine Anzahl von Tasks nicht parallel ausgeführt werden kann

Erhalten der Flexibilität

• Skalierbarkeit des Algorithmus sollte nicht unnötig beeinträchtigt werden

• Wichtig für Portierbarkeit und Skalierung des Algorithmus ist, dass eine variierende Anzahl von Tasks erzeugt werden kann

• Zu starkes Verschmelzen der Tasks kann hinderlich sein

Festlegung auf welchen Prozessoren die Tasks ausgeführt werden

• Ziel: Minimierung der Gesamtausführungszeit , wobei zwei Strategien benutzt werden:

  • Tasks werden so platziert, dass parallel ausführbare Tasks auf verschiedenen Prozessoren ausgeführt werden

  • Tasks, die häufig miteinander kommunizieren, werden auf demselben Prozessor oder zumindest auf benachbarten Prozessoren angeordnet

Einschränkende Randbedingungen

• Beide Strategien können im Konflikt zueinander stehen

• Begrenzung der Anzahl der Tasks pro Prozessor kann vorhanden sein

Abbildungsproblem ist NP vollständig, doch gibt es effiziente

Heuristiken

• Gebietszerlegung: oft feste Anzahl etwa gleich großer Tasks und strukturierte lokale oder globale Kommunikationsmuster

  • Tasks so platzieren, dass Interprozessorkommunikation minimiert wird

  • Eventuell weitere Aggregation von Tasks, die auf demselben Prozessor abgebildet werden

• Ungleichmäßig großen Tasks oder bei unstrukturierten Kommunikationsmustern: Verwendung eines dynamischen Lastbalancierungsalgorithmus

  • Ebenso falls die Anzahl der Tasks oder die Berechnungsmenge der einzelnen Tasks sich dynamisch ändert

• Funktionszerlegung: oft viele kurzlebige Tasks, die sich zu Beginn oder am Ende der Programmausführung mit anderen Tasks koordinieren

  • Task Scheduling Algorithmen sind zu empfehlen, die Tasks auf Prozessoren verteilen, sobald diese untätig sind