Matrix Multiplikation

Formulierung mit con

Das Problem der Multiplikation von Matrizen lässt sich mit con leicht parallelisieren. Matrizen sind rechteckige, insbesondere quadratische Zahlenanordnungen, die in vielen naturwissenschaftlichen und ökonomischen Berechnungen eine wichtige Rolle spielen.

Es seien A, B, C jeweils n x n-Matrizen, (z.B. über den rationalen Zahlen, n eine natürliche Zahl). Gesucht ist das Produkt C = A * B. Die Matrix C = { cij } berechnet sich für jedes i und j nach der Vorschrift

\begin{displaymath}
c_{ij} = \sum_{k=1}^{n} a_{ik} b_{kj} \ \ i, j = 1, \ldots, n
\end{displaymath}

Stellt man die Matrixelemente xij durch die Array-Elemente x[i,j] dar, so kann die Summe in einer Schleife `for k=1 to n do' berechnet werden. Damit ergibt sich der parallele Algorithmus in Abbildung 2.1. Hier sind i und j in jedem parallelen Teil verschieden.

Abbildung 2.1: Multiplikation von Matrizen
\framebox{
\begin{minipage}{10cm}
\begin{tabbing}
{\bf con }\= \+ $i=1$\ {\bf to...
...\
$c[i,j] = s$; \\
{\bf end}; \- \\
{\bf end}
\end{tabbing}\end{minipage}}

Implementierung mit Threads

Implementieren Sie das Programm zur Multiplikation von Matrizen aus Abschnitt 2.1.1. Parallelisieren Sie nur die äußere for-Schleife, d.h., implementieren Sie das folgende Programm mit Java-Threads.

\framebox{
\begin{minipage}{10cm}
\begin{tabbing}
{\bf con }\= \+ $i=1$\ {\bf to...
...\
$c[i,j] = s$; \\
{\bf end}; \- \\
{\bf end}
\end{tabbing}\end{minipage}}

Wir skizzieren die wichtigsten Teile der Lösung, eine vollständige Lösung finden Sie im Jar-File auf der Website.

Die Methode seqmult implementiert zum Vergleich eine sequenzielle Version des Programms. Die Matrizen C, A, und B werden durch double[][] Felder implementiert. A und B werden multipliziert und das Ergebnis wird in C abgelegt.

  public void seqmult(double[][] C, 
                      double[][] A, 
                      double[][] B) {
      for (int i=0; i < A.length; i++) {
          for (int j=0; j < B[0].length; j++) {
              double c = 0.0;
              for (int k=0; k < B.length; k++) {
                  c += A[i][k] * B[k][j];
              }
              C[i][j] = c;
          }
      }
  }

Die Methode parmult implementiert die parallele Version des Programms.

  public void parmult(double[][] C, 
                      double[][] A, 
                      double[][] B) {
      Thread[] t = new Thread[A.length];
      for (int i=0; i < A.length; i++) {
          t[i] = new RowMult(C,A,B,i);
          t[i].start();
      }
      for (int i=0; i < A.length; i++) {
          try { t[i].join(); }
          catch (InterruptedException e) { }
      }
  }

Die äußere for-Schleife wird hierbei durch zwei Schleifen ersetzt, von der die erste die entsprechenden Threads startet und die zweite Schleife auf deren Beendigung wartet. In den Threads wird die run-Methode der Klasse RowMult ausgeführt, die für jeden Wert von i die inneren Schleifen abarbeitet. Der Konstruktor übernimmt die Matrizen und den Indexwert i. RowMult erweitert die Klasse Thread, dadurch genügt oben ein new RowMult(.), um den Thread zu erzeugen. start() und join() werden dann von Thread bereitgestellt.

class RowMult extends Thread {

  double[][] A;
  double[][] B;
  double[][] C;
  int i;  

  RowMult(double[][] Cp, 
          double[][] Ap, 
          double[][] Bp, int ip) {
    A = Ap; B = Bp; C = Cp; i = ip;
  }
  public void run() {
    for (int j=0; j < B[0].length; j++) {
      double c = 0.0;
      for (int k=0; k < B.length; k++) {
          c += A[i][k] * B[k][j];
      }
      C[i][j] = c;
    }
  }
}

© Universität Mannheim, Rechenzentrum, 2004-2007.

Heinz Kredel

Last modified: Tue Aug 19 17:33:59 CEST 2008