---
author:
- 'James Garland and David Gregg, Trinity College Dublin'
title: |
    Low Complexity\
    Unit for Weight-Sharing\
    s
---

neural networks require large amounts of computation and weight data that stretch the limited battery, computation and memory in mobile systems. Researchers have proposed hardware accelerators for that include many parallel hardware multiply-accumulate units.

training involves incrementally modifying the numeric “weight” values associated with connections in the neural network. Once training is complete, there are no further updates of the weight values, and the trained network can be deployed to large numbers of embedded devices. Han [@DeepCompression:Han; @eie:Han] found that similar weight values can occur multiple times in a trained . By binning the weights and retraining the network with the binned values, they found that just 16 weights were sufficient in many cases. They encode the weights by replacing the original numeric values with a four-bit index that specifies which of the 16 shared weights should be used. This greatly reduces the size of the weight matrices.

We propose a novel circuit design aimed specifically at hardware accelerators for that use weight sharing. Rather than performing the operation directly, we instead count the frequency of each weight and accumulate the corresponding image value in a bin. This allows the hardware multiplier in the to be replaced with counting and selection logic. After accumulation, the accumulated image values in the bins are then multiplied with the corresponding weight value of that bin. Where the number of bins is small, the counting and selection logic can be significantly smaller than the corresponding multiplier.

Background {#subsec:background}
==========

The most computationally-intensive part of a is the multi-channel convolution. Fig. \[fig:covCode\] shows pseudo-code for the main loop of the 2D multi-channel convolution operator. The input of the operator consists of an image with many (often 256 or 512 [@GoingDeeperWithConv:szegedy]) channels, which is combined with a large number of kernels to create an output image, again with many channels. The innermost loops can be implemented with a hardware and accelerators for commonly include a large number of parallel [@OptimizingFpgaAccelForCNN:Zhang].

``` {.vhdl language="VHDL" basicstyle="\footnotesize" breaklines="true"}
input[width][height][input_channels];
kernels[output_channels][K][K][input_channels];
output[width][height][output_channels];
for w in 1 to width
  for h in 1 to height
    for o in 1 to output_channels {
      sum = 0;
      for x in 1 to K
        for y in 1 to K
          for i in 1 to input_channels
            sum += input[w+x][h+y][i] *
                           kernels[o][x][y][i];
      output[w][h][o] = sum;
    }
```

A simple unit is a sequential circuit that accepts a pair of numeric values, computes their product and accumulates the result. The accumulator register is typically located within the to reduce routing complexity and delays. When one of the inputs to the is encoded using weight sharing, an extra level of indirection is required. Fig. \[fig:weightSharedRegFileAndMaccBlockDiagram\] shows a simplified version of weight sharing decode with a single . The weights in the are represented by, for example, a 4-bit number which is an index to a table of 16 shared weight values.

![Simple showing how pre-trained ***weight*** values are stored in a weights register file. Values are indexed and retrieved by ***binIndex*** and multiplied by the corresponding ***image*** value.[]{data-label="fig:weightSharedRegFileAndMaccBlockDiagram"}](weightSharedRegFileAndMaccBlockDiagram){width="1\linewidth"}

The most common computation in a is multiply-accumulate. Hardware accelerators for may contain dozens, hundreds or even thousands of units. However, each unit is a relatively expensive piece of hardware consuming large floor area (i.e. large numbers of gates) and power in an . Hardware accelerators for typically use 8-, 16-, 24- or 32-bit fixed point arithmetic [@Eyeriss:Chen]. A combinatorial $w$-bit multiplier requires $O(w^2)$ logic gates to implement which makes up a large part of the unit. Note that sub-quadratic multipliers are possible, but are inefficient for practical values of $w$ [@FastIntegerMultiplication:Furer].

The *gates* column of Table \[table:complexity\] shows the circuit complexity in gates of each sub-component, assuming fixed-point arithmetic. The bit-width of the data is $w$ and the number of bins is $b$ in the weight-shared designs. For example, a simple unit contains an adder ($O(w)$ gates) a multiplier ($O(w)^2$) gates) and a register ($O(w)$ gates). A weight shared also needs a small register file with $b$ entries to allow fast mapping of encoded weight indices to shared weights. The is our novel weight-shared unit which is described in Section \[sec:approach\].

  --------------- ---------- -------- --------------- -----
  Sub Component     Gates     Simple   Weight Shared   PAS
                               MAC          MAC       
  Adder             $O(w)$      1            1          1
  Multiplier       $O(w^2)$     1            1        
  Register          $O(w)$      1           $b$        $b$
  Register                                            
  File Port        $O(wb)$                   1          2
  --------------- ---------- -------- --------------- -----

  : Complexity of , Weight-shared and

\[table:complexity\]

Approach {#sec:approach}
========

We propose to reduce the area and power consumption of the by re-architecting the to do the accumulation first followed by a shared post-pass multiplication. Rather than computing the in the directly, we instead count how many times each of the $b$ weight indexes appears and store the corresponding image value in a register bin. For example, if the shared weight with index $2$ had the value $19$ and were multiplied and accumulated with the image value $25$, then a weight-sharing would compute $19 \times 25=475$ and add this value to the accumulator. Instead we keep $b$ separate accumulators, one for each weight value. If we encounter the shared weight with index $2$, value $19$ and image value $25$, then rather than performing any multiplication, we instead add $25$ to accumulator number $2$ in the local $b$-entry register file. Storing this result in a register file that is local the unit reduces unnecessary data movement.

Our Parallel Accumulate and Store () unit represents the sum as an unevaluated sum of a set of coefficients of each of the $b$ weights (see Fig. \[fig:pasmBlockDiagram\]). The system computes the dot product by computing the total of how many of each of the weights appear in the sum. This turns the multiply-accumulate step into an array-index-and-add operation.

To compute the final dot product value the final of weights and their respective frequencies is calculated using a standard unit. We refer to this combination of a and as a . The post-pass requires just $b$ multiplications whereas the standard dot product needs as many multiplications as there are inputs. With far fewer multiplications needed, one post-pass unit can be shared between several units.

The proposed in Fig. \[fig:pasmBlockDiagram\] stores the $w$ bit ***image*** values in corresponding $b$ weight-bin registers indexed by the ***binIndex*** signal. The has two phases: (1) to accumulate the image values into the weight bins (known as the ) and (2) to multiply the binned values with the weights (completing the ).

Fig. \[fig:pasPhase\] shows how ***image*** value $26.7$ is accumulated into bin $0$ indexed by ***binIndex***. Next $3.4$ is accumulated into bin $1$. This continues until finally accumulating $6.1$ into bin $0$ to give $26.7+6.1=32.8$.

Fig. \[fig:mulPhase\] demonstrates the multiply phase, multiplying and accumulating bin $0$ ***pretrained weight*** with bin $0$ accumulated ***image*** value, giving $32.8\times1.7=55.76$. The contents of ***pretrained weight*** bin $1$ in multiplied and accumulated with ***image*** value in bin $1$ and so on until all the corresponding bins are multiplied and accumulated into the ***result*** register, giving $98.8$.

The latter stage can be implemented on a unit that is shared between several units. units can be replaced by units and a number of units share a single . Due to its parallel nature, the can have higher throughput for known sets of weights when compared to the standard .

![Multiple--Shared- showing units followed by a shared to multiply and accumulate ***weights*** with binned ***image*** values from bins for a bit width $w$ and a $wci$ ***binIndex*** indexing into the $b$ weight-bin register. The accumulation phase accumulates ***image*** values against a ***binIndex*** representing how often the corresponding weight appears. The post-pass multiply-accumulate phase would multiply the weights with binned image values indexed by ***binIndex***.[]{data-label="fig:pasmBlockDiagram"}](pasmBlockDiagram){width="1\linewidth"}

![Phase 1: As each image value is streamed in, its associated bin index is also streamed so that the image values can be accumulated into the correct bins.[]{data-label="fig:pasPhase"}](pasComplete){width="0.60\linewidth"}

![Phase 2: Each accumulated value in each bin is multiplied with its corresponding pretrained weight value to produce the final equivalent result.[]{data-label="fig:mulPhase"}](pasmComplete){width="0.55\linewidth"}

Of course, from Table \[table:complexity\], the is only efficient in a weight shared . If this weight-shared accumulate-shared-multiply system were used in a standard then the number of the weight-bin registers would be prohibitive.

Table \[table:channelsKernelsMatrix\] shows each sequence of operations will consist of $k\times k\times c$ inputs (see lines 10 - 13 of Fig. \[fig:covCode\]). For example, if $b=16$ bins is used for $k=5\times5$ kernels and $c=32$ channels, then 800 accumulations and 16 multipliers (one for each bin) would be required to do the accumulate and multiply. If $b=16$ bins is used, the overhead of the final accumulation is minimal for large numbers of kernels and channels. Careful consideration of the size of bins used with respect to the number of channels and kernels is important due to the $sum$ being multiply-accumulated $i$ many times before the $output$ is updated as can be seen on lines 10 - 13 of Fig. \[fig:covCode\].

[cllll]{} & &\
& & & &\
& & & &\
& & & &\
& & & &\
& & & &\

\[table:channelsKernelsMatrix\]

Evaluation {#sec:evaluation}
==========

We designed a multi-channel, multi-kernel convolution accelerator unit to perform a simplified version of the accumulations in Fig. \[fig:covCode\]. Our accelerator accepts 4 image inputs and 4 shared-weight inputs each cycle, and uses them to compute 16 separate operations each cycle. The standard version performs these operations on 16 weight-shared units (16-). Our proposed unit (16--4-) has 16 units and uses 4 units for post-pass multiplication. Both are coded in Verilog 2001 and synthesized to a flat netlist at 100MHz with a short 0.1ns clock transition time targeted at a 45nm process . We measure and compare the timing, power and gate count in both designs for the same corresponding bit widths and same numbers of weight bins.

The standard 16- and the proposed 16--4- each have $w$ bit ***image*** and ***weight*** inputs and the 16--4- has a $wci$ bit ***binIndex*** input to index into the $b=2^{wci}$ weight bins. The designs are coded using integer/fixed point precision numbers. Both versions are synthesized to produced a gate level netlist and timing constraints designed using [@FpgaXdcTiming:Gangadharan] so that both designs meet timing at 100MHz.

Cadence Genus (version 15.20 - 15.20-p004\_1) is used for synthesizing the into the OSU FreePDK 45nm process and applying the constraints in order to meet timing. Genus supplies commands for reporting approximate timing, gate count and power consumption of the designs at the post synthesis stage. The “report timing”, “report gates” and “report power” of Cadence Genus are used to obtain the results for both and designs. Graphs of the gate count and power consumption results are produced for the two different designs at different bit widths and different numbers of weight bins, showing that the is consistently smaller and more efficient than the weight-sharing .

Fig. \[fig:asicUtilizationComparisonWidth\] shows comparisons of the logic resource requirements of a $b=16$ shared-weight-bin 16--4- and 16- for varying $w$ bit widths. Gate counts are normalised to a NAND2X1 gate. The uses significantly fewer logic gates. For example, for $w=32$ bits wide the 16--4- is 35% smaller in sequential logic, 78% smaller in inverters, 61% smaller in buffers and 68% smaller in logic, an overall 66% saving in total logic gates. The requires more accumulators for the $b$-entry register file, but otherwise overall resource requirements are significantly lower than that of the .

![Logic gate count comparisons (in NAND2X1 gates) for $w=4, 8, 16, 32$ bits wide 16- and 16--4- for $b=16$ weight bins - **lower is better** []{data-label="fig:asicUtilizationComparisonWidth"}](16binDeepUtilizationWidthComparison){width="1\linewidth"}

Fig. \[fig:asicTotalDynamicPowerComparisonWidth\] shows comparisons of power consumption of the designs. 16--4-’s power is lower than the weight-shared 16- and the gap grows with increasing $w$ bit width. For example, for the $w=32$ bit versions of each design, the 16--4- consumes 60% less leakage power, 70% less dynamic power and 70% less total power than that of the 16-.

![Power consumption (in W) comparisons for $w=4, 8, 16, 32$ bits wide 16- and 16--4- for $b=16$ weight bins - **lower is better** []{data-label="fig:asicTotalDynamicPowerComparisonWidth"}](16binDeepPowerWidthComparison){width="1\linewidth"}

Fig. \[fig:asicUtilizationComparisonDepth\] shows the effect of varying the number of bins from $b=4$ to $b=256$, with gate counts normalised to a NAND2X1. For bit width $w=32$ and $b=16$ bins the 16--4- utilization has 35% fewer sequential gates, 78% fewer inverters, 62% fewer buffers and 69% fewer logic and 66% less total logic gates compared to the 16- design. However, at $b=256$, registers and buffers are less efficient than the .

![Logic gate counts comparisons (in NAND2X1 gates) for $b=4, 16, 64, 256$ weight bins for a 16- and 16--4- for $w=32$ bit width - **lower is better** []{data-label="fig:asicUtilizationComparisonDepth"}](32bitWideUtilizationDepthComparison){width="1\linewidth"}

The 16--4- also consumes 61% less leakage power, 70% less dynamic power and 70% less total power (Fig. \[fig:asicTotalDynamicPowerComparisonDepth\]).

![Power consumption (in W) comparisons for $b=4, 16, 64, 256$ weight bins deep 16- and 16--4- for $w=32$ bit width - **lower is better** []{data-label="fig:asicTotalDynamicPowerComparisonDepth"}](32bitWidePowerDepthComparison){width="1\linewidth"}

We also experimented with implementing the designs on a Xilinx Kintex Ultrascale however, for larger values of $b$ bins, such as $b=64$ and $b=256$, our approach quickly becomes inefficient.

The weight-shared introduces a delay in the processing the output of the units. The unit has a throughput of one pair of inputs per cycle, and so computes the initial accumulated values in about $n$ cycles. The post pass unit also has a throughput of one pair of inputs per cycle, so requires a cycle for each of the $b$ accumulator bins, for a total of $n+b$ cycles. In contrast a simple unit requires just $n$ cycles.

Whilst more parallelism of standard could be applied to accelerate a , these parallel would consume more power and area that that of our parallel and shared .

Future improvements should include placing and routing the and designs to a fully routed test chip. Back annotated gate level simulations should be executed on the final netlist to obtain design toggle rates and applied to the power reporting tool. The placement and routing impacts and simulation toggle rates shall increase the power analysis accuracy comparisons of the designs.

Related Work {#sec:relatedWork}
============

Other research groups have proposed numerous hardware accelerators for in both [@limitedNumericalPrecision:Gupta; @OptimizingFpgaAccelForCNN:Zhang] and [@DianNao:Chen]. Gupta [@limitedNumericalPrecision:Gupta] show increased efficiency in a hardware accelerator of a 16-bit fixed-point representation using stochastic rounding without loss of accuracy. Zhang [@OptimizingFpgaAccelForCNN:Zhang] deduce the best accelerator taking requirements into consideration and then implement the best on an to demonstrate high performance and throughput. Chen [@DianNao:Chen] design an accelerator for large scale focussing on the impact of memory on the accelerator performance.

Chen [@Eyeriss:Chen] address the problem of data movement which consumes large amounts of time and energy. They focus on data flow in the to minimize data movement by reusing weights within the hardware accelerator to improve locality. This was implemented in and power and implementation results compared showing the effectiveness of weight reuse in saving power and increasing locality.

Han [@eie:Han] have proposed an Efficient Inference Engine which builds on their ‘Deep compression’ [@DeepCompression:Han] work to perform inferences on the deeply compressed network to accelerate the weight-shared matrix-vector multiplication. This accelerates the classification task whilst saving energy when compared to or implementations.

Both weight sharing [@DeepCompression:Han; @eie:Han] and weight reuse [@Eyeriss:Chen] reduce redundant data movement through different but complementary approaches. This paper builds on these ideas to reduce the circuit complexity of the underlying units.

Conclusion {#sec:conclusion}
==========

In this paper we propose a novel low-complexity unit to exploit weight-sharing in accelerators. The gate count and area for the 16--4- is significantly lower when compared with the 16-. We also found better power efficiency with the 16--4-. accelerators can contain hundreds or thousands of units. We believe that our reduced-complexity design offers the possibility of adding more parallel units to hardware accelerators within a given clock speed, logic area and power budget.

[1]{} \[sec:bibliography\] T. Chen, Z. Du, N. Sun, J. Wang, C, Wu, Y. Chen, *DianNao: A Small-Footprint High-Throughput Accelerator for Ubiquitous Machine-Learning*: ASPLOS, 2014. Y. Chen, J. Emer, V. Sze, *Eyeriss: A Spatial Architecture for Energy-Efficient Dataflow for Convolutional Neural Networks*: IEEE International Solid-State Circuits Conference (ISSCC), 2016. M. F[ü]{}rer, *Faster Integer Multiplication*: ACM Symposium on Theory of Computing, June 11–13, 2007, San Diego, California, USA S. Gangadharan, S. Churiwala, *Constraining Designs for Synthesis and Timing Analysis - A Practical Guide to Synopsys Design Constraints (SDC)*: Springer, 2013. S. Gupta, A. Agrawal, K. Gopalakrishnan, P. Narayanan, *Deep Learning with Limited Numerical Precision*: CoRR, vol. abs/1502.02551, 2015. S. Han, X. Liu, H. Mao, J. Pu, A. Pedram, M. Horowitz, W. Dally, *EIE: Efficient Inference Engine on Compressed Deep Neural Network*: S. Han, H. Mao, W. Dally, *Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding*: ICLR, 2016. C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, A. Rabinovich, , *Going Deeper with Convolutions*: CVF, 2015. C. Zhang, P. Li, G. Sun, Y. Guan, B. Xiao, J. Cong, *Optimizing FPGA-based Accelerator Design for Deep Convolutional Neural Networks*: ACM, 2015.
