Parallel Programming

3. Informationsaustausch

Gesamtaustausch

(total exchange)

- jeder Prozessor führt Scatteroperation aus

iss

Gemeinsame

Variablen

Multibroadcast

- jeder Prozessor führt Einzel-Broadcast aus

Multi-Akkumulation

- jeder Prozessor führt Einzel-Akkumulation aus

gemeinsamer Adressraum

gemeinsamer Speicher

private und gemeinsame Daten

Problem?

3 Strategien zur Realisierung

- Benny gießt Teig in Waffel-Back-Gerät

- Volker holt die fertigen (lecker duftenden) Waffeln raus, wenn sie fertig sind

- Sperren aller Unterbrechungen

- Aktives Warten

- TEST AND SET LOCK (TSL-Instruktion)

- Schlafen und Aufwecken

Beispiel: Benny und Volker backen Waffeln

Wechselseitiger Ausschluss

mutual exclusion

Bedingungen:

- Nur ein Prozess zu jedem Zeitpunkt in kritischem Bereich

- keine Annahmen über Ausführungszeit / Anzahl Prozessoren

- Kein Prozess, der nicht in kritischem Bereich, darf Andere

blockieren

- Eintritt in kritischen Bereich des Prozesses nach endlicher Zeit

(zeitkritische Abläufe) sind Situationen, in denen

Es gibt also...

- zwei oder mehr Prozesse gemeinsame Betriebsmittel nutzen

- Endergebnisse von zeitlicher Reihenfolge der Operationen abhängen

(critical section) ist der Teil ein Prozesses,

Wechselseitiger Ausschluss

der auf gemeinsam benutzte Betriebsmittel zugreift

Race Conditions

kritischer Bereich

Lösung?

IF-Anweisungen

Vektorprozessoren

Fragen?

- 6 Befehle vektorisiert

-> 64 * 9 + 2 = 578 Befehle vorher

vektorisiert

Vektorarchitektur

- führen gleiche Operation auf viele Daten aus

- Vektrorregister

- Vektorrechenwerke

- Rechenoperationen auf gesamtes Vektorregister

- Vektorlade- u. -speichereinheit

- Vorteil: schnelle Verarbeitung -> Pipelining

- Nachteil: Speicherladezeiten

Vektoranweisungen

unterstützende

Programmiersprachen

Y = a * X + Y

Vektorisierende

Compiler

Scatter

(vektorisierbare Schleifen)

- ein Prozessor schickt evtl. verschiedene Nachrichten an alle

- Empfangspuffer / Sendepuffer

Kommunikations-operationen

Gather

- alle Prozessoren schicken Nachricht an einen Prozessor

- Elementweise Kombination durch Konkatination

- Informationsaustausch bei verteiltem Adressraum

-> benötigt Kommunikationsanweisungen

"Message-Passing-Programmierung"

- Sende- u. Empfangsoperationen als Paar

- Punkt-zu-Punkt-Kommunikation

- zusätzlich globale Kommunikationsoperationen

- im Folgenden:

- Netzwerk aus p Prozessoren

- Prozessoridentifikation über Prozessornummer

SIMD-Verarbeitung

Einzel-Broadcast

- ein Prozessor schickt gleiche Nachricht an alle anderen

Einzelakkumulation

- alle Prozessoren schicken Nachricht an einen Prozessor

- Elementweise Kombination durch Reduktionsoperation

1.1 Vektorprozessoren

1.2 SIMD-Instruktionen

Einzeltransfer

- Nachrichtentransfer zwischen P[i] (Sender) und P[j] (Empfänger)

- Sender -> Sendeoperation

-> Sendepuffer mit Nachricht und Empfängernummer

- Empfänger -> Empfangsoperation

-> Empfangspuffer für Nachricht und Sendernummer

- Operationen nur paarweise

- bilden Grundlange jeder Kommunikationsbibliothek

Quellen:

SIMD-Instruktionen

Inhalt

1. SIMD-Verarbeitung

1.1 Vektorprozessoren

1.2 SIMD-Instruktionen

2. Datenverteilung für Felder

3. Informationsaustausch

3.1 Gemeinsame Variablen

3.2 Kommunikationsoperationen

3.3 Parallele Matrix-Vektor-Multiplikation

Parallele

Programmierung

* = Variante der MAC-Operationen (Multiplier-Accumulator)

- d := a + b * c

-Verwendung in Digitalen Signalprozessoren (DSP) -> digitale Equalizer, MP3-Player, Radar, ...

Kapitel 3.6 - 3.8

Benjamin Swiers

Volker Klages

- "Parallel Programming" 2012, Springer

T. Rauber, G. Rünger

- "Betriebssysteme" 2005, Pearson Studium

E. Ehses, L. Köhler, P. Riemer, H. Stenzel, F. Victor

- "Computer Architecture" 2011, Morgan Kaufmann

J.L. Hennessy, D.A. Patterson

Verteilung der Linearkombinationen

- spaltenorientiert streifenweise

-> Spalten von A lokal für jeden Prozessor

- blockweise streifenweise

-> Spalten

-> berechnet Teillinearkombination

Linearkombinationen

- Prozessor P[k] benötigt Block aus b

- nach der Berechnung

-> P[k] hat Vektor d[k] der Länge n

- Akkumulationsoperation mit Addition als Reduktion

- falls Ergebnis repliziert -> Einzel-Broadcast

Verteilung der Skalarprodukte

- Prozessor berechnet Produkt (a[i],b)

- i = {1 ... n}

-> benötigt Zeile a[i] und Vektor b lokal

-> zeilenorientiere streifenweise Datenverteilung

streifenweise Datenverteilung

- Prozessor P[k], k = 1 ... p, erhält Zeilen a[i] lokal

-> i = n / p · (k - 1) + 1 ... n / p · k

- Ergebnisvektor c danach blockweise verteilt

-> soll repliziert vorliegen, wie b

-> Multi-Broadcastoperation

- lokale Feld von Prozessors P[k] besitzt Zeile aus A:

- Berechnung der Linearkombination wird verteilt

-> p Prozessoren, m Spalten

-> jeder berechnet m/p Spaltenvektoren

- Berechnung der inneren Produkte wird verteilt

-> p Prozessoren, n Produkte

-> jeder berechnet n/p Skalarprodukte

Zwei Parallelisierungsansätze

Linearkombination

Gegeben

n innere Produkte

Zwei verschiedene Schleifen

Parallele Matrix-

Vektor-Multiplikation

Eindimensionale

Felder

zyklisch

blockweise

- Feld der Länge n wird auf p Blöcke verteilt

- wenn n KEIN Vielfaches von p

-> letzte Block weniger Feldelemente

- Feldelemente werden der Reihe nach an die Prozessoren verteilt

- Feld v der Länge n

- Anzahl der Blöcke p

blockzyklisch

- Mischform aus blockweiser und zyklischer Verteilung

- Jeder Block hat eine vorgegebene Größe b, wobei b<n/p

- ist n kein Vielfaches von p, umfasst der letzte Block

weniger als b Feldelemente

- Blöcke werden in zyklischer Weise auf die Prozessoren verteilt

2. Datenverteilung für Felder

- Algorithmen/ Berechnungen oft auf Basis von Vektoren oder Matrizen

- ein-/ zwei-/ mehrdimensionale Felder als Datenstruktur in Programmen

- Aufteilung der Felder in Teilbereiche und

- Abbildung dieser Teilbereiche auf die zur Verfügung stehenden Prozessoren =

Partitionierung

verteilter Speicher

- mehrere Prozessoren

-> eigener Speicher

- Netzwerkzugriff

gemeinsamer Adressraum

- gesamte Feld für alle Prozessoren

- Datenverteilung verhindert Konflikte

Beliebig-dimensionale

Felder

Zweidimensionale

Felder

- A sei d-dimensionales Feld

- Aufteilung der Prozessoren in d-dimensionales Gitter

- Datenverteilung für A durch Verteilungsfunktion

streifenweise

schachbrettartig

- statt einzelne Feldelemente werden ganze Spalten (oder Zeilen) zu Blöcken

zusammengefasst

- Spalten (oder Zeilen) der Matrix werden in p gleichgroße Blöcke aufeinander

folgender Spalten (oder Zeilen) unterteilt

- bezieht beide Dimensionen des 2-dimensionalen Feldes ein

und teilt diese in quadratische oder rechteckige Teilstücke auf

- Anordnung der Prozessoren in 2-dimensionales Gitter (Prozessorgitter)

blockweise

zyklisch

- einzelne Matrixelemente werden reihum den Prozessoren

in den Zeilen bzw. Spalten des Prozessorgitters zugeordnet

-> (zyklische Zuordnung in beiden Dimensionen)

- Anzahl Zeilen bzw. Spalten des Prozessorgitters bestimmt Anzahl

der Blöcke in den Zeilen bzw. Spalten der aufzuteilenden Matrix

- Block(i,j) für 1<= i <= p1 und 1<= j <= p2 enthält alle Matrixelemente (k,l) mit

- k=(i-1)*n1/p1+1,...,i* round(n1/p1)

- l=(j-1)* n2/p2 +1,...,j* round(n2/p2)

-> p1 und p2 sind Anzahl Zeilen bzw. Spalten des Prozessorgitters

- Block (i,j) wird dem Prozessor an der Position (i,j) zugeordnet

Elemente von A

Potenzmenge der Prozessoren

block-zyklisch

- statt einzelner Matrixelemente werden rechteckige

Blöcke der Größe b1 x b2 zyklisch über die Prozessoren verteilt