一种高能效基4-Booth编码并行乘法器设计_黄焘.pdf

电子技术应用 2023年 第49卷 第4期Circuits and Systems电路与系统一种高能效基 4-Booth 编码并行乘法器设计*黄焘，闰闰，胡毅，尹立，谢翔（清华大学 集成电路学院，北京 100084）摘 要：常用的卷积神经网络中存在数十亿次乘法运算，神经网络中乘法的大量能耗成为硬件实现神经网络的能效瓶颈之一。为了降低乘法器的能耗，提出了一种高能效基 4-Booth 编码并行乘法器。通过改进部分积生成模块，消除了传统方法中的补偿位，使得乘法器延时减小且能耗降低。后仿真结果显示，所提出的乘法器比现有乘法器面积减小了 5.2%，延时减小了 6.3%，能耗降低了 10.8%。关键词：卷积神经网络；乘法器；基 4-Booth 编码；高能效中图分类号：TN402 文献标志码：A DOI:10.16157/j.issn.0258-7998.223003中文引用格式：黄焘，闰闰，胡毅，等.一种高能效基 4-Booth 编码并行乘法器设计J.电子技术应用，2023，49(4)：117-122.英文引用格式：Huang Tao，Run Run，Hu Yi，et al.An energy efficient radix-4 Booth encoding parallel multiplier designJ.Application of Electronic Technique，2023，49(4)：117-122.An energy efficient radix-4 Booth encoding parallel multiplier designHuang Tao，Run Run，Hu Yi，Yin Li，Xie Xiang(School of Integrated Circuits，Tsinghua University，Beijing 100084，China)Abstract：Common-used Convolutional Neural Networks(CNNs)contain billions of multiplications,which is the bottleneck of hardware implementation of CNNs.To reduce energy cost of multiplier,an energy-efficient radix-4 Booth encoder multiplier is proposed.By improving the partial product module,the compensation bits in conventional multipliers are eliminated,which reduces the delay and energy cost of multiplier.Post simulation indicates that the proposed multiplier reduces the area,delay and energy cost by 5.2%,6.3%and 10.8%respectively.The proposed multiplier can be used in neural network accelerators and breaks the energy efficiency bottleneck.Key words：CNN；multiplier；radix-4 booth encoder；high energy efficiency0 引言自从 2012 年 AlexNet1在 ImageNet 比赛中获得冠军以来，各种结构的卷积神经网络被发明并广泛应用于图像分类、目标识别、语义分割等场景。由于任务复杂度以及对准确率要求的提高，神经网络的计算量也不断提高，从 2012 年 AlexNet1具有9 108次乘法运算量，到2014 年 VGG-162的1.6 1010次乘法运算量，再到 2017年 SENet3的2.1 1010次乘法运算量。大量的乘法运算使得运行神经网络的硬件消耗巨大能耗，妨碍了神经网络在移动端硬件平台上的实现。Horowitz M 在 2014 年ISSCC 上发表的论文显示，8 bit 乘法消耗的能耗是 8 bit加法的 6.7 倍4。所以，降低乘法的能耗是降低神经网络加速器能耗的关键。乘法器实现乘法可以分为如下三步：部分积生成、部分积压缩和部分积最终相加。前人对乘法器能耗优化的研究主要关注点放在第二步，即部分积压缩的优化上，通过使用 4-2 压缩器或者 7-3 压缩器59等新型压缩器来降低乘法器能耗。4-2 压缩器、7-3 压缩器适用于操作数位宽较宽的乘法，例如 16 bit 或 32 bit，而在 8 bit 乘法器中由于部分积行数较少，因此降低能耗效果甚微。在神经网络的移动端应用中，以神经网络的推理为主，而神经网络的推理过程使用 8 bit 精度就足够10。所以，通过设计新型压缩器来降低 8 bit 乘法器的能耗不是一个有效的方法。第三步部分积最终相加实际上是两行部分积相加得到最终乘法结果，对于这一步能耗最低的设计已有定论，使用行波进位加法器能够以最低能耗完成部分积最终相加11。第一步生产部分积的方法中，基-4 Booth 编码能够减少一半的部分积数量，是高能效乘法器常用的方法12。然而，人们采用传统的取反加一的*基金项目：国家重点研发计划(2019YFB2204800)117Circuits and Systems电路与系统www.ChinaAET.com方法来实现基-4 Booth 编码中的求相反数，使得部分积多了若干比特的“加一”补偿位。“加一”补偿位不仅增加了部分积的比特总数，需要更多的加法器或压缩器来完成部分积压缩和最终相加，而且这些补偿位出现在每行部分积的最低位，导致部分积压缩和最终相加过程的关键路径长。可见，“加一”补偿位是导致 8 bit 乘法器能耗高、延时大的主要原因。本文提出了一种新的高能效基 4-Booth 编码并行乘法器设计，通过改进基 4-Booth 编码部分积生成模块，消除了传统方法中的“加一”补偿位，减少了部分积数目，而且使得部分积阵列规整易于压缩，从而降低了乘法器延时和能耗。1 高能效基 4-Booth 编码并行乘法器设计1.1 基 4-Booth 编码算法12基 4-Booth 编码算法12是实现乘法最为常用的方法之一。它将乘数进行三三分组，根据每组 3 比特乘数以及被乘数生成对应的一行部分积。以 8 比特为例，基 4-Booth 编码算法的数学表达式如下：A B=A i=03(-2b2i+1+b2i+b2i-1)22i(1)其中，操作数 A 和 B 都是补码表示的数，乘积结果也是补码。由式(11)可以得到根据每组 3 比特乘数生成部分积规则如表 1 所示。可以看出部分积有 5 种情况：0，A，-A，2A，-2A。由于 2A 和-2A 可 以 通 过 对 A 和-A 移 位 获 得，因 而 基 4-Booth 编码需要产生-A，也就是被乘数的相反数，传统的基 4-Booth 编码模块使用取反加一产生-A1316：-A=A+1(2)在乘法器中，使用这种方法产生部分积会导致部分积增加。图 1 所示为 4 比特乘法示例。图 1 中由框圈注的数字表示由于取反加一产生的补偿位，使得部分积由原来的两行变为三行。对于 8 比特乘法而言，则如图 2 所示，会带来 4 比特“加一”补偿位。1.2 符号扩展位预处理方法15图 2 的符号扩展位为原理上符号位需要扩展到与乘积结果长度相同，在实际设计乘法器中，会使用符号扩展 位 预 处 理 方 法 来 减 少 符 号 位 的 扩 展，方 法 的 原 理如下。单独研究符号扩展位，并假设四行部分积都是负数，则符号扩展位都是 1，如图 3 所示。将所有 1 相加后得到如图 4 所示结果。再考虑部分积有正有负的情况，对于正的一行部分积，只需在对应的一行符号扩展位最末位加 1，就能将该行符号扩展位都变成 0，也就表示该行部分积为正。而对于负的一行部分积，则需在对应的一行符号扩展位最末位加 0。综合考虑，就是在对应的一行符号扩展位加上符号位的反，也就是部分积数值位最高位的反，如图 5所示。表 1乘数编码与部分积关系对应表b2i+1b2ib2i-1000001010011100101110111部分积0AA2A-2A-A-A0图 14 比特补码乘法示例图图 28 比特补码乘法部分积阵列图图 3未处理的全“1”符号扩展位示意图图 4相加后的全“1”符号扩展位示意图118Circuits and Systems电路与系统电子技术应用 2023年 第49卷 第4期再对第一行进行化简，最终为图 6 形式。所以传统 8 比特乘法器部分积结构如图 7 所示。1.3 改进的基 4-Booth 编码模块为了改进传统的基 4-Booth 编码模块，去掉每行部分积额外的补偿位，减小关键路径和减少部分积比特数，从而降低能耗，本文提出了新的基 4-Booth 编码模块。新的基 4-Booth 编码模块使用不同的方法产生-A，该方法可通过卡诺图化简得出，逻辑表达式如下：ci=ai(ai-1+a1+a0)(3)其中-Ai:0=cici-1c1c0，“”为异或操作，“+”为或操作。式子表示-A 的第 i 位由 A 的第 0 到第 i-1 位进行或操作，最后和第 i 位进行异或操作生成。相比传统方法“取反加一”，这种方法能够使用更少逻辑门和更快地生成-A。如图 8 中以 4 比特输入 A 求出-A 为例，左边是传统方法求-A 的电路，使用了 4 个半加器和 4 个非门，其中一个半加器包含一个异或门和一个或门，所以一共使用了4 个或门、4 个异或门和 4 个非门。右边是新的求-A 的方法一共使用 3 个异或门和 2 个或门。相比传统方法，节省了 1 个异或门，2 个或门和 4 个非门。将这种求-A 时的 方 法 用 到 基 4-Booth 编 码 器 中，则 得 到 改 进 的 基 4-Booth 编码器，如图 9 所示。图 9 中传统部分积生成模块的 neg 信号控制选择器选择被乘数本身(A)或者被乘数的非(A)，同时作为“加一”补偿位输到部分积压缩模块；而改进的部分积生成模块的 neg 信号控制选择器选择被乘数本身(A)或者被乘数的相反数(-A)。两种部分积生成模块的 d 和 s 控制移位器进行左移一位、不移位和生成 0。相比左边的传统基 4-Booth 编码器，改进的基 4-Booth 编码器以硬件资源少的方式实现了-A 的生成，省去了每行部分积的补偿图 5实际符号扩展位示意图图 6处理后的最终符号扩展位示意图图 8传统求相反数方法与新的求相反数方法对比图图 7符号扩展位化简后的 8 比特补码乘法部分积阵列图图 9传统部分积生成模块与改进的部分积生成模块对比图119Circuits and Systems电路与系统www.ChinaAET.com位。下一节会讲述，省去补偿位后，部分积阵列比特数会变少，且形状变得整齐容易压缩，并且缩短了关键路径。1.4 高能效基 4-Booth 编码乘法器对于 8 bit 乘法器，分别使用 2.3 节的传统部分积生成模块和改进的部分积生成模块所生成的部分积阵列如图 10 所示。图 10(a)是传统的基 4-Booth 编码乘法器的部分积点阵，图 10(b)是高能效基 4-Booth 编码乘法器点阵，可见高能效基 4-Booth 编码乘法器的部分积点阵少了 4 比特补偿位，相应地，在进行部分积压缩和最终相加时，使用的压缩器数量也不相同，压缩结构采用常用的 Wallace Tree 结构17，如图 11 所示。图 11(a)所示的传统基 4-Booth 编码乘法器一共使用17 个半加器和 33 个全加器完成部分积压缩和部分积最终相加，而图 1(b)所示的高能效基 4-Booth 编码乘法器使用 7 个半加器和 26 个全加器完成部分积压缩和部分积最终相加，一共少了 10 个半加器和 7 个全加器。同时，高能效基 4-Booth 编码乘法器的部分积压缩级数比传统的少一级，意味着高能效基 4-Booth 编码乘法器关键路径短，延时小。文献18针对最后一行部分积的生成方式进行了改进，利用了类似的先生成-A 的方式，然而作者认为只有最后一行部分积的加一补偿位对乘法器延时和能耗有较大影响，仅需针对最后一行部分积使用该方法，并没有对前三行进行更改。将文献18与本文提出的结构进行对比，如图 12 所示，可见文献18中的乘法器使用了16 个半加器和 30 个全加器，虽然比传统的乘法器少了1 个半加器和 2 个全加器，但是比本文提出的结构多了9 个半加器和 4 个全加器。可以看出本文的乘法器结构更优于文献18中的乘法器结构。2 仿真结果本文所提出的 8 比特乘法器设计使用 Verilog 硬件描述语言进行设计；接着在使用 SMIC 40 nm 工艺的标准阈值电压数字标准单元库，并在标准工艺角、1.1V 电源电压以及 25 摄氏度的条件下，使用 Synopsys Design Compiler 软件对乘法器进行综合得到门级网表；再使用Synopsys IC Compiler 软件进行布局布线和生成版图，并提取寄生参数；最终使用 VCS 以及 PTPX 进行后仿，后仿条件是生成 65 536 组随机数，得到乘法器平均进行一次乘法的能耗。对比的 8 比特乘法器也在同样的条件下进行仿真。结果如表 2 所示。可见仿真结果与第 1 节分析相符，本文提出的高能效乘法器通过优化部分积生成的模块，使得部分积阵列比特数减少且形状规整，易于压缩，从而使得乘法器的面积、延时和能耗均有所降低，分别比文献18中的乘法图 10传统部分积求和关键路径与新的部分积求和关键路径对比图图 11传统部分积压缩和新的部分积压缩硬件资源对比图120Circuits and Systems电路与系统电子技术应用 2023年 第49卷 第4期器面积减少 5.2%，延时减小 6.3%，能耗降低 10.8%。3 结论本文提出了一种高能效乘法器，通过优化改进部分积生成模块，使用直接求相反数的方法代替传统的取反加一求相反数的方法，消除了部分积阵列中的“加一”补偿位，使得部分积阵列比特数减少且形状规整，易于压缩，比现有乘法器面积减少 5.2%，延时减小 6.3%，能耗降低 10.8%。参考文献 1 KRIZHEVSKY A,SUTSKEVER I,HINTON G E.ImageNet classification with deep convolutional neural networks J.Communications of the ACM,2017,60(6):84-90.2 SIMONYAN K,ZISSERMAN A.Very deep convolutional networks for large-scale image recognition J.arXiv preprint arxiv:1409.1556,2015.3 HU J,SHEN L,SUN G,et al.Squeeze-and-excitation networksC/Proceedings of the 31st IEEE/CVF Conference on Computer Vision and Pattern Recognition(CVPR),2018.4 HOROWITZ M,IEEE.Computings Energy Problem(and what we can do about it)C/Proceedings of the 1st IEEE International Solid-State Circuits Conference(ISSCC),2014.5 FADAVI-ARDEKANI J.MN Booth encoded multiplier generator using optimized Wallace trees J.IEEE Transactions on Very Large Scale Integration(VLSI)Systems,1993,1(2):120-125.6 ITOH N,NAEMURA Y,MAKINO H,et al.A 600-MHz 54x54-bit multiplier with rectangular-styled Wallace tree J.IEEE Journal of Solid-State Circuits,2001,36(2):249-257.7 ELGUIBALY F.A fast parallel multiplier-accumulator using the modified Booth algorithm J.IEEE Transactions on Circuits and Systems II-Analog and Digital Signal Processing,2000,47(9):902-908.8 CHANG C H,GU J M,ZHANG M Y.Ultra low-voltage low-power CMOS 4-2 and 5-2 compressors for fast arithmetic circuits J.IEEE Transactions on Circuits and Systems I-Regular Papers,2004,51(10):1985-1997.9 MORI J,NAGAMATSU M,HIRANO M,et al.A 10-ns 5454 b parallel structured full array multiplier with 0.5 m CMOS technology J.IEEE Journal of Solid-State Circuits,1991,26(4):600-606.10 JACOB B,KLIGYS S,CHEN B,et al.Quantization and training of neural networks for efficient integer-arithmetic-only inference C/Proceedings of the 31st IEEE/CVF Conference on Computer Vision and Pattern Recognition(CVPR),2018.11 NAGENDRA C,IRWIN M J,OWENS R M.Area-time-power tradeoffs in parallel adders J.IEEE Transactions on Circuits and Systems II-Analog and Digital Signal,1996,43(10):689-702.12 BOOTH A D.A signed binary multiplication technique J.Quarterly Journal of Mechanics and Applied Mathematics,1951,4(2):236-240.13 NAGAMATSU M,TANAKA S,MORI J,et al.A 15-ns 32*32-b CMOS multiplier with an improved parallel structure J.IEEE Journal of Solid-State Circuits,1990,图 12文献18部分积压缩和新的部分积压缩硬件资源对比图表 2后仿真结果对比表乘法器文献18本文面积/m2319.83303.24(-5.2%)延时/ns2.222.08(-6.3%)能耗/pJ0.5580.498(-10.8%)121Circuits and Systems电路与系统www.ChinaAET.com25(2):494-497.14 YEH W C,JEN C W.High-speed Booth encoded parallel multiplier design J.IEEE Transactions on Computers,2000,49(7):692-701.15 DE ANGEL E,SWARTZLANDER E E,JR.Low power parallel multipliers C/VLSI Signal Processing,IX,1996.16 ABU-KHATER I S,BELLAOUAR A,ELMASRY M I.Circuit techniques for CMOS low-power high-performance multipliers J.IEEE Journal of Solid-State Circuits,1996,31(10):1535-1546.17 WALLACE C S.Suggestion for fast multiplier J.IEEE Transactions on Computers,1964,EC13(1):14.18 KANG J-Y,GAUDIOT J-L.A simple high-speed multiplier design J.IEEE Transactions on Computers,2006,55(10):1253-1258.（收稿日期：2022-05-22）作者简介：黄焘（1997-），男，学士，主要研究方向：神经网络加速器。闰闰（2000-），男，学士，主要研究方向：神经网络加速器。谢翔（1971-），通信作者，男，博士，副教授，主要研究方向：片上系统，E-mail：。扫码下载电子文档122