Last active
July 2, 2024 13:04
-
-
Save qqwqqw689/71fdb4aef8482995d09d3fcf539d49b3 to your computer and use it in GitHub Desktop.
MPI sort example.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <mpi.h> | |
| #include <iostream> | |
| #include <vector> | |
| #include <algorithm> | |
| #include <cstdlib> | |
| #include <ctime> | |
| void bubble_sort(std::vector<int>& arr) { | |
| int n = arr.size(); | |
| for (int i = 0; i < n - 1; ++i) { | |
| for (int j = 0; j < n - i - 1; ++j) { | |
| if (arr[j] > arr[j + 1]) { | |
| std::swap(arr[j], arr[j + 1]); | |
| } | |
| } | |
| } | |
| } | |
| void selection_sort(std::vector<int>& arr) { | |
| int n = arr.size(); | |
| for (int i = 0; i < n - 1; ++i) { | |
| int max_idx = i; | |
| for (int j = i + 1; j < n; ++j) { | |
| if (arr[j] > arr[max_idx]) { | |
| max_idx = j; | |
| } | |
| } | |
| std::swap(arr[i], arr[max_idx]); | |
| } | |
| } | |
| std::vector<int> merge(const std::vector<int>& arr1, const std::vector<int>& arr2) { | |
| std::vector<int> result(arr1.size() + arr2.size()); | |
| std::merge(arr1.begin(), arr1.end(), arr2.begin(), arr2.end(), result.begin()); | |
| return result; | |
| } | |
| int main(int argc, char** argv) { | |
| MPI_Init(&argc, &argv); | |
| int rank, size; | |
| MPI_Comm_rank(MPI_COMM_WORLD, &rank); | |
| MPI_Comm_size(MPI_COMM_WORLD, &size); | |
| const int array_size = 80; // Assuming size * 10 is the total number of elements | |
| std::vector<int> data(array_size); | |
| std::vector<int> local_data(array_size / size); | |
| if (rank == 0) { | |
| srand(time(0)); | |
| for (int i = 0; i < array_size; ++i) { | |
| data[i] = rand() % 100; | |
| } | |
| std::cout << "Original data: "; | |
| for (int i = 0; i < array_size; ++i) { | |
| std::cout << data[i] << " "; | |
| } | |
| std::cout << std::endl; | |
| } | |
| MPI_Scatter(data.data(), array_size / size, MPI_INT, local_data.data(), array_size / size, MPI_INT, 0, MPI_COMM_WORLD); | |
| if (rank % 2 == 0) { | |
| bubble_sort(local_data); | |
| } else { | |
| selection_sort(local_data); | |
| } | |
| std::cout << "Process " << rank << " sorted data: "; | |
| for (int i = 0; i < local_data.size(); ++i) { | |
| std::cout << local_data[i] << " "; | |
| } | |
| std::cout << std::endl; | |
| MPI_Gather(local_data.data(), array_size / size, MPI_INT, data.data(), array_size / size, MPI_INT, 0, MPI_COMM_WORLD); | |
| if (rank == 0) { | |
| std::vector<std::vector<int>> parts(size); | |
| for (int i = 0; i < size; ++i) { | |
| parts[i].assign(data.begin() + i * (array_size / size), data.begin() + (i + 1) * (array_size / size)); | |
| if (i % 2 != 0) { | |
| std::reverse(parts[i].begin(), parts[i].end()); | |
| } | |
| } | |
| while (parts.size() > 1) { | |
| std::vector<std::vector<int>> new_parts; | |
| for (size_t i = 0; i < parts.size(); i += 2) { | |
| if (i + 1 < parts.size()) { | |
| new_parts.push_back(merge(parts[i], parts[i + 1])); | |
| } else { | |
| new_parts.push_back(parts[i]); | |
| } | |
| } | |
| parts = new_parts; | |
| } | |
| auto final_sorted_data = parts[0]; | |
| std::cout << "Final sorted data: "; | |
| for (int i = 0; i < final_sorted_data.size(); ++i) { | |
| std::cout << final_sorted_data[i] << " "; | |
| } | |
| std::cout << std::endl; | |
| } | |
| MPI_Finalize(); | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment