SBNet: Sparse Blocks Network for Fast Inference

Conventional deep convolutional neural networks (CNNs) apply convolution operators uniformly in space across all feature maps for hundreds of layers - this incurs a high computational cost for real time applications. For many problems such as object detection and semantic segmentation, we are able to obtain a low-cost computation mask, either from a priori problem knowledge, or from a low resolution segmentation network. We show that such computation masks can be used to reduce computation in the high resolution main network. Variants of sparse activation CNNs have previously been explored on small scale tasks, and showed no degradation in terms of object classification accuracy, but often measured gains in terms of theoretical FLOPs without realizing a practical speed-up when compared to highly optimized dense convolution implementations. In this work, we leverage the sparsity structure of computation masks and propose a novel tiling-based sparse convolution algorithm. We verified the effectiveness of our sparse CNN on LiDAR based 3D object detection, and we report significant wall-clock speed-ups compared to dense convolution, as well as improved detection accuracy.


Introduction
Deep convolutional neural networks (CNNs) have led to major breakthroughs in many computer vision tasks [17]. While model accuracy consistently improves with the number of layers [8], as current standard networks use over a hundred convolution layers, the amount of computation involved in deep CNNs can be prohibitively expensive for real-time applications such as autonomous driving.
Spending equal amount of computation at all spatial locations is a tremendous waste, since spatial sparsity is ubiquitous in many applications: in autonomous driving, only the areas on the road matter for object detection; in video * Equal contribution. segmentation, only occluded and fast moving pixels require recomputation; in 3D object classification [29], sparsity is directly encoded in the inputs as voxel occupancy.
In these examples, spatial sparsity can be represented as binary computation masks where ones indicate active locations that need more computation and zeros inactive. In cases where such masks are not directly available from the inputs, we can predict them in the form of visual saliency [12] or objectness prior [16] by using another relatively cheap network or even a part of the main network itself [2,20]. These binary computation masks can be efficiently incorporated into the computation of deep CNNs: instead of convolving the input features at every location, we propose to use the masks to guide the convolutional filters. Computation masks can also be considered as a form of attention mechanism where the attention weights are binary. While most current uses of attention in computer vision has been predominantly targeted at better model interpretability and higher prediction accuracy, our work highlights the benefit of attentional inference speed-up.
In this work, we leverage structured sparsity patterns of computation masks and propose Sparse Block's Networks (SBNet), which computes convolution on a blockwise decomposition of the mask. We implemented our proposed sparse convolution kernels (fragments of parallel code) on graphics processing unit (GPU) and we report wall-clock time speed-up compared against state-of-the-art GPU dense convolution implementations. Our algorithm works well with popular residual network (ResNet) architectures [8] and produces further speed-up when integrated within a residual unit.
Our sparse block unit can serve as a computational module in almost all deep CNNs for various applications involving sparse regions of interest, bringing inference speedup without sacrificing input resolution or model capacity. We evaluate the effectiveness of our SBNet on LiDAR 3D object detection tasks under a top-down bird's eye view, and we leverage both static road maps and dynamic attention maps as our computation masks. We found SBNet not only achieves significant inference speedup, but also improves detection accuracy compared to dense CNN baselines.

Related work
Sparse computation in deep learning has been extensively explored in the weights domain, where the model size can be significantly reduced through pruning and low-rank decomposition [13,22,7,27,19,10]. However it is not trivial to achieve huge speed-up from sparse filters without loss of accuracy because a single filter channel is rarely very close to zero at every point. [19] explored structured sparsity by pruning an entire filter at the expense of worse network accuracy. Based on these reasons, most of current approaches to speedup deep neural networks leverage other redundancies such as weight quantization [33,1], teacherstudent network compression [9], etc.
On the other end, in the activation domain, sparsity was also explored in various forms. Recitified linear unit (ReLU) activations contain more than 50% zero's on average and speed-up can be realized on both hardware [15] and algorithmic level [25]. Structured sparsity patterns are often present in applications such as 3D object classification. OctNet [24] introduces novel sparse high-resolution 3D representation for 3D object recognition. Different from [24], [6] proposes a generic valid sparse convolution operator where the input density mask is applied everywhere in the network. As we will discuss later, while [6] implements a generic convolution operator, it is not suitable for moderately large input sizes.
When the inputs contain no structured sparsity, one can obtain dynamic computation masks during the inference process over hundreds of layers. [2] learns to skip an adaptive number of layers in ResNet for unimportant regions in object classification tasks. Similarly, [20] infers a pixel-wise mask for reweighting the computation in the context of semantic segmentation. [16] predicts objectness prior heat maps during network inference for more accurate object detection, but the heat maps do not help speed-up the inference process; instead the authors resort downsampled inputs for faster inference. Given the vast availability of those computation masks and heat maps during inference, our proposed sparse convolution operators can be jointly applied to achieve major speedup gains on full resolution.
Sparse inference is beneficial to accuracy as the network focuses more of it's computational attention on useful activation patterns and ignores more of the background noise. For instance, sparse batch normalization (BN) [11,26] is invariant to input sparsity level, and outperforms regular BN in optical flow tasks. Here, we exploited the benefit of sparse BN within our sparse residual units. [3] proposes sparse perforated convolution to increase the receptive field and achieve better classification accuracy.
Sparse computation masks are related to attention mechanism, where the attention weights are binary. Prior work applied visual attention on convolutional features and obtained better model interpretability and accuracy on tasks such as image captioning [30], visual question answering [31,23], etc. However, unlike human attention which helps us reason visual scenes faster, these attentional network structures do not speed up the inference process since the attention weights are dense across the receptive field. Our work lives in the best of both worlds by having fast sparse attentional inference with improved model accuracy.
Comparison with im2col based sparse convolution algorithms Here we discuss the main differences of our approach compared to popular sparse convolution algorithms based on matrix lowering, as seen in [22,25]. These methods all use the same type of matrix lowering which we refer as im2col. Widely known in the implementation of dense convolution in Caffe [14], im2col gathers sliding windows of shape k H × k W × C, where k H × k W is the filter window size and C is the input channel count. B active windows are then reshaped into rows of a matrix of shape B × (k H × k W × C), and multiply with a lowered filter matrix with shape (k H × k W × C) × K, where K is the number of filters. This method is often faster than sparse matrix-vector product due to contiguous memory access and better parallelism. However, these methods introduce memory overhead and cannot leverage the benefits of Winograd convolutions [28,18]. Further, writing out the intermediate lowered results introduces additional memory bandwidth overhead. [6] designed a lookup table based data structure for storing sparsity, but it is still slower when compared to highly optimized Winograd convolutions. Our approach differs from [6,20,25] in that we gather block-wise slices from tensors and maintain the tensor shape instead of lowering them to vectors. Within each active block, we perform a regular dense convolution, and exploit the 2−3× further speedup from using Winograd convolution [28,18] compared to general matrix-matrix multiplication (GEMM).

SBNet: Sparse Blocks Network
In this paper we show that block sparsity can be exploited to significantly reduce the computational complexity of convolutional layers in deep neural networks. Unlike previous work taking advantage of unstructured sparsity, we show that our approach results in both theoretical and practical speed-up without loss of accuracy. We observe that many input sources have structured sparsity that meshes well with block sparsity -background pixels are likely to be surrounded by other background pixels. It stands to reason that computations for entire spatial clumps or 'blocks' of activations can be skipped.
Block sparsity is defined in terms of a mask that can be known upfront from the input data domain knowledge or a priori sparsity structure or can be computed using lower cost operations. In particular, we show the usefulness of our convolution algorithm on LiDAR object detection and we exploit the sparsity from the road and sidewalk map mask and model predicted foreground mask at lowerresolution. For speed-up purposes, the same sparsity mask is reused for every layer in our experiments, but it can also be computed from a different source per layer. In particular at different spatial scales within the network we also use reduced spatial block sizes to better match the granularity of spatial activations at that scale.
The inputs to our sparse convolution module is a dense binary mask. Just like other standard sparse operations, we first need to extract a list of active location indices, which we refer as the reduce mask operation. Then, we would like to extract data from the sparse inputs at specified locations, and paste the computed results back to the original tensor. To summarize, there are two major building blocks in our approach to sparse block-wise convolution: 1. Reduce mask to indices: converts a binary mask to a list of indices, where each index references the location of the corresponding n-dimensional block in the input tensor and in our current implementation this is a 3d block where indices are shared across the channel dimension (see Figure 2).
2. Sparse gather/scatter: For gathering we extract a block from the input tensor, given the start location and the size of the n-d block. Scatter is the inverse operation where we update the output tensor using previously gathered and transformed data and the same index list as we used during the gather phase.
In this section, we first go over details of the above two building blocks, and then we introduce sparse blocks residual unit which groups several layers of computation into sparse blocks. Then follows implementation details that are crucial for achieving a practical speed-up.

Reduce mask to indices
We start with a feature map of size H × W × C. We will demonstrate this for the case of 2D convolutions but the approach is applicable to higher dimensions. Let M ∈ {0, 1} H×W be the binary mask representing the sparsity pattern. We would like to take advantage of non-sparse convolution operations as they have been heavily optimized. With this in mind we propose to tile the sparse indices with a set of rectangles. Unfortunately, covering any binary shape with a minimal number of rectangles is an NP-complete problem [4]. Furthermore, using rectangles of different shapes is not hardware friendly because of difficulty of balancing the computational load of parallel processors for non-uniform input and output sizes. Therefore, we chose to have a uniform block size, so that the gathered blocks can be batched together and passed into a single dense convolution operation.
In signal processing "overlap-add" and "overlap-save" are two standard partitioning schemes for performing convolutions with very long input signals [5]. Our sparse tiling algorithm is an instantiation of the "overlap-save" algorithm where we gather overlapping blocks, but during the scatter stage, each thread writes to non-overlapping blocks so that the writes do not require atomics locking and yield "gapless" equivalent results for adjacent blocks. Knowing the block sizes and overlap sizes, we can perform a simple pooling operation, such as maximum or average pooling followed by a threshold to downsample the input mask. The resulting non-zero locations are the spatial block locations that we extract the patches from. Figure 3 illustrates our tiling algorithm.

Sparse gather/scatter
Sparse gather/scatter operations convert the network between dense and sparse modes.
Unlike regular  gather/scatter kernels that are implemented in deep learning libraries (e.g. tf.gather nd, tf.scatter nd), our proposed kernels not only operates on dense indices but also expands spatially to their neighborhood windows. Patch extracting operations (e.g. tf.space to batch, tf.batch to space) also share some similarities with our approach but lack spatial overlap and indexing capability. This input overlap is essential to producing the output that seamlessly stitches the results of adjacent block convolutions in a way that is locally-equivalent to a dense convolution on a larger block (as we will show in the next section) and fused indexing capability is critical to practical speed-up. Here, we introduce the technical details of our proposed gather and scatter operations.
Gather kernel Given a list of indices of size [B, 3], each index referencing the center location of the non-sparse blocks, where B the number of the blocks, we then slice the blocks out of the 4-d N × H × W × C input tensor using h × w × C slices, and stack the B slices into a new tensor along the batch dimension, yielding a B × h × w × C tensor.
Scatter kernel Scatter is an operation inverse to gather, reusing the same input mask and block index list. The input to scatter kernel is a tensor of shape B × h × w × C. For a mini-network shown in Figure 1, h and w are computed according to the output size reduction following a single unpadded convolution (also known as valid convolution). This convolution is slotted between the scatter and gather operations. When this convolution has a kernel size of k h ×  Figure 4: A residual unit can be grouped into a sparse unit sharing one gather and scatter.
. In the scatter kernel, the results of convolution operation are then copied back on top of the dense activation tensor.

Sparse residual units
The ResNet architecture [8] is widely used in many stateof-the-art deep networks. Sparse residual unit was previously explored using Valid Sparse Convolution proposed in [6]. Our proposed sparse blocks convolution also integrates well with residual units. A single residual unit contains three convolutions, batch normalization and ReLU layers, all of which can be operated in sparse mode. The total increase in receptive field of a residual unit is the same as a single 3 × 3 convolution. Therefore, all 9 layers can share a single gathering and scattering operation without growing the overlap area between blocks. In addition to the computation savings, [26] showed that batch-normalizing across non-sparse elements contributes to better model accuracy since it ignores non-valid data that may introduce noise to the statistics. Figure 4 shows a computation graph of our sparse version of residual unit.
End-to-end training of SBNet is required since batch normalization (BN) statistics are different between full scale activations and dense-only activations. The gradient of a scatter operation is simply the gather operation with the same precomputed block indices executed on the next layers backpropagated gradient tensor and vice versa since gather/scatter act as a mask while backpropagating the gradient. When calculating the gradients of our overlapping gather operation, the scatter needs to perform atomic addition of gradients on the edges of overlapping tiles.

Implementation details
One of major contributions of this work is an implementation of our block convolution algorithm using custom CUDA kernels. As we will show in our experiments this results in signifcant speed up in terms of wall-clock time. This contrasts the literature, were only theoretical gains are reported [6]. In this section we detail the techniques necessary to achieve such speed-ups in practice.
Fused downsample and indexing kernel To minimize the intermediate outputs between kernels, we fused the downsample and indexing kernels into one. Inside each tile we compute a fused max or average pooling operation followed by writing out the block index into a sequential index array using GPU atomics to increment the block counter. Thus the input is a N ×H×W tensor and the output is a list of B×3 sparse indices referring to full channel slices within each block.

Fused transpose+gather and transpose+scatter kernels
When performing 2D spatial gather and scatter, we favour N HW C format because of channel memory locality: in N HW C format, every memory strip of size w × C is contiguous, whereas in N CHW format, only strips of size w are contiguous. Because cuDNN library runs faster with N CHW data layout for convolutions and batch normalization, our gather/scatter kernel also fuses the transpose from N HW C to N CHW tensor data layout inside the same CUDA kernel. This saves a memory round-trip from doing additional transpose operations and is instrumental to achieving a practical speed-up. Under this implementation, the gather kernel outputs tensor of shape B ×C ×h×w, and the scatter kernel takes tensor of shape B × C × h × w . In addition, using N HW C layout makes it so that using different block sizes that align at different spatial locations at residual block boundaries still yields memory-contiguous access minimizing the number of GPU DRAM transactions and maximizing the GPU memory bandwidth utilization.
Using N HW C also allows for memory-coalesced access for spatially perforated blocks that are still gathered into a spatially dense and uniform blocks as long as the number of spatially active pixels for each row and column in the gather perforation pattern adds up to h and w. So our gather-transpose technique is applicable to a "free" implementation of dilated convolutions as well as other perforation patterns.
Fused scatter-add kernel for residual blocks For ResNet architecture during inference, the input tensor can be reused for output so that an extra memory allocation is avoided and there is no need to wipe the output tensor to be all zeros. We implemented a fused kernel of 2D scatter and addition, where we only update the non-sparse locations by adding the convolution results back to the input tensor. If the convolution layer has stride larger than 1, we use the output tensor in the shortcut connection in ResNet architecture as the base tensor, and update nonsparse results on top.

Experiments
We validate our sparse blocks networks on our LiDAR 3D vehicle detection benchmark where the computation mask is available through offline road and sidewalk map information. In addition to using a static map-based mask, we also explored using dynamic attention masks with higher sparsity predicted by a small foreground segmentation network pretrained on dense box labels. We investigate two key aspects of our proposed model: 1) inference speedup compared to a dense deep CNN detector 2) change in detection accuracy brought by the use of sparse convolution.
Experiment environments For all of the experiments, we implemented and benchmarked in TensorFlow 1.2.1 using cuDNN 6.0. Because TensorFlow by default uses NHWC tensor format it incurs a lot of overhead due to transposes on the way in and out of each convolution (as well as BN and filters) compared to cuDNN's preferred NCHW format, we also implemented standard ResNet blocks in NCHW for a more fair comparison. We implemented custom TensorFlow Ops to interface with our CUDA kernels. For comparison with sub-manifold sparse convolution [6], we benchmark using their released PyTorch implementation, using the same version of cuDNN library. We use NVIDIA GTX 1080Ti for layerwise benchmark, and NVIDIA Titan XP for full network benchmark.
Choosing the optimal block sizes Smaller block sizes produce higher mask matching granularity at the expense of increased boundary overlap. Larger blocks have lower percentage of overlap, but depending on the feature map resolution, they are less usable due to their relative size to the total size of the feature map. To achieve the maximum speed-up we perform a search sweep over a range of block sizes to automatically pick the fastest-performing block decomposition.

Dataset
We use our internal Car3D LiDAR detection dataset that contains 14,278 training frames and 5,365 validation frames. We adopt a bird's eye view representation, so that we can leverage spatial sparsity as most of the objects of interest are on the road or sidewalk. Each frame contains LiDAR point cloud sparse data for a region of 40m×70.4m, with height ranging from -2m to 4m. We use discretization bin size 0.05m×0.05m×0.2m and convert the inputs to an intensity map of size 800×1400×33. Two extra bins on zdimension are designated to points outside the height range limit. Each frame of data has a corresponding crop of the road/sidewalk map, which is a top-down binary mask indicating which pixels belong to the road or the sidewalk (see Figure 5).

Model
3D object detector network We adopt a fully convolutional detector architecture that resembles [21]. Our model has a residual network backbone and one convolutional and two upsampling layers with skip connections. For the residual backbone part, it has 2 initial convolution layers (conv-1), followed by [3,6,6,3] residual units per residual block (conv-2 -conv-5), with channel depth [96,192,256,384], and 16× downsampled activation size at the top of the backbone network. Two extra upsampling (deconvolution) layers are appended to bring the outputs back to 4× downsampled size, with skip connections from the outputs of conv-4 and conv-3. Three branches of the outputs predict object classes, box sizes and orientations respectively. Our sparse residual blocks and sparse convolutions are applied on all layers.
Foreground mask network To predict foreground computation masks, we adopt a Pyramid Scene Parsing Network (PSPNet) [32] on a ResNet-18 architecture [8] at 8× downsampled input resolution. The network has no bottleneck layers and has one initial convolution layer, followed by [2,2,2,2] residual units per residual blocks, with channel depth [32,64,128,256]. The network is trained to predict dilated dense box pixel labels.

Experimental design
We first run standalone layerwise speed-up tests, and we compare our approach with theoretical speed-up, i.e. 1/(1sparsity), and the released implementation of sub-manifold sparse CNN [6] ("Sub-M"). Using the same activation size of our detector network, we test the speed-up on three types of masks: 1) Syncthetic masks generated using the top-left sub-region of input images to measure the practical upper bound on speed-up. 2) Road map masks obtained from our offline map data.
3) Predicted masks obtained from the outputs of PSPNet.
We compare detection accuracy with two baselines: 1) Dense: a dense network trained on all detection groudtruth. 2) Dense w/ Road Mask: a dense network trained on detection groundtruth within the road mask.
Our SBNets use computation masks from road and sidewalk maps and predicted masks, trained end-to-end with the same number of training steps as the dense baselines. A detailed set of training hyper-parameters of our object detector and mask network can be found in the Supplementary Material. Detection accuracy is evaluated with on-road vehicles only.

Results and Discussion
Inference speed-ups for single convolution layers and residual blocks are listed in Table 1  block sharing the sparse gather-transpose and sparse scattertranspose computation costs.
Notably, [6] is slower than dense convolution on most activation sizes and sparsity values, whereas our Sparse Blocks achieve much higher speed-up on large resolution sizes, highlighting the practical contributions of our algorithm as increasing number of real-time applications involve high resolution inputs and outputs. Figure 6 plots speed-up vs. sparisty on conv-2 residual blocks, for three types of different masks: synthetic, road map, and predicted. Road maps and predicted masks incur extra overhead compared to synthetic masks due to irregular shapes. Our method significantly closes the gap between real implementations and theoretical maximum, and does not slow down computation even at lower sparsity ratio such as 50-60%, which is the typically the least sparse road maps in our dataset. The computation masks output from the PSP network are 90% sparse on average, bringing up the speedup for all sparse layers (Table 3), compared to using road masks (Table 4), which are only 75% sparse on average. Table 5 reports detection accuracy on the validation set. Using road masks in the loss function seems helpful, as it directs important regions for learning. Importantly, with a  significant 2× speedup, SBNet contributes to another 2% gain in mAP compared to a dense network that uses road masks in the loss function, suggesting the usefulness of sparse convolution during inference. When using model predicted computation masks, we are able to reach 3× speedup, with detection accuracy slightly below our dense baseline.
Detection results of our SBNet detector are visualized in Figure 8. As shown, PSPNet produces much sparser regions of interest compared to road maps while maintaining relatively competitive detection accuracy. Many false negative instances have too few LiDAR points and are hard to detect even by a dense detector.
Finally, we benchmark the computation overhead introduced by the PSPNet in Table 6, which spends less than 4% of the time of a full dense pass of the detector network. SBNet and PSP combined together achieve 36% relative gain in speed compared to the Road Map counterpart. In addition to higher sparsity and speed-up, the predicted masks are much more flexible in areas without offline maps.

Dense
SBNet +Road SBNet +PSP Figure 8: A bird's eye view of our 3D vehicle detection results. Green boxes denote groundtruth and orange outputs. Blue regions denote sparse computation masks.

Conclusion and Future Work
In this work, we introduce the Sparse Blocks network which features fast convolution computation given a computation mask with structured sparsity. We verified significant wall-clock speed-ups compared to state-of-the-art dense convolution implementations. In LiDAR 3D detection experiments, we show both speed-up and improvement in detection accuracy using road map masks, and even higher speed-up using model predicted masks while trading off a small amount of accuracy. We expect our proposed algorithm to achieve further speed-up when used jointly with other orthogonal methods such as weights pruning, model quantization, etc. As future work, sparse blocks can be extended to a combination of different rectangle shapes (c.f. OctNet [24]) to get fine-grained mask representation, which can speed up inference with multi-scaled reasoning.