Sliding Window Sum Algorithms for Deep Neural Networks


Roman Snytsar, Microsoft, United States of America


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 sliding sum algorithms to the training and inference of Deep Neural Networks. We demonstrate how both pooling and convolution primitives could be expressed as sliding sums and evaluated by the compute kernels with a shared structure. We show that the sliding sum convolution kernels are more efficient than the commonly used GEMM kernels on CPUs and could even outperform their GPU counterparts.


Convolution, Machine Learning, Parallel, Vector.