How musaabimran/top-k-shortest-path-problem works
Main Components
• Input/Parsing Component:
• Reads the weighted graph from an input file. This is responsible for parsing the file (actual sample options provided include doctorwho.csv, Email-Euron.txt, etc.) and formatting it appropriately.
• Distance Matrix Initialization:
• Prepares the initial distance matrix by setting self-distances to 0 and other missing edges to infinity. The matrix represents the graph internally.
• MPI-Based Module (Inter-Process Communication):
• Each process handles computation on its subset (calculating local shortest paths).
• OpenMP-Based Module (Intra-Process Parallelism):
• Within each MPI process, OpenMP is used to parallelize intensive looping constructs that perform the path computations.
• Result Gathering and Combination:
• Once every process has computed its local solution, MPI is again used to gather and combine these local solutions into the final Top K shortest path result.
• Execution and Control Flow:
• Contains both serial and parallel execution entry points, depending on the build and runtime configuration.
Relationships and Interactions
• Data Flow:
• Graph input is parsed and used to initialize the distance matrix.
• The distance matrix data is distributed among MPI processes (each receiving a subset of the matrix or graph).
• Within each MPI process, OpenMP threads operate on specific portions of that matrix to compute shortest paths.
• Once local computations are complete, MPI processes exchange data to combine local results into the final global result.
• Dependencies:
• The MPI module handles inter-process communication while the OpenMP module deals with in-process parallelism.
• The control and synchronization mechanisms ensure correct data propagation and merging.
Architectural Patterns and Design Principles
• Hybrid Parallelism Pattern:
• Combined use of MPI and OpenMP demonstrates a layered parallelism approach. MPI handles multi-node or multi-process computation while OpenMP further accelerates this on shared-memory systems.
• Divide and Conquer:
• Pipeline of computation:
Technologies and Libraries
• MPI (Message Passing Interface): Used for distributing computation and exchanging data between processes.
• OpenMP: Provides multi-threading within individual processes, essential for the inner-loop performance.
• C++: The core implementation language, represented by the .cpp files.