Java Matrixmultiplikation mit Threads

[raven16]

Hallo,

ich möchte Operationen eine Matrixmultiplikation teilweise parallel in Threads berechnen. Hier zunächst der serielle Algorithmus:

for(int i=0; i<M; i++){ // row count of matrix A
	for(int j=0; j<O; j++){ // column count of matrix B
		for(int k=0; k<N; k++){ // index for scalar product
			valC[i][j] += valA[i][k] * valB[k][j];  
		}
	}
}

Die äußeren beiden Schleifen sollen nun jeweils neue Threads erstellen, das heißt in jedem Thread der äußeren Schleife werden weitere Threads durch die mittlere Schleife erzeugt, die dann die innere Schleife ausführen. Meine Frage dazu zielt eher in Richtigung Programmdesign ab. Am liebsten würde ich alles in einer Methode erledigen. Brauche ich zusätzlich dann noch für die äußeren Schleifen zwei verschiedene Thread-Klassen, die von Runnable erben oder kann ich dies auch in einer Klasse erledigen? Kann sich überhaupt eine Klasse selbst instanziieren?

Viele Grüße

 

[Crumar]

Worauf zielst du ab? Performance? Das wäre nämlich relativ unwahrscheinlich ein Performance Gewinn. Oder zum lernen? Dann würde ich dir raten, denn Schluss zu ziehen, dass das hier im Normalfall nicht sinnvoll ist.
Zumindest nicht in der Art und Weise, wie du es vor hast.

Meines Erachtens nach wäre es auch schlechtes Programmdesign (in vielen Fällen) wenn Subthreads wieder Subthreads starten.

 

[raven16]

Worauf zielst du ab? Performance? Das wäre nämlich relativ unwahrscheinlich ein Performance Gewinn. Oder zum lernen? Dann würde ich dir raten, denn Schluss zu ziehen, dass das hier im Normalfall nicht sinnvoll ist.

Du hast recht. Das ist rein für Lernzwecke. Haben mehrere Varianten vorgegeben, wovon wir mindestens zwei testen sollen.

 

[VikingGe]

Meines Erachtens nach wäre es auch schlechtes Programmdesign (in vielen Fällen) wenn Subthreads wieder Subthreads starten.

Es würde ja schon reichen, eine Reihe Worker-Threads zu starten, eine Queue einzurichten und da dann jeweils Jobs zu dispatchen. Java bietet da bereits irgendwelche Klassen für, aber es ist auch keine Raketenwissenschaft, sowas selbst zu implementieren - etwas tricky, wenn Jobs selbst wieder Jobs starten sollen, aber solange das nicht gefordert ist, beschränkt sich das auf eine Queue und die Verwendung der wait- und notify-Methoden.

Performancemäßig ist für diesen Anwendungsfall zu beachten, dass das Programm zumindest bei wirklich großen Matrizen permanent im Speicherbandbreitenlimit kleben wird und damit bestenfalls mit zwei Kernen skaliert. Ich persönlich finde ja die Ansätze, das zu umgehen und deutlich effizienter mit dem Cache zu arbeiten, weitaus interessanter, aber gut.

 

[Robert]

Um mal ganz kurz noch am Rande des Themas etwas beizutragen: Matrizen lassen sich auch (etwas) effizienter multiplizieren. Wenn ich mich recht erinnere in O(n^2,7x) statt O(n^3). Leider finde ich gerade den Rechentrick dafür nicht wieder, aber du könntest das ja mal recherchieren, falls es dich interessiert.

Grüße

Edit: Gefunden: Klick

 

[Crumar]

Es würde ja schon reichen, eine Reihe Worker-Threads zu starten, eine Queue einzurichten und da dann jeweils Jobs zu dispatchen.

Dies war eine Sache, auf die ich hinaus wollte . So entgeht man zumindest dem total Overhead Chaos von ThreadStart / ThreadEnde für eine einzige Berechnung.

Edit: @TE Wenn ihr Java 8 verwenden darfst, schau dir Lambda expressions an und wie man diese an einen Thread übergibt.

Alternativ kannst du natürlich auch einen regulären Thread Start verwenden und die Stücke im Code erstmal in drei Methoden aufteilen.

 

[raven16]

Dies war eine Sache, auf die ich hinaus wollte . So entgeht man zumindest dem total Overhead Chaos von ThreadStart / ThreadEnde für eine einzige Berechnung.

Im Prinzip hast du/ihr damit recht. Wir haben quasi 4x den gleichen Algorithmus in Pseudocode bekommen und in jedem Algorithmus soll etwas anderes parallel laufen. Wir vergleichen dann die Performance und die Zeit bzw. Speedup zwischen serielle und parallele Ausführung.

Edit: @TE Wenn ihr Java 8 verwenden darfst, schau dir Lambda expressions an und wie man diese an einen Thread übergibt.

Danke für den Tipp, werde ich mir bei Gelegenheit noch ansehen :-)

Alternativ kannst du natürlich auch einen regulären Thread Start verwenden und die Stücke im Code erstmal in drei Methoden aufteilen.

Wenn ich drei Methoden in einer Thread Klasse schreibe, dann müsste ich ja noch irgendwie feststellen können, in welche der drei for-Schleifen ich mich befinde. Kann ich in der Thread Klasse auch ein Objekt von der eigenen Klasse instanziieren?

Ergänzung (29. November 2016)

Um mal ganz kurz noch am Rande des Themas etwas beizutragen: Matrizen lassen sich auch (etwas) effizienter multiplizieren. Wenn ich mich recht erinnere in O(n^2,7x) statt O(n^3).

Danke für den Tipp. Wenn ich wirklich mal vor haben sollte, ein effizientes Matrizenprogramm zu schreiben, dann behalte ich dies im Hinterkopf. Bei meiner Übung kommt es jedoch mehr auf die Threads an :-)

 

[nullPtr]

Danke für den Tipp. Wenn ich wirklich mal vor haben sollte, ein effizientes Matrizenprogramm zu schreiben, dann behalte ich dies im Hinterkopf. Bei meiner Übung kommt es jedoch mehr auf die Threads an :-)

Hmh, nein. Der Algorithmus von Strassen ist kompliziert und man müsste erstmal evaluieren, wieviel Laufzeit er wirklich spart. Bei Effizienz kommt es nicht unbedingt auf die Komplexitätsklasse an, sondern auch auf den Faktor, der in ihr verschwindet. Dinge wie Cache-Lokalität, etc. spielen da rein.

Das vorgestellte Konzept mit Worker-Threads ist das kanonische. Ich weiß aber nicht, wer auf die Idee kommt, das als Aufgabe zu stellen. Für sowas würde man C/C++/Fortran mit OpenMP verwenden (was du übrigens mit Worker-Threads nachbauen würdest).

 

[Drexel]

Es würde ja schon reichen, eine Reihe Worker-Threads zu starten, eine Queue einzurichten und da dann jeweils Jobs zu dispatchen. Java bietet da bereits irgendwelche Klassen für, aber es ist auch keine Raketenwissenschaft, sowas selbst zu implementieren - etwas tricky, wenn Jobs selbst wieder Jobs starten sollen, aber solange das nicht gefordert ist, beschränkt sich das auf eine Queue und die Verwendung der wait- und notify-Methoden.

Performancemäßig ist für diesen Anwendungsfall zu beachten, dass das Programm zumindest bei wirklich großen Matrizen permanent im Speicherbandbreitenlimit kleben wird und damit bestenfalls mit zwei Kernen skaliert. Ich persönlich finde ja die Ansätze, das zu umgehen und deutlich effizienter mit dem Cache zu arbeiten, weitaus interessanter, aber gut.

Ja so würde ich es auch machen. Am besten noch so programmieren, dass so viele Threads erzeugt werden, wie die Maschine CPU Cores hat, dann sollte sich da noch was gewinnen lassen. Zum üben OK, in der Praxis sollte man sich natürlich Gedanken machen, ob der Mehraufwand und die entstehende Komplexität es wirklich Wert sind...