Repository navigation
Expand file tree
/
Copy pathconvolution.cpp
More file actions
94 lines (82 loc) · 4.31 KB
/
Copy pathconvolution.cpp
File metadata and controls
94 lines (82 loc) · 4.31 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// convolution.cpp — naive sliding window vs. im2col + GEMM.
//
// Python equivalent: scipy.signal.correlate2d(input, kernel, mode='valid')
// for the naive version; torch.nn.functional.conv2d for the im2col path
// (which is, internally, exactly this unfold-then-matmul).
#include "cppml/convolution.hpp"
#include <stdexcept>
namespace cppml {
namespace {
// Output spatial size for a given input/kernel/stride/pad along one axis.
std::size_t out_dim(std::size_t in, std::size_t k, std::size_t stride, std::size_t pad) {
if (in + 2 * pad < k) throw std::invalid_argument("conv2d: kernel larger than padded input");
return (in + 2 * pad - k) / stride + 1;
}
// Read input(y, x) with implicit zero-padding outside the real image.
float padded_at(const Matrix& in, long y, long x) {
if (y < 0 || x < 0 || y >= static_cast<long>(in.rows) || x >= static_cast<long>(in.cols))
return 0.0f;
return in.at(static_cast<std::size_t>(y), static_cast<std::size_t>(x));
}
} // namespace
Matrix conv2d_naive(const Matrix& input, const Matrix& kernel,
std::size_t stride, std::size_t pad) {
const std::size_t oh = out_dim(input.rows, kernel.rows, stride, pad);
const std::size_t ow = out_dim(input.cols, kernel.cols, stride, pad);
Matrix out(oh, ow, 0.0f);
// For each output pixel, dot the kernel against its receptive field. Simple
// and correct, but the inner two loops recompute padded addressing every
// time and never reduce to a GEMM the hardware can accelerate.
for (std::size_t oy = 0; oy < oh; ++oy)
for (std::size_t ox = 0; ox < ow; ++ox) {
float acc = 0.0f;
const long base_y = static_cast<long>(oy * stride) - static_cast<long>(pad);
const long base_x = static_cast<long>(ox * stride) - static_cast<long>(pad);
for (std::size_t ky = 0; ky < kernel.rows; ++ky)
for (std::size_t kx = 0; kx < kernel.cols; ++kx)
acc += padded_at(input, base_y + static_cast<long>(ky),
base_x + static_cast<long>(kx)) *
kernel.at(ky, kx);
out.at(oy, ox) = acc;
}
return out;
}
Matrix im2col(const Matrix& input, std::size_t kh, std::size_t kw,
std::size_t stride, std::size_t pad) {
const std::size_t oh = out_dim(input.rows, kh, stride, pad);
const std::size_t ow = out_dim(input.cols, kw, stride, pad);
// One row per output position; that row is the flattened receptive field.
Matrix cols(oh * ow, kh * kw, 0.0f);
for (std::size_t oy = 0; oy < oh; ++oy)
for (std::size_t ox = 0; ox < ow; ++ox) {
const std::size_t row = oy * ow + ox;
const long base_y = static_cast<long>(oy * stride) - static_cast<long>(pad);
const long base_x = static_cast<long>(ox * stride) - static_cast<long>(pad);
for (std::size_t ky = 0; ky < kh; ++ky)
for (std::size_t kx = 0; kx < kw; ++kx)
cols.at(row, ky * kw + kx) =
padded_at(input, base_y + static_cast<long>(ky),
base_x + static_cast<long>(kx));
}
return cols;
}
Matrix conv2d_im2col(const Matrix& input, const Matrix& kernel,
std::size_t stride, std::size_t pad) {
const std::size_t oh = out_dim(input.rows, kernel.rows, stride, pad);
const std::size_t ow = out_dim(input.cols, kernel.cols, stride, pad);
// 1. Unfold receptive fields -> (oh*ow, kh*kw).
const Matrix cols = im2col(input, kernel.rows, kernel.cols, stride, pad);
// 2. Flatten the kernel to a (kh*kw, 1) column.
Matrix kflat(kernel.rows * kernel.cols, 1, 0.0f);
for (std::size_t i = 0; i < kernel.data.size(); ++i) kflat.data[i] = kernel.data[i];
// 3. The whole convolution is now one matmul: (oh*ow, kh*kw) x (kh*kw, 1).
// This is the im2col trick — trade the extra memory of `cols` for the
// ability to run a single, highly-optimized GEMM. It's exactly how cuDNN
// and PyTorch's CPU path implement convolution under the hood.
const Matrix result = matmul_cache_friendly(cols, kflat);
// 4. Reshape the (oh*ow, 1) result back to a 2D feature map.
Matrix out(oh, ow, 0.0f);
for (std::size_t i = 0; i < oh * ow; ++i) out.data[i] = result.data[i];
return out;
}
} // namespace cppml