Aussie AI

LNS Addition

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

LNS Addition

The biggest area of research is speeding up of LNS addition. Log-domain addition and subtraction are problematic and requires Gaussian logarithm functions to compute. There are various research papers that cover different approximations or methods such as Look-Up Tables (LUTs), Taylor series, interpolations, co-transformations, and other methods.

Other related research. There are several other areas of AI theory that are relevant to LNS addition. Because LNS addition is computing exponentials of log-domain values (i.e. antilogarithms), adding them, and then re-converting them to log-domain, this is a “log of a sum of exponentials” calculation, which is the same as “log-sum-exp networks”. Also, the “sum of exponentials” is the same calculation required for part of Softmax calculations (the denominator), so both hardware acceleration of Softmax (see Chapter 25), and the research theory of Softmax approximation, are relevant. Finally, since the use of the maximum function is one way to approximate LNS addition, the theory of “max-plus networks” based on “tropical algebra” is relevant to optimizing LNS addition.

LNS addition research papers. A lot of work has been done on optimizing LNS addition. Research papers include:

  1. Wikipedia, 2023, Gaussian logarithm, https://en.wikipedia.org/wiki/Gaussian_logarithm
  2. Kouretas I, Basetas C, Paliouras V, 2012, Low-power logarithmic number system addition/subtraction and their impact on digital filters, IEEE Trans Comput 62(11):2196–2209. https://doi.org/10.1109/TC.2012.111, https://ieeexplore.ieee.org/document/6212439 (Coverage of LNS theory, including improvements to addition/subtraction, in relation to digital signal processing.)
  3. I. Orginos, V. Paliouras, and T. Stouraitis, 1995, A novel algorithm for multi-operand Logarithmic Number System addition and subtraction using polynomial approximation, in Proceedings of the 1995 IEEE International Symposium on Circuits and Systems (ISCAS’95), pp. III.1992–III.1995, 1995. https://ieeexplore.ieee.org/document/523812
  4. S. A. Alam, J. Garland, and D. Gregg, 2021, Low-precision logarithmic number systems: Beyond base-2, ACM Transactions on Architecture and Code Optimization (TACO), vol. 18, no. 4, pp. 1–25, 2021. https://arxiv.org/abs/2102.06681 (Covers LNS arithmetic in different bases, with coverage of LNS addition improvements.)
  5. A. Sanyal, P. A. Beerel, and K. M. Chugg, 2020, Neural network training with approximate logarithmic computations, in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2020, pp. 3122–3126. https://arxiv.org/abs/1910.09876 (End-to-end LNS paper that also covers addition approximations.)
  6. M. Arnold, J. Cowles T. Bailey, and J. Cupal, 1991, Implementing back propagation neural nets with logarithmic arithmetic, International AMSE conference on Neural Nets, San Diego, 1991. (Use of LUTs for LNS addition.)
  7. M. G. Arnold, T. A. Bailey, J. J. Cupal, and M. D. Winkel, 1997, On the cost effectiveness of logarithmic arithmetic for backpropagation training on SIMD processors, in Proceedings of International Conference on Neural Networks (ICNN’97), vol. 2. IEEE, 1997, pp. 933–936. https://ieeexplore.ieee.org/document/616150 (Uses LUTs for LNS addition.) li> J. Johnson, 2020, Efficient, arbitrarily high precision hardware logarithmic arithmetic for linear algebra, in Proc. IEEE 27th Symp. Comput. Arithmetic, 2020, pp. 25–32, https://arxiv.org/abs/2004.09313 (Dual-base LNS algorithm, attempting to solve the LNS addition bottleneck.)
  8. P. D. Vouzis, S. Collange and M. G. Arnold, 2008, A Novel Cotransformation for LNS Subtraction, J. Signal Process. Syst., vol. 58, no. 1, pp. 29-40, Oct. 2008. https://doi.org/10.1007/s11265-008-0282-7, https://link.springer.com/article/10.1007/s11265-008-0282-7 (Improving LNS subtraction algorithms.)
  9. D. M. Lewis, 1990, An architecture for addition and subtraction of long word length numbers in the logarithmic number system, ZEEE Trans. Compur., vol. 39, pp. 1325-1336, Nov. 1990. https://ieeexplore.ieee.org/document/61042
  10. H. Henkel, 1989, Improved Addition for the Logarithmic Number System, IEEE Trans. Acoustics Speech and Signal Processing, no. 2, pp. 301-303, Feb. 1989. https://ieeexplore.ieee.org/document/21694 (Improved lookup tables for LNS addition.)
  11. E. E. Swartzlander and A. G. Alexopoulos, 1975, The sign/logarithm number system, IEEE Trans. Comput., vol. C-24, pp. 1238-1242, Dec. 1975. IEEE Transactions on Computers ( Volume C-24, Issue 12, December 1975), https://ieeexplore.ieee.org/document/1672765 (Handle negative numbers in LNS with sign bits.)
  12. I. Kouretas, C. Basetas and V. Paliouras, 2008, Low-Power Logarithmic Number System Addition/Subtraction and their Impact on Digital Filters, Proc. IEEE Int'l Symp. Circuits and Systems (ISCAS '08), pp. 692-695, 2008. https://ieeexplore.ieee.org/document/4541512 (Improvements for slow addition/subtraction of LNS numbers.)
  13. M. Arnold and S. Collange, 2011, A Real/Complex Logarithmic Number System ALU, IEEE Trans. Computers, vol. 60, no. 2, pp. 202-213, Feb. 2011. https://ieeexplore.ieee.org/document/5492676 (Hardware FPGAs and improvements to LNS addition.)
  14. R.C. Ismail and J.N. Coleman, 2011, ROM-less LNS, Proc. IEEE Symp. Computer Arithmetic, pp. 43-51, 2011. https://ieeexplore.ieee.org/document/5992107 (Improvements to LNS addition and lookup tables.)
  15. R. Muscedere, V. Dimitrov, G. Jullien and W. Miller, 2005, Efficient Techniques for Binary-to-Multidigit Multidimensional Logarithmic Number System Conversion using Range-Addressable Look-Up Tables, IEEE Trans. Computers, vol. 54, no. 3, pp. 257-271, Mar. 2005. https://ieeexplore.ieee.org/document/1388191 (Presents multidimensional logarithmic number system (MDLNS) and improvements to LNS addition lookup tables.)
  16. D Primeaux, 2005, Programming with Gaussian logarithms to compute the approximate addition and subtraction of very small (or very large) positive numbers, Sixth International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing and First ACIS International Workshop on Self-Assembling Wireless Network, https://ieeexplore.ieee.org/document/1434878/
  17. CH Cotter, 1971, Gaussian logarithms and navigation, The Journal of Navigation, cambridge.org, https://www.cambridge.org/core/journals/journal-of-navigation/article/gaussian-logarithms-and-navigation/411E21946EDD70EE4208912BE743C5FB PDF: http://www.siranah.de/sources/Gaussian_Logarithms_and_Navigation.pdf
  18. Paliouras, V., and Stouraitis, T., 1996. A novel algorithm for accurate logarithmic number system subtraction, Proceedings of the IEEE International Symposium on Circuits and Systems (ICAS 96). Atlanta, USA, pp. 268-271. https://ieeexplore.ieee.org/document/542021
  19. MG Arnold, 2004, LPVIP: A low-power ROM-less ALU for low-precision LNS, International Workshop on Power and Timing Modeling, https://link.springer.com/chapter/10.1007/978-3-540-30205-6_69, PDF: https://www.researchgate.net/profile/Mark-Arnold-13/publication/220799326_LPVIP_A_low-power_ROM-less_ALU_for_low-precision_LNS/links/54172bc30cf2218008bed8c8/LPVIP-A-low-power-ROM-less-ALU-for-low-precision-LNS.pdf
  20. MG Arnold, J Cowles, T Bailey, 1988, Improved accuracy for logarithmic addition in DSP applications, ICASSP-88, https://ieeexplore.ieee.org/document/196947, PDF: https://www.computer.org/csdl/proceedings-article/icassp/1988/00196947/12OmNvlPkAA
  21. J. N. Coleman, R.C. Ismail, 2015, LNS with Co-Transformation Competes with Floating-Point, January 2015, IEEE Transactions on Computers 65(1):1-1, DOI:10.1109/TC.2015.2409059, https://ieeexplore.ieee.org/document/7061396, PDF: https://www.researchgate.net/publication/273914447_LNS_with_Co-Transformation_Competes_with_Floating-Point
  22. Siti Zarina Md Naziri; Rizalafande Che Ismail; Ali Yeon Md Shakaff, December 2014 The Design Revolution of Logarithmic Number System Architecture, DOI:10.13140/RG.2.1.3494.4166 Conference: 2014 2nd International Conference on Electrical, Electronic and Systems Engineering (ICEESE 2104)At: Berjaya Times Square, Kuala Lumpur, Malaysia, https://ieeexplore.ieee.org/document/7154603 (Good survey of LNS addition methods up to 2014.)
  23. Siti Zarina Md Naziri, Rizalafande Che Ismail, Ali Yeon Md Shakaff, 2016, Implementation of LNS addition and subtraction function with co-transformation in positive and negative region: A comparative analysis, Aug 2016, https://www.researchgate.net/publication/312159669_Implementation_of_LNS_addition_and_subtraction_function_with_co-transformation_in_positive_and_negative_region_A_comparative_analysis, PDF: https://www.researchgate.net/publication/287533531_Arithmetic_Addition_and_Subtraction_Function_of_Logarithmic_Number_System_in_Positive_Region_An_Investigation/link/56777a6208ae125516ec1034/download
  24. Siti Zarina Md Naziri; Rizalafande Che Ismail; Ali Yeon Md Shakaff, Dec 2015, Arithmetic Addition and Subtraction Function of Logarithmic Number System in Positive Region: An Investigation, 2015 IEEE Student Conference on Research and Development (SCOReD), https://ieeexplore.ieee.org/document/7449376
  25. G Tsiaras, V Paliouras, 2017, Multi-operand logarithmic addition/subtraction based on Fractional Normalization, 2017 6th International Conference on Modern Circuits and Systems Technologies (MOCAST), https://ieeexplore.ieee.org/abstract/document/7937686/
  26. G. Tsiaras and V. Paliouras, 2017, Logarithmic Number System addition-subtraction using Fractional Normalization, in IEEE International Symposium on Circuits and Systems (ISCAS), 2017. https://ieeexplore.ieee.org/document/8050569
  27. B Parhami, 2020, Computing with logarithmic number system arithmetic: Implementation methods and performance benefits, Computers & Electrical Engineering, Elsevier, PDF: https://web.ece.ucsb.edu/~parhami/pubs_folder/parh20-cee-comp-w-lns-arithmetic-final.pdf (Overview of LNS including LNS addition and hardware implementations.)
  28. B. Parhami, “Computing with Logarithmic Number System Arithmetic (Extended Online Version with More Reference Citations),” August 2020. https://web.ece.ucsb.edu/~parhami/pubs_folder/parh20-caee-comput-w-lns-arith.pdf
  29. R.C Ismail; R. Hussin; S.A.Z Murad, 2012, Interpolator algorithms for approximating the LNS addition and subtraction: Design and analysis, 2012 IEEE International Conference on Circuits and Systems (ICCAS), https://ieeexplore.ieee.org/document/6408336, PDF: https://www.researchgate.net/profile/Sohiful-Anuar-Zainol-Murad/publication/259921136_Interpolator_Algorithms_for_Approximating_the_LNS_Addition_and_Subtraction_Design_and_Analysis/links/02e7e52e8a7bef3d52000000/Interpolator-Algorithms-for-Approximating-the-LNS-Addition-and-Subtraction-Design-and-Analysis.pdf
  30. C Chen, 2009, Error analysis of LNS addition/subtraction with direct-computation implementation, IET Computers & Digital Techniques, Volume 3, Issue 4, https://digital-library.theiet.org/content/journals/10.1049/iet-cdt.2008.0098
  31. Chichyang Chen; Rui-Lin Chen; Chih-Huan Yang, 2000, Pipelined computation of very large word-length LNS addition/subtraction with polynomial hardware cost, IEEE Transactions on Computers (Volume 49, Issue 7, July 2000), https://ieeexplore.ieee.org/document/863041
  32. Siti Zarina Md Naziri; Rizalafande Che Ismail; Ali Yeon Md Shakaff, 2016, An Analysis of Interpolation Implementation for LNS Addition and Subtraction Function in Positive Region, 2016 International Conference on Computer and Communication Engineering (ICCCE) https://ieeexplore.ieee.org/abstract/document/7808368/
  33. I Osinin, 2019, Optimization of the hardware costs of interpolation converters for calculations in the logarithmic number system, International Conference on Information Technologies, ICIT 2019: Recent Research in Control Engineering and Decision Making, pp. 91–102, https://link.springer.com/chapter/10.1007/978-3-030-12072-6_9

For more research papers on addition and subtraction issues for LNS models, see https://www.aussieai.com/research/logarithmic#addition.

 

• Next:

• 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++