GCC Code Coverage Report

Directory: ./
File: tasks/yurkin_g_shellbetcher/mpi/src/ops_mpi.cpp
Date: 2026-01-10 02:40:41
Exec Total Coverage
Lines: 83 107 77.6%
Functions: 9 11 81.8%
Branches: 57 104 54.8%
Line Branch Exec Source
1 #include "yurkin_g_shellbetcher/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <cmath>
7 #include <cstddef>
8 #include <cstdint>
9 #include <random>
10 #include <vector>
11
12 #include "yurkin_g_shellbetcher/common/include/common.hpp"
13
14 namespace yurkin_g_shellbetcher {
15 namespace {
16
17
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 1 times.
 6 void ShellSort(std::vector<int> &a) {
18 const std::size_t n = a.size();
19
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 1 times.
 6 if (n < 2) {
20 return;
21 }
22
23 std::size_t gap = 1;
24
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
 5 while (gap < n / 3) {
25 ✗ gap = (gap * 3) + 1;
26 }
27
28
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 while (gap > 0) {
29
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 5 times.
 14 for (std::size_t i = gap; i < n; ++i) {
30 9 const int tmp = a[i];
31 std::size_t j = i;
32
4/4
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 5 times.
✓ Branch 3 taken 6 times.
 14 while (j >= gap && a[j - gap] > tmp) {
33 5 a[j] = a[j - gap];
34 j -= gap;
35 }
36 9 a[j] = tmp;
37 }
38 5 gap = (gap - 1) / 3;
39 }
40 }
41
42
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 void OddEvenBatcherMergeLocal(const std::vector<int> &a, const std::vector<int> &b, std::vector<int> &out) {
43 out.clear();
44 6 out.reserve(a.size() + b.size());
45 6 out.insert(out.end(), a.begin(), a.end());
46
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 out.insert(out.end(), b.begin(), b.end());
47
48 const std::size_t n = out.size();
49
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (n < 2) {
50 return;
51 }
52
53
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 6 times.
 36 for (std::size_t phase = 0; phase < n; ++phase) {
54 30 const std::size_t start = phase % 2;
55
2/2
✓ Branch 0 taken 68 times.
✓ Branch 1 taken 30 times.
 98 for (std::size_t i = start; i + 1 < n; i += 2) {
56
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 48 times.
 68 if (out[i] > out[i + 1]) {
57 std::swap(out[i], out[i + 1]);
58 }
59 }
60 }
61 }
62
63 int ComputeNeighbor(int rank, int phase, int size) {
64 int neighbor = MPI_PROC_NULL;
65 ✗ if ((phase % 2) == 0) {
66 ✗ neighbor = (rank % 2 == 0) ? rank + 1 : rank - 1;
67 } else {
68 ✗ neighbor = (rank % 2 == 0) ? rank - 1 : rank + 1;
69 }
70 ✗ if (neighbor < 0 || neighbor >= size) {
71 neighbor = MPI_PROC_NULL;
72 }
73 return neighbor;
74 }
75
76 6 void KeepBlockFromMerged(std::vector<int> &local_data, std::vector<int> &merged, int keep_count, int rank,
77 int partner) {
78
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 const auto k = static_cast<std::size_t>(keep_count);
79
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (merged.size() <= k) {
80 local_data.swap(merged);
81 ✗ return;
82 }
83
84
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank < partner) {
85 3 merged.resize(k);
86 local_data.swap(merged);
87 } else {
88
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 std::vector<int> tmp;
89
1/2
✓ Branch 0 taken 3 times.
✗ Branch 1 not taken.
 3 tmp.assign(merged.end() - static_cast<std::vector<int>::difference_type>(k), merged.end());
90 local_data.swap(tmp);
91 }
92 }
93
94 ✗ void ExchangeAndMergeWithNeighbor(std::vector<int> &local_data, int neighbor, int rank, int keep_count) {
95 ✗ if (neighbor == MPI_PROC_NULL) {
96 ✗ return;
97 }
98
99 ✗ const int send_count = static_cast<int>(local_data.size());
100 ✗ int recv_count = 0;
101
102 ✗ MPI_Sendrecv(&send_count, 1, MPI_INT, neighbor, 100, &recv_count, 1, MPI_INT, neighbor, 100, MPI_COMM_WORLD,
103 MPI_STATUS_IGNORE);
104
105 ✗ std::vector<int> recv_buf(static_cast<std::size_t>(recv_count));
106
107 ✗ MPI_Sendrecv(local_data.data(), send_count, MPI_INT, neighbor, 101, recv_buf.data(), recv_count, MPI_INT, neighbor,
108 101, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
109
110 ✗ std::vector<int> merged;
111 ✗ OddEvenBatcherMergeLocal(local_data, recv_buf, merged);
112 ✗ KeepBlockFromMerged(local_data, merged, keep_count, rank, neighbor);
113 }
114
115 6 void DoPowerOfTwoMergeStep(std::vector<int> &local_data, int rank, int size, int stages, int keep_count) {
116
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 for (int stage = 0; stage < stages; ++stage) {
117
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 for (int sub = stage; sub >= 0; --sub) {
118 6 const int partner = rank ^ (1 << sub);
119
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6 times.
 6 if (partner < 0 || partner >= size) {
120 ✗ continue;
121 }
122
123 6 const int send_count = static_cast<int>(local_data.size());
124 6 int recv_count = 0;
125
126 6 const int tag_count = 2000 + (stage * 16) + sub;
127 6 const int tag_data = 3000 + (stage * 16) + sub;
128
129 6 MPI_Sendrecv(&send_count, 1, MPI_INT, partner, tag_count, &recv_count, 1, MPI_INT, partner, tag_count,
130 MPI_COMM_WORLD, MPI_STATUS_IGNORE);
131
132 6 std::vector<int> recv_buf(static_cast<std::size_t>(recv_count));
133
134
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Sendrecv(local_data.data(), send_count, MPI_INT, partner, tag_data, recv_buf.data(), recv_count, MPI_INT,
135 partner, tag_data, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
136
137 6 std::vector<int> merged;
138
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 OddEvenBatcherMergeLocal(local_data, recv_buf, merged);
139
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 KeepBlockFromMerged(local_data, merged, keep_count, rank, partner);
140
141
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Barrier(MPI_COMM_WORLD);
142 }
143 }
144 6 }
145
146 ✗ void DoOddEvenTransposition(std::vector<int> &local_data, int rank, int size, int keep_count) {
147 ✗ for (int phase = 0; phase < size; ++phase) {
148 const int neighbor = ComputeNeighbor(rank, phase, size);
149 ✗ ExchangeAndMergeWithNeighbor(local_data, neighbor, rank, keep_count);
150 ✗ MPI_Barrier(MPI_COMM_WORLD);
151 }
152 ✗ }
153
154 } // namespace
155
156 6 YurkinGShellBetcherMPI::YurkinGShellBetcherMPI(const InType &in) {
157 SetTypeOfTask(GetStaticTypeOfTask());
158 6 GetInput() = in;
159 GetOutput() = 0;
160 6 }
161
162 6 bool YurkinGShellBetcherMPI::ValidationImpl() {
163
2/4
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 6 times.
 6 return (GetInput() > 0) && (GetOutput() == 0);
164 }
165
166 6 bool YurkinGShellBetcherMPI::PreProcessingImpl() {
167 6 int initialized = 0;
168 6 MPI_Initialized(&initialized);
169
2/4
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 6 times.
 6 return initialized != 0 && GetInput() > 0;
170 }
171
172 6 bool YurkinGShellBetcherMPI::RunImpl() {
173 6 const InType n = GetInput();
174
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (n <= 0) {
175 return false;
176 }
177
178 6 int rank = 0;
179 6 int size = 1;
180 6 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
181 6 MPI_Comm_size(MPI_COMM_WORLD, &size);
182
183 6 const InType base = n / size;
184 6 const InType rem = n % size;
185
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 const InType local_n = base + (rank < rem ? 1 : 0);
186
187 6 std::vector<int> local_data;
188
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 local_data.reserve(static_cast<std::size_t>(local_n));
189
190 6 std::mt19937 rng(static_cast<unsigned int>(n));
191 std::uniform_int_distribution<int> dist(0, 1000000);
192
193 6 const InType offset = (base * static_cast<InType>(rank)) + std::min(static_cast<InType>(rank), rem);
194
195
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 6 times.
 15 for (InType i = 0; i < offset; ++i) {
196 (void)dist(rng);
197 }
198
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 6 times.
 21 for (InType i = 0; i < local_n; ++i) {
199
1/4
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 15 local_data.push_back(dist(rng));
200 }
201
202 6 ShellSort(local_data);
203
204 const int keep_count = static_cast<int>(local_n);
205
206
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 auto is_power_of_two = [](int x) { return x > 0 && ((x & (x - 1)) == 0); };
207
208
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 if (is_power_of_two(size)) {
209 6 const int stages = static_cast<int>(std::log2(size));
210
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 DoPowerOfTwoMergeStep(local_data, rank, size, stages, keep_count);
211 } else {
212 ✗ DoOddEvenTransposition(local_data, rank, size, keep_count);
213 }
214
215 6 std::int64_t local_checksum = 0;
216
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 6 times.
 21 for (int v : local_data) {
217 15 local_checksum += static_cast<std::int64_t>(v);
218 }
219
220 6 std::int64_t global_checksum = 0;
221
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Allreduce(&local_checksum, &global_checksum, 1, MPI_INT64_T, MPI_SUM, MPI_COMM_WORLD);
222
223 6 GetOutput() = static_cast<OutType>(global_checksum & 0x7FFFFFFF);
224
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Barrier(MPI_COMM_WORLD);
225 return true;
226 }
227
228 6 bool YurkinGShellBetcherMPI::PostProcessingImpl() {
229 6 return GetOutput() > 0;
230 }
231
232 } // namespace yurkin_g_shellbetcher
233