GCC Code Coverage Report

Directory: ./
File: tasks/lazareva_a_matrix_mult_strassen/omp/src/ops_omp.cpp
Date: 2026-04-02 17:12:27
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 24 times.
✗ Branch 2 not taken.
 24 LazarevaATestTaskOMP::LazarevaATestTaskOMP(const InType &in) {
13 SetTypeOfTask(GetStaticTypeOfTask());
14 GetInput() = in;
15 GetOutput() = {};
16 24 }
17
18 24 bool LazarevaATestTaskOMP::ValidationImpl() {
19 24 const int n = GetInput().n;
20
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 if (n <= 0) {
21 return false;
22 }
23
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
 24 const auto expected = static_cast<size_t>(n) * static_cast<size_t>(n);
24
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 24 times.
 24 return std::cmp_equal(GetInput().a.size(), expected) && std::cmp_equal(GetInput().b.size(), expected);
25 }
26
27 24 bool LazarevaATestTaskOMP::PreProcessingImpl() {
28 24 n_ = GetInput().n;
29 24 padded_n_ = NextPowerOfTwo(n_);
30 24 a_ = PadMatrix(GetInput().a, n_, padded_n_);
31 24 b_ = PadMatrix(GetInput().b, n_, padded_n_);
32 24 const auto padded_size = static_cast<size_t>(padded_n_) * static_cast<size_t>(padded_n_);
33 24 result_.assign(padded_size, 0.0);
34 24 return true;
35 }
36
37 24 bool LazarevaATestTaskOMP::RunImpl() {
38 24 result_ = Strassen(a_, b_, padded_n_);
39 24 return true;
40 }
41
42 24 bool LazarevaATestTaskOMP::PostProcessingImpl() {
43 24 GetOutput() = UnpadMatrix(result_, padded_n_, n_);
44 24 return true;
45 }
46
47 ✗ int LazarevaATestTaskOMP::NextPowerOfTwo(int n) {
48
1/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 24 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 80 times.
✓ Branch 3 taken 24 times.
 104 while (p < n) {
53 80 p <<= 1;
54 }
55 return p;
56 }
57
58 48 std::vector<double> LazarevaATestTaskOMP::PadMatrix(const std::vector<double> &m, int old_n, int new_n) {
59 48 const auto new_size = static_cast<size_t>(new_n) * static_cast<size_t>(new_n);
60 48 std::vector<double> result(new_size, 0.0);
61
2/2
✓ Branch 0 taken 1288 times.
✓ Branch 1 taken 48 times.
 1336 for (int i = 0; i < old_n; ++i) {
62
2/2
✓ Branch 0 taken 133816 times.
✓ Branch 1 taken 1288 times.
 135104 for (int j = 0; j < old_n; ++j) {
63 133816 const auto dst = (static_cast<ptrdiff_t>(i) * new_n) + j;
64 133816 const auto src = (static_cast<ptrdiff_t>(i) * old_n) + j;
65 133816 result[static_cast<size_t>(dst)] = m[static_cast<size_t>(src)];
66 }
67 }
68 48 return result;
69 }
70
71 24 std::vector<double> LazarevaATestTaskOMP::UnpadMatrix(const std::vector<double> &m, int old_n, int new_n) {
72 24 const auto new_size = static_cast<size_t>(new_n) * static_cast<size_t>(new_n);
73 24 std::vector<double> result(new_size);
74
2/2
✓ Branch 0 taken 644 times.
✓ Branch 1 taken 24 times.
 668 for (int i = 0; i < new_n; ++i) {
75
2/2
✓ Branch 0 taken 66908 times.
✓ Branch 1 taken 644 times.
 67552 for (int j = 0; j < new_n; ++j) {
76 66908 const auto dst = (static_cast<ptrdiff_t>(i) * new_n) + j;
77 66908 const auto src = (static_cast<ptrdiff_t>(i) * old_n) + j;
78 66908 result[static_cast<size_t>(dst)] = m[static_cast<size_t>(src)];
79 }
80 }
81 24 return result;
82 }
83
84 48 std::vector<double> LazarevaATestTaskOMP::Add(const std::vector<double> &a, const std::vector<double> &b, int n) {
85 48 const auto size = static_cast<size_t>(n) * static_cast<size_t>(n);
86 48 std::vector<double> result(size);
87
2/2
✓ Branch 0 taken 196608 times.
✓ Branch 1 taken 48 times.
 196656 for (size_t i = 0; i < size; ++i) {
88 196608 result[i] = a[i] + b[i];
89 }
90 48 return result;
91 }
92
93 24 std::vector<double> LazarevaATestTaskOMP::Sub(const std::vector<double> &a, const std::vector<double> &b, int n) {
94 24 const auto size = static_cast<size_t>(n) * static_cast<size_t>(n);
95 24 std::vector<double> result(size);
96
2/2
✓ Branch 0 taken 98304 times.
✓ Branch 1 taken 24 times.
 98328 for (size_t i = 0; i < size; ++i) {
97 98304 result[i] = a[i] - b[i];
98 }
99 24 return result;
100 }
101
102 8 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 8 const int half = n / 2;
105 8 const auto half_size = static_cast<size_t>(half) * static_cast<size_t>(half);
106 8 a11.resize(half_size);
107 8 a12.resize(half_size);
108 8 a21.resize(half_size);
109 8 a22.resize(half_size);
110
111
2/2
✓ Branch 0 taken 512 times.
✓ Branch 1 taken 8 times.
 520 for (int i = 0; i < half; ++i) {
112
2/2
✓ Branch 0 taken 32768 times.
✓ Branch 1 taken 512 times.
 33280 for (int j = 0; j < half; ++j) {
113 32768 const auto idx = static_cast<size_t>((static_cast<ptrdiff_t>(i) * half) + j);
114 32768 a11[idx] = parent[static_cast<size_t>((static_cast<ptrdiff_t>(i) * n) + j)];
115 32768 a12[idx] = parent[static_cast<size_t>((static_cast<ptrdiff_t>(i) * n) + j + half)];
116 32768 a21[idx] = parent[static_cast<size_t>((static_cast<ptrdiff_t>(i + half) * n) + j)];
117 32768 a22[idx] = parent[static_cast<size_t>((static_cast<ptrdiff_t>(i + half) * n) + j + half)];
118 }
119 }
120 8 }
121
122 4 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 4 const int full = n * 2;
125 4 const auto full_size = static_cast<size_t>(full) * static_cast<size_t>(full);
126 4 std::vector<double> result(full_size);
127
128
2/2
✓ Branch 0 taken 256 times.
✓ Branch 1 taken 4 times.
 260 for (int i = 0; i < n; ++i) {
129
2/2
✓ Branch 0 taken 16384 times.
✓ Branch 1 taken 256 times.
 16640 for (int j = 0; j < n; ++j) {
130 16384 const auto src = static_cast<size_t>((static_cast<ptrdiff_t>(i) * n) + j);
131 16384 result[static_cast<size_t>((static_cast<ptrdiff_t>(i) * full) + j)] = c11[src];
132 16384 result[static_cast<size_t>((static_cast<ptrdiff_t>(i) * full) + j + n)] = c12[src];
133 16384 result[static_cast<size_t>((static_cast<ptrdiff_t>(i + n) * full) + j)] = c21[src];
134 16384 result[static_cast<size_t>((static_cast<ptrdiff_t>(i + n) * full) + j + n)] = c22[src];
135 }
136 }
137 4 return result;
138 }
139
140 20 std::vector<double> LazarevaATestTaskOMP::NaiveMult(const std::vector<double> &a, const std::vector<double> &b, int n) {
141 20 const auto size = static_cast<size_t>(n) * static_cast<size_t>(n);
142 20 std::vector<double> c(size, 0.0);
143
144 20 #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 20 return c;
155 }
156
157 24 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 20 times.
✓ Branch 1 taken 4 times.
 24 if (root_n <= 64) {
160 20 return NaiveMult(root_a, root_b, root_n);
161 }
162
163 4 const int half = root_n / 2;
164
165 4 std::vector<double> a11;
166 4 std::vector<double> a12;
167 4 std::vector<double> a21;
168 4 std::vector<double> a22;
169 4 std::vector<double> b11;
170 4 std::vector<double> b12;
171 4 std::vector<double> b21;
172 4 std::vector<double> b22;
173
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 Split(root_a, root_n, a11, a12, a21, a22);
174
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 Split(root_b, root_n, b11, b12, b21, b22);
175
176 4 std::array<std::vector<double>, 7> lhs;
177 4 std::array<std::vector<double>, 7> rhs;
178
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 lhs.at(0) = Add(a11, a22, half);
179
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 rhs.at(0) = Add(b11, b22, half);
180
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 lhs.at(1) = Add(a21, a22, half);
181
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 rhs.at(1) = b11;
182
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 lhs.at(2) = a11;
183
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 rhs.at(2) = Sub(b12, b22, half);
184
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 lhs.at(3) = a22;
185
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 rhs.at(3) = Sub(b21, b11, half);
186
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 lhs.at(4) = Add(a11, a12, half);
187
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 rhs.at(4) = b22;
188
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 lhs.at(5) = Sub(a21, a11, half);
189
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 rhs.at(5) = Add(b11, b12, half);
190
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 lhs.at(6) = Sub(a12, a22, half);
191
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 rhs.at(6) = Add(b21, b22, half);
192
193 4 std::array<std::vector<double>, 7> m;
194
195 4 #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 4 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 4 times.
✗ Branch 8 not taken.
 4 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 4 times.
✗ Branch 2 not taken.
 4 auto c12 = Add(m.at(2), m.at(4), half);
215
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 auto c21 = Add(m.at(1), m.at(3), half);
216
3/6
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 4 times.
✗ Branch 8 not taken.
 4 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 4 times.
✗ Branch 2 not taken.
 4 return Merge(c11, c12, c21, c22, half);
219 4 }
220
221 } // namespace lazareva_a_matrix_mult_strassen
222