8.4 Matrix-Multiplikation

Für die parallele Multiplikation von Matrizen, die in Jomp mit einer Zeile zu erledigen ist, brauchen wir hier einen eigenen Abschnitt. Zur Verteilung der Matrizen auf die beteiligten Prozesse ist einige Arbeit notwendig.

Aufgabe 47   Entwickeln Sie ein MPI-Programm zur parallelen Multiplikation von Matrizen. C = A x B. Benutzen Sie mpiJava mit Send, Bcast und Recv zur Parallelisierung.

Im folgenden Lösungsvorschlag zeigen wir nur die Methode parmult. Von dem Hauptprogramm geben wir nur eine Skizze an. Wir benötigen keine neuen MPI-Funktionen, wir müssen nur die komplizierteren Kommunikationsaufgaben lösen.

Wir verteilen die Matrix B auf alle Prozesse. Von der Matrix A verteilen wir nur Gruppen von Zeilen. Diese Zeilen reichen aus, um eine entsprechende Zeile der Matrix C zu berechnen (siehe Abbildung 8.4). Die gewünschten Zeilengruppen verwalten wir mit dem Array assign. Wobei assign[i]=k gilt, wenn Prozess k die Zeile i bearbeiten soll.

Abbildung 8.4: Matrix-Verteilung
\includegraphics[width=10.45cm]{figures/MMmpi}

In der Sendeschleife des Masters wird damit die Zeile A[k] an den Prozess assign[k] gesendet. Umgekehrt wird die fertige Zeile C[k] von den Prozessen an den Master-Prozess zurückgeschickt. Die Multiplikation findet nur statt, wenn myid == assign[i] ist, d.h., wenn die Zeile empfangen wurde und der Prozess zuständig ist.

  public void parmult(double[][] C, 
                      double[][] A, 
                      double[][] B) 
         throws MPIException {

      // initialize MPI Communicators
      int myid     = MPI.COMM_WORLD.Rank();
      int numprocs = MPI.COMM_WORLD.Size();

      int counts = A.length;
      int[] assign = new int[counts];
      for (int k=0; k < counts; k++) {
          assign[k] = k % numprocs;
      }

      int msgtag = 4711;
      if ( myid == 0 ) {
         for (int k=0; k < counts; k++ ) {
             if ( myid != assign[k] ) {
                MPI.COMM_WORLD.Send(A[k],0,A[k].length, 
                    MPI.DOUBLE, assign[k], msgtag);
             }
         }
      } else {
         for (int y = 0; y < counts; y++ ) {
             if ( myid == assign[y] ) {
                MPI.COMM_WORLD.Recv(A[y],0,A[y].length, 
                    MPI.DOUBLE, 0, msgtag);
             }
         }
      }
      for (int x=0; x < B.length; x++ ){
         MPI.COMM_WORLD.Bcast(B[x], 0, B[x].length, 
             MPI.DOUBLE, 0);
      }
      for (int i=0; i < counts; i++) {
          if ( myid == assign[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;
             }
          }
      }
      if ( myid == 0 ) {
         for (int k=0; k < counts; k++ ) {
             if ( myid != assign[k] ) {
                MPI.COMM_WORLD.Recv(C[k],0,C[k].length, 
                    MPI.DOUBLE, assign[k], msgtag);
             }
         }
      } else {
          for (int y = 0; y < counts; y++ ) {
             if ( myid == assign[y] ) {
                MPI.COMM_WORLD.Send(C[y],0,C[y].length, 
                    MPI.DOUBLE, 0, msgtag);
             }
          }
      }
  }

Die Skizze des Hauptprogramms ist wie folgt. Auf dem Master-Prozess müssen die Matrizen A, B, C initialisiert werden, auf den Hilfsprozessen genügt es, die Matrizen zu deklarieren. Wir halten die Matrizen A und C mit partiellen Daten auf allen Prozessen, obwohl dies Speicherplatz verschwendet. Beachten Sie, dass die Methode parmult auf allen beteiligten Prozessen ausgeführt werden muss, da sie intern noch Fallunterscheidungen enthält.

        MPI.Init(args) ;
        int myid = MPI.COMM_WORLD.Rank() ;

        if ( myid == 0 ) {
           // init A, B, C
        } else {
           // declare A, B, C
        }

        parmult(C,A,B);

        if ( myid == 0 ) {
           // print C
        } 

        MPI.Finalize();

Die Ausgabe zeigen wir hier nicht, da die Matrizen zu groß und unübersichtlich sind.

Zusammenfassung

In diesem Kapitel haben wir eine Einführung in MPI mit Hilfe des mpiJava-Pakets besprochen. Wir haben die wichtigsten Kommunikationsfunktionen von MPI, wie Send, Recv, Bcast, Scatter und Reduce, kennen gelernt. Das Konzept der Kommunikatoren von MPI, auf das wir nur grob eingehen konnten, bietet sichere Kommunikation innerhalb von Prozessgruppen und eine interessante Möglichkeit, virtuelle Kanäle zu realisieren. Wie wir am Beispiel der Multiplikation von Matrizen gesehen haben, kann es sehr aufwendig sein, die Daten auf Prozesse zu verteilen und wieder einzusammeln bzw. sich einen Algorithmus zu überlegen, der mit verteilten Daten arbeitet.

Für den vollen MPI-Sprachumfang verweisen wir Sie auf die Online-Dokumentation und z.B. auf das einführende Buch [GLS95].


Heinz Kredel
2002-04-05