summaries: There has been a lot of work on limited precision training and inference for deep learning hardware, but in most of this work, the accumulators for the multiply-and-add (FMA) operations that occur for inner products are chosen conservatively or treated as having unlimited precision. The authors address this with  an analytical method to predict the number of mantissa bits needed for partial summations during the forward, delta and gradient computation ops for convolutional and fully connected layers. They propose an information theoretic approach to argue that by using fewer bits of mantissa in the accumulator than necessary, the variance of the resulting sum is less than what it would have been if sufficient bits of mantissa were used. This is surprising to me, as quantization is usually modeled as _adding_ noise, leading to an _increase_ in variance (Mc Kinstry et al. 2018), so this is a nice counterexample to that intuition. Unfortunately the result is presented in a way that implies the variance reduction is what causes the degradation in performance, while obviously (?) it's just a symptom of a deeper problem. E.g., adding noise or multiplying by a constant to get the variance to where it should be, will not help the network converge. The variance is just a proxy for lost information. The authors should make this more clear. The authors conduct a thorough analysis of the numeric precision required for the accumulation operations in neural network training. The analysis is based on Variance Retention Ratio (VRR), and authors show the theoretical impact of reducing the number of bits in the floating point accumulator. And through extensive benchmarks with popular vision models, the authors demonstrate the practical performance of their theoretical analysis.
abstractText: Efforts to reduce the numerical precision of computations in deep learning training have yielded systems that aggressively quantize weights and activations, yet employ wide high-precision accumulators for partial sums in inner-product operations to preserve the quality of convergence. The absence of any framework to analyze the precision requirements of partial sum accumulations results in conservative design choices. This imposes an upper-bound on the reduction of complexity of multiply-accumulate units. We present a statistical approach to analyze the impact of reduced accumulation precision on deep learning training. Observing that a bad choice for accumulation precision results in loss of information that manifests itself as a reduction in variance in an ensemble of partial sums, we derive a set of equations that relate this variance to the length of accumulation and the minimum number of bits needed for accumulation. We apply our analysis to three benchmark networks: CIFAR-10 ResNet 32, ImageNet ResNet 18 and ImageNet AlexNet. In each case, with accumulation precision set in accordance with our proposed equations, the networks successfully converge to the single precision floating-point baseline. We also show that reducing accumulation precision further degrades the quality of the trained network, proving that our equations produce tight bounds. Overall this analysis enables precise tailoring of computation hardware to the application, yielding areaand power-optimal systems.
authors.name: Charbel Sakr
authors.name: Naigang Wang
authors.name: Chia-Yu Chen
authors.name: Jungwook Choi
authors.name: Ankur Agrawal
authors.name: Naresh Shanbhag
authors.name: Kailash Gopalakrishnan
references.authors: A.M. Castaldo R.C. Whaley A.T. Chronopoulos
references.title: Reducing floating point error in dot product using the superblock family of algorithms
references.venue: SIAM journal on scientific computing, 31(2):1156–1174.
references.authors: Chen C.-Y. J. Choi K. Gopalakrishnan V. Srinivasan S. Venkataramani
references.title: Exploiting approximate computing for deep learning acceleration
references.venue: Design, Automation, Test in Europe Conference Exhibition (DATE).
references.authors: X. Gastaldi
references.title: Shake-shake regularization
references.venue: arXiv preprint arXiv:1705.07485.
references.authors: X. Glorot Y. Bengio
references.title: Understanding the difficulty of training deep feedforward neural networks
references.venue: Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 249–256.
references.authors: P. Goyal P. Dollár R. Girshick P. Noordhuis L. Wesolowski A. Kyrola A. Tulloch Y. Jia K. He
references.title: Accurate, large minibatch sgd: training imagenet in 1 hour
references.venue: arXiv preprint arXiv:1706.02677.
references.authors: S. Gupta A. Agrawal K. Gopalakrishnan P. Narayanan
references.title: Deep learning with limited numerical precision
references.venue: International Conference on Machine Learning, pages 1737–1746.
references.authors: S. Han H. Mao W.J. Dally
references.title: Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding
references.venue: arXiv preprint arXiv:1510.00149.
references.authors: S. Han J. Pool J. Tran W. Dally
references.title: Learning both weights and connections for efficient neural network
references.venue: Advances in neural information processing systems, pages 1135–1143.
references.authors: K. He X. Zhang S. Ren J. Sun
references.title: Delving deep into rectifiers: Surpassing human-level performance on imagenet classification
references.venue: Proceedings of the IEEE international conference on computer vision, pages 1026–1034.
references.authors: N.J. Higham
references.title: The accuracy of floating point summation
references.venue: SIAM Journal on Scientific Computing, 14(4):783–799.
references.authors: I. Hubara M. Courbariaux D. Soudry R. El-Yaniv Y. Bengio
references.title: Binarized neural networks
references.venue: Advances in neural information processing systems, pages 4107–4115.
references.authors: U. Köster T. Webb X. Wang M. Nassar A.K. Bansal W. Constable O. Elibol S. Gray S. Hall L Hornof
references.title: Flexpoint: An adaptive numerical format for efficient training of deep neural networks
references.venue: In Advances in Neural Information Processing Systems,
references.authors: D. Lin S. Talathi S. Annapureddy
references.title: Fixed point quantization of deep convolutional networks
references.venue: International Conference on Machine Learning, pages 2849–2858.
references.authors: J.L. McKinstry S.K. Esser R. Appuswamy D. Bablani J.V. Arthur I.B. Yildiz D.S. Modha
references.title: Discovering low-precision networks close to full-precision networks for efficient embedded inference
references.venue: arXiv preprint arXiv:1809.04191.
references.authors: T.G. Robertazzi S.C. Schwartz
references.title: Best “ordering” for floating-point addition
references.venue: ACM Transactions on Mathematical Software (TOMS), 14(1):101–110.
references.authors: C. Sakr Y. Kim N. Shanbhag
references.title: Analytical guarantees on numerical precision of deep neural networks
references.venue: International Conference on Machine Learning, pages 3007–3016.
references.authors: N. Wang J. Choi D. Brand Chen C.-Y. K. Gopalakrishnan
references.title: Training deep neural networks with 8-bit floating point numbers
references.venue: Advances in neural information processing systems.
references.authors: B. Widrow I. Kollár
references.title: Quantization noise
references.venue: Cambridge University Press, 2:5.
references.authors: S. Wu G. Li F. Chen L. Shi
references.title: Training and inference with integers in deep neural networks
references.venue: arXiv preprint arXiv:1802.04680.
references.authors: S. Zhou Y. Wu Z. Ni X. Zhou H. Wen Y. Zou
references.title: Dorefa-net: Training low bitwidth convolutional neural networks with low bitwidth gradients
references.venue: arXiv preprint arXiv:1606.06160.
references.authors: C. Zhu S. Han H. Mao W.J. Dally
references.title: Trained ternary quantization
references.venue: CoRR, abs/1612.01064.
sections.heading: 1 INTRODUCTION
sections.text: Over the past decade, deep learning techniques have been remarkably successful in a wide spectrum of applications through the use of very large and deep models trained using massive datasets. This training process necessitates up to 100’s of ExaOps of computation and Gigabytes of storage. It is, however, well appreciated that a range of approximate computing techniques can be brought to bear to significantly reduce this computational complexity (Chen et al., 2018) - and amongst them, exploiting reduced numerical precision during the training process is extremely effective and has already been widely deployed (Gupta et al., 2015).
  There are several reasons why reduced precision deep learning has attracted the attention of both hardware and algorithms researchers. First, it offers well defined and scalable hardware efficiency, as opposed to other complexity reduction techniques such as pruning (Han et al., 2015b;a), where handling sparse data is needed. Indeed, parameter complexity scales linearly while multiplication hardware complexity scales quadratically with precision bit-width (Zhou et al., 2016). Thus, any advance towards truly binarized networks (Hubara et al., 2016) corresponds to potentially 30x - 1000x complexity reduction in comparison to single precision floating-point hardware. Second, the mathematics of reduced precision has direct ties with the statistical theory of quantization (Widrow and Kollár, 2008). In the context of deep learning, this presents an opportunity for theoreticians to derive analytical trade-offs between model accuracy and numerical precision (Lin et al., 2016; Sakr et al., 2017).
  ∗Work done while at IBM Research.
  Most ongoing efforts on reduced precision deep learning solely focus on quantizing representations and always assume wide accumulators, i.e., ideal summations. The reason being reduced precision accumulation can result in severe training instability and accuracy degradation, as illustrated in Figure 1 (a) for ResNet 18 (ImageNet) model training. This is especially unfortunate, since the hardware complexity in reduced precision floating-point numbers (needed to represent small gradients during training) (Wang et al., 2018; Micikevicius et al., 2017) is dominated by the accumulator bit-width. To illustrate this dominance we developed a model underpinned by the hardware synthesis of low-precision floating-point units (FPU), that translates precision into area complexity of the FPU. Comparisons obtained from this model are shown in Figure 1 (b). We observe that accumulating in high precision severely limits the hardware benefits of reduced precision computations. This presents a new angle to the problem of reduced precision deep learning training which concerns determining suitable accumulation precision and forms the basis of our paper. Our findings are that the accumulation precision requirements in deep learning training are nowhere near 32-b, and in fact could enable further complexity reduction of FPUs by a factor of 1.5 ∼ 2.2×.
sections.heading: 1.1 RELATED WORKS
sections.text: Our work is concerned with establishing theoretical foundations for estimating the accumulation bit precision requirements in deep learning. While this topic has never been addressed in the past, there are prior works in both deep learning and high performance computing communities that align well with ours.
  Most early works on reduced precision deep learning consider fixed-point arithmetic or a variation of it (Gupta et al., 2015). However, when considering quantization of signals involving the backpropagation algorithm, finding a suitable fixed-point configuration becomes challenging due to a weak handle on the scalar dynamic range of the back-propagated signals. Thus, hardware solutions have been sought, and, accordingly, other number formats were considered. Flexpoint (Köster et al., 2017) is a hybrid version between fixed-point and floating-point where scalars in a tensor are quantized to 16-b fixed-point but share 5-b of exponenent to adjust the dynamic range. Similarly, WAGE (Wu et al., 2018) augments Flexpoint with stochastic quantization and enables integer quantization. All of these schemes focused on representation precision, but mostly used 32-bit accumulation. Another option is to use reduced precision floating-point as was done in MPT (Micikevicius et al., 2017), which reduces the precision of most signals to 16-b floating-point, but observes accuracy degradation when reducing the accumulation precision from 32-b. Recently, Wang et al. (2018) quantize all representations to 8-b floating-point and experimentally find that the accumulation could be in 16-b with algorithmic contrivance, such as chunk-based accumulation, to enable convergence.
  The issue of numerical errors in floating-point accumulation has been classically studied in the area of high performance computing. Robertazzi and Schwartz (1988) were among the first to statistically estimate the effects of floating-point accumulation. Assuming a stream of uniformly and exponentially distributed positive numbers, estimates for the mean square error of the floating-
  point accumulation were derived via quantization noise analysis. Because such analyses are often intractable (due to the multiplicative nature of the noise), later works on numerical stability focus on worst case estimates of the accumulation error. Higham (1993) provide upper bounds on the error magnitude by counting and analyzing round-off errors. Following this style of worst case analysis, Castaldo et al. (2008) provide bounds on the accumulation error for different summing algorithms, notably using chunk-based summations. Different approaches to chunking are considered and their benefits are estimated. It is to be noted that these analyses are often loose as they are agnostic to the application space. To the best of our knowledge, a statistical analysis on the accumulation precision specifically tailored to deep learning training remains elusive.
sections.heading: 1.2 CONTRIBUTIONS
sections.text: Our contribution is both theoretical and practical. We introduce the variance retention ratio (VRR) of a reduced precision accumulation in the context of the three deep learning dot products. The VRR is used to assess the suitability, or lack thereof, of a precision configuration. Our main result is the derivation of an actual formula for the VRR that allows us to determine accumulation bit-width for precise tailoring of computation hardware. Experimentally, we verify the validity and tightness of our analysis across three benchmarking networks (CIFAR-10 ResNet 32, ImageNet ResNet 18 and ImageNet AlexNet).
sections.heading: 2 BACKGROUND ON FLOATING-POINT ARITHMETIC
sections.text: The following basic floating-point definitions and notations are used in our work: Floating-point representation: A b-bit floating-point number a has a signed bit, e exponent bits, and m mantissa bits so that b = 1 + e + m. Its binary representation is (Bs, B ′ 1, . . . , B ′ e, B ′′ 1 , . . . , B ′′ m) ∈ {0, 1}b and its value is equal to: a = (−1)Bs × 2E × (1 + M)
  where E = −(2e−1 − 1) + ∑e i=1B ′ i2 (e−i) and M = ∑m i=1B ′′ i 2 −i. Such number is called a (1, e,m) floating-point number. Floating-point operations: One of the most pervasive arithmetic functions used in deep learning is the dot product between two vectors which is the building block of the generalized matrix multiplication (GEMM). A dot product is computed in a multiply-accumulate (MAC) fashion and thus requires two floating-point operations: multiplication and addition. The realization of an ideal floating-point operation requires a certain bit growth at the output to avoid loss of information. For instance, in a typical MAC operation, if c ← c + a × b where a is (1, ea,ma) and b is (1, eb,mb), then c should be (1,max(ea, eb) + 2,ma + mb + 1 + ∆E), which depends on the bit-precision and the relative exponent difference of the operands ∆E . However, it is often more practical to pre-define the precision of c as (1, ec,mc), which requires rounding immediately after computation. Such rounding might cause an operand to be completely or partially truncated out of the addition, a phenomenon called ”swamping” (Higham, 1993), which is the primary source of accumulation errors.
sections.heading: 3 ACCUMULATION VARIANCE
sections.text: The second order statistics (variance) of signals are known to be of great importance in deep learning. For instance, in prior works on weight initialization (Glorot and Bengio, 2010; He et al., 2015), it is customary to initialize random weights subject to a variance constraint designed so as to prevent vanishing or explosion of activations and gradients. Thus, such variance engineering induces fine convergence of DNNs. Importantly, in such analyses, the second order output statistics of a dot product are studied and expressed as a function of that of the accumulated terms, which are assumed to be independent and having similar variance. A fundamental assumption is: V ar(s) = nV ar(p), where V ar(s) and V ar(p) are the variances of the sum and individual product terms, respectively, and n is the length of the dot product. One intuition concerning accumulation with reduced precision is that, due to swamping, some product terms may vanish from the summation, resulting in a lower variance than expected: V ar(s) = ñV ar(p), where ñ < n. This constitutes a violation of a key assumption and effectively leads to the re-emergence of the difficulties in training neural networks with improper weight initialization which often harms the convergence behavior (Glorot and Bengio, 2010; He et al., 2015).
  Input Feature Maps (IFM) Output Feature Maps (OFM)
  IFM Width (IW) OFM Width (OW)
  IF M
  H ei
  gh t
  (IH )
  O FM
  H ei
  gh t
  (O H
  )
  Input Channel Number (ICN)
  Output Channel Number (OCN)
  Kernel Width (KW)
  Ke rn
  el H
  ei gh t (K H)
  Accumulation length = ICN x KW x KH
  (a)
  Input Feature Maps (IFM) Derivatives Output Feature Maps (OFM) Derivatives
  IFM Width (IW) OFM Width (OW)
  IF M
  H ei
  gh t
  (IH )
  O FM
  H ei
  gh t
  (O H
  )
  Output Channel Number (OCN)
  Kernel Width (KW) Kernel Height (KH)
  Accumulation length = OCN x KW x KH
  Input Channel Number (ICN)
  (b)
  Elementwise Product of Input Activations and Output Derivatives
  Product Width (PW)
  Pr od
  uc t H
  ei gh t (P H )
  Accumulation length = BS x PW x PH
  Weight Gradients (2D
  Slice)
  Batch Size (BS)
  (c)
  Figure 2: The three GEMM calls, and hence accumulations, in one iteration of the back-propagation algorithm: (a) the forward propagation (FWD), (b) the backward propagation (BWD), and (c) gradient computation (GRAD). The accumulation of these three GEMMs is across multiple dimensions (mini-batch size, feature maps, output channels etc.) and their lengths are usually very long.
  To explain the poor convergence of our ResNet 18 run (Figure 1 (a)), we evaluate the behavior of accumulation variance across layers. Specifically, we check the three dot products of a backpropagation iteration: the forward propagation (FWD), the backward propagation (BWD), and the gradient computation (GRAD), as illustrated in Figure 2. Indeed, there is an abnormality in reduced precision GRAD as shown in Figure 3. It is also observed that the abnormality of variance is directly related to accumulation length. From Figure 3, the break point corresponds to the switch from the first to the second residual block. The GRAD accumulation length in the former is much longer (4×) than the latter. Thus, evidence points to the direction that for a given precision, there is an accumulation length for which the expected variance cannot be properly retained due to swamping. Motivated by these observations, we propose to study the trade-offs among accumulation variance, length, and mantissa precision.
  Before proceeding, it is important to note that our upcoming analysis differs, in style, from many works on reduced precision deep learning where it is common to model quantization effects as additive noise causing increased variance (McKinstry et al., 2018). Our work does not contradict such findings, since prior arts have considered representation quantization whose effects are, by nature, different from intermediate roundings in partial sums.
sections.heading: 4 MANTISSA PRECISION REQUIREMENTS ANALYSIS
sections.text: We assume sufficient exponent precision throughout and treat reduced precision floating-point arithmetic as an unbiased form of approximate computing, as is customary. Thus, our work focuses on associating second order statistics to mantissa precision.
  We consider the accumulation of n terms {pi}ni=1 which correspond to the element-wise product terms in a dot product. The goal is to compute the correct nth partial sum sn where si = ∑i i′=1 pi′ .
  We assume, as in (He et al., 2015), that the product terms {pi}ni=1 are statistically independent, zeromean, and have the same variance σ2p. Thus, under ideal computation, the variance of sn (which is equal to its second moment) should be V ar(sn)ideal = nσ2p. However, due to swamping effects, the variance of sn under reduced precision is V ar(sn)swamping 6= V ar(sn)ideal.
  Let the product terms {pi}ni=1 and partial sum terms {si} n i=1 have mp and macc mantissa bits, respectively. Our key contribution is a formula for the variance retention ratio V RR = V ar(sn)swampingV ar(sn)ideal . The VRR, which is always less than or equal to unity, is a function of n, mp, and macc only, which needs no simulations to be computed. Furthermore, to preserve quality of computation under reduced precision, it is required that V RR → 1. As it turns out, the VRR for a fixed precision is a curve with ”knee” with respect to n, where a break point in accumulation length beyond which a certain mantissa precision is no longer suitable can be easily identified. Accordingly, for a given accumulation length, the mantissa precision requirements can be readily estimated.
  Before proceeding, we formally define swamping. As illustrated in Figure 4, the bit-shift of pi due to exponent difference may cause partial (e.g., stage 1-4) or full truncation of pi’s bits, called swamping. We define (1) ”full swamping” which occurs when |si| > 2macc |pi+1|, and (2) ”partial swamping” which occurs when 2macc−mp |pi+1| < |si| ≤ 2macc |pi+1|. These two swamping types will be fully considered in our analysis.
sections.heading: 4.1 VARIANCE RETENTION RATIO
sections.text: In the lemma below, we first present a formula for the VRR when only full swamping is considered. Lemma 1. The variance retention ratio of a length n accumulation using macc mantissa bits, and when only considering full swamping, is given by:
  V RRfull swamping =
  ∑n−1 i=2 iqi + nq̃n
  kn (1) where qi = 2Q (
  2macc√ i
  )( 1− 2Q ( 2macc√ i−1 )) , q̃n = 1 − 2Q ( 2macc√ n ) , k = ∑n−1 i=2 qi + q̃n is a
  normalization constant, and Q denotes the elementary Q-function.
  The proof is provided in Appendix A. A preliminary check is that a very large value of macc in (1) causes all {qi}n−1i=1 terms to vanish and q̃n to approach unity. This makes V RR → 1 for high precision as expected. On the other hand, if we assume macc to be small, but let n → ∞, we get nq̃n → 0 because the Q-function term will approach 1 exponentially fast as opposed to the n term which is linear. Furthermore, the terms inside the summation having a large iwill vanish by the same argument, while the n term in the denominator will make the ratio decrease and we would expect V RR → 0. This means that with limited precision, there is little hope to achieve a correct result when the accumulation length is very large. Also, the rapid change in VRR from 0 to 1 indicates that VRR can be used to provide sharp decision boundary for accumulation precision.
  The above result only considers full swamping and is thus incomplete. Next we augment our analysis to take into account the effects of partial swamping. The corresponding formula for the VRR is provided in the following theorem. Theorem 1. The variance retention ratio of a length n accumulation using mp and macc mantissa bits for the input products and partial sum terms, respectively, is given by:
  V RR =
  ∑n−1 i=2 (i− α)+qi1{i>α} + ∑mp jr=2
  (n− αjr )+q′i1{n>αjr} + nk3 kn
  (2)
  where (x)+ = { x if x > 0 0 otherwise , 1A = { 1 if A is true 0 otherwise ,
  α = 2 macc−3mp
  3
  ∑mp j=1 2 j(2j − 1)(2j+1 − 1), qi = 2Q ( 2macc√ i )( 1− 2Q ( 2macc√ i−1 )) ,
  αjr = 2macc−3mp
  3
  ∑jr−1 j=1 2
  j(2j − 1)(2j+1 − 1), q′jr = Njr−12Q ( 2macc−mp+jr−1√ n )( 1− 2Q ( 2macc−mp+jr√ n )) ,k = k1 + k2 + k3,
  k1 = ∑n−1 i=2 qi1{i>α}, k2 = ∑mp jr=2 q′i1{n>αjr}, and k3 = 1− 2Q ( 2macc−mp+1√ n ) .
  The proof is provided in Appendix B. Observe the dependence on macc, mp, and n. Therefore, in what follows, we shall refer to the VRR in (2) as V RR(macc,mp, n). Once again, we verify the extremal behavior of our formula. A very large value ofmacc in (2) causes k1 ≈ k2 ≈ 0 and k3 ≈ 1. This makes V RR→ 1 for high precision as expected. In addition, assuming small macc and letting n → ∞, we get nk3 → 0 because k3 decays exponentially fast due to the Q-function term. By the same argument, q′jr → 0 for all jr and qi → 0 for all but small values of i. Thus, the numerator will be small, while the denominator will increase linearly in n causing V RR → 0. Thus, once more, we establish that with limited accumulation precision, there is little hope for a correct result.
sections.heading: 4.2 VRR WITH CHUNK BASED ACCUMULATIONS
sections.text: Next we consider an accumulation that uses chunking. In particular, assume n = n1×n2 so that the accumulation is broken into n2 chunks, each of length n1. Thus, n2 accumulations of length n1 are performed and the n2 intermediate results are added to obtain sn. This simple technique is known to greatly improve the stability of sums (Castaldo et al., 2008). The VRR can be used to theoretically explain such improvements. For simplicity, we assume two-level chunking (as described above) and same mantissa precision macc for both inter-chunk and intra-chunk accumulations. Applying the above analysis, we may obtain a formula for the VRR as provided in the corollary below, which is proved in Appendix C. Corollary 1. The variance retention ratio of an length n = n1 × n2 accumulation with chunking, where n1 is the chunk size and n2 is the number of chunks, using mp and macc mantissa bits for the input products and partial sum terms, respectively, is given by:
  V RRchunking = V RR(macc,mp, n1)× V RR (macc,min (macc,mp + log2(n1)) , n2) (3)
sections.heading: 4.3 VRR WITH SPARSITY
sections.text: It is common to encounter sparse operands in deep learning dot products. Since addition of zero is an identity operation, the effective accumulation length is often less than as described by the network topology. Indeed, for a given accumulation, supposedly of length n, if we can estimate the non-zero ratio (NZR) of its incoming product terms, then the effective accumulation length is NZR× n. Thus, when an accumulation is known to have sparse inputs with known NZR, a better estimate of the VRR is
  V RRsparsity = V RR(macc,mp, NZR× n). (4)
  Similarly, when considering the VRR with chunking, we may use knowledge of sparsity to obtain the effective intra-accumulation length as NZR × n1. This change is reflected both in the VRR of the intra-chunk accumulation and the input precision of the inter-chunk accumulation:
  V RRchunking and sparsity = V RR(macc,mp, NZR× n1) × V RR (macc,min (macc,mp + log2(NZR× n1)) , n2) (5)
  In practice, the NZR can be estimated by making several observations from baseline data. Using an estimate of the NZR makes our analysis less conservative.
sections.heading: 4.4 USAGE OF ANALYSIS
sections.text: For a given accumulation setup, one may compute the VRR and observe how close it is from the ideal value of 1 in order to judge the suitability of the mantissa precision assignment. It turns out that when measured as a function of accumulation length n for a fixed precision, the VRR has a breakdown region. This breakdown region can very well be observed when considering what we define as the normalized exponential variance lost:
  v(n) = en(1−V RR) (6)
  In Figure 5 (a,b) we plot v(n) for different values of macc when considering both normal accumulation and chunk-based accumulation with a chunk-size of 64. The value of mp is set to 5-b, corresponding to the product of two numbers in (1,5,2) floating-point format (Wang et al., 2018). We consider macc to be suitable for a given n only if v(n) < 50. The reason being, in all plots, the
  variance lost rapidly increases when v(n) > 50 and n increases. On the other hand, when v(n) < 50 and n decreases, the variance lost quickly drops to zero. This choice of a cut-off value is thus chosen purely based on the accumulation length and precision.
  In addition, when performing chunk-based accumulation, the chunk size is a hyperparameter that, a priori, cannot be determined trivially. Castaldo et al. (2008) identified an optimal chunk size minimizing the loose upper bound on the accumulation error they derived. In practice, they did not find the accumulation error to be sensitive to the chunk-size. Neither did Wang et al. (2018) who performed numerical simulations. By sweeping the chunk size and observing the accumulation behavior on synthetic data, it was found that chunking significantly reduces accumulation error as long as the chunk size is not too small nor too large. Using our analysis, we provide a theoretical justification. Figure 5 (c) shows the VRR for various accumulation setups, including chunking when the chunk size is sweeped. For each case we see that chunking raises the VRR to a value close to unity. Furthermore, the VRR curve in that regime is ”flat”, meaning that a specific value of chunk size does not matter as long as it is not too small nor too large. One intuition is that a moderate chunk size prevents both inter- and intra-chunk accumulations to be as large as the original accumulation. In our upcoming chunking experiments we use a chunk size of 64 as was done by Wang et al. (2018).
sections.heading: 5 NUMERICAL RESULTS
sections.text: Using the above analysis, we predict the mantissa precisions required by the three GEMM functions for training the following networks: ResNet 32 on the CIFAR-10 dataset, ResNet 18 and AlexNet on the ImageNet dataset. Those benchmarks were chosen due to both their popularity and topologies which present large accumulation lengths, making them good candidates against which we can verify our work. We use the same configurations as (Wang et al., 2018), in particular, we use 6-b of exponents in the accumulations, and quantize the intermediate tensors to (1,5,2) floating-point format and keep the final layer’s precision in 16 bit. The technique of loss scaling (Micikevicius et al., 2017) is used in order to limit underflows of activation gradients. A single scaling factor of 1000 was used for all models tested.
  In order to realize rounding of partial sums, we modify the CUDA code of the GEMM function (which, in principle, can be done using any framework). In particular, we add a custom rounding function where the partial sum accumulation occurs. Quantization of dot product inputs is handled similarly.
  The predicted precisions for each network and layer/block are listed in Table 1 for the case of normal and chunk-based accumulation with a chunk size of 64. Several insights are to be noted.
  • The required accumulation precision for CIFAR-10 ResNet 32 is in general lower than that of the ImageNet networks. This is simply because, the network topology imposes shorter dot products. • Though, topologically, the convolutional layers in the two ImageNet networks are similar, the precision requirements do vary. Specifically, the GRAD accumulation depends on the feature map
  dimension which is mostly dataset dependent, yet AlexNet requires less precision than ResNet 18. This is because the measured sparsity of the operands was found to be much higher for AlexNet. • Figure 5 suggests that chunking decreases the precision requirements significantly. This is indeed observed in Table 1, where we see that the benefits of chunking reach up to 6-b in certain accumulations, e.g., the GRAD acccumulation in the first ResBlock of ImageNet ResNet 18.
  Because our predicted precision assignment ensures the VRR of all GEMM accumulations to be close to unity, we expect reduced precision training to converge with close fidelity to the baseline. Since our work focuses on accumulation precision, in our experiments, the baseline denotes accumulation in full precision. For a fair comparison, all upcoming results use (1,5,2) representation precision. Thus, the effects of reduced precision representation are not taken into account.
  The goal of our experiments is to investigate both the validity and conservatism of our analysis. In Figure 6, we plot the convergence curves when training with our predicted accumulation precision for a normal accumulation. The runs corresponding to chunk-based accumulations were also performed but are omitted since the trend is similar. Furthermore, we repeat all experiments with precision perturbation (PP), meaning a specific reduction in precision with respect to our prediction. For instance, PP = 0 indicates our prediction while PP = −1 corresponds to a one bit reduction. Finally, in order to better visualize how the accumulation precision affect convergence, we plot in Figure 6 (d) the accuracy degradation as a function of precision perturbation for each of our three networks with both normal and chunk-based accumulations. The following is to be noted:
  • When PP = 0, the converged accuracy always lies within 0.5% of the baseline, a strong indication of the validity of our analysis. We use a 0.5% accuracy cut-off with respect to the baseline as it corresponds to an approximate error bound for neural networks obtained by changing the random numbers seed (Goyal et al., 2017; Gastaldi, 2017). • When PP < 0, a noticeable accuracy degradation is observed, most notably for ImageNet ResNet 18. The converged accuracy is no longer within 0.5% of the baseline. Furthermore, a clear trend observed is that the higher the perturbation, the worse the degradation. • ImageNet AlexNet is more robust to perturbation than the two ResNets. While PP = −1 causes a degradation strictly > 0.5%, it is not much worse than the PP = 0 case. This observation aligns with that from neural net quantization that Alexnet is robust due to its over-parameterized network structure (Zhu et al., 2016). But the trend of increasing degradation remains the same. • Figure 6 (d) suggests that the effects of PP are more pronounced for a chunk-based accumulation. Since the precision assignment itself is lower (Table 1), a specific precision perturbation corresponds to a relatively higher change. For example, decreasing one bit from a 6-b assignment is more important than decreasing one bit from a 10-b assignment. Further justification can be obtained by comparing Figures 5 (a) and 5 (b) where consecutive lines are less closely aligned for the chunk-based accumulation, indicating more sensitivity to precision perturbation.
  Thus, overall, our predictions are adequate and close to the limits beyond which training becomes unstable. These are very encouraging signs that our analysis is both valid and tight.
sections.heading: 6 CONCLUSION
sections.text: We have presented an analytical method to predict the precision required for partial sum accumulation in the three GEMM functions in deep learning training. Our results prove that our method is able to accurately pinpoint the minimum precision needed for the convergence of benchmark networks to the full-precision baseline. Our theoretical concepts are application agnostic, and an interesting extension would be to consider recurrent architectures such as LSTMs. In particular, training via backpropagation in time could make the GRAD accumulation very large depending on the number of past time-steps used. In such a case, our analysis is of great relevance to training precision optimization. On the practical side, this analysis is a useful tool for hardware designers implementing reduced-precision FPUs, who in the past have resorted to computationally prohibitive brute-force emulations. We believe this work addresses a critical missing link on the path to truly low-precision floating-point hardware for DNN training.
sections.heading: ACKNOWLEDGMENT
sections.text: This work is supported in part by IBM Research; IBM SoftLayer; IBM Cognitive Computing Cluster (CCC); IBM-ILLINOIS Center for Cognitive Computing Systems Research (C3SR) - a research collaboration as part of the IBM AI Horizons Network; and C-BRIC, one of six centers in JUMP, a Semiconductor Research Corporation (SRC) program sponsored by DARPA. The authors would like to thank I-Hsin Chung, Ming-Hung Chen and Silvia Melitta Mueller for helpful discussions and support.
sections.heading: A PROOF OF LEMMA 1
sections.text: In order to compute the VRR, we first need to compute V ar(sn) during swamping, i.e., V ar(sn)swamping = Eswamping [ s2n ] , where the equality holds by application of Assumptions 1 and 2. To do so, we rely on the Law of Total Expectation. Indeed, assume that A is the set of events that describe all manners in which the accumulation sn experiencing swamping can occur, and let P (A) be the probability of event A ∈ A. Hence, by the Law of Total Expectation, we have that
  V ar(sn)swamping = ∑ A∈A E [ s2n ∣∣∣∣A]P (A) (7) It is in fact a difficult task to enumerate and describe all events inA. Thus we consider a reduced set of events Â ⊂ A which is representative enough of the manners in which the accumulation occurs, yet tractable so that it can be used as a surrogate to A in (7). We shall form the set Â by application of Assumption 3, 4, and 5 as we proceed.
  We consider a scenario where the first occurrence of full swamping is at iteration i of the summation for i = 2 . . . n− 1. This happens if:
  |si| > 2macc |pi+1| & |si′ | < 2macc |pi′+1| for i′ = 1 . . . i− 1. (8)
  Instead of looking at the actual absolute value of an incoming product term, we replace it by its typical value of σp. Furthermore, we simplify the condition of no swamping prior to iteration i by only considering the accumulated sum at the previous iteration. This is due to Assumption 3 which allows us toconsider a simplified scenario where the accumulation is monotonic in the iterations leading to full swamping. Hence, our simplified condition for the first occurrence of full swamping at iteration i is given by: |si−1| < 2maccσp < |si|. As iteration i corresponds to a full swamping event, we may invoke Assumption 4 and treat each of the two inequalities above independently. Finally, we invoke Assumption 5: since full swamping happens at itertion i, then the result of the accumulation is sn = si since the computation in the following iterations is halted.
  Thus, the event set Â we construct for our analysis consists of the mutually exclusive events {Ai}n−1i=2 where Ai is the event that full swamping occurs for the first time at iteration i under the above assumptions. The condition for event i to happen is given by (8). By Central Limit Theorem, which we use by virtue of the si being a summation of independent, indentically distributed product terms, we have that si ∼ N (0, iσ2p), so that:
  P (Ai) = 2Q
  ( 2macc√
  i
  )( 1− 2Q ( 2macc√ i− 1 )) = qi. (9)
  Furthermore, by Assumption 5 we have:
  E [ s2n ∣∣∣∣Ai] = E [s2i ] = iσ2p. (10) We also add to our space of events, the event An where no full swamping occurs over the course of the accumulation. This event happens if |sn| < 2maccσp and thus has probability P (An) = 1 −
  2Q (
  2macc√ n ) = q̃n. Since this event corresponds to the ideal scenario, we have E [ s2n ∣∣∣∣An] = nσ2p. Thus, under the above conditions we have:
  V ar(sn)swamping = 1
  k n∑ i=2 E [ s2n ∣∣∣∣Ai]P (Ai) = σ2pk ( n−1∑ i=2 iqi + nq̃n ) (11)
  where k = ∑n−1 i=2 qi + q̃n is a normalization constant needed as Â does not describe the full probability space.
  Consequently we obtain (1) as formula for the VRR completing the proof for Lemma 1.
sections.heading: B PROOF OF THEOREM 1
sections.text: First, we do not change the description of the events {Ai}n−1i=2 above. Notably, by Assumption 5, once full swamping occurs, i.e., |si| > 2maccσp, the computation is stuck and stops. The probability of this event is P (Ai) as above. However, to account for partial swamping, we alter the result of
  E [ s2n ∣∣∣∣Ai]. Indeed, partial swamping causes additional loss of variance. When the input product terms have mp bits of mantissa, then before event Ai can occur, the computation should go through each of the mp stages described in Figure 4. We again use Assumption 3 and consider a typical scenario for each of the mp stages of partial swamping preceding a full swamping event whereby the accumulation is monotonic and the magnitude of the incoming product term is close to its typical value σp. Under this assumption, stage j is expected to happen for the following number of iterations:
  Nj = 2 macc+1−(mp−j) = 2macc−mp+j+1 (12)
  for j = 1 . . .mp. At stage j, j least significant bits in the representation of the incoming product term are truncated (swamped). The variance lost because of this truncation, which we call fractional variance loss E[f2j ], can be computed by assuming the truncated bits are equally likely to be 0 or 1 (Assumption 6), so that:
  E[f2j ] = σ 2 p 2j−1∑ k=0 1 2j ( 2−mpk )2 = σ2p2 −2mp (2 j − 1)(2j+1 − 1)
  6 (13)
  Hence, the total fractional variance lost before the occurrence of even Ai is NjE[f2j ]. Thus, we update the value of variance conditioned on Ai as follows:
  E [ s2n ∣∣∣∣Ai] = (iσ2p −NjE[f2j ])+ = σ2p i− 2macc−3mp 3 mp∑ j=1 2j(2j − 1)(2j+1 − 1)  +
  (14)
  where we used the operator (x)+ = { x if x > 0 0 otherwise
  in order to guarantee that the variance is
  positive. Effectively, we neglect the events Ai where i is so small that the variance retained is less than the variance lost due to partial swamping. In other words, an event whereby full swamping occurs very early in the accumulation is considered to have zero probability and we replace P (Ai) in (9) by:
  P (Ai) = qi1{i>α} (15) where qi = 2Q (
  2macc√ i
  )( 1− 2Q ( 2macc√ i−1 )) as in (9), 1 is the indicator function, and α =
  2macc−3mp
  3
  ∑mp j=1 2
  j(2j − 1)(2j+1 − 1) as in (14). In addition, some boundary conditions need to be accounted for. These include the cases when no full swamping happens before the accumulation is complete but partial swamping does happen. We again consider a typical scenario as above and append our event setA with mp− 1 boundary events{ A′jr }mp jr=2
  , where the event A′jr corresponds to the case where the computation has gone through stage jr − 1 of partial swamping but has not reached stage jr yet. The condition for this event is σp2
  macc−mp+jr−1 < |sn| < σp2macc−mp+jr and occurs typically for up to Njr−1 iterations. The total fractional variance lost is:
  σ2p jr−1∑ j=1 Nj 2j−1∑ k=0 1 2j ( 2−mpk )2 = σ2p 2macc−3mp3 jr−1∑ j=1 2j(2j − 1)(2j+1 − 1) (16)
  Hence,
  E [ s2n ∣∣∣∣A′jr] = σ2p (n− αjr )+ (17) where αjr = 2macc−3mp
  3
  ∑jr−1 j=1 2 j(2j −1)(2j+1−1). And the probability of event A′jr is given by:
  P (A′jr ) = q ′ jr1{n>αjr} (18) where q′jr = Njr−12Q ( 2macc−mp+jr−1√ n )( 1− 2Q ( 2macc−mp+jr√ n )) , the multiplication by Njr−1 reflects the number of iterations the event may occur for.
  Finally, the event An is updated and corresponds to the case where neither partial nor full swamping occurs. The condition for this event is |sn| < 2macc−mp+1 and has a probability P (An) = 1 − 2Q (
  2macc−mp+1√ n
  ) .
  Putting things together, we use the law of total expectation as in (7) to compute:
  V ar(sn)swamping =
  σ2p k n−1∑ i=2 (i− α)+qi1{i>α} + mp∑ jr=2 (n− αjr )+q′i1{n>αjr} + nk3  (19) where k = k1 + k2 + k3, k1 = ∑n−1 i=2 P (Ai), k2 = ∑mp jr=2
  P (A′jr ), and k3 = P (An). Hence, the formula for the VRR in (2) in the theorem follows and this concludes the proof.
sections.heading: C PROOF OF COROLLARY 1
sections.text: Applying the above analysis, we may compute the variance of the intermediate results as σ2pn1V RR(macc,mp, n1). To compute the variance of the final result, first note that the mantissa precision of the incoming terms to the inter-chunk accumulation (the results from the intra-chunk accumulation) is min (macc,mp + log2(n1)). The reason being that since the intra-chunk accumulation uses macc mantissa bits, the mantissa cannot grow beyond macc due to the rounding nature of the floating-point accumulation. However, if macc is large enough and n1 is small enough, it is most likely that the mantissa has not grown to the maximum. Assuming accumulation of terms having statistically similar absolute value as was done for the VRR analysis, then the bit growth of the mantissa is logarithmic in n1 and starts at mp.
  Hence, the variance of the computed result sn when chunking is used is:
  V ar(sn)chunking = σ 2 pn1V RR(macc,mp, n1)
  × n2V RR (macc,min (macc,mp + log2(n1)) , n2) (20)
  and hence the VRR with chunking can be computed using (3) in Corollary 1. This completes the proof.
title: ACCUMULATION BIT-WIDTH SCALING FOR ULTRA- LOW PRECISION TRAINING OF DEEP NETWORKS