In one sense Deep Neural Networks (DNNs) are counterintuitive. Despite representing a complex function with thousands and even millions of parameters, a DNN's network structure ensures that this function is a composition of many similar, simpler functions. However, notice that the "atomic operation" in this computation is not the dot product nor the matrix product but what is known in the language of digital signal processing as the multiply-add operation Most processors built to do any kind of digital signal processing include dedicated multiply-accumulate (MAC) units which implement the fused-multiply-add (FMA) operation, where fused simply means that the operation uses only one rounding step. When a DNN model includes thousands or millions of weights, a processor must perform millions of FMA operations to evaluate the model on a single data point. Note however that the FMA operation is moot if one or both of b and c is zero; their product is zero, thus a may remain unchanged.

Our community has greatly improved the efficiency of deep learning applications, including by exploiting sparsity in inputs. Most of that work, though, is for inference, where weight sparsity is known statically, and/or for specialized hardware. We propose a scheme to leverage dynamic sparsity during training. In particular, we exploit zeros introduced by the ReLU activation function to both feature maps and their gradients. This is challenging because the sparsity degree is moderate and the locations of zeros change over time. We also rely purely on software. We identify zeros in a dense data representation without transforming the data and performs conventional vectorized computation. Variations of the scheme are applicable to all major components of training: forward propagation, backward propagation by inputs, and backward propagation by weights. Our method significantly outperforms a highly-optimized dense direct convolution on several popular deep neural networks. At realistic sparsity, we speed up the training of the non-initial convolutional layers in VGG16, ResNet-34, ResNet-50, and Fixup ResNet-50 by 2.19x, 1.37x, 1.31x, and 1.51x respectively on an Intel Skylake-X CPU.