Matrix Multiplication
Having any trouble? Check out the FAQ page.1. Introduction
View the exercise on GitHub.This program computes the product of two square matrices, C = A × B.
A and B are filled with constant values, so every element of the result is known in advance and the output can be checked quickly.
The goal of this assignment is to parallelize the provided sequential reference code using MPI, so that the multiplication runs correctly on multiple processes.
2. Algorithm
All three matrices have size order × order and are stored as flat, row-major arrays of double.
A. Initialization
- Every rank allocates
B. - Only rank 0 allocates
AandC, and only rank 0 initializes the matrices: every element ofAis set to3.0, every element ofBto5.0, andCto0.0. - On all other ranks,
AandCare not allocated andBcontains uninitialized values.
B. Multiplication
The classic triple loop: for each row i of A and each column j of B, C[i][j] accumulates the dot product of row i and column j:
for (i = 0; i < Ndim; i++)
for (j = 0; j < Mdim; j++)
for (k = 0; k < Pdim; k++)
C[i][j] += A[i][k] * B[k][j];
C. Verification
- Each rank measures its own running time, and the maximum is reduced to rank 0.
- Rank 0 compares every element of
Cwith the expected valueorder × 3.0 × 5.0. If the squared error is within tolerance, it printsHey, it worked!.
3. Project Structure
You are provided with the following key files:
matmul.c: The reference sequential code. Use this to understand the logic.matmul_mpi.c: The template for your MPI implementation.Makefile: Build script for compiling the project.test_matmul.sh: Test script that runs the MPI version on several matrix sizes and checks the result.
4. Input and Output Formats
Input
There are no input files: the only input is the matrix order, passed on the command line.
Output
- Standard Output: The execution time of the multiplication, the achieved MFLOPs, and the outcome of the check (
Hey, it worked!orErrors in multiplication: <error>).
5. Usage
Compilation
Use the provided Makefile:
make matmul # sequential reference
make matmul_mpi # your MPI implementation
make all # both
Execution
The program requires the following command-line argument:
mpirun -np <processes> ./matmul_mpi.out <matrix_order>
processes: Number of MPI processes.matrix_order: Size of the (square) matrices.
Testing
Run the full test suite with:
make test
This runs matmul_mpi.out with 4 processes on matrices of order 1000, 1500 and 2000, and checks that each run prints Hey, it worked!.
6. Implementation Requirements
Files to Modify
You are strictly limited to modifying only the following file:
matmul_mpi.c
Constraints
- Parallel Model: You must use MPI.
- Target Section: Only modify the code between the
AREA OF INTERESTandEND AREA OF INTERESTcomments. MPI is already initialized for you. - Immutable Sections: Do not modify argument processing, memory allocation, initialization, time measurement, or the result check.
- Result: At the end of the area of interest, the complete result must be stored in
Con rank 0, where it is verified.
7. Credits
Code adapted from the matrix multiply example by Tim Mattson (Nov 1999).