Aussie AI

55. Advanced Number Systems

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

“The great book of nature is written in mathematical language.”

— Galileo Galilei.

 

 

The methods that computers use to represent numbers are mostly arbitrary. They are based on standardization that occurred years ago, and re-exploring these bit layouts has already yielded faster AI methods (e.g. bfloat16 from Google Research). There is much theoretical research on advanced mathematics and this has recently been applied to optimizing inference algorithms and training. The main areas of research focus include:

  • Numeric bit representations
  • Advanced number systems

Numeric bit representations refer to the bit layouts for integers or floating-point numbers. Integer representations are not changing much, but there's still a choice between one's complement and two's complement to explore. Floating-pointer bit representations, such as modifications to the IEEE 754 floating-point standard, remain an ongoing area of advancements.

Various alternative number systems have been used in computer software and hardware. They have different trade-offs in terms of precision and arithmetic complexity. Several of these have been examined in terms of model inference algorithms, mainly to reduce the number of multiplications. The main ones include:

  • Dyadic numbers
  • Residue Number System (RNS)
  • Posit Number System (PNS)
  • Logarithmic Number System (LNS)

Dyadic numbers, RNS, and PNS have all been applied to AI engines (see below). LNS is an additive method with an extensive amount of theory (see Chapter 52)

If you enjoy this kind of stuff, or if you need a way to get your infant to go to sleep without driving around the block a hundred times, there's also some obscure ones:

  • Tropical algebra (related to Max-Plus networks).
  • Minimax algebra (related to tropical algebra)
  • Double-Base Number System (DBNS)
  • Multiple-Base Number System (MBNS)
  • Multi-Dimensional Logarithmic Number System (MDLNS)
  • Semi-Logarithmic Number System (SLNS)

Advanced Numeric Bit Representations

Although much research focuses on 16-bit floating-point or integer representations of weights, there are some more novel and interesting alternatives. Programmers are used to the current ways that computers store numbers into bits, but these are just traditions, and arose via various trade-offs that may no longer apply with modern increases in computing power. Another type of bit representation that may be important is Posit numbers (see below). None of these newer bit arrangement techniques seem to be in widespread usage yet, but given the success of bfloat16, it's possible that a significant breakthrough still lies in this area of research.

Some of the research papers on floating-point alternative representations include:

  1. Peter Lindstrom, Scott Lloyd, Jeffrey Hittinger, March 28th, 2018, Universal Coding of the Reals: Alternatives to IEEE Floating-Point, CoNGA, https://dl.acm.org/doi/10.1145/3190339.3190344
  2. Jeff Johnson, November 2018, "Making floating-point math highly efficient for AI hardware", Meta (Facebook Research), https://engineering.fb.com/2018/11/08/ai-research/floating-point-math/
  3. G Alsuhli, V Sakellariou, H Saleh, M Al-Qutayri, 2023, Number Systems for Deep Neural Network Architectures: A Survey, https://arxiv.org/abs/2307.05035

For more research papers on the bit representations for floating-point (or integers), see also https://www.aussieai.com/research/advanced-ai-mathematics#bits.

Dyadic Numbers

One type of numeric representation that has received some specific attention in relation to neural networks is dyadic numbers (or “dyadic rationals”). These are rational numbers represented as a division with an integer numerator and a power-of-two denominator. Hence, the number system actually represents them as a pair of two numbers. Although doubling the number of weights doesn't sound like much of an optimization at first glance, the top number allows integer arithmetic to be used, and the bottom number is an integer power-of-two, which allows bitshifting. It may also be possible to use a scaled dyadic engine that pushes the numerator into higher-order integers, and defers the bitshift of the denominator to a less-frequent operation.

Research papers on dyadic numbers:

  1. 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
  2. Nilsson, J. 2009, On numbers badly approximable by dyadic rationals, Isr. J. Math. 171, 93–110 (2009), https://doi.org/10.1007/s11856-009-0042-9
  3. C. Avalos-Ramos, J. A. Felix-Algandar, J. A. Nieto, 2020, Dyadic Rationals and Surreal Number Theory, IOSR Journal of Mathematics (IOSR-JM), e-ISSN: 2278-5728, p-ISSN: 2319-765X. Volume 16, Issue 5 Ser. IV (Sep– Oct 2020), p.35-43, www.iosrjournals.org, PDF: https://www.academia.edu/download/64798757/E1605043543.pdf

For more research papers on dyadic numbers, see also https://www.aussieai.com/research/advanced-ai-mathematics#dyadic. Note: see also dyadic quantization in Chapter 44.

Residue Number System

The residue number system is an alternative method for approximating floating-point arithmetic with integers. The method represents numbers as integers using modulo arithmetic with multiple prime numbers. Hence, it is based on the “residues” (remainders) of division by multiple primes. The opportunities for efficiency when applied to AI include integer arithmetic and special properties of non-carry and parallel addition in modulo arithmetic.

Research papers on the residue number system:

  1. JK Lee, L Mukhanov, AS Molahosseini, 2023, Resource-Efficient Convolutional Networks: A Survey on Model-, Arithmetic-, and Implementation-Level Techniques, https://dl.acm.org/doi/abs/10.1145/3587095, PDF: https://dl.acm.org/doi/pdf/10.1145/3587095
  2. Zhi-Gang Liu and Matthew Mattina, 2020, Efficient residue number system based Winograd convolution, In Proceedings of the European Conference on Computer Vision (ECCV’20). 53–6, https://arxiv.org/abs/2007.12216
  3. S. Salamat, M. Imani, S. Gupta, and T. Rosing, 2018, RNSnet: In-memory neural network acceleration using residue number system, In Proceedings of the 2018 IEEE International Conference on Rebooting Computing (ICRC’18), 1–12, https://ieeexplore.ieee.org/document/8638592
  4. N. Samimi, M. Kamal, A. Afzali-Kusha, and M. Pedram, 2020, Res-DNN: A residue number system-based DNN accelerator unit, IEEE Transactions on Circuits and Systems I: Regular Papers 67, 2 (2020), 658–671, https://ieeexplore.ieee.org/document/8903528
  5. G Alsuhli, V Sakellariou, H Saleh, M Al-Qutayri, 2023, Number Systems for Deep Neural Network Architectures: A Survey, https://arxiv.org/abs/2307.05035
  6. CY Hung, B Parhami, 1994, An approximate sign detection method for residue numbers and its application to RNS division, Computers & Mathematics with Applications, Elsevier, https://doi.org/10.1016/0898-1221(94)90052-3, https://www.sciencedirect.com/science/article/pii/0898122194900523
  7. Molahosseini AS, De Sousa LS, Chang C-H, 2017, Embedded systems design with special arithmetic and number systems, Springer. https://doi.org/10.1007/978-3-319-49742-6, https://link.springer.com/book/10.1007/978-3-319-49742-6 (A text that contains multiple papers on LNS and RNS.)
  8. V Arrigoni, B Rossi, P Fragneto, G Desoli, 2017, Approximate operations in Convolutional Neural Networks with RNS data representation, ESANN, 2017, https://www.esann.org/sites/default/files/proceedings/legacy/es2017-30.pdf
  9. Hiroki Nakahara and Tsutomu Sasao. 2015, A deep convolutional neural network based on nested residue number system, In International Conference on Field Programmable Logic and Applications, 2015, https://ieeexplore.ieee.org/document/7293933
  10. Nicholas S Szabo and Richard I Tanaka. 1967, Residue arithmetic and its applications to computer technology, McGraw-Hill, 1967, https://www.amazon.com/Residue-Arithmetic-Application-Computer-Technology/dp/0070626596/

For more research papers on the residue number system, see also https://www.aussieai.com/research/advanced-ai-mathematics#residue.

Posit Number System

The posit number system is an alternative floating-point arithmetic using multiple exponent fields, where one of the fields is the “regime” of the exponent. Posit numbers have been used in neural networks as an alternative to floating-point numbers in various research papers, and the area seems close to a breakthrough into more mainstream usage. There are hardware versions of posit number computations and “posit quantization” is also possible.

Research papers on the posit number system:

  1. JK Lee, L Mukhanov, AS Molahosseini, 2023, Resource-Efficient Convolutional Networks: A Survey on Model-, Arithmetic-, and Implementation-Level Techniques, https://dl.acm.org/doi/abs/10.1145/3587095, PDF: https://dl.acm.org/doi/pdf/10.1145/3587095
  2. Z. Carmichael, H. F. Langroudi, C. Khazanov, J. Lillie, J. L. Gustafson, and D. Kudithipudi, 2019, Deep positron: A deep neural network using the posit number system, In Proceedings of the 2019 Design, Automation, and Test in Europe Conference and Exhibition (DATE’19). 1421–1426, https://arxiv.org/abs/1812.01762
  3. Zachariah Carmichael, Hamed F. Langroudi, Char Khazanov, Jeffrey Lillie, John L. Gustafson, and Dhireesha Kudithipudi, 2019, Performance-efficiency trade-off of low-precision numerical formats in deep neural networks, In Proceedings of the 2019 Conference for Next Generation Arithmetic (CoNGA’19), ACM, New York, NY, Article 3, 9 pages, https://doi.org/10.1145/3316279.3316282
  4. G Alsuhli, V Sakellariou, H Saleh, M Al-Qutayri, 2023, Number Systems for Deep Neural Network Architectures: A Survey, https://arxiv.org/abs/2307.05035 (Survey of number systems with good coverage of Posits.)
  5. Jinming Lu, Siyuan Lu, Zhisheng Wang, Chao Fang, Jun Lin, Zhongfeng Wang, Li Du, Sep 2019, Training Deep Neural Networks Using Posit Number System, 2019 32nd IEEE International System-on-Chip Conference (SOCC), https://ieeexplore.ieee.org/abstract/document/9088105/, https://arxiv.org/pdf/1909.03831
  6. Raul Murillo, Alberto A. Del Barrio, Guillermo Botella, Min Soo Kim, HyunJin Kim, Nader Bagherzadeh, R Murillo, 2021, PLAM: A posit logarithm-approximate multiplier, https://arxiv.org/pdf/2102.09262
  7. F. de Dinechin, L. Forget, J.-M. Muller, and Y. Uguen, 2019, Posits: the good, the bad and the ugly, in Proceedings of the Conference for Next Generation Arithmetic 2019. New York, NY, USA: ACM, mar 2019, pp. 1–10. https://dl.acm.org/doi/10.1145/3316279.3316285
  8. R. Murillo, A. A. Del Barrio, and G. Botella, 2020, Deep PeNSieve: A deep learning framework based on the posit number system, Digital Signal Processing, vol. 102, p. 102762, Jul 2020. https://www.sciencedirect.com/science/article/abs/pii/S105120042030107X (An example of “posit quantization”.)
  9. H. F. Langroudi, Z. Carmichael, and D. Kudithipudi, 2019, Deep Learning Training on the Edge with Low-Precision Posits, arXiv e-prints, pp. 1474–1479, Jul 2019. https://arxiv.org/abs/1907.13216
  10. M. K. Jaiswal and H. K. So, 2018, Universal number posit arithmetic generator on FPGA, in 2018 Design, Automation & Test in Europe Conference & Exhibition (DATE), vol. 2018-Janua. IEEE, mar 2018, pp. 1159–1162. https://ieeexplore.ieee.org/document/8342187
  11. R. Chaurasiya et al., 2018, Parameterized Posit Arithmetic Hardware Generator, in 2018 IEEE 36th International Conference on Computer Design (ICCD). IEEE, oct 2018, pp. 334–341. https://ieeexplore.ieee.org/document/8615707
  12. M. K. Jaiswal and H. K. So, 2019, PACoGen: A hardware posit arithmetic core generator, IEEE Access, vol. 7, pp. 74 586–74 601, 2019. https://ieeexplore.ieee.org/document/8731915
  13. Y. Uguen, L. Forget, and F. de Dinechin, 2019, Evaluating the Hardware Cost of the Posit Number System, in 2019 29th International Conference on Field Programmable Logic and Applications (FPL). IEEE, Sep 2019, pp. 106–113. https://ieeexplore.ieee.org/document/8892116
  14. R. Murillo, A. A. Del Barrio, and G. Botella, 2020, Customized posit adders and multipliers using the FloPoCo core generator, in 2020 IEEE International Symposium on Circuits and Systems (ISCAS). IEEE, oct 2020, pp. 1–5. https://ieeexplore.ieee.org/document/9180771
  15. M. Cococcioni, F. Rossi, E. Ruffaldi, and S. Saponara, 2020, Fast deep neural networks for image processing using posits and ARM scalable vector extension, Journal of Real-Time Image Processing volume 17, pages 759–771 (2020), https://link.springer.com/article/10.1007/s11554-020-00984-x
  16. Jinming Lu; Chao Fang; Mingyang Xu; Jun Lin; Zhongfeng Wang, 2020, Evaluations on Deep Neural Networks Training Using Posit Number System, IEEE Transactions on Computers, vol. 14, no. 8, pp. 1–1, 2020. https://ieeexplore.ieee.org/document/9066876
  17. M. K. Jaiswal and H. K. So, 2018, Architecture Generator for Type-3 Unum Posit Adder/Subtractor, in 2018 IEEE International Symposium on Circuits and Systems (ISCAS), vol. 2018-May. IEEE, 2018, pp. 1–5. https://ieeexplore.ieee.org/document/8351142
  18. J. L. Gustafson and I. Yonemoto, 2017, Beating Floating-Point at its Own Game: Posit Arithmetic, Supercomputing Frontiers and Innovations, vol. 4, no. 2, pp. 71–86, Jun 2017, https://dl.acm.org/doi/10.14529/jsfi170206, PDF: https://gwern.net/doc/ai/nn/sparsity/low-precision/2017-gustafson.pdf
  19. S. H. F. Langroudi, T. Pandit and D. Kudithipudi, 2018, Deep learning inference on embedded devices: Fixed-point vs posit, Proc. 1st Workshop Energy Efficient Mach. Learn. Cognit. Comput. Embedded Appl. (EMC2), pp. 19-23, Mar. 2018. https://arxiv.org/abs/1805.08624

For more research papers on the posit number system, see also https://www.aussieai.com/research/advanced-ai-mathematics#posit.

Tropical Algebra (Max-Plus)

Tropical algebra is a number system based on addition and maximum operations. The “max-plus” tropical algebra can be used to analyze zero-multiplication AI models that use addition and maximum functions; see Max-Plus networks. There is also a “min-plus” tropical algebra using minimum and addition operations. The tropical algebra is also closely related to the “minimax” algebra.

Some other areas of theory are somewhat related to tropical algebra. One method to approximate Logarithmic Number System (LNS) addition is to use maximum and addition. Also related is the calculation of Softmax, so tropical algebra may have relevance to approximation of Softmax using maximum and addition.

Research papers on tropical algebra:

  1. L. Zhang, G. Naitzat, and L.-H. Lim, 2018, Tropical geometry of deep neural networks, in Proc. Int’l Conf. on Machine Learning, vol. 80, pp. 5824–5832, PMLR, 2018. https://arxiv.org/abs/1805.07091 (Analysis of neural network architecture using tropical algebra.)
  2. P. Maragos, V. Charisopoulos, and E. Theodosis, 2021, Tropical Geometry and Machine Learning, https://ieeexplore.ieee.org/document/9394420
  3. G Smyrnis, P Maragos, 2019, Tropical polynomial division and neural networks, arXiv preprint arXiv:1911.12922, https://arxiv.org/abs/1911.12922 (Lots of tropical algebra theory, but also a neural network approximation tested.)
  4. V. Charisopoulos and P. Maragos, 2018, A tropical approach to neural networks with piecewise linear activations, arXiv preprint arXiv:1805.08749, https://arxiv.org/abs/1805.08749
  5. Diane Maclagan and Bernd Sturmfels. Introduction to tropical geometry, volume 161. American Mathematical Soc., 2015, https://bookstore.ams.org/gsm-161
  6. Wikipedia, 2023, Tropical geometry, https://en.wikipedia.org/wiki/Tropical_geometry
  7. Smyrnis G and Maragos P., 2020, Multiclass neural network minimization via tropical Newton polytope approximation, Proceedings of the 37th International Conference on Machine Learning. (9068-9077). /doi/10.5555/3524938.3525779

For more research papers on the tropical algebra, see also https://www.aussieai.com/research/advanced-ai-mathematics#tropical.

MiniMax Algebra

The minimax algebra is a relative of the tropical algebra. Whereas tropical algebra uses maximum and addition, minimax also adds the minimum operation, but in a different way to the “min-plus” version of tropical algebra. Papers on minimax algebra:

Research papers on MiniMax algebra:

  1. R. Cuninghame-Green, 1979. Minimax Algebra, Springer-Verlag, https://books.google.com.au/books/about/Minimax_Algebra.html?id=l7z_CAAAQBAJ&redir_esc=y

For more research papers on the MiniMax algebra, see also https://www.aussieai.com/research/advanced-ai-mathematics#minimax.

Log-Sum-Exp Networks

Log-sum-exp (LSE) networks involve the formula that is a triple sequence on a vector of numbers: take the logarithm of a sum of exponentials. This is a theoretically interesting area, but not a mainstream neural network architecture.

Haven't we seen the log-sum-exp pattern elsewhere? Yes, several other areas of research are related to log-sum-exp theory. Because logarithmic number system (LNS) addition involves computing exponentials of log-domain values (i.e. antilogarithms), adding them, and then re-converting them to log-domain, this is also emulating a “log of a sum of exponentials” calculation. Hence, log-sum-exp theory relates to approximating LNS addition (for a zero-multiplication logarithmic model). Also, the “sum of exponentials” is the same as the calculation required for the denominator of Softmax calculations, so log-sum-exp theory is also indirectly related to Softmax approximation. Finally, since the use of the maximum function is one way to approximate log-sum-exp (and also LNS addition), the theory of “max-plus networks” based on “tropical algebra” is indirectly related to log-sum-exp networks.

Research papers on Log-Sum-Exp networks:

  1. GC Calafiore, C Possieri, 2020, Efficient model-free Q-factor approximation in value space via log-sum-exp neural networks, 2020 European Control Conference, https://ieeexplore.ieee.org/abstract/document/9143765/, PDF: https://core.ac.uk/download/pdf/327178231.pdf
  2. G. Calafiore, S. Gaubert, and C. Possieri, 2019, Log-sum-exp neural networks and posynomial models for convex and log-log-convex data, IEEE Transactions on Neural Networks and Learning Systems, 2019. https://ieeexplore.ieee.org/abstract/document/8715799/, https://arxiv.org/pdf/1806.07850
  3. GC Calafiore, S Gaubert, 2020, A universal approximation result for difference of log-sum-exp neural networks, IEEE Transactions on Neural Networks and Learning Systems (Volume 31, Issue 12, December 2020), https://ieeexplore.ieee.org/abstract/document/9032340/, PDF: https://arxiv.org/pdf/1905.08503

For more research papers on the Log-Sum-Exp algebra, see also https://www.aussieai.com/research/advanced-ai-mathematics#logsumexp.

Trigonometric Approximations

A very surprising method to replace multiplications with addition is to do so using trigonometric approximations. Note that this is not the same topic as “trigonometric neural networks” in other papers. I'm not sure that using sine and cosine instead of multiplication is going to catch on, but it sure is interesting.

Research papers on trigonometric approximation models:

  1. Jingyong Cai, Masashi Takemoto,Yuming Qiu andHironori Nakajo, 2021, Trigonometric Inference Providing Learning in Deep Neural Networks, Appl. Sci. 2021, 11(15), 6704; https://doi.org/10.3390/app11156704, https://www.mdpi.com/2076-3417/11/15/6704, PDF: https://www.mdpi.com/2076-3417/11/15/6704/pdf
  2. Jingyong 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 LNS and trigonometric approximations.)

For more research papers on inefficient trigonometric approximations, see also https://www.aussieai.com/research/advanced-ai-mathematics#trig.

Double-Base Number System (DBNS)

The DBNS is an advanced number system, where a number is represented by two or more bases, rather than a normal base number with only a single base. In non-DBNS, decimal is base 10, and binary is base 2. But in DBNS, you can have a “base 2 and 3” number, which is the sum of multiples of 2 and 3.

You can also have more than 2 bases, in which case it is called the Multiple-Base Number System (MBNS). Note that there is also an extension of the logarithmic number system (LNS) called Multi-dimensional LNS (MDLNS).

Research papers on the double-base number system:

  1. R. Muscedere, G.A. Jullien,V. Dimitrov, W.C. Miller, 2000, Non-linear signal processing using index calculus DBNS arithmetic, Proc. of the 2090 SPIE conf: on Advanced Algorithms and Architectures in Signal Processing, San Diego, August 2000, https://spie.org/Publications/Proceedings/Paper/10.1117/12.406502?SSO=1
  2. R. Muscedere, G.A. Jullien, V.S. Dimitrov and W.C. Miller, 2000, On efficient techniques for difficult operations in one and two-digit DBNS index calculus, Conference Record of the Thirty-Fourth Asilomar Conference on Signals, Systems and Computers (Cat. No.00CH37154), Oct. 2000, https://ieeexplore.ieee.org/document/910637
  3. Vassil Dimitrov, Graham Jullien, Roberto Muscedere, 2012, Multiple-Base Number System: Theory and Applications (Circuits and Electrical Engineering Book 2), Part of: Circuits and Electrical Engineering (2 books), Jan 24, 2012 https://www.amazon.com/Multiple-Base-Number-System-Applications-Engineering-ebook/dp/B00847CSAG/
  4. Jiajia Chen & Chip-Hong Chang, 2017, Double-Base Number System and Its Application in FIR Filter Design, Embedded Systems Design with Special Arithmetic and Number Systems, pp. 277–310, https://link.springer.com/chapter/10.1007/978-3-319-49742-6_11
  5. V. S. Dimitrov, G. A. Jullien, and W. C. Liller, 1999, Theory and applications of the double-base number system, IEEE Trans. Comput., vol. 48, no. 10, pp. 1098–1106, Oct. 1999. https://ieeexplore.ieee.org/document/805158
  6. Jiajia Chen; Chip-Hong Chang; Feng Feng; Weiao Ding; Jiatao Ding, 2015, Novel Design Algorithm for Low Complexity Programmable FIR Filters Based on Extended Double Base Number System, IEEE Transactions on Circuits and Systems I: Regular Papers ( Volume 62, Issue 1, January 2015), https://ieeexplore.ieee.org/document/6914616
  7. V. S. Dimitrov, L. Imbert, and A. Zakaluzny, 2007, Multiplication by a constant is sublinear, in Proc. 18th IEEE Symp. Comput. Arith., Montpellier, France, Jun. 2007, pp. 261–268. https://ieeexplore.ieee.org/abstract/document/4272873

For more research papers on double-base number systems, see also https://www.aussieai.com/research/advanced-ai-mathematics#dbns.

Hybrid Number Systems

As if the DBNS/MBNS systems were not enough, there are various “hybrid” number systems that combine features from two or more different number systems. Another idea is a “dynamic number system” which is a hybrid system, where the model changes aspects or parameters of its number systems on the fly during inference or training.

Research papers on hybrid number systems:

  1. G Alsuhli, V Sakellariou, H Saleh, M Al-Qutayri, 2023, Number Systems for Deep Neural Network Architectures: A Survey, https://arxiv.org/abs/2307.05035 (This survey paper has a section on hybrid number systems and dynamic number systems.)

For more research papers on hybrid number systems, see also https://www.aussieai.com/research/advanced-ai-mathematics#hybrid.

 

• Next: Chapter 56. Dynamic NAS

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