GCC Code Coverage Report

Directory: ./
File: tasks/lazareva_a_matrix_mult_strassen/omp/src/ops_omp.cpp
Date: 2026-06-04 20:25:32
Exec Total Coverage
Lines: 124 125 99.2%
Functions: 13 14 92.9%
Branches: 55 90 61.1%
Line Branch Exec Source
1 #include "lazareva_a_matrix_mult_strassen/omp/include/ops_omp.hpp"
2
3 #include <array>
4 #include <cstddef>
5 #include <utility>
6 #include <vector>
7
8 #include "lazareva_a_matrix_mult_strassen/common/include/common.hpp"
9
10 namespace lazareva_a_matrix_mult_strassen {
11
12
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 LazarevaATestTaskOMP::LazarevaATestTaskOMP(const InType &in) {
13 SetTypeOfTask(GetStaticTypeOfTask());
14 GetInput() = in;
15 GetOutput() = {};
16 32 }
17
18 32 bool LazarevaATestTaskOMP::ValidationImpl() {
19 32 const int n = GetInput().n;
20
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 if (n <= 0) {
21 return false;
22 }
23
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
 32 const auto expected = static_cast<size_t>(n) * static_cast<size_t>(n);
24
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 32 times.
 32 return std::cmp_equal(GetInput().a.size(), expected) && std::cmp_equal(GetInput().b.size(), expected);
25 }
26
27 32 bool LazarevaATestTaskOMP::PreProcessingImpl() {
28 32 n_ = GetInput().n;
29 32 padded_n_ = NextPowerOfTwo(n_);
30 32 a_ = PadMatrix(GetInput().a, n_, padded_n_);
31 32 b_ = PadMatrix(GetInput().b, n_, padded_n_);
32 32 const auto padded_size = static_cast<size_t>(padded_n_) * static_cast<size_t>(padded_n_);
33 32 result_.assign(padded_size, 0.0);
34 32 return true;
35 }
36
37 32 bool LazarevaATestTaskOMP::RunImpl() {
38 32 result_ = Strassen(a_, b_, padded_n_);
39 32 return true;
40 }
41
42 32 bool LazarevaATestTaskOMP::PostProcessingImpl() {
43 32 GetOutput() = UnpadMatrix(result_, padded_n_, n_);
44 32 return true;
45 }
46
47 ✗ int LazarevaATestTaskOMP::NextPowerOfTwo(int n) {
48
1/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 32 times.
✗ Branch 3 not taken.
 32 if (n <= 0) {
49 return 1;
50 }
51 int p = 1;
52
2/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 132 times.
✓ Branch 3 taken 32 times.
 164 while (p < n) {
53 132 p <<= 1;
54 }
55 return p;
56 }
57
58 64 std::vector<double> LazarevaATestTaskOMP::PadMatrix(const std::vector<double> &m, int old_n, int new_n) {
59 64 const auto new_size = static_cast<size_t>(new_n) * static_cast<size_t>(new_n);
60 64 std::vector<double> result(new_size, 0.0);
61
2/2
✓ Branch 0 taken 2320 times.
✓ Branch 1 taken 64 times.
 2384 for (int i = 0; i < old_n; ++i) {
62
2/2
✓ Branch 0 taken 200384 times.
✓ Branch 1 taken 2320 times.
 202704 for (int j = 0; j < old_n; ++j) {
63 200384 const auto dst = (static_cast<ptrdiff_t>(i) * new_n) + j;
64 200384 const auto src = (static_cast<ptrdiff_t>(i) * old_n) + j;
65 200384 result[static_cast<size_t>(dst)] = m[static_cast<size_t>(src)];
66 }
67 }
68 64 return result;
69 }
70
71 32 std::vector<double> LazarevaATestTaskOMP::UnpadMatrix(const std::vector<double> &m, int old_n, int new_n) {
72 32 const auto new_size = static_cast<size_t>(new_n) * static_cast<size_t>(new_n);
73 32 std::vector<double> result(new_size);
74
2/2
✓ Branch 0 taken 1160 times.
✓ Branch 1 taken 32 times.
 1192 for (int i = 0; i < new_n; ++i) {
75
2/2
✓ Branch 0 taken 100192 times.
✓ Branch 1 taken 1160 times.
 101352 for (int j = 0; j < new_n; ++j) {
76 100192 const auto dst = (static_cast<ptrdiff_t>(i) * new_n) + j;
77 100192 const auto src = (static_cast<ptrdiff_t>(i) * old_n) + j;
78 100192 result[static_cast<size_t>(dst)] = m[static_cast<size_t>(src)];
79 }
80 }
81 32 return result;
82 }
83
84 96 std::vector<double> LazarevaATestTaskOMP::Add(const std::vector<double> &a, const std::vector<double> &b, int n) {
85 96 const auto size = static_cast<size_t>(n) * static_cast<size_t>(n);
86 96 std::vector<double> result(size);
87
2/2
✓ Branch 0 taken 393216 times.
✓ Branch 1 taken 96 times.
 393312 for (size_t i = 0; i < size; ++i) {
88 393216 result[i] = a[i] + b[i];
89 }
90 96 return result;
91 }
92
93 48 std::vector<double> LazarevaATestTaskOMP::Sub(const std::vector<double> &a, const std::vector<double> &b, int n) {
94 48 const auto size = static_cast<size_t>(n) * static_cast<size_t>(n);
95 48 std::vector<double> result(size);
96
2/2
✓ Branch 0 taken 196608 times.
✓ Branch 1 taken 48 times.
 196656 for (size_t i = 0; i < size; ++i) {
97 196608 result[i] = a[i] - b[i];
98 }
99 48 return result;
100 }
101
102 16 void LazarevaATestTaskOMP::Split(const std::vector<double> &parent, int n, std::vector<double> &a11,
103 std::vector<double> &a12, std::vector<double> &a21, std::vector<double> &a22) {
104 16 const int half = n / 2;
105 16 const auto half_size = static_cast<size_t>(half) * static_cast<size_t>(half);
106 16 a11.resize(half_size);
107 16 a12.resize(half_size);
108 16 a21.resize(half_size);
109 16 a22.resize(half_size);
110
111
2/2
✓ Branch 0 taken 1024 times.
✓ Branch 1 taken 16 times.
 1040 for (int i = 0; i < half; ++i) {
112
2/2
✓ Branch 0 taken 65536 times.
✓ Branch 1 taken 1024 times.
 66560 for (int j = 0; j < half; ++j) {
113 65536 const auto idx = static_cast<size_t>((static_cast<ptrdiff_t>(i) * half) + j);
114 65536 a11[idx] = parent[static_cast<size_t>((static_cast<ptrdiff_t>(i) * n) + j)];
115 65536 a12[idx] = parent[static_cast<size_t>((static_cast<ptrdiff_t>(i) * n) + j + half)];
116 65536 a21[idx] = parent[static_cast<size_t>((static_cast<ptrdiff_t>(i + half) * n) + j)];
117 65536 a22[idx] = parent[static_cast<size_t>((static_cast<ptrdiff_t>(i + half) * n) + j + half)];
118 }
119 }
120 16 }
121
122 8 std::vector<double> LazarevaATestTaskOMP::Merge(const std::vector<double> &c11, const std::vector<double> &c12,
123 const std::vector<double> &c21, const std::vector<double> &c22, int n) {
124 8 const int full = n * 2;
125 8 const auto full_size = static_cast<size_t>(full) * static_cast<size_t>(full);
126 8 std::vector<double> result(full_size);
127
128
2/2
✓ Branch 0 taken 512 times.
✓ Branch 1 taken 8 times.
 520 for (int i = 0; i < n; ++i) {
129
2/2
✓ Branch 0 taken 32768 times.
✓ Branch 1 taken 512 times.
 33280 for (int j = 0; j < n; ++j) {
130 32768 const auto src = static_cast<size_t>((static_cast<ptrdiff_t>(i) * n) + j);
131 32768 result[static_cast<size_t>((static_cast<ptrdiff_t>(i) * full) + j)] = c11[src];
132 32768 result[static_cast<size_t>((static_cast<ptrdiff_t>(i) * full) + j + n)] = c12[src];
133 32768 result[static_cast<size_t>((static_cast<ptrdiff_t>(i + n) * full) + j)] = c21[src];
134 32768 result[static_cast<size_t>((static_cast<ptrdiff_t>(i + n) * full) + j + n)] = c22[src];
135 }
136 }
137 8 return result;
138 }
139
140 24 std::vector<double> LazarevaATestTaskOMP::NaiveMult(const std::vector<double> &a, const std::vector<double> &b, int n) {
141 24 const auto size = static_cast<size_t>(n) * static_cast<size_t>(n);
142 24 std::vector<double> c(size, 0.0);
143
144 24 #pragma omp parallel for schedule(static) default(none) shared(a, b, c, n)
145 for (int i = 0; i < n; ++i) {
146 for (int k = 0; k < n; ++k) {
147 const double aik = a[static_cast<size_t>((static_cast<ptrdiff_t>(i) * n) + k)];
148 for (int j = 0; j < n; ++j) {
149 c[static_cast<size_t>((static_cast<ptrdiff_t>(i) * n) + j)] +=
150 aik * b[static_cast<size_t>((static_cast<ptrdiff_t>(k) * n) + j)];
151 }
152 }
153 }
154 24 return c;
155 }
156
157 32 std::vector<double> LazarevaATestTaskOMP::Strassen(const std::vector<double> &root_a, const std::vector<double> &root_b,
158 int root_n) {
159
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 8 times.
 32 if (root_n <= 64) {
160 24 return NaiveMult(root_a, root_b, root_n);
161 }
162
163 8 const int half = root_n / 2;
164
165 8 std::vector<double> a11;
166 8 std::vector<double> a12;
167 8 std::vector<double> a21;
168 8 std::vector<double> a22;
169 8 std::vector<double> b11;
170 8 std::vector<double> b12;
171 8 std::vector<double> b21;
172 8 std::vector<double> b22;
173
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 Split(root_a, root_n, a11, a12, a21, a22);
174
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 Split(root_b, root_n, b11, b12, b21, b22);
175
176 8 std::array<std::vector<double>, 7> lhs;
177 8 std::array<std::vector<double>, 7> rhs;
178
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 lhs.at(0) = Add(a11, a22, half);
179
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 rhs.at(0) = Add(b11, b22, half);
180
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 lhs.at(1) = Add(a21, a22, half);
181
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 rhs.at(1) = b11;
182
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 lhs.at(2) = a11;
183
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 rhs.at(2) = Sub(b12, b22, half);
184
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 lhs.at(3) = a22;
185
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 rhs.at(3) = Sub(b21, b11, half);
186
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 lhs.at(4) = Add(a11, a12, half);
187
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 rhs.at(4) = b22;
188
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 lhs.at(5) = Sub(a21, a11, half);
189
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 rhs.at(5) = Add(b11, b12, half);
190
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 lhs.at(6) = Sub(a12, a22, half);
191
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 rhs.at(6) = Add(b21, b22, half);
192
193 8 std::array<std::vector<double>, 7> m;
194
195 8 #pragma omp parallel for schedule(static) default(none) shared(m, lhs, rhs, half)
196 for (int k = 0; k < 7; ++k) {
197 const auto uk = static_cast<size_t>(k);
198 const int nn = half;
199 const auto sz = static_cast<size_t>(nn) * static_cast<size_t>(nn);
200 std::vector<double> c(sz, 0.0);
201 for (int i = 0; i < nn; ++i) {
202 for (int ki = 0; ki < nn; ++ki) {
203 const double aik = lhs.at(uk)[static_cast<size_t>((static_cast<ptrdiff_t>(i) * nn) + ki)];
204 for (int j = 0; j < nn; ++j) {
205 c[static_cast<size_t>((static_cast<ptrdiff_t>(i) * nn) + j)] +=
206 aik * rhs.at(uk)[static_cast<size_t>((static_cast<ptrdiff_t>(ki) * nn) + j)];
207 }
208 }
209 }
210 m.at(uk) = std::move(c);
211 }
212
213
3/6
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 8 times.
✗ Branch 8 not taken.
 8 auto c11 = Add(Sub(Add(m.at(0), m.at(3), half), m.at(4), half), m.at(6), half);
214
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 auto c12 = Add(m.at(2), m.at(4), half);
215
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 auto c21 = Add(m.at(1), m.at(3), half);
216
3/6
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 8 times.
✗ Branch 8 not taken.
 8 auto c22 = Add(Sub(Add(m.at(0), m.at(2), half), m.at(1), half), m.at(5), half);
217
218
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 return Merge(c11, c12, c21, c22, half);
219 8 }
220
221 } // namespace lazareva_a_matrix_mult_strassen
222