Kapitel 4.3-4.4

Im Prinzip ein Vertrag zwischen einem Datenspeicher und den darauf zugreifenden Prozessen

• Wenn sich die Prozesse an gewisse Regeln halten, arbeitet der Datenspeicher korrekt

• Erwartung: der Prozessor, der ein Read ausführt, erwartet als Ergebnis den Wert des letzten Write

• Frage: was ist das letzte Write in Abwesenheit einer globalen Uhr?

• Lösung: Einsatz verschiedene Konsistenzmodelle (nicht nur strikt)

• Konsequentestes und einfachstes Konsistenzmodell -

• Modell: Jedes Read liefert als Ergebnis den Wert der letzten Write Operation

• Notwendig dazu: absolute globale Zeit Unmöglich in einem

• Multiprozessorsystem, daher nicht implementierbar

Etwas schwächeres Modell, aber implementierbar; meist vom Programmierer angenommen

• Modell: Wenn mehrere nebenläufige Prozesse auf Daten zugreifen, dann ist jede gültige Kombination von Read- und Write-Operationen akzeptabel, solange alle Prozesse dieselbe Folge sehen

• Jede Permutation der Zugriffe ist zulässig, sofern sie von allen Prozessen so wahrgenommen wird

• (Globale) Zeit spielt keine Rolle

• Unter sequentieller Konsistenz können zwei Läufe desselben Programms unterschiedliche Ergebnisse liefern, sofern nicht explizite Synchronisationsoperationen dies verhindern

Idee: Konsistenz des Speicherzugriffs nicht zu allen Zeiten gewährleisten, sondern nur zu bestimmten, vom Programmierer gesetzten Synchronisationspunkten

• Bedeutung: Einführung kritischer Bereiche, innerhalb derer die Inkonsistenz gemeinsamer Daten zugelassen ist, allerdings müssen konkurrierende Lese/Schreibzugriffe durch den kritischen Bereich unterbunden sein

Bedingungen

• Bevor (im Sinne der Programmordnung) ein Schreib-/Lesezugriff bezüglich eines beliebigen Prozessors ausgeführt werden darf, müssen alle vorhergehenden Synchronisationspunkte erreicht worden sein

• Bevor (im Sinne der Programmordnung) eine Synchronisation bezüglich eines beliebigen Prozessors ausgeführt werden darf, müssen alle vorhergehenden Schreib-/Lesezugriffe ausgeführt worden sein

• Synchronisationspunkte müssen sequentiell konsistent sein

Freigabe-Konsistenz

• Weitere Abschwächung der schwachen Konsistenz

• Idee: Kritische Zugriffe können in kritische Abschnitte geklammert werden 2 Synchronisationsoperationen

• Acquire: verzögert Prozess während ein anderer Prozess ebenfalls auf die Variable zugreift

• Release: alle lokalen Änderungen an den geschützten Daten werden sichtbar gemacht

Entry-Konsistenz

• Weitere Abschwächung der Freigabekonsistenz

• Idee: Alle Daten benötigen eine Synchronisations-/ Schlossvariable

• Vor der Aktualisierung eines gemeinsam genutzten Datenelements muss ein Prozess im exklusiven Modus in einen kritischen Bereich eintreten, um sicherzustellen, dass keine anderen Prozesse gleichzeitig versuchen, das Datenelement zu aktualisieren

Ziel: parallele Ausführung von Schleifeniterationen durch Datenparallelität

1. Unterscheidung:

• lokale vs. gemeinsame Variable? Lokale Variablen sind diejenigen, die in jeder Schleifeniteration der parallelisierten Schleife neu initialisiert werden

• Gemeinsame Variablen werden von mehr als einer Iteration der parallelisierten Schleife gelesen und geschrieben

Unabhängig,

• falls eines der beiden Kriterien erfüllt ist

• Variable wird von allen Iteration der parallelisierten Schleife nur gelesen

• Variable hat eine Array-Struktur und auf jedes Array-Element wird nur von einer Iteration der parallelisierten Schleife aus zugegriffen

Abhängig,

• falls keines der o.g. Kriterien erfüllt ist Abhängige Variablen sind gemeinsame Variablen, die von mehreren Iterationen der parallelisierten Schleife uneingeschränkt gelesen oder geschrieben werden

bei abhängiger Variable – Reduktionsvariable, Locked Variable oder Ordered Variable?

Ist eine Array-Variable oder eine skalare Variable mit den folgenden Eigenschaften

• Sie wird in der zu parallelisierenden Schleife nur in einer einzigen assoziativen und kommutativen Operation benutzt; diese Operationen können die Addition, Multiplikation, logisches UND, logisches ODER und exklusives ODER sein

• Die Operation ist von der Form var = var op expr, wobei var die Reduktionsvariable, op eine assoziative und kommutative Operation und expr ein Ausdruck ist, der die Variable var nicht enthält

Ist eine Array-Variable oder eine skalare Variable

• Kann von mehr als einer Iteration der parallelisierten Schleife gelesen oder geschrieben werden

• Jedoch bleibt eine Änderung der Lese- bzw. Schreibreihenfolge ohne Auswirkung

Ist eine Array-Variable oder eine skalare Variable

• Schleifenausführung erzielt nur dann ein korrektes Resultat, wenn die Operationen, die die Ordered-Variable betreffen, in sequentieller Iterationsreihenfolge ausgeführt werden

• Erzwingt eine sequentielle Abarbeitung der Iterationen; parallele Abarbeitung des Iterationsschrittes selbst ist jedoch teilweise möglich

Aufgrund des Zwangs der sequentiellen Iterationsreihenfolge kann folgende Strategie zur Optimierung angewendet werden

• Für jede Ordered-Variable wird eine gemeinsame (shared) IntegerVariable als Wächter im Programm vor dem Schleifeneintritt definiert

Parallelisierung möglichst über die äußere Schleife

• Nur die abhängigen Variablen müssen behandelt werden: Reduktionsvariablen Häufig globale Reduktions-Operationen (bei OpenMP) verwendbar, die genau diese Struktur ausnutzen

• Locked-Variablen Kritischer Bereich: lock...unlock

• Ordered-Variablen „Guards“ müssen in einem kritischen Bereich geschützt werden

• Punkt-zu-Punkt (point-to-point, P2P, 1:1-Kommunikation) 2 Prozesse nehmen teil: Sender und Empfänger

• Kollektive Kommunikation (1:M-Kommunikation, M ≤ P, P ist Anzahl Prozessoren)

  • Einige oder alle Prozesse nehmen teil

  • Verschiedene Varianten zur Datenverteilung, zum Einsammeln von Daten, zum Verknüpfen von Daten

• Sowohl Daten-Nachrichten wie auch Kontroll-Nachrichten existieren

• Zusätzlich werden in beiden Fällen Format-Informationen mitgeteilt

• Ein Prozess sendet gleiche Nachricht an alle teilnehmenden Prozesse

• Beispiel: erfolgreicher Prozess in einer Suche informiert andere Prozesse, die Suche abzubrechen

• Ein Prozess sendet gleiche Nachricht an eine Teilmenge der teilnehmende Prozesse

• Beispiel: sende Aktualisierung einer lokalen iterativen Lösung an die direkten Nachbarn

• Daten von einem Prozess werden auf alle anderen teilnehmenden Prozesse verteilt

• Beispiel: Reihe einer Matrix für parallele Lösung eines LGS

• Daten werden von einem Prozess bei allen Prozessen eingesammelt

• Beispiel: Erstellung des Lösungsvektors aus Teillösungen

• Alle Prozesse sammeln verteilte Daten bei allen anderen Prozessen ein

• Beispiel: Erstellung des Lösungsvektors aus Teillösungen (wie zuvor), aber jetzt benötigen alle Prozessoren die globale Lösung um weiterzumachen

• Daten von allen Prozessen werden auf alle Prozesse verteilt

• Beispiel: Transponieren einer Matrix

• Daten werden von allen Prozessen in einem Prozess zu einem reduzierten Wert vereinigt

• Beispiel: globales Minimum / Maximum / Summe / Produkt, …

All-reduce Kombination aus Reduce und All-to-all Daten werden von allen Prozessen zu einem reduzierten Wert vereinigt und in allen Prozessen abgelegt

Reduce-Scatter Kombination aus Reduce und scatter Daten von allen Prozessen werden reduziert und verteilt

Parallel Prefix Prozesse erhalten partielles Ergebnis der Reduzierungsoperation