Проблема с умножением матрицы на матрицу MPI: кластер медленнее, чем один компьютер

Question

Я кодирую небольшую программу, используя 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;
}

Answer 1

Ну, у вас довольно маленькая матрица (N = 1000), и, во-вторых, вы распределяете свой алгоритм по строкам / столбцам, а не блокируете.

Для более реалистичной версии, использующей лучшие алгоритмы, вы можете приобрести оптимизированную библиотеку BLAS (например, GOTO бесплатна), протестировать однопотоковую производительность с этой, затем получить PBLAS и связать ее с оптимизированной BLAS и сравнить Параллельная работа MPI с использованием версии PBLAS.

Answer 2

Я вижу некоторые ошибки в вашей программе:

1. Во-первых, почему вы вызываете функцию ожидания, поскольку ее реализация просто вызывает MPI_Barrier.MPI_Barrier - это примитивная синхронизация, которая блокирует все потоки, пока они не достигнут "барьера", вызывая MPI_Barrier.Мой вопрос: хотите ли вы, чтобы мастер был синхронизирован с рабочими?В этом контексте это было бы неоптимально, поскольку работнику не нужно ждать, пока мастер начнет свои вычисления.

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-цикл и второй i-цикл совпадают, вы можете сделать:

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

С точки зрения передачи данных ваша программа не оптимизирована, поскольку вы отправляете массив из 1000 целых чисел данных.за каждую передачу данных.Должен быть лучший способ оптимизировать передачу данных, но я позволю вам взглянуть на это.Поэтому внесите исправления, которые я вам сказал, и расскажите нам, какова ваша новая производительность.

И, как сказал @janneb, вы можете использовать библиотеку BLAS для повышения производительности при умножении матриц.Удачи!

Answer 3

Я не просматривал ваш код, но могу дать несколько советов о том, почему ваш результат не может быть неожиданным:

1. Как уже упоминалось, N = 1000 может быть слишком маленьким.Вы должны сделать больше тестов, чтобы увидеть масштабируемость вашей программы (попробуйте установить N = 100, 500, 1000, 5000, 10000 и т. Д.) И сравнить результаты как в вашей системе, так и в кластере.

2. Сравните результаты между вашей системой (один процессор, я полагаю) и одним процессором в кластере.Обычно в производственных средах, таких как серверы или кластеры, один процессор является менее мощным, чем лучшие процессоры, предназначенные для настольных ПК, но они обеспечивают стабильность, надежность и другие функции, полезные для сред, которые работают 24 часа в сутки на полную мощность.

3. Если ваш процессор имеет несколько ядер, несколько процессов MPI могут выполняться одновременно, и синхронизация между ними незначительна по сравнению с синхронизацией между узлами в кластере.

4. Назначены ли вам узлы кластера статически?Возможно, программы других пользователей могут быть запланированы на узлах, на которых вы работаете, одновременно с вами.

5. Прочтите документацию об архитектуре кластера.Некоторые архитектуры могут быть более подходящими для определенных классов задач.

6. Оценка задержки сети кластера.Пинг от каждого узла к другому много раз и вычисление среднего значения может дать приблизительную оценку.

7. Последний, но, возможно, самый важный, ваш алгоритм может быть не оптимальным.Прочитайте / некоторые книги по умножению матриц (я могу порекомендовать «Матричные вычисления», Голуб и Ван Лоан).