Linux Cluster

Programmierung

Übersicht

• Multiplikation von Matrizen
• Das Konzept
• Der Master
• Im Cluster mit 2 Hosts

Multiplikation von Matrizen

Als Beispiel für die Programmierung eines Clusters mit PVM ist die Multiplikation von Matrizen sehr anschaulich. Zu erst kurz die Definition, wie Matrizen multipliziert werden.

Definition: Es sei A eine (m x k)-Matrix und B eine (k x n)-Matrix. Als Produkt A•B der beiden Matrizen ergibt sich die (m x n)-Matrix C:

Beispiel:

Für die Programmierung müssen drei Fragen beantwortet werden:

• Was kann parallel verarbeitet werden?
  => Zeilenberechnung
• Welche Daten sind für die einzelnen Verarbeitungen nötig?
  => Zeile der A-Matrix und ganze B-Matrix
• Was kommt als Ergebnis zurück?
  => Zeile der Ergebnismatrix

Das Konzept

Aus den eben gestellten Fragen lässt sich ein Konzept für das "Master / Slave" Modell entwickeln:

Der Master

1. Ermittle die Anzahl der rechnenden Hosts
2. Schicke die B-Matrix an alle Hosts
3. Verteile die Zeilen der A-Matrix an die entsprechenden Hosts
4. Warte auf Ergebniszeilen und füge diese in die Ergebnismatrix ein

Der Slave

1. Empfange die B-Matrix
2. Empfange die Zeilen der A-Matrix
3. Berechne die Ergebniszeilen
4. Sende die Ergebniszeilen zurück

Der Master

#include <stdio.h>
#include "pvm3.h"

#define MAXHOSTS 10
#define DIMENSION 100

int main(int argc, char **argv)
{
    /* TID, number of hosts, number  */
    /* of different data types in VM */
    int mytid, nproc, narch;
    int info;

    /* array of all TIDs       */
    /* number of working hosts */
    int tids[MAXHOSTS], nworkers;

    int num, i, j;
    int numrows, extra, rownum=0, extra_num;
    float A[DIMENSION][DIMENSION], B[DIMENSION][DIMENSION];
    /* result matrix*/
    float C[DIMENSION][DIMENSION];
    FILE *outfile;
    /* array for information */
    /* about the hosts in VM */
    struct pvmhostinfo *hosts[MAXHOSTS];


    num = 0;
    /* enroll in PVM */
    mytid = pvm_mytid();

    /* get the conf of the VM                              */
    /* proto:                                              */
    /* int info = pvm_config( int *nhost,                  */
    /*                        int *narch,                  */
    /*                        struct pvmhostinfo **hostp ) */
    info = pvm_config(&nproc, &narch, hosts);

    /* set the number of workers   */
    /* if more than one host, the  */
    /* master will not work        */
    nworkers = nproc > 1 ? nproc -1 : 1;

    /* spawn the slaves                                     */
    /* proto:                                               */
    /* int numt = pvm_spawn( char *task,                    */
    /*                       char **argv,                   */
    /*                       int flag,                      */
    /*                       char *where,                   */
    /*                       int ntask,                     */
    /*                       int *tids )                    */
    pvm_spawn("matrixslv", (char**)0, PvmTaskDefault, "", nworkers, tids);

    /* fill the matrixes */
    num = 0;
    for (i=0; i < DIMENSION; i++)
        for (j=0; j < DIMENSION; j++) {
            A[i][j] = num++;
            B[i][j] = num++;
        }

    /******************************************/
    /* Sending the Data                       */
    /******************************************/

    numrows = DIMENSION / (nworkers);
    extra = DIMENSION % (nworkers);
    extra_num = numrows+1;

    /* clear default send buffer        */
    /* and specify decoding to default  */
    pvm_initsend(PvmDataDefault);
    for (i=0; i < DIMENSION; i++)
        /* pack one row of the B matrix */
        pvm_pkfloat(B[i], DIMENSION, 1);
    /* send the buffer to all workers */
    /* tids = array of workers' TIDs  */
    pvm_mcast(tids, nworkers, 1); /* msgTag 1 */

    for (i=0; i < nworkers; i++) {
        pvm_initsend(PvmDataDefault);
        if (extra-- > 0) { /* some extra rows are present */

            /* pack number of rows to deliver */
            /* this worker gets one row more */
            pvm_pkint(&extra_num, 1, 1);
            /* pack the number of the current row */
            pvm_pkint(&rownum, 1, 1);
            /* pack the current row in buffer */
            pvm_pkfloat(A[rownum++], DIMENSION, 1);
        }
        else { /* there are no extra rows            */
               /* means: DIMENSION mod nworkers == 0 */

            /* pack number of rows to deliver */
            pvm_pkint(&numrows, 1, 1);
            /* pack number of current row */
            pvm_pkint(&rownum, 1, 1);
        }
        /* pack the rows in buffer    */
        /* and send to current worker */
        for (j=0; j < numrows; j++)
            pvm_pkfloat(A[rownum++], DIMENSION, 1);
        pvm_send(tids[i], 2); /* msgTag 2 */
    }

    /******************************************/
    /* Receiving the Results                  */
    /******************************************/

    for (i=0; i < nworkers; i++) {
        /* wait and receive any msg with Tag 3 */
        pvm_recv(-1, 3);
        /* unpack number of current row */
        pvm_upkint(&rownum, 1, 1);
        /* unpack number of rows received */
        pvm_upkint(&numrows, 1, 1);
        /* put the received rows in result-matrix */
        for (j=0; j < numrows; j++)
            pvm_upkfloat((C[rownum++]), DIMENSION, 1);
    }

    /******************************************/
    /* Write the results to file              */
    /******************************************/


    outfile = fopen("mmult.out", "w");
    for (i = 0; i < DIMENSION; i++)
        for (j=0; j < DIMENSION; j++)
            fprintf(outfile, "C[%d][%d]:  %f\n", i, j, C[i][j]);
    fclose(outfile);

    pvm_exit();

}

Im Cluster mit 2 Hosts

In einem Cluster mit 2 Hosts, die beide rechnen, sieht eine grafische Darstellung des Ablaufs folgendermaßen aus:

grün = rechnend, gelb = Overhead, weiß = wartend, rot = Nachrichten

Schwarze Abschnitte entsprechen einer sehr schmalen Aneinanderreihung von gelben und grünen Abschnitten.