GCC Code Coverage Report

Directory: ./
File: tasks/dolov_v_qsort_batcher/mpi/src/ops_mpi.cpp
Date: 2026-01-10 02:40:41
Exec Total Coverage
Lines: 101 102 99.0%
Functions: 12 12 100.0%
Branches: 66 82 80.5%
Line Branch Exec Source
1 #include "dolov_v_qsort_batcher/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <cstddef>
7 #include <stack>
8 #include <utility>
9 #include <vector>
10
11 #include "dolov_v_qsort_batcher/common/include/common.hpp"
12
13 namespace dolov_v_qsort_batcher {
14
15
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 DolovVQsortBatcherMPI::DolovVQsortBatcherMPI(const InType &in) {
16 SetTypeOfTask(GetStaticTypeOfTask());
17
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 GetInput() = in;
18 12 }
19
20 12 bool DolovVQsortBatcherMPI::ValidationImpl() {
21 12 return true;
22 }
23
24 12 bool DolovVQsortBatcherMPI::PreProcessingImpl() {
25 12 int world_rank = 0;
26 12 int world_size = 0;
27 12 MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
28 12 MPI_Comm_size(MPI_COMM_WORLD, &world_size);
29
30
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
 12 if (world_rank == 0) {
31 6 total_count_ = static_cast<int>(GetInput().size());
32 }
33
34 12 MPI_Bcast(&total_count_, 1, MPI_INT, 0, MPI_COMM_WORLD);
35
36
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 if (total_count_ < 0) {
37 return false;
38 }
39
40 12 part_sizes_.assign(world_size, 0);
41 12 part_offsets_.assign(world_size, 0);
42
43 12 int base_size = total_count_ / world_size;
44 12 int extra = total_count_ % world_size;
45 int current_offset = 0;
46
47
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 12 times.
 36 for (int i = 0; i < world_size; ++i) {
48
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 2 times.
 46 part_sizes_[i] = base_size + (i < extra ? 1 : 0);
49 24 part_offsets_[i] = current_offset;
50 24 current_offset += part_sizes_[i];
51 }
52
53 12 local_buffer_.resize(part_sizes_[world_rank]);
54 return true;
55 }
56
57 12 bool DolovVQsortBatcherMPI::RunImpl() {
58 12 int world_rank = 0;
59 12 int world_size = 0;
60 12 MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);
61 12 MPI_Comm_size(MPI_COMM_WORLD, &world_size);
62
63
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 2 times.
 12 if (total_count_ <= 0) {
64 return true;
65 }
66
67 10 DistributeData(world_rank, world_size);
68
69
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 1 times.
 10 if (!local_buffer_.empty()) {
70 9 FastSort(local_buffer_.data(), 0, static_cast<int>(local_buffer_.size()) - 1);
71 }
72
73 10 ExecuteBatcherParallel(world_rank, world_size);
74
75 10 CollectData(world_rank, world_size);
76
77 return true;
78 }
79
80 10 void DolovVQsortBatcherMPI::DistributeData(int world_rank, int /*world_size*/) {
81
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 const double *send_ptr = (world_rank == 0) ? GetInput().data() : nullptr;
82 10 MPI_Scatterv(send_ptr, part_sizes_.data(), part_offsets_.data(), MPI_DOUBLE, local_buffer_.data(),
83 10 part_sizes_[world_rank], MPI_DOUBLE, 0, MPI_COMM_WORLD);
84 10 }
85
86 10 void DolovVQsortBatcherMPI::BatcherStep(int p_step, int k, int j, int i, int world_rank, int world_size) {
87 10 int p1 = i + j;
88 10 int p2 = i + j + k;
89
90
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 if ((p1 / (p_step * 2)) == (p2 / (p_step * 2))) {
91
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 if (world_rank == p1 || world_rank == p2) {
92
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 int partner = (world_rank == p1) ? p2 : p1;
93
1/2
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
 10 if (partner < world_size) {
94
1/2
✓ Branch 2 taken 10 times.
✗ Branch 3 not taken.
 10 std::vector<double> neighbor_data(part_sizes_[partner]);
95
96
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 MPI_Sendrecv(local_buffer_.data(), static_cast<int>(local_buffer_.size()), MPI_DOUBLE, partner, 0,
97 neighbor_data.data(), part_sizes_[partner], MPI_DOUBLE, partner, 0, MPI_COMM_WORLD,
98 MPI_STATUS_IGNORE);
99
100 10 std::vector<double> merged;
101
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 MergeSequences(local_buffer_, neighbor_data, merged, world_rank == p1);
102 local_buffer_ = std::move(merged);
103 }
104 }
105 }
106 10 }
107
108 10 void DolovVQsortBatcherMPI::ExecuteBatcherParallel(int world_rank, int world_size) {
109
2/4
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 10 times.
✗ Branch 3 not taken.
 10 if (world_size <= 1 || total_count_ == 0) {
110 return;
111 }
112
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 for (int p_step = 1; p_step < world_size; p_step <<= 1) {
113
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 for (int k = p_step; k >= 1; k >>= 1) {
114
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 for (int j = k % p_step; j <= world_size - 1 - k; j += (k << 1)) {
115
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 for (int i = 0; i < k; ++i) {
116 10 BatcherStep(p_step, k, j, i, world_rank, world_size);
117 }
118 }
119 10 MPI_Barrier(MPI_COMM_WORLD);
120 }
121 }
122 }
123
124
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 9 times.
 10 void DolovVQsortBatcherMPI::MergeSequences(const std::vector<double> &first, const std::vector<double> &second,
125 std::vector<double> &result, bool take_low) {
126
3/4
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
 10 if (first.empty() && second.empty()) {
127 ✗ return;
128 }
129
130 size_t n1 = first.size();
131 size_t n2 = second.size();
132 10 result.resize(n1);
133 10 std::vector<double> combined(n1 + n2);
134 size_t i = 0;
135 size_t j = 0;
136 size_t k = 0;
137
138
2/2
✓ Branch 0 taken 716 times.
✓ Branch 1 taken 10 times.
 726 while (i < n1 && j < n2) {
139
2/2
✓ Branch 0 taken 359 times.
✓ Branch 1 taken 357 times.
 716 if (first[i] <= second[j]) {
140 359 combined[k++] = first[i++];
141 } else {
142 357 combined[k++] = second[j++];
143 }
144 }
145
2/2
✓ Branch 0 taken 62 times.
✓ Branch 1 taken 10 times.
 72 while (i < n1) {
146 62 combined[k++] = first[i++];
147 }
148
2/2
✓ Branch 0 taken 64 times.
✓ Branch 1 taken 10 times.
 74 while (j < n2) {
149 64 combined[k++] = second[j++];
150 }
151
152 auto diff_n1 = static_cast<std::ptrdiff_t>(n1);
153
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (take_low) {
154 5 std::copy(combined.begin(), combined.begin() + diff_n1, result.begin());
155 } else {
156 5 std::copy(combined.end() - diff_n1, combined.end(), result.begin());
157 }
158 }
159
160 10 void DolovVQsortBatcherMPI::CollectData(int world_rank, int /*world_size*/) {
161 10 std::vector<double> global_array;
162
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (world_rank == 0) {
163
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 global_array.resize(total_count_);
164 }
165
166
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 MPI_Gatherv(local_buffer_.data(), static_cast<int>(local_buffer_.size()), MPI_DOUBLE, global_array.data(),
167 part_sizes_.data(), part_offsets_.data(), MPI_DOUBLE, 0, MPI_COMM_WORLD);
168
169
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
 10 if (world_rank == 0) {
170 GetOutput() = std::move(global_array);
171 }
172 10 }
173
174 412 int DolovVQsortBatcherMPI::GetSplitIndex(double *data, int low, int high) {
175 412 double pivot = data[low + ((high - low) / 2)];
176 412 int i = low - 1;
177 412 int j = high + 1;
178 while (true) {
179 947 i++;
180
2/2
✓ Branch 0 taken 845 times.
✓ Branch 1 taken 947 times.
 1792 while (data[i] < pivot) {
181 845 i++;
182 }
183 947 j--;
184
2/2
✓ Branch 0 taken 940 times.
✓ Branch 1 taken 947 times.
 1887 while (data[j] > pivot) {
185 940 j--;
186 }
187
2/2
✓ Branch 0 taken 412 times.
✓ Branch 1 taken 535 times.
 947 if (i >= j) {
188 412 return j;
189 }
190 std::swap(data[i], data[j]);
191 }
192 }
193
194 9 void DolovVQsortBatcherMPI::FastSort(double *data, int low, int high) {
195 std::stack<std::pair<int, int>> s;
196 s.emplace(low, high);
197
2/2
✓ Branch 0 taken 833 times.
✓ Branch 1 taken 9 times.
 842 while (!s.empty()) {
198 std::pair<int, int> range = s.top();
199 s.pop();
200
2/2
✓ Branch 0 taken 412 times.
✓ Branch 1 taken 421 times.
 833 if (range.first < range.second) {
201
1/2
✓ Branch 2 taken 412 times.
✗ Branch 3 not taken.
 412 int split_point = GetSplitIndex(data, range.first, range.second);
202 s.emplace(range.first, split_point);
203
1/2
✓ Branch 1 taken 412 times.
✗ Branch 2 not taken.
 412 s.emplace(split_point + 1, range.second);
204 }
205 }
206 9 }
207
208 12 bool DolovVQsortBatcherMPI::PostProcessingImpl() {
209 12 return true;
210 }
211
212 } // namespace dolov_v_qsort_batcher
213