Sliding Window Sum Algorithms for Deep Neural Networks
Roman Snytsar
Sliding window sums are widely used for string indexing, hashing and time
series analysis. We have developed a family of the generic vectorized sliding
sum algorithms that provide speedup of O(P/w) for window size $w$ and number of
processors P. For a sum with a commutative operator the speedup is improved to
O(P/log(w)). Even more important, our algorithms exhibit efficient memory
access patterns. In this paper we study the application of the sliding sum
algorithms to the training and inference of the Deep Neural Networks. We
demonstrate how both pooling and convolution primitives could be expressed as
sliding sums and evaluated by the compute kernels with the shared structure. We
show that the sliding sum convolution kernels are more efficient than the
commonly used GEMM kernels on the CPU, and could even outperform their GPU
counterparts.