Enhancing BNN storage and performance requirements via efficient quantization and variable encoding

1 Introduction

Deep Neural Networks (DNNs) are highly successful in various tasks such as image classification (Touvron et al., 2022; He et al., 2015) and speech recognition (Baevski et al., 2020). Not surprisingly, they have become a critical component for Machine Learning Applications. Nonetheless, the cost of storing and evaluating DNNs is high since they usually contain millions of parameters. Consequently, performing DNN inference on edge devices is challenging due to constrained resources. In this regard, Binary Neural Networks (BNNs) are an attractive solution to reduce the cost of using DNNs on edge devices. In BNNs, the weights and input features can only take the value of 1 and −1; thus, one bit is used to store them. Therefore, the cost of storing a BNN layer decreases substantially compared to those using integer or floating point values. Moreover, BNNs can be executed efficiently with modest hardware since the matrix multiplications required to evaluate a DNN utilize a series of xnor and popcount operations.

While BNNs are very computationally efficient, their accuracy tends to be relatively low compared to similar state-of-the-art full-precision networks. However, recent BNN models, such as ReactNet (Liu et al., 2020), PokeBNN (Zhang et al., 2022), and FracBNN (Zhang et al., 2021), achieve a top-1 accuracy (the fraction of test images for which the highest-scoring predicted class is the correct one) comparable to state-of-the-art full-precision networks. For instance, ReActNet obtains a top-1 accuracy of 69% on the Imagenet dataset while MobileNet V2 (Sandler et al., 2018) (i.e., CNN model tailored to edge devices) has a top-1 accuracy of 72%. Nevertheless, the number of bits required to store ReActNet is 29 million, whereas it is 27 million for MobileNet V2. Hence, evaluating these models on edge devices is still challenging due to their limited storage and computational resources. Most of the storage and computational requirements of BNNs are due to convolutional operations and the output layer parameters, which is normally a fully-connected layer. For instance, for ReAcnet and PokeBNN, the storage requirements due to convolutions are 55 and 16% of the total model size, respectively. On the other hand, the requirements due to weights for the output layer account for 36 and 47%, respectively.

This work focuses on improving the performance and storage requirement of BNN models composed mainly of convolutional operations. As mentioned earlier, binary kernels require a large amount of storage. In this regard, in a binary kernel (i.e., weights are 1 or −1), for any given n by n channel stored as a sequence of bits, there are 2^*n***n* possible sequences of bits. However, it is observed that during the evaluation of a convolution operation for a given kernel, some sequences of bits occur more frequently than others. For instance, in some layers of ReActNet, 32 individual sequences of bits account for more than 50% of all the possible sequences. To exploit this observation, a variable length compression algorithm is proposed to encode these sequences of bits that employs fewer bits for the most common sequences. For the sake of brevity, in the rest of the paper, the sequence of bits formed with the values of a given channel is referred to as a bit sequence.

Another key observation is that for some layers, some non-frequently used bit sequences can be replaced by others that are employed more often without negatively impacting the accuracy of the network. Accordingly, a clustering algorithm is proposed that substitutes some of the less common bit sequences with others that are similar but very common. By removing the less common bit sequences, the binary kernels can be compressed more efficiently since the number of bits to store the most common ones is smaller.

One significant challenge in implementing a variable-length encoding is providing a software- and hardware-friendly solution while also being efficient (Aspar et al., 2000). A software-only implementation is insufficient since the performance is severely affected by the overhead of decoding the compressed bit sequences. This issue is addressed by providing hardware support to decompress the bit sequences. Moreover, overlapping the fetch and decoding of the bit sequences with the computations is critical to achieving high performance. Finally, employing few resources is essential in resource-constrained FPGAs.

A distinct source for the large storage requirements of BNNs is the weights of the output layer. Typically, this layer is a classifier, and it is implemented as a fully connected layer. For this reason, the number of parameters in this layer is directly related to the number of classes being classified. Moreover, to obtain state-of-the-art accuracy, the output layer is implemented using floating-point values (Vorabbi et al., 2023; Liu et al., 2020; Zhang et al., 2021, 2022) to store its weights. A central issue with the output layer is that employing symmetric linear quantization on this layer tends to severely affect the accuracy of the network, even for high bit widths (i.e., 16 bits). Nevertheless, it has been observed that the output layer can be compressed aggressively without negatively impacting the model accuracy by quantizing a few weights (i.e., outliers) with higher precision and the rest with a very low bit-width. Hence, a scheme is proposed to quantize the output layer that utilizes non-symmetric quantization for outliers and the rest of values. Furthermore, the standard deviation of the weight distribution is employed to determine the number of outliers systematically.

This work extends our prior study on kernel compression for BNNs (Silfa et al., 2023), which focused on reducing kernel storage via a simplified Huffman tree and a clustering-based replacement of rare bit sequences, evaluated on general-purpose CPUs. The contributions that are new to this manuscript are: (i) the analysis of the BNN output layer, showing that it accounts for nearly 50% of the storage and 60% of the execution latency, and the proposal of a specialized quantization scheme (split quantization) that handles outliers and normal values separately; (ii) the FPGA hardware design, including a decoding unit for the compressed kernels and an extended matrix-vector engine that supports split quantization; (iii) the extension of the evaluation to PokeBNN in addition to ReActNet; and (iv) the end-to-end FPGA evaluation on a Pynq Z1, demonstrating a 1.5 × reduction in memory requirements and a 2.2 × speedup. The kernel compression scheme from the prior work is included in this manuscript to make the paper self-contained and to enable its integration with the new output-layer quantization on the FPGA accelerator.

In summary, the main focus of this paper is improving the memory requirements and performance of BNNs on edge devices. The following contributions are claimed:

• The distribution function of all the bit sequences in BNNs is analyzed, showing that some of them are used much more frequently than the rest.
• A simple variable-length encoding is proposed to compress the binary kernels. Also, a novel clustering algorithm is described that increases the frequency of the most common bit sequences. Our scheme compresses the convolutional kernels by 1.3 × on average.
• It is shown that the output layer of the BNN can be aggressively quantized by quantizing the outliers in the output layer with higher bit precision and by employing the standard deviation of all the weights in the output layer to determine the number of outliers. Our proposal reduces the output layer size by 4.5 × , on average, for an accuracy loss of less than 1%.
• Simple hardware extensions are proposed to support these techniques and are evaluated on an FPGA accelerator. Compared to a baseline accelerator, our proposal improves performance by 2.2 × .

2 Background

2.1 Binary Neural Networks

Like full-precision DNNs, Binary Neural Networks (BNNs) are composed of many layers (convolution, fully connected, etc.) stacked on top of each other, as depicted in Figure 1. However, BNNs use one-bit weights and inputs that can take the values +1 and −1, but they usually are trained using full-precision weights (Hubara et al., 2016). Then, the weights and inputs are binarized using Equation 1:

xb={+1ifx>=0,-1otherwise,(1)

where x is a full-precision weight or input and x^*b* is the binarized value.

Convolution operations with binary inputs and weights are computed as their full-precision counterpart. However, Equation 2 is employed to calculate an output feature (Rastegari et al., 2016). In this equation, o is a feature of the output feature map, whereas w^*b* and x^*b* are the binarized kernel (weights) and input vectors. N is the size of input vector x. The kernel and the input vectors are composed of 1 and −1 values, but they are stored as 1 and 0, respectively.

o=2*popcount(xnor(wb,xb))-N(2)

Equation 2 is computing a multiply-accumulate operation (MAC), the primary computation on DNNs. Hence, as mentioned earlier, BNNs are very efficient in computations and memory requirements since MAC operations can be computed using xnor and popcount functions, and weights are stored using one bit.

2.2 BNN models

Recently, on image classification tasks, BNN models can achieve top-1 accuracy, similar to the accuracy of full-precision models tailored to edge devices. In this regard, ReActNet (Liu et al., 2020) and PokeBNN (Zhang et al., 2022) are BNN models based on MobileNet (Sandler et al., 2018) with a top-1 accuracy of 69.4% and 68.21, respectively, on the ImageNet dataset. The accuracy of Mobilenet V2 for the same task is 72%. Since the accuracy of both models is very close to the full-precision counterpart, these models are employed as the baseline for this work and are briefly described in the following sub-sections.

2.2.1 ReActNet

The main building block of ReActNet is shown in Figure 1a. This block comprises two convolutional layers that employ binarized input and kernels. Also, it performs other operations such as batch-norm and Prelu activation functions, which are computed using full-precision. One of the critical contributions of this model is that the Prelu activation is biased by shifting and reshaping its input. By performing this transformation, the accuracy of the network is substantially improved (Liu et al., 2020).

ReActNet is composed of 15 layers which include one input, one output layer, and 13 layers built using the basic block shown in Figure 1a. On the other hand, the input layer is convolutional, whereas the output layer is fully connected. Both layers are computed using full-precision values.

2.2.2 PokeBNN

Figure 1b illustrates the fundamental block (PokeConv) of PokeBNN, consisting of two convolutional operations that employ binarized input and kernels. Like ReAcNet, it contains additional layers for batch-norm and DPReLU activation functions. This model also performs a shift and reshapes the activation distribution. Furthermore, it uses squeeze-and-excitation (SE) layers to allow the network to incorporate global knowledge on given inputs. These innovations significantly enhance the accuracy of the network (Zhang et al., 2022).

PokeBNN comprises an input layer, 16 bottleneck blocks, each constructed with three fundamental PokeConv blocks, and the output layer. In addition, the input layer is convolutional, while the output layer is a fully-connected employing full-precision values.

2.2.3 Storage requirements

Table 1 shows the storage requirements and precision for the primary operations in ReActNet and PokeBNN. In these models, the storage requirement due to the 3 × 3 convolutions accounts for 55.6 and 16.3% of the total, respectively. On the contrary, the storage requirement for the output layer accounts for 36.3 and 47.1%, respectively. Similarly, for the input layer, the storage requirement is small (i.e., less than 1%). Therefore, since the weights for the binary convolution and the output layer represent a significant part of the storage requirements, this work focuses on reducing them.

Table 1. Storage requirement for ReActNet and PokeBNN.

Others refer to activation and batch normalization layers, etc.

3 Binary kernel compression

For the 3 × 3 binarized kernels found in BNN models, each channel is composed of nine values that are either one or zero; thus, there are only 512 unique bitsequences. However, some bitsequences are rarely used, while other sequences tend to appear very frequently. Therefore, this observation is exploited by employing a variable encoding that assigns fewer bits to the most common bitsequences. Moreover, it was experimentally found that some rarely used bitsequences can be substituted by others that are more common without negatively affecting the overall network accuracy.

Figure 2 shows a binarized 3 × 3 kernel with two channels. As mentioned earlier, each of these channels is composed of nine values, which are either 1 or −1, and to represent one channel, at least nine bits are needed. For clarity, to refer to a given bitsequence, a natural mapping is employed, as shown in Figure 2, that assigns a natural number to each bitsequence. In this regard, the value in position 0,0 is set to the most significant bit and the value in position 2,2 to the least significant bit. For example, a channel where all the values are zeros (i.e., −1) will be referred to as 0. Similarly, a channel with only ones is mapped to 511. Note that this is a conceptual representation, and the actual layout of these bits in memory can be different.

Regarding the 1 × 1 kernels found in our baseline models, since those bit sequences have a length of one, they are uniformly distributed, and thus, using a variable encoding is not feasible. It is also possible to create bit sequences across the channel dimension; however, in our experiments, these bit sequences are also seen to be uniformly distributed; therefore, they are not compressed.

3.1 Frequency of use for bit sequences

Figure 3 shows the frequency of use for the 16 most common bitsequences in the 3 × 3 binary kernels of one representative basic block per model. The analysis is performed independently for each block; Table 2 provides the full per-block breakdown across all blocks in both models. As shown in the plot, bitsequences containing only zeros or ones account for 25% for both models. As it can be seen, for ReAcNet, the most common 16 bitsequences account for 46% of all of them, whereas for PokeBNN, the most common 16 bitsequences account for 50.7%. Similarly, shown in Table 2, the top 64 bitsequences account for more than 50 and 42% on average for ReAcNet and PokeBNN, respectively. Moreover, for all the blocks, the 256 most frequently used bitsequences account for up to 92 and 96% in both models. Henceforth, instead of employing nine bits to store each channel, six bits could be used to store almost half of the bitsequences and nine or less for the rest.

Table 2. Distribution of bitsequences for the 3 × 3 kernel in each ReAcNet and PokeBNN basic block.

3.2 Compressing bit sequences

Aiming to increase storage efficiency and to exploit the variability in the frequency of use of the bitsequences, Huffman Encoding is proposed to encode them. When using Huffman encoding to compress the kernels, a Huffman tree must first be created, where each bitsequence is assigned to a tree node. Then, before using a bitsequence, it must be decoded with the help of lookup tables that contain the uncompressed value. The tree is created offline, whereas the decoding is done at runtime.

A significant issue when decoding a Huffman encoded sequence of bits is that it requires optimized lookup tables or complex hardware if high throughput is needed (Aspar et al., 2000). In this regard, a simplified Huffman tree is proposed, where the tree size is limited to a small number of nodes (i.e., four), as shown in Figure 4. In this tree, several encoded bitsequences are assigned to each node and are stored in a table to store. Hence, during the decoding process, the first bits of the encoded bitsequence are used to find out to which table (node) it belongs, and the remaining bits are then employed to address the table and get the uncompressed bitsequence. This simplified version provides a good trade-off between simplicity and compression rate, as shown in Section 7.

3.3 Removing less frequent bit sequences

As shown in Table 2, half of the bit sequences are used less than 10%. We address this by applying a greedy nearest-neighbor heuristic based on Hamming distance, rather than a standard clustering algorithm such as k-means. The Hamming distance between two bit sequences directly measures the number of weight flips required to replace one with the other, so a distance of one corresponds to flipping a single weight, producing the smallest possible perturbation to the network. Specifically, each seldom used bitsequence (sa) is replaced with one employed more frequently (sb) when the Hamming distance between sa and sb is small (i.e., only one-bit difference) and the accuracy of the network is not affected. Consequently, the compression ratio can be improved by increasing the frequency of use of the most common bitsequences while replacing some of the less common ones. Note that this optimization is optional, and the scheme described in 3.2 works without it, as shown in Table 3. Also, this optimization is conservative, and a given sequence is only replaced when the network accuracy does not change.

Table 3. Compression ratio of bitsequences for the 3 × 3 kernel in each basic block of ReAcNet and PokeBNN.

The replacement of some of the less common bitsequences by others more common is accomplished as follows. First, for all the 3 × 3 binary kernels in a given basic block, a list topM is created containing the M most commonly used bitsequences. Then, a second list topN is made, holding the N less commonly employed bitsequences. The bitsequences in topM are sorted by frequency in descending order, whereas bitsequences in topN are sorted in ascending order. Also, an empty map replacementMap is created to store the final mapping.

Then, the bitsequences in topN are considered for replacement with bitsequences from topM. First, a bitsequence (sa) from topN is taken and its Hamming distance against the bitsequences in topM is computed. When a bitsequence (sb) is found such that the Hamming distance between sa and sb is equal to one, sa is mapped with sb. For cases where many bitsequences match this criterion, the bitsequence with the highest frequency is employed. Finally, this process is repeated for all the bitsequences in topN. After the mapping is done, a new 3 × 3 binary kernel is created by replacing each rarely used bitsequence with its corresponding map.

Regarding the parameters M and N, we do not impose a fixed cutoff on either: the topM pool is the full set of 9-bit sequences ordered by descending frequency, and the topN pool is the same set ordered by ascending frequency. We walk through the candidate replacements in order, pairing each rare sequence in topN with its nearest-Hamming-distance counterpart in topM, and accept a replacement only if it does not degrade the network accuracy on the validation set. The number of replacements that survive this accuracy check is therefore an empirical outcome of the procedure rather than a hand-tuned hyperparameter; across all layers, the average number of accepted replacements is approximately 256, as reflected in the Clustering column of Table 3 in Section 7. This formulation makes the procedure deterministic given the network and the validation set, and removes the need for a manual sweep over M and N.

4 Output layer compression

In DNN models targeting classification tasks, the output layer is usually a classifier implemented as a fully-connected layer. Hence, its storage requirement directly relates to the number of classified classes. A common approach to decrease storage requirements and improve the performance of DNN models is to employ linear quantization (Wu et al., 2016; Jouppi et al., 2017; Wu et al., 2020). When applying linear quantization, a full-precision value (y) is approximated as the value (y_*q*), which is expressed as a function of an integer index and a quantization step (q) as shown in Equations 3a–c. For these equations, n is the bit-width of the integer index i_*k*, for example, eight bits, and α is the maximum absolute value of y. For DNN layers, after the weights and inputs are quantized, they are stored as n-bit integers, and the calculations are done using integer arithmetic. The floating-point values to be quantized compose a symmetric range, and for the rest of the paper, this scheme is referred to as symmetric quantization.

q=α2n-1(3a)

ik=round(y/q)(3b)

yq=q*i(3c)

Figure 5 shows the accuracy of our baseline models using two quantization schemes to compress the output layer. In this plot, the baseline accuracy is computed using floating-point values (i.e., fp16) for the weights and inputs of the output layer. As shown in Figure 5, when using the symmetric quantization scheme, even for small compression ratios in both models, the accuracy is impacted negatively. In this work, split quantization is proposed, a new quantization scheme that obtains a compression ratio of 3 × for both models without impacting their accuracy. Also, it achieves a compression ratio of 4.5 × and 5 × for ReActNet and PokeBNN while keeping the accuracy loss below 1%, whereas for symmetric quantization, the accuracy loss is more than 5% for both models.

We note that split quantization is a post-training quantization scheme: no retraining or calibration-based fine-tuning of the BNN model is performed in any of the experiments in this section. The ReActNet and PokeBNN models are used with their published trained weights, and the comparisons that follow (against symmetric quantization in Figure 5 and against per-tail variants in Figure 6) are therefore all between post-training schemes. Learned mixed-precision schemes such as LSQ (Esser et al., 2020) and PACT (Choi et al., 2018) adjust quantization parameters during fine-tuning and therefore fall outside this scope, since a direct comparison would conflate the quantization scheme itself with the use of fine-tuning.

4.1 Analysis of the output layer weight distribution

Figure 7 shows the weight distribution of the output layer for the baseline models. As seen, for ReActNet, more than 90% of the weights are negative, whereas for PokeBNN, more than 70% are positive. Therefore, when using symmetric quantization, half of the quantized values are employed to represent most of the original values. For linear quantization, the maximum error between a floating-point value (y) and its approximation (y_*q*) is half of the quantization step (q). Hence, a small quantization step is preferred when employing linear quantization to have a better approximation and, thus, to minimize any negative effect in accuracy. As seen in Equation 3a, the bit-width should be increased or the value of α (range of the floating point values) decreased to obtain a small quantization step. In the case of BNN models, having a small quantization step is preferred since increasing the bit width will increase the storage requirements.

As depicted in Figure 7, for both models, most of the values are concentrated in a small region around the mean (Figure 7a). Those values are referred to as normal and the values outside this region as outliers; the boundary between them is set systematically using the standard deviation, as described in Section 4.2.1. The outliers are very spread, and thus when using symmetric quantization, a large number of bits is needed to obtain a small quantization step. A common approach to this issue is to clip the outliers value. However, this approach severely affects accuracy. For instance, in ReActNet, when using clipping and 2.5% of the largest weights (in absolute value) are considered outliers, the accuracy drops to 68% for a bit-width of 16 (i.e., a loss of 1.2%).

Another approach is to use two different ranges to quantize normal values and outliers. By doing this, a small bit-width can be used for the normal values while maintaining a small quantization step. However, as shown in Figure 6, the bit-width for the outliers cannot be reduced too far since, in this case, accuracy drops sharply. For instance, the accuracy of ReAcNet drops to 55% when using two bits for the outliers, as seen in Figure 6. On the contrary, note that the bit-width for the normal values is substantially reduced without affecting the accuracy.

A symmetric range is used to quantize the outliers, which include positive and negative values. However, as shown in Figure 7, the range of the negative and positive outliers are not equal. Thus, the size of the quantization step used for the outliers could be decreased by splitting them into positives and negatives and then using a different range for each interval. As a result, in this work, the weights are divided into three regions: normal values, positive, and negative outliers. Having three intervals creates extra overhead in identifying each weight. In Section 5.2.2, a method is described to encode and store each of these groups of values efficiently. Finally, An important decision when dividing the weights into normal and outliers is finding a criterion that can be employed systematically. In this regard, the standard deviation is used to decide which values are normal or outliers.

4.2 Split quantization

Split quantization is done in the following manner. First, the values are divided into two groups: normal and outliers. To determine which values are considered outliers, the methodology described in 4.2.1 is employed. Next, after finding the outlier group, it is further split into positive and negative. Then, for these three groups of values, Equation 4c is employed to compute their quantization step (q). In Equation 4c, n, v_*max*, and v_*min* are different for each group. Also, to obtain the integer index (i), Equation 3b is transformed into Equation 4a. In Equation 4a, the value is first shifted by m i.e., the average of the group range, which is defined in Equation 4b. As seen in Figure 7, the weight distribution is skewed, and thus, it is centered to ensure that positives and negatives values are distributed equally, as can be seen in Figure 8. Moreover, when using symmetric quantization, the index employed to quantize the maximum value (v_*max*) is 2^*n*−1; however in practice, the index 2^*n*−1−1 is used since that is the maximum positive index that can be represented when using n bits to store a range composed of zero, negative and positive numbers. This poses a challenge when using small values of n (i.e., low precision) since the error introduced when representing v_*max* is too large (i.e., q instead of q/2) [this has also been observed in (Wu et al. 2020)]. Hence, this issue is handled by shifting Equation 3b by a factor of 0.5 before performing the round operation, as shown in Equation 4a.

ik=round(y-mq-12)(4a)

m=vmax+vmin2(4b)

q=vmax-vmin2n(4c)

4.2.1 Outliers selection

The mean (μ) and the standard deviation (σ) are employed to systematically divide the weights into outliers and normal. In this case, the interval of the normal values is [μ−kσ, μ+k**σ] where k is a constant. Figure 9 shows the best accuracy obtained using different bit-widths for outliers and normal values and different values of k. As seen in both models, for compression ratios less than 4 × , their accuracy is similar for most values of k (i.e., amount of outliers). However, for larger compression ratios, the accuracy drops dramatically as the number of outliers decreases. This drop occurs because the normal value range increases; thus, the quantization step is larger. In the limit case where no outliers are selected, the scheme reduces to applying a single quantization range over all weights, losing the benefit of handling long-tail values separately. Our chosen operating point of k = 1.5, which corresponds to approximately 12% of the weights being classified as outliers, provides the best trade-off across both models. Finally, since our scheme has three different types of weights, extra bits are needed to identify each group. Hence, one bit is employed to distinguish between normal and outliers. Then, another bit is used for outliers to differentiate between positive and negative outliers. These extra bits are considered to compute the compression ratio in all our experiments.

4.2.2 Output layer input quantization

When using quantization for the output layer, its input must be quantized to employ integer math when evaluating the output layer thoroughly. Figures 10a,b shows the accuracy of the baseline models, ReActNet and PokeBNN respectively, after compressing both weights and inputs for the output layer using split quantization. The input can be compressed by a factor of up to 6 × without affecting the accuracy.

5 Software and hardware implementation

5.1 Overview

A main goal of this work is to employ the compressed 3 × 3 binary kernels and quantized output layer during the evaluation of a BNN model. Conceptually, the overall evaluation works as follows. First, the frequency of use for each bitsequence in all the 3 × 3 binary kernels is computed. Then, based on those frequencies, a Huffman Tree is created and an encoding is assigned to each of the bitsequences. Similarly, the weights of the output layer are quantized using split quantization and the bit-width for the outliers and normal weights is selected. Moreover, two bit-masks are created: the first, outlier mask, is used to indicate the weights that are either outliers or normal, whereas the latter, sign mask is used to mark if an outlier is negative or positive. The previous steps are done offline and only once. Regarding the inputs of the output layer, several of them are first sampled to find the bit-width and the range of values considered normals or outliers. Then, the input is quantized at runtime using the bit-width computed in the previous step.

When evaluating a 3 × 3 kernel, the Huffman tree corresponding to that kernel is stored in memory. After this, the compressed bitsequences and inputs are fetched from memory. Then, the bitsequences are decompressed, and the kernel evaluation is performed. This process is repeated for all bitsequences in the kernel. Compressing the kernels decreases the storage requirements but adds an overhead to decode the bitsequences, which would result in a slowdown if implemented in software. However, this overhead can be mitigated with additional hardware support. These issues are detailed in the following sections.

Regarding the evaluation of the output layer, this is done as follows. First, the outlier mask and sign mask for weights are stored in memory. Then, the input values are split into outliers and normals, and then quantized using Equation 4a. Next, a dot product between each row of the weights matrix and the input vector is performed. However, note that when performing the dot product, the multiplications of each element need to be accumulated into separate variables depending on whether the values multiplied are outliers (positive or negative) or normals. Hence, after multiplying a single input or weight element, it must be checked whether it is normal or an outlier using the outlier mask and sign mask, and the result accumulated into the corresponding accumulator. Once all the elements of a row have been multiplied and accumulated, the results on each accumulator are multiplied by its corresponding quantization step. Then, all the accumulators are added together to obtain the final result. This process is repeated until all the rows of the weight matrix are computed.

5.2 Software baseline

5.2.1 3 × 3 binary convolutions

When evaluating the 3 × 3 convolutional layers of BNNs in modern hardware (i.e., CPUs, FPGAs), one of the most critical components is laying out the kernels in memory such that the number of bits loaded into the internal register of the hardware (Zhang et al., 2019; Trusov et al., 2022) is maximized. In this regard, one of the most efficient methods is to pack bits from different channels together so that the number of bits packed fills an entire register when loaded from memory (Zhang et al., 2019). For simplicity, this method is referred to as channel packing.

In channel packing, the group of bits packed from each channel must belong to the same position (e.g., 0,0), as shown in Figure 11. Also, when the number of channels is larger than the CPU register's size, the channels are split into several sub-groups such that they can be loaded independently into the CPU registers. Note that channel packing works best when the number of channels is divisible by the size of the CPU registers; otherwise, padding is needed. Padding BNN kernels is challenging since the zero value represents a −1. Subsequently, when padding is done, the kernel computation must account for the extra −1. In this work, channel packing is employed to store the uncompressed 3 × 3 binary kernels, and it is done offline, as in Zhang et al. (2019). Also, since the number of channels for all the kernels is a power of two, padding is not employed.

Regarding the layout in memory of the compressed kernels, note that each of the encoded bitsequence has a variable length, and thus channel packing cannot be performed offline. In this case, they are stored consecutively in memory as a sequence of encoded words. As a result, once an encoded bitsequence is decoded during the kernel evaluation, it needs to be packed into the internal registers of the underlying hardware. Moreover, the size of a decoded bitsequence is 9 bits, whereas the typical size of an internal register is a power of two (e.g., 32 bits); hence if packing is not done, the CPU registers are underutilized.

The compression scheme was implemented in software to evaluate its feasibility. Then, the performance of this implementation was compared against a baseline using uncompressed kernels. The simplified Huffman Tree described in Section 3.2 was employed for the compression scheme. In this case, the size of each tree is limited to four nodes and four tables are used to store the decoded bitsequence. Then, the first bits of each encoded bitsequence are employed to indicate the table where it belongs. Moreover, the remaining bits in the uncompressed bitsequence are used to get the original from its corresponding table. The result of this comparison is that the compressed kernel implementation is 1.47 × slower than the baseline. This slowdown is due to the overhead of decoding and packing the bitsequences at runtime. Hence, to mitigate this issue, performing it in hardware is proposed, and the required hardware structure is described in Section 5.3.

5.2.2 Split quantization

Regarding split quantization, a kernel similar to the implementations in ARMNN (ArmTools, 2023) is employed to perform matrix-vector multiplication. However, support was added to fetch values (i.e., inputs and weights) based on the outlier mask and sign mask. Moreover, since the smallest bit-width supported by the baseline CPU is 8 bits, all values have to be quantized using 8 bits. Hence, extra hardware is needed to support lower bit widths. Also, due to the overhead of indirectly fetching the normal and outlier values when compared to a baseline using symmetric quantization, split quantization has a slowdown of 1.3 × . Due to CPU limitations, split quantization is more suitable for FPGAs, where smaller bit widths can be easily supported.

5.3 Hardware support

In order to evaluate our proposals with the required hardware support, they were implemented on an FPGA. To this end, the accelerator proposed in (Zhang et al., 2021) is used as a baseline. This accelerator, shown in Figure 12, is highly optimized for BNN models with architectures similar to ReacNet. It consists of a convolution engine, a matrix-vector multiplication engine, and additional hardware structures to compute the activation functions and batch normalization. Also, the matrix-vector multiplication unit is employed to evaluate the last layer and the other dense layers found in PokeBNN. Finally, to further optimize the baseline, the batch-norm and binarization layers are fused following a methodology similar to the one proposed in Daghero et al. (2021). For simplicity, this accelerator is referred to as FracBNN in the rest of the paper.

The accelerator is designed for a ZYNQ SOC using Vitis-HLS and Vivado. The model is stored in the main memory and sent to the FPGA by a program driver running on the CPU of the ZYNQ SOC. The driver is written in Python using the Pynq framework. The interface between the driver and the accelerator uses AXI ports, and the model is evaluated layer by layer. In this regard, the weights and inputs are copied to the internal BRAM of the programable logic when evaluating a layer. Then, to start the evaluation in the kernel, a command is written to one of the internal registers of the Zynq SOC. Each of the main components of the accelerator is implemented as a HLS function. To synthesize the buffers and internal storage, the internal BRAM of the ZYNQ programmable logic is used, and the interface between the main memory uses DMA.

5.3.1 Supporting kernel compression

As mentioned earlier, when evaluating convolutions with compressed kernels, the software implementation is penalized by the need to decode and pack the bitsequences at run-time. To mitigate this issue when employing kernel compression on FPGAs, a decoding unit is added to the accelerator. This new unit is in charge of decoding and packing the compressed kernels. The decoding unit, shown in Figure 12, is tailored to streaming and decoding the encoded bit sequences. It comprises a streaming unit and a packing unit.

In FracBNN, the 3 × 3 binary kernels are channel packed and fetched from main memory in a sliding windows manner, so it is modified in the following way. First, the streaming unit loads a 3 × 3 window of encoded bit sequences from main memory and uses the stream address register to store the base address of the bit sequences that will be fetched. Then, a request to load T bytes from the address in the stream address register is sent to the memory controller. Once the T bytes are fetched from main memory, they are stored in the input buffer. After this, the decoding process starts by sending m-bits of data from the input buffer to the stream parser. A new request to fetch the next bytes is performed while doing the decoding to overlap both activities. In the stream parser, from this m-bits, the first n bits are used to create the node address, which identifies the node of the Huffman tree belonging to the current bit sequence. Since the length of the encoded bit sequence is variable, its length needs to be found after finding the node. This is done by reading it from the length table, which is addressed with the node address. Then, with the length information, the remaining bits of the encoded bit sequence can be obtained and stored in the decoded address register. Next, in the decoder unit, the uncompressed bit sequences are stored in a scratchpad memory (BRAM) (uncompressed table), which is partitioned into multiple banks. Then, the node address and the value in the decoded address register are employed to address the uncompressed table and get the uncompressed bit sequence. Finally, the uncompressed sequence is passed to the packingunit. The previous process is repeated until the whole stream of bits in the input buffer have been processed.

The packingunit is in charge of channel packing the bit sequences received from the streamingunit into the packing registers. In this unit, after receiving a bit sequence, it is distributed into k registers (e.g., 9 ) each of R bits (e.g., 128 bits). After the sequences are channel packed, they are passed to the convolution unit, where they are processed. This process is repeated until the whole kernel is evaluated.

5.3.2 Supporting split quantization

To support split quantization, the matrix-vector multiplication engine of the baseline accelerator is extended as shown in Figure 12. To this end, extra buffers are added to store the sign and outlier masks. Also, a quantization unit is added to perform the quantization of the input in the FGPA. Furthermore, the matrix-vector multiplication is modified in the following way. First, the input vector is loaded from the main memory and passed to the quantization unit, and then it is quantized using split quantization. The quantization step, bit-width, and interval range (outlier, normal) are computed offline. Note that only these parameters are computed offline; the input activations themselves are quantized at runtime by the quantization unit, using the precomputed parameters. Then, normal and outlier values are stored on separate buffers after they are quantized. Once the input is quantized, a row of the weight matrix starts to be fetched, and depending on the outlier and sign mask, they are stored in separate buffers. Then, after a row of weights has been fetched and the values split into different buffers, the vector multiplication between the input and the row of weights starts to be performed. Also, the next row of weights begins to be fetched. During the multiplication step, the corresponding bit mask and sign mask need to be checked to determine where the value being multiplied is stored. Then, after an input value and weight are multiplied, the result is accumulated. The accumulation is done in a different register depending on the type of values being multiplied (i.e., normal or outlier) since they need to be multiplied by a different quantization step at the end to compute the final outcome. This process is repeated for each row of the weight matrix. Finally, note that to support a given bit-width, the matrix-vector unit must be synthesized for it. Hence, the accelerator must be recompiled to change the bit-width employed during split quantization. This is a deliberate trade-off, as a fixed bit-width allows the multipliers, adders, and buffers to be sized exactly to the required precision, reducing LUT usage and improving timing. Supporting runtime-configurable bit-widths is feasible. For instance, this can be done by synthesizing the unit at the maximum supported precision and masking unused bits, or by instantiating parallel units for different bit-widths. However, both approaches would incur additional area overhead. We leave this exploration as future work.

6 Evaluation methodology

The Pytorch implementation of ReActNet and PokeBNN is employed as our software baseline to evaluate their accuracy, and in all our experiments, the ImageNet dataset is used. Also, Python is used to compress and analyze the frequency of use for each bit sequence. For the performance evaluation on a CPU, the daBnn (Zhang et al., 2019) C++ framework is used to implement the convolutional layers of the BNN models. DaBnn employs channel packing for the kernels and inputs. Moreover, it provides several C++ functions to compute the most common layers found in BNNs. This library is highly optimized for the ARM CPUs architecture and uses the NEON extensions. Finally, to evaluate the output layer, a matrix-vector multiplication kernel from ARM NN (ArmTools, 2023) is employed.

Our proposals are evaluated on a PYNQ-Z1 board which contains a Xilinx Zynq-7000 SoC with an XC7Z020 FPGA and an ARM Cortex-A9 embedded processor. Vitis HLS and Vivado are employed for HLS compilation and Synthesis. To assess the software baseline, it is evaluated on the ARM Cortex-A9 of the Z1 board. Also, the assembly functions used by daBnn were rewritten, such that they are employed when computing the binary kernels. Moreover, the matrix-vector multiplication kernels for the output layer are modified to use split quantization. The main configuration parameters for the Z1 and the accelerator are shown in Table 4.

Table 4. Configuration parameters.

7 Results

To evaluate our proposals, the modified accelerator is synthesized for a PYNQ-Z1. To evaluate its performance, it is compared against the FracBNN (Zhang et al., 2021) accelerator without our schemes. This baseline evaluates the output layer using 16-bit floating point numbers (fp16). Also, to split the outliers, a k value of 1.5 is employed, which works better in both models. Regarding the configuration of the Huffman tree, we adopted a four-node tree to keep the decoder simple: a deeper tree would increase the number of prefix-comparison stages and the number of independent BRAM-backed tables, with diminishing returns on compression. Within this four-node tree, we constrained the number of entries per node to be a power of two so that the payload bits within each node are an integer number of bits and the uncompressed-table BRAMs can be addressed with a clean log₂(size)-bit index. The total codeword length for a node is then the prefix length plus log₂ (size). For the chosen allocation (32, 64, 64, 256), this gives codeword lengths of 6, 8, 9, and 12 bits, respectively. The specific allocation was guided by the frequency distribution shown in Figure 3 and Table 2: the smallest node holds the very-high-frequency tier, the middle nodes cover the medium-frequency tier, and the largest node absorbs the long tail.

Table 3 shows the compression ratio by layer for ReAcnet and PokeBNN. The Huffman column refers to encoding the 3 × 3 kernels without removing the less frequent bitsequences, whereas the 256 most uncommon are removed for the Clustering column. When only using Huffman, the compression ratio for ReAcNet is between 1.18 × and 1.25 × . On the other hand, for PokeBNN, the compression ratios are between 1.1 × and 1.24 × . For both models, these improvements come from employing only 6 bits to store the 32 most common bit sequences, which have an average frequency of use of 46 and 39% for ReAcNet and PokeBnn, respectively. Also, for both models, the rest of the bit sequences are stored using 8, 9, and 12 bits. For these groups, the average frequency of use ranges from 28 to 5%. After removing some of the least used bit sequences, the average compression ratio for ReAcNet is 1.32 × , whereas it is 1.3 × for PokeBNN. This extra improvement comes from increasing the frequency of the top 32 bit sequences to 65% on average. Also, the frequency of use for sequences stored using 12 bits is less than 1%. Finally, sequences encoded with 8 and 9 bits have a frequency of use of less than 25 and 8%, respectively. Note that for both of these optimizations, the model's original accuracy is maintained. Also, this compressing scheme does not provide performance benefits since the computations remain the same, and loading and decoding overlap with them.

Regarding the compression of the output layer, a trade-off between accuracy and reduction can be obtained considering 12% of the values as outliers and the rest as normal. For this configuration, without losing accuracy, the output layer of ReAcnet can be compressed by 2.6 × and by 2.8 × for PokeBNN. Also, for an accuracy loss smaller than 1%, the compression ratio for ReAcnet is up to 3.8 × , whereas for PokeBNN, it is 4.9 × . Finally, the overall compression ratios for ReAcnet and PokeBnn are 1.55 × and 1.51 × , respectively, when combining kernel compression and the output layer quantization without losing accuracy.

Table 5 shows the speedup (SP column) for different bit-widths to quantize the output layer on the accelerator, compared to a baseline using 16-bit floating point values. As can be seen, speedups of 13 × to 55 × are obtained when quantizing the weights and inputs with 2, 4, and 8 bits, respectively. In this regard, the performance improvement comes from two sources; first, the latency of fetching the weights and inputs is decreased since the number of bytes loaded decreases in proportion with the bit-width. Also, more bits are packed into each request to main memory. Secondly, with a smaller bit-width, the multiplications' latency is lower since smaller multipliers and adders are employed to compute the output layer. Finally, for the end-to-end evaluation of ReAcNet and PokeBNN, an average speedup of 2.2 × and 2.3 × is obtained. These speedups come from executing the output layer faster; kernel compression does not contribute to the speedup, since the binary convolution is unchanged and the loading and decoding of the compressed kernels overlap with computation.

Table 5. Performance and compression comparison for the output layer evaluated on the accelerator.

For the baseline, the accelerator uses 16 bits floating point values. SP is the speedup for computing the output layer. The column Bits(n/o) represent bit-width employed for normal and outlier values, respectively. Ratio is the compression ratio and Loss is the accuracy loss compared to the baseline. LUT is the percentage of the lookup table used to implement the vector-matrix unit on the FPGA.

7.1 Design trade-offs and resource considerations

The proposed techniques present several trade-offs that are worth making explicit. The bit-width employed in the matrix-vector engine is fixed at synthesis time and cannot be reconfigured at run-time (see Section 5.3.2); changing the operating bit-width requires re-synthesizing the accelerator. The kernel compression ratio depends on the entropy of the bit-sequence distribution of each layer, so models whose 3 × 3 binary kernels have a close-to-uniform distribution would benefit less from variable-length encoding. The clustering optimization in Section 3.3 is conservative by design and only applies replacements that do not affect accuracy, so its additional gain over plain Huffman encoding is layer-dependent. Split quantization, in turn, is a post-training scheme that does not require retraining the network ; this is a practical advantage for deployment, but it also means that, at the most aggressive bit-widths, accuracy cannot be recovered through fine-tuning.

The contribution of split quantization to the overall compression ratio also depends on the size of the output layer relative to the rest of the model, which in turn depends on the number of classes being classified. In our ImageNet-trained models, the output layer accounts for 36 to 47% of total storage because of the 1000-class classifier layer. For deployment scenarios that reuse the same convolutional layers with smaller classifier layers, such as fine-grained classification (Krause et al., 2013; Wah et al., 2011), medical imaging (Wang et al., 2017; Codella et al., 2018), or industrial quality control (Bergmann et al., 2019), the output layer represents a smaller fraction of the model and the contribution of split quantization shrinks proportionally. To quantify this effect, we computed the projected overall compression ratio assuming the same convolutional layers and an output layer scaled proportionally to the number of classes. For a 200-class classifier layer, the overall compression ratio drops from 1.54 × to approximately 1.32 × , while for a 10-class classifier layer it drops to approximately 1.26 × , with the benefit coming almost entirely from kernel compression. Conversely, for tasks with larger class counts than ImageNet, such as face recognition (Guo et al., 2016) or large-vocabulary speech recognition (Chiu et al., 2018), the output layer dominates further and the benefit of split quantization grows.

Regarding power consumption, both proposed techniques reduce the amount of work performed per inference, which is the main driver of energy in embedded BNN inference. Kernel compression reduces the number of bytes fetched from DRAM, while split quantization reduces both the bit-width of the output-layer operands and the number of bytes loaded for the output-layer weights and inputs. The hardware structures added to the baseline accelerator are small: the decoding unit uses 1 KB for the uncompressed table, 256 B for the register file, and 256 B for the input buffer (Table 4), and the quantization unit and the sign/outlier mask buffers added to the matrix-vector engine are similarly modest. We therefore expect the energy per inference to improve roughly in proportion to the 2.2 × latency improvement reported in Section 7, although the instantaneous power may remain comparable to the baseline since the peak switching activity of the accelerator is dominated by the convolution engine, which is unchanged.

In terms of area, Table 5 reports the LUT usage of the matrix-vector unit for the three evaluated bit-widths (12%, 16%, and 27% of the Pynq-Z1 LUTs for 2/2, 4/4, and 8/4 bits, respectively). These figures are substantially lower than what an equivalent fp16 implementation would require, since the LUT cost of integer multipliers and adders grows quickly with bit-width. The decoding unit adds a small amount of additional logic, dominated by the streaming and packing structures shown in Figure 12; its area is small compared to the convolution engine, which is the largest block in the accelerator. The overall design fits comfortably on the XC7Z020.

8 Related work

Hardware acceleration for BNNs has been an active area of research in recent years. In this regards, there have been several works targeting CPUs (Trusov et al., 2022), FPGAs (Zhang et al., 2021; Du et al., 2022; Fiscaletti et al., 2020), ASICs (Hosseini and Mohsenin, 2021), and GPUs (Chen J.-A. et al., 2023). FracBnn (Zhang et al., 2021) proposes an FPGA accelerator for ReActNet. In addition, it improves performance by employing up to two bits for activation and increasing the level of sparsity in the kernels. The work in Du et al. (2022) proposes an FPGA accelerator that combines the xnors operations and accumulations to improve performance. BNNsplit (Fiscaletti et al., 2020) is another accelerator that divides the evaluation of the BNN model across multiple FPGAs. The work in Liang et al. (2018) proposes a BNN accelerator for FPGAs where the normalization layers are computing using shift-based operations to reduce the cost of the multipliers. Our proposal differs from these works since it focuses on compressing the kernels and quantizing the output layer.

Hosseini and Mohsenin (2021) propose a programmable many-core accelerator targeting the primary operations found in BNN networks. The work in Cho et al. (2021) is another BNN accelerator that analyzes each layer and, based on the given parameters, reconfigures the hardware to increase parallelism. Both works target ASICs, whereas our work focuses on FPGAs.

The work in Trusov et al. (2022) proposes a new blocking algorithm to partition the binary kernels using a small block size such that the utilization of CPU vector registers is increased. In Deep Compression (Han et al., 2015), Huffman encoding is applied to full-precision networks after pruning them. This scheme works on GPUs, and the optimizations are in software. Our proposal is different since it is a hybrid software/hardware approach. Similarly, the work in Chen T. et al. (2023) prunes the layers of a BNN model using the latent weights obtained during back-propagation. Their network targets Cifar-10 and Mnist, and after pruning, the model size is reduced by 33%–46%. Likewise, in Kong et al. (2022), the authors proposed an early-exit scheme that chooses between three models of different sizes based on a confidence level. They implemented this scheme on an FPGA and improved the performance by 20% with an accuracy drop of 1.56%. Our work differs from theirs since it focuses on compressing the kernel with variable encoding and quantization, whereas they employ pruning or early-exit. Regarding training and inference frameworks for BNNs, RebNet (Ghasemzadeh et al., 2018) proposes a framework for training BNNs that adjusts and reconfigures the model based on the target accuracy of the application. Also, it can generate an FPGA design that is ready for deployment. FINN (Umuroglu et al., 2017) is another framework tailored to building accelerators for BNNs. Once a BNN model is designed, FINN can generate an HLS accelerator for the model, which can be synthesized for a target FPGA.

Compared to our previous proposal (Silfa et al., 2023), the output layer of BNN models for image classification is observed to account for almost 50% of the storage requirement and 60% of the execution latency of the entire model. Then, the weights and inputs for the output layer are extensively analyzed, showing that they can be quantized with very low bit-width. In addition, a quantization scheme for the input and weights of the output layer is proposed. Then, the required hardware structures are added to a BNN accelerator (Zhang et al., 2021) to support our techniques (quantization and clustering). The compression scheme in Silfa et al. (2023) is for general-purpose CPUs. Moreover, the workbench models are extended. Finally, the schemes proposed in this work improve storage and performance by 1.5 × and 2.2 × , while the improvements for Silfa et al. (2023) are 1.2 × and 1.4 × .

Table 6 summarizes the main FPGA-based BNN accelerators discussed in this section and highlights the distinguishing features of our proposal. Unlike prior work, our scheme targets both the convolutional kernels and the output layer, combining variable-length encoding with split quantization and providing the corresponding FPGA hardware support. A direct quantitative comparison across these accelerators is not straightforward, since they target heterogeneous FPGAs (Pynq-Z1/Zynq-7020, Stratix-V, Zynq UltraScale+, and others), different BNN topologies (MobileNet-derived, VGG-derived, CNV/SFC), and different datasets (ImageNet, CIFAR-10); normalizing metrics such as ops per LUT or accuracy per stored bit across these dimensions would require assumptions (LUT-equivalence factors between vendor families, model-size scaling laws across topologies) that obscure rather than clarify the underlying differences. The quantitative comparison in this work is therefore made against FracBNN (Zhang et al., 2021), which shares the FPGA platform, the BNN models, and the dataset with our setup, eliminating the largest sources of heterogeneity. Against this baseline, our techniques reduce model storage by 1.5 × and improve end-to-end performance by 2.2 × on average, with the per-component breakdown reported in Section 7.

Table 6. Comparison of FPGA-based BNN accelerators.

Kernel comp. and Output comp. indicate whether the work compresses the convolutional kernels and the output layer, respectively.

9 Conclusion

In this work, our aim is to reduce the storage requirements of binary neural networks while improving performance. To this end, the storage requirement for the 3 × 3 binary kernels and the output layer is decreased using a variable encoding scheme and aggressive linear quantization. To compress the 3 × 3 binary kernels, some of their bit sequences are shown to occur more frequently than others. Then, this observation is exploited by encoding the bit sequences with a simplified Huffman Tree. Furthermore, to reduce the storage requirement of the output layer, it is observed that only a small subset of the weights needs high precision when quantized. Hence, the weights of the output layer are divided into two groups, each requiring different precision. It is worth noting that the relative contribution of each technique depends on the model and task: split quantization is most beneficial when the output layer represents a large fraction of the model, as in classification tasks with many classes, while kernel compression remains effective regardless of the number of classes. Finally, after applying both schemes, an average compression ratio of 1.5 × and an average speedup of 2.2 × are obtained.

Generative AI statement

The author(s) declared that Generative AI was not used in the creation of this manuscript.

Any alternative text (alt text) provided alongside figures in this article has been generated by Frontiers with the support of artificial intelligence and reasonable efforts have been made to ensure accuracy, including review by the authors wherever possible. If you identify any issues, please contact us.

Publisher's note

All claims expressed in this article are solely those of the authors and do not necessarily represent those of their affiliated organizations, or those of the publisher, the editors and the reviewers. Any product that may be evaluated in this article, or claim that may be made by its manufacturer, is not guaranteed or endorsed by the publisher.

Footnotes

Edited by: Jaime H. Moreno, Retired, Yorktown Heights, NY, United States

Reviewed by: Dhruva Ghai, Oriental University, India

Minh Huan Vo, Ho Chi Minh City University of Technology and Education, Vietnam

Yichi Zhang, Google, Inc., United States