GCC Code Coverage Report

Directory: ./
File: tasks/kichanova_k_lin_system_by_conjug_grad/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 140 147 95.2%
Functions: 21 21 100.0%
Branches: 100 164 61.0%
Line Branch Exec Source
1 #include "kichanova_k_lin_system_by_conjug_grad/stl/include/ops_stl.hpp"
2
3 #include <cmath>
4 #include <cstddef>
5 #include <functional>
6 #include <future>
7 #include <mutex>
8 #include <queue>
9 #include <stdexcept>
10 #include <thread>
11 #include <utility>
12 #include <vector>
13
14 #include "kichanova_k_lin_system_by_conjug_grad/common/include/common.hpp"
15 #include "util/include/util.hpp"
16
17 namespace kichanova_k_lin_system_by_conjug_grad {
18
19 namespace {
20
21 class ThreadPool {
22 public:
23 2598 static ThreadPool &Instance() {
24
5/8
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 2590 times.
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 8 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 8 times.
✗ Branch 10 not taken.
 2598 static ThreadPool pool(ppc::util::GetNumThreads());
25 2598 return pool;
26 }
27
28 1636 void ParallelFor(int n, const std::function<void(int, int)> &func) {
29
1/2
✓ Branch 0 taken 1636 times.
✗ Branch 1 not taken.
 1636 if (n <= 0) {
30 ✗ return;
31 }
32
33 1636 int num_threads = static_cast<int>(threads_.size());
34
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1636 times.
 1636 if (num_threads == 0) {
35 ✗ func(0, n);
36 ✗ return;
37 }
38
39 1636 std::vector<std::future<void>> futures;
40
1/2
✓ Branch 1 taken 1636 times.
✗ Branch 2 not taken.
 1636 futures.reserve(num_threads);
41
42 1636 int chunk_size = n / num_threads;
43 1636 int remainder = n % num_threads;
44
45
2/2
✓ Branch 0 taken 4096 times.
✓ Branch 1 taken 1636 times.
 5732 for (int thread_idx = 0; thread_idx < num_threads; ++thread_idx) {
46 4096 int start = thread_idx * chunk_size;
47 4096 int end = start + chunk_size;
48
2/2
✓ Branch 0 taken 1636 times.
✓ Branch 1 taken 2460 times.
 4096 if (thread_idx == num_threads - 1) {
49 1636 end += remainder;
50 }
51
52
3/6
✓ Branch 1 taken 4096 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4096 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 4096 times.
✗ Branch 8 not taken.
 12288 futures.push_back(Enqueue([func, start, end]() {
53
2/2
✓ Branch 0 taken 3912 times.
✓ Branch 1 taken 184 times.
 4096 if (start < end) {
54 3912 func(start, end);
55 }
56 4096 }));
57 }
58
59
2/2
✓ Branch 0 taken 4096 times.
✓ Branch 1 taken 1636 times.
 5732 for (auto &future : futures) {
60
1/2
✓ Branch 1 taken 4096 times.
✗ Branch 2 not taken.
 4096 future.get();
61 }
62 1636 }
63
64 962 double ParallelReduce(int n, const std::function<double(int, int)> &func) {
65
1/2
✓ Branch 0 taken 962 times.
✗ Branch 1 not taken.
 962 if (n <= 0) {
66 return 0.0;
67 }
68
69 962 int num_threads = static_cast<int>(threads_.size());
70
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 962 times.
 962 if (num_threads == 0) {
71 ✗ return func(0, n);
72 }
73
74 962 std::vector<std::future<double>> futures;
75
1/2
✓ Branch 1 taken 962 times.
✗ Branch 2 not taken.
 962 futures.reserve(num_threads);
76
77 962 int chunk_size = n / num_threads;
78 962 int remainder = n % num_threads;
79
80
2/2
✓ Branch 0 taken 2408 times.
✓ Branch 1 taken 962 times.
 3370 for (int thread_idx = 0; thread_idx < num_threads; ++thread_idx) {
81 2408 int start = thread_idx * chunk_size;
82 2408 int end = start + chunk_size;
83
2/2
✓ Branch 0 taken 962 times.
✓ Branch 1 taken 1446 times.
 2408 if (thread_idx == num_threads - 1) {
84 962 end += remainder;
85 }
86
87
3/6
✓ Branch 1 taken 2408 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2408 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 2408 times.
✗ Branch 8 not taken.
 7224 futures.push_back(Enqueue([func, start, end]() {
88
2/2
✓ Branch 0 taken 2268 times.
✓ Branch 1 taken 140 times.
 2408 if (start >= end) {
89 return 0.0;
90 }
91 2268 return func(start, end);
92 }));
93 }
94
95 double result = 0.0;
96
2/2
✓ Branch 0 taken 2408 times.
✓ Branch 1 taken 962 times.
 3370 for (auto &future : futures) {
97
1/2
✓ Branch 1 taken 2408 times.
✗ Branch 2 not taken.
 2408 result += future.get();
98 }
99 return result;
100 962 }
101
102 private:
103
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 16 explicit ThreadPool(size_t num_threads) {
104 8 if (num_threads == 0) {
105 num_threads = 1;
106 }
107
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 8 times.
 28 for (size_t i = 0; i < num_threads; ++i) {
108
1/2
✓ Branch 2 taken 20 times.
✗ Branch 3 not taken.
 40 threads_.emplace_back([this]() { Worker(); });
109 }
110 8 }
111
112 8 ~ThreadPool() {
113 {
114 8 std::unique_lock<std::mutex> lock(mutex_);
115 8 stop_ = true;
116 }
117 8 condition_.notify_all();
118
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 8 times.
 28 for (auto &thread : threads_) {
119
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
 20 if (thread.joinable()) {
120 20 thread.join();
121 }
122 }
123 16 }
124
125 template <typename F>
126 13008 auto Enqueue(F &&f) -> std::future<decltype(f())> {
127 auto task = std::make_shared<std::packaged_task<decltype(f())()>>(std::forward<F>(f));
128
1/2
✓ Branch 1 taken 6504 times.
✗ Branch 2 not taken.
 13008 std::future<decltype(f())> result = task->get_future();
129 {
130
1/2
✓ Branch 1 taken 6504 times.
✗ Branch 2 not taken.
 13008 std::unique_lock<std::mutex> lock(mutex_);
131
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6504 times.
 13008 if (stop_) {
132 ✗ throw std::runtime_error("Enqueue on stopped ThreadPool");
133 }
134 26016 tasks_.emplace([task]() { (*task)(); });
135 }
136 13008 condition_.notify_one();
137 13008 return result;
138 }
139
140 20 void Worker() {
141 while (true) {
142 std::function<void()> task;
143 {
144
1/2
✓ Branch 1 taken 6524 times.
✗ Branch 2 not taken.
 6524 std::unique_lock<std::mutex> lock(mutex_);
145
4/4
✓ Branch 0 taken 12896 times.
✓ Branch 1 taken 20 times.
✓ Branch 2 taken 6392 times.
✓ Branch 3 taken 6504 times.
 12916 condition_.wait(lock, [this] { return stop_ || !tasks_.empty(); });
146
3/4
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 6504 times.
✓ Branch 2 taken 20 times.
✗ Branch 3 not taken.
 6524 if (stop_ && tasks_.empty()) {
147 20 return;
148 }
149
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 6504 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 6504 if (tasks_.empty()) {
150 continue;
151 }
152 6504 task = std::move(tasks_.front());
153 tasks_.pop();
154 }
155
1/2
✓ Branch 0 taken 6504 times.
✗ Branch 1 not taken.
 6504 if (task) {
156 task();
157 }
158 }
159 }
160
161 std::vector<std::thread> threads_;
162 std::queue<std::function<void()>> tasks_;
163 std::mutex mutex_;
164 std::condition_variable condition_;
165 bool stop_ = false;
166 };
167
168 962 double ComputeDotProduct(const std::vector<double> &a, const std::vector<double> &b, int n) {
169
1/2
✓ Branch 0 taken 962 times.
✗ Branch 1 not taken.
 962 if (n <= 0) {
170 return 0.0;
171 }
172
1/2
✓ Branch 2 taken 962 times.
✗ Branch 3 not taken.
 1924 return ThreadPool::Instance().ParallelReduce(n, [&](int start, int end) {
173 double sum = 0.0;
174
2/2
✓ Branch 0 taken 6044 times.
✓ Branch 1 taken 2268 times.
 8312 for (int i = start; i < end; ++i) {
175 6044 sum += a[i] * b[i];
176 }
177 return sum;
178 });
179 }
180
181 433 void ComputeMatrixVectorProduct(const std::vector<double> &a, const std::vector<double> &v, std::vector<double> &result,
182 int n) {
183
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 433 times.
 433 if (n <= 0) {
184 ✗ return;
185 }
186 433 const auto stride = static_cast<size_t>(n);
187
1/2
✓ Branch 3 taken 433 times.
✗ Branch 4 not taken.
 866 ThreadPool::Instance().ParallelFor(n, [&](int start, int end) {
188
2/2
✓ Branch 0 taken 2786 times.
✓ Branch 1 taken 1030 times.
 3816 for (int i = start; i < end; ++i) {
189 double sum = 0.0;
190 2786 const double *a_row = &a[static_cast<size_t>(i) * stride];
191
2/2
✓ Branch 0 taken 20588 times.
✓ Branch 1 taken 2786 times.
 23374 for (int j = 0; j < n; ++j) {
192 20588 sum += a_row[j] * v[j];
193 }
194 2786 result[i] = sum;
195 }
196 1030 });
197 }
198
199 433 void UpdateSolution(std::vector<double> &x, const std::vector<double> &p, double alpha, int n) {
200
1/2
✓ Branch 0 taken 433 times.
✗ Branch 1 not taken.
 433 if (n <= 0) {
201 return;
202 }
203
1/2
✓ Branch 3 taken 433 times.
✗ Branch 4 not taken.
 866 ThreadPool::Instance().ParallelFor(n, [&](int start, int end) {
204
2/2
✓ Branch 0 taken 2786 times.
✓ Branch 1 taken 1030 times.
 3816 for (int i = start; i < end; ++i) {
205 2786 x[i] += alpha * p[i];
206 }
207 });
208 }
209
210 433 void UpdateResidual(std::vector<double> &r, const std::vector<double> &ap, double alpha, int n) {
211
1/2
✓ Branch 0 taken 433 times.
✗ Branch 1 not taken.
 433 if (n <= 0) {
212 return;
213 }
214
1/2
✓ Branch 3 taken 433 times.
✗ Branch 4 not taken.
 866 ThreadPool::Instance().ParallelFor(n, [&](int start, int end) {
215
2/2
✓ Branch 0 taken 2786 times.
✓ Branch 1 taken 1030 times.
 3816 for (int i = start; i < end; ++i) {
216 2786 r[i] -= alpha * ap[i];
217 }
218 });
219 }
220
221 337 void UpdateSearchDirection(std::vector<double> &p, const std::vector<double> &r, double beta, int n) {
222
1/2
✓ Branch 0 taken 337 times.
✗ Branch 1 not taken.
 337 if (n <= 0) {
223 return;
224 }
225
1/2
✓ Branch 3 taken 337 times.
✗ Branch 4 not taken.
 674 ThreadPool::Instance().ParallelFor(n, [&](int start, int end) {
226
2/2
✓ Branch 0 taken 2314 times.
✓ Branch 1 taken 822 times.
 3136 for (int i = start; i < end; ++i) {
227 2314 p[i] = r[i] + (beta * p[i]);
228 }
229 });
230 }
231
232 } // namespace
233
234
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 KichanovaKLinSystemByConjugGradSTL::KichanovaKLinSystemByConjugGradSTL(const InType &in) {
235 SetTypeOfTask(GetStaticTypeOfTask());
236
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 GetInput() = in;
237 96 GetOutput() = OutType();
238 96 }
239
240 96 bool KichanovaKLinSystemByConjugGradSTL::ValidationImpl() {
241 const InType &input_data = GetInput();
242
1/2
✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
 96 if (input_data.n <= 0) {
243 return false;
244 }
245
1/2
✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
 96 if (input_data.A.size() != static_cast<size_t>(input_data.n) * static_cast<size_t>(input_data.n)) {
246 return false;
247 }
248
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 96 times.
 96 if (input_data.b.size() != static_cast<size_t>(input_data.n)) {
249 ✗ return false;
250 }
251 return true;
252 }
253
254 96 bool KichanovaKLinSystemByConjugGradSTL::PreProcessingImpl() {
255 96 GetOutput().assign(GetInput().n, 0.0);
256 96 return true;
257 }
258
259
1/2
✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
 96 bool KichanovaKLinSystemByConjugGradSTL::RunImpl() {
260 const InType &input_data = GetInput();
261 OutType &x = GetOutput();
262
263 96 int n = input_data.n;
264
1/2
✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
 96 if (n <= 0) {
265 return false;
266 }
267
268 96 const std::vector<double> &a = input_data.A;
269 const std::vector<double> &b = input_data.b;
270 96 double epsilon = input_data.epsilon;
271
272 96 std::vector<double> r(n);
273
1/4
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 96 std::vector<double> p(n);
274
1/4
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 96 std::vector<double> ap(n);
275
276
2/2
✓ Branch 0 taken 472 times.
✓ Branch 1 taken 96 times.
 568 for (int i = 0; i < n; i++) {
277 472 r[i] = b[i];
278 472 p[i] = r[i];
279 }
280
281
1/2
✓ Branch 1 taken 96 times.
✗ Branch 2 not taken.
 96 double rr_old = ComputeDotProduct(r, r, n);
282 96 double residual_norm = std::sqrt(rr_old);
283
1/2
✓ Branch 0 taken 96 times.
✗ Branch 1 not taken.
 96 if (residual_norm < epsilon) {
284 return true;
285 }
286
287 96 int max_iter = n * 1000;
288
1/2
✓ Branch 0 taken 433 times.
✗ Branch 1 not taken.
 433 for (int iter = 0; iter < max_iter; iter++) {
289
1/2
✓ Branch 1 taken 433 times.
✗ Branch 2 not taken.
 433 ComputeMatrixVectorProduct(a, p, ap, n);
290
291
1/2
✓ Branch 1 taken 433 times.
✗ Branch 2 not taken.
 433 double p_ap = ComputeDotProduct(p, ap, n);
292
1/2
✓ Branch 0 taken 433 times.
✗ Branch 1 not taken.
 433 if (std::abs(p_ap) < 1e-30) {
293 break;
294 }
295
296 433 double alpha = rr_old / p_ap;
297
1/2
✓ Branch 1 taken 433 times.
✗ Branch 2 not taken.
 433 UpdateSolution(x, p, alpha, n);
298
1/2
✓ Branch 1 taken 433 times.
✗ Branch 2 not taken.
 433 UpdateResidual(r, ap, alpha, n);
299
300
1/2
✓ Branch 1 taken 433 times.
✗ Branch 2 not taken.
 433 double rr_new = ComputeDotProduct(r, r, n);
301 433 residual_norm = std::sqrt(rr_new);
302
2/2
✓ Branch 0 taken 337 times.
✓ Branch 1 taken 96 times.
 433 if (residual_norm < epsilon) {
303 break;
304 }
305
306 337 double beta = rr_new / rr_old;
307
1/2
✓ Branch 1 taken 337 times.
✗ Branch 2 not taken.
 337 UpdateSearchDirection(p, r, beta, n);
308
309 rr_old = rr_new;
310 }
311
312 return true;
313 }
314
315 96 bool KichanovaKLinSystemByConjugGradSTL::PostProcessingImpl() {
316 96 return true;
317 }
318
319 } // namespace kichanova_k_lin_system_by_conjug_grad
320