GCC Code Coverage Report

Line	Branch	Exec	Source
1			#include "buzulukskiy_d_sort_batcher/mpi/include/ops_mpi.hpp"
2
3			#include <mpi.h>
4
5			#include <algorithm>
6			#include <climits>
7			#include <cstddef>
8			#include <iterator>
9			#include <tuple>
10			#include <utility>
11			#include <vector>
12
13			#include "buzulukskiy_d_sort_batcher/common/include/common.hpp"
14
15			namespace buzulukskiy_d_sort_batcher {
16			namespace {
17			constexpr int kRadixBase = 10;
18			constexpr int kMaxIterations = 100;
19
20		✗	void RadixSortUnsigned(std::vector<int> &arr) {
21		✗	if (arr.empty()) {
22		✗	return;
23			}
24		✗	const int max_val = *std::ranges::max_element(arr);
25		✗	std::vector<int> output(arr.size());
26		✗	for (int exp = 1; max_val / exp > 0; exp *= kRadixBase) {
27		✗	std::vector<int> count(static_cast<std::size_t>(kRadixBase), 0);
28		✗	for (const int val : arr) {
29		✗	count[static_cast<std::size_t>((val / exp) % kRadixBase)]++;
30			}
31		✗	for (std::size_t i = 1; i < static_cast<std::size_t>(kRadixBase); ++i) {
32		✗	count[i] += count[i - 1];
33			}
34		✗	for (std::size_t i = arr.size(); i-- > 0;) {
35		✗	const int digit = (arr[i] / exp) % kRadixBase;
36		✗	output[--count[static_cast<std::size_t>(digit)]] = arr[i];
37			}
38			arr.swap(output);
39			}
40			}
41
42		✗	void RadixSortLSD(std::vector<int> &data) {
43		✗	if (data.empty()) {
44		✗	return;
45			}
46		✗	std::vector<int> positives;
47		✗	std::vector<int> negatives;
48		✗	for (const int val : data) {
49		✗	if (val < 0) {
50		✗	negatives.push_back(val == INT_MIN ? INT_MAX : -val);
51			} else {
52			positives.push_back(val);
53			}
54			}
55		✗	if (!positives.empty()) {
56		✗	RadixSortUnsigned(positives);
57			}
58		✗	if (!negatives.empty()) {
59		✗	RadixSortUnsigned(negatives);
60			std::ranges::reverse(negatives);
61		✗	for (int &v_ref : negatives) {
62		✗	v_ref = (v_ref == INT_MAX ? INT_MIN : -v_ref);
63			}
64			}
65			data.clear();
66		✗	data.insert(data.end(), negatives.begin(), negatives.end());
67		✗	data.insert(data.end(), positives.begin(), positives.end());
68			}
69
70		✗	void ExchangeAndMerge(std::vector<int> &local, int partner, const std::vector<int> &counts, int rank) {
71		✗	if (partner < 0 || std::cmp_greater_equal(partner, counts.size())) {
72		✗	return;
73			}
74		✗	std::vector<int> remote(static_cast<std::size_t>(counts[static_cast<std::size_t>(partner)]));
75		✗	MPI_Sendrecv(local.data(), static_cast<int>(local.size()), MPI_INT, partner, 0, remote.data(),
76			static_cast<int>(remote.size()), MPI_INT, partner, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
77		✗	std::vector<int> combined;
78		✗	combined.reserve(local.size() + remote.size());
79		✗	std::ranges::merge(local, remote, std::back_inserter(combined));
80		✗	const auto my_size = static_cast<std::size_t>(counts[static_cast<std::size_t>(rank)]);
81		✗	if (rank < partner) {
82		✗	local.assign(combined.begin(), combined.begin() + static_cast<std::ptrdiff_t>(my_size));
83			} else {
84		✗	local.assign(combined.end() - static_cast<std::ptrdiff_t>(my_size), combined.end());
85			}
86			}
87
88		✗	void BatcherStep(int i, int j, int k, int phase_step, int rank, int size, std::vector<int> &local,
89			const std::vector<int> &counts) {
90		✗	const int r1 = i + j;
91		✗	const int r2 = i + j + k;
92		✗	if (r2 < size && (r1 / (phase_step * 2)) == (r2 / (phase_step * 2))) {
93		✗	if (rank == r1) {
94		✗	ExchangeAndMerge(local, r2, counts, rank);
95		✗	} else if (rank == r2) {
96		✗	ExchangeAndMerge(local, r1, counts, rank);
97			}
98			}
99		✗	}
100
101		✗	void BatcherInner(int k, int phase_step, int rank, int size, std::vector<int> &local, const std::vector<int> &counts) {
102		✗	for (int j = k % phase_step; j + k < size; j += 2 * k) {
103		✗	for (int i = 0; i < k; ++i) {
104		✗	BatcherStep(i, j, k, phase_step, rank, size, local, counts);
105			}
106			}
107		✗	}
108
109		✗	void BatcherNetworkPhase(std::vector<int> &local, int rank, int size, const std::vector<int> &counts) {
110			// Исправлено: p -> phase_step (длина имени)
111		✗	for (int phase_step = 1; phase_step < size; phase_step <<= 1) {
112		✗	for (int k = phase_step; k > 0; k >>= 1) {
113		✗	BatcherInner(k, phase_step, rank, size, local, counts);
114		✗	MPI_Barrier(MPI_COMM_WORLD);
115			}
116			}
117		✗	}
118
119		✗	void BatcherStabilizationPhase(std::vector<int> &local, int rank, int size, const std::vector<int> &counts) {
120			const int step_limit = std::min(size, kMaxIterations);
121		✗	for (int step_idx = 0; step_idx < step_limit; ++step_idx) {
122		✗	bool even_step = (step_idx % 2 == 0);
123		✗	bool even_rank = (rank % 2 == 0);
124		✗	int partner = (even_step == even_rank) ? rank + 1 : rank - 1;
125		✗	if (partner >= 0 && partner < size) {
126		✗	ExchangeAndMerge(local, partner, counts, rank);
127			}
128		✗	MPI_Barrier(MPI_COMM_WORLD);
129			}
130		✗	}
131
132		✗	std::tuple<std::vector<int>, std::vector<int>, std::size_t> CalculateDistribution(int n, int size, int rank) {
133		✗	std::vector<int> counts(static_cast<std::size_t>(size), 0);
134		✗	std::vector<int> displs(static_cast<std::size_t>(size), 0);
135		✗	int base = n / size;
136		✗	int rem = n % size;
137			int offset = 0;
138		✗	for (int i = 0; i < size; ++i) {
139		✗	counts[static_cast<std::size_t>(i)] = base + (i < rem ? 1 : 0);
140		✗	displs[static_cast<std::size_t>(i)] = offset;
141		✗	offset += counts[static_cast<std::size_t>(i)];
142			}
143		✗	return {counts, displs, static_cast<std::size_t>(counts[static_cast<std::size_t>(rank)])};
144			}
145			} // namespace
146
147		✗	BuzulukskiyDSortBatcherMPI::BuzulukskiyDSortBatcherMPI(const InType &in) : BaseTask() {
148			SetTypeOfTask(GetStaticTypeOfTask());
149		✗	GetInput() = in;
150		✗	}
151
152		✗	bool BuzulukskiyDSortBatcherMPI::ValidationImpl() {
153		✗	return true;
154			}
155		✗	bool BuzulukskiyDSortBatcherMPI::PreProcessingImpl() {
156		✗	return true;
157			}
158		✗	bool BuzulukskiyDSortBatcherMPI::PostProcessingImpl() {
159		✗	return true;
160			}
161
162		✗	bool BuzulukskiyDSortBatcherMPI::RunImpl() {
163		✗	int rank = 0;
164		✗	int size = 0;
165		✗	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
166		✗	MPI_Comm_size(MPI_COMM_WORLD, &size);
167		✗	int n = (rank == 0) ? static_cast<int>(GetInput().size()) : 0;
168		✗	MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
169		✗	if (n == 0) {
170		✗	if (rank == 0) {
171		✗	GetOutput() = InType();
172			}
173		✗	return true;
174			}
175		✗	auto [counts, displs, local_size] = CalculateDistribution(n, size, rank);
176		✗	std::vector<int> local(local_size);
177		✗	MPI_Scatterv(rank == 0 ? GetInput().data() : nullptr, counts.data(), displs.data(), MPI_INT, local.data(),
178			static_cast<int>(local_size), MPI_INT, 0, MPI_COMM_WORLD);
179		✗	if (!local.empty()) {
180		✗	RadixSortLSD(local);
181			}
182		✗	BatcherNetworkPhase(local, rank, size, counts);
183		✗	BatcherStabilizationPhase(local, rank, size, counts);
184		✗	std::vector<int> res(static_cast<std::size_t>(n));
185		✗	MPI_Allgatherv(local.data(), static_cast<int>(local.size()), MPI_INT, res.data(), counts.data(), displs.data(),
186			MPI_INT, MPI_COMM_WORLD);
187			GetOutput() = std::move(res);
188			return true;
189			}
190			} // namespace buzulukskiy_d_sort_batcher
191