Parallel Graph Algorithms for MOSP Using MPI, OpenMP, and METIS

Overview

This project implements parallel algorithms for solving the Multi-Objective Shortest Path (MOSP) problem using distributed and shared-memory parallelism. The implementation leverages:

• MPI for inter-node communication.
• OpenMP for intra-node parallelism.
• METIS for graph partitioning.

The goal is to efficiently compute Pareto-optimal solutions for large-scale graphs while analyzing scalability and performance across different system configurations.

This project was developed as part of a course on Parallel and Distributed Computing at FAST NUCES. It demonstrates the effective use of modern parallel computing techniques to solve challenging graph problems.

---

Table of Contents

1. Objectives
2. Features
3. Dependencies
4. Directory Structure
5. Usage
6. Scalability Analysis
7. Datasets
8. Contributing
9. License
10. Acknowledgments

---

Objectives

The primary objectives of this project are:

1. Correctness: Implement a parallel algorithm for solving the MOSP problem that produces accurate results.
2. Efficiency: Optimize the algorithm for performance using MPI and OpenMP.
3. Scalability: Evaluate how the algorithm scales with increasing graph sizes and system configurations.
4. Graph Partitioning: Use METIS to partition the graph and facilitate efficient parallel processing.
5. Documentation: Maintain clear documentation and version control to track progress and ensure reproducibility.

---

Features

• Multi-Objective Optimization: Supports multiple objectives (e.g., distance, cost, time) for shortest path computation.
• Parallelism:
  • MPI: Distributes graph partitions across multiple nodes.
  • OpenMP: Exploits shared-memory parallelism within each node.
• Graph Partitioning: Uses METIS to divide the graph into balanced subgraphs.
• Dynamic Updates: Handles dynamic changes to the graph (e.g., edge insertions or deletions).
• Performance Metrics: Measures execution time, FLOPs, and MFLOPS to evaluate performance.

---

Dependencies

To compile and run the project, you need the following dependencies:

1. C++ Compiler: GCC or Clang with C++17 support.
2. MPI: OpenMPI or MPICH.
3. OpenMP: Included with most modern C++ compilers.
4. METIS: For graph partitioning (install from METIS GitHub).
5. Python (Optional): For preprocessing or validation scripts.

---

Directory Structure

project-root/
├── src/                  # Source code files
│   ├── parallel_update.cpp  # Main implementation of the parallel MOSP algorithm
│   └── utils.cpp         # Utility functions for parsing and debugging
├── datasets/             # Input graph and partition files
│   ├── dummy_100_nodes.txt  # Example graph file in METIS format
│   └── dummy_100_nodes.txt.part.4  # Partition file generated by METIS
├── results/              # Output files (Pareto fronts, logs, etc.)
├── scripts/              # Scripts for preprocessing or analysis
├── LICENSE               # License file
└── README.md             # This file

---

Usage

Step 1: Install Dependencies

Ensure you have the required dependencies installed. For example:

sudo apt-get install gcc g++ openmpi-bin libopenmpi-dev metis

Step 2: Compile the Code

Navigate to the project directory and compile the source code:

mpic++ -std=c++17 -fopenmp src/parallel_update.cpp -o parallel_update

Step 3: Generate Partition File

Use METIS to partition the graph:

gpmetis datasets/dummy_100_nodes.txt 4

This will generate a partition file named dummy_100_nodes.txt.part.4.

Step 4: Run the Program

Run the program using MPI:

mpirun -np 4 ./parallel_update datasets/dummy_100_nodes.txt datasets/dummy_100_nodes.txt.part.4

Step 5: Analyze Results

The program outputs Pareto-optimal solutions and performance metrics to the results/ directory. Logs for each MPI rank are stored in separate files (output_rank*.txt).

---

Scalability Analysis

To evaluate the scalability of the algorithm:

1. Use graphs of varying sizes (e.g., 100, 1,000, 10,000 vertices).
2. Experiment with different numbers of MPI processes and OpenMP threads.
3. Measure execution time, speedup, and efficiency.

Example command for scalability testing:

mpirun -np 8 ./parallel_update datasets/large_graph.txt datasets/large_graph.txt.part.8

---

Datasets

The project includes example datasets in the datasets/ directory. You can also use publicly available graph datasets such as:

• SNAP Datasets
• KONECT

Ensure that the graph files are converted to the METIS format before use.

---

Contributing

Contributions are welcome! If you'd like to contribute, please follow these steps:

1. Fork the repository.
2. Create a new branch (git checkout -b feature/your-feature).
3. Commit your changes (git commit -m "Add your feature").
4. Push to the branch (git push origin feature/your-feature).
5. Open a pull request.

---

License

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

---

Acknowledgments

We would like to thank:

• Our instructor and teaching assistants for their guidance throughout the project.
• The authors of the research papers and tools (e.g., METIS, MPI) that inspired this work.
• The open-source community for providing valuable resources and libraries.

---

If you have any questions or suggestions, feel free to open an issue or contact us directly. Thank you for your interest in our project! 🚀