GCC Code Coverage Report

Directory: ./
File: tasks/belov_e_shell_batcher/mpi/src/ops_mpi.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 114 117 97.4%
Functions: 12 12 100.0%
Branches: 98 150 65.3%
Line Branch Exec Source
1 #include "belov_e_shell_batcher/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <cstddef>
7 #include <limits>
8 #include <utility>
9 #include <vector>
10
11 #include "belov_e_shell_batcher/common/include/common.hpp"
12
13 namespace belov_e_shell_batcher {
14
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 BelovEShellBatcherMPI::BelovEShellBatcherMPI(const InType &in) {
15 SetTypeOfTask(GetStaticTypeOfTask());
16
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 GetInput() = in;
17 6 }
18
19 6 bool BelovEShellBatcherMPI::ValidationImpl() {
20 6 return !GetInput().empty();
21 }
22
23 6 bool BelovEShellBatcherMPI::PreProcessingImpl() {
24 6 return true;
25 }
26
27 6 void ShellSort(std::vector<int> &arr) {
28 size_t n = arr.size();
29
30
2/2
✓ Branch 0 taken 46 times.
✓ Branch 1 taken 6 times.
 52 for (size_t gap = n / 2; gap > 0; gap /= 2) {
31
2/2
✓ Branch 0 taken 17000068 times.
✓ Branch 1 taken 46 times.
 17000114 for (size_t i = gap; i < n; i++) {
32 17000068 int temp = arr[i];
33 size_t j = i;
34
35
4/4
✓ Branch 0 taken 24857622 times.
✓ Branch 1 taken 999981 times.
✓ Branch 2 taken 8857535 times.
✓ Branch 3 taken 16000087 times.
 25857603 while (j >= gap && arr[j - gap] > temp) {
36 8857535 arr[j] = arr[j - gap];
37 j -= gap;
38 }
39
40 17000068 arr[j] = temp;
41 }
42 }
43 6 }
44
45 6 std::vector<int> BatcherLeftMerge(std::vector<int> &input_left_arr, std::vector<int> &input_right_arr,
46 int local_arr_size, int rank, MPI_Comm comm) {
47 6 std::vector<int> even_arr1;
48
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 even_arr1.reserve(local_arr_size);
49 6 std::vector<int> even_arr2;
50
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 even_arr2.reserve(local_arr_size);
51
2/2
✓ Branch 0 taken 500016 times.
✓ Branch 1 taken 6 times.
 500022 for (int i = 0; i < local_arr_size; i += 2) {
52
1/2
✓ Branch 0 taken 500016 times.
✗ Branch 1 not taken.
 500016 even_arr1.push_back(input_left_arr[i]);
53 }
54
2/2
✓ Branch 0 taken 500016 times.
✓ Branch 1 taken 6 times.
 500022 for (int i = 0; i < local_arr_size; i += 2) {
55
1/2
✓ Branch 0 taken 500016 times.
✗ Branch 1 not taken.
 500016 even_arr2.push_back(input_right_arr[i]);
56 }
57
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 std::vector<int> even_arr;
58
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 even_arr.resize(even_arr1.size() + even_arr2.size());
59 6 std::ranges::merge(even_arr1, even_arr2, even_arr.begin());
60
61 6 std::vector<int> odd_arr;
62
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 odd_arr.resize((2 * static_cast<size_t>(local_arr_size)) - even_arr.size());
63
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Sendrecv(even_arr.data(), static_cast<int>(even_arr.size()), MPI_INT, rank + 1, 0, odd_arr.data(),
64 static_cast<int>(odd_arr.size()), MPI_INT, rank + 1, 0, comm, MPI_STATUS_IGNORE);
65
66 6 std::vector<int> left_arr;
67
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 left_arr.reserve(local_arr_size);
68
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (local_arr_size != 0) {
69 left_arr.push_back(even_arr[0]);
70 }
71 int i = 0;
72
2/2
✓ Branch 0 taken 500014 times.
✓ Branch 1 taken 6 times.
 500020 while (left_arr.size() < static_cast<size_t>(local_arr_size)) {
73
2/2
✓ Branch 0 taken 500013 times.
✓ Branch 1 taken 1 times.
 500014 std::pair<int, int> comp = {even_arr[i + 1], odd_arr[i]};
74
2/2
✓ Branch 0 taken 500013 times.
✓ Branch 1 taken 1 times.
 500014 if (comp.first > comp.second) {
75 comp = {comp.second, comp.first};
76 }
77
78 left_arr.push_back(comp.first);
79
2/2
✓ Branch 0 taken 500010 times.
✓ Branch 1 taken 4 times.
 500014 if (left_arr.size() < static_cast<size_t>(local_arr_size)) {
80 left_arr.push_back(comp.second);
81 }
82 i++;
83 }
84 6 return left_arr;
85 }
86
87 6 std::vector<int> BatcherRightMerge(std::vector<int> &input_left_arr, std::vector<int> &input_right_arr,
88 int local_arr_size, int rank, MPI_Comm comm) {
89 6 std::vector<int> odd_arr1;
90
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 odd_arr1.reserve(local_arr_size);
91 6 std::vector<int> odd_arr2;
92
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 odd_arr2.reserve(local_arr_size);
93
2/2
✓ Branch 0 taken 500014 times.
✓ Branch 1 taken 6 times.
 500020 for (int i = 1; i < local_arr_size; i += 2) {
94
1/2
✓ Branch 0 taken 500014 times.
✗ Branch 1 not taken.
 500014 odd_arr1.push_back(input_left_arr[i]);
95 }
96
2/2
✓ Branch 0 taken 500014 times.
✓ Branch 1 taken 6 times.
 500020 for (int i = 1; i < local_arr_size; i += 2) {
97
1/2
✓ Branch 0 taken 500014 times.
✗ Branch 1 not taken.
 500014 odd_arr2.push_back(input_right_arr[i]);
98 }
99
100
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 std::vector<int> odd_arr;
101
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 odd_arr.resize(odd_arr1.size() + odd_arr2.size());
102 6 std::ranges::merge(odd_arr1, odd_arr2, odd_arr.begin());
103
104 6 std::vector<int> even_arr;
105
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 even_arr.resize((2 * static_cast<size_t>(local_arr_size)) - odd_arr.size());
106
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Sendrecv(odd_arr.data(), static_cast<int>(odd_arr.size()), MPI_INT, rank - 1, 0, even_arr.data(),
107 static_cast<int>(even_arr.size()), MPI_INT, rank - 1, 0, comm, MPI_STATUS_IGNORE);
108
109 6 std::vector<int> right_arr;
110
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 right_arr.reserve(local_arr_size);
111 size_t i = 0;
112
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 2 times.
 6 if (local_arr_size % 2 == 0) {
113
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 1 times.
 4 i = (static_cast<size_t>(local_arr_size) / 2) - 1;
114
115 std::pair<int, int> comp = {even_arr[i + 1], odd_arr[i]};
116
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 1 times.
 4 if (comp.first > comp.second) {
117 comp = {comp.second, comp.first};
118 }
119
120 right_arr.push_back(comp.second);
121 i++;
122 } else {
123 2 i = (static_cast<size_t>(local_arr_size) - 1) / 2;
124 }
125
4/4
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 500012 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 500010 times.
 500016 for (; i + 1 < even_arr.size() && i < odd_arr.size(); i++) {
126 std::pair<int, int> comp = {even_arr[i + 1], odd_arr[i]};
127
2/2
✓ Branch 0 taken 500001 times.
✓ Branch 1 taken 9 times.
 500010 if (comp.first > comp.second) {
128 comp = {comp.second, comp.first};
129 }
130
131 right_arr.push_back(comp.first);
132 right_arr.push_back(comp.second);
133 }
134
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 6 times.
 8 for (; i + 1 < even_arr.size(); i++) {
135 right_arr.push_back(even_arr[i + 1]);
136 }
137
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 6 times.
 10 for (; i < odd_arr.size(); i++) {
138 right_arr.push_back(odd_arr[i]);
139 }
140 6 return right_arr;
141 }
142
143 6 void LeftProcAct(int rank, std::vector<int> &local_arr, int local_arr_size, MPI_Comm comm) {
144 6 std::vector<int> right_arr;
145
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 right_arr.resize(local_arr_size);
146
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Sendrecv(local_arr.data(), local_arr_size, MPI_INT, rank + 1, 0, right_arr.data(), local_arr_size, MPI_INT,
147 rank + 1, 0, comm, MPI_STATUS_IGNORE);
148
2/6
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 6 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 12 local_arr = BatcherLeftMerge(local_arr, right_arr, local_arr_size, rank, comm);
149 6 }
150
151 6 void RightProcAct(int rank, std::vector<int> &local_arr, int local_arr_size, MPI_Comm comm) {
152 6 std::vector<int> left_arr;
153
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 left_arr.resize(local_arr_size);
154
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Sendrecv(local_arr.data(), local_arr_size, MPI_INT, rank - 1, 0, left_arr.data(), local_arr_size, MPI_INT,
155 rank - 1, 0, comm, MPI_STATUS_IGNORE);
156
2/6
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 6 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 12 local_arr = BatcherRightMerge(left_arr, local_arr, local_arr_size, rank, comm);
157 6 }
158
159 12 void EvenPhase(int rank, int mpi_size, std::vector<int> &local_arr, int local_arr_size, MPI_Comm comm) {
160
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 12 if (mpi_size % 2 != 0 && rank == mpi_size - 1) {
161 return;
162 }
163
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (rank % 2 == 0) {
164 6 LeftProcAct(rank, local_arr, local_arr_size, comm);
165 } else {
166 6 RightProcAct(rank, local_arr, local_arr_size, comm);
167 }
168 }
169
170 6 void OddPhase(int rank, int mpi_size, std::vector<int> &local_arr, int local_arr_size, MPI_Comm comm) {
171
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank == 0) {
172 return;
173 }
174
2/4
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 3 times.
 3 if (mpi_size % 2 == 0 && rank == mpi_size - 1) {
175 return;
176 }
177 ✗ if (rank % 2 == 0) {
178 ✗ RightProcAct(rank, local_arr, local_arr_size, comm);
179 } else {
180 ✗ LeftProcAct(rank, local_arr, local_arr_size, comm);
181 }
182 }
183
184 6 bool BelovEShellBatcherMPI::RunImpl() {
185 6 int mpi_size = 0;
186 6 int rank = 0;
187
188 6 MPI_Comm_size(MPI_COMM_WORLD, &mpi_size);
189 6 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
190
191 6 std::vector<int> arr;
192 6 int n = 0;
193
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank == 0) {
194 arr = GetInput();
195 3 n = static_cast<int>(arr.size());
196 }
197
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
198
199
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 4 times.
 6 int garbage = (n % mpi_size == 0) ? 0 : (mpi_size - (n % mpi_size));
200
201
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank == 0) {
202
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 3 times.
 4 for (int i = 0; i < garbage; i++) {
203
1/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 1 arr.push_back(std::numeric_limits<int>::max());
204 }
205 }
206
207 6 int local_arr_size = (n + garbage) / mpi_size;
208 6 std::vector<int> local_arr;
209
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 local_arr.resize(local_arr_size);
210
211
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Scatter(arr.data(), local_arr_size, MPI_INT, local_arr.data(), local_arr_size, MPI_INT, 0, MPI_COMM_WORLD);
212
213 6 ShellSort(local_arr);
214
215
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 6 times.
 24 for (int i = 0; i < mpi_size + 1; i++) {
216
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 6 times.
 18 if (i % 2 == 0) {
217
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 EvenPhase(rank, mpi_size, local_arr, local_arr_size, MPI_COMM_WORLD);
218 } else {
219
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 OddPhase(rank, mpi_size, local_arr, local_arr_size, MPI_COMM_WORLD);
220 }
221 }
222
223
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 arr.resize(n + garbage);
224
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Allgather(local_arr.data(), local_arr_size, MPI_INT, arr.data(), local_arr_size, MPI_INT, MPI_COMM_WORLD);
225
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 arr.resize(n);
226
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 GetOutput() = arr;
227 6 return true;
228 }
229
230 6 bool BelovEShellBatcherMPI::PostProcessingImpl() {
231 6 return true;
232 }
233
234 } // namespace belov_e_shell_batcher
235