GCC Code Coverage Report

Directory: ./
File: tasks/zyazeva_s_gauss_jordan_elimination/mpi/src/ops_mpi.cpp
Date: 2026-01-27 01:59:34
Exec Total Coverage
Lines: 140 143 97.9%
Functions: 11 11 100.0%
Branches: 91 130 70.0%
Line Branch Exec Source
1 #include "zyazeva_s_gauss_jordan_elimination/mpi/include/ops_mpi.hpp"
2
3 #include <mpi.h>
4
5 #include <algorithm>
6 #include <climits>
7 #include <cmath>
8 #include <cstddef>
9 #include <utility>
10 #include <vector>
11
12 #include "zyazeva_s_gauss_jordan_elimination/common/include/common.hpp"
13
14 namespace zyazeva_s_gauss_jordan_elimination {
15
16
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 ZyazevaSGaussJordanElMPI::ZyazevaSGaussJordanElMPI(const InType &in) {
17 SetTypeOfTask(GetStaticTypeOfTask());
18
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 InType temp = in;
19 14 GetInput() = std::move(temp);
20 14 }
21
22 14 bool ZyazevaSGaussJordanElMPI::ValidationImpl() {
23 14 int rank = 0;
24 14 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
25
26 14 bool is_valid = false;
27
28
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 if (rank == 0) {
29 const auto &matrix = GetInput();
30
31
1/2
✓ Branch 0 taken 7 times.
✗ Branch 1 not taken.
 7 if (matrix.empty()) {
32 is_valid = false;
33 } else {
34 7 int n = static_cast<int>(matrix.size());
35 7 is_valid = true;
36
37
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 7 times.
 26 for (const auto &row : matrix) {
38
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 19 times.
 19 if (row.size() != (static_cast<std::size_t>(n) + 1)) {
39 ✗ is_valid = false;
40 ✗ break;
41 }
42 }
43 }
44 }
45
46 14 MPI_Bcast(&is_valid, 1, MPI_C_BOOL, 0, MPI_COMM_WORLD);
47 14 return is_valid;
48 }
49
50 14 bool ZyazevaSGaussJordanElMPI::PreProcessingImpl() {
51 14 GetOutput() = std::vector<float>();
52 14 return true;
53 }
54 namespace {
55
56 14 std::vector<int> DistributeRows(int size, int n) {
57 14 std::vector<int> rows(size);
58 14 int base = n / size;
59 14 int extra = n % size;
60
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 14 times.
 42 for (int proc = 0; proc < size; ++proc) {
61
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 10 times.
 46 rows[proc] = base + (proc < extra ? 1 : 0);
62 }
63 14 return rows;
64 }
65
66 void CalculateScatterParameters(int size, const std::vector<int> &rows, int width, std::vector<int> &send_counts,
67 std::vector<int> &displs) {
68 int offset_rows = 0;
69
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 14 times.
 42 for (int proc = 0; proc < size; ++proc) {
70 28 send_counts[proc] = rows[proc] * width;
71 28 displs[proc] = offset_rows * width;
72 28 offset_rows += rows[proc];
73 }
74 }
75
76 void ScatterMatrix(int rank, const std::vector<double> &flat, const std::vector<int> &send_counts,
77 const std::vector<int> &displs, std::vector<double> &local_matrix, int local_rows, int width) {
78
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 MPI_Scatterv(rank == 0 ? flat.data() : nullptr, send_counts.data(), displs.data(), MPI_DOUBLE, local_matrix.data(),
79 local_rows * width, MPI_DOUBLE, 0, MPI_COMM_WORLD);
80 14 }
81
82 int CalculateStartRow(int rank, const std::vector<int> &rows) {
83 int start_row = 0;
84
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 14 times.
 21 for (int proc = 0; proc < rank; ++proc) {
85 7 start_row += rows[proc];
86 }
87 return start_row;
88 }
89
90 int FindRowOwner(int row_index, int size, const std::vector<int> &rows) {
91 int owner = 0;
92 int acc = 0;
93
2/4
✓ Branch 0 taken 52 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 52 times.
✗ Branch 3 not taken.
 104 for (int proc = 0; proc < size; ++proc) {
94
6/8
✓ Branch 0 taken 52 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 14 times.
✓ Branch 3 taken 38 times.
✓ Branch 4 taken 52 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 14 times.
✓ Branch 7 taken 38 times.
 104 if (row_index >= acc && row_index < acc + rows[proc]) {
95 owner = proc;
96 break;
97 }
98 28 acc += rows[proc];
99 }
100 return owner;
101 }
102
103 int FindLocalPivotRow(int k, int start_row, int local_rows, const std::vector<double> &local_matrix, int width,
104 double k_eps) {
105 int local_found = INT_MAX;
106
2/2
✓ Branch 0 taken 51 times.
✓ Branch 1 taken 16 times.
 67 for (int i = 0; i < local_rows; ++i) {
107 51 int gi = start_row + i;
108
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 32 times.
 51 if (gi < k) {
109 19 continue;
110 }
111 32 if (std::fabs(local_matrix[(static_cast<std::size_t>(i) * static_cast<std::size_t>(width)) +
112
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 22 times.
 32 static_cast<std::size_t>(k)]) > k_eps) {
113 local_found = gi;
114 break;
115 }
116 }
117 return local_found;
118 }
119
120 int FindGlobalPivotRow(int local_found) {
121 38 int global_found = 0;
122
1/2
✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
 38 MPI_Allreduce(&local_found, &global_found, 1, MPI_INT, MPI_MIN, MPI_COMM_WORLD);
123 38 return global_found;
124 }
125
126 void SwapRowsSameOwner(int rank, int owner, int k, int global_found, int start_row, std::vector<double> &local_matrix,
127 int width) {
128 38 if (rank == owner) {
129 19 int lk = k - start_row;
130 19 int lf = global_found - start_row;
131
2/2
✓ Branch 0 taken 76 times.
✓ Branch 1 taken 19 times.
 95 for (int j = 0; j < width; ++j) {
132 std::swap(
133 76 local_matrix[(static_cast<std::size_t>(lk) * static_cast<std::size_t>(width)) + static_cast<std::size_t>(j)],
134 76 local_matrix[(static_cast<std::size_t>(lf) * static_cast<std::size_t>(width)) + static_cast<std::size_t>(j)]);
135 }
136 }
137 }
138
139 38 void NormalizePivotRow(int rank, int owner, int k, int start_row, std::vector<double> &local_matrix,
140 std::vector<double> &pivot, int width, double k_eps) {
141
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 19 times.
 38 if (rank == owner) {
142 19 int lk = k - start_row;
143 double piv =
144
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 19 times.
 19 local_matrix[(static_cast<std::size_t>(lk) * static_cast<std::size_t>(width)) + static_cast<std::size_t>(k)];
145
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 19 times.
 19 if (std::fabs(piv) < k_eps) {
146 ✗ MPI_Abort(MPI_COMM_WORLD, 1);
147 }
148
2/2
✓ Branch 0 taken 76 times.
✓ Branch 1 taken 19 times.
 95 for (int j = 0; j < width; ++j) {
149 76 pivot[j] =
150 76 local_matrix[(static_cast<std::size_t>(lk) * static_cast<std::size_t>(width)) + static_cast<std::size_t>(j)] /
151 piv;
152 }
153 using DiffT = std::vector<double>::difference_type;
154
1/2
✓ Branch 0 taken 19 times.
✗ Branch 1 not taken.
 19 std::ranges::copy(pivot, local_matrix.begin() + (static_cast<DiffT>(lk) * static_cast<DiffT>(width)));
155 }
156
157 38 MPI_Bcast(pivot.data(), width, MPI_DOUBLE, owner, MPI_COMM_WORLD);
158 38 }
159
160 38 void EliminateColumn(int k, int start_row, int local_rows, std::vector<double> &local_matrix,
161 const std::vector<double> &pivot, int width) {
162
2/2
✓ Branch 0 taken 57 times.
✓ Branch 1 taken 38 times.
 95 for (int i = 0; i < local_rows; ++i) {
163 57 int gi = start_row + i;
164
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 38 times.
 57 if (gi == k) {
165 19 continue;
166 }
167 double f =
168 38 local_matrix[(static_cast<std::size_t>(i) * static_cast<std::size_t>(width)) + static_cast<std::size_t>(k)];
169
2/2
✓ Branch 0 taken 162 times.
✓ Branch 1 taken 38 times.
 200 for (int j = 0; j < width; ++j) {
170 162 local_matrix[(static_cast<std::size_t>(i) * static_cast<std::size_t>(width)) + static_cast<std::size_t>(j)] -=
171 162 f * pivot[j];
172 }
173 }
174 38 }
175
176 14 std::vector<double> ExtractLocalSolution(int local_rows, const std::vector<double> &local_matrix, int width, int n) {
177 14 std::vector<double> local_solution(local_rows);
178
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 14 times.
 33 for (int i = 0; i < local_rows; ++i) {
179 19 local_solution[i] =
180 19 local_matrix[(static_cast<std::size_t>(i) * static_cast<std::size_t>(width)) + static_cast<std::size_t>(n)];
181 }
182 14 return local_solution;
183 }
184
185 14 std::vector<double> GatherSolutions(int rank, int size, const std::vector<int> &rows,
186 const std::vector<double> &local_solution, int n) {
187 14 std::vector<int> sol_counts(size);
188
1/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 14 std::vector<int> sol_displs(size);
189
190 int off = 0;
191
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 14 times.
 42 for (int proc = 0; proc < size; ++proc) {
192 28 sol_counts[proc] = rows[proc];
193 28 sol_displs[proc] = off;
194 28 off += sol_counts[proc];
195 }
196
197 14 std::vector<double> solution;
198
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 if (rank == 0) {
199
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 solution.resize(static_cast<std::size_t>(n));
200 }
201
202
3/4
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
✓ Branch 3 taken 14 times.
✗ Branch 4 not taken.
 21 MPI_Gatherv(local_solution.data(), static_cast<int>(local_solution.size()), MPI_DOUBLE,
203 rank == 0 ? solution.data() : nullptr, sol_counts.data(), sol_displs.data(), MPI_DOUBLE, 0,
204 MPI_COMM_WORLD);
205
206 14 return solution;
207 }
208
209 14 bool SetFinalOutput(int rank, const std::vector<double> &solution, std::vector<float> &output_ref) {
210
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 if (rank == 0) {
211 7 std::vector<float> final_solution(solution.size());
212
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 7 times.
 26 for (std::size_t i = 0; i < solution.size(); ++i) {
213 19 final_solution[i] = static_cast<float>(solution[i]);
214 }
215
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 output_ref = final_solution;
216 }
217 14 return true;
218 }
219
220 } // namespace
221
222 14 bool ZyazevaSGaussJordanElMPI::RunImpl() {
223 14 int rank = 0;
224 14 int size = 0;
225 14 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
226 14 MPI_Comm_size(MPI_COMM_WORLD, &size);
227
228 const auto &input = GetInput();
229
230 14 int n = 0;
231
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 if (rank == 0) {
232 7 n = static_cast<int>(input.size());
233 }
234 static_cast<void>(input);
235 14 MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
236
237 14 const int width = n + 1;
238
239 14 std::vector<double> flat(static_cast<std::size_t>(n) * static_cast<std::size_t>(width));
240
241
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 if (rank == 0) {
242
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 7 times.
 26 for (int i = 0; i < n; ++i) {
243
2/2
✓ Branch 0 taken 76 times.
✓ Branch 1 taken 19 times.
 95 for (int j = 0; j < width; ++j) {
244 76 flat[(static_cast<std::size_t>(i) * static_cast<std::size_t>(width)) + static_cast<std::size_t>(j)] =
245 76 static_cast<double>(input[static_cast<std::size_t>(i)][static_cast<std::size_t>(j)]);
246 }
247 }
248 }
249
250
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 MPI_Bcast(flat.data(), n * width, MPI_DOUBLE, 0, MPI_COMM_WORLD);
251
252
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 std::vector<int> rows = DistributeRows(size, n);
253
254
1/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 14 std::vector<int> send_counts(size);
255
1/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 14 std::vector<int> displs(size);
256 14 CalculateScatterParameters(size, rows, width, send_counts, displs);
257
258
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 int local_rows = rows[rank];
259
1/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 14 std::vector<double> local_matrix(static_cast<std::size_t>(local_rows) * width);
260
261
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 ScatterMatrix(rank, flat, send_counts, displs, local_matrix, local_rows, width);
262
263 14 int start_row = CalculateStartRow(rank, rows);
264
265 const double k_eps = 1e-12;
266
1/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 14 std::vector<double> pivot(width);
267
268
2/2
✓ Branch 0 taken 38 times.
✓ Branch 1 taken 14 times.
 52 for (int k = 0; k < n; ++k) {
269 38 int owner = FindRowOwner(k, size, rows);
270
271 int local_found = FindLocalPivotRow(k, start_row, local_rows, local_matrix, width, k_eps);
272 38 int global_found = FindGlobalPivotRow(local_found);
273
274 38 int owner2 = FindRowOwner(global_found, size, rows);
275
276
1/2
✓ Branch 0 taken 38 times.
✗ Branch 1 not taken.
 38 if (owner == owner2) {
277
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 19 times.
 38 SwapRowsSameOwner(rank, owner, k, global_found, start_row, local_matrix, width);
278 }
279
280
1/2
✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
 38 NormalizePivotRow(rank, owner, k, start_row, local_matrix, pivot, width, k_eps);
281 38 EliminateColumn(k, start_row, local_rows, local_matrix, pivot, width);
282 }
283
284
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 std::vector<double> local_solution = ExtractLocalSolution(local_rows, local_matrix, width, n);
285
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 std::vector<double> solution = GatherSolutions(rank, size, rows, local_solution, n);
286
287 auto &output_ref = const_cast<std::vector<float> &>(GetOutput());
288
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 28 return SetFinalOutput(rank, solution, output_ref);
289 }
290
291 14 bool ZyazevaSGaussJordanElMPI::PostProcessingImpl() {
292 14 int rank = 0;
293 14 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
294
295
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 7 times.
 14 if (rank == 0) {
296 7 return !GetOutput().empty();
297 }
298 return true;
299 }
300
301 } // namespace zyazeva_s_gauss_jordan_elimination
302