Einschätzung von Alg. zur parallelen Matrixmultiplikation

Algorithmen, Sprachunabhängige Diskussionen zu Konzepten, Programmiersprachen-Design
Antworten
Proxic
Beiträge: 14
Registriert: So Apr 24, 2016 9:38 pm

Einschätzung von Alg. zur parallelen Matrixmultiplikation

Beitrag von Proxic » So Nov 13, 2016 11:36 pm

Ich arbeite mich gerade ein wenig in die parallele Programmierung ein und da ich noch ein wenig Probleme mit dem Verständis habe und wie das ganze dann aufgeteilt wird, habe ich hier mal eine konkrete Frage zu mehreren Algorithmen, die aber alle dasselbe tun und zwar zwei Matrizen zu multiplizieren. Mir fällt es jetzt noch ein wenig schwer zu beurteilen, welcher von denen jetzt nun effizienter ist als der andere und auch ein wenig das warum. Das sind allerdings noch sehr einfache Verfahren.

1. Algorithmus:

Code: Alles auswählen

con for i = 1 to matA.rows do
	con for j = 1 to matB.cols do
		for k = 1 to matA.cols do
			c_ij += a_ik * b_jk
		end
	end
end
2. Algorithmus:

Code: Alles auswählen

for i = 1 to matA.rows do
	con for j = 1 to matB.cols do
		for k = 1 to matA.cols do
			c_ij += a_ik * b_jk
		end
	end
end
3. Algorithmus

Code: Alles auswählen

// r ist die transponirte Matrix von B
r =  b^T
for i = 1 to matA.rows do
	con for j = 1 to matB.cols do
		c_ij += vector-a_ik *vector- r_j
	end
end
und der letzte Algorithmus

Code: Alles auswählen

con for i = 1 to matA.rows do
	for j = 1 to matB.cols do
		c_ij += vector-a_i * b_j^T // transponirter Spaltenvektor
	end
end
(Nur zur Aufkörung: Ein Bodenstrich steht für einen Index und ein ^ für hoch)

Das sind erst einmal ziemlich einfache Algorithmen aber es geht ja auch erst einmal um's Prinzip. Ab 1000x1000 oder so lohnen die sich dann ja auch wohl schon und darum geht es ja auch. Ich will die Algorithmen vor allem für große Matrizen betrachten.

Wenn ich die also jetzt bewerten würde, dann ist doch sicherlich der erste auch mit einer der besten, da das Ergebnis dann in einem eigenem Thread abgearbeitet werden würde. Die innerste Schleife kann ja auch so immer ein Problempunkt sein, wenn diese sehr langsam ist, und damit auch zu einer schlechten Laufzeit führen.

Der zweite dagegen dürfte wohl einer der schlechtesten sein, da dieser ja nur die mittlere Schleife parallelisiert und die äußerste Schleife und die innerste sequentiell ausführt. Bei dem bin ich aber auch ehrlich gesagt wieder ein wenig verwirrt. das con der zweiten Schleife heißt ja nicht, dass die dritte Schleife auch parallel läuft, oder?

Der dritte dürfte eigentlich ganz okay sein, obwohl man da dann ja auch erst einmal die Matrix B transponieren müsste, was wieder 2 Schleifen erfordern würde, wobei dann nachher die Berchnung parallelisiert erfolgt, aber trotzdem ebend 2 zusätzliche Schleifen.

Bei dem letzten bin ich mir ehrlich gesagt gar nicht sicher aber da würde man doch dann die transponierung auch noch in dem sequentiellen Teil ausführen, oder wie? Scheint mir aber sehr schlecht zu sein aber bei dem bin ich mir gar nicth sicher.

Kann jetzt auch sein, dass ich hier totalen Stuss rede (was ich mal nicht hoffe) aber ich denke dann, dass ich die Algorithmen so bewerten würde:
1 Algo. Sehr gut, da die Berechnung sequentiell in einem anderen Thread staffindet.
3 Algo: Ganz gut, obowhl man noch zwei zusätzliche Schleifen bräuchte aber es wird ja vorher transponiert.
2 Algo. Eher schlecht, da die äußerste und die innerste sequentiell laufen?
4 Algo. Der schlechteste?

Wäre meine Einschätzung so richtig oder liege ich da ganz falsch oder nur hier und da?

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8489
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Einschätzung von Alg. zur parallelen Matrixmultiplikatio

Beitrag von Xin » Mo Nov 14, 2016 2:03 pm

Disclaimer: Ich habe noch nichts parallel programmiert um eine Berechnung zu beschleunigen. Entsprechend verfüge ich hier über keine Erfahrung. Allerdings ist Parallelprogrammierung ein wichtiges und breit diskutiertes Thema und ich laufe gerade auf ein Problem, was sich Parallelisieren lässt. Auf Fachkonferenzen bekommt man einiges mit.

Wichtigste Aussage: "Serielle Programmierung ist das Goto des 21. Jahrhunderts.", denn Computer werden eher breiter als schneller. Man muss sich also heute damit auseinander setzen, wie man Algorithmen breiter berechnen kann, da die Serielle Ausführung nicht beschleunigt werden kann.

Mit der Parallelen Programmierung kommen zwei neue Faktoren dazu: Erstens: Das Aufsplitten einer Aufgabe, wie auch das zusammen führen von Ergebnissen führt zu Kosten, die zusätzlich zur seriellen Abfertigung anfallen. Die benötigte Rechenleistung steigt also um eine Aufgabe durchzuführen und zwar jedesmal, wenn ein neuer Thread gestartet wird bzw. beendet wird.
Zweitens: Wenn Threads miteinander kommunizieren müssen wird es teuer. Darum eignen sich besonders Aufgaben, die unabhängig voneinander arbeiten, um parallelisiert zu werden.

In Deinem Fall müssen die Threads nicht miteinander kommunizieren.
Dein Hauptaufwand ist also Threads zu Starten und zu vernichten. Und hier stellt sich nun die Frage, wie oft Du das machen möchtest. Im Idealfall teilst Du also weit oben auf und jeder Thread bearbeteitet die darin liegenden Schleifen seriell. So musst Du nur selten Threads starten und stoppen. Wenn Du nun natürlich eine 3xX Matrix verrechnest, hast aber eine 4-Core-CPU, dann bleibt eine CPU arbeitslos - Du verschenkst also bereitstehende Leistung.
Wenn Du die innere Schleife parallelisierst arbeiten alle CPUs. Dafür erhöht sich der Aufwand, um Threads zu erzeugen und zu vernichten, was den Vorteil wieder zunichte machen kann.
Das Geheimnis ist eine gute Balance zwischen Threads und Arbeitsmenge zu finden.

Und das ist bedauerlicherweise wirklich ausprobieren. Zumal die eine Lösung auf einem Dual-Core schneller sein kann, wo viele Threads erzeugen werden, die darauf warten müssen, dass ein Kern frei wird, um überhaupt anlaufen zu können, die andere auf einem Octa-Core schneller läuft. Aktuelle Xeon-CPUs haben 24 Kerne, also 48 parallele Threads. Pro CPU, die können ja auch mit mehreren CPUs verbaut werden. Da ist dann vielleicht auch mehr Zeit vorhanden, um im Hintergrund Threads anzulegen oder zu verwerfen.

Muss man Ausprobieren.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

nufan
Wiki-Moderator
Beiträge: 2446
Registriert: Sa Jul 05, 2008 3:21 pm

Re: Einschätzung von Alg. zur parallelen Matrixmultiplikatio

Beitrag von nufan » Mo Nov 14, 2016 10:15 pm

In deinem Beispiel geht es vor allem um die ideale Verwendung des Caches. Ich kann dir für Details Slides meiner Uni anbieten in denen genau dieses Beispiel in seiner sequentiellen Form behandelt wird, die sind öffentlich: http://www.par.tuwien.ac.at/teaching/20 ... OpenMP.pdf (bzw. Übersicht: http://www.par.tuwien.ac.at/teaching/2016w/184.710.psp)
Auf Folie 24 findest du die Ergebnisse eines Benchmarks (Best-Case: 0.32s, Worst-Case: 13.80s).

Wo genau du die Parallelisierung einsetzt ist eine gute Frage. Wie Xin bereits erwähnt hat musst du versuchen den Overhead akzeptabel zu halten - und das geht in der Praxis oft wirklich nur durch ausprobieren.

Proxic
Beiträge: 14
Registriert: So Apr 24, 2016 9:38 pm

Re: Einschätzung von Alg. zur parallelen Matrixmultiplikatio

Beitrag von Proxic » So Nov 20, 2016 1:09 am

@Xin
Genau wegen den genannten Gründen beschäftige ich mich ja auch unter anderem damit. Das Material das ich gerade durcharbeite nennt diese Vorteile / Nachteile natürlich auch und das man wirklich erst einmal ein großes Problem braucht, was sich auch aufteilen lässt, also nach dem Prinzip "Teile und Herrsche" und dann ggf. wieder zusammenfügen lässt, wie z.B beim Mergesort.
Xin hat geschrieben:In Deinem Fall müssen die Threads nicht miteinander kommunizieren.
Dein Hauptaufwand ist also Threads zu Starten und zu vernichten. Und hier stellt sich nun die Frage, wie oft Du das machen möchtest. Im Idealfall teilst Du also weit oben auf und jeder Thread bearbeteitet die darin liegenden Schleifen seriell. So musst Du nur selten Threads starten und stoppen. Wenn Du nun natürlich eine 3xX Matrix verrechnest, hast aber eine 4-Core-CPU, dann bleibt eine CPU arbeitslos - Du verschenkst also bereitstehende Leistung.
Wenn Du die innere Schleife parallelisierst arbeiten alle CPUs. Dafür erhöht sich der Aufwand, um Threads zu erzeugen und zu vernichten, was den Vorteil wieder zunichte machen kann.
Das Geheimnis ist eine gute Balance zwischen Threads und Arbeitsmenge zu finden.
Ja, das stimmt. Das mit dem starten und vernichten kann man aber auch ein wenig umgehen, indem man bspw. einen ThreadPool verwendet, den es ja bspw. in C# und auch Java gibt. Dort werden Threads dann recycelt, anstatt immer wieder neue Threads zu erzeugen und zu vernichten. Für 3x3 Matrizen lohnt sich das ganze natürlich mit Threads nicht, da der sequentielle Algorithmus da eh noch schneller ist, weil man dann ja auch noch die Threads etc. erzeugen muss. Es geht ja wie oben schon gesagt um n > 1000x1000 Matrizen.

Dass das ganze auch stark von der Anzahl der CPU's und der Implementierung abhängt ist auch klar aber es ging mir ja auch un eine Abschätzung, die eine einigermaßen gute Implementierung annimmt und eine durchschnittliche Anzahl von Kernen, also 4 oder 6.

@nufan
Danke, werde ich mir mal anschauen.


Ich werde die vier Varianten auch alle definitiv mal ausprobieren und auch die Laufzeit messen und dann mal schauen, was da besser oder schlechter ist. Bei der dritten und vierten Variante frage ich mich aber auch, wie das dann funktionieren soll. Würde das bei der Berechnung dann echt mit 2 Schleifen funktionieren? Ich habe das mal mit der drittem Algorithmus und einer Matrix getestet aber da komme ich nicht auf das richtige Ergebnis. Würde das dann nicht so aussehen (erst einmal seriell)?

Code: Alles auswählen

double[][] a = new double[][]{{1,2},{3,4}};
double[][] b = new double[][]{{1,2},{3,4}};

for(i = 0; i < rowsMatA; i++) {
	for(j = 0; j < columnsMatB; j++) {
		c[i][j] = a[i][0] * r[0][j];
	}
}
Das mit dem transponieren habe ich natürlich vorher auch gemacht. Die transponierte Matrix von b, also r wäre dann ja, um bei der Programmierdarstellung zu bleiben

Code: Alles auswählen

double[][] r = new double[][]{{2,4},{3,5}};
Das Ergebnis was ich dann kriege ist aber

Code: Alles auswählen

{{0,4},{6,12}}
aber müsste das nicht wie bei der ersten Variante

Code: Alles auswählen

{{10,13},{22,29}}
sein? Ich habe das mal per Hand nachgerechnet und auch noch einmal online eingegeben und da sollte doch dann eigentlich {{10,13},{22,29}} rauskommen oder nicht? Das Ergebnis sollte ja mit allen vier Algorithmen das gleiche sein. Ich habe das jetzt aber nach dem Schema des ersten per Hand berechnet. Ich bin mir aber nicht zu 100% sicher, ob ich den 3. Algorithmus so richtig geschrieben habe, weil ich das so mit Matrizen glaube ich noch nie berechnet habe.

Proxic
Beiträge: 14
Registriert: So Apr 24, 2016 9:38 pm

Re: Einschätzung von Alg. zur parallelen Matrixmultiplikatio

Beitrag von Proxic » So Nov 20, 2016 2:20 am

Ach, mist. b sollte eigentlich {{2,3},{4,5}} sein. Was ich vielleicht auch noch sagen sollte ist, dass ich mir vorher die Anzahl der Zeilen und Spalten hole. Die werden dann in den Variablen rowsMatrixA und columnsMatrixB gespeichert aber ich hoffe mal das ist so klar und c sieht so aus:

Code: Alles auswählen

double[][] c = new double[rowsMatrixA][columnsMatrixB];
Ich denke aber auch, dass es wohl nicht nötig ist den zweiten überhaupt zu implementieren, oder doch? Vom Gedanken her ist der doch wirklich auch mit einer der schlechtesten, egal wie man diesen dann implementieren würde?

Antworten