Journal of Computer Science and Technology ›› 2023, Vol. 38 ›› Issue (2): 298-308.doi: 10.1007/s11390-023-2572-8

Special Issue: Computer Architecture and Systems

• Special Section on Approximate Computing Circuits and Systems • Previous Articles     Next Articles

LMM: A Fixed-Point Linear Mapping Based Approximate Multiplier for IoT

Ying Wu1 (吴 莹), Chen-Yi Wen1 (温晨怡), Xun-Zhao Yin1 (尹勋钊), and Cheng Zhuo1, 2, * (卓 成), Senior Member, IEEE   

  1. 1 College of Information Science and Electronic Engineering, Zhejiang University, Hangzhou 310027, China
    2 Key Laboratory of Collaborative Sensing and Autonomous Unmanned Systems of Zhejiang Province, Hangzhou 310027, China
  • Received:2022-06-09 Revised:2023-02-13 Accepted:2023-02-23 Online:2023-05-10 Published:2023-05-10
  • Contact: Cheng Zhuo E-mail:czhuo@zju.edu.cn
  • About author:Cheng Zhuo received his B.S. and M.S. degrees from Zhejiang University, Hangzhou, in 2005 and 2007, respectively, and his Ph.D. degree in computer science and engineering from the University of Michigan, Ann Arbor, MI, in 2010. He is currently a professor with the College of Information Science Electronic Engineering, Zhejiang University, Hangzhou. His research interests include low power optimization, 3-D integration, hardware acceleration, and power and signal integrity. Dr. Zhuo has published over 120 technical papers and received four Best Paper Nominations in DAC, ICCAD, VTS, and CSTIC. He also received ACM SIGDA Technical Leadership Award, JSPS Invitation Fellowship, and Humboldt Research Fellowship for Experienced Researchers. Dr. Zhuo has served on the technical program and organization committees of many international conferences, and as the associate editor of IEEE TCAD, ACM TODAES, and Elsevier Integration. He is a senior member of IEEE and a fellow of IET.
  • Supported by:
    This work was supported by the National Key Research and Development Program of China under Grant No. 2018YFE0126300, and the National Natural Science Foundation of China under Grant Nos. 62034007 and 62141404.

The development of IoT (Internet of Things) calls for circuit designs with energy and area efficiency for edge devices. Approximate computing which trades unnecessary computation precision for hardware cost savings is a promising direction for error-tolerant applications. Multipliers, as frequently invoked basic modules which consume non-trivial hardware costs, have been introduced approximation to achieve distinct energy and area savings for data-intensive applications. In this paper, we propose a fixed-point approximate multiplier that employs a linear mapping technique, which enables the configurability of approximation levels and the unbiasedness of computation errors. We then introduce a dynamic truncation method into the proposed multiplier design to cover a wider and more fine-grained configuration range of approximation for more flexible hardware cost savings. In addition, a novel normalization module is proposed for the required shifting operations, which balances the occupied area and the critical path delay compared with normal shifters. The introduced errors of our proposed design are analyzed and expressed by formulas which are validated by experimental results. Experimental evaluations show that compared with accurate multipliers, our proposed approximate multiplier design provides maximum area and power savings up to 49.70% and 66.39% respectively with acceptable computation errors.

Key words: approximate computing; fixed-point; linear mapping; multiplier; Internet of Things (IoT);

[1] Atzori L, Iera A, Morabito G. The Internet of Things: A survey. Computer Networks, 2010, 54(15): 2787–2805. DOI: 10.1016/j.comnet.2010.05.010.
[2] Zhuo C, Luo S H, Gan H L, Hu J, Shi Z G. Noise-aware DVFS for efficient transitions on battery-powered IoT devices. IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(7): 1498–1510. DOI: 10.1109/tcad.2019.2917844.
[3] Wen C Y, Dong X, Chen B X, Tida U R, Shi Y Y, Zhuo C. Magnetic core TSV-inductor design and optimization for on-chip DC-DC converter. ACM Trans. Design Automation of Electronic Systems, 2022, 27(5): Article No. 52. DOI: 10.1145/3507700.
[4] Gupta V, Mohapatra D, Park S P, Raghunathan A, Roy K. IMPACT: IMPrecise adders for low-power approximate computing. In Proc. the 2011 IEEE/ACM International Symposium on Low Power Electronics and Design, Aug. 2011, pp.409–414. DOI: 10.1109/ISLPED.2011.5993675.
[5] Han J, Orshansky M. Approximate computing: An emerging paradigm for energy-efficient design. In Proc. the 18th IEEE European Test Symposium, May 2013. DOI: 10.1109/ETS.2013.6569370.
[6] Imani M, Rahimi A, Rosing T S. Resistive configurable associative memory for approximate computing. In Proc. the 2016 Design, Automation & Test in Europe Conference & Exhibition, Mar. 2016, pp.1327–1332. DOI: 10.3850/9783981537079_0454.
[7] Liu W Q, Lombardi F, Shulte M. A retrospective and prospective view of approximate computing. Proceedings of the IEEE, 2020, 108(3): 394–399. DOI: 10.1109/jproc.2020.2975695.
[8] Venkataramani S, Chippa V K, Chakradhar S T, Roy K, Raghunathan A. Quality programmable vector processors for approximate computing. In Proc. the 46th Annual IEEE/ACM International Symposium on Microarchitecture, Dec. 2013. DOI: 10.1145/2540708.2540710.
[9] Deng J N, Shi Z G, Zhuo C. Energy-efficient real-time UAV object detection on embedded platforms. IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(10): 3123–3127. DOI: 10.1109/tcad.2019.2957724.
[10] Mitchell J N. Computer multiplication and division using binary logarithms. IRE Trans. Electronic Computers, 1962, EC-11(4): 512–517. DOI: 10.1109/tec.1962.5219391.
[11] Lim Y C. Single-precision multiplier with reduced circuit complexity for signal processing applications. IEEE Trans. Computers, 1992, 41(10): 1333–1336. DOI: 10.1109/12.166611.
[12] Schulte M J, Swartzlander E E. d multiplication with correction constant. In Proc. the 1993 IEEE Workshop on VLSI Signal Processing, Oct. 1993, pp.388–396. DOI: 10.1109/vlsisp.1993.404467.
[13] Ansari M S, Cockburn B F, Han J. An improved logarithmic multiplier for energy-efficient neural computing. IEEE Trans. Computers, 2020, 70(4): 614–625. DOI: 10.1109/tc.2020.2992113.
[14] Liu W Q, Xu J H, Wang D Y, Wang C H, Montuschi P, Lombardi F. Design and evaluation of approximate logarithmic multipliers for low power error-tolerant applications. IEEE Trans. Circuits and Systems I: Regular Papers, 2018, 65(9): 2856–2868. DOI: 10.1109/tcsi.2018.2792902.
[15] Esposito D, Strollo A G M, Napoli E, De Caro D, Petra N. Approximate multipliers based on new approximate compressors. IEEE Trans. Circuits and Systems I: Regular Papers, 2018, 65(12): 4169–4182. DOI: 10.1109/tcsi.2018.2839266.
[16] Ha M, Lee S. Multipliers with approximate 4-2 compressors and error recovery modules. IEEE Embedded Systems Letters, 2018, 10(1): 6–9. DOI: 10.1109/les.2017.2746084.
[17] Hashemi S, Bahar R I, Reda S. DRUM: A dynamic range unbiased multiplier for approximate applications. In Proc. the 2015 IEEE/ACM International Conference on Computer-Aided Design, Nov. 2015, pp.418–425. DOI: 10.1109/iccad.2015.7372600.
[18] Kulkarni P, Gupta P, Ercegovac M. Trading accuracy for power with an underdesigned multiplier architecture. In Proc. the 24th International Conference on VLSI Design, Jan. 2011, pp.346–351. DOI: 10.1109/vlsid.2011.51.
[19] Narayanamoorthy S, Moghaddam H A, Liu Z H, Park T, Kim N S. Energy-efficient approximate multiplication for digital signal processing and classification applications. IEEE Trans. Very Large Scale Integration (VLSI) Systems, 2015, 23(6): 1180–1184. DOI: 10.1109/tvlsi.2014.2333366.
[20] Tung C W, Huang S H. Low-power high-accuracy approximate multiplier using approximate high-order compressors. In Proc. the 2nd International Conference on Communication Engineering and Technology, Apr. 2019, pp.163–167. DOI: 10.1109/iccet.2019.8726875.
[21] Venkatachalam S, Ko S B. Design of power and area efficient approximate multipliers. IEEE Trans. Very Large Scale Integration (VLSI) Systems, 2017, 25(5): 1782–1786. DOI: 10.1109/tvlsi.2016.2643639.
[22] George J, Marr B, Akgul B E S, Palem K V. Probabilistic arithmetic and energy efficient embedded signal processing. In Proc. the 2006 International Conference on Compilers, Architecture and Synthesis for Embedded Systems, Oct. 2006, pp.158–168. DOI: 10.1145/1176760.1176781.
[23] Schlachter J, Camus V, Enz C, Palem K V. Automatic generation of inexact digital circuits by gate-level pruning. In Proc. the 2015 IEEE International Symposium on Circuits and Systems, May 2015, pp.173–176. DOI: 10.1109/iscas.2015.7168598.
[24] Chen C T, Qian W K, Imani M, Yin X Z, Zhuo C. PAM: A piecewise-linearly-approximated floating-point multiplier with unbiasedness and configurability. IEEE Trans. Computers, 2022, 71(10): 2473–2486. DOI: 10.1109/tc.2021.3131850.
[25] Oklobdzija V G. An algorithmic and novel design of a leading zero detector circuit: Comparison with logic synthesis. IEEE Trans. Very Large Scale Integration (VLSI) Systems, 1994, 2(1): 124–128. DOI: 10.1109/92.273153.
[26] Wallace C S. A suggestion for a fast multiplier. IEEE Trans. Electronic Computers, 1964, EC-13(1): 14–17. DOI: 10.1109/pgec.1964.263830.
[1] Tong Li, Hong-Lan Jiang, Hai Mo, Jie Han, Lei-Bo Liu, and Zhi-Gang Mao. Approximate Processing Element Design and Analysis for the Implementation of CNN Accelerators [J]. Journal of Computer Science and Technology, 2023, 38(2): 309-327.
[2] Hao-Hua Que, Yu Jin, Tong Wang, Ming-Kai Liu, Xing-Hua Yang, and Fei Qiao. A Survey of Approximate Computing: From Arithmetic Units Design to High-Level Applications [J]. Journal of Computer Science and Technology, 2023, 38(2): 251-272.
[3] Yuan-Hu Cheng, Li-Bo Huang, Yi-Jun Cui, Sheng Ma, Yong-Wen Wang, and Bing-Cai Sui. RV16: An Ultra-Low-Cost Embedded RISC-V Processor Core [J]. Journal of Computer Science and Technology, 2022, 37(6): 1307-1319.
[4] Wen-Li Zhang, Ke Liu, Yi-Fan Shen, Ya-Zhu Lan, Hui Song, Ming-Yu Chen, Yuan-Fei Chen. Labeled Network Stack: A High-Concurrency and Low-Tail Latency Cloud Server Framework for Massive IoT Devices [J]. Journal of Computer Science and Technology, 2020, 35(1): 179-193.
[5] Chiou-Yng Lee, Yung-Hui Chen, Che-Wun Chiou, and Jim-Min Lin. Unified Parallel Systolic Multiplier Over GF(2^m) [J]. , 2007, 22(1): 28-38 .
[6] Chiou-Yng Lee, Jenn-Shyong Horng, and I-Chang Jou. Low-Complexity Bit-Parallel Multiplier over GF(2$^m$) Using Dual Basis Representation [J]. , 2006, 21(6): 887-892 .
[7] HOU WenTing (侯文婷), HONG XianLong (洪先龙), WU WeiMin (吴为民) and CAI YiCi (蔡懿慈). FaSa: A Fast and Stable Quadratic Placement Algorithm [J]. , 2003, 18(3): 0-0.
[8] CHEN YiSong (陈毅松), WANG GuoPing (汪国平) and DONG ShiHai (董士海). Further Improvement on Dynamic Programming for Optimal Bit Allocation [J]. , 2003, 18(1): 0-0.
[9] WANG Jiaqi (王家琦), TAO Qing (陶卿) and WANG Jue (王珏). Kernel Projection Algorithm for Large-Scale SVM Problems [J]. , 2002, 17(5): 0-0.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Zhou Di;. A Recovery Technique for Distributed Communicating Process Systems[J]. , 1986, 1(2): 34 -43 .
[2] Li Wei;. A Structural Operational Semantics for an Edison Like Language(2)[J]. , 1986, 1(2): 42 -53 .
[3] Chen Shihua;. On the Structure of Finite Automata of Which M Is an(Weak)Inverse with Delay τ[J]. , 1986, 1(2): 54 -59 .
[4] Li Wanxue;. Almost Optimal Dynamic 2-3 Trees[J]. , 1986, 1(2): 60 -71 .
[5] C.Y.Chung; H.R.Hwa;. A Chinese Information Processing System[J]. , 1986, 1(2): 15 -24 .
[6] Sun Zhongxiu; Shang Lujun;. DMODULA:A Distributed Programming Language[J]. , 1986, 1(2): 25 -31 .
[7] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[8] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[9] Jin Lan; Yang Yuanyuan;. A Modified Version of Chordal Ring[J]. , 1986, 1(3): 15 -32 .
[10] Pan Qijing;. A Routing Algorithm with Candidate Shortest Path[J]. , 1986, 1(3): 33 -52 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved