Packing Sparse Convolutional Neural Networks for Efficient Systolic Array Implementations: Column Combining Under Joint Optimization

H. T. Kung; Bradley McDanel; Sai Qian Zhang

Source-linked AI summary

Packing Sparse Convolutional Neural Networks for Efficient Systolic Array Implementations: Column Combining Under Joint Optimization

H. T. Kung, Bradley McDanel, Sai Qian Zhang

arXiv:1811.04770v1Nov 7, 2018cs.LGcs.ARstat.ML

TL;DR

Sparse CNN weights are difficult to map efficiently onto regular systolic arrays. The paper combines filter-matrix columns, prunes conflicting weights, and retrains iteratively to jointly improve utilization and accuracy, achieving approximately 4× higher utilization and reported gains in energy efficiency and latency.

Problem
Unstructured sparse CNN weights are not directly amenable to efficient implementation on systolic arrays designed for dense matrix multiplication.
Method
Column combining jointly optimizes CNN classification accuracy and systolic-array utilization through iterative pruning, packing, and retraining.
Results
Approximately 4× higher systolic-array utilization, 3× energy efficiency, and 12× inference latency performance are reported against prior art.
Takeaways & Limitations
Column combining transforms sparse computations to fit regular systolic arrays while retaining classification accuracy through retraining.
Takeaways & Limitations
The implementation uses 8-bit inputs and weights with 32-bit integer accumulation, adding complexity to the bit-serial systolic-array design.

Abstract

from arXiv · show

This paper describes a novel approach of packing sparse convolutional neural networks for their efficient systolic array implementations. By combining subsets of columns in the original filter matrix associated with a convolutional layer, we increase the utilization efficiency of the systolic array substantially (e.g., ~4x) due to the increased density of nonzeros in the resulting packed filter matrix. In combining columns, for each row, all filter weights but one with the largest magnitude are pruned. We retrain the remaining weights to preserve high accuracy. We demonstrate that in mitigating data privacy concerns the retraining can be accomplished with only fractions of the original dataset (e.g., 10\% for CIFAR-10). We study the effectiveness of this joint optimization for both high utilization and classification accuracy with ASIC and FPGA designs based on efficient bit-serial implementations of multiplier-accumulators. We present analysis and empirical evidence on the superior performance of our column combining approach against prior arts under metrics such as energy efficiency (3x) and inference latency (12x).

1. Introduction

CNN accelerators use systolic arrays efficiently, but irregularly distributed sparse weights leave zero weights occupying array cells. The paper proposes column combining with retraining to jointly improve systolic-array utilization and preserve classification accuracy.

Systolic arrays provide parallel processing, regular processing-element layouts, efficient communication, and data reuse for CNN acceleration.
Weight pruning reduces CNN parameters and computation, but produces sparse weights whose irregular structure challenges systolic-array utilization.
Column combining packs sparse CNNs by pruning conflicting-row weights except the largest-magnitude weight, then retraining iteratively to recover accuracy.
The approach jointly optimizes CNN topology for systolic-array structure while preserving most classification accuracy through retraining.
The paper contributes column combining, privacy-aware retraining with fractions of the original dataset, row permutation, cross-layer pipelining, and ASIC/FPGA validation.

2. Background and Related Work

CNN convolution can be mapped to matrix multiplication on weight-stationary systolic arrays, while pruning and alternative convolution structures reduce computation but create mapping and quantization considerations. The background motivates hardware-aware packing for sparse CNN inference.

A convolutional layer’s computation can be expressed as matrix-matrix multiplication and mapped onto a weight-stationary systolic array.Weights remain stationary while inputs and accumulated results move through the array.
Systolic-array accelerator design emphasizes reducing off-chip memory accesses and reusing fetched weights, inputs, and intermediate results.
FPGAs support exploration of low-precision, novel-training, and pruning-based CNN designs, including validation against prior accelerator results.
Separable convolution replaces one standard convolution with depthwise and pointwise layers to reduce model size and computation, while pointwise filters omit spatial neighbors.
Pruning can remove up to 90% of weights in networks such as AlexNet and VGG-16 without impacting classification accuracy.
The paper’s iterative pruning gradually removes small-magnitude weights, producing layers with as low as 10% nonzero weights while maintaining baseline-like performance.
The proposed implementation quantizes inputs and weights to 8-bit fixed-point values while using 32-bit integer accumulation.

3. Column Combining

Column combining jointly optimizes sparse CNNs for classification accuracy and systolic-array utilization by grouping compatible columns, pruning conflicts, and retraining the remaining weights. Row permutation and cross-layer pipelining further support efficient data routing and lower latency.

3. Column Combining: Column combining jointly optimizes sparse CNNs for classification accuracy and systolic-array utilization during deployment.The iterative training procedure prunes and packs the network for the target systolic-array structure while retraining to preserve accuracy.
3.2. Column Combining Overview: Columns with limited conflicts are grouped and combined into one packed column, pruning all conflicting weights except the largest-magnitude weight per row.A group satisfies the limited-conflict condition when it has at most γ conflicts per row on average.
3.2. Column Combining Overview: The algorithm seeks few combined columns and high packed-column density while minimizing classification-accuracy loss.A dense-column-first policy favors groups producing high-density combined columns, with retraining applied after pruning.
3.3. Column Combining Algorithm: The method iteratively performs initial pruning, column grouping, conflict pruning, and network retraining to improve systolic-array fit.Typical parameters are α = 8, β = 20, and γ = 0.5.
3.5. Row Permutation for Contiguous Column Groups: Row permutation places outputs needed by the next layer contiguously, reducing routing overhead after column combining.Without permutation, routing between arrays can require an expensive switchbox; permutation instead aligns grouped outputs.
3.6. Cross-layer Pipelining of CNN Inference: Cross-layer pipelining forwards each output element immediately to the next layer and reduces LeNet-5 ASIC inference latency by 3.5×.The approach is motivated by realtime settings where single-sample latency matters more than batch throughput.

4. Systolic Array System Description for Column Combining

The system implements column-combined CNN layers with weight-stationary, bit-serial systolic arrays. Its components support multiplexed inputs, high-precision accumulation, shifting, ReLU, quantization, and inter-layer data movement.

System Components: The system loads layer weights into MX systolic cells and streams shifted input data from buffers for bit-serial matrix multiplication.Results pass through ReLU and quantization before being stored for subsequent processing.
Bit-serial MAC: The bit-serial MAC multiplies 8-bit inputs by signed 8-bit weights and accumulates products into the partial result.Absolute-value multiplication, sign handling, and bit-serial addition are implemented by separate logic elements.
Bit-serial Systolic Arrays: 32-bit accumulation creates a 24-clock gap between input words, which can be filled by interleaving four independent streams with 4× expanded processing and accumulation paths.This design addresses the longer computation time required for high-precision accumulation.
MX Cells: MX cells accept inputs from multiple channels, use the appropriate input in each MAC, and forward the inputs upward through the array.The ASIC and FPGA designs pack up to 8 inputs into one cell, reducing per-cycle input requirements compared with bit-parallel operation.
Data Movement and Activation: Row permutation makes grouped input channels contiguous, while shift and ReLU blocks prepare streamed inputs and suppress negative 32-bit outputs before requantization.Double buffering overlaps next-tile prefetch with input transfer, and ReLU output can feed the following layer.

5. Performance Analysis for the Column Combining Algorithm

Performance analysis evaluates iterative column-combining training and its effects on utilization, accuracy, and systolic-array tiling. Across ResNet-20 experiments, combining increases packed density and substantially reduces the tiles required for matrix multiplication.

Evaluation Setup: The evaluation uses MNIST and CIFAR-10 with LeNet-5, VGG-16, and ResNet-20, replacing convolution layers with shift followed by pointwise convolution.These experiments assess the column-combining approach across multiple CNN architectures and datasets.
Iterative Training: Iterative pruning and retraining reduced ResNet-20 nonzero weights from 740K to 125K, while final training improved classification accuracy by an additional 5%.The first pruning iteration produced the largest reduction, from 740K to 440K nonzero weights.
Columns per Group: Utilization efficiency increased from under 20% at α = 1 to 90% at α = 8, with approximately a 1% classification-accuracy decrease.At α = 16, utilization did not improve further because remaining nonzero weights created more conflicts.
Limited-Conflict Condition: Utilization efficiency increased from 52% at γ = 0.1 to 93% at γ = 0.5, while classification accuracy changed by around 1%.Higher γ permits more conflicts and therefore more pruning, while retraining lets remaining weights adjust.
Partitioned Matrix Multiplication: Column combining transformed a 16%-nonzero, 9-tile filter matrix into an 89%-nonzero packed matrix requiring 3 tiles on a 32×32 array.The example arranged 94 original columns into 17 packed groups, producing a 3× tile reduction.

6. Column Combining with Limited Datasets

The paper examines column combining when vendors receive pretrained models but not the original training data. Using a subset of the data for iterative pruning and retraining can preserve relatively high accuracy, especially for pretrained models.

Data Privacy Constraint: Pruning without retraining significantly degrades classification accuracy, making sparse-model deployment difficult when customers withhold sensitive or proprietary training data.This setting motivates using only a subset of the original dataset for retraining.
Limited-Data Retraining: A pretrained ResNet-20 exceeded 90% classification accuracy using 15% of the full CIFAR-10 training data for column combining.At 1% of the data, the pretrained and newly trained approaches differed most, by 15% classification accuracy.
Pretrained versus New Models: A newly trained network required 35% of the CIFAR-10 training dataset to exceed 90% classification accuracy, compared with 15% for the pretrained model.The comparison indicates that pretrained weights can support column combining with less retraining data.

7. Hardware Implementation Experiments and Performance Evaluation

The hardware evaluation compares column-combining systolic-array designs with baselines and prior ASIC/FPGA accelerators, measuring accuracy, throughput, area efficiency, energy efficiency, and latency. Column combining reduces tiles and energy while improving throughput, and cross-layer pipelining substantially reduces single-sample latency.

Evaluation setup: The evaluation compares ASIC and FPGA implementations using accuracy, throughput, area efficiency, energy efficiency, and single-sample latency.ASIC experiments include LeNet-5, VGG-16, and ResNet-20; FPGA experiments include ResNet-20 on CIFAR-10.
ASIC evaluation: 4× to 6× reductions in energy consumption and required tiles accompany 3× to 4× greater throughput for column-combine pruning across three CNN structures.Figure 16 reports these comparisons across the evaluated parameter settings.
ASIC comparison with prior designs: 3× higher energy efficiency and 2.2× higher area efficiency than SC-DCNN type a are achieved by design 1 while also attaining higher classification accuracy.Design 2 exceeds SC-DCNN type b in classification accuracy, area efficiency by 1.4×, and energy efficiency by 1.7×.
Energy-efficiency analysis: 94.5% of optimal energy efficiency is achieved at γ = 0.5 with about 0.7% absolute classification-accuracy degradation when r is small.The analysis connects this near-optimal result to approximately 94.5% packing efficiency.
FPGA evaluation: 93.1% accuracy and 3× higher energy efficiency than the next-best design are reported for the FPGA ResNet-20 implementation on CIFAR-10.The reported accuracy is around 5–6% higher than other models.
Cross-layer pipelining: 3.5× and 9.3× latency reductions are obtained for LeNet-5 and ResNet-20, respectively, with cross-layer pipelining.The pipelined ResNet-20 design also achieves end-to-end latency over 12× smaller than the next-best implementation while attaining higher classification accuracy.

8. Conclusion

The paper addresses inefficient sparse computation on regular systolic arrays by combining filter-matrix columns and retraining the resulting network. This joint optimization increases array utilization and delivers higher energy efficiency and lower inference latency than prior designs.

Conclusion: Column combining packs sparse CNN filter matrices by retaining the largest-magnitude weight on each conflicting row and retraining the pruned network.The column-combining and network-retraining steps are iterated to improve both systolic-array utilization and classification accuracy.
Conclusion: Approximately 4× higher systolic-array utilization leads to 3× higher energy efficiency and 12× lower inference latency than prior approaches.The approach requires a slight increase in systolic-cell complexity to provide multiplexing support.