GCC Code Coverage Report

Directory: ./
File: tasks/nalitov_d_dijkstras_algorithm/all/src/ops_all.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 86 89 96.6%
Functions: 7 7 100.0%
Branches: 55 80 68.8%
Line Branch Exec Source
1 #include "nalitov_d_dijkstras_algorithm/all/include/ops_all.hpp"
2
3 #include <mpi.h>
4 #include <omp.h>
5
6 #include <algorithm>
7 #include <array>
8 #include <atomic>
9 #include <cstddef>
10 #include <cstdint>
11 #include <utility>
12 #include <vector>
13
14 #include "nalitov_d_dijkstras_algorithm/common/include/common.hpp"
15
16 namespace nalitov_d_dijkstras_algorithm {
17
18 namespace {
19
20 struct NodePayload {
21 int cost;
22 int vtx;
23 };
24
25 30 NodePayload FindLocalMin(const std::vector<Cost> &dist, const std::vector<char> &visited, int start_idx, int count,
26 int threads) {
27 int best_c = kInf;
28 int best_v = -1;
29
30 30 #pragma omp parallel num_threads(threads) default(none) shared(dist, visited, start_idx, count, best_c, best_v)
31 {
32 int thr_c = kInf;
33 int thr_v = -1;
34
35 #pragma omp for nowait
36 for (int i = 0; i < count; ++i) {
37 if (visited[static_cast<size_t>(i)] == 0 && dist[static_cast<size_t>(i)] < thr_c) {
38 thr_c = dist[static_cast<size_t>(i)];
39 thr_v = start_idx + i;
40 }
41 }
42
43 #pragma omp critical
44 {
45 if (thr_c < best_c || (thr_c == best_c && thr_v != -1 && (best_v == -1 || thr_v < best_v))) {
46 best_c = thr_c;
47 best_v = thr_v;
48 }
49 }
50 }
51
52 30 return {.cost = best_c, .vtx = best_v};
53 }
54
55 24 void UpdateNeighborDistance(int target, int weight, int global_cost, int l_start, int l_count,
56 std::vector<Cost> &local_dist, const std::vector<char> &local_visited) {
57
4/4
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 12 times.
✓ Branch 3 taken 8 times.
 24 if (target >= l_start && target < l_start + l_count) {
58 12 int local_idx = target - l_start;
59
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 if (local_visited[static_cast<size_t>(local_idx)] == 0) {
60 12 int new_dist = global_cost + weight;
61 std::atomic_ref<int> target_ref(local_dist[static_cast<size_t>(local_idx)]);
62
63 int old_dist = target_ref.load(std::memory_order_relaxed);
64
1/2
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
 12 while (new_dist < old_dist) {
65
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
 12 if (target_ref.compare_exchange_weak(old_dist, new_dist, std::memory_order_relaxed)) {
66 break;
67 }
68 }
69 }
70 }
71 24 }
72
73 void RelaxNeighbors(const std::vector<std::pair<int, int>> &neighbors, const NodePayload &global, int l_start,
74 int l_count, std::vector<Cost> &local_dist, const std::vector<char> &local_visited, int threads) {
75 const size_t sz = neighbors.size();
76 30 #pragma omp parallel for num_threads(threads) default(none) \
77 shared(neighbors, sz, global, l_start, l_count, local_dist, local_visited)
78 for (size_t i = 0; i < sz; ++i) {
79 int target = neighbors[i].first;
80 int weight = neighbors[i].second;
81 UpdateNeighborDistance(target, weight, global.cost, l_start, l_count, local_dist, local_visited);
82 }
83 30 }
84
85 int64_t CalculateLocalSum(const std::vector<Cost> &local_dist, int l_count, int threads) {
86 int64_t local_sum = 0;
87 8 #pragma omp parallel for num_threads(threads) default(none) reduction(+ : local_sum) shared(local_dist, l_count)
88 for (int i = 0; i < l_count; ++i) {
89 if (local_dist[static_cast<size_t>(i)] != kInf) {
90 local_sum += local_dist[static_cast<size_t>(i)];
91 }
92 }
93 return local_sum;
94 }
95
96 } // namespace
97
98
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 NalitovDDijkstrasAlgorithmALL::NalitovDDijkstrasAlgorithmALL(const InType &in) {
99 SetTypeOfTask(GetStaticTypeOfTask());
100 GetInput() = in;
101 8 GetOutput() = 0;
102 8 }
103
104 8 bool NalitovDDijkstrasAlgorithmALL::ValidationImpl() {
105 8 MPI_Comm_rank(MPI_COMM_WORLD, &rank_);
106 8 int is_valid = 1;
107
108
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (rank_ == 0) {
109 const auto &in = GetInput();
110
3/6
✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 4 times.
 4 if (in.n <= 0 || in.n > 10000 || in.source < 0 || in.source >= in.n) {
111 ✗ is_valid = 0;
112 } else {
113
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 4 times.
 16 for (const auto &a : in.arcs) {
114
5/10
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 12 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 12 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 12 times.
 12 if (a.from < 0 || a.to < 0 || a.from >= in.n || a.to >= in.n || a.weight < 0) {
115 ✗ is_valid = 0;
116 ✗ break;
117 }
118 }
119 }
120 }
121
122 8 MPI_Bcast(&is_valid, 1, MPI_INT, 0, MPI_COMM_WORLD);
123 8 return is_valid == 1;
124 }
125
126 8 bool NalitovDDijkstrasAlgorithmALL::PreProcessingImpl() {
127 8 MPI_Comm_rank(MPI_COMM_WORLD, &rank_);
128 8 MPI_Comm_size(MPI_COMM_WORLD, &size_);
129
130 8 std::array<int, 3> meta{};
131
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (rank_ == 0) {
132 4 meta[0] = GetInput().n;
133 4 meta[1] = GetInput().source;
134 4 meta[2] = static_cast<int>(GetInput().arcs.size());
135 }
136 8 MPI_Bcast(meta.data(), 3, MPI_INT, 0, MPI_COMM_WORLD);
137
138 8 n_ = meta[0];
139 8 source_ = meta[1];
140 8 int arc_count = meta[2];
141
142 8 std::vector<int> arc_buf(static_cast<size_t>(arc_count) * 3);
143
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (rank_ == 0) {
144
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 4 times.
 16 for (int i = 0; i < arc_count; ++i) {
145 12 size_t idx = static_cast<size_t>(i) * 3;
146 12 arc_buf[idx + 0] = GetInput().arcs[i].from;
147 12 arc_buf[idx + 1] = GetInput().arcs[i].to;
148 12 arc_buf[idx + 2] = GetInput().arcs[i].weight;
149 }
150 }
151
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
 8 if (arc_count > 0) {
152
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 MPI_Bcast(arc_buf.data(), arc_count * 3, MPI_INT, 0, MPI_COMM_WORLD);
153 }
154
155
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 graph_.assign(n_, {});
156
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
 32 for (int i = 0; i < arc_count; ++i) {
157
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 size_t idx = static_cast<size_t>(i) * 3;
158
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 graph_[static_cast<size_t>(arc_buf[idx])].emplace_back(arc_buf[idx + 1], arc_buf[idx + 2]);
159 }
160
161 8 const int base = n_ / size_;
162 8 const int rem = n_ % size_;
163
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 1 times.
 8 local_start_ = (rank_ * base) + std::min(rank_, rem);
164
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 1 times.
 8 local_count_ = base + (rank_ < rem ? 1 : 0);
165
166
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 local_dist_.assign(local_count_, kInf);
167
1/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 8 local_visited_.assign(local_count_, 0);
168
169
3/4
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
 8 if (source_ >= local_start_ && source_ < local_start_ + local_count_) {
170 4 local_dist_[source_ - local_start_] = 0;
171 }
172
173 8 return true;
174 }
175
176 8 bool NalitovDDijkstrasAlgorithmALL::RunImpl() {
177 8 const int threads = omp_get_max_threads();
178 8 const int l_start = local_start_;
179 8 const int l_count = local_count_;
180 8 const int n_total = n_;
181
182 bool all_done = false;
183
184
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 8 times.
 38 for (int step = 0; step < n_total; ++step) {
185 30 NodePayload local = FindLocalMin(local_dist_, local_visited_, l_start, l_count, threads);
186
187 30 NodePayload global{};
188 30 MPI_Allreduce(&local, &global, 1, MPI_2INT, MPI_MINLOC, MPI_COMM_WORLD);
189
190
2/4
✓ Branch 0 taken 30 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 30 times.
✗ Branch 3 not taken.
 30 if (global.vtx == -1 || global.cost == kInf) {
191 all_done = true;
192 }
193
194
1/2
✓ Branch 0 taken 30 times.
✗ Branch 1 not taken.
 30 if (!all_done) {
195
4/4
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 15 times.
✓ Branch 3 taken 7 times.
 30 if (global.vtx >= l_start && global.vtx < l_start + l_count) {
196 15 local_visited_[static_cast<size_t>(global.vtx - l_start)] = 1;
197 }
198
199 30 RelaxNeighbors(graph_[static_cast<size_t>(global.vtx)], global, l_start, l_count, local_dist_, local_visited_,
200 threads);
201 }
202 }
203
204 8 int64_t local_sum = CalculateLocalSum(local_dist_, l_count, threads);
205 8 int64_t global_sum = 0;
206 8 MPI_Reduce(&local_sum, &global_sum, 1, MPI_INT64_T, MPI_SUM, 0, MPI_COMM_WORLD);
207
208
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (rank_ == 0) {
209 4 GetOutput() = global_sum;
210 }
211
212 8 return true;
213 }
214
215 8 bool NalitovDDijkstrasAlgorithmALL::PostProcessingImpl() {
216 8 OutType result = GetOutput();
217 8 MPI_Bcast(&result, 1, MPI_INT64_T, 0, MPI_COMM_WORLD);
218
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 if (rank_ != 0) {
219 4 GetOutput() = result;
220 }
221 8 return true;
222 }
223
224 } // namespace nalitov_d_dijkstras_algorithm
225