Efficient Convolution Operation

Regular Convolution

Sliding window over the image and do multi-adds on patch level one by one.

Image to Column Convolution

To better utilize CPU cache and the locality of reference, we convert convolution operations into matrix multiplication.

The Locality of Reference (Principal of Locality)

• Processor tendency to access the same set of memory locations repetitively

• Temporal locality: reuse of specific data/resources within a short time duration

• Spatial locality: use of data elements within relatively close storage locations

• The locality is a predictable behavior, upon which built systems are great candidates for performance optimization. Techniques like caching, memory prefetching, and processor core branch prediction can contribute to the optimization.

Winograd Convolution

Operations with g0 ~ g2 can be precalculated. Then, the convolution operation is saved from 6 MUL operations to only 4, with 1.5 times faster. For 2-d matrix convolutions, let's say 4x4 matrix with 3x3 convolution kernel, it can be saved from 2 * 2 * 9 = 35 MULs to 4 * 4 = 16 MULs with 2.25 times faster.

1-d Convolution

Extend it to 2d convolution

Reference

https://blog.usejournal.com/understanding-winograd-fast-convolution-a75458744ffblog.usejournal.com

https://zhuanlan.zhihu.com/p/72149270zhuanlan.zhihu.com

Locality of referenceWikipedia