CN111368699B - Convolutional neural network pruning method based on patterns and pattern perception accelerator - Google Patents

Abstract

The pattern-based convolutional neural network pruning method and the pattern-aware accelerator of the present invention first propose a pattern-based convolutional neural network (PCNN) filter, and realize regular pruning in the filter based on a multi-knapsack framework, which can be compared with existing There are pruning methods that are orthogonal, which are similar to fine-grained sparsity, but still retain some regularity to some extent. In each layer, we limit the number of non-zeros in the filter to be the same, so that the computational workload can be the same for different convolution windows. Based on the uniform sparsity ratio in the filter, the types of patterns in a layer are very limited. Using a pattern mask with very few bits and the corresponding non-zero sequence to describe the filter, instead of describing all the values, significantly reduces the memory size and calculation amount, and is very friendly to accuracy and hardware. And it can be orthogonal to other pruning methods such as filter pruning. PCNN's pruning method can achieve up to 9 times weight pruning, and the loss of accuracy is negligible.

Description

Pattern-Based Convolutional Neural Network Pruning Method and Pattern-Aware Accelerator

technical field

The invention relates to a convolutional neural network method and hardware optimization, in particular to a pattern-based convolutional neural network pruning method and a pattern-aware accelerator.

Background technique

Neural network is one of the most important algorithms in the field of artificial intelligence at present, and it can be widely used in fields such as face recognition, self-driving and health care. Traditionally, a neural network consists of three distinct layers, including a convolutional layer, a pooling layer, and a fully connected layer, which implement feature extraction, downsampling, and classification functions, respectively. With the development of network architectures, convolutional layers have become the main bottleneck of computation and storage. Therefore, in order to bring artificial intelligence to various fields with lower overhead, it is urgent to solve a large number of calculations and parameters.

Convolutional neural networks (CNNs) have been rapidly developed in many applications such as image classification, object detection, and natural language processing. In the existing technology, a trend to improve accuracy is to increase the model capacity, but with it, the workload (memory access loss) and parameters have increased by more than 10 billion and 60 million respectively. As a result, traditional embedded computing platforms like CPUs are not powerful enough to handle such large amounts of data. For edge devices with a large number of parallel units, many accelerators for neural networks implemented on ASICs or FPGAs are proposed.

While these accelerators can improve throughput, moving off-chip data from DRAM to on-chip storage and processing large amounts of computation is still very challenging. Various methods have been proposed to further reduce the storage and computation burden, including low-rank factorization, quantization, and knowledge distillation. Another effective method is weight pruning, which can significantly reduce the model size. However, the methods proposed in earlier research pruned the weights randomly (called ragged pruning), which required sparse models to be stored in a variant of the Sparse Column Compression (CSC) format, resulting in considerable additional indices. to represent the ownership value. Furthermore, in highly parallel architectures, the imbalance of workload among different computing units leads to stalls or complicated workload arbitration design, preventing these hardware from fully exploiting the advantages of weight pruning.

Compared with irregular pruning, regular pruning is more hardware-friendly, including channel pruning, filter pruning, convolution kernel/connection pruning and shape pruning, as shown in Figure 1. Channel and filter pruning are used for input and output channels that are equal in depth, respectively, and channel pruning is equivalent to filter pruning for input and output, respectively. Convolution kernel or connection pruning means the same, i.e. remove some filters between input and output channels. And shape pruning is pruning the weights in the filter at the same position. Rule pruning has been explored for hardware friendliness. Explore different granularities, including irregular sparsity (0-dimensional), vector-level sparsity (1-dimensional), kernel-level sparsity (2-dimensional), and filter-level sparsity (3-dimensional). However, it can be observed that higher levels of sparsity have a greater impact on accuracy than lower levels of sparsity. In short, on the one hand, coarse-grained pruning seriously affects the accuracy, on the other hand, fine-grained pruning is not friendly to hardware, and it is urgent to find a better granularity.

The purpose of pruning is to remove redundancy, and model compression is an effective method to remove redundancy in the original model. Model compression involves various methods, including parameter pruning and sharing, low-rank factorization, and knowledge distillation. Pruning methods are the equivalent of a surgeon to remove redundant neurons or synapses inherent in neural networks that are not performance sensitive. By locating non-informative weights throughout the network, it can easily reduce parameters by more than a factor of 2 with negligible drop in accuracy. Approximate the original parameters using low-rank factorized tensors or matrix degradations with fewer parameters. Knowledge distillation trains a compressed thinner neural network by distilling a large neural network. However, because the basic idea of knowledge distillation is to train a compact model from a teacher model by learning the class distribution output by softmax, knowledge distillation can only be applied to classification tasks with a softmax loss function. Compared to the other two compression methods, model pruning enjoys better compression ratios and robustness to various settings.

The earliest model pruning proposed an iterative pruning method to prune small non-informative weights. For AlexNet on the ImageNet dataset, it reduces the number of weights by a factor of 9 and the amount of computation by a factor of 3. AMC is provided to automatically select the best pruning settings instead of manual methods for better compression and precision. However, when deploying compressed models on hardware, unavoidable indexing overhead is required to encode weights with 4-bit indexes stored in sparse columnar compression (CSC) format. Furthermore, unbalanced workloads across different computing channels lead to insufficient parallelism. The root of this problem lies in the irregularity of its pruning.

Regular pruning solves this problem by pruning weights in a regular fashion. Existing regular pruning methods aim at reducing input/output channels and aim at pruning several kernels in order to remove kernel connectivity between input and output channels or filter intra- weights.

To deal with the trade-off between existing regular pruning methods and accuracy, finer-grained pruning is required to preserve prediction accuracy while preserving regularity without requiring extensive indexes.

As shown in Figure 2, the bottom of the pruning algorithm pyramid is more regular but harmful to accuracy, while the top is irregular but less harmful. There is a gap between shape-level pruning and fine-grained pruning to develop a method that is less sensitive to model compression but still regular. Compared to vector pruning or intra-filter stride pruning or shape pruning, pruned filters with patterns seem to be an Best way. It is reasonable to assume that the prediction accuracy of this pruned model can be improved when we make those non-zero values naturally distribute across the filter rather than constraining them to be aligned in a vector or in a fixed shape, but in practice the algorithm And the results introduced in the architecture are less obvious. For the algorithm, the total pattern set of IKR with finite elements lacks a reliable selection process, and the pattern selection of the filter is based only on the l1-norm. This approach is insufficient to preserve the accuracy of the entire model, since error propagation through the layers is ignored. Furthermore, experiments are limited to small neural networks and datasets, such that the resulting architectures cannot skip redundant computations and thus cannot accelerate computations.

Contents of the invention

Aiming at the problems existing in the prior art, the present invention provides a pattern-based convolutional neural network pruning method and a pattern-aware accelerator. The method fills the gap between fine-grained pruning and shape-level pruning. The gap in the algorithm pyramid provides a new dimension of regular pruning, which achieves better performance than traditional coarse-grained pruning methods. The accelerator can achieve higher memory compression ratio and better acceleration in sparse networks. Highly parallel computing is achieved through thorough workload balancing.

The present invention is achieved through the following technical solutions:

A pattern-based convolutional neural network pruning method, comprising the following steps,

Step 1, the pattern-based convolutional neural network is constrained by the hardware conditions, and the convolution kernel pattern set of each layer of the convolutional neural network is distilled and screened through the following objective function to obtain the transformation from F _l to P _l relationship, so as to obtain a smaller set of convolution kernel patterns and reduce the bit overhead of the pattern index;

st∑x _lj ≤ V _l , x _lj ∈ {0, 1}, (2)

P _l =∪p _lj x _lj , p _lj ∈ _{F n} , (3)

l=1,...,N, j=1,...,N _l . (4)

Wherein, the convolutional neural network includes N convolutional layers, the set of weights in the convolutional layers is W={W ₁ ,...,W _N }, and W ₁ represents the weights in the lth convolutional layer ; w _lj is the weight of the j-th convolution kernel in W _l , N _l is the number of convolution kernels in W _l ; n is the number of non-zero values for each pattern, and λ and β are used to balance the last two terms parameters;

种图案类型，t_n是F_n中图案的总数，t_n＝|F_n|；P_l是从F_n导出的第l层中的选择的图案，在每个P_l中仅有V_l种图案类型，

V_l是选择的图案的期望数量，V_l＝|P_l|；The complete set of pattern sets for each layer is F={F ₁ , F ₂ ,...,F _n }, and the distilled set P={P ₁ ,P ₂ ,...,P _l } extracted from F, without Redundant patterns; _Fn is the full set or candidate set of patterns with n non-zero values, in each _Fn there is

pattern types, t _n is the total number of patterns in F _n , t _n = |F _n |; P _l is the selected pattern in the lth layer derived from F _n , there are only V _l types in each P _l Pattern type,

V _l is the desired number of selected patterns, V _l = |P _l |;

是通过保持最大绝对值来将w_lj匹配到P_l中的最近图案的投影函数；When x _lj =1, select the i-th pattern of P _l , and vice versa;

is the projection function that matches w _lj to the nearest pattern in P _l by maintaining the maximum absolute value;

Step 2, the weights of the convolutional layer are represented by sparsity and the distilled pattern as {S, P} to realize the pruning of the pattern-based convolutional neural network; where, S={s ₁ , s ₂ , ..., s _l } is the sparsity of the lth convolutional layer, determined by n _l /K _l , where n _l is the number of non-zero values, and K _l is the size of the convolution kernel of each layer.

Preferably, in step 1, given the values of V _l and n, the transformation relationship from F _l to P _l will be obtained through the objective function, converted into a pattern distillation based on the knapsack problem, and solved by a greedy algorithm; until traversing under hardware constraints Different n and V _l , choose to get the best setting.

Further, through the following steps, the transformation relationship from F _l to P _l obtained through the objective function is transformed into a pattern selection based on the knapsack problem,

In step a, the pattern distillation is represented by the following formula:

st∑x _li ≤ V _l , x _li ∈ {0, 1}, i=1, ..., t _n (9)

P _l =∪p _li x _li , p _li ∈ F _n , (10)

l=1,...,N, j=1,...,N _l . (11)

Step b, consider each w _lj as a single knapsack, then the capacity of each knapsack is 1; using the selected pattern to represent W is considered to be a multi-knapsack problem MKP;

Step c, since all capacities of w _lj are 1, KP-based pattern selection is actually a multi-knapsack problem MKP-1 with exactly the same capacity.

Further, the multi-knapsack problem MKP is solved through the greedy algorithm based on the pattern distillation optimization of the knapsack problem; specifically, in the pattern selection, for each layer, select the most valuable pattern for each convolution kernel, and then Denote the top V _l patterns that will minimize the loss function, denote W _l .

Preferably, for the convolutional neural network, the convolution filter is forced to be suitable for the selected pattern set, thereby by selecting the pattern to approach the weight W scheme of the convolutional neural network, and then using the alternating direction multiplier method ADMM to optimize convolutional neural network; specifically,

Given the original dataset {X, Y} and loss function L, the convolutional neural network is optimized as follows,

where f represents the function of the CNN, W represents the weight of the convolutional layer, θ represents other parameters of the CNN, and P is the selected pattern set.

A pattern-aware accelerator based on a pattern-based convolutional neural network, consisting of a pattern-aware processing element group, a pattern mask register, a convolution kernel register, a sparse calculation controller and a decoding unit, and a shared activation register & zero-value detection unit; sparse The calculation controller and the input end of the decoding unit are connected to the pattern mask register and the convolution kernel register, and are interactively connected to the pattern perception processing element group according to the input pattern mask mapping table, and the pattern perception processing element group input end is connected to share activation Register & zero value detection unit;

The weights of the pattern-based convolutional neural network obtained by the pruning method described in any one of the above items are stored in the convolution kernel register.

Preferably, the following pipelined data processing is performed in the pattern perception processing element;

The first stage is the data preprocessing stage;

Restore the weights to the original filter according to the pattern mask mapping table; for activations, the data is loaded into the register file, and an activation sparsity mask is generated to represent zero; for patterns, it is transformed into a weight sparsity mask Code, similar to activation;

The second stage is the generation of sparse pointers;

Calculate the pointer offset table to locate the non-zero activation weight pair, and gradually obtain each pointer of the non-zero activation weight pair based on the pointer offset table until the entire filter calculation is completed;

Finally in the third stage, when all the partial sums from the individual input channels are added together, ReLU is used to obtain the final result.

Further, in the second stage, the specific processing method for the generation of the sparse pointer is as follows,

Computing pointer offset tables by processing filter pattern codes;

At the beginning of each convolutional layer calculation, load the configuration word to build the pattern decoder;

Based on the pattern decoder, each pattern code can be decoded into a corresponding pattern filter sparsity mask of 9 bits in length; the input pattern code matches the specified pattern, and then a 9-bit pattern sparsity mask is obtained, where "1" means non-zero value, and "0" means zero value;

At the same time in the activation register, the input vector is cached in the register file on the one hand, and on the other hand, each value of the vector is checked whether it is zero and an activation sparsity mask of 9-bit length is obtained;

After enforcing the AND operation between the pattern sparsity mask and the activation sparsity mask, the computed sparsity mask is obtained to represent valid non-zero activation weight pairs, and the computed sparsity mask is indexed according to the pointer offset table After offset processing, the final sparse pointer is obtained.

Furthermore, the pointer offset table used for the sparsity mask offset is to calculate each position of the effective activation weight pair; the pointer offset table consists of two parts: the pointer head and the pointer offset; the pointer head represents the first effective pair position; the pointer offset indicates the distance between the current position and the nearest unused non-zero value, and the pointer offset table is processed as follows:

First, a NOT operation is applied to each bit of the computed sparsity mask in order to accumulate the number of zeros between nonzeros;

Second, add each bit through the negative mask; and once bit 0 is observed, the accumulated sum will be reset;

The process of generating pointers according to the deviation table is as follows:

First, the initial value of the pointer is zero, and it is directly added to the head of the pointer to find the first valid pair;

Then, add the pointer to the offset from the current position plus an extra 1 to find the next valid pair;

Finally, after each accumulation, the pointer is compared to 9 to decide whether to end the workflow.

Preferably, the filter packaged in the pattern-aware processing element PE includes pattern masks and non-zero sequences stored in different SRAMs;

Read non-zero weights with a fixed word length from the weight SRAM as a non-zero sequence group; in the weight SRAM, the weights are quantized to an 8-bit word length;

The pattern configurator reconfigures the weight register file according to the configuration word, and divides the vectors read from the pattern SRAM into several groups according to the length of the non-zero sequence;

After the pattern configurator reconfigures the group division method of the weight according to the configuration word, it assigns the weight as a filter to the pattern perception processing element PE group;

SRAM access adopts bit-by-bit group division;

The pattern configurator is used to define how the pattern words are split to load the subsequent shift registers to sequentially read the pattern codes to feed to the PE array.

Compared with the prior art, the present invention has the following beneficial technical effects:

The present invention first proposes a filter based on a pattern-based convolutional neural network (PCNN), and implements rule pruning in the filter based on a multi-knapsack framework, which can be orthogonal to existing pruning methods, which is similar to fine-grained sparsity, But still maintain a certain degree of regularity to a certain extent. In each layer, we limit the number of non-zeros in the filter to be the same, so that the computational workload can be the same for different convolution windows. Based on the uniform sparsity ratio in the filter, the types of patterns in one layer are very limited. Using a pattern mask with very few bits and the corresponding non-zero sequence to describe the filter, instead of describing all the values, significantly reduces the memory size and calculation amount, and is very friendly to accuracy and hardware. Experiments show that the pruning method of PCNN can achieve up to 9 times weight pruning, and the accuracy loss is negligible. Combined with other pruning methods such as filter pruning, PCNN's pruning method achieves up to 34.4 times reduction in model size with negligible accuracy loss, which demonstrates the orthogonality feature.

Further, after determining the exact same sparsity of each filter in one layer, through the framework of the nonlinear knapsack problem, realize pattern distillation to select the best types of patterns in the entire enumeration set. The relationship with various factors such as filter sparsity and number of pattern types is optimized.

The present invention proposes an accelerator based on filter pattern perception, which has a better storage compression ratio than traditional pruning, not only can evaluate the benefits of pattern filter pruning, but also balances low-overhead filter coding and different convolutions The workload in the window realizes a high degree of parallel computing, which makes the storage significantly increased and the calculation significantly reduced. Compared with irregular pruning, the pattern-aware accelerator fully exploits the advantages of PCNN, its memory footprint is reduced by 6.5 times (tested in terms of 8 times weight and 9 times compression ratio), and it is more effective in balancing workload. Sufficient acceleration is achieved for the case where the area overhead per PE is 13.9% and the memory is 3.3%.

Description of drawings

FIG. 1 is a schematic diagram of channel pruning, filter pruning, convolution kernel pruning, and shape pruning in the prior art.

Fig. 2 is a schematic diagram of a pruning algorithm pyramid with different regularities of the pruning method in the prior art.

Fig. 3a is a schematic diagram of the top and bottom of the pattern filter described in the example of the present invention.

Figure 3b shows overhead and compression for various pattern types described in the examples of the present invention.

Fig. 4 is a schematic diagram of pattern distribution in CONV4 of VGG16 described in the example of the present invention.

Figure 5 is a comparison of the results of different pattern selections described in the examples of the present invention.

Fig. 6a is the storage structure of weights and patterns of the pattern perception accelerator in the example of the present invention.

Fig. 6b is the storage format of the weight value of the pattern perception accelerator in the example of the present invention.

Fig. 7 is a schematic diagram of the calculation of the convolutional layer described in the example of the present invention.

Fig. 8a is a schematic diagram of the computing unit of the accelerator in the example of the present invention.

Fig. 8b is a schematic flow chart of generating pointers of the accelerator in the example of the present invention.

Fig. 8c is a schematic diagram of the decoder module of the accelerator in the example of the present invention.

Fig. 9 is a schematic diagram of the processing flow of the accelerator in the example of the present invention.

Fig. 10 is a schematic diagram of the structural arrangement of the accelerator in the example of the present invention.

Detailed ways

The present invention will be further described in detail below in conjunction with specific embodiments, which are explanations of the present invention rather than limitations.

In the traditional way, the filter is filled with K values, so that the data sequence of K is used to describe the filter. However, when simply employing pruning methods, filters often exhibit sparsity, so we can exploit sparsity masks to represent non-zero locations.

种图案类型，9位字长编码可以表示所有可能性。为了获得规则剪枝，使用非零序列的相同长度有利于平衡不同卷积窗口的工作负载。因此，可将图案类型减少到

其中7位字长掩码编码是足够的。如图3b所示，柱状条表示图案编码的位成本。从下到上的两条线分别表示当非零数量为4时滤波器的开销百分比和压缩比。对于各种稀疏性，图案滤波器引入平均17％的编码开销，而同时在1个非零的示例中享有至多9倍的压缩。With the help of a sparsity mask, only the non-zero part is required, as shown in Figure 3a for the raw representation of the filter described at the top, and for the pattern-based use of the pattern mask and sequence of non-zeros shown at the bottom. Encoding the sparsity mask has a small overhead. Taking the most commonly used 3×3 filter as an example, since at most

A pattern type, 9-bit word length code can represent all possibilities. To obtain regular pruning, using the same length of non-zero sequences is beneficial to balance the workload of different convolution windows. Therefore, the pattern types can be reduced to

A 7-bit word length mask encoding is sufficient. As shown in Fig. 3b, the histogram bars represent the bit cost of pattern encoding. The two lines from bottom to top represent the overhead percentage and compression ratio of the filter when the number of non-zeros is 4, respectively. For various sparsities, the pattern filter introduces an average 17% coding overhead while enjoying up to 9x compression in 1 non-zero example.

Furthermore, we observed pattern distribution, as shown in Fig. 4, in CONV4 of VGG16, with a total of 126 patterns, of which the number of non-zeros is 4. Therefore, some pattern types remain less important, allowing further removal of some patterns.

Therefore, based on the above considerations, we can use the following terms to describe our pattern pruning method.

The set S = {s ₁ , s ₂ , ..., s _l } is the sparsity ratio of the l-th convolutional layer, determined by n _l /K _l , where n _l is the number of non-zero values and K _l is The convolution kernel size of each layer. With the shared parameters of _sl , a balanced workload of each filter is guaranteed.

Next, the set F = {F ₁ , F ₂ , ..., F _n } is the complete set of pattern sets for each layer, and the distilled set P = {P ₁ , P ₂ , ..., P _l } without redundant patterns.

种图案类型，在每个P_l中仅有V_l

种图案类型。In each _Fn there is

pattern types, only V _l in each P _l

pattern type.

Through the optimization of the pattern-based convolutional neural network, we can obtain the transformation relation from F _l to P _l . At this point, the weights of the convolutional layers are formulated as {S, P}, which is an intuitive description of the pattern pruning method.

对于计算加速，由于规则剪枝，硬件可以充分利用稀疏性实现FLOP与∑_Slrl的降低比。Finally, for hardware, the memory compression ratio of the weights is computed by ∑s _l r _l , where r _l is the ratio of the parameters of each layer to the total model. The overhead of the pattern mask is at most γΣK _l , which is determined by the convolution kernel size K _l and the ratio γ of the pattern mask word length to the non-zero sequence word length. Here, the word length of the pattern mask is

For computing acceleration, due to rule pruning, the hardware can make full use of sparsity to achieve a reduction ratio of FLOPs to ∑ _Slrl .

Among them, the optimization of the pattern-based convolutional neural network is as follows,

Consider a convolutional neural network CNN containing N convolutional layers, where W _l represents the weight in the lth convolutional layer, W={W ₁ ,...,W _N }. Considering the hardware, our aim is to find the appropriate number of patterns to represent W with less bit cost of indexing. At the same time, a higher sparsity of patterns is required. Thus, we get the following objective function

st∑x _lj ≤ V _l , x _lj ∈ {0, 1}, (2)

P _l =∪p _lj x _lj , p _lj ∈ _{F n} , (3)

l=1,...,N, j=1,...,N _l . (4)

是通过保持最大(最大n)绝对值来将w_lj匹配到P_l中的最近图案的射影函数。where w _lj is the jth convolution kernel in W _l , and N _l is the number of convolution kernels in W _l . n is the number of non-zero values for each pattern, and λ and β are parameters used to balance the latter two terms. F _n is the full or candidate set of patterns with n non-zero values, and t _n is the total number of patterns in F _n (ie, t _n =|F _n |). P _l is the selected pattern in layer l derived from _Fn , V _l is the desired number of selected patterns, V _l = |P _l |. When x _lj =1, the ith pattern of P _l is selected, and vice versa.

is the projective function that matches w _lj to the nearest pattern in P _l by maintaining the largest (max n) absolute value.

In practice, the optimization problem in Equations 1-4 has no definite solution. However, given the values of _Vl and n, the above optimization is similar to the 0-1 knapsack problem and can be solved by a greedy algorithm. The optimal setting cannot be chosen until the different n and _Vl are traversed under hardware constraints.

We provide a scheme for selecting patterns to approximate the weights W of a CNN, and then employ the Alternating Direction Multiplier Method (ADMM) to optimize our CNN model. Instead of forcing the weights to be specially quantized, we force the convolutional filters to fit the chosen pattern set. Given the original data set {X, Y} and the loss function L, the following optimization is performed,

where f represents the function of the CNN, W represents the weight of the convolutional layer, θ represents other parameters of the CNN, and P is the selected pattern set.

The knapsack problem mentioned above is detailed as follows.

The goal of the original knapsack problem is to select objects with limited capacity, and the total return of the selected objects should be as large as possible. Given a knapsack with finite volume V, with n items, the i-th item has volume and payoff v _i and c _i . The 0-1 knapsack problem can be formulated as an optimization problem of the following linear integer programming formula:

st∑v _i x _i ≤ V, x _i ∈ {0, 1}, i=1,..., n. (7)

where _xi = 1 means we choose the i-th item to go into the backpack, and vice versa.

The pattern selection based on the knapsack problem (KP) is thus as follows.

Pattern distillation means that we have to select the most profitable finite pattern from the candidate set, which exactly corresponds to the core idea of the knapsack problem. However, unlike the knapsack problem where the volume of each pattern is equal to 1, each pattern can be selected more times, and the payoff for each pattern is no longer a specified value but a function between w _lj and all selected patterns P .

We express pattern distillation with the following formula:

st∑x _li ≤ V _l , x _li ∈ {0, 1}, i=1, ..., t _n (9)

P _l =∪ _pli x _li , p _li ∈ F _n , (10)

l=1,...,N, j=1,...,N _l . (11)

Also, if we regard each w _lj as a single knapsack, each knapsack has a capacity of 1, in other words, we can only choose one pattern from w _lj 's candidate set. Then, representing W with the selected patterns is considered as the multi-knapsack problem (MKP). Exceptionally, since all capacities of w _lj are 1, KP-based pattern selection is actually a multiple knapsack problem (MKP) with exactly the same capacity.

It is well known that MKP is a strongly NP-hard problem. The direct method to obtain the approximate algorithm of MKP is the generalized greedy algorithm (G-Greedy). G-Greedy first sorts items in descending order and knapsacks in ascending order, and then assigns items one by one according to the order and under capacity constraints. However, in our pattern selection, unlike the G-Greedy algorithm, each pattern is not limited to the number of selections. For this particular problem, we propose an efficient greedy algorithm for solving KP-based pattern optimization. For each layer, we first select the most favorable pattern for each kernel, then collect the number of already selected patterns, and finally keep the pattern with the highest frequency (top 10% or a fixed number, here, for each layer, We use the top _V1 valuable patterns), details are shown in Algorithm 1.

Essentially, the proposed greedy algorithm is a mathematical statistical method, which is simple but effective. We will show the difference between different selected patterns and show that the patterns distilled from our method are more valuable.

The effectiveness of the above pattern selection was evaluated.

For example, for n=2, we project the weight W to the set of all possible patterns F _n , and count the frequency of each pattern that has been used to represent W, as shown in FIG. 4 . Then compute the reconstruction loss between the pattern and the weights in each layer

And compared with the three pattern selection methods:

• Highest: Multiple patterns with the highest overall frequency.

• Lowest: the number of patterns with the lowest overall frequency.

• Distillation: Distilled pattern.

Figure 5 shows different patterns leading to different performance in VGG-16 where | _Pn |=16. The pattern with the highest frequency is significantly better than the pattern with the lowest frequency because the most frequently used patterns are more stable than the infrequently used patterns. However, the distilled pattern achieves the best performance, showing that the overall statistical pattern is not optimal, implying that different layers require different patterns. Note that the reconstruction loss represents the loss between the pattern and the weights in each layer, as shown in Equation 12

Overall, the advantages of the pattern pruning methods described in this invention can be observed for different models and various sparsity settings on datasets. The benefits of pattern pruning come from a balance between regularity and fine-grained pruning. Compared with shape-level pruning, pattern pruning allows different sparse shapes in various filters, thus enhancing the representation ability. Compared with fine-grained pruning, we only constrain the uniform sparsity ratio of filters in one layer, so our method is not much different from fine-grained pruning. In this way, it can be viewed as a regular-patch for fine-grained pruning.

By further constraining the number of patterns in each layer to study the impact of regularity on accuracy, the method described in the present invention achieves less overhead for storing indexes than deep compression with 4 bits per weight .

The method of the present invention is compared with other studies on VGG-16 and ResNet-18 on CIFAR10. For various baselines used in different studies, we fairly compare the relative accuracy results. It can be observed that our method can significantly compress parameters and at the same time reduce floating-point computation FLOPs with negligible loss of precision. Better implementation of floating-point FLOP reduction comes from higher sparsity in layers with large size, which takes more computation, while other coarse-grained methods avoid pruning these layers. For ResNet-18, PCNN also achieves better performance than other coarse-grained pruning, especially in FLOP reduction. Moreover, the PCNN pruning method proposed by the present invention can be orthogonal to existing pruning methods.

On the basis of the above, the present invention also provides an image perception accelerator with small area and low power consumption. Note that currently 3×3 filters are widely used and the dominant type in various CNNs, and the proposed architecture is optimized for this type. At the same time, it cooperates with the storage format of the corresponding pattern-aware accelerator to maximize the potential of storage compression.

In pattern pruning methods, filters are represented by corresponding pattern masks and sequences of non-zeros. So, in storage we deal with filters in packages containing pattern masks and non-zero sequences stored in different SRAMs. The reason for the different SRAM designs for pattern masks and non-zero sequences is the different formats and different fine-grained control flows of these two data types.

For non-zero weights, the word length is fixed such that they can be read from storage as sequential groups, as shown in Figure 6b. In this storage structure, we quantize the weights into 8-bit words. Read weights from SRAM as byte reads, which provides flexibility to sequentially load non-zero weights. The storage SRAM of the present invention is generated based on Faraday's MEMAKER, and the bit width of the byte can be customized based on the pattern configuration word to meet the requirement of the non-zero sequence length in the byte reading pattern. The pattern configurator reconfigures the weight register file according to the configuration word, divides the vectors read from the pattern SRAM into several groups according to the length of the non-zero sequence, obtains the pattern mask (SPM code), and passes the pattern decoder to 9-bit The weight mask is input to the group of pattern-aware processing elements PE, as shown in Fig. 6a. In addition, the configuration word also reconfigures the group division method of the weight value and stores it in the convolution kernel register. Afterwards, the weights are distributed as filters to the group of pattern-aware processing elements PE by the sparse calculation controller.

而不是最大方法

因此，图案的总开销减少到

例如，在CIFAR10上的VGG-16上的各种设置a的情况下动态方案可以比最大方法节省40％的索引存储。However, the word length of the pattern mask is different from that of the weights and is variable across layers. In contrast, we employ bitwise rather than sequential group partitioning in masked memory accesses. According to the results of the experiment, in fact, at most 32 types of patterns are enough to ensure the accuracy, so we store the pattern code in a 60-bit wide SRAM, as shown in Figure 6b, which includes 12 5-bit patterns (32 types), Or 15 4-bit patterns (16 types), or 20 3-bit patterns (8 types), or 30 2-bit patterns (4 types), or 60 1-bit patterns (2 types). The pattern configurator defines here how pattern words are split to load subsequent shift registers. Next, the pattern codes are read sequentially to feed to the PE array. Compared to fixed-length copies, the overhead of pattern pruning can be reduced to less than _γΣKl as in the initial hardware description. Utilizing the dynamic bit width format for pattern encoding, the pattern overhead rate in layer l is optimized from γ to _γl ', where _γl ' is optimized for dynamic adjustment

instead of the max method

Therefore, the overall overhead of the pattern is reduced to

For example, the dynamic scheme can save 40% index storage than the largest method in the case of various settings a on VGG-16 on CIFAR10.

The overall structure of the pattern perception accelerator based on pattern filter sparseness of the present invention is shown in FIG. Shared activation register & zero value detection unit. The sparse calculation controller is connected to the pattern mask register and the convolution kernel register with the input end of the decoding unit, and is interactively connected with the processing element (PE) group according to the input pattern mask mapping table, and the input end of the processing element (PE) group Connect shared activation register & zero value detection unit.

The proposed accelerator structure can fully exploit the sparsity in neural networks with shared activations and balanced pattern filters. As shown in Figure 7, each input feature map can be reused for all output channels with corresponding filter banks.

By multiplexing the activations of n PEs, the weights of different output channels are loaded for each PE. In this way, the balance between different PEs can be maintained even with zero random distribution in activations, so that both activation sparsity and weight sparsity can be handled simultaneously. The pattern mask mapping table in Fig. 8a is used to represent the pattern type of each filter, which facilitates the reconstruction convolution computation. It can fully achieve speedup from theoretical algorithmic gain compared to plain copy that directly processes the data stream. Additionally, higher speedups can be obtained from sparsity in activations.

The pipelined strategy in the pattern-aware processing unit PE shown in FIG. 9 . All operations are pipelined for high throughput.

The first stage is the data preprocessing stage. Restore the weights to the original filter according to the pattern mask mapping table. For activations, data is loaded into the register file, and an activation sparsity mask is generated to represent zeros. For patterns, it is converted into a weight sparsity mask, similar to activations.

In the second stage, the generation of sparse pointers, the pointer offset table is calculated to locate non-zero activation weight pairs, which helps to reduce redundant loops. Afterwards, based on the pointer offset table, we can gradually obtain each pointer of a pair of non-zero activation weights until the entire filter computation is completed.

Finally, when all the partial sums from the individual input channels are multiplied together, ReLU is used to obtain the final result.

The generation of sparse pointers is critical in the proposed accelerator. Therefore, the workflow for generating pointers is detailed below. An overview is shown in Figure 8b, where the filter pattern code is processed to compute the pointer offset table. At the beginning of layer computation, configuration words are loaded to build the pattern decoder. Based on the pattern decoder, each pattern code can be decoded into a corresponding filter sparsity mask of 9-bit length. As shown in the example shown in the upper left part of Fig. 8b, the input code matches the third pattern, and then obtains the sparsity mask shown in the gray square on the left in Fig. 8b, where "1" indicates a non-zero value, and "0" means zero value. At the same time in the activation register, the input vector is cached in the register file on the one hand, and on the other hand, each value of the vector is checked for zero and a sparsity mask of length 9 is obtained. After enforcing an AND operation between two sparsity masks, a computed sparsity mask can be obtained to represent valid non-zero activation weight pairs, and after pointer offset processing through the sparsity mask, the final sparseness pointer. With the help of activation weights for sparsity detection, the amount of computation can be further reduced.

The pointer offset table for the sparsity mask offset is each location where valid activation weight pairs are computed. The function of the offset module is shown in the upper part of Fig. 8c. There is an adder-and chain of operations to obtain a table of 9-word pointer offsets, each representing the distance to the nearest zero. The pointer offset table can be processed as follows: First, a negation operation is applied to each bit of the computed sparsity mask in order to accumulate the number of zeros between nonzeros. Second, add each bit through the negative mask. And once bit 0 is observed, the accumulated sum will be reset. An example of the pointer offset table is shown in Fig. 8c, which consists of two parts: pointer head and pointer offset. The pointer head indicates the location of the first valid pair. The pointer offset represents the distance between the current position and the nearest unused non-zero value. But in practice, only those offsets that are on valid pairs are used, since no other offsets are reached.

The workflow and examples of pointer generation are shown at the bottom of Fig. 8c. First, the pointer is initialized to zero and added directly to the pointer head to find the first valid pair. Then, add the pointer to the offset from the current position plus an extra 1 to find the next valid pair. Each time after accumulation, the pointer is compared with 9 to decide whether to end the workflow. In the examples in Figures 8b and 8c, there are three valid pairs in the original sparsity mask. So, the first time the pointer added to the pointer head is to find (a ₁ , w ₁ ), and later added to the corresponding pointer offset and another "1" to find (a ₃ , w ₃ ) and (a ₅ , w ₅ ). When the pointer totals 9, the workflow ends and the pointer is reset to zero.

Thus, with pattern-aware accelerators, workloads can be aligned across different PEs with shared equal-length non-zero sequences of activations and filters. It should be noted that in Fig. 8a, only the required activations and weights are loaded into the PE, thus reducing the internal bandwidth. Furthermore, the sparsity mask-based processing pipeline can simultaneously detect zeros in activation vectors and filters.

The evaluation of the accelerator, described in the present invention, implements the architecture and baseline replica of the pattern-aware accelerator with RTL as follows. The area and power overhead of the pattern-aware architecture was evaluated with Synopsys Design Compiler in UMC's 55nm standard power CMOS process. The pattern-aware accelerator layout is shown in Figure 10, including buffers for input and output data, weight buffers, pattern SRAM, register files, and PE groups and phase-locked loops. The overhead of each component, in the overall design of the architecture of the pattern-aware accelerator, the overhead brought by the pattern design is very small.

In terms of memory footprint, compared to random pruning, the pattern pruning method only requires an extra pattern encoding for each filter instead of each weight. With the pattern pruning method, for most cases, 128KB weight SRAM is used for at most 32768 filters of 3X3 size with 4 non-zeros, while for workloads, 4K pattern SRAM is enough, 16 types of patterns are enough Maintain accuracy. As a result, this accelerator architecture introduces only 3.1% memory overhead to store parameters. And when the data SRAM is considered, the area of the pattern SRAM is equal to 3.4% of the other SRAM. The overhead of EIE for sparsity occupies 19.1% of the area of the whole chip, and the size of pointer SRAM is about 25% of other SRAM. In contrast, we can save 7x overhead compared to EIE. Taking VGG-16 with 1 non-zero and 16 patterns in the filter as an example, since weights are represented in 8 bits in the architecture, 6.5 times of parameters can be saved (considering both index data overhead and weight data overhead ).

In terms of performance improvement, compared with the non-pattern-aware architecture, the proposed pattern-aware architecture can achieve 9 times full acceleration, resulting in 13.9% area overhead and 3.3% storage overhead. In addition, when the proposed accelerator architecture deals with dense networks, the data preprocessing stage and the sparse pointer stage in the pipeline can be bypassed, and related modules can be turned off by clock gating during the sparse period. In other similar studies, only sparse networks are well supported. For Eyeriss, zero calculations are only processed by clock gating to save power, but still consume time. For Cambricon-X, we only focus on weight sparsity rather than activation weight pairs. SCNN exploits weight and activation sparsity by introducing coordinate-aligned data. However, for dense networks, those computational overheads cannot be hidden. EIE supports irregular pruning, but results in additional indexing cost, while Cambricon-S utilizes coarse-grained pruning to achieve low additional cost, but is only suitable for channel-level pruning.

The present invention proposes a novel filter representation method PCNN for describing sparse filters with template masks and non-zero sequences. This pruning method fills the gap in the pruning algorithm pyramid between fine-grained pruning and shape-level pruning, providing a new dimension of regular pruning to achieve better performance than traditional coarse-grained pruning methods. Experiments show that 8 to 9 times of compression and calculation acceleration can be achieved with less than 1% loss of accuracy. Additionally, pattern pruning can be easily combined with coarse-grained pruning methods to improve accuracy, achieving a compression ratio of 34.4 with negligible loss of accuracy. For storage overhead, only a 5-bit index per filter is introduced, which is lower than the 4-bit index per weight in EIE. For computation, with only 13.9% PE area overhead and 3.3% storage area overhead, the proposed accelerator architecture can achieve equivalent or better acceleration than the PCNN algorithm, since it can balance the workload with pattern pruning, and detect Sparsity of weights and activations.

Claims (9)

1. The pattern perception accelerator of the convolutional neural network based on the pattern is characterized by consisting of a pattern perception processing element group, a pattern mask register, a convolutional kernel register, a sparse calculation controller, a decoding unit and a shared activation register & zero value detection unit; the sparse calculation controller is connected with the input end of the decoding unit, the pattern mask register and the convolution kernel register, and is interactively connected with the pattern perception processing element group according to the input pattern mask mapping table, and the input end of the pattern perception processing element group is connected with the shared activation register and the zero value detection unit;

registering the weight of the convolutional neural network based on the pattern obtained by the convolutional neural network based on the pattern pruning method in a convolutional kernel register;

the convolutional neural network pruning method based on the pattern comprises the following steps,

step 1, the convolution neural network based on patterns takes hardware conditions as constraints, and distillation screening is carried out on a convolution kernel pattern set of each layer of the convolution neural network through the following objective function to obtain a secondary F _l To P _l Thereby obtaining a smaller convolution kernel mapA pattern set, which reduces the bit overhead of pattern index;

s.t.∑x _lj ≤V _l ，x _lj ∈{0，1}， (2)

P _l ＝∪p _lj x _lj ，P _lj ∈F _n ， (3)

l＝1，...，N，j＝1，...，N _l . (4)

wherein the convolutional neural network comprises N convolutional layers, and the weight set in the convolutional layers is W = { W = ₁ ，…，W _N }，W _l Representing the weight in the first convolution layer; w is a _lj Is W _l Weight of the jth convolution kernel of (1), N _l Is W _l The number of convolution kernels in (a); n is the number of non-zero values per pattern, λ and β are used to balance the parameters of the latter two terms;

the complete set of pattern sets for each layer is F = { F = } ₁ ，F ₂ ，…，F _n Extraction of distilled set P = { P from F ₁ ，P ₂ ，…，P _l }, no redundant pattern; f _n Is a full or candidate set of patterns having n non-zero values, at each F _n Therein is provided with

Kind of pattern type, t _n Is F _n Total number of middle patterns, t _n ＝|F _n |；P _l Is from F _n Derived selected patterns in the l-th layer, at each P _l In which only V is _l Seed pattern type, <' > or>

V _l Is the desired number of selected patterns, V _l ＝|P _l |；

When x is _lj When =1, P is selected _l The ith pattern of (2), otherwiseVice versa;

is to maintain w at the maximum absolute value _lj Is matched to P _l The projection function of the nearest pattern in (a);

step 2, expressing the weight of the convolutional layer as { S, P } from sparsity and distilled pattern, and realizing pruning of the convolutional neural network based on the pattern; wherein S = { S = ₁ ，s ₂ ，...，s _l Is the sparsity of the l convolutional layer, from n _l /K _l Determining, wherein n _l Number of non-zero values, K _l Is the size of each layer of the convolution kernel.

2. The pattern aware accelerator of a pattern based convolutional neural network of claim 1, wherein said pattern aware processing element performs pipelined data processing therein;

the first stage, data preprocessing stage;

restoring the weight value to the original filter according to the pattern mask mapping table; for activate, data is loaded into the register file and an activate sparsity mask is generated to represent zeros; for patterns, it is converted to weight sparsity masks, similar to activations;

the second stage, generating a sparse pointer;

calculating a pointer offset table to position the nonzero activation weight pair, and gradually obtaining each pointer of the nonzero activation weight pair based on the pointer offset table until the whole filter is calculated;

finally, in the third stage, the ReLU is used to obtain the final result when all partial sums from the respective input channels are added together.

3. The pattern-aware accelerator of a convolutional neural network based on pattern as claimed in claim 2, wherein in the second phase, the sparse pointer is generated by the following specific processing method,

calculating a pointer offset table by processing the filter pattern code;

loading configuration words to establish a pattern decoder when the calculation of each convolution layer is started;

based on the pattern decoder, each pattern code may be decoded into a corresponding pattern filter sparsity mask of 9-bit length; inputting a pattern code matching a specified pattern, and then obtaining a 9-bit pattern sparsity mask, wherein '1' represents a non-zero value and '0' represents a zero value;

simultaneously activating the register, the input vector being cached in the register file on the one hand, and on the other hand, each value of the vector being checked for zero and obtaining an activation sparsity mask of 9 bits length;

and after the forced execution and operation between the pattern sparsity mask and the activation sparsity mask, obtaining a calculation sparsity mask to represent an effective nonzero activation weight pair, and performing pointer offset processing on the calculation sparsity mask according to a pointer offset table to obtain a final sparse pointer.

4. The pattern aware accelerator of a pattern-based convolutional neural network of claim 3, wherein the pointer offset table for sparsity mask offsets is for each position where a valid activation weight pair is calculated; the pointer offset table consists of a pointer head and a pointer offset; the index tip indicates the position of the first active pair; the pointer offset represents the distance between the current position and the nearest unused non-zero value, and the pointer offset table is processed as follows:

first, a negation operation is applied to each bit of the computed sparsity mask to accumulate the number of zeros between non-zeros;

secondly, add each bit by a negative mask; and once bit 0 is observed, the accumulated sum will be reset;

the procedure for generating the pointer from the deviation table is as follows:

firstly, the initial value of the pointer is zero, and the initial value is directly added with the head of the pointer to find a first effective pair;

then, add the pointer to the offset of the current position and the extra 1 to find the next valid pair;

finally, each time after accumulation, the pointer is compared to 9 to decide whether to end the workflow.

5. The pattern aware accelerator of a pattern based convolutional neural network of claim 2, wherein the pattern aware processing element PE comprises a filter encapsulated in it that contains a pattern mask and a non-zero sequence stored in different SRAMs;

reading a nonzero weight with a fixed word length as a nonzero sequence group from a weight SRAM; in a weight SRAM, the weight is quantized to 8-bit word length;

the pattern configurator reconfigures the weight register file according to the configuration words, and divides the vectors read from the pattern SRAM into a plurality of groups according to the length of the nonzero sequence;

the pattern configurator reconfigures the group division mode of the weight according to the configuration words, and then distributes the weight to the pattern perception processing element PE group as a filter;

the access of the SRAM adopts a group division mode according to bits;

the pattern configurator is used to define a pattern word splitting pattern to load a subsequent shift register to sequentially read pattern encodings for feeding to the PE array.

6. The pattern aware accelerator of a pattern-based convolutional neural network as claimed in claim 1, wherein in step 1, V is given _l And n, F will be obtained by the objective function _l To P _l The transformation relation of (1) is converted into pattern distillation based on the knapsack problem, and solved through a greedy algorithm; until different n and V are traversed under hardware constraints _l The best setting is selected.

7. The pattern aware accelerator of a pattern based convolutional neural network of claim 6, wherein F is obtained by an objective function by _l To P _l The transformation relationship of (a) is converted into a pattern selection based on the knapsack problem,

step a, pattern distillation is expressed by the following formula:

s.t.∑x _li ≤V _l ，x _li ∈{0，1}，i＝1，...，t _n (9)

P _l ＝∪p _li x _li ，p _li ∈F _n ， (10)

l＝1，...，N，j＝l，...，N _l . (11)

step b, mixing each w _lj As a single backpack, the capacity of each backpack is 1; representing W with the selected pattern is considered a multi-knapsack problem MKP;

step c, due to w _lj All capacities of 1, the KP based pattern selection is actually a multi-knapsack problem MKP-1 with exactly the same capacity.

8. The pattern aware accelerator of a pattern-based convolutional neural network of claim 7, wherein the multi-knapsack problem MKP is solved by a greedy algorithm of pattern distillation optimization based on knapsack problem; specifically, in making the pattern selection, for each layer, the most valuable pattern is selected for each convolution kernel, and then the top V that will minimize the loss function _l A pattern, represents W _l 。

9. The pattern aware accelerator of a pattern-based convolutional neural network of claim 1, wherein for said convolutional neural network, a forced convolution filter is adapted to the selected pattern set to optimize the convolutional neural network by selecting the pattern to approximate the weight W scheme of the convolutional neural network, and then using an alternating direction multiplier method ADMM; in particular, the method comprises the following steps of,

given the original data set X, Y and the loss function L, the convolutional neural network is optimized as follows,

where f represents a function of CNN, W represents weights of convolutional layers, θ represents other parameters of CNN, and P is a selected pattern set.

Images