Bit-balance: Model-Hardware Co-design for Accelerating NNs by Exploiting Bit-level Sparsity

The computing process of NNs is shown in Fig.1. A CONV layer receives $C_{i}$ input channels (ICs) of IFMs with a size of $H_{i}\times W_{i}$. Each OFM of $C_{o}$ output channels (OCs), with a size of $H_{o}\times W_{o}$, is generated by sliding a $H_{k}\times W_{k}$ kernel window on one IFM and then accumulating across the temporary results of $C_{i}$ ICs. Finally, $C_{o}$ OFMs are calculated by convolving $C_{o}$ groups of kernels with shared IFMs. For FC layers, the size of IFMs and OFMs are both $1\times 1$. Set IFMs as matrix $I$[$C_{i}$,$H_{i}$,$W_{i}$], weights as $W$[$C_{o}$,$C_{i}$,$H_{k}$,$W_{k}$] and OFMs as $O$[$C_{o}$,$H_{o}$,$W_{o}$], and the process can be described as Equ.1.

Referring to Equ.1, the basic operations of NN processing are MACs. Assuming the bitwidth of weights is $N$, the MAC of an IFM, $I_{0}$, and a weight, $W_{0}$, can be decomposed to shift and add operations, as shown in Equ.2, which is flexible for varying bitwidth.

To accelerate bit-serial processing, quantizing the weight to lower bitwidth is the most straightforward method. If the weight is quantized from $N$-bit to $N_{pb}$-bit, we can achieve $N/N_{pb}\times$ speedup. An example of bit-serial computing with quantized weight is shown in Fig.2, achieving $1.3\times$ performance improvement. However, assuming the value of $N$-bit weight is $2^{N}$, it can be decreased to $2^{N_{pb}}$ when the bitwidth is tailored to $N_{pb}$. To maintain the accuracy, the reduction of bitwidth can be limited, which constrains the performance improvement.
To further improve performance, the bit sparsity of weights can be exploited for acceleration by skipping zero-bits computing. Assuming the NNZB in each weight is $N_{nzb}$ with the largest value being $N_{nzb\_max}$, weights are compressed and loaded in PE array, with $N_{nzb\_max}$ computing cycles. An example of bit-serial computing by exploiting sparsity is shown in Fig.3(a), achieving $1.6\times$ performance. However, since the sparsity ratio of weights is randomly distributed, the workloads across the PE array is imbalanced. The PEs with small NNZB must wait for those with large NNZB to finish. Thus, $PE_{1}$ will be idle for $2$ cycles, indicating inefficient PE utilization. Moreover, once the $N_{nzb\_max}$ is equal to original weight bitwidth, there can be no performance improvement.

Since NNs have the nature of strong fault tolerance, the weights allow redundant bits. However, quantizing weights to lower bitwidths directly will significantly decrease the numeric range of weight value and exploiting the randomly distributed bit sparsity of weights will suffer from imbalance workloads. Thus, to maintain the numeric range of weight value and balance computing loads across the PE array, we proposed a bit-sparsity quantization method, which set several weight bits as zero and maintain the maximum NNZB, $N_{nzb\_max}$, in each weight to no more than a certain value. Assuming the bitwidth of original weight is $N$, its numeric range can be calculated as $\sum_{i=0}^{N_{nzb\_max}}\binom{N}{i}$. Compared with quantizing the weights to $N_{pb}$-bit directly, the numeric range of weight value in our method is more abundant, as shown in Tab.I. The case of $N_{nzb\_max}=3$ in bit-sparsity quantization can be competitive with $N_{pb}=9$ in bitwidth quantization.

To reduce the overhead of sparsity processing, the weights are encoded with length, sign, bit position, and bitmap, as shown in Fig.6. The length, $N_{nzb\_max}$, represents the maximum NNZB of all weights, which only needs to be stored once for all weights in the current layer. The sign, $W_{s}$, indicates the positivity or negativity of one weight. The bit position, $W_{p}$, determines how many bits IFM should shift. The bitmap, $W_{b}$, indicates whether the bit position is valid or not since the NNZB of some weights is smaller than $N_{nzb\_max}$.

Fig.7 shows an example of sparse bit-serial computing. Fig.7(a) shows the original MAC operation, $Psum=I_{0}*W_{0}+I_{1}*W_{1}$. Fig.7(b) shows the encoding format of two weights, with the maximum NNZB, $N_{nzb\_max}=3$. The computing flow is shown in Fig.7(c). At $T_{0}$, we fetch $W_{p0}=1$, $W_{p1}=1$, and then $I_{0}$ and $I_{1}$ both shift left 1-bit, calculating $Psum=20$. Similarly, at $T_{1}$, the Psum is calculated as $140$. Since the last bitmap of $W_{b1}$ is zero, the operation of $W_{p1}$ is invalid and the final result is $60$. The entire process takes $3$ cycles, which is $2.67\times$ faster than $8$ cycles of the original process.

As shown in Fig.8, the top-level architecture mainly consists of input-weight buffers (I&W buffer), a systolic-based PE array, post-processing modules (Post-pro module), output buffers, a top controller, and a DMA interface. Initially, the weights in encoding format and control parameters were generated at software level. These data and input images were directly loaded into DRAMs. Next, the IFMs and weights were fetched by I&W buffers and then transferred to the PE array. After massive bit-serial operations by PEs, post-pro modules take in the outputs to perform ReLU and pooling for final OFMs, which were buffered in the output buffers temporarily. Finally, the OFMs of the current layer were stored to DRAMs for the next layer computing. We executed layer-wise, and the OFMs of the last layer were classified to output the final results. The top controller mastered the entire computing flow and the on/off-chip data were transported through the DMA interface.

The systolic-based PE array, in charge of bit-serial computing, is composed of $N_{PE}\times N_{PE}$ PEs, among which PEs of the same row share IFMs of one IC, and PEs of the same column process OFMs of one OC. Each PE contains a complement processing unit, a shift unit, and an accumulation unit, as shown in Fig.9. First, the sign of weight, $W_{s}$, chose the complement or the original value of the IFM. Then, the temporary result was shifted left based on the weight-bit position, $W_{p}$. Finally, the shifted result was accumulated with adjacent PE. To reduce power consumption, the complement processing unit and shift unit are gated when the weight bitmap, $W_{b}$, is zero. Moreover, to adapt to different bitwidths of IFMs and weights, we merged the 8-bit operation with 16-bit operation for higher resource utilization. The 16-bit IFMs with the corresponding 32-bit temporary results can be divided as two pairs of 8-bit IFMs and 16-bit temporary results, achieving $2\times$ peak throughput in 8-bit operation compared with the 16-bit.

To reduce energy consumption of the on/off-chip data movement, we need to buffer IFMs, weights, and OFMs for data reusing. Thus, the on-chip buffers mainly consist of I&W buffers and output buffers. To avoid performance bottleneck of data loading, we utilized each group of two memories as Ping-Pong buffers, one for DRAM access and the other for PE transporting, which is similar with other systolic-array based accelerators[25]. To support adaptive bitwidth computing, the bitwidths of I&W buffers and output buffers are both 16-bit, which can store one 16-bit IFM/OFM or two 8-bit IFMs/OFMs per address. For weights in encoding format, we store 16 weight signs, 16 weight bitmaps, 4 weight positions of 16-bit precision, or 5 weight positions of 8-bit precision per address.

For limited on-chip buffer resources and PE array size, we need to partition IFMs and weights into independent sub-tiles in terms of edge size and input/output channel, referring to the tiling method[25]. Considering the resources of Psum storage, the size of IFM sub-tiles is set no larger than $W_{IS}\times H_{IS}$, and the sizes of IFM tiles on the width and height dimension are $T_{WI}$ and $T_{HI}$, respectively. For limited PE array size, we only process $N_{PE}$ input and output channels concurrently, with tiling numbers of $T_{IC}$ and $T_{OC}$. The specific tiling parameters are shown in Tab.II. After data partition, each tile of IFMs and weights can be processed with sparse bit-serial computing independently.

Considering dataflow and partition of IFM and weight, to map various networks on Bit-balancing, we designed a network mapping algorithm. The computing flow description is shown in Tab.III. The 1st and 4th rows decide the dataflow according to Adaptive Dataflow Configuration[25]. For "reuse IFM first (RIF)", we finish the OFM computing of all OCs for one output tile before switching to the next output tile; otherwise, for "reuse weight first (RWF)", we finish computing of all output tiles for one OC before switching to the next OC. The 2nd and 3rd rows describe the partition of IFM, with a row number of $T_{ofm\_row}$ and column number of $T_{ofm\_col}$. The 5th row drives the accumulation of input channels to obtain the final Psums. The 6th and 7th rows represent the element number of one tile of IFM and one kernel. The 8th row indicates the maximum NNZB of the weights, where $N_{nzb\_max}$ is loaded as a parameter because the weights from training are fixed. The 9th row indicates that the PE is performing the sparse bit-serial computing with IFM and the weight bit position.

Bit-balance Implementation: To measure the area, power, and critical path delay, we implemented Bit-balance in Verilog and conducted a functional simulation on Cadence Xcelium 2019.2. Then, the Verilog code was synthesized with Synopsys Design Compiler (DC). The on-chip SRAM buffers are generated by Memory Compiler. The on-chip power is calculated by Synopsys Prime Suite 2020.09 with the Switching Activity Interface Format(SAIF) file generated from testbench. The reports of resource utilization and power breakdown are shown in Tab.IV.
The size of the PE array is $32\times 32$, achieving a peak throughput of $1024GOP/s$ and $2048GOP/s$ for 16b and 8b shift-add operations respectively. The IFMs and weights are both encoded in 16 bits or 8bit, and their Psum are correspondingly truncated to 32 bits and 16 bits respectively. Since the PEs are implemented with shift-add units, the area of computing core (CC), containing PE array, post processing module, and controller, is only 2.91mm². To balance the data reuse efficiency and resource overhead, we set the IFM tiling unit as $8\times 8$. Each I&W buffer contains two $1K\times 16b$ and two $256\times 16b$ single-port static random-access memories (SRAMs); each output buffer and post processing module contain two $64\times 16b$ single-port Register Files (RFs) and one $64\times 16b$ dual-port RF, respectively. Thus, the total on-chip memories are 176KB. The power consumption mainly comes from the computing core, taking up 85% power of full chip.

To verify the superiority of Bit-balance, we set some baseline accelerators as shown in Tab.V. The brief descriptions of each accelerator are presented as below:
1) Eyeriss[9] is a typical bit-parallel accelerator based on the 16-bit fixed-point MAC, without considering the sparsity of IFMs or weights. By comparison, Bit-balance achieves better performance through exploiting weight bit sparsity and higher energy efficiency by replacing MAC units with shift-add units.
2) Cambricon-X[13] accelerates NNs by skipping zero-weight elements computing. However, the whole architecture is designed for accelerating NNs of 16-bit precision, resulting in inefficient resource utilization in lower-bit operation. By comparison, Bit-Balance achieves higher resource efficiency through bit-serial computing.
3) Stripe[16] allows per-layer selection of precision instead of fixed-point values, which improves performance proportionally with the bitwidth of IFMs based on bit-serial computing. But it only truncates the bitwidth while ignoring the bit sparsity of IFMs. By comparison, Bit-Balance achieves higher performance by skipping the zero bits of weights.
4) Laconic[21] tears MAC operation into IFMs and weights bit-serial computing and achieves great speedup by exploiting both IFM and weight sparsity. However, the distribution of zero bits in IFMs and weights can be irregular, which causes imbalanced workload in the PE array and degrades performance. By comparison, Bit-Balance achieves higher performance through bit-sparsity quantization.
5) Bitlets[23] proposes a bit interleaving philosophy to maximally exploit bit-level sparsity, which enforces the acceleration by decreasing the number of weights involved in computing. However, the logic corresponding to the bit-interleaving occupies 40% area of the entire PE module. Besides, the computing units for the high-bit can be idle during low-bit operation, causing inefficient resource efficiency. By comparison, we achieved higher energy efficiency and resource efficiency with model-hardware co-design and adaptive bitwidth computing.
As for benchmarks, we conducted inference on AlexNet[1], VGG-16[2], ResNet-50[4], GoogleNet[3], Yolo-v3[5] and compared our design with each baseline. The first four NNs are testified on ImageNet[1] and Yolo-v3 is testified on CoCo[26].

To show the advantages of sparse processing methods in Bit-balance, we compared our design against Eyeriss[9], Cambricon-X[13], Stripe[16], Laconic[21], and Bitlets[23] on normalized performance, achieving $1.6\times$~$8.6\times$, $1.1\times$~$2.4\times$, $4\times$~$7.1\times$, $2.2\times$~$4.3\times$, and $1.1\times$~$1.9\times$ speedup, respectively, as shown in Fig.10. In AlexNet, VGG-16, ResNet-50, GoogleNet, and Yolo-v3, we set the maximum NNZB, $N_{nzb\_max}$, as 3~4 in 16-bit precision and 4~5 in 8-bit precision, respectively, as shown in Tab.VI. The columns of Top 1 and Top 5 accuracy show the inference accuracy of each NN and its corresponding accuracy loss in the brackets, which is referred to the training structures of Pytorch[27]. The performance is calculated by the ratio of frequency and total cycles of inference computing, achieving $4\times$~$8\times$ speedup compared with the basic bit-serial computing of 16-bit precision. Though the accuracy of 16-bit precision is higher than the 8-bit and its maximum NNZB is also smaller, the peak throughput of the 8-bit is twofold, resulting in higher performance naturally. The normalized performance, $R_{p}$, is calculated by the ratio of our performance and other accelerators. Since Cambricon-X, Stripe, and Laconic didn’t provide their performance in the paper, the normalized performance is calculated based on the comparison with Bitlet and Eyeriss in our benchmarks.

Since the processing methods of each accelerator are different, it’s essential to explore whether the benefits outperform the incurred overhead. We compared the energy efficiency and resource efficiency of Bit-balance with Eyeriss[9], Cambricon-X[13], Stripe[16], Laconic[21], and Bitlet[23], achieving $2.7\times$~$11.3\times$, $1.3\times$~$2.8\times$, $3\times$~$5.6\times$, $2.7\times$~$5.4\times$, and $1.8\times$~$2.7\times$ energy efficiency improvement, respectively, as shown in Fig.11, and achieving $3.9\times$~$21\times$, $1.6\times$~$3.9\times$, $1.7\times$~$3\times$, $3.2\times$~$6.3\times$, and $2.1\times$~$3.8\times$ resource efficiency improvement, respectively, as shown in Fig.12. The energy efficiency is calculated as $R_{np}/R_{p}$, where $R_{np}$ and $R_{p}$ represent the ratio of Bit-balance and other baselines in normalized performance and power, respectively. For resource efficiency, the ratio of power, $R_{p}$, is replaced with the ratio of area, $R_{a}$, in the expression of energy efficiency. Since the PE array size of Stripe has been scaled for computing normalized performance, the expression, $R_{np}/R_{a}$ should multiply the ratio of peak performance, $R_{pp}$, representing the throughput per area.
Compared with fixed-point architectures, the MAC units consume more area and power than add-shift units in Bit-balance. For Eyeriss, the PE consists of a MAC unit and some memories, where the MAC unit only accounts for 9% of total area and power, indicating that Eyeriss consumes much more resources and energy for one MAC operation than that in Bit-balance. Noting that we scale the frequency of Eyeriss to 1GHz, the power should be scaled up by $5\times$ while the area remains unchanged. In the best case, we achieve $8.6/(857/(236\times 5))=13.4\times$ energy efficiency and $8.6/(4.99/12.25)=21\times$ resource efficiency improvement in 8-bit precision at VGG-16. For Cambricon-X, it introduces the indexing module for sparse weights processing, accounting for 31% of the total area and 34% of the total power. However, the processing of sparse weights in Bit-balance are similar with dense bit-serial computing, inducing little overhead. Thus, we achieve $1.3\times$~$2.8\times$ energy efficiency and $1.6\times$~$3.9\times$ resource efficiency improvement.

With higher sparsity of weight bits comes higher performance, under the sacrifice of accuracy. To explore the influence of weight-bit sparsity on performance and accuracy, we trained several groups of weights with different maximum NNZBs, as shown in Fig.13 and Fig.14. The top-1 accuracy of float 32-bit precision in AlexNet, VGG-16, ResNet-50, GoogleNet, and Yolo-v3 are 56.5%, 71.6%, 76.1%, 69.8%, and 62.6%, respectively referring to Pytorch[27]. For 16-bit precision, the accuracy loss of each NN without bit-sparsity quantization is only 0~0.2%. Then, we quantized the maximum NNZB to 2~6, achieving $2.67\times$~$8\times$ speedup. In the stage of $N_{nzb\_max}=6$~$4$, the accuracy of all NNs remains stable, with only 0.1%~1.0% loss. At the point of $N_{nzb\_max}=3$, the accuracy of GoogleNet drops about 3.7%. When $N_{nzb\_max}=2$, the accuracy of all NNs precipitously drops. Thus, we chose $N_{nzb\_max}=3$ or $4$ for 16-bit precision in our work.
The phenomenon in 8-bit precision is similar with the 16-bit precision. The 8-bit precision accuracy loss of each NN without bit-sparsity quantization is 0.2%~2.1%. In the stage of $N_{nzb\_max}=7$~$5$, the accuracy holds steady. At the point of $N_{nzb\_max}=4$, the accuracy of AlexNet, ResNet-50, and GoogleNet drops about 1.9%~2.8%. When $N_{nzb\_max}=3$, the accuracy of all NNs precipitously degrades. Thus, we chose $N_{nzb\_max}=4$ or $5$ for 8-bit precision computing.
Though the performance improvement of 8-bit precision is higher than the 16-bit in Bit-balance owing to the adaptive bitwidth computing, there still exits some NNs of specific domains that are more suitable for 16-bit precision to maintain accuracy. For example, the accuracy of Yolo-v3 with 16-bit precision is 2% higher than that of 8-bit precision on average, which is a significant accuracy improvement for NNs. Thus, adaptive bitwidth is essential for sparse bit-serial computing in NN acceleration.

Since Bit-balance processes the weights with encoding format, it induces storage overhead and increases power consumption of DRAM access compared with original weights. To illustrate the benefit of sparse processing in Bit-balance, we compared the energy efficiency of the whole system with basic bit-serial architecture (Bit-balance without sparse processing). The power of DRAM access is estimated with CACTI[28] by the total DRAM access counts and runtime. Based on the dataflow in Section.V, though we consume $1\times$~$1.4\times$ power for $1\times$~$2.4\times$ DRAM access as shown in Fig.15 and Fig.16, the energy efficiency of Bit-balance is still $1.14\times$~$5.3\times$ higher than basic bit-serial architecture owing to $1.6\times$~$5.3\times$ performance improvement as shown in Fig.17.