Shift-Add Networks

Shift-Add Networks

Multiplication can be simulated via bitshifts and addition. There are two basic ideas:

• Use shift counts as weights.
• Approximate multiplication with shifts and adds.

The first idea is to use a single bitshift instead of multiplication (without any addition). This is called “power-of-two quantization” or “logarithmic quantization” because the shift-count weights are stored as integer-truncated log2 of the original weights. See Chapter 44 for more on the logarithmic quantization technique.

The second alternative are the “shift-add” networks, which mimic multiplications using bitshifting and addition. Papers on “shift-add networks” using a combination of bitshift and addition for zero-multiplication:

Research papers on shift-add neural networks:

1. Haoran You, Huihong Shi, Yipin Guo, Yingyan (Celine) Lin, 2023, ShiftAddViT: Mixture of Multiplication Primitives Towards Efficient Vision Transformer, arXiv preprint arXiv:2306.06446, https://arxiv.org/abs/2306.06446 (Uses a combination of addition and shifting.)
2. You H, Chen X, Zhang Y, Li C, Li S, Liu Z, Wang Z, Lin Y., 2020, Shiftaddnet: A hardware-inspired deep network, In: Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., Lin, H. (eds.) Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, Virtual, https://arxiv.org/abs/2010.12785
3. Abhishek Ramdas Nair, Pallab Kumar Nath, Shantanu Chakrabartty, Chetan Singh Thakur, 2022, Multiplierless MP-Kernel Machine For Energy-efficient Edge Devices, https://arxiv.org/pdf/2106.01958 (Uses addition, shift, comparison, and underflow/overflow operations.)
4. Haoran You, Xiaohan Chen, Yongan Zhang, Chaojian Li, Sicheng Li, Zihao Liu, Zhangyang Wang, and Yingyan Lin. 2020, Shiftaddnet: A hardware-inspired deep network, In NeurIPS, 2020, https://arxiv.org/abs/2010.12785
5. J. Faraone et al., 2020, AddNet: Deep neural networks using FPGA-optimized multipliers, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 28, no. 1, pp. 115–128, Jan. 2020. https://ieeexplore.ieee.org/document/8848603, https://arxiv.org/abs/1911.08097 (Uses bitshift and addition instead of multiplication.)

For more research papers on shift-add networks, see https://www.aussieai.com/research/zero-multiplication#shiftadd.

• Next: • Up: Table of Contents • Buy: Generative AI in C++: Coding Transformers and LLMs

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