GCC Code Coverage Report

Directory: ./
File: tasks/kondakov_v_global_search/mpi/src/ops_mpi.cpp
Date: 2026-01-10 02:40:41
Exec Total Coverage
Lines: 144 153 94.1%
Functions: 13 16 81.2%
Branches: 103 156 66.0%
Line Branch Exec Source
1 #include "kondakov_v_global_search/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <array>
7 #include <cmath>
8 #include <cstddef>
9 #include <iterator>
10 #include <limits>
11 #include <utility>
12 #include <vector>
13
14 #include "kondakov_v_global_search/common/include/common.hpp"
15
16 namespace kondakov_v_global_search {
17
18
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 KondakovVGlobalSearchMPI::KondakovVGlobalSearchMPI(const InType &in) {
19
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 MPI_Comm_rank(MPI_COMM_WORLD, &world_rank_);
20
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 MPI_Comm_size(MPI_COMM_WORLD, &world_size_);
21 SetTypeOfTask(GetStaticTypeOfTask());
22 8 GetInput() = in;
23 8 GetOutput() = {};
24 8 }
25
26 636 double KondakovVGlobalSearchMPI::EvaluateFunction(double x) {
27 const auto &cfg = GetInput();
28
3/4
✓ Branch 0 taken 542 times.
✓ Branch 1 taken 67 times.
✓ Branch 2 taken 27 times.
✗ Branch 3 not taken.
 636 switch (cfg.func_type) {
29 542 case FunctionType::kQuadratic: {
30 542 double t = cfg.func_param;
31 542 return (x - t) * (x - t);
32 }
33 67 case FunctionType::kSine:
34 67 return std::sin(x) + (0.1 * x);
35 case FunctionType::kAbs:
36 27 return std::abs(x);
37 default:
38 return std::numeric_limits<double>::quiet_NaN();
39 }
40 }
41
42 ✗ bool KondakovVGlobalSearchMPI::IsRoot() const {
43 1936 return world_rank_ == 0;
44 }
45
46 8 bool KondakovVGlobalSearchMPI::ValidationImpl() {
47 const auto &cfg = GetInput();
48
4/8
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 8 times.
 8 bool local_valid = cfg.left < cfg.right && cfg.accuracy > 0.0 && cfg.reliability > 0.0 && cfg.max_iterations > 0;
49
50 8 bool global_valid = false;
51 8 MPI_Allreduce(&local_valid, &global_valid, 1, MPI_C_BOOL, MPI_LAND, MPI_COMM_WORLD);
52 8 return global_valid;
53 }
54
55 8 bool KondakovVGlobalSearchMPI::PreProcessingImpl() {
56 const auto &cfg = GetInput();
57
58
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (IsRoot()) {
59 points_x_.clear();
60 values_y_.clear();
61 4 points_x_.reserve(cfg.max_iterations + (world_size_ * 10));
62 4 values_y_.reserve(cfg.max_iterations + (world_size_ * 10));
63
64 4 double f_a = EvaluateFunction(cfg.left);
65
1/2
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
 4 double f_b = EvaluateFunction(cfg.right);
66
2/4
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 4 times.
 4 if (!std::isfinite(f_a) || !std::isfinite(f_b)) {
67 ✗ return false;
68 }
69
70 4 points_x_ = {cfg.left, cfg.right};
71 4 values_y_ = {f_a, f_b};
72
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 3 times.
 4 best_point_ = (f_a < f_b) ? cfg.left : cfg.right;
73 4 best_value_ = std::min(f_a, f_b);
74 }
75
76 8 SyncGlobalState();
77 8 return true;
78 }
79
80 640 void KondakovVGlobalSearchMPI::SyncGlobalState() {
81
2/2
✓ Branch 0 taken 320 times.
✓ Branch 1 taken 320 times.
 640 int n = IsRoot() ? static_cast<int>(points_x_.size()) : 0;
82 640 MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
83
84
2/2
✓ Branch 0 taken 320 times.
✓ Branch 1 taken 320 times.
 640 if (!IsRoot()) {
85 320 points_x_.resize(n);
86 320 values_y_.resize(n);
87 }
88
89
1/2
✓ Branch 0 taken 640 times.
✗ Branch 1 not taken.
 640 if (n > 0) {
90 640 MPI_Bcast(points_x_.data(), n, MPI_DOUBLE, 0, MPI_COMM_WORLD);
91 640 MPI_Bcast(values_y_.data(), n, MPI_DOUBLE, 0, MPI_COMM_WORLD);
92 }
93
94 640 best_value_ = std::numeric_limits<double>::max();
95
2/2
✓ Branch 0 taken 79196 times.
✓ Branch 1 taken 640 times.
 79836 for (std::size_t i = 0; i < points_x_.size(); ++i) {
96
2/2
✓ Branch 0 taken 40364 times.
✓ Branch 1 taken 38832 times.
 79196 if (values_y_[i] < best_value_) {
97 40364 best_value_ = values_y_[i];
98 40364 best_point_ = points_x_[i];
99 }
100 }
101 640 }
102
103
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 78 times.
 78 double KondakovVGlobalSearchMPI::ComputeAdaptiveLipschitzEstimate(double r) const {
104 const double min_slope = 1e-2;
105
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 78 times.
 78 if (points_x_.size() < 2) {
106 ✗ return r * min_slope;
107 }
108
109 double max_slope = min_slope;
110
2/2
✓ Branch 0 taken 8376 times.
✓ Branch 1 taken 78 times.
 8454 for (std::size_t i = 1; i < points_x_.size(); ++i) {
111 8376 double dx = points_x_[i] - points_x_[i - 1];
112
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8376 times.
 8376 if (dx <= 0.0) {
113 ✗ continue;
114 }
115
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8376 times.
 8376 double dy = std::abs(values_y_[i] - values_y_[i - 1]);
116
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 8376 times.
 8376 if (!std::isfinite(dy)) {
117 ✗ continue;
118 }
119
1/2
✓ Branch 0 taken 8376 times.
✗ Branch 1 not taken.
 8376 double slope = dy / dx;
120
1/2
✓ Branch 0 taken 8376 times.
✗ Branch 1 not taken.
 8376 if (std::isfinite(slope) && slope > max_slope) {
121 max_slope = slope;
122 }
123 }
124 78 return r * max_slope;
125 }
126
127 78556 double KondakovVGlobalSearchMPI::IntervalMerit(std::size_t i, double l_est) const {
128 78556 double x_l = points_x_[i - 1];
129 78556 double x_r = points_x_[i];
130 78556 double f_l = values_y_[i - 1];
131 78556 double f_r = values_y_[i];
132 78556 double h = x_r - x_l;
133 78556 double df = f_r - f_l;
134 78556 return (l_est * h) - (2.0 * (f_l + f_r)) + ((df * df) / (l_est * h));
135 }
136
137 628 double KondakovVGlobalSearchMPI::ProposeTrialPoint(std::size_t i, double l_est) const {
138
2/2
✓ Branch 0 taken 599 times.
✓ Branch 1 taken 29 times.
 628 double x_l = points_x_[i - 1];
139 628 double x_r = points_x_[i];
140 628 double f_l = values_y_[i - 1];
141 628 double f_r = values_y_[i];
142 628 double mid = 0.5 * (x_l + x_r);
143 628 double asym = (f_r - f_l) / (2.0 * l_est);
144 628 double cand = mid - asym;
145
4/4
✓ Branch 0 taken 599 times.
✓ Branch 1 taken 29 times.
✓ Branch 2 taken 24 times.
✓ Branch 3 taken 575 times.
 628 if (cand <= x_l || cand >= x_r) {
146 cand = mid;
147 }
148 628 return cand;
149 }
150
151 ✗ std::size_t KondakovVGlobalSearchMPI::LocateInsertionIndex(double x) const {
152 auto it = std::ranges::lower_bound(points_x_, x);
153 ✗ return static_cast<std::size_t>(std::distance(points_x_.begin(), it));
154 }
155
156 628 void KondakovVGlobalSearchMPI::InsertEvaluation(double x, double fx) {
157 628 auto idx = LocateInsertionIndex(x);
158 628 points_x_.insert(points_x_.begin() + static_cast<std::vector<double>::difference_type>(idx), x);
159 628 values_y_.insert(values_y_.begin() + static_cast<std::vector<double>::difference_type>(idx), fx);
160
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 615 times.
 628 if (fx < best_value_) {
161 13 best_value_ = fx;
162 13 best_point_ = x;
163 }
164 628 }
165
166
2/2
✓ Branch 0 taken 632 times.
✓ Branch 1 taken 8 times.
 640 void KondakovVGlobalSearchMPI::SelectIntervalsToRefine(double l_est,
167 std::vector<std::pair<double, std::size_t>> &merits) {
168 merits.clear();
169
2/2
✓ Branch 0 taken 78556 times.
✓ Branch 1 taken 640 times.
 79196 for (std::size_t i = 1; i < points_x_.size(); ++i) {
170 78556 merits.emplace_back(IntervalMerit(i, l_est), i);
171 }
172
16/22
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 3374 times.
✓ Branch 5 taken 4882 times.
✓ Branch 6 taken 1968 times.
✓ Branch 7 taken 1406 times.
✓ Branch 8 taken 1458 times.
✓ Branch 9 taken 3424 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✓ Branch 12 taken 1852 times.
✓ Branch 13 taken 7180 times.
✓ Branch 14 taken 19526 times.
✓ Branch 15 taken 7180 times.
✓ Branch 16 taken 295468 times.
✓ Branch 17 taken 78456 times.
✓ Branch 18 taken 72030 times.
✓ Branch 19 taken 78456 times.
✓ Branch 20 taken 173330 times.
✓ Branch 21 taken 68884 times.
 810618 std::ranges::sort(merits, [](const auto &a, const auto &b) { return a.first > b.first; });
173 640 }
174
175 ✗ bool KondakovVGlobalSearchMPI::CheckConvergence(const Params &cfg,
176 const std::vector<std::pair<double, std::size_t>> &merits) {
177
1/4
✓ Branch 0 taken 640 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 640 if (merits.empty()) {
178 return false;
179 }
180
2/4
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 632 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 640 double width = points_x_[merits[0].second] - points_x_[merits[0].second - 1];
181
2/4
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 632 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 640 if (width <= cfg.accuracy) {
182 8 has_converged_ = true;
183 ✗ return true;
184 }
185 return false;
186 }
187
188 632 void KondakovVGlobalSearchMPI::GatherAndBroadcastTrialResults(const std::vector<std::pair<double, std::size_t>> &merits,
189 int num_trials, double l_est) {
190 double local_x = 0.0;
191 double local_fx = 0.0;
192 632 int local_count = 0;
193
194
3/4
✓ Branch 0 taken 628 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 628 times.
✗ Branch 3 not taken.
 632 if (world_rank_ < num_trials && !merits.empty()) {
195
1/2
✓ Branch 0 taken 628 times.
✗ Branch 1 not taken.
 628 std::size_t idx = merits[world_rank_].second;
196 628 double x = ProposeTrialPoint(idx, l_est);
197
1/2
✓ Branch 0 taken 628 times.
✗ Branch 1 not taken.
 628 double fx = EvaluateFunction(x);
198
1/2
✓ Branch 0 taken 628 times.
✗ Branch 1 not taken.
 628 if (std::isfinite(fx)) {
199 local_x = x;
200 local_fx = fx;
201 628 local_count = 2;
202 }
203 }
204
205
1/2
✓ Branch 2 taken 632 times.
✗ Branch 3 not taken.
 632 std::vector<int> counts(world_size_);
206
1/2
✓ Branch 1 taken 632 times.
✗ Branch 2 not taken.
 632 MPI_Allgather(&local_count, 1, MPI_INT, counts.data(), 1, MPI_INT, MPI_COMM_WORLD);
207
208
1/4
✓ Branch 1 taken 632 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 632 std::vector<int> displs(world_size_);
209
2/2
✓ Branch 0 taken 632 times.
✓ Branch 1 taken 632 times.
 1264 for (int i = 1; i < world_size_; ++i) {
210 632 displs[i] = displs[i - 1] + counts[i - 1];
211 }
212
1/2
✓ Branch 0 taken 632 times.
✗ Branch 1 not taken.
 632 int total = (world_size_ > 0) ? (displs.back() + counts.back()) : 0;
213
214 632 std::vector<double> recv_buf;
215
1/2
✓ Branch 0 taken 632 times.
✗ Branch 1 not taken.
 632 if (total > 0) {
216
1/2
✓ Branch 1 taken 632 times.
✗ Branch 2 not taken.
 632 recv_buf.resize(total);
217 }
218 632 std::array<double, 2> send_buf = {local_x, local_fx};
219
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 628 times.
 632 const double *send_ptr = (local_count > 0) ? send_buf.data() : nullptr;
220
221
1/2
✓ Branch 1 taken 632 times.
✗ Branch 2 not taken.
 632 MPI_Allgatherv(send_ptr, local_count, MPI_DOUBLE, recv_buf.data(), counts.data(), displs.data(), MPI_DOUBLE,
222 MPI_COMM_WORLD);
223
224
2/2
✓ Branch 0 taken 316 times.
✓ Branch 1 taken 316 times.
 632 if (IsRoot()) {
225
2/2
✓ Branch 0 taken 628 times.
✓ Branch 1 taken 316 times.
 944 for (int i = 0; i < total; i += 2) {
226
1/2
✓ Branch 1 taken 628 times.
✗ Branch 2 not taken.
 628 InsertEvaluation(recv_buf[i], recv_buf[i + 1]);
227 }
228 }
229 632 }
230
231 8 bool KondakovVGlobalSearchMPI::RunImpl() {
232 const auto &cfg = GetInput();
233 8 std::vector<std::pair<double, std::size_t>> merits;
234 8 double l_est = ComputeAdaptiveLipschitzEstimate(cfg.reliability);
235
236
1/2
✓ Branch 0 taken 640 times.
✗ Branch 1 not taken.
 640 for (int step = 0; step < cfg.max_iterations; ++step) {
237
2/2
✓ Branch 0 taken 70 times.
✓ Branch 1 taken 570 times.
 640 if (step % 10 == 0) {
238 70 l_est = ComputeAdaptiveLipschitzEstimate(cfg.reliability);
239 }
240
241
1/2
✓ Branch 1 taken 640 times.
✗ Branch 2 not taken.
 640 SelectIntervalsToRefine(l_est, merits);
242 if (CheckConvergence(cfg, merits)) {
243 break;
244 }
245
246
1/2
✓ Branch 1 taken 632 times.
✗ Branch 2 not taken.
 632 int num_trials = std::min(static_cast<int>(merits.size()), world_size_);
247
1/2
✓ Branch 1 taken 632 times.
✗ Branch 2 not taken.
 632 GatherAndBroadcastTrialResults(merits, num_trials, l_est);
248
1/2
✓ Branch 1 taken 632 times.
✗ Branch 2 not taken.
 632 SyncGlobalState();
249 632 total_evals_ += num_trials;
250 }
251
252
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (IsRoot()) {
253 4 GetOutput() =
254 4 Solution{.argmin = best_point_, .value = best_value_, .iterations = total_evals_, .converged = has_converged_};
255 }
256 8 return true;
257 }
258
259 8 bool KondakovVGlobalSearchMPI::PostProcessingImpl() {
260 8 Solution sol;
261
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (IsRoot()) {
262 4 sol = GetOutput();
263 }
264
265 8 MPI_Bcast(&sol.argmin, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD);
266 8 MPI_Bcast(&sol.value, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD);
267 8 MPI_Bcast(&sol.iterations, 1, MPI_INT, 0, MPI_COMM_WORLD);
268
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 int converged = sol.converged ? 1 : 0;
269 8 MPI_Bcast(&converged, 1, MPI_INT, 0, MPI_COMM_WORLD);
270 8 sol.converged = (converged != 0);
271
272 8 GetOutput() = sol;
273 8 return true;
274 }
275
276 } // namespace kondakov_v_global_search
277