GCC Code Coverage Report

Line	Branch	Exec	Source
1			#include "sizov_d_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 <limits>
10			#include <vector>
11
12			#include "sizov_d_global_search/common/include/common.hpp"
13
14			namespace sizov_d_global_search {
15
16		✗	SizovDGlobalSearchMPI::SizovDGlobalSearchMPI(const InType &in) {
17			SetTypeOfTask(GetStaticTypeOfTask());
18			GetInput() = in;
19		✗	GetOutput() = {};
20		✗	}
21
22		✗	bool SizovDGlobalSearchMPI::ValidationImpl() {
23			const auto &p = GetInput();
24		✗	if (!p.func) {
25			return false;
26			}
27		✗	if (!(p.left < p.right)) {
28			return false;
29			}
30		✗	if (!(p.accuracy > 0.0)) {
31			return false;
32			}
33		✗	if (!(p.reliability > 0.0)) {
34			return false;
35			}
36		✗	if (p.max_iterations <= 0) {
37		✗	return false;
38			}
39			return true;
40			}
41
42		✗	bool SizovDGlobalSearchMPI::PreProcessingImpl() {
43			const auto &p = GetInput();
44
45		✗	int rank = 0;
46		✗	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
47
48		✗	int ok = 1;
49
50		✗	if (rank == 0) {
51			x_.clear();
52			y_.clear();
53
54		✗	x_.reserve(static_cast<std::size_t>(p.max_iterations) + 8U);
55		✗	y_.reserve(static_cast<std::size_t>(p.max_iterations) + 8U);
56
57		✗	const double left = p.left;
58		✗	const double right = p.right;
59
60		✗	const double f_left = p.func(left);
61		✗	const double f_right = p.func(right);
62
63		✗	if (!std::isfinite(f_left) || !std::isfinite(f_right)) {
64		✗	ok = 0;
65			} else {
66			x_.push_back(left);
67			x_.push_back(right);
68			y_.push_back(f_left);
69			y_.push_back(f_right);
70
71		✗	if (f_left <= f_right) {
72		✗	best_x_ = left;
73		✗	best_y_ = f_left;
74			} else {
75		✗	best_x_ = right;
76		✗	best_y_ = f_right;
77			}
78
79		✗	iterations_ = 0;
80		✗	converged_ = false;
81			}
82			}
83
84		✗	MPI_Bcast(&ok, 1, MPI_INT, 0, MPI_COMM_WORLD);
85		✗	if (ok == 0) {
86			return false;
87			}
88
89		✗	BroadcastState(rank);
90			return true;
91			}
92
93		✗	void SizovDGlobalSearchMPI::GetChunk(std::size_t intervals, int rank, int size, std::size_t &begin, std::size_t &end) {
94		✗	if (intervals == 0U || size <= 0) {
95		✗	begin = 0;
96		✗	end = 0;
97			return;
98			}
99
100		✗	const auto s = static_cast<std::size_t>(size);
101		✗	const auto r = static_cast<std::size_t>(rank);
102
103		✗	const std::size_t base = intervals / s;
104		✗	const std::size_t rem = intervals % s;
105
106		✗	begin = (r * base) + std::min(r, rem);
107		✗	end = begin + base + ((r < rem) ? 1U : 0U);
108		✗	end = std::min(end, intervals);
109			}
110
111		✗	double SizovDGlobalSearchMPI::EstimateM(double reliability, int rank, int size) const {
112		✗	constexpr double kMinSlope = 1e-2;
113
114			const std::size_t n = x_.size();
115		✗	if (n < 2U) {
116		✗	return reliability * kMinSlope;
117			}
118
119		✗	const std::size_t intervals = n - 1U;
120
121			std::size_t begin = 0;
122		✗	std::size_t end = 0;
123			GetChunk(intervals, rank, size, begin, end);
124
125		✗	double local_max = 0.0;
126		✗	for (std::size_t k = begin; k < end; ++k) {
127		✗	const std::size_t i = k + 1U;
128
129		✗	const double dx = x_[i] - x_[i - 1U];
130		✗	if (!(dx > 0.0)) {
131		✗	continue;
132			}
133
134		✗	const double y1 = y_[i];
135		✗	const double y2 = y_[i - 1U];
136		✗	if (!std::isfinite(y1) || !std::isfinite(y2)) {
137		✗	continue;
138			}
139
140		✗	const double slope = std::abs(y1 - y2) / dx;
141		✗	if (std::isfinite(slope)) {
142		✗	local_max = std::max(local_max, slope);
143			}
144			}
145
146		✗	double global_max = local_max;
147		✗	if (size > 1) {
148		✗	MPI_Allreduce(&local_max, &global_max, 1, MPI_DOUBLE, MPI_MAX, MPI_COMM_WORLD);
149			}
150
151		✗	return reliability * std::max(global_max, kMinSlope);
152			}
153
154		✗	double SizovDGlobalSearchMPI::Characteristic(std::size_t i, double m) const {
155		✗	const double x_right = x_[i];
156		✗	const double x_left = x_[i - 1U];
157		✗	const double y_right = y_[i];
158		✗	const double y_left = y_[i - 1U];
159
160		✗	const double dx = x_right - x_left;
161		✗	const double df = y_right - y_left;
162
163		✗	return (m * dx) + ((df * df) / (m * dx)) - (2.0 * (y_right + y_left));
164			}
165
166		✗	double SizovDGlobalSearchMPI::NewPoint(std::size_t i, double m) const {
167		✗	const double x_right = x_[i];
168		✗	const double x_left = x_[i - 1U];
169		✗	const double y_right = y_[i];
170		✗	const double y_left = y_[i - 1U];
171
172		✗	const double mid = 0.5 * (x_left + x_right);
173		✗	const double shift = (y_right - y_left) / (2.0 * m);
174
175		✗	double x_new = mid - shift;
176		✗	if (x_new <= x_left || x_new >= x_right) {
177			x_new = mid;
178			}
179		✗	return x_new;
180			}
181
182		✗	SizovDGlobalSearchMPI::IntervalChar SizovDGlobalSearchMPI::ComputeLocalBestInterval(double m, int rank,
183			int size) const {
184			IntervalChar res{};
185			res.characteristic = -std::numeric_limits<double>::infinity();
186			res.index = -1;
187
188			const std::size_t n = x_.size();
189		✗	if (n < 2U) {
190		✗	return res;
191			}
192
193		✗	const std::size_t intervals = n - 1U;
194
195			std::size_t begin = 0;
196		✗	std::size_t end = 0;
197			GetChunk(intervals, rank, size, begin, end);
198
199		✗	for (std::size_t k = begin; k < end; ++k) {
200		✗	const std::size_t i = k + 1U;
201		✗	const double c = Characteristic(i, m);
202		✗	if (c > res.characteristic) {
203			res.characteristic = c;
204		✗	res.index = static_cast<int>(i);
205			}
206			}
207
208		✗	return res;
209			}
210
211		✗	int SizovDGlobalSearchMPI::ReduceBestIntervalIndex(const IntervalChar &local, int n, int size) {
212		✗	IntervalChar global = local;
213
214		✗	if (size > 1) {
215		✗	MPI_Allreduce(&local, &global, 1, MPI_DOUBLE_INT, MPI_MAXLOC, MPI_COMM_WORLD);
216			}
217
218		✗	if (global.index < 1 || global.index >= n) {
219		✗	return -1;
220			}
221			return global.index;
222			}
223
224		✗	bool SizovDGlobalSearchMPI::CheckStopByAccuracy(const Problem &p, int best_idx, int rank) const {
225		✗	int flag = 0;
226
227		✗	if (rank == 0) {
228		✗	const auto i = static_cast<std::size_t>(best_idx);
229		✗	const double left = x_[i - 1U];
230		✗	const double right = x_[i];
231		✗	const double width = right - left;
232
233		✗	if (width <= p.accuracy) {
234		✗	flag = 1;
235			}
236			}
237
238		✗	MPI_Bcast(&flag, 1, MPI_INT, 0, MPI_COMM_WORLD);
239		✗	return flag != 0;
240			}
241
242		✗	void SizovDGlobalSearchMPI::BroadcastState(int rank) {
243		✗	int n = 0;
244		✗	if (rank == 0) {
245		✗	n = static_cast<int>(x_.size());
246			}
247
248		✗	MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
249
250		✗	x_.resize(static_cast<std::size_t>(n));
251		✗	y_.resize(static_cast<std::size_t>(n));
252
253		✗	if (n > 0) {
254		✗	MPI_Bcast(x_.data(), n, MPI_DOUBLE, 0, MPI_COMM_WORLD);
255		✗	MPI_Bcast(y_.data(), n, MPI_DOUBLE, 0, MPI_COMM_WORLD);
256			}
257		✗	}
258
259		✗	void SizovDGlobalSearchMPI::BroadcastInsertMsg(InsertMsg &msg, int rank) {
260		✗	MPI_Bcast(&msg.idx, 1, MPI_INT, 0, MPI_COMM_WORLD);
261		✗	MPI_Bcast(&msg.x_new, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD);
262		✗	MPI_Bcast(&msg.y_new, 1, MPI_DOUBLE, 0, MPI_COMM_WORLD);
263
264			(void)rank;
265		✗	}
266
267		✗	void SizovDGlobalSearchMPI::BroadcastNewPoint(int best_idx, double m, const Problem &p, int rank) {
268		✗	InsertMsg msg{};
269
270		✗	if (rank == 0) {
271		✗	const auto i = static_cast<std::size_t>(best_idx);
272
273		✗	const double x_new = NewPoint(i, m);
274		✗	const double y_new = p.func(x_new);
275
276		✗	if (std::isfinite(y_new)) {
277			auto pos = std::ranges::lower_bound(x_, x_new);
278			const std::size_t idx = static_cast<std::size_t>(pos - x_.begin());
279
280		✗	msg.x_new = x_new;
281		✗	msg.y_new = y_new;
282		✗	msg.idx = static_cast<int>(idx);
283
284		✗	x_.insert(pos, x_new);
285		✗	y_.insert(y_.begin() + static_cast<std::ptrdiff_t>(idx), y_new);
286
287		✗	if (y_new < best_y_) {
288		✗	best_x_ = x_new;
289		✗	best_y_ = y_new;
290			}
291			} else {
292		✗	msg.idx = -1;
293			}
294			}
295
296		✗	BroadcastInsertMsg(msg, rank);
297
298		✗	if (rank != 0 && msg.idx >= 0) {
299		✗	const auto idx = static_cast<std::size_t>(msg.idx);
300		✗	if (idx <= x_.size()) {
301		✗	x_.insert(x_.begin() + static_cast<std::ptrdiff_t>(idx), msg.x_new);
302		✗	y_.insert(y_.begin() + static_cast<std::ptrdiff_t>(idx), msg.y_new);
303			}
304			}
305		✗	}
306
307		✗	void SizovDGlobalSearchMPI::BroadcastResult(int rank) {
308		✗	std::array<double, 2> result{};
309		✗	std::array<int, 2> meta{};
310
311		✗	if (rank == 0) {
312		✗	result[0] = best_x_;
313		✗	result[1] = best_y_;
314		✗	meta[0] = iterations_;
315		✗	meta[1] = converged_ ? 1 : 0;
316			}
317
318		✗	MPI_Bcast(result.data(), 2, MPI_DOUBLE, 0, MPI_COMM_WORLD);
319		✗	MPI_Bcast(meta.data(), 2, MPI_INT, 0, MPI_COMM_WORLD);
320
321		✗	best_x_ = result[0];
322		✗	best_y_ = result[1];
323		✗	iterations_ = meta[0];
324		✗	converged_ = (meta[1] != 0);
325		✗	}
326
327		✗	bool SizovDGlobalSearchMPI::RunImpl() {
328			const auto &p = GetInput();
329
330		✗	int rank = 0;
331		✗	int size = 1;
332		✗	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
333		✗	MPI_Comm_size(MPI_COMM_WORLD, &size);
334
335		✗	if (x_.size() < 2U) {
336			return false;
337			}
338
339		✗	double m = EstimateM(p.reliability, rank, size);
340
341		✗	for (int iter = 0; iter < p.max_iterations; ++iter) {
342		✗	iterations_ = iter + 1;
343
344		✗	if ((iter % 10) == 0) {
345		✗	m = EstimateM(p.reliability, rank, size);
346			}
347
348		✗	const int n = static_cast<int>(x_.size());
349		✗	if (n < 2) {
350		✗	converged_ = false;
351		✗	break;
352			}
353
354		✗	const IntervalChar local = ComputeLocalBestInterval(m, rank, size);
355		✗	const int best_idx = ReduceBestIntervalIndex(local, n, size);
356		✗	if (best_idx < 1) {
357		✗	converged_ = false;
358		✗	break;
359			}
360
361		✗	if (CheckStopByAccuracy(p, best_idx, rank)) {
362		✗	if (rank == 0) {
363		✗	converged_ = true;
364			}
365			break;
366			}
367
368		✗	BroadcastNewPoint(best_idx, m, p, rank);
369			}
370
371		✗	BroadcastResult(rank);
372
373		✗	GetOutput() = Solution{
374		✗	.argmin = best_x_,
375		✗	.value = best_y_,
376		✗	.iterations = iterations_,
377		✗	.converged = converged_,
378			};
379		✗	return true;
380			}
381
382		✗	bool SizovDGlobalSearchMPI::PostProcessingImpl() {
383		✗	return true;
384			}
385
386			} // namespace sizov_d_global_search
387