GCC Code Coverage Report

Directory: ./
File: tasks/votincev_d_qsort_batcher/mpi/src/ops_mpi.cpp
Date: 2026-01-10 02:40:41
Exec Total Coverage
Lines: 97 105 92.4%
Functions: 12 13 92.3%
Branches: 57 96 59.4%
Line Branch Exec Source
1 #include "votincev_d_qsort_batcher/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <vector>
7
8 #include "votincev_d_qsort_batcher/common/include/common.hpp"
9
10 namespace votincev_d_qsort_batcher {
11
12
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 VotincevDQsortBatcherMPI::VotincevDQsortBatcherMPI(const InType &in) {
13 SetTypeOfTask(GetStaticTypeOfTask());
14
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 GetInput() = in;
15 20 }
16
17 // убеждаемся, что массив не пустой
18 20 bool VotincevDQsortBatcherMPI::ValidationImpl() {
19 const auto &vec = GetInput();
20 20 return !vec.empty();
21 }
22
23 // препроцессинг (не нужен)
24 20 bool VotincevDQsortBatcherMPI::PreProcessingImpl() {
25 20 return true;
26 }
27
28 // главный MPI метод
29 20 bool VotincevDQsortBatcherMPI::RunImpl() {
30 // получаю кол-во процессов
31 20 int proc_n = 0;
32 20 MPI_Comm_size(MPI_COMM_WORLD, &proc_n);
33
34 // получаю ранг процесса
35 20 int rank = 0;
36 20 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
37
38 // если процесс 1 - то просто как в SEQ
39
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
 20 if (proc_n == 1) {
40 ✗ auto out = GetInput();
41 ✗ if (!out.empty()) {
42 ✗ QuickSort(out.data(), 0, static_cast<int>(out.size()) - 1);
43 }
44 ✗ GetOutput() = out;
45 return true;
46 }
47
48 // размер массива знает только 0-й процесс
49 20 int total_size = 0;
50
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (rank == 0) {
51 10 total_size = static_cast<int>(GetInput().size());
52 }
53
54 // рассылаем размер массива всем процессам
55 20 MPI_Bcast(&total_size, 1, MPI_INT, 0, MPI_COMM_WORLD);
56
57
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 if (total_size == 0) {
58 return true;
59 }
60
61 // вычисление размеров и смещений
62 20 std::vector<int> sizes;
63 20 std::vector<int> offsets;
64
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 ComputeDistribution(proc_n, total_size, sizes, offsets);
65
66 // распределение данных (Scatter)
67
1/4
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 20 std::vector<double> local(sizes[rank]);
68
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 ScatterData(rank, sizes, offsets, local);
69
70 // локальная сортировка
71 // каждый процесс сортирует свой кусок
72
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 if (!local.empty()) {
73
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 QuickSort(local.data(), 0, static_cast<int>(local.size()) - 1);
74 }
75
76 // чет-нечет слияние Бэтчера
77
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 BatcherMergeSort(rank, proc_n, sizes, local);
78
79 // 0й процесс собирает результыт от других процессов
80
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 GatherResult(rank, total_size, sizes, offsets, local);
81
82 return true;
83 }
84
85 20 void VotincevDQsortBatcherMPI::ComputeDistribution(int proc_n, int total_size, std::vector<int> &sizes,
86 std::vector<int> &offsets) {
87 20 int base = total_size / proc_n; // минимальный размер блока
88 20 int extra = total_size % proc_n; // оставшиеся элементы
89
90 20 sizes.resize(proc_n);
91 20 offsets.resize(proc_n);
92
93 // распределяем остаток по первым процессам (процессам с меньшим рангом)
94
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 20 times.
 60 for (int i = 0; i < proc_n; i++) {
95
1/2
✓ Branch 0 taken 40 times.
✗ Branch 1 not taken.
 80 sizes[i] = base + (i < extra ? 1 : 0);
96 }
97
98 // смещения (начальный индекс для каждого блока)
99 20 offsets[0] = 0;
100
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 20 times.
 40 for (int i = 1; i < proc_n; i++) {
101 20 offsets[i] = offsets[i - 1] + sizes[i - 1];
102 }
103 20 }
104
105 20 void VotincevDQsortBatcherMPI::ScatterData(int rank, const std::vector<int> &sizes, const std::vector<int> &offsets,
106 std::vector<double> &local) {
107 // GetInput().data() только для процесса с rank == 0
108
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (rank == 0) {
109 10 MPI_Scatterv(GetInput().data(), sizes.data(), offsets.data(), MPI_DOUBLE, local.data(), sizes[rank], MPI_DOUBLE, 0,
110 MPI_COMM_WORLD);
111 } else {
112 10 MPI_Scatterv(nullptr, sizes.data(), offsets.data(), MPI_DOUBLE, local.data(), sizes[rank], MPI_DOUBLE, 0,
113 MPI_COMM_WORLD);
114 }
115 20 }
116
117 ✗ int VotincevDQsortBatcherMPI::GetPartnerRank(int rank, int proc_n, int phase) {
118 int partner = -1;
119 // Классическая схема Odd-Even Transposition (Batcher-like для P процессов)
120
2/4
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 40 if (phase % 2 == 0) {
121 // Чётная фаза: (0,1), (2,3), (4,5)...
122
2/4
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 20 if (rank % 2 == 0) {
123 10 partner = rank + 1;
124 } else {
125 10 partner = rank - 1;
126 }
127 } else {
128 // Нечётная фаза: (1,2), (3,4), (5,6)...
129
2/4
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 20 if (rank % 2 == 1) {
130 10 partner = rank + 1;
131 } else {
132 10 partner = rank - 1;
133 }
134 }
135
136
2/4
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 40 if (partner < 0 || partner >= proc_n) {
137 ✗ return -1;
138 }
139 return partner;
140 }
141
142 20 void VotincevDQsortBatcherMPI::PerformMergePhase(int rank, int partner, const std::vector<int> &sizes,
143 std::vector<double> &local, std::vector<double> &recv_buf,
144 std::vector<double> &merge_buf) {
145 20 MPI_Sendrecv(local.data(), sizes[rank], MPI_DOUBLE, partner, 0, recv_buf.data(), sizes[partner], MPI_DOUBLE, partner,
146 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
147
148 20 std::merge(local.begin(), local.end(), recv_buf.begin(), recv_buf.begin() + sizes[partner], merge_buf.begin());
149
150 // малые влево, большие вправо
151
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (rank < partner) {
152 // младший процесс забирает начало (наименьшие элементы)
153 10 std::copy(merge_buf.begin(), merge_buf.begin() + sizes[rank], local.begin());
154 } else {
155 // старший процесс забирает конец (наибольшие элементы)
156 10 std::copy(merge_buf.begin() + sizes[partner], merge_buf.begin() + sizes[partner] + sizes[rank], local.begin());
157 }
158 20 }
159
160 20 void VotincevDQsortBatcherMPI::BatcherMergeSort(int rank, int proc_n, const std::vector<int> &sizes,
161 std::vector<double> &local) {
162
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
 20 if (proc_n <= 1) {
163 ✗ return;
164 }
165
166 20 int max_block = *std::ranges::max_element(sizes);
167 20 std::vector<double> recv_buf(max_block);
168
1/4
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 20 std::vector<double> merge_buf(sizes[rank] + max_block);
169
170 // для полной сортировки в схеме Odd-Even требуется P фаз
171
2/2
✓ Branch 0 taken 40 times.
✓ Branch 1 taken 20 times.
 60 for (int phase = 0; phase < proc_n; phase++) {
172 int partner = GetPartnerRank(rank, proc_n, phase);
173
174 if (partner != -1) {
175
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 PerformMergePhase(rank, partner, sizes, local, recv_buf, merge_buf);
176 }
177 }
178 }
179
180 // 0й процесс собирает данные со всех других процессов
181 20 void VotincevDQsortBatcherMPI::GatherResult(int rank, int total_size, const std::vector<int> &sizes,
182 const std::vector<int> &offsets, const std::vector<double> &local) {
183
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 10 times.
 20 if (rank == 0) {
184
1/2
✓ Branch 2 taken 10 times.
✗ Branch 3 not taken.
 10 std::vector<double> result(total_size);
185
186 // 0-й процесс собирает данные
187
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 MPI_Gatherv(local.data(), sizes[rank], MPI_DOUBLE, result.data(), sizes.data(), offsets.data(), MPI_DOUBLE, 0,
188 MPI_COMM_WORLD);
189
190
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 GetOutput() = result;
191 } else {
192 // остальные процессы отправляют свои данные 0-му
193 10 MPI_Gatherv(local.data(), sizes[rank], MPI_DOUBLE, nullptr, nullptr, nullptr, MPI_DOUBLE, 0, MPI_COMM_WORLD);
194 }
195 20 }
196
197 // partition (для qsort)
198 5580 int VotincevDQsortBatcherMPI::Partition(double *arr, int l, int h) {
199 int i = l;
200 int j = h;
201 5580 double pivot = arr[(l + h) / 2];
202
203
2/2
✓ Branch 0 taken 19456 times.
✓ Branch 1 taken 5580 times.
 30616 while (i <= j) {
204
2/2
✓ Branch 0 taken 11390 times.
✓ Branch 1 taken 19456 times.
 30846 while (arr[i] < pivot) {
205 11390 i++;
206 }
207
2/2
✓ Branch 0 taken 11735 times.
✓ Branch 1 taken 19456 times.
 31191 while (arr[j] > pivot) {
208 11735 j--;
209 }
210
211
2/2
✓ Branch 0 taken 693 times.
✓ Branch 1 taken 18763 times.
 19456 if (i <= j) {
212 std::swap(arr[i], arr[j]);
213 18763 i++;
214 18763 j--;
215 }
216 }
217 // i — это граница следующего правого подмассива
218 5580 return i;
219 }
220
221 // итеративная qsort
222 20 void VotincevDQsortBatcherMPI::QuickSort(double *arr, int left, int right) {
223
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 std::vector<int> stack;
224
225 stack.push_back(left);
226 stack.push_back(right);
227
228
2/2
✓ Branch 0 taken 5580 times.
✓ Branch 1 taken 20 times.
 5600 while (!stack.empty()) {
229
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5580 times.
 5580 int h = stack.back();
230 stack.pop_back();
231 5580 int l = stack.back();
232 stack.pop_back();
233
234
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5580 times.
 5580 if (l >= h) {
235 ✗ continue;
236 }
237
238 // вызываю Partition для разделения массива
239 5580 int p = Partition(arr, l, h);
240 // p - это i после Partition. j находится на p-1 или p-2.
241
242 // p - начало правого подмассива (i)
243 // j - конец левого подмассива (j после Partition)
244
245 // пересчитываю l и h для стека, используя внутренние границы Partition
246 5580 int l_end = p - 1; // конец левого подмассива
247 5580 int r_start = p; // начало правого подмассива
248
249 // если левый подмассив существует
250
2/2
✓ Branch 0 taken 3091 times.
✓ Branch 1 taken 2489 times.
 5580 if (l < l_end) {
251 stack.push_back(l);
252 stack.push_back(l_end);
253 }
254
255 // если правый подмассив существует
256
2/2
✓ Branch 0 taken 2469 times.
✓ Branch 1 taken 3111 times.
 5580 if (r_start < h) {
257 stack.push_back(r_start);
258 stack.push_back(h);
259 }
260 }
261 20 }
262
263 // здесь ничего не надо делать
264 20 bool VotincevDQsortBatcherMPI::PostProcessingImpl() {
265 20 return true;
266 }
267
268 } // namespace votincev_d_qsort_batcher
269