Distributed Matrix Multiplication with MPI and OpenMP

A high-performance parallel implementation of matrix-matrix multiplication using hybrid MPI+OpenMP programming, demonstrating efficient distributed memory parallelization and communication optimization techniques.

Overview

This project implements distributed dense matrix multiplication (C = A × B) using an outer-product approach with MPI for inter-node communication and OpenMP for intra-node parallelization. The implementation partitions matrices across multiple processes and leverages collective communication operations for optimal performance on HPC clusters.

Features

• Hybrid Parallelization: Combines MPI (distributed memory) and OpenMP (shared memory) for multi-level parallelism
• Outer Product Algorithm: Each process computes partial results using column-panels of A and row-panels of B
• Optimized Communication: Uses MPI collective operations (Scatter, Reduce) to minimize communication overhead
• Scalability Testing: Supports strong scaling experiments across multiple nodes
• Performance Profiling: Built-in timing for communication vs. computation analysis
• Verification: Automated correctness checking against sequential reference implementation

Algorithm

The implementation uses a distributed outer-product approach:

1. Data Distribution:

   • Matrix A is partitioned column-wise: each process loads its column-panel (N × N/P elements)
   • Matrix B is loaded at rank 0 and scattered row-wise using MPI_Scatter

2. Local Computation:

   • Each process computes: local_C = A[:, k] × B[k, :] where k is its assigned panel
   • Uses optimized ikj loop ordering for cache efficiency
   • OpenMP parallelizes the outer loop across threads

3. Result Aggregation:

   • MPI_Reduce with MPI_SUM combines partial results at rank 0
   • Final matrix C = sum of all local_C matrices

Technical Highlights

Memory Layout Awareness

The implementation carefully handles C's row-major memory layout:

• Row-panels can be scattered directly (contiguous memory)
• Column-panels require each process to load its portion from file
• This design choice avoids the need for MPI derived datatypes

Communication Strategies

Compared two reduction strategies:

• MPI_Reduce: Sends result only to rank 0 (optimal for this use case)
• MPI_Allreduce: Distributes result to all ranks (12% communication overhead)

Performance Results

Strong Scaling (Matrix Size: 1024×1024)

Configuration	Processes	Nodes	Communication Time	Computation Time
Baseline	2	1	0.436s	0.267s
Medium	4	2	0.530s	0.150s
Large	8	4	0.620s	0.113s

Key Observations:

• Computation time scales well: ~2.4x speedup from 2 to 8 processes
• Communication overhead increases with process count (as expected)
• Achieved 58% parallel efficiency at 8 processes

Large-Scale Performance (Matrix Size: 2048×2048, 4 processes)

• MPI_Reduce: 1.796s communication, 0.870s computation
• MPI_Allreduce: 2.009s communication (+12%), 0.862s computation

Build and Run

Prerequisites

• MPI implementation (OpenMPI, MVAPICH, or Intel MPI)
• C compiler with OpenMP support
• Python (for data generation)

Compilation

# Build with specific matrix size
mpicc -O3 a4.c -D NN=1024 -fopenmp -D USE_THREAD -o matmul

# Or use the provided script
./run.sh a4.c 1024 4 10

Execution

# Run with specific configuration
# Syntax: ./run.sh <source> <matrix_size> <num_processes> <threads_per_process>

# Example: 1024×1024 matrix, 4 MPI processes, 10 OpenMP threads per process
./run.sh a4.c 1024 4 10

# For SLURM clusters with 2 nodes
srun --nodes=2 --ntasks=4 --ntasks-per-node=2 ./matmul

Implementation Details

Key Functions

• dist_mm(): Main distributed matrix multiplication driver
• local_matmul(): Local GEMM kernel with OpenMP parallelization
• load_tile(): Efficient panel loading from file
• MPI_Scatter(): Distributes row-panels of matrix B
• MPI_Reduce(): Aggregates partial results

Optimization Techniques

1. Loop Ordering: ikj ordering for better cache locality
2. Thread Parallelization: OpenMP parallel for on outer loop with private variables
3. Collective Communication: Avoids point-to-point overhead
4. Memory Alignment: Row-major layout optimization

Files

• a4.c - Main implementation with MPI_Reduce
• gen-data.py - Random matrix data generator
• run.sh - Build and execution script
• answer.txt - Performance analysis and experimental results
• mat_*.txt - Generated test matrices and intermediate results

Analysis

The project explores several key distributed computing concepts:

1. Memory Contiguity: Why column-panels cannot be scattered directly in row-major layout
2. Communication Overhead: Quantitative comparison of Reduce vs. Allreduce
3. Scaling Behavior: Strong scaling analysis across multiple nodes
4. Hybrid Parallelism: Optimal balance between MPI processes and OpenMP threads

Future Improvements

• Implement Cannon's algorithm or SUMMA for better scalability
• Add support for non-square matrices and non-power-of-2 process counts
• Integrate with BLAS/LAPACK for optimized local computation
• Implement weak scaling experiments
• Add GPU acceleration support

License

This project demonstrates practical HPC programming techniques for educational and portfolio purposes.

Author

Portfolio project demonstrating expertise in parallel computing, MPI programming, and performance optimization on HPC systems.