Mercury: Accelerating DNN Training By Exploiting Input Similarity

DNN operations consist of numerous multidimensional dot products between weight and input vectors extracted from the weight and input matrices. Let us consider a weight vector w and two input vectors $\textbf{v}_{1}=[v_{1,1},v_{1,2},v_{1,3}]$ and $\textbf{v}_{2}=[v_{1,1}+\epsilon_{1},v_{1,2}+\epsilon_{2},v_{1,3}+\epsilon_{3}]$. If $\epsilon_{i}$ (for $1\leq i\leq 3$) represents an insignificant difference, then $\textbf{v}_{1}$ and $\textbf{v}_{2}$ have value similarity. The dot product of $\textbf{v}_{2}$ and w would be $\textbf{v}_{2}\textbf{.w}=\textbf{v}_{1}\textbf{.w}+{\bf\epsilon.w}$. If $\epsilon_{i}\approx 0$, then ${\bf\epsilon.w}\approx 0$, and therefore, $\textbf{v}_{2}\textbf{.w}\approx\textbf{v}_{1}\textbf{.w}$. In other words, if $\textbf{v}_{2}$ and $\textbf{v}_{1}$ have value similarity, the computation of $\textbf{v}_{2}$ with a weight vector is considerably similar to that of $\textbf{v}_{1}$ and, therefore, can be skipped by reusing the results of $\textbf{v}_{1}$.

To further motivate the readers, we analyzed the VGG13 network [55] with ten convolution layers. We counted what fraction of input and gradient vectors have similarities in the convolution layers. The similarity is detected using a well-established technique called Random Projection with Quantization (RPQ) [5] (more details in $\S$ II-A). The similarity in input vectors leads to computation reuse in the forward propagation, while that of gradient vectors leads to computation reuse in the backward propagation. Figure 1 shows that VGG13 has up to $75\%$ similarity among input vectors and up to $67\%$ similarity among gradient vectors. By capitalizing on these similarities, Mercury speeds up the VGG13 training by $1.89\times$ compared to baseline ($\S$ VII-A).

When it comes to DNN inference acceleration, the two dominant techniques are sparsity exploitation [2, 47, 1, 56, 10, 20, 25] and computational reuse [29, 50, 27, 28, 66, 42, 52]. Unfortunately, applying these techniques directly during training has never been easy [41, 40]. Thus, most of the efforts for reducing DNN training time focus on alternative approaches, such as distributed training [19, 43], data compression [65, 31, 22], low precision training [17, 18, 35]. Recently, there is some work about exploiting sparsity in DNN training [41, 40, 62]. Yet the challenges of reusing similar computational data due to input similarity during training are not well-studied. Most of the current work in this category is either software based [45, 46] or limited to inference only [46, 15, 42, 52]. Extending them for training in an accelerator is difficult due to two major challenges.

• •

  Similarity Detection: Detecting similarity among inputs requires extra computations and hardware. Therefore, reducing the computations while reusing the existing hardware as much as possible becomes a major bottleneck for exploiting input similarity.

• •

  Dataflow Modification: When two inputs are similar, computations for one input can be reused for the other. This creates an irregularity in the dataflow of an accelerator. Changing the dataflow or using a new one will vanquish the benefit of the accelerator’s original dataflow. Thus, addressing the irregularity in computations while maintaining the original accelerator dataflow becomes a significant objective for adopting input similarity.

We propose a novel scheme, called Mercury, to exploit input similarity during the training phase in a DNN accelerator. Mercury uses RPQ [5] in hardware to detect similarity among input vectors. We show a formulation of RPQ where it follows the same computation pattern as a convolution operation. Therefore, Mercury reuses the existing hardware Processing Elements (PEs) to perform RPQ. Mercury uses RPQ to convert an input vector into a bit-sequence, called Signature. Mercury calculates one signature for each input vector. If two input vectors produce the same signature, they are significantly similar and thus, have higher similarity. During the DNN operation between a weight and input vector, the input vector’s signature is used to access a special cache, called MCache. MCache uses signatures to calculate indices and tags and (previously) computed results as data. If there is a hit on MCache, the computation is skipped. Instead, the computed result stored in the data-portion of the cache entry is reused. On the other hand, if there is a miss, the computation continues, and the result is stored into MCache. Input similarity introduces irregularity in the original computation pattern of a DNN accelerator by skipping some computations. Mercury adds a bitmap (called Hitmap) and some shared structures to make the dataflow and computations continuous and uninterrupted. The signatures produced during the forward propagation are stored in memory to be reused during the backward propagation of the training phase. Moreover, Mercury dynamically decides when and to what extent input similarity should be exploited based on its impact on performance and accuracy. In summary, we make the following contributions:

1. 1.

   Mercury is the first accelerator to exploit input similarity using RPQ for improving training performance. We propose to adapt Mercury dynamically based on accuracy and performance impact.

2. 2.

   We propose to use RPQ in hardware to detect similarity among input vectors dynamically. We show a novel formulation of RPQ where it follows the same computation pattern as a convolution operation. Therefore, Mercury can calculate RPQ-based signatures using the same hardware PEs and dataflow used for DNN operations. We show how signature calculation can be further pipelined.

3. 3.

   Input similarity causes irregularity in the original computation pattern of an accelerator due to the reuse of computations. We propose to add a cache, MCache, along with a bitmap (Hitmap) and some shared structures to make the dataflow and computations continuous and regular.

4. 4.

   We implemented Mercury in Virtex 7 FPGA board [59]. We showed a scalable implementation of MCache to meet the demand of the Mercury. We evaluated Mercury using twelve DNN models (including a transformer model) with three different dataflows and achieved an average speedup of $1.97\times$ with an accuracy similar to the baseline system.

Random Projection [5] is a dimensionality reduction technique often used in similarity estimation of high-dimensional data (such as image and text). Given a vector, $\mathbf{X}$ of size $1\times m$, random projection works by multiplying $\mathbf{X}$ with a random matrix $\mathbf{R}$ of size $m\times n$. The elements of $\mathbf{R}$ are randomly populated from a normal distribution, whose mean is 0 and variance is 1. The multiplication produces a projected vector $\mathbf{X}_{p}$ of size $1\times n$. Thus, random projection converts one vector to another with a different dimension (often a lower one). Random projection ensures that if two vectors are close (similar) in their original dimension, their projected vectors will also be close (with a Euclidean distance scaled accordingly) in the newer dimension. Elements of $\mathbf{X}_{p}$ can be quantized further. One such quantization approach is sign-based. So, if an element of $\mathbf{X}_{p}$ has a sign bit equal to 0, it is quantized to 0. Otherwise, it is quantized to 1. Thus, RPQ converts $\mathbf{X}$ into a bit sequence, called signature. Figure 2 shows an example of how RPQ converts a vector into a signature. If RPQ converts two vectors, $\mathbf{X}_{1}$ and $\mathbf{X}_{2}$, into the same signature, their Euclidean distance in the new dimension is 0. Therefore, their distance in the original dimension is $\approx 0$. So, $\mathbf{X}_{1}\approx\mathbf{X}_{2}$.

RPQ has been used in many domains such as learning [24], compression [8], etc. To provide insight into how RPQ behaves, we conducted an experiment with ten randomly generated unique vectors of dimension $10$. We generated ten more similar vectors from each of the vectors (by adding some random $\epsilon$ to each dimension). We generate signatures of all vectors and compare them with each other to determine how many unique vectors we can find. Since we started with ten unique vectors, a comparison should find a similar number of unique vectors. Figure 3 shows the number of unique vectors found by RPQ. It also shows results with another technique, Bloom Filter [6],  [7]. For smaller signatures, both methods declare many dissimilar vectors as similar. However, RPQ is able to detect unique vectors better than Bloom Filters at longer signatures.

A typical DNN accelerator is shown in Figure 4. The accelerator has a number of hardware PEs. Each PE has vertical and horizontal connections with neighboring PEs using on-chip networks. There is a global buffer to hold inputs, weights, and partial-sums. The chip is connected to off-chip memory to receive inputs and store outputs. Each PE contains registers to hold inputs, weights, and partial sums. Each PE also contains multiplier and adder units. Each PE distributes inputs and weights and generates partial sums based on a dataflow.

Different dataflows have been proposed in literature [11, 10, 37] to optimize different aspects of the DNN operations. Examples are Weight-Stationary, Output-Stationary, Input-Stationary, and Row-Stationary. The dataflow name often reflects which data is kept unchanged in the PE unit throughout the computation. In Weight-Stationary, each PE statically holds a weight inside its register file. Those operations that use the same weight are mapped to the same PE unit [11]. Output-Stationary [49] localizes the partial result accumulation inside each PE unit. For Row-Stationary, each PE processes one row of the input. Filter weights stream horizontally, input rows stream diagonally, and partial sums are accumulated vertically. Row-Stationary has been proposed in Eyeriss [10] and is considered one of the most efficient dataflows for reuse.

Eyeriss [10] used row stationary dataflow for inference. However, it can be easily extended for training. During the back propagation, each layer performs two computations - one for the weight update and the other for calculating the gradient of the inputs. Consider a convolution between the input of dimension $H\times W$ and the weight of dimension $k_{1}\times k_{2}$. This results in an output of size $(H-k_{1}+1)\times(W-k_{2}+1)$. For simplicity, let us assume that there is one channel in the input and output. We can easily update the equations with more channels. For updating weights, we measure $\frac{\partial{E}}{{\partial{w_{m^{\prime},n^{\prime}}^{l}}}}$ which is interpreted as how changing a single-point $w_{m^{\prime},n^{\prime}}$ of the weight affects the loss function $E$.

In this equation 1, $\delta_{i,j}^{l}$, and $O_{i+m^{\prime},j+n^{\prime}}^{l-1}$ represent the gradients of outputs in layer $l$ and outputs of layer $l-1$ respectively. Equation 1 shows that for calculating the gradient of weights in layer $l$, the convolution between gradients of outputs in layer $l$ and outputs of layer $l-1$ is needed. Similar to inference, this convolution can be done with row-stationary dataflow. For the second computation of the back propagation, we compute $\frac{\partial{E}}{{\partial{x_{i^{\prime},j^{\prime}}^{l}}}}$, which can be interpreted as how changing in a single- point $x_{i^{\prime},j^{\prime}}$ of the input feature map affects the loss function $E$. As shown in Figure 5, we can see that the output region affected by point $x_{i^{\prime},j^{\prime}}$ of the input is the output region bounded by the dashed lines where the top left corner point is given by $(i^{\prime}-k_{1}+1,j^{\prime}-k_{2}+1)$ and the bottom right corner point is given by $(i^{\prime},j^{\prime})$. Based on this figure, the gradient of input $x_{i^{\prime},j^{\prime}}$ can be calculated as:

The first part of this equation 2 contains the convolution operation between gradients of layer $l+1$ and weights of layer $l+1$. This is $\sum_{m=0}^{k_{1}-1}\sum_{n=0}^{k_{2}-1}\delta_{i^{\prime}-m,j^{\prime}-n}^{l+1}w_{m,n}^{l+1}$, and the second part is the partial derivative of the activation function. So, similar to inference, we can also use the row-stationary dataflow for this part of back propagation. We can pad the gradient matrix by zeros for pixels in corners to have a generic formula for all pixels. Thus, we can use the row-stationary dataflow for training as it contains similar computations as the inference.

UCNN [29] exploits weight repetitions in a CNN model. At the core of UCNN is the factorized dot product dataflow and activation group reuse. SumMerge extends the idea of UCNN into CPU-based implementation [50]. TensorDash [41] accelerates DNN training by skipping ineffective multiply-accumulate (MAC) computation.Eager-Pruning [64] speeds up training by detecting and pruning insignificant weights early.

DeepReuse [46] and Adaptive Deep Reuse (ADR) [45] exploit similarity in inputs to improve inference and training performance, respectively. The scope of both approaches is limited to software implemented CNN models. Both approaches use Locality Sensitive Hashing (LSH) to find the similarity among input vectors. Although Mercury shares some similarities with ADR at a high level, ADR cannot be directly implemented in hardware because of the following issues. First, the use of LSH requires a computationally expensive pre-processing step to build clusters and determine the centroids. This step is not trivial to do in a hardware accelerator. That is why Cicek et al. [14] proposed to design a separate accelerator just for detecting input similarities and interface it with a CNN accelerator to improve the inference performance. Second, ADR interleaves LSH calculations with convolution operations to determine if some result is already computed or not. Such interleaving of operations in an accelerator will interfere with its original dataflow, thereby reducing the potential benefit of computational similarity. Thanks to our formulation of RPQ as a convolution operation ($\S$ III-B1), additional calculations for detecting input similarities blend in with the original operations without interfering with the accelerator’s dataflow. Furthermore, due to the use of Hitmap along with some extra hardware resources, the reuse of already computed results does not modify the dataflow either.

Diffy [42] and Riera et al. [52] propose to exploit similarity in pixelated or streaming video to accelerate DNN inference. Both approaches use element-wise comparison to detect similar elements. This is inefficient since the comparison either needs to be done serially over all elements or only within a limited number of neighboring elements. Recently, Servais et al. [53] exploit similarity in consecutive rows or columns of inputs and weights for CNN training. Unlike prior approaches, Mercury uses a well established hashing technique, RPQ, to check similarity at vector granularity across all vectors in constant time. RPQ is hardware-friendly and can be easily used in both forward and backward propagation. Moreover, unlike Mercury, prior approaches require a new dataflow in the accelerator and cannot be used on top of an existing dataflow. Another line of work looks at redundancy in training data. However, Mercury is orthogonal to that approach and can be applied on top of it [4], [16], [23], [33], [34], [36], [44], [57], [63].

Mercury works on vectors extracted from multidimensional inputs. The overview of Mercury is shown in Figure 6. First, Mercury determines which input vectors are similar. This is done before the input vectors are multiplied with weight vectors. Mercury calculates an RPQ-based signature for an input vector by multiplying the vector with a random projection matrix followed by quantization. Mercury formulates signature calculation as a convolution operation and reuses the same hardware PEs with the original dataflow. Mercury generates one signature for each input vector. If two signatures are identical, the corresponding vectors are similar. Therefore, the computed dot product between one of the input vectors and a weight vector can be reused for that of the other input vector and the same weight vector. Mercury uses a cache, called MCache, to store computed results corresponding to different signatures. A Hitmap keeps track of the signatures that cause a hit. When Mercury performs a dot-product between an input vector and a weight vector (or derivatives during the backward propagation), Mercury checks if this vector is similar to any prior vector using the Hitmap; if so, the result stored in MCache is reused. Mercury stores the signatures calculated during the forward propagation and reuses them during the backward propagation to skip similar computations. As the training proceeds, Mercury increases signature length to adjust to the extent of similarity among vectors. Only vectors with a higher degree of the similarity are allowed to reuse computed results in the later stages of training. Thus, Mercury dynamically adjusts computation reuse to keep accuracy degradation insignificant.

Next we will elaborate on Mercury operations. We choose row-stationary [10] dataflow as our baseline ($\S$II-C shows how it can support training). We will first explain how Mercury works in this baseline accelerator. Then, we will discuss how other dataflows are supported.

Mercury detects similarity dynamically among input vectors before performing any operation with weights. To simplify hardware and keep dataflow the same, Mercury formulates signature calculation as a convolution operation, where the convolution is performed between the input vectors and some random projection matrix. This is done every time there is a new set of input vectors (e.g., when a new channel is processed). When the actual filters of a channel are convoluted with the input vectors, signatures are used to determine if similar dot products are already computed.

Here, we explain how signatures along with MCache can be utilized to skip similar computations in the forward propagation followed by the backward propagation. We will first explain it for a convolution layer ($\S$ III-C1 & III-C2). In $\S$ III-C3 and$\S$ III-C4, we will address it for other layers.

As training proceeds, DNN models become more sensitive to computation reuse. So, we propose Mercury to be adaptive.

Increase in Signature Length: If signature length increases, vectors ${\bf v_{1}}$ and ${\bf v_{2}}$ are found to have similarity only when ${\bf v_{1}-v_{2}=\epsilon}$ becomes significantly smaller. So, a larger signature has a lesser effect on model accuracy but it may reduce computation reuse. Therefore, Mercury starts with a smaller signature size (e.g., 20 bits long) and progressively increases signature length as the model is trained more. Towards this end, Mercury calculates the average loss in each iteration during training. If there is no change in the loss for $K$ consecutive iterations, then Mercury increments signature length by 1.

Stoppage of Similarity Detection: Mercury analytically determines if detecting similarity can save computations or not. If no computation can be saved, then Mercury turns off the similarity detection phase. In order to implement this, Mercury records the total computation cost (i.e., cycles) $C_{S}$ for signature generation in forward and backward propagation when some computations are reused. This cost is compared with the total computation cost $C_{B}$ of the baseline system without any computation reuse. $C_{B}$ can be calculated analytically using different hardware components’ latency. If the former cost is more than the later for $T$ consecutive batches of inputs, Mercury stops generating signatures.

Figure 13 shows the impact of Mercury on the models’ accuracy. Overall, there is a $0.7\%$ reduction in validation accuracy¹¹1Hyper-parameters are adjusted in training to achieve optimal accuracy. Considering the inherent randomness during the training process, we argue that Mercury’s accuracy is comparable to the baseline system. Also, we got the same bleu_score of $33.52$ on test data for the transformer.

Figure 14(a) shows the adaptivity of Mercury across different models. Based on the similarity detection costs in layers and the overall performance during the model training, Mercury may turn off similarity detection in some layers during the training. Figure 14(b) shows the computational cycle breakdown of Mercury and baseline. This cycles includes computation cycles of convolutional, fully connected, and attention layers as well as signature calculation. Most of the cycles belong to the layer computations. The signature computation accounts for only a fraction of the total cycles. Overall, Mercury can reduce the total computation time by about $50\%$, which results in an average speedup of $1.97\times$, as shown in Figure 14(c). For bigger networks, such as ResNet152, VGG19, and Inception-V4, there are more saving opportunities since there are more chances of similarity between vectors.

We conduct a detailed analysis of VGG13 to show how Mercury works at runtime, focusing on the characterization of the MCache access, the savings, and the number of unique vectors found across layers. The results are shown in Figure 15. Figure 15(a) shows a gradual increase in MCache Hit and MAU percentage due to the reduction in the number of input vectors and cache occupants. Figure 15(b) shows that the computational cycles may vary across layers of VGG13 due to the difference in layers’ size and channels. Some layers have a higher cycle count related to the input size and number of input and output channels, and the amount of savings differs. The number of unique vectors is also different across layers. As shown in Figure 15(c), the first few layers have the highest number of unique vectors since they have a large input size. This value is lower for the later layers due to the smaller input size.

This section analyzes the impact of different MCache sizes and organizations on the performance of Mercury. As shown in Figure 16, Mercury performance increases with cache size and associativity. Unfortunately, Vivado did not finish synthesis of 32-way cache-based designs even after one day (our time limit for the server). Thus, we had to limit ourselves to 8 or 16-way. Combining with Table IV shows that moving from a 512-entry, 8-way to a 1024-entry, 16-way cache only increases the power consumption by $2.85\%$ while giving $4.88\%$ more speed up. Doubling the cache size to $2048$ entries gives insignificant performance gains; thus, $1024$-entry and $16$-way is selected as the default configuration for MCache.

Figure 18(a) and 18(b) show the speedup of our scheme when deployed on top of the Input-Stationary and Weight-Stationary dataflow. For Input-Stationary, Mercury gives an average performance gains of $1.55\times$ over the baseline. The maximum speedup of $1.72\times$ is achieved in VGG-19. Mercury works better with Weight-Stationary as it achieves an average speedup of $1.66\times$ over the baseline. The maximum speedup of $1.89\times$ is observed in ResNet101.

In this section, we provide a detailed analysis of the resource usage and power consumption of Mercury implementation on the Virtex 7 FPGA board. Table IV compares the resource usage and on-chip power consumption of Mercury for different MCache sizes. Specifically, quadrupling the number of MCache sets only increases the overall power consumption by $6.5\%$. If we fix the number of sets to $64$ and increase the number of ways from $2$ to $16$, the power consumption increases by $3.98\%$, as shown in Table IV. This result indicates that Mercury design can work with different sizes of cache and various number of ways with reasonable overhead. As shown in Table IV, Mercury increases resource usage and the power consumption by $1.135\times$. The majority of this increment is related to the power of Signals and Logic which is the result of using adaptable cache-based structure in the proposed design. However, as explained in $\S$ V, since we fixed the cache size and number of ways to an optimal value, the Mercury resource consumption will be almost the same even if we increase the size of input images and number of PEs.