Schreiben Sie ein Multithread-Programm, in dem eine Matrizenmultiplikation C = A * B
von zwei 4x4-Matrizen A und B mit Integerelementen wahlweise von einer beliebigen
Anzahl von Threads (also von einem, von zwei, von drei, …, von vierzehn, von fünfzehn
oder von sechzehn Threads) arbeitsteilig durchgeführt wird. Die Zahl der arbeitenden
Threads soll beim Aufruf des Programms als Aufrufparameter angegeben werden
können.
Verwenden Sie dabei die beiden Ausgangsmatrizen
Ihr Programm sollte als Ergebnis die beiden Ausgangsmatrizen A und B sowie
die arbeitsteilig berechnete Produktmatrix C = A * B ausgeben.
kann jemand mir einen Hinweis geben, wo ich vorgehen kann?
ich möchte diese so anpassen dass man thread_count = Integer.parseInt(args[0]) statt public static final int NUM_OF_THREADS = 16; auch Ergebnisse bekommt.
ich hoffe ihr hilft mir
public class MatrixMultiThread {
public static final int NUM_OF_THREADS = 16;
public static void main(String args[])
{
int row;
int col;
int MatrixA[][] = {{1,-2,3,4},{-2,3,0,1},{4,-1,2,1},{-2,1,3,-1}};
int MatrixB[][] = {{2,-4,-1,1},{-1,1,-2,2},{5,0,3,-2},{1,-2,1,0}};
int MatrixC[][] = new int[4][4];
int threadcount = 0;
// int thread_count = Integer.parseInt(args[0]);
//
// int[] scount = new int [16 % threadcount];
//
// System.out.println(scount);
Thread[] thrd = new Thread[NUM_OF_THREADS];
try
{
for(row = 0 ; row < 4; row++)
{
for (col = 0 ; col < 4; col++ )
{
thrd[threadcount] = new Thread(new MultiplicationThreading(row, col,MatrixA, MatrixB, MatrixC));
thrd[threadcount].start();
thrd[threadcount].join();
threadcount++;
}
}
}
catch (InterruptedException ie){}
// Ausgabe Matrix A
System.out.println(" Matrix A: ");
for(row = 0 ; row < 4; row++)
{
for (col = 0 ; col < 4; col++ )
{
System.out.print(" "+MatrixA[row][col]);
}
System.out.println();
}
// Ausgabe Matrix B
System.out.println(" Matrix B: ");
for(row = 0 ; row < 4; row++)
{
for (col = 0 ; col < 4; col++ )
{
System.out.print(" "+MatrixB[row][col]);
}
System.out.println();
}
// Ausgabe Matrix C
System.out.println(" Resulting Matrix C: ");
for(row = 0 ; row < 4; row++)
{
for (col = 0 ; col < 4; col++ )
{
System.out.print(" "+MatrixC[row][col]);
}
System.out.println();
}
// System.out.println(threadcount);
//
// for(k=0 ; k < threadcount ; k++)
// {
//
// }
//
}
}
public class MultiplicationThreading implements Runnable
{
private int row;
private int col;
private int MatrixA[][];
private int MatrixB[][];
private int MatrixC[][];
public MultiplicationThreading(int row, int col,int MatrixA[][], int MatrixB[][], int MatrixC[][] )
{
this.row = row;
this.col = col;
this.MatrixA = MatrixA;
this.MatrixB = MatrixB;
this.MatrixC = MatrixC;
}
@Override
public void run()
{
for(int k = 0; k < MatrixB.length; k++)
{
MatrixC[row][col] += MatrixA[row][k] * MatrixB[k][col];
}
}
}
das ist doch schon eine ganze Menge Integer.parseInt(args[0]);
sollte funktionieren, wenn ein Parameter übergeben wird, was man freilich erstmal hinbekommen muss,
Starten von Konsole oder IDE, Frage zur Parameterübergabe?
die threadcount-Variable verwendest du freilich schon anders, in erster Ansicht ungeeignet, aber du kannst ja beliebig weitere einführen und sei es vorerst ‘n’,
den eingelesenen Wert in ‘n’ zu speichern und dann ein Array dieser Größe anzulegen sollte überschaubar schwer sein?
der Rest ist noch nicht allzu gut,
bei einem 4x4er Array legst du genau 16 Threads an, das passt nur im Moment zusammen, nicht allgemein
ein richtig schönes Konzept zur Aufteilung habe ich nicht aus dem Stehgreif, vielleicht in den Internet-Artikeln dazu vorhanden,
siehe auch edit meines ersten Postings,
pauschal könntest du die Anzahl Felder = m durch die Anzahl Threads = t teilen, auf Rundungen achten,
und Threads Felder-Nummern von bis verteilen,
hier bei 4x4-Matrix = 16 Felder und krumme Anzahl von 3 Threads bekäme der erste 6 Felder (erste Zeile + zwei der nächsten Zeile), die anderen je 5 Felder usw.,
schön wird das wie gesagt nicht, Arbeit und klein-klein Variablen…
Threads zu starten und direkt mit join auf deren Ende zu warten erzwingt Ausführung hintereinander, der erste ist fertig (man wartet ja) bevor der zweite beginnt,
das ist die exakt falsche Verwendung, sollte man nicht so deutlich einbauen…
die Thread-Verarbeitung mag hier eh nicht sinnvoll sein, aber zumindest kann man mitspielen:
ERST alle Threads starten, DANN in einer zweiten Schleife bei allen join aufrufen, warten bis alle fertig sind
zum Vergleich:
du hast eingebaut: Lehrer verteilt Klausur an ersten Schüler, wartet bis der fertig ist, geht dann zum nächsten Schüler usw.,
richtig ist, an alle Schüler Klausur zu verteilen, dann auf Ende aller zu warten
Code wie Ausgabe einer Matrix muss man nicht 3x hintereinander schreiben,
lieber eine Methode mit Parameter einführen,
dass ist eines der wesentlichen Elemente von Programmierung,
wäre wichtiger zu erkennen und erlernen als alles andere in der Aufgabe (etwa Details zu Thread usw.)
überhall hast du 4 stehen, die Matrixen können aber auch andere Größe haben, gehe von length der Arrays aus!
edit: na gut, 4 immerhin in der Aufgabe genannt, dennoch unnötig starr,
SlaterB hat ja schon angedeutet, dass es ziemlich frickelig wäre, diese Aufteilung der Aufgaben für mehrere Threads „manuell“ umzusetzen. Bei einer 4x4-Matrix, die mit 3 Threads berechnet wird könnte man das auf 6+6+4 oder 5+5+6 aufteilen („möglichst gleichmäßig“, ja…), aber wie spezifiziert man die Einträge, um die ein Thread sich kümmert? Sollte man dem „MultiplicationThreading“ weitere Parameter geben? Das wird eklig und unübersichtlich.
Die einfache Lösung wäre da, einen ThreadPoolExecutor zu erstellen, der genau die festgelegte Anzahl von threads hat. Dem kann man dann einfach eine Liste von 16 runnables (Callables) hinwerfen, und der kümmert sich dann schon drum, das richtig aufzuteilen.
int numRows = 4;
int numCols = 4;
int n = 3;
ExecutorService executor = Executors.newFixedThreadPool(n);
Collection<Callable<Object>> tasks = new ArrayList<Callable<Object>>();
for (int r=0; r<numRows; r++)
{
for (int c=0; c<numCols; c++)
{
Runnable runnable = createRunnable(r, c);
tasks.add(Executors.callable(runnable));
}
}
try
{
executor.invokeAll(tasks);
}
catch (InterruptedException e)
{
Thread.currentThread().interrupt();
}
Vielleicht würde der eine odere andere Lehrer das als „schummeln“ ansehen. Ich halte dagegen: Know your API
ist aber auch unabhängig vom Rahmen der Aufgabe fürs reale Leben wenig hilfreich,
wenn man an tatsächlich parallele Ausführung auf z.B. verschiedenen CPUs glaubt und die Arrays in die MB gehen so dass sich das auch etwas lohnen würde,
dann will man doch nicht Millionen Runnable, zwar parallel aber jeweils einzeln abgearbeit…,
gegenüber einzelnen Runnables mit Schleifenarbarbeitung für z.B. zugeordneten krummen Indexbereich 4.387.980 bis 6.759.879 erschreckender Mehraufwand
Herzlichen Dank für eure Hilfe und Rückmeldungen.
anscheinend hat Marco13 eine mögliche Lösung hier aufgeschrieben. Aber ich bin kein Profi und kann nicht dem Prof das erklären wie ich das gemacht habe.
SlaterB hat diese Aufgabe sehr gut verstanden. Wenn ich alles manuell mache, ist alles sehr übersichtlich.
Kann man diese auch mit do while Schleife lösen?
Zum Beispiel man erzeugt immer einen neuen Thread und fragt ob es eine Arbeit zu berechnen gibt?
Wir haben z.B. 5 Thread und 16 Matrix Berechnungen. Die erste vier machen jeweils 3 und der letzte Thread den Rest (Sprich die letzte Berechnung …+A(4,4)*B(4,4))
[quote=saruul]Zum Beispiel man erzeugt immer einen neuen Thread und fragt ob es eine Arbeit zu berechnen gibt?
Wir haben z.B. 5 Thread und 16 Matrix Berechnungen. Die erste vier machen jeweils 3[/quote]
wie kommst du auf 3 für die ersten vier?
durch Berechnung, eine do-while-Schleife brauchst du dann nicht, du weißt wieviele Threads mit welchen Werten
insbesonder ist ja auch gerade die Anzahl Threads vorgegeben! nix mit immer neuen Threads, Anzahl bekannt, darauf die Last verteilen,
bisschen musst du schon selber machen, insbesondere Fragen nach Code teils wenig aussichtsreich
(aber manchmal kommt noch wer anders ohne große Worte doch mit Code )
überlege für dein Beispiel ganz konkret wer welche row/col-Kombinationen bekommen sollte,
und dann Verfahren wie zu organisieren,
ein Mittelweg hin zu Marco13s Lösung wäre, die MultiplicationThreading-Objekte im Voraus anzulegen,
dann wie bisher die Doppelschleife und jede row/col-Kombination einem MultiplicationThreading nach dem anderen reihum in eine dortige Liste zuzufügen,
danach beginnen dann alle mit der Arbeit ihrer jeweiligen Auftragsliste
bei riesigen Mengen immer noch qualvoller Aufwand, aber schon paar Stufen besser als einzelne Runnables in ExecutorService,
und vor allem für dich wichtig ExecutorService nicht nötig
row/col-Kombination sind etwas kompliziert zu handhaben,
gewisse Alternative ist, die Felder von 1-16 durchzunummerien (im allgemeinen Fall nicht genau 16),
dann nur noch Indexe zu merken und dann sind auch leichter Vorgaben a la ‚bearbeite Index 5-9‘ zu machen,
in der Abarbeitung müsste man dann auf row/col zurückrechnen
[QUOTE=SlaterB]ein Mittelweg hin zu Marco13s Lösung wäre, die MultiplicationThreading-Objekte im Voraus anzulegen, dann wie bisher die Doppelschleife und jede row/col-Kombination einem MultiplicationThreading nach dem anderen reihum in eine dortige Liste zuzufügen,
danach beginnen dann alle mit der Arbeit ihrer jeweiligen Auftragsliste[/QUOTE]
Hmm, wäre es nicht pfiffiger die Aufträge nicht im voraus auf die Threads zu verteilen, sondern die Threads sich ständig neue Aufträge abholen zu lassen - solange der Vorrat reicht? Die Aufgabenstellung legt ja nahe, das die Threads jeweils Skalarprodukte berechnen sollen. Ein solcher Auftrag lässt sich leicht als Klasse formulileren:
class Skalarprodukt {
// wird vom Auftraggeber ausgefuellt
double[][] m1, m2;
int zeilenIndex, spaltenIndex;
// wird vom Bearbeiter ausgefuellt
double ergebnis;
}
Dazu bräuchte man dann nur noch zwei synchronized Methoden: Eine die neue Aufträge herausgibt und eine zweite, welche die bearbeiteten Aufträge wieder entgegennimmt. Die Threads besäßen dann eine Hauptschleife, in der sie eine neue Aufgabe anfordern, diese bearbeiten, und das Ergebnis wieder abliefern. Wenn es keine neuen Aufgaben mehr gibt können sich die Threads beenden.
Ein solches System wäre recht leicht zu implementieren, und die Lastverteilung ergibt sich automatisch.
Ach quatsch. Dann kann man auch gleich an Einhörner, Kobolde und Eskimos glauben :o)
Mal im Ernst: Es ist ja klar, dass es keinen Sinn macht, 16 dot-producs aus 4D-vektoren auf 16 Threads zu machen. Deswegen bin ich schon davon ausgegangen, dass die Aufgabe mit dem Hintergedanken gestellt wurde, was man denn macht, wenn man eine „große“ Matrix hat. (Dewegen will auch nochmal deinen wichtigen Hinweis hervorheben, dass die „4“ nicht überall hartverdrahtet stehen sollte, sondern es stattdessen zwei Variablen, z.b. numRows und numCols geben sollte).
BTW: Tatsächlich machen „die Großen“ so eine parallele Matrixmultiplikation eher nicht mit dot products (also nicht mit inner products), sondern als Summe von outer products. Da hatte ich ja bei diesem Hazelcast-Wettbewerb was gebastelt, um diesen Beitrag herum, und einem ParallelMatrixMultiplicator.
Wie auch immer: Man sollte den Overhead von „vielen“ Runnables nicht überschätzen. Der ThreadPool und seine interne Magic sind schon sehr ausgefeilt, so dass der Overhead da „nicht so groß“ sein sollte. Insbesondere sollte man die Tücken des Schedulings nicht außer Acht lassen: Wenn man die Tasks am Anfang „perfekt“ (und starr!) in gleich große Stücke aufteilt, kann sich daran nichts mehr ändern. Wenn ein CPU-Kern zwischendurch mal den GC laufen läßt (oder damit beschäftigt ist, das „Sie haben Post“-Fenster vom Mailclient einzublenden :D) dann kann es sein, dass einer der Tasks „hinterherhinkt“. Vielleicht sind die anderen Kerne dann schon fertig, und einer arbeitet noch am Rest seines (großen!) Blocks rum, obwohl er eigentlich Arbeit abegeben könnte. Wenn man die Tasks etwas feingranularer macht, und jeder, der gerade Zeit hat, sich einen kleinen, übschaubaren Task abholt und bearbeitet, kann dieses Problem nicht auftreten.
Das entspricht auch ziemlich genau dem, was @Dow_Jones gesagt hat:
[QUOTE=Dow_Jones;91577]Hmm, wäre es nicht pfiffiger die Aufträge nicht im voraus auf die Threads zu verteilen, sondern die Threads sich ständig neue Aufträge abholen zu lassen - solange der Vorrat reicht?
[/quote]
Nur braucht man da halt (eigentlich) nichts mehr selbst zu implementieren, weil der ThreadPoolExecutor genau das schon macht.
BTW: Im ForkJoinPool ist diser Gedanke auf die Spitze getrieben. Eigentlich mit einem etwas eigeschränkten Anwendungsbereich (Fork Join eben :)), aber tatsächlich ist das work-stealing dort so brutalst-effizient implementiert, dass es gerüchteweise Fälle geben soll, wo man einen ForkJoinPool statt eines normalen ThreadPoolExecutors verwenden sollte, weil ersterer einfach trickreicher implementiert ist.
Trickreich…
Es gibt nicht viele Stellen in der Standard-Java-API, wo
die Implementierungskommentare 200 Zeilen haben
so viel mit „Unsafe“ hantiert wird
so viel mit Bitshifts getrickst wird
so viel „implizites Wissen“ über das Java Memory Model gezielt ausgenutzt wird und
(ohne anmaßend erscheinen zu wollen) ich beim drüberlesen schlicht demütig aussteige…
aber der ForkJoinPool gehört dazu:
for (int r = w.seed, k = r, j = -(m + m); j <= m + m; ++j) {
ForkJoinTask<?> t; ForkJoinTask<?>[] q; int b, i;
ForkJoinWorkerThread v = ws[k & m];
if (v != null && (b = v.queueBase) != v.queueTop &&
(q = v.queue) != null && (i = (q.length - 1) & b) >= 0) {
long u = (i << ASHIFT) + ABASE;
if ((t = q**) != null && v.queueBase == b &&
UNSAFE.compareAndSwapObject(q, u, t, null)) {
int d = (v.queueBase = b + 1) - v.queueTop;
v.stealHint = w.poolIndex;
if (d != 0)
signalWork(); // propagate if nonempty
w.execTask(t);
}
r ^= r << 13; r ^= r >>> 17; w.seed = r ^ (r << 5);
return false; // store next seed
}
else if (j < 0) { // xorshift
r ^= r << 13; r ^= r >>> 17; k = r ^= r << 5;
}
else
++k;
}
while ((((e = (int)(c = ctl)) | (u = (int)(c >>> 32))) &
(INT_SIGN|SHORT_SIGN)) == (INT_SIGN|SHORT_SIGN) && e >= 0) {
if (e > 0) { // release a waiting worker
int i; ForkJoinWorkerThread w; ForkJoinWorkerThread[] ws;
if ((ws = workers) == null ||
(i = ~e & SMASK) >= ws.length ||
(w = ws**) == null)
break;
long nc = (((long)(w.nextWait & E_MASK)) |
((long)(u + UAC_UNIT) << 32));
if (w.eventCount == e &&
UNSAFE.compareAndSwapLong(this, ctlOffset, c, nc)) {
w.eventCount = (e + EC_UNIT) & E_MASK;
if (w.parked)
UNSAFE.unpark(w);
break;
}
}
else if (UNSAFE.compareAndSwapLong
(this, ctlOffset, c,
(long)(((u + UTC_UNIT) & UTC_MASK) |
((u + UAC_UNIT) & UAC_MASK)) << 32)) {
addWorker();
break;
}
}
Jup. Alles klar.
Aber mal zurück zum eigentlichen Problem: Diese Verteilung der Aufgaben ist eben wirklich ein bißchen tricky.
wie kommst du auf 3 für die ersten vier?
Da komm’ ich auch drauf. Bei „naiven“ Verteilungen, die für große Datenmengen meistens ganz gut funktionieren, können u.U. recht große Unterschiede zwischen den Taskgrößen auftreten. Wichtig ist hier aber auch der Punkt
Ich denke, das sollte man so machen. Bei allem anderen würde man in die Hölle kommen: „Thread 0 macht Zeile 0 und die ersten 3 von Zeile 1, Thread 1 macht das letzte von Zeile 1, Zeile 2 und das erste von Zeile 3 … :sick:“. Nene, indizes und zurückrechnen ist da leichter. Hab’ mal grob geschaut, das könnte etwa so aussehen
public class MatrixThreadDistribution
{
public static void main(String[] args)
{
int numThreads = 5;
int numRows = 4;
int numCols = 4;
int totalIndices = numRows * numCols;
int indicesPerThread = (totalIndices - 1) / numThreads + 1;
int spare = indicesPerThread * numThreads - totalIndices;
int currentIndex = 0;
for (int i=0; i<numThreads; i++)
{
int minIndex = currentIndex;
int maxIndex = minIndex+indicesPerThread;
if (i < spare)
{
maxIndex--;
}
currentIndex = maxIndex;
// Here, a task could be created, and receive
// minIndex, maxIndex, numCols + the Matrices
// ...
System.out.println("Thread "+i+" handles "+minIndex+" to "+maxIndex);
for (int index=minIndex; index<maxIndex; index++)
{
int row = index/numCols;
int col = index%numCols;
System.out.println(" "+row+", "+col);
}
}
}
}
Wenn man dem MultiplicationThreading nun die genannten Infos (minIndex, maxIndex, numCols und die Matrizen) übergibt, kann man in seiner run-Methode praktisch das gleiche machen, wie vorher - nur eben für alle Indizes:
for (int index=minIndex; index<maxIndex; index++)
{
int row = index/numCols;
int col = index%numCols;
// Rest wie vorher....
}
Hallo zusammen
noch mal vielen Dank für die Vorschläge.
Ich habe die oben geschrieben Code von Marco13 ausprobiert.
Aber wenn ich numThread=7 habe, ist indicesPerThread=15/7+1.
Hast du diese Code speziell für numThread=5 geschrieben oder kann man diese auch für beliebige Threads benutzen?
Ich mach mich mit dieser Aufgabe so fertig und muss am nächsten Dienstag abgeben.
wieso das ‚aber‘? der zweite Satzteil ist nicht direkt schockierend, da wäre eine Erklärung schon nett,
es muss jedenfalls nicht genau aufgehen, numThread kein Teiler sein wie 5 einer von 15 ist, int-Rechnung in Java rundet ab, 15/7 = 2 ist hier gewünschtes Ergebnis,
der Rest muss eh noch verteilt werden, dafür ist spare da,
bei 7 Threads wird indicesPerThread 3, gar nicht so schlecht, in der Summe 7x zuviel, aber dafür ist ja noch spare da,
die weitere Ausgabe zeigt doch exakte Verteilung genau der 16 Elemente auf die 7 Threads?
)