GCC Code Coverage Report

Directory: ./
File: tasks/tabalaev_a_matrix_mul_strassen/seq/src/ops_seq.cpp
Date: 2026-04-02 17:12:27
Exec Total Coverage
Lines: 104 104 100.0%
Functions: 11 11 100.0%
Branches: 84 148 56.8%
Line Branch Exec Source
1 #include "tabalaev_a_matrix_mul_strassen/seq/include/ops_seq.hpp"
2
3 #include <algorithm>
4 #include <cmath>
5 #include <cstddef>
6 #include <stack>
7 #include <utility>
8 #include <vector>
9
10 #include "tabalaev_a_matrix_mul_strassen/common/include/common.hpp"
11
12 namespace tabalaev_a_matrix_mul_strassen {
13
14
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 TabalaevAMatrixMulStrassenSEQ::TabalaevAMatrixMulStrassenSEQ(const InType &in) {
15 SetTypeOfTask(GetStaticTypeOfTask());
16
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 GetInput() = in;
17 GetOutput() = {};
18 48 }
19
20 48 bool TabalaevAMatrixMulStrassenSEQ::ValidationImpl() {
21 const auto &in = GetInput();
22
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 48 times.
 48 return in.a_rows > 0 && in.a_cols_b_rows > 0 && in.b_cols > 0 &&
23
2/4
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 48 times.
 96 in.a.size() == static_cast<size_t>(in.a_rows * in.a_cols_b_rows) &&
24
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
 48 in.b.size() == static_cast<size_t>(in.a_cols_b_rows * in.b_cols);
25 }
26
27 48 bool TabalaevAMatrixMulStrassenSEQ::PreProcessingImpl() {
28 GetOutput() = {};
29 const auto &in = GetInput();
30 48 a_rows_ = in.a_rows;
31 48 a_cols_b_rows_ = in.a_cols_b_rows;
32 48 b_cols_ = in.b_cols;
33
34 48 size_t max_dim = std::max({a_rows_, a_cols_b_rows_, b_cols_});
35 48 padded_n_ = 1;
36
2/2
✓ Branch 0 taken 224 times.
✓ Branch 1 taken 48 times.
 272 while (padded_n_ < max_dim) {
37 224 padded_n_ *= 2;
38 }
39
40 48 padded_a_.assign(padded_n_ * padded_n_, 0.0);
41 48 padded_b_.assign(padded_n_ * padded_n_, 0.0);
42
43
2/2
✓ Branch 0 taken 4392 times.
✓ Branch 1 taken 48 times.
 4440 for (size_t i = 0; i < a_rows_; ++i) {
44
2/2
✓ Branch 0 taken 1047336 times.
✓ Branch 1 taken 4392 times.
 1051728 for (size_t j = 0; j < a_cols_b_rows_; ++j) {
45 1047336 padded_a_[(i * padded_n_) + j] = in.a[(i * a_cols_b_rows_) + j];
46 }
47 }
48
49
2/2
✓ Branch 0 taken 4312 times.
✓ Branch 1 taken 48 times.
 4360 for (size_t i = 0; i < a_cols_b_rows_; ++i) {
50
2/2
✓ Branch 0 taken 1047336 times.
✓ Branch 1 taken 4312 times.
 1051648 for (size_t j = 0; j < b_cols_; ++j) {
51 1047336 padded_b_[(i * padded_n_) + j] = in.b[(i * b_cols_) + j];
52 }
53 }
54 48 return true;
55 }
56
57 48 bool TabalaevAMatrixMulStrassenSEQ::RunImpl() {
58 96 result_c_ = StrassenMultiply(padded_a_, padded_b_, padded_n_);
59
60 auto &out = GetOutput();
61 48 out.assign(a_rows_ * b_cols_, 0.0);
62
63
2/2
✓ Branch 0 taken 4392 times.
✓ Branch 1 taken 48 times.
 4440 for (size_t i = 0; i < a_rows_; ++i) {
64
2/2
✓ Branch 0 taken 1048536 times.
✓ Branch 1 taken 4392 times.
 1052928 for (size_t j = 0; j < b_cols_; ++j) {
65 1048536 out[(i * b_cols_) + j] = result_c_[(i * padded_n_) + j];
66 }
67 }
68 48 return true;
69 }
70
71 48 bool TabalaevAMatrixMulStrassenSEQ::PostProcessingImpl() {
72 48 return true;
73 }
74
75 5472 std::vector<double> TabalaevAMatrixMulStrassenSEQ::Add(const std::vector<double> &mat_a,
76 const std::vector<double> &mat_b) {
77 5472 std::vector<double> res(mat_a.size());
78
2/2
✓ Branch 0 taken 9142272 times.
✓ Branch 1 taken 5472 times.
 9147744 for (size_t i = 0; i < mat_a.size(); ++i) {
79 9142272 res[i] = mat_a[i] + mat_b[i];
80 }
81 5472 return res;
82 }
83
84 3648 std::vector<double> TabalaevAMatrixMulStrassenSEQ::Subtract(const std::vector<double> &mat_a,
85 const std::vector<double> &mat_b) {
86 3648 std::vector<double> res(mat_a.size());
87
2/2
✓ Branch 0 taken 6094848 times.
✓ Branch 1 taken 3648 times.
 6098496 for (size_t i = 0; i < mat_a.size(); ++i) {
88 6094848 res[i] = mat_a[i] - mat_b[i];
89 }
90 3648 return res;
91 }
92
93 5520 std::vector<double> TabalaevAMatrixMulStrassenSEQ::BaseMultiply(const std::vector<double> &mat_a,
94 const std::vector<double> &mat_b, size_t n) {
95 5520 std::vector<double> res(n * n, 0.0);
96
2/2
✓ Branch 0 taken 175936 times.
✓ Branch 1 taken 5520 times.
 181456 for (size_t i = 0; i < n; ++i) {
97
2/2
✓ Branch 0 taken 5624064 times.
✓ Branch 1 taken 175936 times.
 5800000 for (size_t k = 0; k < n; ++k) {
98
2/2
✓ Branch 0 taken 179897344 times.
✓ Branch 1 taken 5624064 times.
 185521408 for (size_t j = 0; j < n; ++j) {
99 179897344 res[(i * n) + j] += mat_a[(i * n) + k] * mat_b[(k * n) + j];
100 }
101 }
102 }
103 5520 return res;
104 }
105
106 912 void TabalaevAMatrixMulStrassenSEQ::PushStrassenSubtasks(std::stack<StrassenFrame> &frames,
107 const std::vector<double> &mat_a,
108 const std::vector<double> &mat_b, size_t n) {
109 912 size_t h = n / 2;
110 912 size_t sz = h * h;
111 912 std::vector<double> a11(sz);
112
1/4
✓ Branch 1 taken 912 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 912 std::vector<double> a12(sz);
113
1/4
✓ Branch 1 taken 912 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 912 std::vector<double> a21(sz);
114
1/4
✓ Branch 1 taken 912 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 912 std::vector<double> a22(sz);
115
1/4
✓ Branch 1 taken 912 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 912 std::vector<double> b11(sz);
116
1/4
✓ Branch 1 taken 912 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 912 std::vector<double> b12(sz);
117
1/4
✓ Branch 1 taken 912 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 912 std::vector<double> b21(sz);
118
1/4
✓ Branch 1 taken 912 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 912 std::vector<double> b22(sz);
119
120
2/2
✓ Branch 0 taken 34304 times.
✓ Branch 1 taken 912 times.
 35216 for (size_t i = 0; i < h; ++i) {
121
2/2
✓ Branch 0 taken 1523712 times.
✓ Branch 1 taken 34304 times.
 1558016 for (size_t j = 0; j < h; ++j) {
122 1523712 size_t idx_src = (i * n) + j;
123 1523712 size_t idx_dst = (i * h) + j;
124 1523712 a11[idx_dst] = mat_a[idx_src];
125 1523712 a12[idx_dst] = mat_a[idx_src + h];
126 1523712 a21[idx_dst] = mat_a[idx_src + (h * n)];
127 1523712 a22[idx_dst] = mat_a[idx_src + (h * n) + h];
128
129 1523712 b11[idx_dst] = mat_b[idx_src];
130 1523712 b12[idx_dst] = mat_b[idx_src + h];
131 1523712 b21[idx_dst] = mat_b[idx_src + (h * n)];
132 1523712 b22[idx_dst] = mat_b[idx_src + (h * n) + h];
133 }
134 }
135
136
1/2
✓ Branch 1 taken 912 times.
✗ Branch 2 not taken.
 1824 frames.push({{}, {}, n, 1});
137
138 912 frames.push({Subtract(a12, a22), Add(b21, b22), h, 0});
139 912 frames.push({Subtract(a21, a11), Add(b11, b12), h, 0});
140 912 frames.push({Add(a11, a12), b22, h, 0});
141 912 frames.push({a22, Subtract(b21, b11), h, 0});
142 912 frames.push({a11, Subtract(b12, b22), h, 0});
143 912 frames.push({Add(a21, a22), b11, h, 0});
144
1/4
✓ Branch 1 taken 912 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 912 frames.push({Add(a11, a22), Add(b11, b22), h, 0});
145
21/42
✓ Branch 1 taken 912 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 912 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 912 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 912 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 912 times.
✗ Branch 14 not taken.
✓ Branch 16 taken 912 times.
✗ Branch 17 not taken.
✓ Branch 19 taken 912 times.
✗ Branch 20 not taken.
✓ Branch 22 taken 912 times.
✗ Branch 23 not taken.
✓ Branch 25 taken 912 times.
✗ Branch 26 not taken.
✓ Branch 28 taken 912 times.
✗ Branch 29 not taken.
✓ Branch 31 taken 912 times.
✗ Branch 32 not taken.
✓ Branch 34 taken 912 times.
✗ Branch 35 not taken.
✓ Branch 37 taken 912 times.
✗ Branch 38 not taken.
✓ Branch 40 taken 912 times.
✗ Branch 41 not taken.
✓ Branch 43 taken 912 times.
✗ Branch 44 not taken.
✓ Branch 46 taken 912 times.
✗ Branch 47 not taken.
✓ Branch 49 taken 912 times.
✗ Branch 50 not taken.
✓ Branch 52 taken 912 times.
✗ Branch 53 not taken.
✓ Branch 55 taken 912 times.
✗ Branch 56 not taken.
✓ Branch 58 taken 912 times.
✗ Branch 59 not taken.
✓ Branch 61 taken 912 times.
✗ Branch 62 not taken.
 7296 }
146
147
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 912 times.
 912 std::vector<double> TabalaevAMatrixMulStrassenSEQ::CombineStrassenResults(std::stack<std::vector<double>> &results,
148 size_t n) {
149 auto p7 = std::move(results.top());
150 results.pop();
151 auto p6 = std::move(results.top());
152 results.pop();
153 auto p5 = std::move(results.top());
154 results.pop();
155 auto p4 = std::move(results.top());
156 results.pop();
157 auto p3 = std::move(results.top());
158 results.pop();
159 auto p2 = std::move(results.top());
160 results.pop();
161 auto p1 = std::move(results.top());
162 results.pop();
163
164 912 size_t h = n / 2;
165
1/4
✓ Branch 1 taken 912 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 912 std::vector<double> res(n * n);
166
2/2
✓ Branch 0 taken 34304 times.
✓ Branch 1 taken 912 times.
 35216 for (size_t i = 0; i < h; ++i) {
167
2/2
✓ Branch 0 taken 1523712 times.
✓ Branch 1 taken 34304 times.
 1558016 for (size_t j = 0; j < h; ++j) {
168 1523712 size_t idx = (i * h) + j;
169 1523712 res[(i * n) + j] = p1[idx] + p4[idx] - p5[idx] + p7[idx];
170 1523712 res[(i * n) + j + h] = p3[idx] + p5[idx];
171 1523712 res[((i + h) * n) + j] = p2[idx] + p4[idx];
172 1523712 res[((i + h) * n) + j + h] = p1[idx] - p2[idx] + p3[idx] + p6[idx];
173 }
174 }
175 912 return res;
176 }
177
178 48 std::vector<double> TabalaevAMatrixMulStrassenSEQ::StrassenMultiply(const std::vector<double> &mat_a,
179 const std::vector<double> &mat_b, size_t n) {
180 std::stack<StrassenFrame> frames;
181 std::stack<std::vector<double>> results;
182
183 48 frames.push({mat_a, mat_b, n, 0});
184
185
2/2
✓ Branch 0 taken 7344 times.
✓ Branch 1 taken 48 times.
 7392 while (!frames.empty()) {
186 StrassenFrame current = std::move(frames.top());
187 frames.pop();
188
189
2/2
✓ Branch 0 taken 6432 times.
✓ Branch 1 taken 912 times.
 7344 if (current.stage == 0) {
190
2/2
✓ Branch 0 taken 5520 times.
✓ Branch 1 taken 912 times.
 6432 if (current.n <= 32) {
191
1/2
✓ Branch 1 taken 5520 times.
✗ Branch 2 not taken.
 11040 results.push(BaseMultiply(current.mat_a, current.mat_b, current.n));
192 } else {
193
1/2
✓ Branch 1 taken 912 times.
✗ Branch 2 not taken.
 912 PushStrassenSubtasks(frames, current.mat_a, current.mat_b, current.n);
194 }
195 } else {
196
1/2
✓ Branch 1 taken 912 times.
✗ Branch 2 not taken.
 1824 results.push(CombineStrassenResults(results, current.n));
197 }
198 7344 }
199
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 96 return results.top();
200
3/6
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 48 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 48 times.
✗ Branch 8 not taken.
 48 }
201 } // namespace tabalaev_a_matrix_mul_strassen
202