View
136
Download
2
Category
Preview:
Citation preview
Parallele Algorithmen zur Matrix Multiplikation
Matthias Dohm
Parallele Algorithmen zur Matrix MultiplikationSeminar Parallele Programmierung und Parallele Algorithmen
2 Parallele Algorithmen zur Matrix Multiplikation
Agenda
Einleitung
Algorithmen für quadratische Matrizen und quadratische Prozessor Grids
Algorithmen für nicht quadratische Matrizen und nicht quadratische Prozessor Grids
Fazit und Ausblick
3 Parallele Algorithmen zur Matrix Multiplikation
Agenda
Einleitung
Algorithmen für quadratische Matrizen und quadratische Prozessor Grids
Algorithmen für nicht quadratische Matrizen und nicht quadratische Prozessor Grids
Fazit und Ausblick
4 Parallele Algorithmen zur Matrix Multiplikation
8
6
4
2
7
5
3
1
Einleitung
16151413
1211109
8765
4321
300
220
140
60
242
178
114
50
Multiplikation
++
+
5 Parallele Algorithmen zur Matrix Multiplikation
Einleitung
𝑐𝑖,𝑗 = 𝑎𝑖,𝑘𝑏𝑘,𝑗𝑛−1𝑘=0
public static int[][] MatrixMult (int[][]a, int[][]b) {int m = a.length; //A is a m x n matrixint n = b.length; //B is a n x o matrixint o = b[0].length; //Result is a m x o matrix
int[][] c = new int[m][o];
//Calculationfor (int i = 0; i < m; i++) {
for (int j = 0; j < o; j++) {c[i][j] = 0; //Initialize c_i,jfor (int k = 0; k < n; k++) {
c[i][j] += a[i][k]*b[k][j];}
}}return c;
}
Θ(n³)Laufzeit
m
n
o
6 Parallele Algorithmen zur Matrix Multiplikation
Block-orientierter Algorithmus
Laufzeit: Θ(n³)
Einleitung
𝐶= ൬𝐴00𝐵00 + 𝐴01𝐵10 𝐴00𝐵01 + 𝐴01𝐵11𝐴10𝐵00 + 𝐴11𝐵10 𝐴10𝐵11 + 𝐴11𝐵11൰
a 0,0 a 0,1 a 0,2 a 0,3 a 0,4 a 0,5
a 1,0 a 1,1 a 1,2 a 1,3 a 1,4 a 1,5
a 2,0 a 2,1 a 2,2 a 2,3 a 2,4 a 2,5
a 3,0 a 3,1 a 3,2 a 3,3 a 3,4 a 3,5
a 4,0 a 4,1 a 4,2 a 4,3 a 4,4 a 4,5
a 5,0 a 5,1 a 5,2 a 5,3 a 5,4 a 5,5
b 0,0 b 0,1 b 0,2 b 0,3 b 0,4 b 0,5
b 1,0 b 1,1 b 1,2 b 1,3 b 1,4 b 1,5
b 2,0 b 2,1 b 2,2 b 2,3 b 2,4 b 2,5
b 3,0 b 3,1 b 3,2 b 3,3 b 3,4 b 3,5
b 4,0 b 4,1 b 4,2 b 4,3 b 4,4 b 4,5
b 5,0 b 5,1 b 5,2 b 5,3 b 5,4 b 5,5
A0,0 A0,1
A1,1A1,0
B0,0 B0,1
B1,1B1,0
7 Parallele Algorithmen zur Matrix Multiplikation
Einleitung
ArchitekturVerteilter Speicher
KommunikationGleichzeitiges Senden und Empfangen möglich
Kein paralleles Senden an mehrere Empfänger und Empfangen von mehreren Sendern
8 Parallele Algorithmen zur Matrix Multiplikation
Einleitung
Algorithmen von Cannon und FoxBlock-orientierte Algorithmen
Prozessoren als 2D-Grid organisiert (muss quadratisch sein)
Matrizen müssen quadratisch sein
Algorithmus von LiVariante von Cannons Algorithmus für nicht quadratische Matrizen und Prozessor-Grids
MM3, MM4, MM5
Varianten vom Algorithmus von Fox für nicht quadratische Matrizen und Prozessor-Grids
9 Parallele Algorithmen zur Matrix Multiplikation
Agenda
Einleitung
Algorithmen für quadratische Matrizen und quadratische Prozessor Grids
Algorithmen für nicht quadratische Matrizen und nicht quadratische Prozessor Grids
Fazit und Ausblick
10 Parallele Algorithmen zur Matrix Multiplikation
Algorithmus von Cannon
Matrizen A und B werden auf Prozesse aufgeteilt
Entsprechender Teil von C wird initialisiert
Problem: Nur Prozesse entlang der Hauptdiagonalen halten passende Teilmatrizen (Ai,k, Bk,j)
Deshalb: UmordnungAi,j : i Spalten nach links
Bi,j : j Zeilen nach oben
A 0,0 A 0,1 A 0,2 A 0,3
B 0,0 B 0,1 B 0,2 B 0,3
A 1,0 A 1,1 A 1,2 A 1,3
B 1,0 B 1,1 B 1,2 B 1,3
A 2,0 A 2,1 A 2,2 A 2,3
B 2,0 B 2,1 B 2,2 B 2,3
A 3,0 A 3,1 A 3,2 A 3,3
B 3,0 B 3,1 B 3,2 B 3,3
Process Mi,j Submatrix of M
A 0,0 A 0,1 A 0,2 A 0,3
B 0,0 B 1,1 B 2,2 B 3,3
A 1,1 A 1,2 A 1,3 A 1,0
B 1,0 B 2,1 B 3,2 B 0,3,
A 2,2 A 2,3 A 2,0 A 2,1
B 2,0 B 3,1 B 0,2 B 1,3
A 3,3 A 3,0 A 3,1 A 3,2
B 3,0 B 0,1 B 1,2 B 2,3
11 Parallele Algorithmen zur Matrix Multiplikation
A 0,0 A 0,1 A 0,2 A 0,3
B 0,0 B 1,1 B 2,2 B 3,3
A 1,1 A 1,2 A 1,3 A 1,0
B 1,0 B 2,1 B 3,2 B 0,3,
A 2,2 A 2,3 A 2,0 A 2,1
B 2,0 B 3,1 B 0,2 B 1,3
A 3,3 A 3,0 A 3,1 A 3,2
B 3,0 B 0,1 B 1,2 B 2,3
Algorithmus von Cannon
Iteration (Anzahl der Prozess-Zeilen)
Alle Prozesse führen eine (sequentielle) Matrix Multiplikation aus
KommunikationsschrittProzess sendet Block von A nach links und empfängt Block von A von rechts
Prozess sendet Block von B nach oben und empfängt Block von B von unten
Umordnung wird rückgängig gemacht
A 0,1 A 0,2 A 0,3 A 0,0
B 1,0 B 2,1 B 3,2 B 0,3
A 1,2 A 1,3 A 1,0 A 1,1
B 2,0 B 3,1 B 0,2 B 1,3,
A 2,3 A 2,0 A 2,1 A 2,2
B 3,0 B 0,1 B 1,2 B 2,3
A 3,0 A 3,1 A 3,2 A 3,3
B 0,0 B 1,1 B 2,2 B 3,3
12 Parallele Algorithmen zur Matrix Multiplikation
Algorithmus von Cannon - Komplexität
Größe des Prozess Grid: p × p
Größe der Matrizen: n × n
Zeitaufwand für Multiplikation von 2 Elementen + Addition zum Ergebnis: χ
Zeit zum Aufbau einer Kommunikation: λ
Zeit zum Übertragen eines Matrix-Elements: 1 / β
13 Parallele Algorithmen zur Matrix Multiplikation
Algorithmus von Cannon - Komplexität
Berechnungen pro Iteration
Berechnungen Gesamt
Übertragung einer Submatrix
Kommunikation Gesamt
3
p
n
2
33
p
n
p
np
2
221
p
n
p
n
2
2
)2(2p
np
14 Parallele Algorithmen zur Matrix Multiplikation
Algorithmus von Fox
Matrizen A und B werden auf Prozesse aufgeteilt
Entsprechender Teil von C wird initialisiert
Keine Umordnung erforderlich
Submatrizen von A werden entlang der Prozessreihe per Broadcast übertragen
A 0,0 A 0,1 A 0,2 A 0,3
B 0,0 B 0,1 B 0,2 B 0,3
A 1,0 A 1,1 A 1,2 A 1,3
B 1,0 B 1,1 B 1,2 B 1,3
A 2,0 A 2,1 A 2,2 A 2,3
B 2,0 B 2,1 B 2,2 B 2,3
A 3,0 A 3,1 A 3,2 A 3,3
B 3,0 B 3,1 B 3,2 B 3,3
Process Mi,j Submatrix of M
A 0,0 A 0,0 A 0,0 A 0,0
B 0,0 B 0,1 B 0,2 B 0,3
A 1,1 A 1,1 A 1,1 A 1,1
B 1,0 B 1,1 B 1,2 B 1,3,
A 2,2 A 2,2 A 2,2 A 2,2
B 2,0 B 2,1 B 2,2 B 2,3
A 3,3 A 3,3 A 3,3 A 3,3
B 3,0 B 3,1 B 3,2 B 3,3
15 Parallele Algorithmen zur Matrix Multiplikation
Algorithmus von Fox
Iteration (Anzahl der Prozess-Zeilen)
Alle Prozesse führen eine (sequentielle) Matrix Multiplikation aus
KommunikationsschrittProzess sendet Block von B nach oben und empfängt Block von B von unten
Pro Zeile wird ein Block von A per Broadcast entlang der Zeile übertragen (entfällt in der letzten Iteration)
A 0,0 A 0,0 A 0,0 A 0,0
B 0,0 B 0,1 B 0,2 B 0,3
A 1,1 A 1,1 A 1,1 A 1,1
B 1,0 B 1,1 B 1,2 B 1,3,
A 2,2 A 2,2 A 2,2 A 2,2
B 2,0 B 2,1 B 2,2 B 2,3
A 3,3 A 3,3 A 3,3 A 3,3
B 3,0 B 3,1 B 3,2 B 3,3
A 0,0 A 0,1 A 0,2 A 0,3
B 1,0 B 1,1 B 1,2 B 1,3
A 1,0 A 1,1 A 1,2 A 1,3
B 2,0 B 2,1 B 2,2 B 2,3,
A 2,0 A 2,1 A 2,2 A 2,3
B 3,0 B 3,1 B 3,2 B 3,3
A 3,0 A 3,1 A 3,2 A 3,3
B 0,0 B 0,1 B 0,2 B 0,3
16 Parallele Algorithmen zur Matrix Multiplikation
Algorithmus von Fox- Komplexität
Berechnungen Gesamt(wie bei Algorithmus von Cannon)
Übertragung einer Submatrix von B
Broadcast einer Submatrix von A
Kommunikation Gesamt
2
33
p
n
p
np
2
221
p
n
p
n
2
2
2
2
logp
np
p
npp
2
2
logp
np
17 Parallele Algorithmen zur Matrix Multiplikation
Laufzeitvergleich: Algorithmen von Cannon und Fox
Algorithmus von Cannon ist schneller wenn:
2
2
2
2
2
2
log)2(2p
np
p
npp
p
np
pppp log)2(2
ppp log4
p 4
18 Parallele Algorithmen zur Matrix Multiplikation
Agenda
Einleitung
Algorithmen für quadratische Matrizen und quadratische Prozessor Grids
Algorithmen für nicht quadratische Matrizen und nicht quadratische Prozessor Grids
Fazit und Ausblick
19 Parallele Algorithmen zur Matrix Multiplikation
a 0,0 a 0,1 a 0,2 a 0,3 a 0,4 a 0,5 a 0,6
a 1,0 a 1,1 a 1,2 a 1,3 a 1,4 a 1,5 a 1,6
a 2,0 a 2,1 a 2,2 a 2,3 a 2,4 a 2,5 a 2,6
a 3,0 a 3,1 a 3,2 a 3,3 a 3,4 a 3,5 a 3,6
a 4,0 a 4,1 a 4,2 a 4,3 a 4,4 a 4,5 a 4,6
b 0,0 b 0,1 b 0,2 b 0,3 b 0,4 b 0,5 b 0,6 b 0,7
b 1,0 b 1,1 b 1,2 b 1,3 b 1,4 b 1,5 b 1,6 b 1,7
b 2,0 b 2,1 b 2,2 b 2,3 b 2,4 b 2,5 b 2,6 b 2,7
b 3,0 b 3,1 b 3,2 b 3,3 b 3,4 b 3,5 b 3,6 b 3,7
b 4,0 b 4,1 b 4,2 b 4,3 b 4,4 b 4,5 b 4,6 b 4,7
b 5,0 b 5,1 b 5,2 b 5,3 b 5,4 b 5,5 b 5,6 b 5,7
b 6,0 b 6,1 b 6,2 b 6,3 b 6,4 b 6,5 b 6,6 b 6,7
Algorithmus von Li (C stationär)Umordnung besteht aus 2 Phasen
Blöcke werden verschoben
Zeilen/Spalten werden verschoben
Für jede Prozess-ZeileSpaltenindex der ersten Spalte von A soll Zeilenindex der ersten Zeile von B entsprechen
Für jede Prozess-SpalteZeilenindex der ersten Zeile von B soll Spaltenindex der ersten Spalte von A entsprechen
20 Parallele Algorithmen zur Matrix Multiplikation
a 0,0 a 0,1 a 0,2 a 0,3 a 0,4 a 0,5 a 0,6
a 1,0 a 1,1 a 1,2 a 1,3 a 1,4 a 1,5 a 1,6
a 2,2 a 2,3 a 2,4 a 2,5 a 2,6 a 2,0 a 2,1
a 3,2 a 3,3 a 3,4 a 3,5 a 3,6 a 3,0 a 3,1
a 4,2 a 4,3 a 4,4 a 4,5 a 4,6 a 4,0 a 4,1
Algorithmus von Li (C stationär)Umordnung besteht aus 2 Phasen
Blöcke werden verschoben
Zeilen/Spalten werden verschoben
Für jede Prozess-ZeileSpaltenindex der ersten Spalte von A soll Zeilenindex der ersten Zeile von B entsprechen
Für jede Prozess-SpalteZeilenindex der ersten Zeile von B soll Spaltenindex der ersten Spalte von A entsprechen
b 0,0 b 0,1 b 0,2 b 0,3 b 0,4 b 3,5 b 3,6 b 3,7
b 1,0 b 1,1 b 1,2 b 1,3 b 1,4 b 4,5 b 4,6 b 4,7
b 2,0 b 2,1 b 2,2 b 2,3 b 2,4 b 5,5 b 5,6 b 5,7
b 6,5 b 6,6 b 6,7
b 3,0 b 3,1 b 3,2 b 3,3 b 3,4 b 0,5 b 0,6 b 0,7
b 4,0 b 4,1 b 4,2 b 4,3 b 4,4 b 1,5 b 1,6 b 1,7
b 5,0 b 5,1 b 5,2 b 5,3 b 5,4 b 2,5 b 2,6 b 2,7
b 6,0 b 6,1 b 6,2 b 6,3 b 6,4
21 Parallele Algorithmen zur Matrix Multiplikation
b 0,0 b 0,1 b 2,2 b 2,3 b 2,4 b 4,5 b 4,6 b 4,7
b 1,0 b 1,1 b 3,2 b 3,3 b 3,4 b 5,5 b 5,6 b 5,7
b 2,0 b 2,1 b 4,2 b 4,3 b 4,4 b 6,5 b 6,6 b 6,7
b 0,5 b 0,6 b 0,7
b 3,0 b 3,1 b 5,2 b 5,3 b 5,4 b 1,5 b 1,6 b 1,7
b 4,0 b 4,1 b 6,2 b 6,3 b 6,4 b 2,5 b 2,6 b 2,7
b 5,0 b 5,1 b 0,2 b 0,3 b 0,4 b 3,5 b 3,6 b 3,7
b 6,0 b 6,1 b 1,2 b 1,3 b 1,4
a 0,0 a 0,1 a 0,2 a 0,3 a 0,4 a 0,5 a 0,6
a 1,0 a 1,1 a 1,2 a 1,3 a 1,4 a 1,5 a 1,6
a 2,3 a 2,4 a 2,5 a 2,6 a 2,0 a 2,1 a 2,2
a 3,3 a 3,4 a 3,5 a 3,6 a 3,0 a 3,1 a 3,2
a 4,3 a 4,4 a 4,5 a 4,6 a 4,0 a 4,1 a 4,2
Algorithmus von Li (C stationär)Umordnung besteht aus 2 Phasen
Blöcke werden verschoben
Zeilen/Spalten werden verschoben
Für jede Prozess-ZeileSpaltenindex der ersten Spalte von A soll Zeilenindex der ersten Zeile von B entsprechen
Für jede Prozess-SpalteZeilenindex der ersten Zeile von B soll Spaltenindex der ersten Spalte von A entsprechen
22 Parallele Algorithmen zur Matrix Multiplikation
b 0,0 b 0,1 b 2,2 b 2,3 b 2,4 b 4,5 b 4,6 b 4,7
b 1,0 b 1,1 b 3,2 b 3,3 b 3,4 b 5,5 b 5,6 b 5,7
b 2,0 b 2,1 b 4,2 b 4,3 b 4,4 b 6,5 b 6,6 b 6,7
b 0,5 b 0,6 b 0,7
b 3,0 b 3,1 b 5,2 b 5,3 b 5,4 b 1,5 b 1,6 b 1,7
b 4,0 b 4,1 b 6,2 b 6,3 b 6,4 b 2,5 b 2,6 b 2,7
b 5,0 b 5,1 b 0,2 b 0,3 b 0,4 b 3,5 b 3,6 b 3,7
b 6,0 b 6,1 b 1,2 b 1,3 b 1,4
a 0,0 a 0,1 a 0,2 a 0,3 a 0,4 a 0,5 a 0,6
a 1,0 a 1,1 a 1,2 a 1,3 a 1,4 a 1,5 a 1,6
a 2,3 a 2,4 a 2,5 a 2,6 a 2,0 a 2,1 a 2,2
a 3,3 a 3,4 a 3,5 a 3,6 a 3,0 a 3,1 a 3,2
a 4,3 a 4,4 a 4,5 a 4,6 a 4,0 a 4,1 a 4,2
Algorithmus von Li (C stationär)Iteration (bis dieser Zustand wieder erreicht wird)
Alle Prozesse führen eine (sequentielle) Matrix Multiplikation aus (soweit möglich)
KommunikationsschrittProzess sendet Block von A nach links und empfängt Block von A von rechts (wenn alle Elemente von A benutzt)
Prozess sendet Block von B nach oben und empfängt Block von B von unten (wenn alle Elemente von B benutzt)
Umordnung wird rückgängig gemacht
23 Parallele Algorithmen zur Matrix Multiplikation
b 0,0 b 0,1 b 2,2 b 2,3 b 2,4 b 4,5 b 4,6 b 4,7
b 1,0 b 1,1 b 3,2 b 3,3 b 3,4 b 5,5 b 5,6 b 5,7
b 2,0 b 2,1 b 4,2 b 4,3 b 4,4 b 6,5 b 6,6 b 6,7
b 0,5 b 0,6 b 0,7
b 3,0 b 3,1 b 5,2 b 5,3 b 5,4 b 1,5 b 1,6 b 1,7
b 4,0 b 4,1 b 6,2 b 6,3 b 6,4 b 2,5 b 2,6 b 2,7
b 5,0 b 5,1 b 0,2 b 0,3 b 0,4 b 3,5 b 3,6 b 3,7
b 6,0 b 6,1 b 1,2 b 1,3 b 1,4
a 0,0 a 0,1 a 0,2 a 0,3 a 0,4 a 0,5 a 0,6
a 1,0 a 1,1 a 1,2 a 1,3 a 1,4 a 1,5 a 1,6
a 2,3 a 2,4 a 2,5 a 2,6 a 2,0 a 2,1 a 2,2
a 3,3 a 3,4 a 3,5 a 3,6 a 3,0 a 3,1 a 3,2
a 4,3 a 4,4 a 4,5 a 4,6 a 4,0 a 4,1 a 4,2
Algorithmus von Li (C stationär)Iteration (bis dieser Zustand wieder erreicht wird)
Alle Prozesse führen eine (sequentielle) Matrix Multiplikation aus (soweit möglich)
KommunikationsschrittProzess sendet Block von A nach links und empfängt Block von A von rechts (wenn alle Elemente von A benutzt)
Prozess sendet Block von B nach oben und empfängt Block von B von unten (wenn alle Elemente von B benutzt)
Umordnung wird rückgängig gemacht
a 0,2 a 0,3 a 0,4 a 0,5 a 0,6 a 0,0 a 0,1
a 1,2 a 1,3 a 1,4 a 1,5 a 1,6 a 1,0 a 1,1
a 2,5 a 2,6 a 2,0 a 2,1 a 2,2 a 2,3 a 2,4
a 3,5 a 3,6 a 3,0 a 3,1 a 3,2 a 3,3 a 3,4
a 4,5 a 4,6 a 4,0 a 4,1 a 4,2 a 4,3 a 4,4
24 Parallele Algorithmen zur Matrix Multiplikation
Algorithmus von Li - Komplexität
Größe des Prozess Grid: p × q
Größe der Matrizen:A: m × n
B: n × o
C: m × o
Zeitaufwand für Multiplikation von 2 Elementen + Addition zum Ergebnis: χ
Zeit zum Aufbau einer Kommunikation: λ
Zeit zum Übertragen eines Matrix-Elements: 1 / β
m
n
o
25 Parallele Algorithmen zur Matrix Multiplikation
Algorithmus von Li- Komplexität
Berechnungen Gesamt
Übertragung einer Submatrix von A
Umordnungsschritt
Kommunikation Gesamt
pq
mnoχ
1
pq
mn
pq
nomn24
1
pq
no22
1
pq
mn22
1
pq
no1
pq
mn
pq
nomn242 pq
pq
pnoqmnnomn41qp8
26 Parallele Algorithmen zur Matrix Multiplikation
a 0,0 a 0,1 a 0,2 a 0,3 a 0,4 a 0,5 a 0,6
a 1,0 a 1,1 a 1,2 a 1,3 a 1,4 a 1,5 a 1,6
a 2,0 a 2,1 a 2,2 a 2,3 a 2,4 a 2,5 a 2,6
a 3,0 a 3,1 a 3,2 a 3,3 a 3,4 a 3,5 a 3,6
a 4,0 a 4,1 a 4,2 a 4,3 a 4,4 a 4,5 a 4,6
b 0,0 b 0,1 b 0,2 b 0,3 b 0,4 b 0,5 b 0,6 b 0,7
b 1,0 b 1,1 b 1,2 b 1,3 b 1,4 b 1,5 b 1,6 b 1,7
b 2,0 b 2,1 b 2,2 b 2,3 b 2,4 b 2,5 b 2,6 b 2,7
b 3,0 b 3,1 b 3,2 b 3,3 b 3,4 b 3,5 b 3,6 b 3,7
b 4,0 b 4,1 b 4,2 b 4,3 b 4,4 b 4,5 b 4,6 b 4,7
b 5,0 b 5,1 b 5,2 b 5,3 b 5,4 b 5,5 b 5,6 b 5,7
b 6,0 b 6,1 b 6,2 b 6,3 b 6,4 b 6,5 b 6,6 b 6,7
MM3 – Zeilen-Version
1. Schritt:Für jede Prozess-Zeile
Spalte wird gesucht, deren Spaltenindex dem Zeilenindex der ersten Zeile von B entspricht
Der Teil der Submatrix ab dieser Spalte wird per Broadcast entlang der Zeile übertragen
Die nicht benutzten Elemente der Submatrizen werden im letzten Schritt übertragen und verwendet
a 0,0 a 0,1 a 0,0 a 0,1 a 0,0 a 0,1
a 1,0 a 1,1 a 1,0 a 1,1 a 1,0 a 1,1
a 2,3 a 2,3 a 2,3
a 3,3 a 3,3 a 3,3
a 4,3 a 4,3 a 4,3
27 Parallele Algorithmen zur Matrix Multiplikation
a 0,0 a 0,1 a 0,0 a 0,1 a 0,0 a 0,1
a 1,0 a 1,1 a 1,0 a 1,1 a 1,0 a 1,1
a 2,3 a 2,3 a 2,3
a 3,3 a 3,3 a 3,3
a 4,3 a 4,3 a 4,3
b 0,0 b 0,1 b 0,2 b 0,3 b 0,4 b 0,5 b 0,6 b 0,7
b 1,0 b 1,1 b 1,2 b 1,3 b 1,4 b 1,5 b 1,6 b 1,7
b 2,0 b 2,1 b 2,2 b 2,3 b 2,4 b 2,5 b 2,6 b 2,7
b 3,0 b 3,1 b 3,2 b 3,3 b 3,4 b 3,5 b 3,6 b 3,7
b 4,0 b 4,1 b 4,2 b 4,3 b 4,4 b 4,5 b 4,6 b 4,7
b 5,0 b 5,1 b 5,2 b 5,3 b 5,4 b 5,5 b 5,6 b 5,7
b 6,0 b 6,1 b 6,2 b 6,3 b 6,4 b 6,5 b 6,6 b 6,7
MM3 – Zeilen-Version
Iteration (bis dieser Zustand wieder erreicht wird)
Alle Prozesse führen eine (sequentielle) Matrix Multiplikation aus (soweit möglich)
KommunikationsschrittNächster Prozess sendet Block von A per Broadcast (wenn alle Elemente von A in dieser Zeile benutzt)
Prozess sendet Block von B nach oben und empfängt Block von B von unten (wenn alle Elemente von B benutzt)
28 Parallele Algorithmen zur Matrix Multiplikation
a 0,0 a 0,1 a 0,2 a 0,3 a 0,4 a 0,5 a 0,6
a 1,0 a 1,1 a 1,2 a 1,3 a 1,4 a 1,5 a 1,6
a 2,0 a 2,1 a 2,2 a 2,3 a 2,4 a 2,5 a 2,6
a 3,0 a 3,1 a 3,2 a 3,3 a 3,4 a 3,5 a 3,6
a 4,0 a 4,1 a 4,2 a 4,3 a 4,4 a 4,5 a 4,6
b 0,0 b 0,1 b 0,2 b 0,3 b 0,4 b 0,5 b 0,6 b 0,7
b 1,0 b 1,1 b 1,2 b 1,3 b 1,4 b 1,5 b 1,6 b 1,7
b 2,0 b 2,1 b 2,2 b 2,3 b 2,4 b 2,5 b 2,6 b 2,7
b 3,0 b 3,1 b 3,2 b 3,3 b 3,4 b 3,5 b 3,6 b 3,7
b 4,0 b 4,1 b 4,2 b 4,3 b 4,4 b 4,5 b 4,6 b 4,7
b 5,0 b 5,1 b 5,2 b 5,3 b 5,4 b 5,5 b 5,6 b 5,7
b 6,0 b 6,1 b 6,2 b 6,3 b 6,4 b 6,5 b 6,6 b 6,7
MM3 – Zeilen-Version
Iteration (bis dieser Zustand wieder erreicht wird)
Alle Prozesse führen eine (sequentielle) Matrix Multiplikation aus (soweit möglich)
KommunikationsschrittNächster Prozess sendet Block von A per Broadcast (wenn alle Elemente von A in dieser Zeile benutzt)
Prozess sendet Block von B nach oben und empfängt Block von B von unten (wenn alle Elemente von B benutzt)
29 Parallele Algorithmen zur Matrix Multiplikation
MM3 - Komplexität
Berechnungen Gesamt
Erster + letzter Broadcast-Schritt
Kommunikation Gesamt
pq
mnoχ
1
pq
mnqlogqlog2
1
pq
nop
1
pq
mnqlog)1q(
1
pq
mnqlogqlog2
pq
no pmn q log q1qlog)1(q p
30 Parallele Algorithmen zur Matrix Multiplikation
a 0,0 a 0,1 a 0,0 a 0,1 a 0,0 a 0,1
a 1,0 a 1,1 a 1,0 a 1,1 a 1,0 a 1,1
a 2,3 a 2,3 a 2,3
a 3,3 a 3,3 a 3,3
a 4,3 a 4,3 a 4,3
b 0,0 b 0,1 b 0,2 b 0,3 b 0,4 b 0,5 b 0,6 b 0,7
b 1,0 b 1,1 b 1,2 b 1,3 b 1,4 b 1,5 b 1,6 b 1,7
b 2,0 b 2,1 b 2,2 b 2,3 b 2,4 b 2,5 b 2,6 b 2,7
b 3,0 b 3,1 b 3,2 b 3,3 b 3,4 b 3,5 b 3,6 b 3,7
b 4,0 b 4,1 b 4,2 b 4,3 b 4,4 b 4,5 b 4,6 b 4,7
b 5,0 b 5,1 b 5,2 b 5,3 b 5,4 b 5,5 b 5,6 b 5,7
b 6,0 b 6,1 b 6,2 b 6,3 b 6,4 b 6,5 b 6,6 b 6,7
MM3
Nachteile von MM3
Schlechte Verteilung der Last
Zusätzlicher Broadcast Schritt
MM4 behebt diese Probleme durch einen Umordnungsschritt
31 Parallele Algorithmen zur Matrix Multiplikation
a 0,0 a 0,1 a 0,2 a 0,3 a 0,4 a 0,5 a 0,6
a 1,0 a 1,1 a 1,2 a 1,3 a 1,4 a 1,5 a 1,6
a 2,0 a 2,1 a 2,2 a 2,3 a 2,4 a 2,5 a 2,6
a 3,0 a 3,1 a 3,2 a 3,3 a 3,4 a 3,5 a 3,6
a 4,0 a 4,1 a 4,2 a 4,3 a 4,4 a 4,5 a 4,6
b 0,0 b 0,1 b 0,2 b 0,3 b 0,4 b 0,5 b 0,6 b 0,7
b 1,0 b 1,1 b 1,2 b 1,3 b 1,4 b 1,5 b 1,6 b 1,7
b 2,0 b 2,1 b 2,2 b 2,3 b 2,4 b 2,5 b 2,6 b 2,7
b 3,0 b 3,1 b 3,2 b 3,3 b 3,4 b 3,5 b 3,6 b 3,7
b 4,0 b 4,1 b 4,2 b 4,3 b 4,4 b 4,5 b 4,6 b 4,7
b 5,0 b 5,1 b 5,2 b 5,3 b 5,4 b 5,5 b 5,6 b 5,7
b 6,0 b 6,1 b 6,2 b 6,3 b 6,4 b 6,5 b 6,6 b 6,7
MM4 – Zeilen-Version
1. Schritt:Für jede Prozess-Zeile
Spalte wird gesucht, deren Spaltenindex dem Zeilenindex der ersten Zeile von B entspricht
Die Spalten von A werden nach links verschoben, sodass diese Spalte die erste in ihrem Block ist
Pro Zeile wird ein Block von A per Broadcast entlang der Zeile übertragen
a 0,0 a 0,1 a 0,2 a 0,3 a 0,4 a 0,5 a 0,6
a 1,0 a 1,1 a 1,2 a 1,3 a 1,4 a 1,5 a 1,6
a 2,1 a 2,2 a 2,3 a 2,4 a 2,5 a 2,6 a 2,0
a 3,1 a 3,2 a 3,3 a 3,4 a 3,5 a 3,6 a 3,0
a 4,1 a 4,2 a 4,3 a 4,4 a 4,5 a 4,6 a 4,0
32 Parallele Algorithmen zur Matrix Multiplikation
b 0,0 b 0,1 b 0,2 b 0,3 b 0,4 b 0,5 b 0,6 b 0,7
b 1,0 b 1,1 b 1,2 b 1,3 b 1,4 b 1,5 b 1,6 b 1,7
b 2,0 b 2,1 b 2,2 b 2,3 b 2,4 b 2,5 b 2,6 b 2,7
b 3,0 b 3,1 b 3,2 b 3,3 b 3,4 b 3,5 b 3,6 b 3,7
b 4,0 b 4,1 b 4,2 b 4,3 b 4,4 b 4,5 b 4,6 b 4,7
b 5,0 b 5,1 b 5,2 b 5,3 b 5,4 b 5,5 b 5,6 b 5,7
b 6,0 b 6,1 b 6,2 b 6,3 b 6,4 b 6,5 b 6,6 b 6,7
MM4 – Zeilen-Version
1. Schritt:Für jede Prozess-Zeile
Spalte wird gesucht, deren Spaltenindex dem Zeilenindex der ersten Zeile von B entspricht
Die Spalten von A werden nach links verschoben, sodass diese Spalte die erste in ihrem Block ist
Pro Zeile wird ein Block von A per Broadcast entlang der Zeile übertragen
a 0,0 a 0,1 a 0,2 a 0,3 a 0,4 a 0,5 a 0,6
a 1,0 a 1,1 a 1,2 a 1,3 a 1,4 a 1,5 a 1,6
a 2,1 a 2,2 a 2,3 a 2,4 a 2,5 a 2,6 a 2,0
a 3,1 a 3,2 a 3,3 a 3,4 a 3,5 a 3,6 a 3,0
a 4,1 a 4,2 a 4,3 a 4,4 a 4,5 a 4,6 a 4,0
a 0,0 a 0,1 a 0,0 a 0,1 a 0,0 a 0,1
a 1,0 a 1,1 a 1,0 a 1,1 a 1,0 a 1,1
a 2,3 a 2,4 a 2,3 a 2,4 a 2,3 a 2,4
a 3,3 a 3,4 a 3,3 a 3,4 a 3,3 a 3,4
a 4,3 a 4,4 a 4,3 a 4,4 a 4,3 a 4,4
33 Parallele Algorithmen zur Matrix Multiplikation
b 0,0 b 0,1 b 0,2 b 0,3 b 0,4 b 0,5 b 0,6 b 0,7
b 1,0 b 1,1 b 1,2 b 1,3 b 1,4 b 1,5 b 1,6 b 1,7
b 2,0 b 2,1 b 2,2 b 2,3 b 2,4 b 2,5 b 2,6 b 2,7
b 3,0 b 3,1 b 3,2 b 3,3 b 3,4 b 3,5 b 3,6 b 3,7
b 4,0 b 4,1 b 4,2 b 4,3 b 4,4 b 4,5 b 4,6 b 4,7
b 5,0 b 5,1 b 5,2 b 5,3 b 5,4 b 5,5 b 5,6 b 5,7
b 6,0 b 6,1 b 6,2 b 6,3 b 6,4 b 6,5 b 6,6 b 6,7
MM4 – Zeilen-VersionIteration (bis dieser Zustand wieder erreicht wird)
Alle Prozesse führen eine (sequentielle) Matrix Multiplikation aus (soweit möglich)
KommunikationsschrittNächster Prozess sendet Block von A per Broadcast (wenn alle Elemente von A in dieser Zeile benutzt)
Prozess sendet Block von B nach oben und empfängt Block von B von unten (wenn alle Elemente von B benutzt)
Umordnung wird rückgängig genacht
a 0,0 a 0,1 a 0,0 a 0,1 a 0,0 a 0,1
a 1,0 a 1,1 a 1,0 a 1,1 a 1,0 a 1,1
a 2,3 a 2,4 a 2,3 a 2,4 a 2,3 a 2,4
a 3,3 a 3,4 a 3,3 a 3,4 a 3,3 a 3,4
a 4,3 a 4,4 a 4,3 a 4,4 a 4,3 a 4,4
34 Parallele Algorithmen zur Matrix Multiplikation
MM4 - Komplexität
Berechnungen Gesamt
Umordnungsschritt
Kommunikation Gesamt
pq
mnoχ
1
pq
mn
1
pq
nop
1
pq
mnqlogq
1
pq
mn2
pq
no pmn q) log q(21pqlogq2
35 Parallele Algorithmen zur Matrix Multiplikation
Anmerkungen
Keiner der vorgestellten Algorithmen ist für alle Fälle optimal
Algorithmus von Li:Matrix mit den meisten Elementen sollte stationär sein
Vorteile auf großen Prozessor Grids
MM3, MM4, MM5
Zeilen-Version hat Vorteile, wenn die Blockgröße von A klein ist, oder die Anzahl der Prozess-Spalten gering ist
36 Parallele Algorithmen zur Matrix Multiplikation
Agenda
Einleitung
Algorithmen für quadratische Matrizen und quadratische Prozessor Grids
Algorithmen für nicht quadratische Matrizen und nicht quadratische Prozessor Grids
Fazit und Ausblick
37 Parallele Algorithmen zur Matrix Multiplikation
Fazit und Ausblick
Matrix Multiplikation ist gut parallelisierbar
Kein Algorithmus ist für alle Fälle optimal
Für jeden Fall kann der optimale Algorithmus gewählt werden
Vorgestellte Algorithmen sind nur ein kleiner AusschnittWeitere Varianten der Algorithmen von Cannon und Fox
Broadcast-Broadcast Algorithmus
Algorithmen auf Hypercubes
38 Parallele Algorithmen zur Matrix Multiplikation
Literatur
John Gunnels, Calvin Lin, Grog Morrow, Robert van de Geijn: Analysis of a Class of Parallel Matrix Multiplication Algorithms, Proc. Int’l Parallel Processing Symp., 1998.
Jin Li: A Poly: Algorithm for Parallel Dense Matrix Multiplication on Two-Dimensional Process Grid Topologies, Mississippi, 1996.
Michael J. Quinn: Parallel Programming with C with MPI and OpenMP, Boston, Mass., McGraw-Hill, 2004.
39 Parallele Algorithmen zur Matrix Multiplikation
Fragen
?
40 Parallele Algorithmen zur Matrix Multiplikation
a 0,0 a 0,1 a 0,2 a 0,3 a 0,4 a 0,5 a 0,6
a 1,0 a 1,1 a 1,2 a 1,3 a 1,4 a 1,5 a 1,6
a 2,0 a 2,1 a 2,2 a 2,3 a 2,4 a 2,5 a 2,6
a 3,0 a 3,1 a 3,2 a 3,3 a 3,4 a 3,5 a 3,6
a 4,0 a 4,1 a 4,2 a 4,3 a 4,4 a 4,5 a 4,6
b 0,0 b 0,1 b 0,2 b 0,3 b 0,4 b 0,5 b 0,6 b 0,7
b 1,0 b 1,1 b 1,2 b 1,3 b 1,4 b 1,5 b 1,6 b 1,7
b 2,0 b 2,1 b 2,2 b 2,3 b 2,4 b 2,5 b 2,6 b 2,7
b 3,0 b 3,1 b 3,2 b 3,3 b 3,4 b 3,5 b 3,6 b 3,7
b 4,0 b 4,1 b 4,2 b 4,3 b 4,4 b 4,5 b 4,6 b 4,7
b 5,0 b 5,1 b 5,2 b 5,3 b 5,4 b 5,5 b 5,6 b 5,7
b 6,0 b 6,1 b 6,2 b 6,3 b 6,4 b 6,5 b 6,6 b 6,7
MM5
Bei MM3 und MM4 können Zeilen- und Spaltenversion unabhängig von der Form der Matrix oder des Prozess Grids benutzt werden
Bei MM5
Zeilenversion nur, wenn q ≤ p
Spaltenversion nur, wenn p ≤ q
Also hier: Spaltenversion
41 Parallele Algorithmen zur Matrix Multiplikation
a 0,0 a 0,1 a 0,2 a 0,3 a 0,4 a 0,5 a 0,6
a 1,0 a 1,1 a 1,2 a 1,3 a 1,4 a 1,5 a 1,6
a 2,0 a 2,1 a 2,2 a 2,3 a 2,4 a 2,5 a 2,6
a 3,0 a 3,1 a 3,2 a 3,3 a 3,4 a 3,5 a 3,6
a 4,0 a 4,1 a 4,2 a 4,3 a 4,4 a 4,5 a 4,6
b 0,0 b 0,1 b 0,2 b 0,3 b 0,4 b 0,5 b 0,6 b 0,7
b 1,0 b 1,1 b 1,2 b 1,3 b 1,4 b 1,5 b 1,6 b 1,7
b 2,0 b 2,1 b 2,2 b 2,3 b 2,4 b 2,5 b 2,6 b 2,7
b 3,0 b 3,1 b 3,2 b 3,3 b 3,4 b 3,5 b 3,6 b 3,7
b 4,0 b 4,1 b 4,2 b 4,3 b 4,4 b 4,5 b 4,6 b 4,7
b 5,0 b 5,1 b 5,2 b 5,3 b 5,4 b 5,5 b 5,6 b 5,7
b 6,0 b 6,1 b 6,2 b 6,3 b 6,4 b 6,5 b 6,6 b 6,7
MM5
Iteration(bis dieser Zustand wieder erreicht wird)
Pro Prozess-SpalteAlle Zeilen von B, die für Berechnungen verwendet werden können, werden per Broadcast entlang der Spalte übertragen(evtl. mehrere Schritte)
Alle Prozesse führen eine (sequentielle) Matrix Multiplikation aus
Prozess sendet Block von A nach links und empfängt Block von A von rechts
b 0,0 b 0,1 b 2,2 b 2,3 b 2,4 b 4,5 b 4,6 b 4,7
b 1,0 b 1,1 b 3,2 b 3,3 b 3,4 b 5,5 b 5,6 b 5,7
b 6,5 b 6,6 b 6,7
b 1,0 b 1,1 b 2,2 b 2,3 b 2,4 b 4,5 b 4,6 b 4,7
b 2,0 b 2,1 b 3,2 b 3,3 b 3,4 b 5,5 b 5,6 b 5,7
b 6,5 b 6,6 b 6,7
42 Parallele Algorithmen zur Matrix Multiplikation
MM5 - Komplexität
Berechnungen Gesamt
Anzahl der Broadcast Schritte pro Iteration schlecht vorauszusagen
Falls q mod p = 0 (Spalten Version), reicht immer 1 Broadcast Schritt
Dann: Kommunikation Gesamt
pq
mnoχ
1
pq
mnq
1
pq
noplogq
pq
mn qno p log q1plogqq
Recommended