GCC Code Coverage Report

Directory: ./
File: tasks/gasenin_l_djstra/all/src/ops_all.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 57 57 100.0%
Functions: 5 5 100.0%
Branches: 20 28 71.4%
Line Branch Exec Source
1 #include "gasenin_l_djstra/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <omp.h>
5
6 #include <algorithm>
7 #include <array>
8 #include <cstdint>
9 #include <cstdlib>
10 #include <limits>
11 #include <utility>
12 #include <vector>
13
14 #include "gasenin_l_djstra/common/include/common.hpp"
15
16 namespace gasenin_l_djstra {
17 namespace {
18
19 void MinPairImpl(void *in, void *inout, const int *len, MPI_Datatype * /*dtype*/) {
20 auto *a = static_cast<InType *>(in);
21 auto *b = static_cast<InType *>(inout);
22 for (int i = 0; i < *len; i += 2) {
23 if (a[i] < b[i]) {
24 b[i] = a[i];
25 b[i + 1] = a[i + 1];
26 }
27 }
28 }
29
30 void FindThreadLocalMinima(const std::vector<InType> &dist, const std::vector<char> &visited, int local_n, int start_v,
31 InType inf, std::vector<InType> &thread_mins, std::vector<InType> &thread_vertices) {
32 30 #pragma omp parallel default(none) shared(local_n, start_v, dist, visited, thread_mins, thread_vertices, inf)
33 {
34 const int tid = omp_get_thread_num();
35 InType t_min = inf;
36 InType t_v = -1;
37
38 #pragma omp for nowait
39 for (int i = 0; i < local_n; ++i) {
40 if (visited[i] == 0 && dist[i] < t_min) {
41 t_min = dist[i];
42 t_v = start_v + i;
43 }
44 }
45
46 thread_mins[tid] = t_min;
47 thread_vertices[tid] = t_v;
48 }
49 30 }
50
51 std::pair<InType, InType> ReduceThreadMinima(const std::vector<InType> &thread_mins,
52 const std::vector<InType> &thread_vertices, int num_threads, InType inf) {
53 InType local_min = inf;
54 InType local_vertex = -1;
55
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 30 times.
 90 for (int i = 0; i < num_threads; ++i) {
56
2/2
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 39 times.
 60 if (thread_mins[i] < local_min) {
57 local_min = thread_mins[i];
58 21 local_vertex = thread_vertices[i];
59 }
60 }
61 return {local_min, local_vertex};
62 }
63
64 void UpdateLocalDistances(std::vector<InType> &dist, const std::vector<char> &visited, int local_n, int start_v,
65 InType global_vertex, InType global_min) {
66 30 #pragma omp parallel for default(none) shared(local_n, start_v, dist, visited, global_vertex, global_min)
67 for (int i = 0; i < local_n; ++i) {
68 if (visited[i] == 0) {
69 const InType global_i = start_v + i;
70 if (global_i != global_vertex) {
71 const InType weight = std::abs(global_vertex - global_i);
72 const InType new_dist = global_min + weight;
73 dist[i] = std::min(new_dist, dist[i]);
74 }
75 }
76 }
77 }
78
79 // Compute local sum of distances (excluding INF)
80 int64_t ComputeLocalSum(const std::vector<InType> &dist, int local_n, InType inf) {
81 int64_t local_sum = 0;
82 6 #pragma omp parallel for reduction(+ : local_sum) default(none) shared(local_n, dist, inf)
83 for (int i = 0; i < local_n; ++i) {
84 if (dist[i] != inf) {
85 local_sum += dist[i];
86 }
87 }
88 return local_sum;
89 }
90
91 } // namespace
92
93 6 GaseninLDjstraALL::GaseninLDjstraALL(const InType &in) {
94 SetTypeOfTask(GetStaticTypeOfTask());
95 6 GetInput() = in;
96 GetOutput() = 0;
97 6 }
98
99 6 bool GaseninLDjstraALL::ValidationImpl() {
100 6 return GetInput() > 0;
101 }
102
103 6 bool GaseninLDjstraALL::PreProcessingImpl() {
104 6 MPI_Comm_rank(MPI_COMM_WORLD, &rank_);
105 6 MPI_Comm_size(MPI_COMM_WORLD, &size_);
106
107 6 const InType n = GetInput();
108 6 const InType inf = std::numeric_limits<InType>::max();
109
110 6 const int chunk = n / size_;
111 6 const int rem = n % size_;
112
113
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
 6 if (rank_ < rem) {
114 3 local_n_ = chunk + 1;
115 3 start_v_ = rank_ * local_n_;
116 } else {
117 3 local_n_ = chunk;
118 3 start_v_ = (rem * (chunk + 1)) + ((rank_ - rem) * chunk);
119 }
120
121 6 dist_.assign(local_n_, inf);
122 6 visited_.assign(local_n_, 0);
123
124
3/4
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 6 if (0 >= start_v_ && 0 < start_v_ + local_n_) {
125 3 dist_[0 - start_v_] = 0;
126 }
127
128 6 return true;
129 }
130
131 6 bool GaseninLDjstraALL::RunImpl() {
132 6 const InType n = GetInput();
133 6 const InType inf = std::numeric_limits<InType>::max();
134
135 6 std::vector<InType> &dist = dist_;
136 6 std::vector<char> &visited = visited_;
137 6 const int local_n = local_n_;
138 6 const int start_v = start_v_;
139
140 auto min_pair_op_func = [](void *in, void *inout, const int *len, MPI_Datatype *dtype) {
141 MinPairImpl(in, inout, len, dtype);
142 };
143
144 6 MPI_Op min_pair_op = MPI_OP_NULL;
145
146 6 MPI_Op_create(reinterpret_cast<MPI_User_function *>(+min_pair_op_func), 1, &min_pair_op);
147
148 int num_threads = 1;
149 6 #pragma omp parallel default(none) shared(num_threads)
150 {
151 #pragma omp single
152 num_threads = omp_get_num_threads();
153 }
154
155 6 std::vector<InType> thread_mins(num_threads, inf);
156
1/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 6 std::vector<InType> thread_vertices(num_threads, -1);
157
158
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 6 times.
 36 for (int iteration = 0; iteration < n; ++iteration) {
159 FindThreadLocalMinima(dist, visited, local_n, start_v, inf, thread_mins, thread_vertices);
160
161 auto [local_min, local_vertex] = ReduceThreadMinima(thread_mins, thread_vertices, num_threads, inf);
162
163 30 std::array<InType, 2> local_pair = {local_min, local_vertex};
164 30 std::array<InType, 2> global_pair = {inf, -1};
165
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 MPI_Allreduce(local_pair.data(), global_pair.data(), 1, MPI_LONG_LONG_INT, min_pair_op, MPI_COMM_WORLD);
166
167 30 InType global_min = global_pair[0];
168 30 InType global_vertex = global_pair[1];
169
170
1/2
✓ Branch 0 taken 30 times.
✗ Branch 1 not taken.
 30 if (global_vertex == -1) {
171 break;
172 }
173
174
4/4
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 9 times.
✓ Branch 2 taken 15 times.
✓ Branch 3 taken 6 times.
 30 if (global_vertex >= start_v && global_vertex < start_v + local_n) {
175 15 visited[global_vertex - start_v] = 1;
176 }
177
178 UpdateLocalDistances(dist, visited, local_n, start_v, global_vertex, global_min);
179 }
180
181
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Op_free(&min_pair_op);
182
183 6 int64_t local_sum = ComputeLocalSum(dist, local_n, inf);
184
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 MPI_Allreduce(&local_sum, &total_sum_, 1, MPI_INT64_T, MPI_SUM, MPI_COMM_WORLD);
185
186 6 return true;
187 }
188
189 6 bool GaseninLDjstraALL::PostProcessingImpl() {
190 6 GetOutput() = static_cast<OutType>(total_sum_);
191 6 return true;
192 }
193
194 } // namespace gasenin_l_djstra
195