# Automatic Mapping of the Best-Suited DNN Pruning Schemes for Real-Time
Mobile Acceleration

Yifan Gong<EMAIL_ADDRESS>,  Geng Yuan  Northeastern
UniversityBostonMAUSA<EMAIL_ADDRESS>,  Zheng Zhan  Northeastern
UniversityBostonMAUSA<EMAIL_ADDRESS>,  Wei Niu  College of William
and MaryWilliamsburgVAUSA<EMAIL_ADDRESS>,  Zhengang Li  Northeastern
UniversityBostonMAUSA<EMAIL_ADDRESS>,  Pu Zhao  Northeastern
UniversityBostonMAUSA<EMAIL_ADDRESS>,  Yuxuan Cai  Northeastern
UniversityBostonMAUSA<EMAIL_ADDRESS>,  Sijia Liu  Michigan State
UniversityEast LansingMIUSA<EMAIL_ADDRESS>,  Bin Ren  College of William
and MaryWilliamsburgVAUSA<EMAIL_ADDRESS>,  Xue Lin  Northeastern
UniversityBostonMAUSA<EMAIL_ADDRESS>,  Xulong Tang  University of
PittsburghPittsburghPAUSA<EMAIL_ADDRESS>and  Yanzhi Wang  Northeastern
UniversityBostonMAUSA<EMAIL_ADDRESS>
###### Abstract.

Weight pruning is an effective model compression technique to tackle the
challenges of achieving real-time deep neural network (DNN) inference on
mobile devices. However, prior pruning schemes have limited application
scenarios due to accuracy degradation, difficulty in leveraging hardware
acceleration, and/or restriction on certain types of DNN layers. In this
paper, we propose a general, fine-grained structured pruning scheme and
corresponding compiler optimizations that are applicable to any type of DNN
layer while achieving high accuracy and hardware inference performance. With
the flexibility of applying different pruning schemes to different layers
enabled by our compiler optimizations, we further probe into the new problem
of determining the best-suited pruning scheme considering the different
acceleration and accuracy performance of various pruning schemes. Two pruning
scheme mapping methods, one is search-based and the other is rule-based, are
proposed to automatically derive the best-suited pruning regularity and block
size for each layer of any given DNN. Experimental results demonstrate that
our pruning scheme mapping methods, together with the general fine-grained
structured pruning scheme, outperform the state-of-the-art DNN optimization
framework with up to 2.48$\times$ and 1.73$\times$ DNN inference acceleration
on CIFAR-10 and ImageNet dataset without accuracy loss.

network pruning, mobile acceleration, neural architecture search

††copyright: acmcopyright††journal: TODAES††journalyear: 2021††journalvolume:
1††journalnumber: 1††article: 1††publicationmonth: 1††price: 15.00††doi:
10.1145/3495532††ccs: Computing methodologies Machine learning††ccs: Computing
methodologies Neural networks††ccs: Computing methodologies Machine learning
approaches††ccs: Computing methodologies Machine learning algorithms

##  1\. Introduction

Model compression techniques have been proposed to reduce the computation and
memory intensity without compromising accuracy (Wen et al., 2016; Guo et al.,
2016; Min et al., 2018; He et al., 2018; Zhang et al., 2018a, b; Li et al.,
2020a). It is a promising solution for achieving various practical deep
learning (DL)-based methods such as fingerprinting (Jian et al., 2021),
YOLO(Cai et al., 2021), super-resolution (Zhan et al., 2021), and speech
recognition (Dong et al., 2020) in real time on resource-limited platforms,
especially mobiles and embedded devices (Li et al., 2021; Zhao et al., 2020;
Niu et al., 2020a). Among the compression techniques, weight pruning (Wen et
al., 2016; Guo et al., 2016; Min et al., 2018; He et al., 2018, 2019) explores
and reduces the vast redundancy in the number of weights and results in
structural sparsity of DNN models with fewer memory references and power
consumption during inference.

The design of a weight pruning method includes two fundamental aspects, i.e.,
_pruning regularity_ and _pruning algorithm_. The former refers to the
structural characteristics of the DNNs after pruning, whereas the latter
determines the rule to identify the weights to be pruned. From the _pruning
regularity_ aspect, the widely adopted pruning schemes include unstructured
pruning, structured pruning, and pattern-based pruning. Specifically,
unstructured pruning is flexible to prune any weights and generally yields
promising accuracy. However, they are not compatible with hardware
accelerations due to the irregular computation after pruning (Han et al.,
2015; Guo et al., 2016; Liu et al., 2018). On the other hand, structured
pruning eliminates weights while maintaining a full matrix format. It is
hardware-friendly but suffers from notable accuracy degradation due to the
coarse-grained nature in pruning whole filters/channels (Min et al., 2018;
Zhuang et al., 2018; Zhu et al., 2018; Ma et al., 2020d; Zhao et al., 2019;
Liu et al., 2020). Recently proposed pattern-based pruning overcomes the
shortcomings of prior works by incorporating fine-grained structured pruning
in a hardware-aware fashion (Ma et al., 2020a; Niu et al., 2020b), with the
aid of compiler. However, pattern-based pruning is only applicable to
3$\times$3 convolutional (CONV) layers and is difficult to be generalized to
fully-connected (FC) layers and CONV layers with other kernel sizes. There
lacks a pruning regularity that is general and achieves high accuracy and
hardware performance simultaneously.

From the _pruning algorithm_ aspect, heuristic-based pruning was first
proposed in (Han et al., 2015) and gets improvements with more sophisticated
designed heuristics (Li et al., 2017; Luo et al., 2017; Yu et al., 2018;
Zhuang et al., 2018; He et al., 2019; Dong and Yang, 2019). Regularization-
based pruning (Wen et al., 2016; Zhang et al., 2018a; He et al., 2018; Ren et
al., 2019b; Li et al., 2019; Liu et al., 2019a; Yuan et al., 2019b; Yuan et
al., 2019a; Ma et al., 2019b; Li et al., 2020b; Gong et al., 2020; Ma et al.,
2020e), on the other hand, are more mathematics-oriented. Recent works (Zhang
et al., 2018a, b; Ren et al., 2019b; Li et al., 2019; Ma et al., 2020b)
achieve substantial weight reduction without hurting the accuracy by
leveraging Alternating Direction Methods of Multipliers (ADMM) with dynamic
regularization penalties, but these methods require the manual setting of the
compression rate for each layer.

To fully exploit the potential of the pruned models on mobile devices for
inference accelerations, it is necessary to incorporate compiler optimizations
to support efficient sparse computation and storage. However, state-of-the-art
compiler-based DNN execution frameworks such as TensorFlow-Lite (TFLite) (Ten,
[n.d.]), Alibaba Mobile Neural Network (MNN) (Ali, [n.d.]), and TVM (Chen et
al., 2018b) do not support sparse (pruned) model inference acceleration on the
mobile platforms, while the recent works PCONV (Ma et al., 2020a) and PatDNN
(Niu et al., 2020b) only have limited sparse inference support for 3$\times$3
CONV layers.

Apart from the individual limitations mentioned above, there is one additional
deficiency that prevents DNN models from taking full advantage of weight
pruning. Different pruning schemes result in different acceleration and
accuracy performance, but prior works simply apply the same pruning scheme to
the entire model, undermining the flexibility to select the best-suited
pruning scheme for each layer to achieve better accuracy and acceleration
performance.

This paper aims to overcome the above limitations of prior works. More
specifically, we make the following contributions towards a general, fine-
grained structured pruning scheme and two automatic pruning scheme mapping
methods.

For the pruning scheme part:

  * •

We propose a novel and general pruning regularity, block-based pruning for FC
layers and block-punched pruning for CONV layers with different kernel sizes,
that can achieve high accuracy and high hardware inference performance
simultaneously.

  * •

We adopt a reweighted dynamic regularization algorithm to derive the
structured sparsity with automatically determined compression rate for each
layer and each block without compromising the accuracy.

  * •

To extract the fine-grained structure information and exploit hardware
parallelism, we propose a compiler-based mobile acceleration framework that
supports the proposed pruning regularity as well as other pruning
regularities. It provides the flexibility to apply different pruning schemes
to different layers for a better performance of the pruned model.

For the automatic pruning scheme mapping methods part: Taking the different
acceleration and accuracy performance of various pruning schemes into
consideration, we probe into the new problem of determining the best-suited
pruning scheme for each layer of any given DNN. We propose two automatic
pruning scheme mapping methods to address this problem. More specifically:

  * •

The first is a search-based method leveraging the recent concept of network
architecture search (NAS) (Zoph and Le, 2017; Zhong et al., 2018; Tan et al.,
2019; Wu et al., 2019; Cai et al., 2018), which employs reinforcement learning
(RL) technique to yield close-to-optimal pruning scheme mappings.

  * •

The second is a training-free, rule-based method leveraging an offline-
generated latency model. It is efficient and more useful in practice.

We perform comprehensive evaluations of the proposed general pruning scheme
and the two mapping methods on representative DNN models and benchmark
datasets. Experimental results demonstrate that our methods significantly
outperform state-of-the-art DNN pruning framework PatDNN in terms of accuracy
and latency performance. We achieve 17.22ms, 18.17ms, and 3.90ms ImageNet
inference time with negligible accuracy loss on an off-the-shelf mobile phone
for ResNet-50, VGG-16, and MobileNetV2, respectively. Furthermore, the search-
based method only shows a slightly better performance than the rule-based
method while the rule-based method is training-free in pruning scheme mapping.

##  2\. Background and Related Works

###  2.1. DNN Pruning: Regularity and Algorithm

####  2.1.1. Pruning Regularity

From the pruning regularity aspect, existing pruning schemes can be divided
into three categories: fine-grained unstructured pruning, coarse-grained
structured pruning, and pattern-based pruning. We show the different pruning
regularities in Fig. 1, with colored grids representing remaining weights. The
left and middle column in the figure illustrates pruning regularities in the
4-D weight tensor format and 2-D weight matrix format for CONV layers,
respectively. The right column shows the different regularities for FC layers.

Unstructured pruning is fine-grained and flexible in removing weights at
arbitrary locations (Guo et al., 2016; Frankle and Carbin, 2018; Dai et al.,
2019c, b), as shown in Fig. 1 (a) and (b). Though having the advantage in
maintaining accuracy, unstructured pruning leads to sparse and irregular
weight matrices, and as a result, indices are required to locate the non-zero
weights in the sparse matrix storage format, e.g., CSR format. Therefore, it
cannot effectively and efficiently leverage the hardware parallelism provided
by the underlying system. Consequently, unstructured pruning is generally not
compatible with GPU acceleration for DNN inference, and speed degradation can
often be observed (Ma et al., 2019a).

Structured pruning (Wen et al., 2016; He et al., 2017; He et al., 2019; Yu et
al., 2018; Yuan et al., 2021a) focuses on CONV layers and maintains structured
regularity. It consists of filter pruning and channel pruning that prune the
entire filter(s)/channel(s). In the weight matrix format representation as
shown in Fig. 1 (c), filter pruning corresponds to reducing one row of the
weight matrix and it is also termed as row pruning. Accordingly, channel
pruning corresponds to reducing multiple consecutive columns. The key
advantage of structured pruning is that a full matrix will be maintained with
dimension reduction, thereby facilitating hardware acceleration. However,
structured pruning is coarse-grained and often leads to certain accuracy
degradation (Wang et al., 2019; Niu et al., 2020b).

Figure 1. Different weight pruning schemes for CONV and FC layers using 4D
tensor and 2D matrix representation.

Pattern-based pruning (Niu et al., 2020b; Ma et al., 2020a; Yuan et al.,
2021b) alleviates the shortcomings of prior works by incorporating the
benefits from fine-grained pruning while maintaining structures that can be
exploited for hardware accelerations with the help of compiler. Pattern-based
pruning is a combination of kernel pattern pruning and connectivity pruning as
shown in Fig. 1 (e). Kernel pattern pruning prunes weights at an intra-kernel
level by enforcing the locations of the remaining weights in a kernel to form
a specific kernel pattern. Different kernels can have different kernel
patterns, but the total types of kernel patterns are restricted to a fixed-
size set. Each kernel pattern reserves 4 non-zero weights to match the single-
instruction multiple-data (SIMD) architecture of embedded CPU/GPU processors
to maximize the hardware throughput. As a fixed number of weights are pruned,
the compression rate is constant for kernel pattern pruning. For a higher
compression rate, connectivity pruning is adopted as the supplementary to
kernel pattern pruning. Connectivity pruning prunes weights at an inter-kernel
level via cutting the connections between certain input and output channels.

However, pattern-based pruning is designed for 3$\times$3 CONV layers and
suffers difficulty when generalized to CONV layers with other kernel sizes and
FC layers. To avoid the execution overhead of branching conditions caused by
using different pattern types, pattern-based pruning requires limiting the
maximum number of different pattern types to be used. Generally, 8 or 16
different pattern types are allowed to be selected from all possible 4-entry
pattern combinations to ensure a decent acceleration while not hurting
accuracy. For larger kernel sizes such as 5x5/7x7, 4-entry patterns need to be
selected from 25/49 weights (instead of 9 weights in 3x3 case), making the
pattern have too many potential candidates. As a result, if only 8 or 16
patterns are used, there will be an accuracy degradation. Moreover, as studied
in (Ma et al., 2020c), the Gaussian filter-like patterns and the Enhanced
Laplacian of Gaussian (ELoG) filter-like patterns (as shown in Fig. 1 (e)) are
more preferred since they can provide an enhancement on feature extraction.
But such 4-entry patterns in 5x5/7x7 kernels cannot provide the receptive
field size that the large kernels are supposed to have. For the 1x1 CONV
layer, there is only one weight in a kernel, making the pattern-based pruning
same as unstructured pruning, which is hard to achieve actual acceleration.
Therefore, the existing pattern-based pruning is only suitable for 3x3
kernels, which significantly restricts the application scenarios of pattern-
based pruning.

####  2.1.2. Pruning Algorithm

There are two main categories of pruning algorithm, i.e., heuristic-based
algorithm and regularization-based algorithm. Heuristic-based pruning
algorithm was first proposed to achieve unstructured pruning by pruning
weights with small magnitudes in an iterative manner (Han et al., 2015). Later
heuristic works get improved in multiple directions including structured-
preserving pruning (Li et al., 2017; Luo et al., 2017; Yu et al., 2018),
combining growth of neurons and connections with pruning (Dai et al., 2019c),
and introducing meticulously-designed criteria (Yu et al., 2018; Zhuang et
al., 2018; He et al., 2019; Luo et al., 2017) to replace magnitudes for the
pruning.

Regularization-based algorithm deal with the pruning problem using a more
mathematics-oriented method. To solve filter/channel pruning problems, early
works (Wen et al., 2016; He et al., 2017) incorporate $\ell_{1}$ or $\ell_{2}$
structured regularization in the loss function. Work (Liu et al., 2017)
introduces a scaling factor to each channel while imposing $\ell_{1}$
regularization on the scaling factors in batch normalization to prune channels
with near-zero scaling factors. However, these works directly apply fixed
regularization terms that penalize all weights equally, incurring potential
accuracy loss. Later works (Zhang et al., 2018a; Ren et al., 2019b; Gong et
al., 2020) adopt ADMM to reform the pruning problem as optimization problems
with dynamic regularization penalties, thus preserving accuracy. One drawback
of these methods is the requirement for the manual setting of the compression
rate for each layer.

###  2.2. Compiler-based DNN Frameworks on Mobile

Mobile devices become key carriers of deep learning (Hegde et al., 2016; Lane
et al., 2017; Ota et al., 2017; Zhang et al., 2019) to enable the widespread
of machine intelligence. To facilitate the deployment of various DNN models on
mobile devices, multiple mobile DNN execution frameworks from both industry
and academia attract broad attention (Lane et al., 2016; Lane et al., 2015; Xu
et al., 2018; Huynh et al., 2017; Yao et al., 2017; Han et al., 2016). TFLite
(Ten, [n.d.]), MNN (Ali, [n.d.]), and TVM (Chen et al., 2018b) are three
representative state-of-the-art end-to-end DNN execution frameworks with high
execution efficiency. They employ several performance optimization techniques,
such as various computation graph optimizations, tensor optimizations, and
half-float support. Particularly, TVM includes a more advanced parameter auto-
tuning technique. However, none of these frameworks support sparse (pruned)
DNN models on mobile platforms111TVM considers sparsity recently for desktop
processors.. This is the essential drawback that obstructs the real-time DNN
inference on mobile devices. Take VGG-16 network, one of the key DNN models in
transfer learning, as an example, TVM takes 200ms to perform an inference on
the embedded GPU (Adreno 640), and TFLite takes an even longer time (270 ms).

Previous efforts based on fine-grained pattern-based pruning such as PatDNN
(Niu et al., 2020b) and PCONV (Ma et al., 2020a) employ a set of compiler-
based optimizations to support sparse DNN models, significantly accelerating
the end-to-end DNN inference on mobile devices. However, they mainly
accelerate the square and small convolution kernels used in 3$\times$3 CONV
layers. A larger kernel size, e.g., 5$\times$5, 7$\times$7, will introduce
huge code execution overhead due to the increasing number of branches in
generated code. In addition, they cannot support FC layers and 1$\times$1 CONV
layers that are commonly used in DNNs.

##  3\. Overview of the Automatic Pruning Scheme Mapping Framework

Figure 2. High-level overview of proposed automatic pruning scheme mapping
framework.

To achieve real-time mobile acceleration for various modern DNNs, we propose
an automatic pruning scheme mapping framework, which is illustrated in Fig. 2.
Given an arbitrary DNN model, the framework can automatically map the best
pruning configurations to each layer and leverage compiler-based optimizations
to achieve inference speedup. The layer-wise configurations include the
pruning regularity, compression rate, and the block size.

In order to achieve the design objective, our framework contains the following
innovations. We first propose a general, fine-grained pruning regularity that
is applicable to different types of layers while achieving both high accuracy
and hardware acceleration performance to overcome the limitations of prior
pruning regularities in Section 4.1. To determine the compression rate for
each layer automatically without compromising accuracy, we introduce a
reweighted pruning algorithm in Section 4.2. For the goal of transforming
compression to real inference speedup on mobile devices, we propose
corresponding compiler-based optimizations that support the proposed pruning
regularity as well as other pruning regularities in Section 4.3. As directly
applying the same pruning scheme to the entire model can not yield the optimal
performance, we further propose to map the best-suited pruning configurations
to each layer of any given DNN for mobile devices thanks to the flexibility
enabled by our compiler optimizations. The mapping methods include a
comprehensive search-based method that can provide close-to-optimal results in
Section 5.1 and a training-free rule-based method that is more useful in-
practice while reaching similar performance as the search-based method in
Section 5.2.

##  4\. General, Fine-grained Structured Pruning Scheme

In this section, we present a novel fine-grained structured pruning scheme and
corresponding compiler optimizations to (i) achieve high accuracy and hardware
inference performance simultaneously while applicable to different types of
layers; (ii) determine the compression rate for each layer automatically
without compromising the accuracy; and (iii) provide the supports to the
proposed pruning regularity and other pruning regularities for the
exploitation of the hardware parallelism. We start by providing a general
fine-grained structured pruning regularity that includes block-based pruning
for FC layers and block-punched pruning for CONV layers with different kernel
sizes in Section 4.1. Next, a reweighted dynamic regularization algorithm
which allows the automatic determination of the per-layer and per-block
compression rate is introduced to derive the sparse regularity in Section 4.2.
Then we provide corresponding compiler optimizations for the proposed pruning
scheme to enable efficient on-device inference of the pruned model in Section
4.3.

###  4.1. General, Fine-Grained Structured Pruning Regularity

Though state-of-the-art pattern-based pruning strikes a desirable balance
between accuracy and hardware efficiency, it only works for CONV layers with
$3\times 3$ kernels and suffers difficulty when generalized to layers with
other kernel sizes and FC layers. Note that not all of the layers only operate
on $3\times 3$ kernels in a given DNN model. As a result, the number of layers
using $3\times 3$ kernels affect the effectiveness of pattern-based pruning.
Fig. 3 illustrates the percentage of the parameters and multiply-and-
accumulates (MACs) in $3\times 3$ CONV layers of four representative networks.
The large portion of non-$3\times 3$ CONV layers leaves great space for higher
compression rate and faster inference that cannot be achieved by pattern-based
pruning alone.

Figure 3. Comparisons of (a) parameter ratio and (b) computation ratio for
3$\times$3 CONV layers and non-3$\times$3 layers for different networks on
ImageNet dataset.

To alleviate the deficiencies, we propose a general pruning scheme with fine-
grained structured pruning regularity, including block-based pruning for FC
layers and block-punched pruning for CONV layers with different kernel sizes.

####  4.1.1. Block-based Pruning for FC Layers

Block-based pruning is an extension of the coarse-grained structured pruning
that prunes rows/columns in matrix-based computation for FC layers. As shown
in Fig. 1 (g), we divide a whole weight matrix of a FC layer to a number of
equal-sized blocks (e.g., 4$\times$4, 16$\times$32, 64$\times$128, etc.), and
apply independent row and column pruning for each block. The compression rate
(the number of pruned rows/columns) for each block can either be the same or
different, which depends on the design requirements.

####  4.1.2. Block-punched Pruning for CONV Layers

Compared with matrix-based representation and computation, tensor-based
representation and computation are more suitable for CONV layers. Thus,
inspired by block-based pruning, we further propose block-punched pruning that
is tailored for CONV layers and can be accelerated with the same compiler
optimizations. As shown in Fig. 1 (f), block-punched pruning first partitions
the weight tensor of a CONV layer into groups (blocks) of kernels along the
filter and input channel dimensions. For each block, the weights at the same
locations for all kernels within the block are pruned. With effective
compiler-level executable code generation, high hardware parallelism and
inference acceleration on mobile can be achieved.

Compared with state-of-the-art pattern-based pruning, the proposed fine-
grained structured pruning regularity is general and flexible as it can
adaptively prune FC layers and CONV layers with different kernel sizes. In the
same time, block-based pruning and block-punched pruning can simultaneously
achieve high accuracy and high hardware inference performance like pattern-
based pruning. The high accuracy is attributed to the fine-grained property of
pruning regularity, which allows higher flexibility when searching the pruned
model structure compared to coarse-grained structured pruning that prunes
entire rows/columns in weight matrices. On the other hand, the high hardware
inference performance is attributed to the appropriate degree of structural
regularity, which can be exploited by compiler-level code generation to
achieve high or even maximum hardware parallelism. With an appropriate
selection of the block size, the remaining entries in each block can still be
sufficient to exploit high hardware parallelism. The block size for each layer
is an important hyperparameter that influences hardware performance and
accuracy. We will elaborate on how to select the appropriate block size for
each layer in Section 5.2.2.

###  4.2. Reweighted Dynamic Regularization Algorithm

Another important design aspect of a pruning scheme is the pruning algorithm.
Prior pruning algorithms such as using the group Lasso regularization (Wen et
al., 2016; He et al., 2017; Liu et al., 2017) or ADMM (Zhang et al., 2018a;
Ren et al., 2019a; Li et al., 2019), either suffer from potential accuracy
loss or require compression rate tuning manually. To overcome the limitations,
we propose to adopt reweighted group Lasso (Candes et al., 2008) method to
discover the structured sparsity with systematically and dynamically
reweighted penalties. More specifically, the reweighted method reduces the
penalties on weights with larger magnitudes, which are likely to be more
critical weights, and increases the penalties on weights with smaller
magnitudes. A comparison of the characteristics of different regularization-
based pruning algorithms is shown in Table 1.

Table 1. Comparison of different pruning algorithms.

For the $i$-th layer in the DNN, if the layer is a FC layer, let
$\bm{W}_{i}\in\mathbb{R}^{P_{i}\times Q_{i}}$ denote the 2-D weight matrix,
with $P_{i}$ and $Q_{i}$ indicating the rows and columns of the weight matrix,
otherwise $\bm{W}_{i}\in\mathbb{R}^{P_{i}\times Q_{i}\times K_{i}^{h}\times
K_{i}^{w}}$ represents the 4-D weight tensor of a CONV layer, where $P_{i}$ is
the number of filters, $Q_{i}$ is the number of input channels, $K_{i}^{w}$
and $K_{i}^{h}$ are the kernel width and kernel height. Let
$\bm{b}_{i}\in\mathbb{R}^{P_{i}}$ represent the bias for the $i$-th layer. We
also define $\bm{W}:=\\{\bm{W}_{i}\\}_{i=1}^{N}$, and
$\bm{b}:=\\{\bm{b}_{i}\\}_{i=1}^{N}$ as the set of all weights and biases in
the DNN. We denote the loss of the DNN under dataset $\mathcal{D}$ by
$f(\bm{W},\bm{b};\mathcal{D})$. Each $\bm{W}_{i}$ is divided into $J$ blocks
with the same size, $p_{i}\times q_{i}$ for a FC layer and $p_{i}\times
q_{i}\times K_{i}^{h}\times K_{i}^{w}$ for a CONV layer, namely,
$\bm{W}_{i}=[\bm{W}_{i1},\bm{W}_{i2},...,\bm{W}_{iJ}]$, where
$\bm{W}_{ij}\in\mathbb{R}^{p_{i}\times q_{i}}$ for a FC layer and
$\bm{W}_{ij}\in\mathbb{R}^{p_{i}\times q_{i}\times K_{i}^{h}\times K_{i}^{w}}$
for a CONV layer. The general reweighted pruning problem is formulated as

(1)
$\small\underset{\bm{W},\bm{b}}{\text{minimize\quad}}f\big{(}\bm{W},\bm{b};\mathcal{D}\big{)}+\lambda\sum_{i=1}^{N}R(\bm{\alpha}_{i}^{(t)},\bm{W}_{i}),\\\
$

where $\lambda$ is the hyperparameter to adjust the relative importance
between accuracy and sparsity. Let $\bm{\alpha}_{i}^{(t)}$ denote the
collection of penalty values applied on the weights $\bm{W}_{i}$ for layer $i$
at step $t$. Note that each element in $\bm{\alpha}_{i}^{(t)}$ is a positive
value that is determined by reweighted $\ell_{1}$ algorithm (Candes et al.,
2008).

For block-based row pruning, the regularization term is

(2) $\small
R({\bm{\alpha}}_{i}^{(t)},\bm{W}_{i})=\sum_{j=1}^{J}\sum_{m=1}^{p_{i}}\big{\|}\alpha_{ijm}^{(t)}\circ[\bm{W}_{ij}]_{m,:}\big{\|}_{F}^{2},$

where the operator $\circ$ represents element-wise multiplication,
$[\bm{W}_{ij}]_{m,:}$ denotes the $m$-th row of $\bm{W}_{ij}$, and
$\alpha^{(t)}_{ijm}$ is updated by
$\alpha^{(t)}_{ijm}=\frac{1}{\|[\bm{W}_{ij}]^{t}_{m,:}\|_{F}^{2}+\epsilon}$ to
help increase the degree of sparsity beyond group Lasso regularization.

For block-based column pruning, the regularization term is

(3) $\small
R({\bm{\alpha}}_{i}^{(t)},\bm{W}_{i})=\sum_{j=1}^{J}\sum_{n=1}^{q_{i}}\big{\|}\alpha_{ijn}^{(t)}\circ[\bm{W}_{ij}]_{:,n}\big{\|}_{F}^{2},$

where $[\bm{W}_{ij}]_{:,n}$ is the $n$-th column of $\bm{W}_{ij}$ and
$\alpha^{(t)}_{ijn}$ is updated by
$\alpha^{(t)}_{ijn}=\frac{1}{\|[\bm{W}_{ij}]^{t}_{:,n}\|_{F}^{2}+\epsilon}$.
The block-based row pruning problem (2) and column pruning problem (3) can be
solved separately or simultaneously using a standard deep learning solver.

For block-punched pruning, the regularization term is formulated as

(4) $\small
R({\bm{\alpha}}_{i}^{(t)},\bm{W}_{i})=\sum_{j=1}^{J}\sum_{m=1}^{K_{i}^{h}}\sum_{n=1}^{K_{i}^{w}}\big{\|}\alpha_{ijmn}^{(t)}\circ[\bm{W}_{ij}]_{:,:,m,n}\big{\|}_{F}^{2},$

where $[\bm{W}_{ij}]_{:,:,m,n}$ indicates the weight located at the $m$-th row
and $n$-th column in a kernel for all kernels in the block and
$\alpha^{(t)}_{ijmn}=\frac{1}{\|[\bm{W}_{ij}]^{t}_{:,:,m,n}\|_{F}^{2}+\epsilon}$.
The reweighted method only requires the hyperparameter $\lambda$ and the soft
constraints formulation allows the automatic determination of the compression
rate for each layer and each block.

###  4.3. Compiler Optimizations for Proposed Pruning Regularity

Figure 4. Blocked Compressed Storage (BCS) for weights.

Compiler optimizations can turn the sparsity of pruned models into higher
speedups. Without compiler optimizations, the pruned weights (with zero
values) still participate in the inference computations, resulting in minor
inference speedup. Hence, we develop a comprehensive compiler-based automatic
code generation framework to extract the fine-grained structure information in
block-punched and block-based pruning. The framework also supports other
pruning regularities including unstructured pruning, structured pruning, and
pattern-based pruning. Our proposed compiler-based mobile acceleration
framework first compacts the model storage with a novel compression format
called Blocked Compressed Storage (BCS) format, as shown in Fig. 4. Then, it
performs computation reordering to reduce the branches within each thread and
eliminate the load imbalance among threads.

BCS stores non-zero weights as Compressed Sparse Row format (CSR) with a
better compression rate by further compressing the index with a hierarchical
structure. Traditional CSR has to store each non-zero weight with an explicit
column index. Our proposed block-based/block-punched pruning preserves non-
zero weights in identical columns within each block, inducing many repeated
column indices if we use CSR. BCS eliminates this redundancy with a
hierarchical compression on the column index only.

Fig. 4 shows a simplified example. Weights array stores all non-zero weights.
Compact column array stores the compressed column index, e.g., [0, 3, 6]
denotes the column id of the first three weights [1, 2, 3]. Column stride
array denotes the start and end index of each row in compact column array,
e.g., [0, 3] denotes that the column index for the first row starts from index
0 and ends at index 2 in compact column array. The same column indices may be
used for multiple rows. Occurrence array is used to specify the start and end
rows with the identical column index, e.g., [0, 2] means that row 0 and 1
share the same column index. BCS also contains a row offset array to specify
the starting location of each row in weight array.

Usually, the weight distribution is not as regular as the above simplified
example, thus, a row reordering optimization is also included to further
improve the regularity of the weight matrix. After this reordering, the
continuous rows with identical or similar numbers of non-zero weights are
processed by multi-threads simultaneously, thereby eliminating thread
divergence and achieving load balance. Each thread processes more than one
rows, thus eliminating branches and improving instruction-level parallelism.
We also incorporate other compiler-based optimizations for on-mobile DNN
inference acceleration, such as the layer-fusion, the auto-tuning, and the
high-level domain-specific language. More details are provided in the
Appendix.

###  4.4. Effectiveness of the Proposed Pruning Scheme

Figure 5. Accuracy and latency performance with different block sizes on
ResNet-50 using ImageNet dataset.

We show an example of the inference accuracy and acceleration performance of
the proposed pruning scheme on ResNet-50 using ImageNet dataset in Fig. 5.
More thorough evaluation results are presented in Section 6.2. Here, block-
based pruning is applied for all FC layers and block-punched pruning is
applied for all CONV layers. The compression rate for each layer is derived by
the reweighted dynamic regularization algorithm. As can be seen from the
figure, unstructured pruning, which is equivalent as setting the block size as
$1\times 1$ for each layer, achieves the highest accuracy while has the worst
performance in latency. In contrast, structured pruning, i.e., using the whole
matrix as the block size, achieves the fastest inference but degrades the
accuracy the most. With a suitable block size, our proposed fine-grained
structured pruning scheme achieves high accuracy and inference speed
simultaneously. The reason is that the maximal hardware parallelism is limited
by the computation resource. Since the weight matrix/tensor is typically very
large, the remaining entries in each block is still sufficient to exploit high
hardware parallelism. With parallelism maximally exploited, the hardware
inference performance can be almost the same as coarse-grained structured
pruning.

Takeaway: In this section, we first introduced a general, fine-grained
structured pruning regularity, which can work for CONV layers with any kernel
size and FC layers. Second, we proposed reweighted group Lasso with block-
based constraints as the pruning algorithm to derive the structured sparsity
with automatically determined compression rate for each layer and each block.
Third, we develop the first compiler-based mobile acceleration framework that
supports general block-based/block-punched sparsity as well as other pruning
regularities, which is flexible and allows different layers to adopt different
pruning regularities and block sizes.

##  5\. Automatic Pruning Scheme Mapping Methods for Mobile Devices

Though the general, fine-grained pruning scheme proposed in Section 4 can
achieve high accuracy and hardware acceleration performance, it is not optimal
to directly apply the same pruning scheme to the entire model as different
layers may prefer different pruning regularities and configurations, e.g., the
compression rate and block size. Fortunately, effective compiler optimization
techniques provide the flexibility to apply different pruning regularities and
block sizes to different layers. As different weight pruning schemes have
different acceleration and accuracy performance under the same mobile
acceleration framework, it is important to have a pruning scheme mapping
method to determine the pruning configurations for each layer. Therefore, we
further probe into the problem of mapping the best-suited pruning scheme for
each layer of any given DNN to obtain pruned model with better performance in
terms of accuracy and latency in this section.

The performance of a pruned model is influenced by the compression rate,
pruning regularity, and block size when block-based/block-punched pruning is
selected, of each layer. This is a new challenge resulted from the new
dimension of compiler-aware pruning scheme optimizations. To find the
appropriate pruning schemes in such a large design space, we propose two
automatic pruning scheme mapping methods, one is search-based and the other is
rule-based, as shown in Fig. 6. The former is a more comprehensive framework
to yield close-to-optimal pruning scheme mapping results, while the latter is
a _training-free_ procedure that is efficient and more useful in practice.
Note that with our proposed reweighted dynamic regularization algorithm in
Section 4.2, the compression rate can be obtained automatically for each layer
and each block. Thus, the search space of the pruning scheme mapping problem
can be reduced to finding the appropriate pruning regularity and the block
size for each layer in the given DNN.

Figure 6. Overview of (a) Search-based pruning scheme mapping, and (b) rule-
based pruning scheme mapping.

###  5.1. Search-based Pruning Scheme Mapping Method

Albeit we simplify the search space with the reweighted dynamic regularization
algorithm to determine the per-layer and per-block compression rate
automatically, there is still a huge amount of combinations of pruning
regularities and block sizes to seek. Inspired by recent advances in NAS (Zoph
and Le, 2017; Zhong et al., 2018; Tan et al., 2019; Wu et al., 2019; Cai et
al., 2018), we consider to leverage a search-based method by employing RL (Li
and Malik, 2016; Sutton and Barto, 2018) to map the appropriate pruning scheme
for each layer of a given DNN.

In RL, an agent interacts with the environment by taking an action $a_{t}\in
A$ according to a policy $\pi$ upon the observation of a state $s_{t}\in S$ at
time step $t$. For our problem, each time step $t$ corresponds to the pruning
scheme mapping of one layer. The state $s_{t}\in S$ represents the information
of current layer, which is defined as a $4$-D vector {layer type, kernel size,
input channel number, output channel number}. The action $a_{t}\in A$ is the
mapping decision for the current layer, which is a $2$-D vector {pruning
regularity, block size}. For a $N$-layer DNN with information
$\mathcal{I}=\\{s_{1},\cdots,s_{N}\\}$, an entire mapping
$\mathcal{M}=\\{a_{1},\cdots,a_{N}\\}$ can be found with $N$ time steps. Let
$R(\mathcal{M})$ denote the cumulative reward for $\mathcal{M}$, which is the
optimization target of the RL agent. A good pruning scheme mapping should
achieve high accuracy and hardware performance jointly, thus we define
$R(\mathcal{M})$ as the weighted sum of the accuracy and the negative of the
latency of the pruned model with information $\mathcal{I}$ under the mapping
$\mathcal{M}$.

We leverage the policy gradient method (Sutton et al., 1999) to directly learn
a parameterized policy for the pruning scheme mapping, and the training
objective of the policy is defined as:

(5) $\small
J(\theta)=\mathbb{E}_{\mathcal{M}\sim\pi(\mathcal{M}|\mathcal{I};\theta)}[R(\mathcal{M})|\mathcal{I}],$

where $\pi(\mathcal{M}|\mathcal{I};\theta)$ is a sequence-to-sequence model in
our work. The input to the encoder RNN is the sequence of the information of
each layer in the target DNN and the decoder is an LSTM with $N$ time steps to
output the mapping decision for each layer at the same encoder time step. We
estimate the gradient of the objective function by drawing $K$ mapping
decision samples from $\mathcal{M}_{k}\sim\pi(\mathcal{M}|\mathcal{I};\theta)$
and reduce the variance of the estimate with a baseline term $B$, leading to

(6)
$\small\nabla_{\theta}J(\theta)\approx\frac{1}{K}\sum_{k=1}^{K}(R(\mathcal{M}_{k})-B)\cdot\nabla_{\theta}\log\pi(\mathcal{M}_{k}|\mathcal{I};\theta).$

For each mapping decision sample $M_{k}$ in a training iteration of the
policy, we need to compress the target DNN to obtain the accuracy and latency
performance for the calculation of the reward $R(\mathcal{M}_{k})$. The
latency is obtained via deploying pruned model with compiler code generation
on target device and measuring the real execution time. To accelerate the
policy training, we adopt magnitude-based, one-shot pruning and early stopping
for faster accuracy evaluation during the policy training process. More
specifically, once a mapping $\mathcal{M}_{k}$ is obtained, we conduct a one-
shot pruning for each layer of the DNN based on the weight magnitude and
retrain the DNN for two epochs to regain accuracy. This partially regained
accuracy can be used to predict the final model accuracy and compare the
performance between different schemes (Zhong et al., 2018; Tan et al., 2019).
Furthermore, as compiler code generation and latency measurement do not depend
on absolute weight values and are faster than DNN training, we overlap the
compiler code generation and latency measurement with the accuracy evaluation
of the pruned model.

###  5.2. Rule-based Pruning Scheme Mapping Method

The advantage of the search-based method is that it can find the globally
close-to-optimal pruning configurations for each of the layers in a given DNN.
While it works perfectly for small DNN models, the searching overheads
increases exponentially when the models size increases, making it unsuitable
for large-size DNN models. Therefore, we design a _training-free_ _rule-based_
method that maps the best-suited pruning schemes in a layer-wise fashion to
avoid the time-consuming search process for the best mapping. We consider the
search-based solution as the performance upper-bound, and we target to make
the rule-based method perform as well as the search-based one, yet highly
efficient and practical.

####  5.2.1. Latency Model

To obtain the latency performance without the pruning and retraining of the
given DNN, we build latency models for different types of layers, e.g.,
1$\times$1 CONV, 3$\times$3 CONV, 5$\times$5 CONV, and depthwise-3$\times$3
CONV, on the target device, e.g., Samsung S10 smartphone. Each latency model
contains latency results for different settings, including block size, number
of filters, input and output feature map size, pruning scheme, and compression
rate. The results are measured on the target device by running test models
with each setting for 100 runs. Each test model has 10 cascaded layers with
the same setting. Since building the latency model does not involve DNN
training, it will not take a very long time. The testing time for each run of
each setting is in milliseconds (ms) level. For instance, our latency model
including 512 different layer settings can be built in around 30 minutes. Such
a building time is negligible compared to the DNN training or the searching
process, which usually counts in days. The latency model only needs to be
built once for a target device and is universal to different DNN models.

####  5.2.2. Block-Size Selection

Block size has a significant impact on the accuracy and hardware performance
for block-based/block-punched pruning. A larger block size is typically more
hardware-friendly and easier to leverage the built-in hardware acceleration,
yet it may cause more severe accuracy degradation due to the coarse
granularity. On the contrary, a smaller block size typically leads to higher
accuracy but also increases the latency. An appropriate setting of the block
size can achieve high accuracy as unstructured pruning (essentially with block
size 1$\times$1) and high hardware acceleration performance as structured
pruning (essentially with block size of whole weight tensor/matrix)
simultaneously.

To determine the proper block size for each layer without the requirement of a
time-consuming training process, we consider to decouple the two optimization
targets, i.e., accuracy and hardware performance. To minimize the impact of
pruning on hardware performance, our rule-based method will first derive the
inference latency of each block size from the offline generated latency models
and normalize the latency (i.e., divide by the MACs of that layer). We
introduce a latency threshold $\beta$, indicating the acceptable latency
degradation range of the proposed general pruning regularity compared with
coarse-grained structured pruning. The value of $\beta$ can be adjusted
according to the design requirement, and it can either be the same for the
entire model or different for each layer. For example, $\beta=20\%$ means that
the inference speed of block-based/block-punched pruning can be at most 20%
slower than structured pruning under the same compression rate. After the
hardware performance-driven design is satisfied, we only need to consider the
influence of block size on accuracy. As a smaller block size can provide a
finer granularity in pruning and the consequent higher accuracy, the smallest
valid block size that satisfies the $\beta$-degradation requirement is
selected as the desired block size. This process depends on our latency model,
and is free of training.

####  5.2.3. 3$\times$3 CONV Layer: Pattern or Block

For 3$\times$3 CONV layers, both pattern-based pruning and block-punched
pruning can be applied. To map the best-suited pruning scheme, the problem is
to compare the accuracy and inference latency of block-punched pruning and
pattern-based pruning.

Figure 7. The top-1/top-5 accuracy comparisons of pattern-based pruning and
block-punched pruning (block size of 4$\times$16) under the same compression
rates for ResNet-18 and VGG-16 on CIFAR-10 and ImageNet dataset.

Accuracy Perspective: To investigate the accuracy of pattern-based pruning and
block-punched pruning, we conduct comprehensive experiments on ResNet-18 and
VGG-16 with CIFAR-10 and ImageNet dataset. Fig. 7 (a) and (b) show an example
of the comparison results on the CIFAR-10 dataset and the block size is set to
4$\times$16\. Note that only 3$\times$3 CONV layers are pruned and
non-3$\times$3 layers remain unpruned to provide a fair comparison. Here, the
compression rate indicates the parameter reduction rate for each 3$\times$3
CONV layer. From the figure, we can make the following observations: i) block-
punched pruning consistently shows comparable or higher accuracy for the
pruned model under different compression rates on CIFAR-10 dataset; ii) both
block-punched and pattern-based pruning achieve accuracy enhancement when the
compression rate is relatively low, especially on ResNet-18. The reason is
that pruning with a small compression rate can help mitigate the over-fitting
problem.

The comparison results of pattern-based pruning and block-punched pruning on
ImageNet dataset with different compression rates are shown in Fig. 7 (c) and
(d). Different from the observations on CIFAR-10 dataset, pattern-based
pruning shows a better accuracy performance under various compression rate
settings for both ResNet-18 and VGG-16.

We attribute the different performance on the two datasets to: (1) For tasks
on easy datasets such as CIFAR-10 that can easily achieve higher than 90%
accuracy, the networks are generally overparameterized and both block-punched
and pattern-based pruning schemes can achieve a high compression rate (e.g.,
¿10$\times$) and significant acceleration without hurting the model
generalization ability. Thus, the acceleration performance of the two pruning
schemes becomes a more essential factor that contributes to the pruning scheme
selection. Compared to pattern-based pruning, the block-based/block-punched
pruning has a more strict constraint on the weight structure, benefiting
hardware parallelism and hence a higher acceleration performance under the
same compression rate. Therefore, block-based/block-punched pruning is more
favorable for easier datasets. (2) For tasks on harder datasets such as
ImageNet that even the unpruned network can only achieve less than 80% Top-1
accuracy, the pattern-based pruning scheme is more desirable than block-
based/block-punched pruning on 3$\times$3 CONV layers. Because the patterns
used by pattern-based pruning form the shape of Gaussian filter or Laplacian
of Gaussian filter that can enhance the ability for feature extraction (as
mentioned in Sec. 2.1), which plays an important role in preserving accuracy
under an accelerable compression rate.

Based on the above results, we make the following remark:

###### Remark 1.

For 3$\times$3 CONV layers, block-punched pruning is more suitable for tasks
with easier datasets while pattern-based pruning suits tasks with harder
datasets better.

We will provide more discussions and verification of the remark in Section
6.3.

Latency Perspective: Latency is the other important aspect in performance
evaluation of a pruning scheme. From comprehensive comparative experiments
conducted offline, we have observed that under the same compression rate, the
latency performance of block-punched pruning is better than pattern-punched
pruning when the block size is large, but worse when the block size is small.
The latency of these two pruning regularities mainly depends on which one can
achieve a larger compression rate under the same accuracy. Thus, latency is
considered as a secondary criterion for the best-suited pruning scheme mapping
in the rule-based method. More discussion will be provided in Section 6.3.

####  5.2.4. 3$\times$3 Depth-wise CONV Layer

The 3$\times$3 depth-wise CONV layer (3$\times$3-DW) is widely used in current
DNN designs such as the MobileNet family (Sandler et al., 2018). It is a
special case of 3$\times$3 CONV layer, which applies a 2-D depth filter at
each depth level of the input tensor. Thus, both pattern-based pruning and
block-punched pruning can be applied to 3$\times$3-DW layers theoretically. In
our rule-based selection policy, we prefer not prune 3$\times$3-DW layers
mainly for two reasons: (1) 3$\times$3-DW layers are computation- and memory-
efficient; (2) 3$\times$3-DW layers are sensitive to pruning.

We use MobileNet-V2 on ImageNet as an example, 33% of layers are 3$\times$3-DW
layers, but they only contribute 6.9% MACs and 1.7% parameters in total.
Pruning 3$\times$3-DW layers will not achieve a considerable gain even if all
of them are pruned. On the other hand, the 3$\times$3-DW layers contribute 33%
of activations, making each weight in the 3$\times$3-DW layer more
significant. Moreover, in a regular 3$\times$3 CONV layer, one input
(activation) channel will be filtered by multiple CONV kernels that come from
different CONV filters and have different pruned locations, mitigating the
damage of pruning on feature extraction. On the contrary, in a 3$\times$3-DW
layer, one input channel will only be filtered by one CONV kernel, which makes
3$\times$3-DW layers more sensitive to the pruning.

We conduct an ablation study about the impact of pruning 3$\times$3-DW on
accuracy and overall pruning ratio. The results show that pruning
3$\times$3-DW layers will only slightly increase the pruning ratio while
leading to a noticeable accuracy loss. Our experiment results shown in Section
6.2 indicate both pattern-based pruning and block-punched pruning lead to a
non-negligible accuracy drop when applied to 3$\times$3-DW layers. Therefore,
our rule-based method does not map any pruning scheme to the 3$\times$3 depth-
wise CONV layers.

Figure 8. Rule-based pruning scheme selection.

We summarize the workflow of the training-free rule-based method in Fig. 8.
For each layer of a given DNN, we first examine the layer type. If the layer
is a 3$\times$3 depth-wise CONV layer, no pruning scheme is mapped. For
3$\times$3 CONV layers, the pruning regularity depends on the size of the
dataset. Pattern-based pruning is mapped to 3$\times$3 CONV layers if the task
has a large dataset, otherwise block-punched pruning is selected. The proposed
general block-based/block-punched pruning is mapped to all other types of
layers. When block-based/block-punched pruning is selected, the block size is
determined according to an offline generated latency model with a latency
threshold. We note that the entire mapping process, including the pruning
regularity mapping and block size selection, is training-free without
incurring any additional cost.

##  6\. Evaluation

###  6.1. Methodology

Evaluation Objective: (i) Show the effectiveness of the general, fine-grained
structured pruning scheme and the corresponding compiler optimizations; (ii)
compare the overall pruning scheme mapping framework with state-of-the-art DNN
inference acceleration framework PatDNN (Niu et al., 2020b) in terms of
accuracy and latency. Note that PatDNN already outperforms other DNN inference
frameworks including TVM (Chen et al., 2018b), MNN (Ali, [n.d.]), and
Tensorflow-Lite (Ten, [n.d.]), thus the comparison with PatDNN is sufficient
to show the effectiveness of our methods.

Our achieved speedup mainly comes from: (i) our general, fine-grained
structured pruning is applicable to all types of layers, which better
compresses the model size and reduces the computation workload; (ii) our
compressed sparse matrix storage and associated compiler optimizations improve
the computation regularity/parallelism, thus transforming the computation
reduction to real performance gains; (iii) our automatic pruning scheme
mapping methods successfully map the best-suited pruning configurations to
each layer, maximizing the compression rate while maintaining accuracy.

DNN Models: We evaluate on three mainstream DNNs, VGG-16 (Simonyan and
Zisserman, 2014), ResNet-50 (He et al., 2016), and MobileNet-V2 (Sandler et
al., 2018). They are trained on two representative datasets, CIFAR-10 and
ImageNet (Deng et al., 2009). We also conduct experiments on YOLOv4
(Bochkovskiy et al., 2020) with MS COCO dateset (Lin et al., 2014).

Evaluation Platforms and Running Configurations: All the evaluated models are
trained on a server with 8 NVIDIA RTX 2080Ti GPUs. The training codes are
implemented with the PyTorch API. The latency is measured on the mobile GPU of
an off-the-shelf Samsung Galaxy S10 smartphone, which has the Qualcomm
Snapdragon 855 mobile platform with a Qualcomm Kryo 485 Octa-core CPU and a
Qualcomm Adreno 640 GPU. Each test takes 50 runs on different inputs with 8
threads on CPU, and all pipelines on GPU. As different runs do not vary
greatly, only the average time is reported for readability. All runs are tuned
to the best configurations. We empirically choose the latency threshold
$\beta=20\%$.

Figure 9. Latency of 1$\times$1 and 3$\times$3 CONV layer under different
feature sizes and input/output channels.

###  6.2. Evaluations of Proposed Pruning Scheme

We first evaluate the inference latency of block-punched pruning using
different block sizes on 1$\times$1 and 3$\times$3 CONV layers with different
layer sizes, as shown in Fig. 9. The input feature map size of the testing
CONV layers is set to 56$\times$56, 28$\times$28, 14$\times$14, and 7$\times$7
while the input/output channel size is set to 64, 128, 256, and 512. These
configurations are commonly used in real DNN networks such as ResNet-50 and
VGG-16 on ImageNet. And these configurations keep the MACs the same for all
1$\times$1/3$\times$3 CONV layers, which can help us observe the impact of
different input feature map size and number of channels on latency better.

From Fig. 9 (a), we can see that the latency is reduced with a larger block
size. However, the speedup gradually saturates. The reason is that the
remaining weights in each block are more likely to be sufficient to exploit
high hardware parallelism with larger block size. Another observation is that
the layer inference latency increases for all block sizes as the size of the
input feature map decreases and the number of input/output channels increases.
The reason is that a smaller input feature map size lowers the reuse rate of
each weight, causing hardware parallelism degradation. Similar observations
can also be found in Figure 9 (b), which shows the latency results for
different 3$\times$3 CONV layers.

Similar results can also be observed on FC layers with block-based pruning.
Fig. 10 (a) shows the latency comparisons on two FC layers. The size of the FC
layer on the left-hand side is used as the first FC layer in VGG-16, while the
right-hand side is the representative FC layer in BERT. The latency of each FC
layer is normalized to its own 1$\times$1 block size result. We can observe
that for large FC layers, increasing the block size can reduce latency
effectively, while the latency reduction achieved by increasing the block size
gets saturated gradually in relatively small FC layers.

###  6.3. Automatic Pruning Scheme Mapping Methods Evaluations

Table 2. Comparison on YOLOv4. Pruning Scheme | # Weights | Compres. Rate | mAP | FPS
---|---|---|---|---
Not Prune | 64.36M |  1$\times$ | 57.3 | 3.5
Structured | 8.82M |  7.3$\times$ | 39.4 | 11.8
Unstructured | 5.75M |  11.2$\times$ | 52.5 | 7.6
Pattern | 10.22M |  *6.3$\times$ | 52.8 | 9.7
Block | 10.38M |  *6.2$\times$ | 52.4 | 9.1
Block | 7.94M |  8.1$\times$ | 51.3 | 11.5
Hybrid | 7.57M |  8.5$\times$ | 51.7 | 12.3
* Overall compression rate, but only 3$\times$3 CONV layers are pruned.

Figure 10. (a) Latency of two example FC layers. (b) Example of latency
comparisons of 3$\times$3 CONV layer using pattern-based pruning and block-
punched pruning.

Table 3. Accuracy comparison ($\Delta$ acc.) of applying pattern-based pruning and block-punched pruning to the depth-wise 3$\times$3 CONV layers in MobileNetV2. | CIFAR-10 | CIFAR-100
---|---|---
Compres. rate |  7.19$\times$->8.12$\times$ |  2.78$\times$->2.91$\times$
Pattern-based | -0.4 | -0.9
Block-based | -1.01 | -1.51

Table 4. Comparison with PatDNN on CIFAR-10 dataset (top-1 acc.) and ImageNet dataset (top-1/top-5 acc.). Network | Method |  | Pruning
---
scheme
Pruned layers |  | Original
---
acc. (%)
| Compres.
---
rate
| Acc.
---
drop (%)
| Latency
---
(ms)
| MACs
---
CIFAR-10 |
ResNet-50 | PatDNN | Pattern | 3x3 CONV | 95.6 |  1.57$\times$ | -1.0 | 10.44 | 1.9G
Rule-based | Block | 3x3 CONV, 1x1 CONV | 95.6 |  11.51$\times$ | 0.1 | 4.25 | 0.6G
Search-based | Hybrid | 3x3 CONV, 1x1 CONV | 95.6 |  11.88$\times$ | 0.1 | 4.20 | 0.6G
VGG-16 | PatDNN | Pattern | 3x3 CONV | 93.9 |  8.0$\times$ | -0.4 | 2.59 | 73M
Rule-based | Block | 3x3 CONV | 93.9 |  12.38$\times$ | -0.3 | 2.02 | 59M
Search-based | Hybrid | 3x3 CONV | 93.9 |  12.50$\times$ | -0.3 | 2.00 | 58M
MobileNetV2 | PatDNN | Pattern | 3x3 DW CONV | 94.6 |  1.01$\times$ | -0.1 | 3.63 | 296M
Rule-based | Block | 1x1 CONV | 94.6 |  7.53$\times$ | 0.2 | 1.86 | 89M
Search-based | Block | 1x1 CONV | 94.6 |  7.54$\times$ | 0.1 | 1.86 | 89M
ImageNet |
ResNet-50 | PatDNN | Pattern | 3x3 CONV | 76.1/92.8 |  1.56$\times$ | —/-0.2 | 29.89 | 3.0G
Rule-based | Hybrid | 3x3 CONV, 1x1 CONV | 76.1/92.8 |  4.37$\times$ | 0.3/0.1 | 17.26 | 1.6G
Search-based | Hybrid | 3x3 CONV, 1x1 CONV | 76.1/92.8 |  4.41$\times$ | 0.1/0 | 17.22 | 1.6G
VGG-16 | PatDNN | Pattern | 3x3 CONV | 74.5/91.7 |  8.0$\times$ | —/0.1 | 18.91 | 3.8G
Rule-based | Pattern | 3x3 CONV | 74.5/91.7 |  8.22$\times$ | 0.2/0.1 | 18.17 | 3.5G
Search-based | Pattern | 3x3 CONV | 74.5/91.7 |  8.22$\times$ | 0.2/0.1 | 18.17 | 3.5G
MobileNetV2 | PatDNN | Pattern | 3x3 DW CONV | 71.0/90.3 |  1.01$\times$ | —/0 | 4.90 | 300M
Rule-based | Block | 1x1 CONV | 71.0/90.3 |  1.76$\times$ | 0.5/0.3 | 3.98 | 177M
Search-based | Block | 1x1 CONV | 71.0/90.3 |  1.82$\times$ | 0.5/0.3 | 3.90 | 165M

####  6.3.1. Accuracy Analysis on Pattern-based Pruning and Block-Punched
Pruning

From the results on ResNet-18 and VGG-16 with CIFAR-10 and ImageNet dataset,
we make Remark 1. We further examine the remark on YOLOv4 with MS COCO
dataset, which can be reasonably regarded as difficult task, as shown in Table
2. The compression rate refers to the compression rate of the entire model and
the block size is 4$\times$16\. When only 3$\times$3 CONV layers are pruned,
pattern-based pruning achieves a higher mean average precision (mAP), which
matches the remark that pattern-based pruning suits tasks with larger dataset
better on 3$\times$3 CONV layers. However, current pattern-based pruning is
only applicable to 3$\times$3 layers, limiting the compression performance.
With the proposed general pruning scheme applicable to different layers, we
achieve an 8.1$\times$ compression rate with 51.3 mAP and 11.5 frames per
second (FPS). A hybrid pruning scheme by mapping pattern-based pruning to
3$\times$3 CONV layers and block-based/block-punched pruning to all the other
layers can further achieve an 8.5$\times$ compression rate with 51.7 mAP and
12.3 FPS. We also show the results of unstructured pruning and structured
pruning, which achieve 52.5 mAP and 39.4 mAP, and 7.6 FPS and 11.8 FPS,
respectively. It can be observed that our hybrid scheme method is 1.62$\times$
faster than unstructured pruning while maintaining comparable accuracy. When
compared to structured pruning, our hybrid scheme method achieve much higher
accuracy and is also slightly faster than structured pruning at the same time.
This further strengthens the advantage of our proposed method.

####  6.3.2. Latency Analysis on Pattern-based Pruning and Block-Punched
Pruning

We conduct comprehensive comparative experiments offline to analyze the
latency performance of pattern-based pruning and block-punched pruning to
determine the best-suited pruning scheme for 3$\times$3 CONV layers. Fig. 10
(b) shows an example of the latency comparisons for a 3$\times$3 CONV layer
with 28$\times$28 input feature map size and 128 input/output channels under
different compression rates. Under 4$\times$ and 8$\times$ compression,
pattern-based pruning has similar latency performance to block-punched pruning
with a block size of 8$\times$16\. When the compression rate is higher than
12$\times$, pattern-based pruning has similar speed as block-punched pruning
with a block size of 16$\times$32\. However, the latency difference between
pattern-based pruning and block-punched pruning is minor, as we discussed in
Section 5.2.3, thus we consider latency performance as a secondary criterion
in rule-based pruning scheme mapping method.

####  6.3.3. Ablation Study on 3$\times$3 Depth-wise CONV Layer

As mentioned in Section 5.2.4, 3$\times$3 depth-wise CONV layers usually only
account for a small portion of weights and computations, and they play an
important role in capturing spatial correlations in DNNs (Chollet, 2017), thus
we propose not to prune 3$\times$3 depth-wise CONV layers. Table 3 shows the
accuracy results of applying pattern-based pruning and block-punched pruning
to 3$\times$3 depth-wise CONV layers in MobileNetV2. Here we use the baseline
models that all the 1$\times$1 CONV layers are pruned by block-punched pruning
with compression rate 7.19$\times$ and 2.78$\times$ for CIFAR-10 and
CIFAR-100, respectively. Then, on top of the pruned model, we apply an extra
2.22$\times$ pattern-based/block-punched pruning only for the 3$\times$3
depth-wise CONV layers and compare the final accuracy. The results show that
the overall compression rate only increases slightly, but there is non-
negligible accuracy drop for pattern-based pruning and block-based pruning.
Thus, our rule-based pruning scheme mapping method will not map any pruning
scheme for 3$\times$3 depth-wise CONV layers.

####  6.3.4. Evaluations of Automatic Pruning Scheme Mapping Methods

We compare the search-based and rule-based methods with the state-of-the-art
end-to-end inference framework PatDNN (Niu et al., 2020b), which uses pattern-
based pruning with ADMM pruning algorithm. The comparison results are shown in
Table 4. Here, the compression rate refers to the parameter reduction rate of
the CONV layers. The accuracy for ImageNet dataset indicates the top-5
accuracy.

The configurations of the search-based method are obtained using 5 GPU
servers, and take 3 and 9 days for CIFAR-10 and ImageNet models, respectively,
which is acceptable for RL-based search methods (Zoph and Le, 2017; Tan et
al., 2019). We use search-based method to provide a close-to-optimal result,
which indicates the performance upper-bound. Accelerating the search process
is not the main concern of our work, and our search process can be accelerated
by adopting fast evaluation techniques such as Bayesian Optimization (Klein et
al., 2017; Chen et al., 2018a).

For ResNet-50 on CIFAR-10, rule-based method can achieve an 11.51$\times$
compression rate with only 0.1% accuracy drop, significantly higher than the
results obtained by PatDNN. The reason for the limited performance of PatDNN
is that only 44.3% of the parameters of ResNet-50 are in the 3$\times$3 CONV
layers that can be pruned with pattern-based pruning, as shown in Fig. 3. Our
rule-based method, on the other hand, maps the flexible block-punched pruning
that can be applied to CONV layers with different kernel sizes, thus achieving
a much higher compression rate. Search-based method reaches a slightly higher
compression rate and minor latency reduction compared with the rule-based
method.

With the automatic mapping of block-punched pruning and block size provided by
the rule-based method and compression rate derived by the reweighted pruning
algorithm, we reach a 12.38$\times$ compression rate with 0.3% accuracy
improvement on VGG-16 for CIFAR-10 dataset. Still, search-based method renders
a slightly better performance than rule-based method.

For MobileNet-V2, mapping block-based pruning with optimized block size on
1$\times$1 CONV layers by rule-based method achieves a 7.53$\times$
compression rate with only 0.2% accuracy drop. The compression rate is much
higher than PatDNN, as pattern-based pruning cannot be applied to 1$\times$1
CONV, and 3$\times$3 depth-wise CONV layers only account for 1.9% of the
parameters in the model. The performance difference between rule-based method
and search-based method is negligible.

Different from CIFAR-10, pattern-based pruning has a better accuracy
performance on tasks with large datasets like ImageNet as discussed in Remark
1. Hence, rule-based method maps pattern-based pruning to 3$\times$3 CONV
layers and block-punched pruning with optimized block size to the remaining
layers. For ResNet-50 on ImageNet, rule-based method can reach a 4.37$\times$
compression rate with only 0.1% accuracy loss, and 1.73$\times$ speedup on
mobile GPU over PatDNN.

For VGG-16 on ImageNet, both rule-based method and search-based method maps
pattern-based pruning to all the 3$\times$3 layers with the reweighted dynamic
regularization algorithm, and achieves a 8.22$\times$ compression rate with
only 0.1% accuracy loss, which outperforms PatDNN. As all methods adopt
pattern-based pruning, the performance difference between our methods and
PatDNN is attributed to the pruning algorithm. With the reweighted pruning
aglorithm, our method has the advantage of determining the compression rate
for each layer automatically while PatDNN is based on ADMM and requires the
manual setting of the compression rate for each layer. For MobileNet-V2 on
ImageNet dataset, both rule-based method and search-based method map block-
punched pruning to 1$\times$1 CONV layers, and reaches a 1.76$\times$
compression rate and 1.82$\times$ compression rate, respectively.

We also compare our method with other representative model compression
techniques including NetAdapt (Yang et al., 2018), ChamNet (Dai et al.,
2019a), AMC (He et al., 2018), AutoSlim (Liu et al., 2019b), and MetaPruning
(Liu et al., 2019c) on the ImageNet dataset, and the results are shown in
Table 5. At 200M MACs level, our rule-based method achieves the same accuracy
as AMC with fewer MACs. Our method also outperforms the 0.75$\times$ channel
scaled MoileNetV2 in both accuracy and MACs. At 150M MACs level, the model
obtained by our rule-based model achieves the highest top-1 accuracy with
similar MACs compared with AutoSlim and the 0.5$\times$ channel scaled
MobileNetV1.

Combining all the results, we can see that both the rule-based and the search-
based method significantly outperform PatDNN. Rule-based method can provide
pruned models with similar accuracy and latency performance as search-based
method, and avoids the policy training process, thus is more useful in
practice. Moreover, with the assist of our compiler optimization, both methods
can easily achieve real-time DNN inference (less than 33ms) on all models
mentioned above.

Table 5. The comparisons with models obtained by various model compression techniques on ImageNet.  Group | Model | MACs | Top-1 Acc
---|---|---|---
300M MACs |  MobileNetV2 1.0$\times$ | 300M | 71.0%
NetAdapt-MobileNetV1 (Yang et al., 2018) | 284.3M | 69.1%
ChamNet-B (Dai et al., 2019a) | 323M | 73.8%
200M MACs |  MobileNetV2 0.75$\times$ | 209M | 69.8%
AMC-MobileNetV2 (He et al., 2018) | 211M | 70.8%
AutoSlim-MobileNetV2 (Liu et al., 2019b) | 207M | 73%
MetaPruning-MobileNetV2 (Liu et al., 2019c) | 217M | 71.2%
Ours (Rule-based) | 203M | 70.8%
150M MACs |  MobileNetV1 0.5$\times$ | 150M | 63.3%
AutoSlim-MobileNetV1 (Liu et al., 2019b) | 150M | 67.9%
Ours (Rule-based) | 177M | 70.5%
Ours (Rule-based) | 151M | 69.8%

####  6.3.5. Portability Evaluation on Different Platforms

We further evaluate the portability of our proposed rule-based pruning scheme
mapping method on different mobile platforms. Three tested platforms are
Samsung Galaxy S10, S20, and S21, respectively. They are equipped with
different types of chipsets and mobile GPUs. The detailed hardware
specifications are shown in Table 6. Table 7 shows the portability evaluation
results on the three platforms using our rule-based pruning scheme mapping
method. We use VGG16 network and test on CIFAR10 and ImageNet dataset,
respectively. We build latency model for each platform and use the same
latency threshold $\beta=20\%$. It can be observed that our rule-based method
can consistently achieve high model accuracy and leverages the better hardware
for a higher inference speed, which illustrates the stability of our
reweighted pruning algorithm and the effectiveness and portability of our
rule-based method.

Table 6. Hardware specifications of platforms for portability evaluation. Model | Chipset | GPU | RAM
---|---|---|---
Samsung Galaxy S10 | Qualcomm Snapdragon 855 | Adreno 640 | 8GB
Samsung Galaxy S20 | Qualcomm Snapdragon 865 | Adreno 650 | 12GB
Samsung Galaxy S21 | Qualcomm Snapdragon 888 | Adreno 666 | 8GB
Table 7. Portability evaluation on different platforms using rule-based method on VGG16. Dataset | Platform |  | Compres.
---
rate
MACs |  | Top-1
---
acc.
| Latency
---
(ms)
CIFAR10 | Galaxy S10 |  12.38$\times$ | 59M | 94.2% | 2.02
Galaxy S20 |  12.06$\times$ | 62M | 94.1% | 1.85
Galaxy S21 |  12.12$\times$ | 61M | 94.2% | 1.65
ImageNet | Galaxy S10 |  8.22$\times$ | 3.5G | 74.3% | 18.17
Galaxy S20 |  8.12$\times$ | 3.4G | 74.5% | 16.23
Galaxy S21 |  8.15$\times$ | 3.4G | 74.5% | 15.12

##  7\. Conclusion

We propose a general pruning scheme with fine-grained structured pruning
regularity and reweighted dynamic pruning algorithm. Compiler optimizations
are introduced to extract the structure information and exploit hardware
parallelism. We further probe into the new problem of mapping the best-suited
pruning scheme for each layer of any given DNN and propose two automatic
pruning scheme mapping methods. Experimental results demonstrate the
effectiveness of the proposed pruning scheme and pruning scheme mapping
methods.

###### Acknowledgements.

This research is partially funded by National Science Foundation CCF-1919117,
CNS-1909172, CCF-2047516 (CAREER), and CCF-1901378, and Jeffress Trust Awards
in Interdisciplinary Research to William & Mary. Any opinions, findings, and
conclusions or recommendations expressed in this material are those of the
authors and do not necessarily reflect the views of NSF or Thomas F. and Kate
Miller Jeffress Memorial Trust.

## References

  * (1)
  * Ten ([n.d.]) [n.d.].  https://www.tensorflow.org/mobile/tflite/.
  * Ali ([n.d.]) [n.d.].  https://github.com/alibaba/MNN.
  * Pyt ([n.d.]) [n.d.].  https://pytorch.org/mobile/home.
  * Ashari et al. (2015) Arash Ashari, Shirish Tatikonda, Matthias Boehm, Berthold Reinwald, Keith Campbell, John Keenleyside, and P Sadayappan. 2015\.  On optimizing machine learning workloads via kernel fusion.  _ACM SIGPLAN Notices_ 50, 8 (2015), 173–182.
  * Bezanson et al. (2017) Jeff Bezanson, Alan Edelman, Stefan Karpinski, and Viral B Shah. 2017.  Julia: A fresh approach to numerical computing.  _SIAM review_ 59, 1 (2017), 65–98.
  * Bochkovskiy et al. (2020) Alexey Bochkovskiy, Chien-Yao Wang, and Hong-Yuan Mark Liao. 2020.  Yolov4: Optimal speed and accuracy of object detection.  _arXiv preprint arXiv:2004.10934_ (2020).
  * Boehm et al. (2018) Matthias Boehm, Berthold Reinwald, Dylan Hutchison, Alexandre V Evfimievski, and Prithviraj Sen. 2018\.  On optimizing operator fusion plans for large-scale machine learning in systemml.  _arXiv preprint arXiv:1801.00829_ (2018).
  * Cai et al. (2018) Han Cai, Ligeng Zhu, and Song Han. 2018.  Proxylessnas: Direct neural architecture search on target task and hardware.  _arXiv preprint arXiv:1812.00332_ (2018).
  * Cai et al. (2021) Yuxuan Cai, Hongjia Li, Geng Yuan, Wei Niu, Yanyu Li, Xulong Tang, Bin Ren, and Yanzhi Wang. 2021\.  YOLObile: Real-Time Object Detection on Mobile Devices via Compression-Compilation Co-Design. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 35. 955–963.
  * Candes et al. (2008) Emmanuel J Candes, Michael B Wakin, and Stephen P Boyd. 2008\.  Enhancing sparsity by reweighted $\ell_{1}$ minimization.  _Journal of Fourier analysis and applications_ 14, 5-6 (2008), 877–905.
  * Chen et al. (2018b) Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan, Haichen Shen, Meghan Cowan, Leyuan Wang, Yuwei Hu, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. 2018b.  TVM: An automated end-to-end optimizing compiler for deep learning. In _the USENIX Symposium on Operating Systems Design and Implementation (OSDI)_.
  * Chen et al. (2018a) Yutian Chen, Aja Huang, Ziyu Wang, Ioannis Antonoglou, Julian Schrittwieser, David Silver, and Nando de Freitas. 2018a.  Bayesian optimization in alphago.  _arXiv preprint arXiv:1812.06855_ (2018).
  * Chollet (2017) François Chollet. 2017\.  Xception: Deep learning with depthwise separable convolutions. In _Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR)_.
  * Dai et al. (2019a) Xiaoliang Dai, Yangqing Jia, Peter Vajda, Matt Uyttendaele, Niraj K. Jha, Peizhao Zhang, Bichen Wu, Hongxu Yin, Fei Sun, Yanghan Wang, and et al. 2019a.  ChamNet: Towards Efficient Network Design Through Platform-Aware Model Adaptation.  _2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ (Jun 2019).  https://doi.org/10.1109/cvpr.2019.01166
  * Dai et al. (2019b) Xiaoliang Dai, Hongxu Yin, and Niraj K Jha. 2019b.  Grow and Prune Compact, Fast, and Accurate LSTMs.  _IEEE Trans. Comput._ 69, 3 (2019), 441–452.
  * Dai et al. (2019c) Xiaoliang Dai, Hongxu Yin, and Niraj K Jha. 2019c.  NeST: A neural network synthesis tool based on a grow-and-prune paradigm.  _IEEE Trans. Comput._ 68, 10 (2019), 1487–1497.
  * Deng et al. (2009) Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. 2009\.  Imagenet: A large-scale hierarchical image database. In _Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on_. IEEE, 248–255.
  * Dong et al. (2020) Peiyan Dong, Siyue Wang, Wei Niu, Chengming Zhang, Sheng Lin, Zhengang Li, Yifan Gong, Bin Ren, Xue Lin, and Dingwen Tao. 2020.  Rtmobile: Beyond real-time mobile acceleration of rnns for speech recognition. In _2020 57th ACM/IEEE Design Automation Conference (DAC)_. IEEE, 1–6.
  * Dong and Yang (2019) Xuanyi Dong and Yi Yang. 2019.  Network pruning via transformable architecture search. In _Advances in Neural Information Processing Systems (NeurIPS)_. 759–770.
  * Frankle and Carbin (2018) Jonathan Frankle and Michael Carbin. 2018.  The lottery ticket hypothesis: Finding sparse, trainable neural networks. In _The International Conference on Learning Representations (ICLR)_.
  * Gong et al. (2020) Yifan Gong, Zheng Zhan, Zhengang Li, Wei Niu, Xiaolong Ma, Wenhao Wang, Bin Ren, Caiwen Ding, Xue Lin, Xiaolin Xu, et al. 2020\.  A privacy-preserving-oriented dnn pruning and mobile acceleration framework. In _Proceedings of the 2020 on Great Lakes Symposium on VLSI_. 119–124.
  * Guo et al. (2016) Yiwen Guo, Anbang Yao, and Yurong Chen. 2016.  Dynamic network surgery for efficient dnns. In _Advances in Neural Information Processing Systems (NeurIPS)_.
  * Han et al. (2015) Song Han, Jeff Pool, John Tran, and William Dally. 2015\.  Learning both weights and connections for efficient neural network. In _Advances in neural information processing systems (NeurIPS)_.
  * Han et al. (2016) Seungyeop Han, Haichen Shen, Matthai Philipose, Sharad Agarwal, Alec Wolman, and Arvind Krishnamurthy. 2016\.  Mcdnn: An approximation-based execution framework for deep stream processing under resource constraints. In _Proceedings of the 14th Annual International Conference on Mobile Systems, Applications, and Services (MobiSys)_. ACM, 123–136.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016\.  Deep residual learning for image recognition. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * He et al. (2018) Yihui He, Ji Lin, Zhijian Liu, Hanrui Wang, Li-Jia Li, and Song Han. 2018\.  Amc: Automl for model compression and acceleration on mobile devices. In _Proceedings of the European Conference on Computer Vision (ECCV)_.
  * He et al. (2019) Yang He, Ping Liu, Ziwei Wang, Zhilan Hu, and Yi Yang. 2019.  Filter pruning via geometric median for deep convolutional neural networks acceleration. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * He et al. (2017) Yihui He, Xiangyu Zhang, and Jian Sun. 2017.  Channel pruning for accelerating very deep neural networks. In _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_.
  * Hegde et al. (2016) Gopalakrishna Hegde, Siddhartha, Nachiappan Ramasamy, and Nachiket Kapre. 2016.  CaffePresso: an optimized library for deep learning on embedded accelerator-based platforms. In _2016 International Conference on Compliers, Architectures, and Sythesis of Embedded Systems (CASES)_. IEEE, 1–10.
  * Huynh et al. (2017) Loc N Huynh, Youngki Lee, and Rajesh Krishna Balan. 2017\.  Deepmon: Mobile gpu-based deep learning framework for continuous vision applications. In _Proceedings of the 15th Annual International Conference on Mobile Systems, Applications, and Services (MobiSys)_. ACM, 82–95.
  * Jian et al. (2021) Tong Jian, Yifan Gong, Zheng Zhan, Runbin Shi, Nasim Soltani, Zifeng Wang, Jennifer G Dy, Kaushik Roy Chowdhury, Yanzhi Wang, and Stratis Ioannidis. 2021\.  Radio Frequency Fingerprinting on the Edge.  _IEEE Transactions on Mobile Computing_ (2021).
  * Klein et al. (2017) Aaron Klein, Stefan Falkner, Simon Bartels, Philipp Hennig, and Frank Hutter. 2017.  Fast bayesian optimization of machine learning hyperparameters on large datasets. In _Artificial Intelligence and Statistics_. PMLR, 528–536.
  * Lane et al. (2016) Nicholas D Lane, Sourav Bhattacharya, Petko Georgiev, Claudio Forlivesi, Lei Jiao, Lorena Qendro, and Fahim Kawsar. 2016.  Deepx: A software accelerator for low-power deep learning inference on mobile devices. In _Proceedings of the 15th International Conference on Information Processing in Sensor Networks_. IEEE Press, 23.
  * Lane et al. (2017) Nicholas D Lane, Sourav Bhattacharya, Akhil Mathur, Petko Georgiev, Claudio Forlivesi, and Fahim Kawsar. 2017.  Squeezing deep learning into mobile and embedded devices.  _IEEE Pervasive Computing_ 16, 3 (2017), 82–88.
  * Lane et al. (2015) Nicholas D Lane, Petko Georgiev, and Lorena Qendro. 2015\.  DeepEar: robust smartphone audio sensing in unconstrained acoustic environments using deep learning. In _Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing_. ACM, 283–294.
  * Li et al. (2017) Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. 2017.  Pruning filters for efficient convnets.  _International Conference on Learning Representations (ICLR)_ (2017).
  * Li et al. (2021) Hongjia Li, Geng Yuan, Wei Niu, Yuxuan Cai, Mengshu Sun, Zhengang Li, Bin Ren, Xue Lin, and Yanzhi Wang. 2021.  Real-Time Mobile Acceleration of DNNs: From Computer Vision to Medical Applications. In _2021 26th Asia and South Pacific Design Automation Conference (ASP-DAC)_. IEEE, 581–586.
  * Li and Malik (2016) Ke Li and Jitendra Malik. 2016.  Learning to optimize.  _arXiv preprint arXiv:1606.01885_ (2016).
  * Li et al. (2019) Tuanhui Li, Baoyuan Wu, Yujiu Yang, Yanbo Fan, Yong Zhang, and Wei Liu. 2019\.  Compressing convolutional neural networks via factorized convolutional filters. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Li et al. (2020a) Yuhang Li, Xin Dong, and Wei Wang. 2020a.  Additive Powers-of-Two Quantization: An Efficient Non-uniform Discretization for Neural Networks. In _International Conference on Learning Representations (ICLR)_.
  * Li et al. (2020b) Zhengang Li, Yifan Gong, Xiaolong Ma, Sijia Liu, Mengshu Sun, Zheng Zhan, Zhenglun Kong, Geng Yuan, and Yanzhi Wang. 2020b.  SS-Auto: A Single-Shot, Automatic Structured Weight Pruning Framework of DNNs with Ultra-High Efficiency.  _arXiv preprint arXiv:2001.08839_ (2020).
  * Lin et al. (2014) Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. 2014.  Microsoft coco: Common objects in context. In _European conference on computer vision_. Springer, 740–755.
  * Liu et al. (2019a) Ning Liu, Xiaolong Ma, Zhiyuan Xu, Yanzhi Wang, Jian Tang, and Jieping Ye. 2019a.  AutoCompress: An Automatic DNN Structured Pruning Framework for Ultra-High Compression Rates.  _arXiv preprint arXiv:1907.03141_ (2019).
  * Liu et al. (2019b) Ning Liu, Xiaolong Ma, Zhiyuan Xu, Yanzhi Wang, Jian Tang, and Jieping Ye. 2019b.  AutoSlim: An Automatic DNN Structured Pruning Framework for Ultra-High Compression Rates.  _arXiv preprint arXiv:1907.03141_ (2019).
  * Liu et al. (2020) Ning Liu, Xiaolong Ma, Zhiyuan Xu, Yanzhi Wang, Jian Tang, and Jieping Ye. 2020\.  AutoCompress: An Automatic DNN Structured Pruning Framework for Ultra-High Compression Rates. In _AAAI_.
  * Liu et al. (2017) Zhuang Liu, Jianguo Li, Zhiqiang Shen, Gao Huang, Shoumeng Yan, and Changshui Zhang. 2017\.  Learning efficient convolutional networks through network slimming. In _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_.
  * Liu et al. (2019c) Zechun Liu, Haoyuan Mu, Xiangyu Zhang, Zichao Guo, Xin Yang, Kwang-Ting Cheng, and Jian Sun. 2019c.  MetaPruning: Meta Learning for Automatic Neural Network Channel Pruning.  _2019 IEEE/CVF International Conference on Computer Vision (ICCV)_ (Oct 2019).  https://doi.org/10.1109/iccv.2019.00339
  * Liu et al. (2018) Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. 2018.  Rethinking the Value of Network Pruning. In _International Conference on Learning Representations_.
  * Luo et al. (2017) Jian-Hao Luo, Jianxin Wu, and Weiyao Lin. 2017.  Thinet: A filter level pruning method for deep neural network compression. In _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_.
  * Ma et al. (2020a) Xiaolong Ma, Fu-Ming Guo, Wei Niu, Xue Lin, Jian Tang, Kaisheng Ma, Bin Ren, and Yanzhi Wang. 2020a.  Pconv: The missing but desirable sparsity in dnn weight pruning for real-time execution on mobile devices. In _Thirty-Fourth AAAI conference on artificial intelligence (AAAI)_.
  * Ma et al. (2020b) Xiaolong Ma, Zhengang Li, Yifan Gong, Tianyun Zhang, Wei Niu, Zheng Zhan, Pu Zhao, Jian Tang, Xue Lin, Bin Ren, et al. 2020b.  Blk-rew: A unified block-based dnn pruning framework using reweighted regularization method.  _arXiv preprint arXiv:2001.08357_ (2020).
  * Ma et al. (2019a) Xiaolong Ma, Sheng Lin, Shaokai Ye, Zhezhi He, Linfeng Zhang, Geng Yuan, Sia Huat Tan, Zhengang Li, Deliang Fan, Xuehai Qian, Xue Lin, Kaisheng Ma, and Yanzhi Wang. 2019a.  Non-Structured DNN Weight Pruning – Is It Beneficial in Any Platform?  arXiv:1907.02124 [cs.LG]
  * Ma et al. (2020c) Xiaolong Ma, Wei Niu, Tianyun Zhang, Sijia Liu, Sheng Lin, Hongjia Li, Wujie Wen, Xiang Chen, Jian Tang, Kaisheng Ma, et al. 2020c.  An image enhancing pattern-based sparsity for real-time inference on mobile devices. In _European Conference on Computer Vision_. Springer, 629–645.
  * Ma et al. (2020d) Xiaolong Ma, Geng Yuan, Sheng Lin, Caiwen Ding, Fuxun Yu, Tao Liu, Wujie Wen, Xiang Chen, and Yanzhi Wang. 2020d.  Tiny but Accurate: A Pruned, Quantized and Optimized Memristor Crossbar Framework for Ultra Efficient DNN Implementation. In _ASP-DAC_.
  * Ma et al. (2020e) Xiaolong Ma, Geng Yuan, Sheng Lin, Caiwen Ding, Fuxun Yu, Tao Liu, Wujie Wen, Xiang Chen, and Yanzhi Wang. 2020e.  Tiny but accurate: A pruned, quantized and optimized memristor crossbar framework for ultra efficient dnn implementation. In _2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC)_. IEEE, 301–306.
  * Ma et al. (2019b) Xiaolong Ma, Geng Yuan, Sheng Lin, Zhengang Li, Hao Sun, and Yanzhi Wang. 2019b.  ResNet Can Be Pruned 60$\times$: Introducing Network Purification and Unused Path Removal (P-RM) after Weight Pruning. In _2019 IEEE/ACM International Symposium on Nanoscale Architectures (NANOARCH)_. IEEE, 1–2.
  * Min et al. (2018) Chuhan Min, Aosen Wang, Yiran Chen, Wenyao Xu, and Xin Chen. 2018.  2pfpce: Two-phase filter pruning based on conditional entropy.  _arXiv preprint arXiv:1809.02220_ (2018).
  * Niu et al. (2020a) Wei Niu, Zhenglun Kong, Geng Yuan, Weiwen Jiang, Jiexiong Guan, Caiwen Ding, Pu Zhao, Sijia Liu, Bin Ren, and Yanzhi Wang. 2020a.  Achieving Real-Time Execution of Transformer-based Large-scale Models on Mobile with Compiler-aware Neural Architecture Optimization.  _arXiv preprint arXiv:2009.06823_ (2020).
  * Niu et al. (2020b) Wei Niu, Xiaolong Ma, Sheng Lin, Shihao Wang, Xuehai Qian, Xue Lin, Yanzhi Wang, and Bin Ren. 2020b.  Patdnn: Achieving real-time DNN execution on mobile devices with pattern-based weight pruning. In _Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)_.
  * Ota et al. (2017) Kaoru Ota, Minh Son Dao, Vasileios Mezaris, and Francesco GB De Natale. 2017.  Deep learning for mobile multimedia: A survey.  _ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM)_ 13, 3s (2017), 1–22.
  * Ren et al. (2019a) Ao Ren, Tianyun Zhang, Shaokai Ye, Jiayu Li, Wenyao Xu, Xuehai Qian, Xue Lin, and Yanzhi Wang. 2019a.  Admm-nn: An algorithm-hardware co-design framework of dnns using alternating direction methods of multipliers. In _Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)_.
  * Ren et al. (2019b) Ao Ren, Tianyun Zhang, Shaokai Ye, Wenyao Xu, Xuehai Qian, Xue Lin, and Yanzhi Wang. 2019b.  ADMM-NN: an algorithm-hardware co-design framework of DNNs using alternating direction methods of multipliers. In _ASPLOS_.
  * Sandler et al. (2018) Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen. 2018.  Mobilenetv2: Inverted residuals and linear bottlenecks. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Simonyan and Zisserman (2014) Karen Simonyan and Andrew Zisserman. 2014.  Very deep convolutional networks for large-scale image recognition.  _arXiv:1409.1556_ (2014).
  * Sutton and Barto (2018) Richard S Sutton and Andrew G Barto. 2018.  _Reinforcement learning: An introduction_.  MIT press.
  * Sutton et al. (1999) Richard S Sutton, David A McAllester, Satinder P Singh, Yishay Mansour, et al. 1999\.  Policy gradient methods for reinforcement learning with function approximation.. In _NIPs_ , Vol. 99. Citeseer, 1057–1063.
  * Tan et al. (2019) Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoc V Le. 2019.  Mnasnet: Platform-aware neural architecture search for mobile. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_. 2820–2828.
  * Wang et al. (2019) Yanzhi Wang, Shaokai Ye, Zhezhi He, Xiaolong Ma, Linfeng Zhang, Sheng Lin, Geng Yuan, Sia Huat Tan, Zhengang Li, Deliang Fan, Xuehai Qian, Xue Lin, and Kaisheng Ma. 2019.  Non-structured DNN weight pruning considered harmful.  _arXiv:1907.02124_ (2019).
  * Wen et al. (2016) Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. 2016.  Learning structured sparsity in deep neural networks. In _Advances in Neural Information Processing Systems (NeurIPS)_.
  * Wu et al. (2019) Bichen Wu, Xiaoliang Dai, Peizhao Zhang, Yanghan Wang, Fei Sun, Yiming Wu, Yuandong Tian, Peter Vajda, Yangqing Jia, and Kurt Keutzer. 2019\.  Fbnet: Hardware-aware efficient convnet design via differentiable neural architecture search. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_. 10734–10742.
  * Xu et al. (2018) Mengwei Xu, Mengze Zhu, Yunxin Liu, Felix Xiaozhu Lin, and Xuanzhe Liu. 2018.  DeepCache: Principled Cache for Mobile Deep Vision. In _Proceedings of the 24th Annual International Conference on Mobile Computing and Networking_. ACM, 129–144.
  * Yang et al. (2018) Tien-Ju Yang, Andrew Howard, Bo Chen, Xiao Zhang, Alec Go, Mark Sandler, Vivienne Sze, and Hartwig Adam. 2018\.  NetAdapt: Platform-Aware Neural Network Adaptation for Mobile Applications.  _Lecture Notes in Computer Science_ (2018), 289–304.  https://doi.org/10.1007/978-3-030-01249-6_18
  * Yao et al. (2017) Shuochao Yao, Shaohan Hu, Yiran Zhao, Aston Zhang, and Tarek Abdelzaher. 2017.  Deepsense: A unified deep learning framework for time-series mobile sensing data processing. In _Proceedings of the 26th International Conference on World Wide Web_. 351–360.
  * Yu et al. (2018) Ruichi Yu, Ang Li, Chun-Fu Chen, Jui-Hsin Lai, Vlad I Morariu, Xintong Han, Mingfei Gao, Ching-Yung Lin, and Larry S Davis. 2018.  Nisp: Pruning networks using neuron importance score propagation. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Yuan et al. (2021a) Geng Yuan, Payman Behnam, Zhengang Li, Ali Shafiee, Sheng Lin, Xiaolong Ma, Hang Liu, Xuehai Qian, Mahdi Nazm Bojnordi, Yanzhi Wang, and et al. 2021a.  FORMS: Fine-grained Polarized ReRAM-based In-situ Computation for Mixed-signal DNN Accelerator.  _2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA)_ (Jun 2021).  https://doi.org/10.1109/isca52012.2021.00029
  * Yuan et al. (2019a) Geng Yuan, Xiaolong Ma, Caiwen Ding, Sheng Lin, Tianyun Zhang, Zeinab S Jalali, Yilong Zhao, Li Jiang, Sucheta Soundarajan, and Yanzhi Wang. 2019a.  An ultra-efficient memristor-based dnn framework with structured weight pruning and quantization using admm. In _2019 IEEE/ACM International Symposium on Low Power Electronics and Design (ISLPED)_. IEEE, 1–6.
  * Yuan et al. (2019b) Geng Yuan, Xiaolong Ma, Sheng Lin, Zhengang Li, and Caiwen Ding. 2019b.  A SOT-MRAM-based Processing-In-Memory Engine for Highly Compressed DNN Implementation.  _arXiv preprint arXiv:1912.05416_ (2019).
  * Yuan et al. (2021b) Geng Yuan, Xiaolong Ma, Wei Niu, Zhengang Li, Zhenglun Kong, Ning Liu, Yifan Gong, Zheng Zhan, Chaoyang He, Qing Jin, Siyue Wang, Minghai Qin, Bin Ren, Yanzhi Wang, Sijia Liu, and Xue Lin. 2021b.  MEST: Accurate and Fast Memory-Economic Sparse Training Framework on the Edge.  arXiv:2110.14032 [cs.LG]
  * Zhan et al. (2021) Zheng Zhan, Yifan Gong, Pu Zhao, Geng Yuan, Wei Niu, Yushu Wu, Tianyun Zhang, Malith Jayaweera, David Kaeli, Bin Ren, et al. 2021\.  Achieving on-Mobile Real-Time Super-Resolution with Neural Architecture and Pruning Search. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 4821–4831.
  * Zhang et al. (2019) Chaoyun Zhang, Paul Patras, and Hamed Haddadi. 2019\.  Deep learning in mobile and wireless networking: A survey.  _IEEE Communications Surveys & Tutorials_ 21, 3 (2019), 2224–2287.
  * Zhang et al. (2018a) Tianyun Zhang, Shaokai Ye, Kaiqi Zhang, Jian Tang, Wujie Wen, Makan Fardad, and Yanzhi Wang. 2018a.  A systematic dnn weight pruning framework using alternating direction method of multipliers. In _Proceedings of the European Conference on Computer Vision (ECCV)_.
  * Zhang et al. (2018b) Tianyun Zhang, Kaiqi Zhang, Shaokai Ye, Jiayu Li, Jian Tang, Wujie Wen, Xue Lin, Makan Fardad, and Yanzhi Wang. 2018b.  Adam-admm: A unified, systematic framework of structured weight pruning for dnns.  _arXiv:1807.11091_ (2018).
  * Zhao et al. (2019) Chenglong Zhao, Bingbing Ni, Jian Zhang, Qiwei Zhao, Wenjun Zhang, and Qi Tian. 2019\.  Variational convolutional neural network pruning. In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Zhao et al. (2020) Pu Zhao, Wei Niu, Geng Yuan, Yuxuan Cai, Hsin-Hsuan Sung, Wujie Wen, Sijia Liu, Xipeng Shen, Bin Ren, Yanzhi Wang, et al. 2020\.  Achieving Real-Time LiDAR 3D Object Detection on a Mobile Device.  _arXiv preprint arXiv:2012.13801_ (2020).
  * Zhong et al. (2018) Zhao Zhong, Junjie Yan, Wei Wu, Jing Shao, and Cheng-Lin Liu. 2018.  Practical block-wise neural network architecture generation. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 2423–2432.
  * Zhu et al. (2018) Xiaotian Zhu, Wengang Zhou, and Houqiang Li. 2018.  Improving Deep Neural Network Sparsity through Decorrelation Regularization. In _Proceedings of International Joint Conferences on Artificial Intelligence (IJCAI)_.
  * Zhuang et al. (2018) Zhuangwei Zhuang, Mingkui Tan, Bohan Zhuang, Jing Liu, Yong Guo, Qingyao Wu, Junzhou Huang, and Jinhui Zhu. 2018\.  Discrimination-aware channel pruning for deep neural networks. In _Advances in Neural Information Processing Systems (NeurIPS)_.
  * Zoph and Le (2017) Barret Zoph and Quoc V. Le. 2017.  Neural Architecture Search with Reinforcement Learning. In _International Conference on Learning Representations (ICLR)_.

##  Appendix A Compiler Optimization Details

We provide more details of our compiler optimizations in this section.
Different from prior DNN inference acceleration frameworks (Ten, [n.d.]; Pyt,
[n.d.]; Ali, [n.d.]; Chen et al., 2018b; Niu et al., 2020b; Ma et al., 2020a)
that only support dense models or pattern-based pruned models, our compiler
optimizations are general, support both dense (unpruned) model and sparse
(pruned) model with different pruning schemes for fast inference on various
mobile platforms. Besides the blocked compressed storage (BCS) and the row
reordering optimization mentioned in the main paper (Section 4.3), our
compiler-based optimization techniques also include (i) a layer fusion
mechanism to fuse different layers together for the reduction of memory
consumption of intermediate results and number of operators; (ii) an auto-
tuning process to determine the best-suited configurations of parameters for
different mobile CPUs/GPUs; (iii) Domain Specific Language (DSL) based code
generation.

###  A.1. Layer Fusion Mechanism

To effectively reduce the model inference latency, a layer fusion technique is
incorporated in our compiler optimization to fuse the computation operators in
the computation graph. With layer fusion, both the memory consumption of the
intermediate results and the number of operators can be reduced. The fusion
candidates in a model are identified based on two kinds of polynomial
calculation properties, i.e., compression laws and data access patterns. The
compression laws include associative property, communicative property, and
distributive property.

However, looking for the fusion candidates in such a large space of all
combinations of computation operations is too expensive. Therefore, we
introduce two constraints to guide the looking up process: (i) only explore
the opportunities that are specifically provided due to the above properties,
and (ii) only consider enlarging the overall computation for CPU/GPU
utilization improvement and reducing the memory access for memory performance
improvement as the cost metrics in the fusion. Compared with prior works on
loop fusion (Ashari et al., 2015; Bezanson et al., 2017; Boehm et al., 2018),
our method is more aggressive without high exploration cost.

###  A.2. Auto-Tuning for Different Mobile CPUs/GPUs

During DNN execution, there are many tuning parameters, e.g., matrix tiling
sizes, loop unrolling factors, and data placement on GPU memory, that
influence the performance. It is hard to determine the best-suited
configuration of these parameters manually. To alleviate this problem, our
compiler incorporates an auto-tuning approach for both sparse (pruned) model
and dense (unpruned) model. The Genetic Algorithm is leveraged to explore the
best-suited configurations automatically. It starts parameter search after an
initialization with an arbitrary number of chromosomes and explores the
parallelism better. Acceleration codes for different DNN models and different
mobile CPUs/GPUs can be generated efficiently and quickly through this auto-
tuning process, providing the foundation for fast end-to-end inference. The
auto-tuning optimizations, together with the layer-fusion and sparse model
optimizations, make our framework outperform other acceleration frameworks.

###  A.3. DSL-based Code Generation

In deep learning, a computational graph of a DNN model can be represented by a
directed acyclic graph (DAG). Each node in this graph corresponds to an
operator. We propose a high-level Domain Specific Language (DSL) to specify
such kind of operators. Each operator in a computational graph also with a
layerwise Intermediate Representation (IR) which contains BCS pruning
information. The input and output are different tensors in terms of different
shapes. This DSL also provides a Tensor function for users to create matrices
(or tensors).

In this way, DSL is equivalent to a computational graph (that is, DSL is
another type of high-level functions used to simulate the data flow of the DNN
model), and they can be easily converted to each other. DSL provides users
with the flexibility to use existing DNNs or create new DNNs, improving the
productivity of DNN programming. If the DNN already exists, we will convert it
into an optimized calculation graph and convert this graph into a DSL.
Otherwise, the user writes the model code in the DSL, converts it back to a
calculation graph, performs advanced optimization, and regenerates the
optimized DSL code.

Finally, our compiler translates the DSL into low-level C++ code for mobile
CPU and OpenCL code for mobile GPU, and optimizes the low-level code through a
set of optimizations enabled by BCS pruning. The generated code can be then
deployed on the mobile device.