MPI Algorithms in Zig

This project implements parallel algorithms using MPI (Message Passing Interface) in Zig. Currently, it includes a parallel merge sort implementation.

Prerequisites

• Zig (0.11.0 or later)
• OpenMPI or MPICH
• C compiler (gcc/clang)

Installing Prerequisites

For Ubuntu/Debian:

sudo apt update
sudo apt install zig openmpi-bin libopenmpi-dev build-essential

For macOS:

brew install zig open-mpi

Project Structure

mpi-algorithms/
├── build.zig          # Build configuration
├── src/
│   ├── main.zig      # Main entry point
│   ├── sort.zig      # Sorting implementations
│   ├── utils.zig     # Utility functions
│   └── types.zig     # Type definitions
└── README.md         # This file

Building the Project

1. Clone the repository:

git clone https://github.com/sinhaparth5/mpi-algorithms
cd mpi-algorithms

1. Build the project:

zig build

Running the Program

To run the parallel merge sort with 4 processes:

mpirun -np 4 zig-out/bin/mpi-algorithms

You can adjust the number of processes by changing the -np parameter.

Running Tests

To run the test suite:

zig build test

Implementation Details

The parallel merge sort implementation:

1. Divides the input array into chunks
2. Distributes chunks to different MPI processes
3. Each process sorts its chunk using sequential merge sort
4. The root process (rank 0) collects and merges the sorted chunks
5. Verifies the final sorted array

Performance Considerations

• The optimal number of processes depends on:
  • Input size
  • Available CPU cores
  • Memory bandwidth
  • Network speed (for distributed systems)
• For small arrays, overhead from MPI communication might outweigh benefits
• Best performance typically achieved when:
  • Input size is large
  • Data is evenly distributed
  • Number of processes matches available CPU cores

Contributing

1. Fork the repository
2. Create your feature branch
3. Commit your changes
4. Push to the branch
5. Create a Pull Request

License

This project is licensed under the MIT License - see the LICENSE file for details.