GCC Code Coverage Report

Directory: ./
File: tasks/zorin_d_strassen_alg_matrix_seq/stl/src/ops_stl.cpp
Date: 2026-05-11 08:26:31
Exec Total Coverage
Lines: 58 169 34.3%
Functions: 9 21 42.9%
Branches: 32 172 18.6%
Line Branch Exec Source
1 #include "zorin_d_strassen_alg_matrix_seq/stl/include/ops_stl.hpp"
2
3 #include <algorithm>
4 #include <cstddef>
5 #include <future>
6 #include <vector>
7
8 #include "util/include/util.hpp"
9 #include "zorin_d_strassen_alg_matrix_seq/common/include/common.hpp"
10
11 namespace zorin_d_strassen_alg_matrix_seq {
12
13 namespace {
14
15 constexpr std::size_t kCutoff = 256;
16 constexpr std::size_t kBlockSize = 64;
17
18 std::size_t NextPow2(std::size_t x) {
19 112 if (x <= 1) {
20 return 1;
21 }
22 std::size_t p = 1;
23
2/2
✓ Branch 0 taken 272 times.
✓ Branch 1 taken 96 times.
 368 while (p < x) {
24 272 p <<= 1;
25 }
26 return p;
27 }
28
29 void ZeroMatrix(double *dst, std::size_t stride, std::size_t n) {
30
2/2
✓ Branch 0 taken 880 times.
✓ Branch 1 taken 112 times.
 992 for (std::size_t i = 0; i < n; ++i) {
31 880 std::fill_n(dst + (i * stride), n, 0.0);
32 }
33 }
34
35 ✗ void AddToBuffer(const double *a, std::size_t a_stride, const double *b, std::size_t b_stride, double *dst,
36 std::size_t n, double b_coeff) {
37 ✗ for (std::size_t i = 0; i < n; ++i) {
38 ✗ const double *a_row = a + (i * a_stride);
39 ✗ const double *b_row = b + (i * b_stride);
40 ✗ double *dst_row = dst + (i * n);
41 ✗ for (std::size_t j = 0; j < n; ++j) {
42 ✗ dst_row[j] = a_row[j] + (b_coeff * b_row[j]);
43 }
44 }
45 ✗ }
46
47 void MulMicroBlock(const double *a, std::size_t a_stride, const double *b, std::size_t b_stride, double *c,
48 std::size_t c_stride, std::size_t i_begin, std::size_t i_end, std::size_t k_begin, std::size_t k_end,
49 std::size_t j_begin, std::size_t j_end) {
50
2/2
✓ Branch 0 taken 880 times.
✓ Branch 1 taken 112 times.
 992 for (std::size_t i = i_begin; i < i_end; ++i) {
51 880 double *c_row = c + (i * c_stride);
52 880 const double *a_row = a + (i * a_stride);
53
2/2
✓ Branch 0 taken 10576 times.
✓ Branch 1 taken 880 times.
 11456 for (std::size_t k = k_begin; k < k_end; ++k) {
54 10576 const double aik = a_row[k];
55 10576 const double *b_row = b + (k * b_stride);
56
2/2
✓ Branch 0 taken 148624 times.
✓ Branch 1 taken 10576 times.
 159200 for (std::size_t j = j_begin; j < j_end; ++j) {
57 148624 c_row[j] += aik * b_row[j];
58 }
59 }
60 }
61 }
62
63 112 void MulJBlocks(const double *a, std::size_t a_stride, const double *b, std::size_t b_stride, double *c,
64 std::size_t c_stride, std::size_t n, std::size_t ii, std::size_t i_end, std::size_t kk,
65 std::size_t k_end) {
66
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 112 times.
 224 for (std::size_t jj = 0; jj < n; jj += kBlockSize) {
67 112 const std::size_t j_end = std::min(jj + kBlockSize, n);
68 MulMicroBlock(a, a_stride, b, b_stride, c, c_stride, ii, i_end, kk, k_end, jj, j_end);
69 }
70 112 }
71
72 void MulKBlocks(const double *a, std::size_t a_stride, const double *b, std::size_t b_stride, double *c,
73 std::size_t c_stride, std::size_t n, std::size_t ii, std::size_t i_end) {
74
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 112 times.
 224 for (std::size_t kk = 0; kk < n; kk += kBlockSize) {
75 112 const std::size_t k_end = std::min(kk + kBlockSize, n);
76 112 MulJBlocks(a, a_stride, b, b_stride, c, c_stride, n, ii, i_end, kk, k_end);
77 }
78 }
79
80 112 void NaiveMulBlocked(const double *a, std::size_t a_stride, const double *b, std::size_t b_stride, double *c,
81 std::size_t c_stride, std::size_t n) {
82 112 ZeroMatrix(c, c_stride, n);
83
84
2/2
✓ Branch 0 taken 112 times.
✓ Branch 1 taken 112 times.
 224 for (std::size_t ii = 0; ii < n; ii += kBlockSize) {
85 112 const std::size_t i_end = std::min(ii + kBlockSize, n);
86 MulKBlocks(a, a_stride, b, b_stride, c, c_stride, n, ii, i_end);
87 }
88 112 }
89
90 ✗ void CombineQuadrants(const std::vector<double> &m1, const std::vector<double> &m2, const std::vector<double> &m3,
91 const std::vector<double> &m4, const std::vector<double> &m5, const std::vector<double> &m6,
92 const std::vector<double> &m7, double *c, std::size_t c_stride, std::size_t half) {
93 ✗ for (std::size_t i = 0; i < half; ++i) {
94 ✗ double *c11 = c + (i * c_stride);
95 double *c12 = c11 + half;
96 ✗ double *c21 = c + ((i + half) * c_stride);
97 double *c22 = c21 + half;
98
99 ✗ const double *m1_row = m1.data() + (i * half);
100 const double *m2_row = m2.data() + (i * half);
101 const double *m3_row = m3.data() + (i * half);
102 const double *m4_row = m4.data() + (i * half);
103 const double *m5_row = m5.data() + (i * half);
104 const double *m6_row = m6.data() + (i * half);
105 const double *m7_row = m7.data() + (i * half);
106
107 ✗ for (std::size_t j = 0; j < half; ++j) {
108 ✗ c11[j] = m1_row[j] + m4_row[j] - m5_row[j] + m7_row[j];
109 ✗ c12[j] = m3_row[j] + m5_row[j];
110 ✗ c21[j] = m2_row[j] + m4_row[j];
111 ✗ c22[j] = m1_row[j] - m2_row[j] + m3_row[j] + m6_row[j];
112 }
113 }
114 ✗ }
115
116 using StrassenSeqFn = void (*)(const double *, std::size_t, const double *, std::size_t, double *, std::size_t,
117 std::size_t);
118
119 void StrassenSeqImpl(const double *a, std::size_t a_stride, const double *b, std::size_t b_stride, double *c,
120 std::size_t c_stride, std::size_t n);
121
122 constexpr StrassenSeqFn kStrassenSeqFn = &StrassenSeqImpl;
123
124 ✗ void ComputeProduct(const double *a1, std::size_t a1_stride, const double *a2, std::size_t a2_stride, double a2_coeff,
125 const double *b1, std::size_t b1_stride, const double *b2, std::size_t b2_stride, double b2_coeff,
126 std::vector<double> &out, std::size_t n) {
127 ✗ std::vector<double> lhs(n * n);
128 ✗ std::vector<double> rhs(n * n);
129 ✗ AddToBuffer(a1, a1_stride, a2, a2_stride, lhs.data(), n, a2_coeff);
130 ✗ AddToBuffer(b1, b1_stride, b2, b2_stride, rhs.data(), n, b2_coeff);
131 ✗ out.assign(n * n, 0.0);
132 ✗ kStrassenSeqFn(lhs.data(), n, rhs.data(), n, out.data(), n, n);
133 ✗ }
134
135 ✗ void ComputeProductSingle(const double *a, std::size_t a_stride, const double *b1, std::size_t b1_stride,
136 const double *b2, std::size_t b2_stride, double b2_coeff, std::vector<double> &out,
137 std::size_t n) {
138 ✗ std::vector<double> rhs(n * n);
139 ✗ AddToBuffer(b1, b1_stride, b2, b2_stride, rhs.data(), n, b2_coeff);
140 ✗ out.assign(n * n, 0.0);
141 ✗ kStrassenSeqFn(a, a_stride, rhs.data(), n, out.data(), n, n);
142 ✗ }
143
144 ✗ void ComputeProductSingleLeft(const double *a1, std::size_t a1_stride, const double *a2, std::size_t a2_stride,
145 double a2_coeff, const double *b, std::size_t b_stride, std::vector<double> &out,
146 std::size_t n) {
147 ✗ std::vector<double> lhs(n * n);
148 ✗ AddToBuffer(a1, a1_stride, a2, a2_stride, lhs.data(), n, a2_coeff);
149 ✗ out.assign(n * n, 0.0);
150 ✗ kStrassenSeqFn(lhs.data(), n, b, b_stride, out.data(), n, n);
151 ✗ }
152
153 112 void StrassenTopStl(const double *a, std::size_t a_stride, const double *b, std::size_t b_stride, double *c,
154 std::size_t c_stride, std::size_t n) {
155
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 112 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 112 if (n <= kCutoff || ppc::util::GetNumThreads() <= 1) {
156 112 kStrassenSeqFn(a, a_stride, b, b_stride, c, c_stride, n);
157 112 return;
158 }
159
160 ✗ const std::size_t half = n / 2;
161
162 ✗ const double *a11 = a;
163 ✗ const double *a12 = a + half;
164 ✗ const double *a21 = a + (half * a_stride);
165 ✗ const double *a22 = a21 + half;
166
167 ✗ const double *b11 = b;
168 ✗ const double *b12 = b + half;
169 ✗ const double *b21 = b + (half * b_stride);
170 ✗ const double *b22 = b21 + half;
171
172 ✗ std::vector<double> m1;
173 ✗ std::vector<double> m2;
174 ✗ std::vector<double> m3;
175 ✗ std::vector<double> m4;
176 ✗ std::vector<double> m5;
177 ✗ std::vector<double> m6;
178 ✗ std::vector<double> m7;
179
180 ✗ auto f1 = std::async(std::launch::async, [&] {
181 ✗ ComputeProduct(a11, a_stride, a22, a_stride, 1.0, b11, b_stride, b22, b_stride, 1.0, m1, half);
182 ✗ });
183 auto f2 = std::async(std::launch::async,
184 ✗ [&] { ComputeProductSingleLeft(a21, a_stride, a22, a_stride, 1.0, b11, b_stride, m2, half); });
185 auto f3 = std::async(std::launch::async,
186 ✗ [&] { ComputeProductSingle(a11, a_stride, b12, b_stride, b22, b_stride, -1.0, m3, half); });
187 auto f4 = std::async(std::launch::async,
188 ✗ [&] { ComputeProductSingle(a22, a_stride, b21, b_stride, b11, b_stride, -1.0, m4, half); });
189 auto f5 = std::async(std::launch::async,
190 ✗ [&] { ComputeProductSingleLeft(a11, a_stride, a12, a_stride, 1.0, b22, b_stride, m5, half); });
191 ✗ auto f6 = std::async(std::launch::async, [&] {
192 ✗ ComputeProduct(a21, a_stride, a11, a_stride, -1.0, b11, b_stride, b12, b_stride, 1.0, m6, half);
193 ✗ });
194 ✗ auto f7 = std::async(std::launch::async, [&] {
195 ✗ ComputeProduct(a12, a_stride, a22, a_stride, -1.0, b21, b_stride, b22, b_stride, 1.0, m7, half);
196 ✗ });
197
198 ✗ f1.get();
199 ✗ f2.get();
200 ✗ f3.get();
201 ✗ f4.get();
202 ✗ f5.get();
203 ✗ f6.get();
204 ✗ f7.get();
205
206 ✗ CombineQuadrants(m1, m2, m3, m4, m5, m6, m7, c, c_stride, half);
207 }
208
209 112 void StrassenSeqImpl(const double *a, std::size_t a_stride, const double *b, std::size_t b_stride, double *c,
210 std::size_t c_stride, std::size_t n) {
211
1/2
✓ Branch 0 taken 112 times.
✗ Branch 1 not taken.
 112 if (n <= kCutoff) {
212 112 NaiveMulBlocked(a, a_stride, b, b_stride, c, c_stride, n);
213 112 return;
214 }
215
216 ✗ const std::size_t half = n / 2;
217
218 const double *a11 = a;
219 ✗ const double *a12 = a + half;
220 ✗ const double *a21 = a + (half * a_stride);
221 ✗ const double *a22 = a21 + half;
222
223 const double *b11 = b;
224 ✗ const double *b12 = b + half;
225 ✗ const double *b21 = b + (half * b_stride);
226 ✗ const double *b22 = b21 + half;
227
228 ✗ std::vector<double> m1(half * half);
229 ✗ std::vector<double> m2(half * half);
230 ✗ std::vector<double> m3(half * half);
231 ✗ std::vector<double> m4(half * half);
232 ✗ std::vector<double> m5(half * half);
233 ✗ std::vector<double> m6(half * half);
234 ✗ std::vector<double> m7(half * half);
235 ✗ std::vector<double> lhs(half * half);
236 ✗ std::vector<double> rhs(half * half);
237
238 ✗ AddToBuffer(a11, a_stride, a22, a_stride, lhs.data(), half, 1.0);
239 ✗ AddToBuffer(b11, b_stride, b22, b_stride, rhs.data(), half, 1.0);
240 ✗ kStrassenSeqFn(lhs.data(), half, rhs.data(), half, m1.data(), half, half);
241
242 ✗ AddToBuffer(a21, a_stride, a22, a_stride, lhs.data(), half, 1.0);
243 ✗ kStrassenSeqFn(lhs.data(), half, b11, b_stride, m2.data(), half, half);
244
245 ✗ AddToBuffer(b12, b_stride, b22, b_stride, rhs.data(), half, -1.0);
246 ✗ kStrassenSeqFn(a11, a_stride, rhs.data(), half, m3.data(), half, half);
247
248 ✗ AddToBuffer(b21, b_stride, b11, b_stride, rhs.data(), half, -1.0);
249 ✗ kStrassenSeqFn(a22, a_stride, rhs.data(), half, m4.data(), half, half);
250
251 ✗ AddToBuffer(a11, a_stride, a12, a_stride, lhs.data(), half, 1.0);
252 ✗ kStrassenSeqFn(lhs.data(), half, b22, b_stride, m5.data(), half, half);
253
254 ✗ AddToBuffer(a21, a_stride, a11, a_stride, lhs.data(), half, -1.0);
255 ✗ AddToBuffer(b11, b_stride, b12, b_stride, rhs.data(), half, 1.0);
256 ✗ kStrassenSeqFn(lhs.data(), half, rhs.data(), half, m6.data(), half, half);
257
258 ✗ AddToBuffer(a12, a_stride, a22, a_stride, lhs.data(), half, -1.0);
259 ✗ AddToBuffer(b21, b_stride, b22, b_stride, rhs.data(), half, 1.0);
260 ✗ kStrassenSeqFn(lhs.data(), half, rhs.data(), half, m7.data(), half, half);
261
262 ✗ CombineQuadrants(m1, m2, m3, m4, m5, m6, m7, c, c_stride, half);
263 }
264
265 } // namespace
266
267
1/2
✓ Branch 1 taken 112 times.
✗ Branch 2 not taken.
 112 ZorinDStrassenAlgMatrixSTL::ZorinDStrassenAlgMatrixSTL(const InType &in) {
268 SetTypeOfTask(GetStaticTypeOfTask());
269 GetInput() = in;
270 GetOutput().clear();
271 112 }
272
273 112 bool ZorinDStrassenAlgMatrixSTL::ValidationImpl() {
274 const auto &in = GetInput();
275
1/2
✓ Branch 0 taken 112 times.
✗ Branch 1 not taken.
 112 if (in.n == 0) {
276 return false;
277 }
278
1/2
✓ Branch 0 taken 112 times.
✗ Branch 1 not taken.
 112 if (in.a.size() != in.n * in.n) {
279 return false;
280 }
281
1/2
✓ Branch 0 taken 112 times.
✗ Branch 1 not taken.
 112 if (in.b.size() != in.n * in.n) {
282 return false;
283 }
284
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 112 times.
 112 if (!GetOutput().empty()) {
285 ✗ return false;
286 }
287 return true;
288 }
289
290 112 bool ZorinDStrassenAlgMatrixSTL::PreProcessingImpl() {
291 112 const auto n = GetInput().n;
292 112 GetOutput().assign(n * n, 0.0);
293 112 return true;
294 }
295
296 112 bool ZorinDStrassenAlgMatrixSTL::RunImpl() {
297 const auto &in = GetInput();
298
2/2
✓ Branch 0 taken 96 times.
✓ Branch 1 taken 16 times.
 112 const std::size_t n = in.n;
299 const std::size_t padded = NextPow2(n);
300
301 112 std::vector<double> a_pad(padded * padded, 0.0);
302
1/4
✓ Branch 1 taken 112 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 112 std::vector<double> b_pad(padded * padded, 0.0);
303
1/4
✓ Branch 1 taken 112 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 112 std::vector<double> c_pad(padded * padded, 0.0);
304
305
2/2
✓ Branch 0 taken 704 times.
✓ Branch 1 taken 112 times.
 816 for (std::size_t i = 0; i < n; ++i) {
306 704 std::copy_n(in.a.data() + (i * n), n, a_pad.data() + (i * padded));
307 704 std::copy_n(in.b.data() + (i * n), n, b_pad.data() + (i * padded));
308 }
309
310
1/2
✓ Branch 1 taken 112 times.
✗ Branch 2 not taken.
 112 StrassenTopStl(a_pad.data(), padded, b_pad.data(), padded, c_pad.data(), padded, padded);
311
312 auto &out = GetOutput();
313
2/2
✓ Branch 0 taken 704 times.
✓ Branch 1 taken 112 times.
 816 for (std::size_t i = 0; i < n; ++i) {
314 704 std::copy_n(c_pad.data() + (i * padded), n, out.data() + (i * n));
315 }
316
317 112 return true;
318 }
319
320 112 bool ZorinDStrassenAlgMatrixSTL::PostProcessingImpl() {
321 112 return true;
322 }
323
324 } // namespace zorin_d_strassen_alg_matrix_seq
325