Aussie AI

53. Arithmetic Optimization Research

  • Book Excerpt from "Generative AI in C++"
  • by David Spuler, Ph.D.

“Optimization hinders evolution.
Everything should be built top-down, except the first time.
Simplicity does not precede complexity, but follows it.”

— Alan Perlis, Computer Scientist.

 

 

Overview of Arithmetic Optimizations

We take them for granted in C++ now, but all of the arithmetic operations were once coded by other programmers, first as software algorithms and then later as hardware microcode. There are numerous research papers on how to perform addition and multiplication fast, let alone more the complex schemes for division and square-root.

Just when you thought you could completely ignore all this obscure theory, along comes the nasty multiplication bottleneck in your AI engine. Is CPU multiplication really as fast as it can be? What about addition? What about floating-point? Is there a faster way to do multiplication than what's in your GPU today?

Surprisingly, the answer has been a resounding “Yes!” as has been shown by the 2018 invention of the “Brain float 16” (bfloat16) by Google. This is a 16-bit alternative floating-point representation, with different arithmetic properties, as parallelized in its Tensor Processing Unit (TPU) chips. Hence, I politely suggest that you might want to dust off all these old papers and put on your thinking cap. Some of the main research areas include:

  • Faster algorithms for multiplication arithmetic (mostly hardware acceleration algorithms for chip designers)
  • Alternatives to using arithmetic multiplication (e.g. bitshifting, logarithms, other fancy stuff) (see Multiplication-free inference in Chapter 51)
  • Approximate multiplication algorithms (faster ways to multiply two numbers by allowing errors)
  • Matrix algebra theory (e.g. factorization/decomposition) applied to making tensor algorithms faster
  • Advanced number systems using alternative arithmetic methods (see Chapter 55)

Approximations of these arithmetic operations might be a way to go even faster in either sequential or parallel processing. One example is already implemented in x86 CPUs with the FTZ and DAZ floating-point modes (see Chapter 9), which are approximations that dispense with some of the less important parts of the IEEE 754 floating-point standard. Another example is the many papers on 8-bit floating-point quantization (FP8 quantization).

More ideas for research: Could there be anything more? Well, I'm even going to throw out a few ideas:

  • Disabling negative-zero in floating-point would be helpful.
  • Floating-point representations that don't use an offset for the exponent. Adding to the exponent is like bitshifting.
  • Add-as-integer approximate multiplication by addition (Mogami, 2020) would also be faster if we didn't need to adjust for the exponent's offset.
  • RELU built into a fast hardware operation via bitwise-AND with the negated sign bit.
  • Bitshift operators on floating-point numbers.
  • Logarithmic Number System (LNS) arithmetic operation speedups, especially LNS addition.

It's hard to predict what other little parallelization tricks might be hidden in all these old papers, when you consider that they were almost all written for sequential execution.

Multiplication Optimizations

Multiplication is the foremost bottleneck in training and inference of neural networks and Transformer architectures. Most models rely on matrix multiplications, whether you call it tensors or convolutions, which involve vector dot products, which in turn involve “multiply-and-add” sequences (called “multiply-accumulate” or MAC). The multiplication part is more expensive than the accumulation.

There have been various ideas over the years of AI research as to how to optimize multiplications, including:

  • Hardware-accelerated multiplication (lately, this is a GPU's bread-and-butter)
  • Advanced floating-point formats (e.g. bfloat16)
  • Faster multiplication arithmetic algorithms
  • Approximate multiplication arithmetic algorithms
  • Integer multiplication instead of floating-point (see quantization)
  • Faster matrix multiplication algorithms (e.g. low-rank matrices, tensor decomposition)
  • Avoiding or reducing multiplications (e.g. zero-multiplication models, pruning, zero skipping, sparsity, etc.)
  • Advanced mathematical numerical systems

Although being able to multiply two integers together is taken for granted by modern programmers, there are actually complicated algorithms happening behind the scenes (i.e. in the chips). Early algorithms include Karatsuba multiplication (1962), Toom-Cook multiplication, Schonhage–Strassen algorithms, and contributions by Knuth. The improvement and parallelization of such algorithms is fundamental to GPU and hardware accelerator design. Use of such algorithms in software acceleration of model inference seems unlikely to beat hardware acceleration.

Approximate Multiplication

In addition to faster integer multiplication algorithms, there are various ways to approximate multiplication arithmetic, using “inexact logic”. This means approximating the low-level numeric multiplication of integers or floating-point weights, not to be confused with approximating matrix multiplication in higher-level algorithms. The aim is to be faster, trading off some errors in the multiplication. Research exists in this area for both integer multiplication and floating-point multiplication.

A simple example of approximating integer multiplication is the use of power-of-two weights and bitshift algorithms (or multiple bitshift-adds), as discussed in the section on weight bitshifting. Some of the more theoretical algorithms for approximating integer multiplication arithmetic are shown below.

These methods are interesting, but using these in software inference algorithms seems unlikely to be faster than hardware acceleration of (non-approximate) multiplication. In fact, Kim et al. (2019) notes that they tested their new algorithms against a non-GPU version of the models, as their algorithm was slower than hardware-accelerated models. The possible use of these approximate multiplication algorithms to further speed up multiplication in hardware accelerators, accepting some error, has been somewhat explored, but seems an area offering future improvements.

Nevertheless, there has been an explosion of papers on approximate multiplication algorithms and their use in model inference and training. For analysis of low-level approximate multiplication algorithms and their theory, including logarithmic approximate multiplication and non-logarithmic approximate multiplication, see advanced AI mathematics. Also related is the Logarithmic number system (LNS) and other obscure number systems such as Dyadic numbers, the Residue Number System (RNS) and Posit Number System (PNS); see advanced number systems. See also additive neural networks and multiplier-free inference.

Papers focused on approximate multiplication algorithms:

  1. M. A. Hanif, A. Marchisio et al., 2018, X-DNNs: Systematic cross-layer approximations for energy-efficient deep neural networks, Journal of Low Power Electronics, vol. 14, no. 4, pp. 520–534, Dec. 2018. https://www.semanticscholar.org/paper/X-DNNs:-Systematic-Cross-Layer-Approximations-for-Hanif-Marchisio/5ddaf1aff7d5a4a3484963849828c8d2d1315bc3
  2. M. Shafique, R. Hafiz, S. Rehman, W. El-Harouni, and J. Henkel, 2016, Cross-layer approximate computing: From logic to architectures, Proceedings of the 53rd Annual Design Automation Conference, ACM (2016), p. 99., https://ieeexplore.ieee.org/document/7544342
  3. S. Mittal, 2016, A survey of techniques for approximate computing, ACM Computing Surveys (CSUR) 48, 62 (2016), https://dl.acm.org/doi/10.1145/2893356
  4. P. Kulkarni, P. Gupta, and M. Ercegovac, 2011, Trading accuracy for power with an underdesigned multiplier architecture, 2011 24th International Conference on VLSI Design (VLSI Design), IEEE (2011), pp. 346–351, https://ieeexplore.ieee.org/document/5718826
  5. V. Gupta, D. Mohapatra, S. P. Park, A. Raghunathan, and K. Roy, 2011, Impact: imprecise adders for low-power approximate computing, Proceedings of the 17th IEEE/ACM International Symposium on Low-Power Electronics and Design, IEEE Press (2011), pp. 409–414, https://ieeexplore.ieee.org/document/5993675
  6. M. T. Teimoori, M. A. Hanif, A. Ejlali, and M. Shafique, 2018, AdAM: Adaptive approximation management for the non-volatile memory hierarchies, Design, Automation and Test in Europe Conference and Exhibition (DATE), 2018, IEEE (2018), pp. 785–790, https://ieeexplore.ieee.org/document/8342113
  7. F. Sampaio, M. Shafique, B. Zatt, S. Bampi, and J. Henkel, 2015, Approximation-aware Multi-Level Cells STT-RAM cache architecture, 2015 International Conference on Compilers, Architecture and Synthesis for Embedded Systems (CASES), October (2015), pp. 79–88, https://ieeexplore.ieee.org/abstract/document/7324548
  8. Muhammad Shafique, Rehan Hafiz, Semeen Rehman, Walaa El-Harouni, Jörg Henkel, 2016, A Low Latency Generic Accuracy Configurable Adder, in 53nd ACM/EDAC/IEEE Design Automation Conference & Exhibition (DAC), 2016. (Open-Source Library of Low-Power Approximate Computing Modules, 2023), Code: https://ces.itec.kit.edu/lpACLib.php Code: https://sourceforge.net/projects/lpaclib/
  9. S. S. Sarwar, S. Venkataramani et al., 2018, Energy-efficient neural computing with approximate multipliers, J. Emerg. Technol. Comput. Syst., vol. 14, no. 2, pp. 16:1–16:23, Jul. 2018, https://dl.acm.org/doi/10.1145/3097264
  10. Q. Zhang, T. Wang, Y. Tian, F. Yuan, and Q. Xu, 2015, Approxann: An approximate computing framework for artificial neural network, in DATE’15, March 2015, pp. 701–706, https://ieeexplore.ieee.org/document/7092478
  11. P. Kulkarni, P. Gupta, M. Ercegovac, 2011, Trading Accuracy for Power with an Underdesigned Multiplier Architecture, 24th International Conference on VLSI Design (VLSI Design), pp. 346–351, 2011, https://ieeexplore.ieee.org/document/5718826
  12. M. A. Hanif, R. Hafiz, and M. Shafique, 2018, Error resilience analysis for systematically employing approximate computing in convolutional neural networks, Design, Automation and Test in Europe Conference and Exhibition (DATE), 2018, IEEE (2018), pp. 913–916, https://ieeexplore.ieee.org/document/8342139
  13. K. Bhardwaj, P. S. Mane, J. Henkel, 2014, Power- and Area-Efficient Approximate Wallace Tree Multiplier for Error-Resilience Systems, ISQED, 2014, https://ieeexplore.ieee.org/document/6783335
  14. K. Y. Kyaw, W.-L. Goh, K.-S. Yeo, 2010, Low-power high-speed multiplier for error-tolerant application, IEEE International Conference of Electron Devices and Solid-State Circuits (EDSSC), 2010, https://ieeexplore.ieee.org/document/5713751
  15. M. B. Sullivan, E. E. Swartzlander, 2012, Truncated error correction for flexible approximate multiplication, ASILOMAR, pp. 355–359, 2012, https://ieeexplore.ieee.org/document/6489023
  16. W. El-Harouni, S. Rehman, B. S. Prabakaran, A. Kumar, R. Hafiz, and M. Shafique, 2017, Embracing approximate computing for energy-efficient motion estimation in high efficiency video coding, 2017 Design, Automation and Test in Europe Conference and Exhibition (DATE), IEEE (2017), pp. 1384–1389, https://ieeexplore.ieee.org/document/7927209
  17. M. Brandalero, A. C. S. Beck, L. Carro, and M. Shafique, 2018, Approximate on-the-fly coarse-grained reconfigurable acceleration for general-purpose applications, 2018 55th ACM/ESDA/IEEE Design Automation Conference (DAC), IEEE (2018), pp. 1–6, https://ieeexplore.ieee.org/document/8465930
  18. J. Zhang, K. Rangineni, Z. Ghodsi, and S. Garg, 2018, ThUnderVolt: Enabling aggressive voltage underscaling and timing error resilience for energy efficient deep neural network accelerators, arXiv preprint arXiv:1802.03806 (2018), https://arxiv.org/abs/1802.03806
  19. J. S. Miguel, J. Albericio, N. E. Jerger, and A. Jaleel, 2016, The bunker cache for spatio-value approximation, 2016 49th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), IEEE (2016), pp. 1–12, https://ieeexplore.ieee.org/document/7783746
  20. V. Mrazek, S. S. Sarwar, L. Sekanina, Z. Vasicek, and K. Roy, 2016, Design of power-efficient approximate multipliers for approximate artificial neural networks, 2016 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), November (2016), pp. 1–7, https://ieeexplore.ieee.org/document/7827658
  21. S. Kim, P. Howe, T. Moreau, A. Alaghi, L. Ceze, and V. Sathe, 2018, MATIC: Learning Around Errors for Efficient Low-Voltage Neural Network Accelerators, Design, Automation and Test in Europe Conference and Exhibition (DATE), 2018, IEEE (2018), pp. 1–6, https://arxiv.org/abs/1706.04332
  22. S. De, J. Huisken, and H. Corporaal, 2018, Designing energy efficient approximate multipliers for neural acceleration, in 2018 21st Euromicro Conference on Digital System Design (DSD). IEEE, 2018, pp. 288–295, https://ieeexplore.ieee.org/document/8491830
  23. V. Mrazek, R. Hrbacek, Z. Vasicek, and L. Sekanina, 2017, EvoApprox8b: Library of approximate adders and multipliers for circuit design and benchmarking of approximation methods, Proceedings of the Conference on Design, Automation and Test in Europe, European Design and Automation Association (2017), pp. 258–261, https://ieeexplore.ieee.org/document/7926993
  24. V. Mrazek, Z. Vasicek, and L. Sekanina, 2018, Design of quality-configurable approximate multipliers suitable for dynamic environment, in AHS’18, 2018, pp. 264–271, https://ieeexplore.ieee.org/document/8541479
  25. X. He, L. Ke, W. Lu, G. Yan, and X. Zhang, 2018, Axtrain: Hardware-oriented neural network training for approximate inference, arXiv preprint arXiv:1805.08309 (2018), https://arxiv.org/abs/1805.08309v1
  26. S. Rehman, W. El-Harouni, M. Shafique, A. Kumar, and J. Henkel, 2016, Architectural-space exploration of approximate multipliers, Proceedings of the 35th International Conference on Computer-Aided Design, ICCAD’16, ACM, New York, NY, USA (2016), pp. 80:1–80:8, https://ieeexplore.ieee.org/abstract/document/7827657, PDF: https://esim-project.eu/files/user/akumar/pdf/ICCAD_2017_ApproxMult.pdf
  27. S. Misailovic, M. Carbin, S. Achour, Z. Qi, M. C. Rinard, 2014, Chisel: reliability- and accuracy-aware optimization of approximate computational kernels, OOPSLA, 309-328, 2014, https://dspace.mit.edu/handle/1721.1/91290
  28. Y. Wang, Y. Qin, D. Deng, J. Wei, Y. Zhou, Y. Fan, T. Chen, H. Sun, L. Liu, S. Wei et al., 2022, A 28nm 27.5 TOPS/W approximate-computing-based transformer processor with asymptotic sparsity speculating and out-of-order computing, in 2022 IEEE International Solid-State Circuits Conference (ISSCC), vol. 65. IEEE, 2022, pp. 1–3, https://ieeexplore.ieee.org/document/9731686
  29. Y Wu, C Chen, W Xiao, X Wang, C Wen, J Han, 2023, A Survey on Approximate Multiplier Designs for Energy Efficiency: From Algorithms to Circuits, arXiv preprint, 2023, https://arxiv.org/abs/2301.12181 (Extensive survey of approximate multiplication methods.)
  30. G Alsuhli, V Sakellariou, H Saleh, M Al-Qutayri, 2023, Number Systems for Deep Neural Network Architectures: A Survey, 2023, https://arxiv.org/abs/2307.05035 (Various number systems have approximate multiplication properties.)
  31. Zixuan Ou, Bing Yu, Wenbin Ye, 2023, An Efficient Algorithm-Hardware Co-Design for Radar-Based Fall Detection With Multi-Branch Convolutions, IEEE Transactions on Circuits and Systems I: Regular Papers, vol.70, no.4, pp.1613-1624, 2023. https://ieeexplore.ieee.org/document/10005051
  32. Mahdi Taheri, Mohammad Hasan Ahmadilivani, Maksim Jenihhin, Masoud Daneshtalab, Jaan Raik, 2023, APPRAISER: DNN Fault Resilience Analysis Employing Approximation Errors, 2023 26th International Symposium on Design and Diagnostics of Electronic Circuits and Systems (DDECS), pp.124-127, 2023. https://ieeexplore.ieee.org/document/10139468, https://arxiv.org/abs/2305.19733
  33. Efstratios Zacharelos, Italo Nunziata, Gerardo Saggese, Antonio G.M. Strollo, Ettore Napoli, 2022, Approximate Recursive Multipliers Using Low Power Building Blocks, IEEE Transactions on Emerging Topics in Computing, vol.10, no.3, pp.1315-1330, 2022. https://ieeexplore.ieee.org/document/9812478
  34. Kah Phooi Seng, Li-Minn Ang, 2022, Embedded Intelligence: State-of-the-Art and Research Challenges, IEEE Access, vol.10, pp.59236-59258, 2022. https://ieeexplore.ieee.org/document/9775683, PDF: https://research.usc.edu.au/esploro/outputs/99640278002621
  35. Antonio Giuseppe Maria Strollo, Ettore Napoli, Davide De Caro, Nicola Petra, Gerardo Saggese, Gennaro Di Meo, 2022, Approximate Multipliers Using Static Segmentation: Error Analysis and Improvements, IEEE Transactions on Circuits and Systems I: Regular Papers, vol.69, no.6, pp.2449-2462, 2022. https://ieeexplore.ieee.org/document/9726786
  36. Haroon Waris, Chenghua Wang, Chenyu Xu, Weiqiang Liu, 2022, AxRMs: Approximate Recursive Multipliers Using High-Performance Building Blocks, IEEE Transactions on Emerging Topics in Computing, vol.10, no.2, pp.1229-1235, 2022. https://ieeexplore.ieee.org/document/9483645
  37. Ying Wu, Chuangtao Chen, Weihua Xiao, Xuan Wang, Chenyi Wen, Jie Han, Xunzhao Yin, Weikang Qian, Cheng Zhuo, 2023, A Survey on Approximate Multiplier Designs for Energy Efficiency: From Algorithms to Circuits, ACM Transactions on Design Automation of Electronic Systems, 2023. https://doi.org/10.1145/3610291, https://arxiv.org/abs/2301.12181 (Extensive survey of many approximate multiplication algorithms.)
  38. Sudeh Shirkavand Saleh Abad, Mohammad Hossein Moaiyeri, 2022, Hardware-accuracy trade-offs for error-resilient applications using an ultra-efficient hybrid approximate multiplier, The Journal of Supercomputing, 2022. https://doi.org/10.1007/s11227-022-04789-6
  39. Giorgos Armeniakos, Georgios Zervakis, Dimitrios Soudris, Jörg Henkel, 2023, Hardware Approximate Techniques for Deep Neural Network Accelerators: A Survey, ACM Computing Surveys, vol.55, no.4, pp.1, 2023. https://doi.org/10.1145/3527156, https://arxiv.org/abs/2203.08737 (Survey of many approximate techniques in AI including logarithmic and non-logarithmic approximate multiplication.)
  40. X. Jiao, V. Akhlaghi, Yu Jiang, and R. K. Gupta. 2018. Energy-efficient neural networks using approximate computation reuse, Proc. of the 2018 Design, Automation and Test in Europe Conference and Exhibition, (DATE) (2018), 1223–1228. https://ieeexplore.ieee.org/document/8342202, PDF: http://wingtecher.com/themes/WingTecherResearch/assets/papers/date18-energy-efficient.pdf (Caches and reuses approximate computations by using Bloom filters, a data structure similar to hashing.)
  41. Ao Ren, Ji Li, Zhe Li, Caiwen Ding, Xuehai Qian, Qinru Qiu, Bo Yuan, Yanzhi Wang, 2017, SC-DCNN: Highly-scalable deep convolutional neural network using stochastic computing, ACM SIGPLAN Notices, vol. 52, no. 4, pp. 405-418, 2017. https://arxiv.org/abs/1611.05939 (Stochastic method with multiplication and addition approximations via AND gates and multiplexers.)

For more research papers on approximate multiplication, see https://www.aussieai.com/research/multiplication#approximate-multiplication.

Logarithmic Approximate Multiplication

The most common method to approximate multiplication is to use addition of the logarithms of two numbers, but more generally than via simple bitshifting. This approach is similar to logarithmic quantization (power-of-two quantization). These papers specifically use logarithmic approximation methods.

  1. P. Gysel, J. Pimentel et al., 2018, Ristretto: A framework for empirical study of resource-efficient inference in convolutional neural networks, IEEE Trans. Neural Netw. Learn. Syst., 2018, https://ieeexplore.ieee.org/abstract/document/8318896
  2. Min Soo Kim; Alberto A. Del Barrio; Leonardo Tavares Oliveira; Román Hermida; Nader Bagherzadeh, 2018, Efficient Mitchell’s Approximate Log Multipliers for Convolutional Neural Networks, IEEE Transactions on Computers, Volume 68 Issue 5, p.660-675, November 2018, https://ieeexplore.ieee.org/abstract/document/8532287
  3. T. Hokchhay, S. Hashemi, R. I. Bahar, and S. Reda, 2017, Hardware-software codesign of accurate, multiplier-free deep neural networks, in Proc. 54th Annu. Design Autom. Conf. (DAC), 2017, pp. 1–6., https://arxiv.org/abs/1705.04288
  4. M. S. Ansari, B. F. Cockburn, and J. Han, 2020, An improved logarithmic multiplier for energy-efficient neural computing, IEEE Transactions on Computers, 2020, https://ieeexplore.ieee.org/document/9086744
  5. J. N. Mitchell, 1962, Computer multiplication and division using binary logarithms, IEEE Trans. Electron. Comput., vol. EC-11, no. 4, pp. 512–517, Aug. 1962, https://ieeexplore.ieee.org/document/5219391
  6. Z. Babic, A. Avramovic, and P. Bulic, 2011, An iterative logarithmic multiplier, Microprocess. Microsyst., vol. 35, no. 1, pp. 23–33, Feb. 2011, https://dl.acm.org/doi/10.1016/j.micpro.2010.07.001
  7. U. Lotric and P. Bulic, 2012, Applicability of approximate multipliers in hardware neural networks, Neurocomput., vol. 96, pp. 57–65, Nov. 2012, https://dl.acm.org/doi/10.1016/j.neucom.2011.09.039
  8. Z. Du, K. Palem, A. Lingamneni, O. Temam, Y. Chen, and C. Wu, 2014, Leveraging the error resilience of machine-learning applications for designing highly energy efficient accelerators, in Proc. 19th Asia South Pacific Des. Autom. Conf., 2014, pp. 201–206, https://pages.saclay.inria.fr/olivier.temam/files/eval/DLCPTW2014.pdf
  9. M. S. Kim, A. A. D. Barrio, R. Hermida, and N. Bagherzadeh, 2018, Low-power implementation of Mitchell’s approximate logarithmic multiplication for convolutional neural networks, in Proc. 23rd Asia South Pacific Des. Autom. Conf., 2018, pp. 617–622, https://ieeexplore.ieee.org/document/8297391 (Approximate logarithm approach using the Logarithm Number System.)
  10. S. S. Sarwar, S. Venkataramani, A. Raghunathan, and K. Roy, 2016, Multiplier-less artificial neurons exploiting error resiliency for energy-efficient neural computing, in Proc. Des. Autom. Test Eur. Conf. Exhib., 2016, pp. 145–150, https://arxiv.org/abs/1602.08557
  11. Rezaei S, Omidi R and Azarpeyvand A. (2022), Logarithm-approximate floating-point multiplier, Microelectronics Journal, 127:C, Volume 127, September 2022, 105521, https://doi.org/10.1016/j.mejo.2022.105521
  12. M. Skrbek, 1999, Fast neural network implementation, Neural Network World 5 (1999), 375–391, https://www.researchgate.net/publication/265303033_Fast_neural_network_implementation (Uses shift-add methods.)
  13. T. Mogami, 2020, Deep neural network training without multiplications, In Beyond BackPropagation WS at 34th Conference on Neural Information Processing Systems, 2020, https://arxiv.org/abs/2012.03458 (This multiplication of floating-point numbers with integer addition is effectively using Mitchell's approximate multiplication.)
  14. G Alsuhli, V Sakellariou, H Saleh, M Al-Qutayri, 2023, Number Systems for Deep Neural Network Architectures: A Survey, 2023, https://arxiv.org/abs/2307.05035
  15. Y Wu, C Chen, W Xiao, X Wang, C Wen, J Han, 2023, A Survey on Approximate Multiplier Designs for Energy Efficiency: From Algorithms to Circuits, arXiv preprint, 2023, https://arxiv.org/abs/2301.12181
  16. Durgesh Nandan; Jitendra Kanungo; Anurag Mahajan, 2017, An efficient VLSI architecture for iterative logarithmic multiplier, 2017 4th International Conference on Signal Processing and Integrated Networks (SPIN), February 2017, https://ieeexplore.ieee.org/document/8049986 (Uses LNS and Mitchell's approximate multiplication algorithm.)
  17. Uroš Lotrič, Ratko Pilipović, Patricio Bulić, 2021, A Hybrid Radix-4 and Approximate Logarithmic Multiplier for Energy Efficient Image Processing, Electronics, vol.10, no.10, pp.1175, 2021. https://doi.org/10.3390/electronics10101175
  18. J Cai, 2022, Log-or-Trig: Towards efficient learning in deep neural networks, Thesis, Graduate School of Engineering, Tokyo University of Agriculture and Technology, https://tuat.repo.nii.ac.jp/?action=repository_action_common_download&item_id=1994&item_no=1&attribute_id=16&file_no=3, PDF: https://tuat.repo.nii.ac.jp/index.php?action=pages_view_main&active_action=repository_action_common_download&item_id=1994&item_no=1&attribute_id=16&file_no=1&page_id=13&block_id=39 (Examines logarithmic LNS multiplication and also trigonometric methods.)
  19. Mark Arnold, 2023, Machine Learning using Logarithmic Arithmetic with Preconditioned Input to Mitchell's Method, 2023 IEEE 5th International Conference on Artificial Intelligence Circuits and Systems (AICAS), https://ieeexplore.ieee.org/abstract/document/10168554/

For more research papers on logarithmic approximate multiplication, see https://www.aussieai.com/research/multiplication#logarithmic-multiplication.

Addition Optimizations

Addition is not the main bottleneck when compared to multiplication, but there are various ways to improve addition, or to use addition in optimization of neural networks.

Addition has a role in optimization techniques such as:

  • Adder networks (and other types of multiplication-free networks)
  • Add-as-integer approximate multiplication
  • Logarithmic models (because logarithms convert multiplications to additions)
  • Binary quantization or ternary quantization (only requires additions and/or subtractions, or neither if bitwise operators used)
  • Approximate addition algorithms
  • Max-Plus networks (using addition and maximum operations)
  • Log-sum-exp (LSE) networks

Research papers on addition optimizations such as approximate addition:

  1. V. Gupta, D. Mohapatra, S.P. Park, A. Raghunathan, 2011, IMPACT: IMPrecise adders for low-power approximate computing, International Symposium on Low Power Electronics and Design (ISLPED), pp. 409–414, 2011, https://dl.acm.org/doi/10.5555/2016802.2016898
  2. V. Gupta, D. Mohapatra, A. Raghunathan, K. Roy, 2013, Low-Power Digital Signal Processing Using Approximate Adders, IEEE Transaction on CAD of Integrated Circuits and Systems 32(1): 124-137, 2013, https://dl.acm.org/doi/10.1109/TCAD.2012.2217962
  3. M. Shafique, W. Ahmad, R. Hafiz, J. Henkel, 2015, A Low Latency Generic Accuracy Configurable Adder, IEEE/ACM Design Automation Conference (DAC), 2015, https://ieeexplore.ieee.org/abstract/document/7167270
  4. R. Ye, T. Wang, F. Yuan, R. Kumar, Q. Xu, 2013, On reconfiguration-oriented approximate adder design and its application, International Conference on Computer-Aided Design (ICCAD), pp.48-54, 2013, PDF: https://www.cse.cuhk.edu.hk/~qxu/ye-iccad13.pdf
  5. J. Miao, K. He, A. Gerstlauer, M. Orshansky, 2012, Modeling and synthesis of quality-energy optimal approximate adders, International Conference on Computer Aided Design (ICCAD), pp. 728-735, 2012, https://ieeexplore.ieee.org/document/6386754
  6. A. B. Kahng, S. Kang, 2012, Accuracy-configurable adder for approximate arithmetic designs, IEEE/ACM Design Automation Conference (DAC), pp.820-825, 2012, https://ieeexplore.ieee.org/document/6241600
  7. S. Mazahir, O. Hasan, R. Hafiz, M. Shafique, J. Henkel, 2016, An Area-Efficient Consolidated Configurable Error Correction for Approximate Hardware Accelerators, ACM/EDAC/IEEE 53rd Design Automation Conference (DAC), 2016, https://ieeexplore.ieee.org/document/7544339
  8. N. Zhu, W.-L. Goh, K.-S. Yeo, 2009, An enhanced low-power high-speed Adder for Error-Tolerant application, 12th International Symposium on Integrated Circuits (ISIC), 2009, https://ieeexplore.ieee.org/document/5403865
  9. Ryu, H. Kim, W. Yi and J.-J. Kim, 2019, BitBlade: Area and energy-efficient precision-scalable neural network accelerator with bitwise summation, Proc. 56th Annu. Design Autom. Conf., pp. 1-6, Jun. 2019. https://ieeexplore.ieee.org/document/8807054
  10. Ao Ren, Ji Li, Zhe Li, Caiwen Ding, Xuehai Qian, Qinru Qiu, Bo Yuan, Yanzhi Wang, 2017, SC-DCNN: Highly-scalable deep convolutional neural network using stochastic computing, ACM SIGPLAN Notices, vol. 52, no. 4, pp. 405-418, 2017. https://arxiv.org/abs/1611.05939 (Stochastic method with multiplication and addition approximations via AND gates and multiplexers.)

For more research papers on optimization of addition arithmetic, see https://www.aussieai.com/research/addition.

Division

Division is an expensive operation, and has been largely avoided in neural networks (with preference given to multiplication, addition and bitwise operators). However, there is some research in regard to division arithmetic. Related research areas include:

  • Division algorithms: Faster ways to implement division, now mainly for hardware designers.
  • Approximate division algorithms
  • Power-of-two quantization. Bitshifting can optimize division, as it can for multiplication. Right bitshift is an obvious optimization for integer division involving power-of-2 divisors. This has relevance in relation to logarithmic quantization.
  • Integer division: For some thoughts on the use of general integer division of weights in quantization, see division quantization.
  • Advanced number system division: See dyadic numbers and dyadic quantization for an obscure number system involving power-of-two division.

I don't think I've seen a paper on using division in a neural network, but here are some research papers on low-level division arithmetic optimization and approximate division:

  1. LibDivide, 2023, https://libdivide.com/ and https://github.com/ridiculousfish/libdivide
  2. Ridiculous Fish, 2021, Benchmarking division and libdivide on Apple M1 and Intel AVX512, May 12th, 2021, https://ridiculousfish.com/blog/posts/benchmarking-libdivide-m1-avx512.html
  3. S. Hashemi, R. Bahar, and S. Reda, 2016, A low-power dynamic divider for approximate applications, Proceedings of the 53rd Annual Design Automation Conference, ACM (2016), p. 105, https://ieeexplore.ieee.org/document/7544348
  4. Suganthi Venkatachalam; Elizabeth Adams; Seok-Bum Ko, May 2019, Design of approximate restoring dividers, 2019 IEEE International Symposium on Circuits and Systems (ISCAS), https://ieeexplore.ieee.org/document/8702363
  5. Chitlu Subhasri, Bhaskara Rao Jammu, L. Guna Sekhar Sai Harsha, Nalini Bodasingi, Visweswara Rao Samoju, 2021, Hardware‐efficient approximate logarithmic division with improved accuracy, Journal of Circuit Theory and Applications, 2021, Wiley Online Library, https://onlinelibrary.wiley.com/doi/abs/10.1002/cta.2900, https://doi.org/10.1002/cta.2900
  6. Mohsen Imani; Ricardo Garcia; Andrew Huang; Tajana Rosing, May 2019, CADE: Configurable approximate divider for energy efficiency, 2019 Design, Automation & Test in Europe Conference & Exhibition (DATE) https://ieeexplore.ieee.org/document/8715112
  7. Hiromasa Nakayama, June 2006, Algorithm computing the local b function by an approximate division algorithm in D, https://www.sciencedirect.com/science/article/pii/S0747717108001375, https://arxiv.org/abs/math/0606437
  8. Jackson Melchert; Setareh Behroozi; Jingjie Li; Younghyun Kim, 2019, SAADI-EC: A quality-configurable approximate divider for energy efficiency, IEEE Transactions on Very Large Scale Integration (VLSI) Systems (Volume 27, Issue 11, November 2019, pp.2680-2692), https://ieeexplore.ieee.org/document/8766885
  9. Reza Zendegani; Mehdi Kamal; Arash Fayyazi; Ali Afzali-Kusha; Saeed Safari; Massoud Pedram, 2016, SEERAD: A high speed yet energy-efficient rounding-based approximate divider, 2016 Design, Automation & Test in Europe Conference & Exhibition (DATE), 14-18 March 2016, https://ieeexplore.ieee.org/document/7459545
  10. X Li, B Liu, RH Yang, V Courville, C Xing, VP Nia, 2023, DenseShift: Towards Accurate and Efficient Low-Bit Power-of-Two Quantization, Proceedings of the IEEE/CVF, https://openaccess.thecvf.com/content/ICCV2023/papers/Li_DenseShift_Towards_Accurate_and_Efficient_Low-Bit_Power-of-Two_Quantization_ICCV_2023_paper.pdf (Shows how division by a power-of-two, which is a bitshift in integers, can be done using integer addition on the sign and exponent bits of a floating-point number.)

For more research on division arithmetic, see https://www.aussieai.com/research/division

End-to-End Integer Arithmetic

Integers everywhere. That's the goal of end-to-end integer arithmetic for inference in a Transformer. The weights and activations as integers is the realm of integer-only arithmetic quantization. But all components also need to be processed as integers to achieve end-to-end integer-only inference.

Integer arithmetic is much faster than parallel arithmetic, for both sequential or parallel computation. Replacing floating-point calculations with integer arithmetic is a well-known optimization and the conversion of AI engines to use integer-only arithmetic has been an ongoing area of research.

In regard to AI, everyone thinks of quantization, which is the most common use of integer arithmetic. Integer quantization has moved from research into the mainstream with commonly used sizes being 16-bit, 8-bit, and even 4-bit integers (see Chapter 44). However, integer quantization does not typically perform all arithmetic in integers, but often converts back and forth from floating-point.

The extension to “integer-only arithmetic quantization” remains an area of research and there is a considerable amount of research being done to create “integer-only engines” for faster AI. A full implementation will need integer arithmetic not just in the weights and MatMuls, but also in the other Transformer components, such as:

  • Integer Softmax
  • Integer activation functions (e.g. RELU is easy)
  • Integer normalization
  • Integer positional encoding

Non-Quantization Integer Research: Quantization is not the only place where integer arithmetic optimizations can be used in AI engines. A list of AI other optimization techniques that involve integer arithmetic includes:

  • Bitshift-add networks
  • Add-as-integer networks
  • Bitwise neural networks
  • Weightless Neural Networks (WNNs)
  • XNOR networks (see also binary quantization)

Research papers on end-to-end integer networks:

  1. J Zhong, Z Liu, X Chen, Apr 2023, Transformer-based models and hardware acceleration analysis in autonomous driving: A survey, https://arxiv.org/abs/2304.10891 (Mainly focused on 8-bit integer arithmetic for machine vision Transformers.)
  2. Zhewei Yao, Zhen Dong, Zhangcheng Zheng, Amir Gholami, Jiali Yu, Eric Tan, Leyuan Wang, Qijing Huang, Yida Wang, Michael Mahoney, Kurt Keutzer, 2021, HAWQ-V3: Dyadic Neural Network Quantization, Proceedings of the 38th International Conference on Machine Learning, PMLR 139:11875-11886, 2021, https://arxiv.org/abs/2011.10680 (Integers only in quantized weights and activations with INT4 or INT8, but also uses integers for batch normalization and residual connection components, too.)
  3. Y. Lin, Y. Li, T. Liu et al., 2020, Towards fully 8-bit integer inference for the transformer model, in Proc. of IJCAI, 2020, pp. 3759–3765. https://arxiv.org/abs/2009.08034 (Integers for weights, but also for Softmax, layer normalization, and other components, by replacing or approximating non-linear functions such as exponential and square-root.)
  4. Peng Peng, Mingyu You, Weisheng Xu, and Jiaxin Li. 2021, Fully integer-based quantization for mobile convolutional neural network inference, Neurocomputing, 432:194–205, 2021, https://www.sciencedirect.com/science/article/abs/pii/S0925231220319354 (Quantizes with INT4, but not only weights, but also has integer batch normalization.)
  5. Sehoon Kim, Amir Gholami, Zhewei Yao, Michael W. Mahoney, Kurt Keutzer, 2021, I-BERT: Integer-only BERT Quantization, Proceedings of the 38th International Conference on Machine Learning, PMLR 139:5506-5518, 2021, https://arxiv.org/abs/2101.01321, https://proceedings.mlr.press/v139/kim21d.html (I-BERT uses quantization, but also has integer arithmetic for GELU, Softmax, and Layer Normalization.)
  6. Dong, Z., Yao, Z., Gholami, A., Mahoney, M. W., Keutzer, K., 2019, HAWQ: Hessian AWare Quantization of neural networks with mixed-precision, In The IEEE International Conference on Computer Vision (ICCV), October 2019. https://ieeexplore.ieee.org/document/9009512, https://arxiv.org/abs/1905.03696 (Early paper that isn't quite end-to-end with integers.)
  7. Ruokai Yin, Yuhang Li, Abhishek Moitra, Priyadarshini Panda, Dec 2022, Training Integer-Only Deep Recurrent Neural Networks, https://arxiv.org/abs/2212.11791 (Integer-only version of RNNs called iRNN, with integer-only layer normalization, integer-only attention, and piecewise linear approximation for integer-only activation functions such as tanh and sigmoid.)
  8. R Yin, Y Li, A Moitra, P Panda, Sep 2023, MINT: Multiplier-less Integer Quantization for Spiking Neural Networks, https://arxiv.org/abs/2305.09850
  9. Shuo Huai, Di Liu, Xiangzhong Luo, Hui Chen, Weichen Liu, Ravi Subramaniam, 2023, Crossbar-Aligned & Integer-Only Neural Network Compression for Efficient In-Memory Acceleration, ASPDAC '23: Proceedings of the 28th Asia and South Pacific Design Automation Conference, January 2023, Pages 234–239, https://doi.org/10.1145/3566097.3567856, https://dl.acm.org/doi/abs/10.1145/3566097.3567856
  10. Z Zhang, B He, Z Zhang, 2023, Practical Edge Kernels for Integer-Only Vision Transformers Under Post-training Quantization, Proceedings of Machine Learning and Systems 5 pre-proceedings (MLSys 2023) mlsys2023, https://proceedings.mlsys.org/paper_files/paper/2023/hash/023560744aae353c03f7ae787f2998dd-Abstract-mlsys2023.html, PDF: https://proceedings.mlsys.org/paper_files/paper/2023/file/023560744aae353c03f7ae787f2998dd-Paper-mlsys2023.pdf (Integer-only-arithmetic quantization with integer-only versions of Softmax, LayerNorm, and GELU.)
  11. Eyyüb Sari, Vanessa Courville, Vahid Partovi Nia, Feb 2022, iRNN: Integer-only Recurrent Neural Network, https://arxiv.org/abs/2109.09828
  12. J Bartels, A Hagihara, L Minati, 2023, An Integer-Only Resource-Minimized RNN on FPGA for Low-Frequency Sensors in Edge-AI, IEEE Sensors Journal, Volume 23, Issue 15, 01 August 2023, https://ieeexplore.ieee.org/abstract/document/10161725/, PDF: https://ieeexplore.ieee.org/iel7/7361/4427201/10161725.pdf
  13. Lin, Y., Zhang, T., Sun, P., Li, Z., and Zhou, S., 2022, FQ-ViT: Post-Training Quantization for Fully Quantized Vision Transformer, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pp. 1173–1179, 2022. https://arxiv.org/abs/2111.13824
  14. A. Rock, A. Untether, O. Khalil, O. Shai, and P. Grouchy, 2022, INT8 Transformers for Inference Acceleration, 36th Conference on Neural Information Processing Systems (NeurIPS), PDF: https://neurips2022-enlsp.github.io/papers/paper_52.pdf

For more research papers on end-to-end integer arithmetic in AI engines, see https://www.aussieai.com/research/integer#end2end.

 

• Next: Chapter 54. Ensemble Multi-AI Research

• Up: Table of Contents

• Buy: Generative AI in C++: Coding Transformers and LLMs

Generative AI in C++ The new AI programming book by Aussie AI co-founders:
  • AI coding in C++
  • Transformer engine speedups
  • LLM models
  • Phone and desktop AI
  • Code examples
  • Research citations

Get your copy from Amazon: Generative AI in C++