5

MPI を使用して小さなプログラムをコーディングし、行列と行列の乗算を並列化します。問題は、私のコンピューターでプログラムを実行すると、完了するまでに約 10 秒かかりますが、クラスターでは約 75 秒かかることです。同期の問題があると思いますが、（まだ）わかりません。

ここに私のソースコードがあります:

/*matrix.c
mpicc -o out matrix.c
mpirun -np 11 out
*/

#include <mpi.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define N 1000

#define DATA_TAG 10
#define B_SENT_TAG 20
#define FINISH_TAG 30

int master(int);
int worker(int, int);

int main(int argc, char **argv) {
    int myrank, p;
    double s_time, f_time;

    MPI_Init(&argc,&argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
    MPI_Comm_size(MPI_COMM_WORLD, &p);

    if (myrank == 0) {
        s_time = MPI_Wtime();
        master(p);
        f_time = MPI_Wtime();
        printf("Complete in %1.2f seconds\n", f_time - s_time);
        fflush(stdout);
    }
    else {
        worker(myrank, p);
    }
    MPI_Finalize();
    return 0;
}

int *read_matrix_row();
int *read_matrix_col();
int send_row(int *, int);
int recv_row(int *, int, MPI_Status *);
int send_tag(int, int);
int write_matrix(int *);

int master(int p) {
    MPI_Status status;
    int *a; int *b;
    int *c = (int *)malloc(N * sizeof(int));
    int i, j; int num_of_finish_row = 0;

    while (1) {
        for (i = 1; i < p; i++) {
            a = read_matrix_row();
            b = read_matrix_col();
            send_row(a, i);
            send_row(b, i);
            //printf("Master - Send data to worker %d\n", i);fflush(stdout);
        }
        wait();
        for (i = 1; i < N / (p - 1); i++) {
            for (j = 1; j < p; j++) {
                //printf("Master - Send next row to worker[%d]\n", j);fflush(stdout);
                b = read_matrix_col();
                send_row(b, j);
            }
        }
        for (i = 1; i < p; i++) {
            //printf("Master - Announce all row of B sent to worker[%d]\n", i);fflush(stdout);
            send_tag(i, B_SENT_TAG);
        }
        //MPI_Barrier(MPI_COMM_WORLD);
        for (i = 1; i < p; i++) {
            recv_row(c, MPI_ANY_SOURCE, &status);
            //printf("Master - Receive result\n");fflush(stdout);
            num_of_finish_row++;
        }
        //printf("Master - Finish %d rows\n", num_of_finish_row);fflush(stdout);
        if (num_of_finish_row >= N)
            break;
    }
    //printf("Master - Finish multiply two matrix\n");fflush(stdout);
    for (i = 1; i < p; i++) {
        send_tag(i, FINISH_TAG);
    }
    //write_matrix(c);
    return 0;
}

int worker(int myrank, int p) {
    int *a = (int *)malloc(N * sizeof(int));
    int *b = (int *)malloc(N * sizeof(int));
    int *c = (int *)malloc(N * sizeof(int));
    int i;
    for (i = 0; i < N; i++) {
        c[i] = 0;
    }
    MPI_Status status;
    int next = (myrank == (p - 1)) ? 1 : myrank + 1;
    int prev = (myrank == 1) ? p - 1 : myrank - 1;
    while (1) {
        recv_row(a, 0, &status);
        if (status.MPI_TAG == FINISH_TAG)
            break;
        recv_row(b, 0, &status);
        wait();
        //printf("Worker[%d] - Receive data from master\n", myrank);fflush(stdout);
        while (1) {
            for (i = 1; i < p; i++) {
                //printf("Worker[%d] - Start calculation\n", myrank);fflush(stdout);
                calc(c, a, b);
                //printf("Worker[%d] - Exchange data with %d, %d\n", myrank, next, prev);fflush(stdout);
                exchange(b, next, prev);
            }
            //printf("Worker %d- Request for more B's row\n", myrank);fflush(stdout);
            recv_row(b, 0, &status);
            //printf("Worker %d - Receive tag %d\n", myrank, status.MPI_TAG);fflush(stdout);
            if (status.MPI_TAG == B_SENT_TAG) {
                break;
                //printf("Worker[%d] - Finish calc one row\n", myrank);fflush(stdout);
            }
        }
        //wait();
        //printf("Worker %d - Send result\n", myrank);fflush(stdout);
        send_row(c, 0);
        for (i = 0; i < N; i++) {
            c[i] = 0;
        }
    }
    return 0;
}

int *read_matrix_row() {
    int *row = (int *)malloc(N * sizeof(int));
    int i;
    for (i = 0; i < N; i++) {
        row[i] = 1;
    }
    return row;
}
int *read_matrix_col() {
    int *col = (int *)malloc(N * sizeof(int));
    int i;
    for (i = 0; i < N; i++) {
        col[i] = 1;
    }
    return col;
}

int send_row(int *row, int dest) {
    MPI_Send(row, N, MPI_INT, dest, DATA_TAG, MPI_COMM_WORLD);
    return 0;
}

int recv_row(int *row, int src, MPI_Status *status) {
    MPI_Recv(row, N, MPI_INT, src, MPI_ANY_TAG, MPI_COMM_WORLD, status);
    return 0;
}

int wait() {
    MPI_Barrier(MPI_COMM_WORLD);
    return 0;
}
int calc(int *c_row, int *a_row, int *b_row) {
    int i;
    for (i = 0; i < N; i++) {
        c_row[i] = c_row[i] + a_row[i] * b_row[i];
        //printf("%d ", c_row[i]);
    }
    //printf("\n");fflush(stdout);
    return 0;
}

int exchange(int *row, int next, int prev) {
    MPI_Request request; MPI_Status status;
    MPI_Isend(row, N, MPI_INT, next, DATA_TAG, MPI_COMM_WORLD, &request);
    MPI_Irecv(row, N, MPI_INT, prev, MPI_ANY_TAG, MPI_COMM_WORLD, &request);
    MPI_Wait(&request, &status);
    return 0;
}

int send_tag(int worker, int tag) {
    MPI_Send(0, 0, MPI_INT, worker, tag, MPI_COMM_WORLD);
    return 0;
}

int write_matrix(int *matrix) {
    int i;
    for (i = 0; i < N; i++) {
        printf("%d ", matrix[i]);
    }
    printf("\n");
    fflush(stdout);
    return 0;
}
4

3 に答える 3

4

さて、かなり小さな行列 (N=1000) があり、次にブロックではなく行/列ベースでアルゴリズムを配布します。

より優れたアルゴリズムを使用したより現実的なバージョンについては、最適化された BLAS ライブラリ (たとえば、GOTO は無料) を取得し、そのライブラリでシングル スレッドのパフォーマンスをテストしてから、PBLAS を入手して最適化された BLAS とリンクし、MPI 並列パフォーマンスを比較することをお勧めします。 PBLAS バージョンを使用します。

于 2011-04-18T12:36:00.923 に答える
2

プログラムにエラーがあります。

  1. まず、その実装は単に。を呼び出しているのに、なぜwait関数を呼び出しているのですかMPI_Barrier。MPI_Barrierは、を呼び出して「バリア」に到達するまですべてのスレッドをブロックする基本的な同期ですMPI_Barrier。私の質問は、マスターをワーカーと同期させたいですか？このコンテキストでは、ワーカーはマスターが計算を開始するのを待つ必要がないため、これは最適ではありません。

  2. 次に、不要なforループが2つあります。

    for (i = 1; i < N / (p - 1); i++) {
    for (j = 1; j < p; j++) {
        b = read_matrix_col();
        send_row(b, j);
    }
}

for (i = 1; i < p; i++) {
    send_tag(i, B_SENT_TAG);
}

最初のiループでは、ステートメントで変数を使用しません。jループと2番目のiループは同じなので、次のことができます。

for (i = 0; i < p; i++) {
    b = read_matrix_col();
    send_row(b, j);
    send_tag(i, B_SENT_TAG);
 }

データ転送に関しては、データ転送ごとに1000整数のデータの配列を送信しているため、プログラムは最適化されていません。データ転送を最適化するためのより良い方法があるはずですが、それを見てみましょう。だから私があなたに言った修正をして、あなたの新しいパフォーマンスは何であるかを教えてください。

@jannebが言ったように、行列乗算のパフォーマンスを向上させるためにBLASライブラリを使用できます。幸運を！

于 2011-04-18T13:35:50.627 に答える
1

私はあなたのコードを調べませんでしたが、結果が予期しないものではない理由についていくつかのヒントを提供できます。

  1. すでに述べたように、N=1000 は小さすぎる可能性があります。プログラムのスケーラビリティを確認するためにさらにテストを行い (N=100、500、1000、5000、10000 などに設定してみてください)、システムとクラスターの両方で結果を比較する必要があります。

  2. システム (私が推測する 1 つのプロセッサ) とクラスタ上の単一のプロセッサの間で結果を比較します。通常、サーバーやクラスターなどの実稼働環境では、単一のプロセッサーはデスクトップ用に設計された最高のプロセッサーよりも強力ではありませんが、安定性、信頼性、および 1 日 24 時間フル稼働する環境に役立つその他の機能を提供します。

  3. プロセッサーに複数のコアがある場合、複数の MPI プロセスが同時に実行される可能性があり、クラスター内のノード間の同期と比較して、それらの間の同期は無視できます。

  4. クラスタのノードは静的に割り当てられていますか? 同時に実行しているノードで、他のユーザーのプログラムをスケジュールすることができます。

  5. クラスターのアーキテクチャに関するドキュメントをお読みください。一部のアーキテクチャは、特定のクラスの問題により適している場合があります。

  6. クラスターのネットワークのレイテンシーを評価します。各ノードから別のノードに何度もpingを送信し、平均値を計算すると、大まかな見積もりが得られる場合があります。

  7. 最後になりますが、おそらく最も重要なのは、アルゴリズムが最適でない可能性があることです。行列の乗算に関する本を読んでください (「Matrix Computations」、Golub、Van Loan をお勧めします)。

于 2011-04-18T21:11:33.437 に答える