1. Goal
I am implementing matrix multiplication by Fox method for square mxn matrices AB = C and world_size = 4 processors disposed as a topological mesh/grid:
P0-P1
| |
P2-P3
where - represents mesh_r (mesh_rows) communicator and | represents mesh_c (mesh_columns) communicator, build through build_mesh procedure.
2. My code
int main(int argc, char *argv[])
{
int process_rank, world_size;
int mesh_rows, mesh_columns;
int mesh_dimension = 2;
int *process_coordinates;
MPI_Comm mesh, mesh_r, mesh_c;
int process_rank_mesh;
int *A, *A_loc;
int *B, *B_loc;
int *C, *C_loc;
int m, n, mloc, nloc;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &process_rank);
MPI_Comm_size(MPI_COMM_WORLD, &world_size);
if (process_rank == 0) {
m = n = /*world_size * 1*/ 2; // multiple of world_size = 4
}
MPI_Bcast(&m, 1, MPI_INT, 0, MPI_COMM_WORLD);
MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
A = fill_matrix(A, m, n);
B = fill_matrix(A, m, n);
C = (int*) calloc(m * n, sizeof(int));
if (process_rank == 0)
mesh_rows = 2;
if (is_divisible(world_size, mesh_rows))
mesh_columns = world_size / mesh_rows;
else {
mesh_rows = 1;
mesh_columns = world_size / mesh_rows;
}
MPI_Bcast(&mesh_rows, 1, MPI_INT, 0, MPI_COMM_WORLD);
MPI_Bcast(&mesh_columns, 1, MPI_INT, 0, MPI_COMM_WORLD);
process_coordinates = (int*) calloc(mesh_dimension, sizeof(int));
build_mesh(&mesh, &mesh_r, &mesh_c, process_rank, world_size, mesh_rows, mesh_columns, process_coordinates);
MPI_Comm_rank(mesh, &process_rank_mesh);
mloc = m / mesh_rows;
nloc = m / mesh_columns;
handle_errors(m, n, world_size, process_rank);
A_loc = (int*) calloc(mloc * nloc, sizeof(int));
distribute(A, A_loc, m, n, mloc, nloc, world_size, mesh_rows, mesh_columns);
B_loc = (int*) calloc(mloc * nloc, sizeof(int));
distribute(B, B_loc, m, n, mloc, nloc, world_size, mesh_rows, mesh_columns);
C_loc = (int*) calloc(mloc * nloc, sizeof(int));
distribute(C, C_loc, m, n, mloc, nloc, world_size, mesh_rows, mesh_columns);
int *A_loc_add = (int*) calloc(mloc * nloc, sizeof(int)); // blocco di A addizionale inviato dai processori sulla diagonale a quelli su mesh_r
// START BMR
memcpy(A_loc_add, A_loc, sizeof(A_loc) * mloc);
MPI_Bcast(A_loc_add, mloc * nloc, MPI_INT, f(process_rank), mesh_r);
// Compute Cij = AB for each process
for (int i = 0; i < m; i++) {
if (process_rank == 0 || process_rank == 3)
C_loc[i] += A_loc[i] * B_loc[i];
else
C_loc[i] += A_loc_add[i] * B_loc[i];
}
for (int i = 1; i < m; i++) {
// Broadcast
memcpy(A_loc_add, A_loc, sizeof(A_loc) * mloc);
MPI_Bcast(A_loc_add, mloc * nloc, MPI_INT, !f(process_rank), mesh_r);
// Rolling
int *t_loc = (int*) calloc(mloc * nloc, sizeof(int)); // variabile temporanea necessaria per lo scambio
memcpy(t_loc, B_loc, sizeof(B_loc) * mloc);
MPI_Status status;
int mate; // P0 <-> P2 e P1 <-> P3 - that is B_loc swap in mesh_c communicator
if (process_rank == 0) {
mate = 2;
MPI_Send(t_loc, mloc * nloc, MPI_INT, mate, 0, MPI_COMM_WORLD);
MPI_Recv(t_loc, mloc * nloc, MPI_INT, mate, 0, MPI_COMM_WORLD, &status);
} else if (process_rank == 1) {
mate = 3;
MPI_Send(t_loc, mloc * nloc, MPI_INT, mate, 0, MPI_COMM_WORLD);
MPI_Recv(t_loc, mloc * nloc, MPI_INT, mate, 0, MPI_COMM_WORLD, &status);
} else if (process_rank == 2) {
mate = 0;
MPI_Send(t_loc, mloc * nloc, MPI_INT, mate, 0, MPI_COMM_WORLD);
MPI_Recv(t_loc, mloc * nloc, MPI_INT, mate, 0, MPI_COMM_WORLD, &status);
} else if (process_rank == 3) {
mate = 1;
MPI_Send(t_loc, mloc * nloc, MPI_INT, mate, 0, MPI_COMM_WORLD);
MPI_Recv(t_loc, mloc * nloc, MPI_INT, mate, 0, MPI_COMM_WORLD, &status);
}
memcpy(B_loc, t_loc, sizeof(t_loc) * mloc);
free(t_loc);
// multiply
dot_product(A_loc_add, C_loc, B_loc, m);
}
// END BMR
MPI_Finalize();
return 0;
}
void dot_product(int *A_loc_add, int *C_loc, int *B_loc, int m)
{
for (int i = 0; i < m; i++)
C_loc[i] += A_loc_add[i] * B_loc[i];
}
int f(int process_rank)
{
if (process_rank == 0 || process_rank == 1)
return 0;
else
return 1;
}
void distribute(int *Mat, int *Mat_loc, int m, int n, int mloc, int nloc, int world_size, int mesh_rows, int mesh_columns)
{
MPI_Datatype square_block;
int stride = n;
int count = mloc;
int block_length = nloc;
MPI_Type_vector(count, block_length, stride, MPI_INT, &square_block);
MPI_Datatype square_block_resized;
MPI_Type_create_resized(square_block, 0, sizeof(int), &square_block_resized);
MPI_Type_commit(&square_block_resized);
int *send_counts = (int*) calloc(world_size, sizeof(int));
int *displs = (int*) calloc(world_size, sizeof(int));
for (int i = 0; i < mesh_rows; i++) {
for (int j = 0; j < mesh_columns; j++) {
send_counts[i * mesh_columns + j] = 1;
displs[i * mesh_columns + j] = i * n * block_length + j * block_length;
}
}
MPI_Scatterv(Mat, send_counts, displs, square_block_resized, Mat_loc, mloc * nloc, MPI_INT, 0, MPI_COMM_WORLD);
}
void handle_errors(int m, int n, int world_size, int process_rank)
{
if (process_rank == 0) {
if (m != n) {
perror("Not square matrices\n");
MPI_Abort(MPI_COMM_WORLD, EXIT_FAILURE);
}
if (world_size != 4) {
perror("World size must be 4\n");
MPI_Abort(MPI_COMM_WORLD, EXIT_FAILURE);
}
}
}
bool is_divisible(int dividend, int divisor)
{
return dividend % divisor == 0;
}
void build_mesh(MPI_Comm *mesh, MPI_Comm *mesh_r, MPI_Comm *mesh_c, int process_rank, int world_size,
int mesh_rows, int mesh_columns, int *process_coordinates)
{
int mesh_dimension = 2;
int *mesh_n_dimension;
int mesh_reorder = 0;
int *mesh_period;
int *remain_dims = (int*) calloc(mesh_dimension, sizeof(int));
mesh_n_dimension = (int*) calloc(mesh_dimension, sizeof(int));
mesh_n_dimension[0] = mesh_rows;
mesh_n_dimension[1] = mesh_columns;
mesh_period = (int*) calloc(mesh_dimension, sizeof(int));
mesh_period[0] = mesh_period[1] = 0;
MPI_Cart_create(MPI_COMM_WORLD, mesh_dimension, mesh_n_dimension, mesh_period, mesh_reorder, mesh);
MPI_Cart_coords(*mesh, process_rank, mesh_dimension, process_coordinates);
remain_dims[0] = 0;
remain_dims[1] = 1;
MPI_Cart_sub(*mesh, remain_dims, mesh_r);
remain_dims[0] = 1;
remain_dims[1] = 0;
MPI_Cart_sub(*mesh, remain_dims, mesh_c);
}
int *fill_matrix(int *Mat, int m, int n)
{
int k = 0;
Mat = (int*) calloc(m * n, sizeof(int));
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
Mat[i * n + j] = ++k;
return Mat;
}
3. Result
My algorithm is working fine if m = 2:
C00:
7
C01:
10
C10:
15
C11:
22
as you can see here
but makes mistakes when calculating C for other values of m (e.g. world_size * 1):
C00:
58 92
242 308
C01:
78 120
294 368
C10:
198 260
494 588
C11:
274 344
602 704
whose expected result C is:
- Can you help me? You can use this online matrices multiplication tool for debugging and calculate expected result. I am 100% sure that
build_meshanddistributeprocedures are correct: the bug must be in BMR section