随着OpenAI公司的ChatGPT(chat generative pre-trained transformer)、百度的文心一言以及复旦大学的MOSS等各种AI模型平台的陆续推出,人工智能话题迅速成为广泛关注的焦点。这些模型平台的出现是基于各种结构神经网络的广泛应用。随着对AI模型智能化要求的提高,各种AI模型任务的复杂度也随之提高,其中神经网络中的乘加单元运算量也不断增多。目前,AlexNet网络模型训练的乘法运算量已经达到9×108次[1],同时乘法器也是数字信号处理器(DSP)的重要组成部分,其运行速度极大地影响了处理器的运行速度,因此降低乘法器的延时和减小其芯片面积至关重要。
Radix-4 Booth编码乘法器算法的核心步骤是部分积生成、部分积压缩和最终求和电路。部分积生成和压缩主要影响着乘法器的版图面积,最终求和电路则影响着乘法器的工作速度。在部分积生成方面[2],使用Radix-4、 Radix-8、 Radix-16等高基编码来减小部分积的数量。在部分积压缩阶段,Wallace压缩方式是利用保留进位加法器构成树状结构对部分积阵列压缩处理,这种压缩方式通过设计不同结构压缩器来提高压缩速率[3],在最终求和部分,使用快速进位加法器求和来提高乘法器的运行速度。姚若河等[4]在部分积生成方面,采用基数更大的Radix-16、Radix-32和Radix-64编码使得部分积的个数降低,但基数更大的编码算法使得编码器电路复杂度增加,进而需要在解码器电路中引入更多的组合逻辑电路,降低了乘法器的运行速度。Scheunemann等[5]在Wallace压缩阶段,使用5级进位保留加法器(carry save adder,CSA),增大了压缩模块的延时。Jain等[6]在最终求和部分,使用纹波进位加法器(ripple carry adder,RCA)结构,减小了面积,但因为多bit伪和的求和电路位数是32位,其门传输延时是65级,此加法器结构降低了乘法器的工作速度。Moni等[7]采用Dadda树压缩方式,分别将16位乘数和被乘数分为高8位和低8位,采用阵列压缩的方式,降低了压缩阵列的延时,但是增大了此模块的面积。
本文综合考虑了面积和延时两方面因素,提出了一种新型的16位定点乘法器。所提出的Radix-4 Booth算法乘法器结构有以下3点改进。
(1)提出了一种新型的取补码电路,以硬件资源少的方式实现被乘数补码电路的生成。并通过改进编码器和解码器电路,用3个flag信号控制产生部分积,减少了部分积的个数。此模块在减小乘法器面积的同时,降低了部分积生成模块的门传输延时。
(2)在Wallace压缩结构中仅使用了两级压缩结构。在压缩电路中,灵活采用改进的4-2压缩器和CSA结构。并对扩展符号位进行预处理和在第二级Wallace压缩中提前进行高位求和运算,缩短了最后求和电路的关键路径。
(3)提出了一种新型的快速求和电路,进一步优化电路关键路径延时,进而提高乘法器的工作速度。
1 乘法器整体设计
为了使部分积阵列易于压缩,在不增加乘法器延时的前提下,本文提出两种乘法器结构方案。方案1为纯组合逻辑电路组成的乘法器(multipliers composed of pure combinational logic circuits, MCL),如图1(a)所示。MCL乘法器结构最大限度地减小乘法器面积,并通过新型求和电路缩短门电路传输延时,进而提高乘法器的运行速度。方案2为带有时序逻辑的乘法器(multiplier with sequential logic, MSL),MSL的单元结构是两级流水线,用于增加乘法器单元的吞吐量,如图1(b)所示。P1～P8为编码器和解码器电路生成的8个部分积。在部分积生成单元中引入了流水线寄存器的第一个阶段,并在部分积压缩阶段和最终求和阶段(C和S)之间增加了另一个流水线阶段。对比MCL和MSL两种乘法器结构,除了MSL增加流水线寄存器以外,其他结构均相同。
图1 MCL和MSL乘法器结构图
Figure 1 Schematic diagram of MCL and MSL multiplier
2 部分积生成
2.1 传统的编码电路和解码电路
Radix-4 Booth编码算法规则是乘数最低位补零,然后依次从低到高检测乘数的3位数,以A×B两个16位有符号定点数进行举例说明,乘数B的3位组合如图2所示。
图2 乘数B组合示意图
Figure 2 Schematic diagram of multiplier B combination
在图2中,b-1=0。相邻检测3位之间重叠1位,通过编码器电路,将部分积从16个减少为8个,从而提升了乘法器的运算速度。将16位有符号二进制数B转化为其对应的十进制如式(1)所示,A与B的乘积可以表示为式(2)。
(1)
(2)
根据式(2)可以得到多项式Y的真值表和部分积的关系,如表1所示。
表1 多项式Y的真值表
Table 1 Truth table of polynomial Y
b2n+1b2nb2n-1Y部分积b2n+1b2nb2n-1Y部分积00000100-2-2A0011A101-1-A0101A110-1-A01122A11100
通过表1可知,对乘数B进行编码可以得到5种部分积的结果。当Y=0时,则对被乘数A每1位都置零;当Y=1时,则对被乘数A保持不变;当Y=-1时,则对被乘数A每1位都取反加1;当Y=2时,则对被乘数A左移1位,并最低位补零;当Y=-2时,则对被乘数A左移1位后,再取反加1。
2.2 改进的编码电路和解码电路
2.2.1 改进的取补码电路
本文改进的被乘数取补码电路使用新的方法通过化简卡诺图得到-A的第i位进位逻辑表达式如式(3)所示。
ci=ai⊕(ai-1+ai-2+…+a1+a0)。
(3)
式中:ci为被乘数A第i位向i+1位的进位;⊕表示异或门。
-A可以用ci表示,其逻辑表达式如式(4)所示。
-A[i∶0]=cici-1…c1c0。
(4)
本文以4位二进制数X来求出-X为例进行对比说明,如图3所示。图3(a)是传统半加器求解-X的电路,图3(b)是采用改进的方法。其中每个半加器使用1个异或门和1个与门,所以传统方法一共使用了4个非门、4个与门、4个异或门。图3(b)采用了2个或门、3个异或门。由于与门和或门在电路中的面积和延时基本相同,所以这种改进的求-X的电路节省了4个非门、2个或门和1个异或门。由此将这个方法用到16位求补码电路中,可以节省17个非门、2个或门和1个异或门。
图3 取补码电路
Figure 3 Complementary code taking circuit
2.2.2 改进的编码器电路
改进的编码器电路需要对多项式Y真值表进行重新编码,如表2所示。
表2 改进的编码器编码表
Table 2 Improved encoder coding table
Y部分积F2AF-AFA000001A0011A00122A101-2-2A110-1-A010-1-A01000000
根据表2可以得出新的3个flag(FA, F-A, F2A)信号逻辑表达式如式(5)所示:
(5)
根据式(5)可以得到实现3个flag信号的控制电路如图4所示。
图4 改进的编码器电路
Figure 4 Improved encoder circuit
在图4中,改进的编码器电路使用了3个非门、4个与(或)门和1个异或门。与文献[5]和文献[8]相比,编码器电路门电路个数上基本相同。
2.2.3 改进的解码器电路
通过改进的编码器电路得到解码器电路如图5所示。在图5中,由FA和F-A来选择生成部分积是保持乘数A还是取补码后的-A,接着通过第二个多路选择器的选通端F2A选出是否需要左移的数据。
图5 改进的解码器电路
Figure 5 Improved decoder circuit
将本文部分积生成模块的门电路个数和总的门传输延时与文献[5]和文献[8]进行对比,得到表3。
表3 部分积生成模块对比
Table 3 Comparison of partial product generation modules
乘法器结构门个数门传输延时文献[5]4个多路选择器6级与(或)门文献[8]3个多路选择器7级与(或)门本文2个多路选择器6级与(或)门
在表3中,部分积生成模块中编码器门个数基本相同,解码器中门个数对芯片面积影响更为重要。因此,本文只比较解码器结构中所使用的多路选择器数量。
本文与文献[5]相比,门电路的传输延时相同,但是少了2个多路选择器;与文献[8]相比,少了1个多路选择器和少了1级门传输延时。因为部分积是18位的,所以解码器电路中的1个多路选择器对应18个二输入的选择器,又因为Radix-4 Booth算法生成的8个部分积每一个都需要经过编码和解码模块,所以减少1个多路选择器带来的是编解码电路面积成倍缩小。因此,本文改进的编解码电路不仅减小了此模块的面积开销,而且提高了此模块的运行速度。详细的电路设计以生成P1为例进行说明,如图6所示。
图6 P1部分积生成示意图
Figure 6 Schematic diagram of P1 partial product generation
在图6中,FA和F-A通过一级与或门选出是否需要对被乘数取补码的17位中间值M,当编码电路FA和F-A信号同时为0时,通过2级与(或)门将M[16∶0]全部置零,然后将通过F2A信号得到的P1[17∶0]全部置零。当FA=1、F-A=0时,M[16∶0]保持被乘数A数据本体。接着通过第二级多路选择器,当F2A=1时,代表左移有效,P1[16∶1]=M[15∶0];当F2A=0时,代表左移无效,P1[16∶1]=M[16∶1];因为是有符号数,P1[17]是部分积的符号位,所以无论左移信号F2A是否有效,P1[17]=M[16]。对于P1[0],当F2A=1时,P1[0]=0;当F2A=0时,P1[0]=M[0]。
3 Wallace压缩电路
由于Wallace压缩模块并行性很高,所以在此模块主要考虑如何减小版图面积,也要避免增大门传输延时。本文主要从两个方面进行改进:一方面通过设计不同的压缩器进而使用混合压缩的结构对生成的8个部分积压缩;另一方面要对过多的符号扩展位进行预处理,从而减少使用压缩器个数,达到减小面积的目的。
3.1 传统的Wallace压缩模块
3.1.1 传统的压缩器结构
Wallace压缩模块是由4-2压缩器、CSA和半加器组合而成,4-2压缩器是由两个CSA组合得到的,其结构如图7所示。
图7 传统的CSA和4-2压缩器
Figure 7 Traditional CSA and 4-2 compressor
图7(a)为CSA电路结构图,图7(b)为2个CSA级联得到的4-2压缩器电路图。CSA使用了2个异或门和3个与门,最长门传输延时为2级异或门。4-2压缩器的工作原理是:i1、i2、i3进入第一级CSA,得到Cout和S1,然后将S1和i4和Cin送入第二级CSA,得到C2和S2。这种4-2压缩器使用门的数量是CSA结构的两倍,最长门传输延时为4级异或门。
由图7可以得到CSA结构的C1和S1的逻辑表达式如式(6)所示:
(6)
由CSA级联得到的4-2压缩器的Cout、C2和S2的逻辑表达式如式(7)所示:
(7)
对于4-2压缩器有多种设计方法,但是必须满足基本公式:
i1+i2+i3+i4+Cin=S2+2(C2+Cout)。
(8)
3.1.2 传统的Wallace压缩结构
对比式(7)中CSA的逻辑表达式可以发现CSA就是进位保留的全加器,生成了两个伪和C1和S1。而对比4-2压缩器的逻辑表达式可以发现其压缩器的Cout和Cin没有代数关系,不会造成级联,适合并行乘法器的使用。但是对于传统的4-2压缩器,缺点是关键路径即C2的生成经过了4级异或门的传输延时。传统的Wallace压缩结构如图8所示,两级压缩电路传输延时最长的路径是第一级4-2压缩器的输入到第二级压缩器输出的S21,最长门传输延时是8级异或门。
图8 传统的Wallace压缩结构图
Figure 8 Traditional Wallace compressed structure diagram
在图8中,白色圆圈代表符号扩展位,P1～P8为编解码电路生成的8个部分积,每个部分积的符号扩展位需要扩展到与最终积长度一致。首先P1～P4采用4-2压缩器、CSA混合压缩生成了两个伪和S11和C11,同理P4～P8生成两个伪和S12和C12。然后再将生成的S11、C11、S12、C12进行混合压缩生成第二级伪和S21和C21。从图8中可以看出,传统Wallace压缩结构一共使用了68个4-2压缩器,造成Wallace压缩结构面积过大。
从压缩模块的面积和门传输延时两个角度来看,Wallace压缩电路有很大的优化空间。
3.1.3 传统的求和电路
对于多位求和电路,常用结构和算法包括串行进位加法器(RCA)、跳跃进位加法器(CSPA)、选择进位加法器(SCA)、超前进位加法器(CLA)和并行前缀加法器(PPA)5种。RCA的速度最慢,面积最小;CSPA速度相比于RCA有了很大提高,而且面积增加不大;SCA和CLA的速度相差不大,都可以达到高速运算的要求;PPA速度最快,相当于SCA的1.5倍,但电路结构复杂造成了其面积仍然比较大。
从式(8)中可以看出,4-2压缩器的Cin跟Cout没有级联关系,并且图8中可以看出前2级的部分积压缩是高度并行的,所以关键路径的延时在于最后两个伪和数组成的求和电路。
传统求和电路采用RCA结构30位S21和C21进行求和,单个的RCA加法器结构Cin到Cout门传输延时是2级与(或)门,30位RCA结构级联的门传输延时是61级。此加法器结构面积最小,但是门传输延时很大。文献[9]采用一级CLA结构,减小了求和电路传输延时,但是一级32位CLA造成了求和电路面积过大。
3.2 改进的Wallace压缩模块
3.2.1 改进的压缩器结构
本文改进的CSA结构如图9(a)所示,改进的4-2压缩器设计如图9(b)所示。在任何工艺中,与非门和或非门比与门和或门内部结构更简单,传输延时更小[10]。改进的CSA传输延时从2级与门变为2级与非门。改进4-2压缩器的最长门传输延时为3级异或门,比图7(b)少了1级异或门,压缩器的门个数基本相同,同时满足4-2压缩器的基本公式。
图9 改进的CSA和4-2压缩器
Figure 9 Improved CSA and 4-2 compressor
3.2.2 符号位预处理
根据图8可以知,传统的Wallace压缩结构中每一行的部分积符号位都需要扩展到与乘积结果长度相同,符号扩展位较多,这需要用大量的4-2压缩器来对符号扩展位进行压缩,无疑增大了芯片面积。针对符号扩展位过多的问题,由于16位乘法器生成的积位数最多是32位,对于符号位相加位数超过32位的数可以忽略不计,所以将符号扩展位进行计算得到规律表达如式(9)所示。将式(9)和式(10)中的
放入对应部分积的符号扩展位,对于P1符号扩展位,根据式(10)可以把
放入P1的17～19位。S1～S8是8个部分积的符号位,通过对符号扩展位的预处理,将72个符号扩展位缩减到10位和6个1。每个部分积符号位不再需要扩展到第31位,减小了Wallace压缩结构所使用的4-2压缩器数量。
=
(9)
(10)
3.2.3 改进的Wallace压缩结构
本文采用改进的CSA和4-2压缩器混合压缩,优化后的Wallace压缩结构如图10所示。此混合压缩结构一共使用了11个半加器、40个4-2压缩器、11个RCA和9个CSA。另外采用新型4-2压缩器结构,使得两级压缩中的门传输延时由8级异或门缩短到6级异或门。
图10 改进的Wallace压缩结构图
Figure 10 Improved Wallace compression structure diagram
改进的混合压缩结构在第二级4-2压缩中S12和C12的[7∶4]和[31∶26]位提前使用11个RCA计算。优化后C21的[31∶26]和[8∶0]位全部为0,在S21和C21的[30∶24]位可以使用半加器级联,31位不必关心进位。通过第二级压缩高位的提前计算,使得伪和相加的两位求和电路相加位数从32位变为16位,显著提高了乘法电路的运算速度。
3.2.4 改进的求和电路
本设计将图10中的两位求和电路分为4组,采用两级CLA结构。组内采用CLA结构,组间采用CLA结构,其电路结构示意图如图11所示。
图11 两级CLA结构示意图
Figure 11 Schematic diagram of two-level CLA structure
在图11中,S0～S15为16位和,Ci为低位进位,Co为两位求和电路的进位,PG1～PG4为组内的进位产生和进位传递信号产生模块;C3、C7、C11为利用组间进位模块产生的组内CLA进位输入端。改进的两级CLA求和电路只有8级门电路传输延时,相对于使用RCA结构的33级,缩短了25级。将改进的16位求和结构应用于Wallace压缩电路S21和C21的[25∶10]位中,使得伪和相加电路门传输延时缩短为16级。改进的求和电路既缩短了使用RCA结构带来的过度延时,也避免了使用一级CLA结构带来的巨大面积开销。
4 仿真分析
本文设计采用硬件描述语言Verilog HDL,使用ModelSim进行仿真,并在赛灵思Xilinx公司的FPGA-xc3s500e开发板上实现了MCL和MSL结构。通过写测试文件,遍历有符号16位数据范围(-32 768～32 767)。将测试文件数据A和B输入VIVADO18.3软件的IP核中,遍历所有乘法数据可能,对比两组乘法运算结果,如果一致则correct输出为1,否则为0。初步验证两种乘法器结构功能的正确性后,在相同的综合策略下用FPGA板卡实现,将本文设计的MSL结构与文献[11]乘法器所使用的硬件资源、性能以及功耗进行比较,如表4所示。
表4 仿真结果对比
Table 4 Comparison of simulation results
乘法器结构LUTFFIO电路延时/ns功耗/mW文献[11]6873696628.8686.18MSL5801936617.4783.40
本文设计的MSL比文献[11]少了107个LUT(查找表)和176个FF(寄存器)。延时降低39.5%,功耗减少3.2%。因此初步判定,MSL在面积和性能方面要优于现有的流水线乘法器。
5 结果分析
本文提出的16位高效乘法器在VIVADO18.3软件中验证功能正确性后,接着使用TSMC180 nm工艺标准阈值电压数字标准单元库,用EDA Synopsys工具Design Compiler 对乘法器进行综合得到总电路的面积、电路延时和功耗延迟积PDP信息。新型乘法器与现有乘法器的对比如表5所示。
表5 TSMC180 nm综合结果对比
Table 5 Comparison of comprehensive results of TSMC180 nm
乘法器结构 面积/μm2电路延时/ns功耗/mWPDP/ (ns·mW)Synopsys27 0605.822.8616.65文献[4]22 1924.792.5412.17文献[12]19 25010.342.0621.30MCL19 5403.812.6510.10MSL30 3491.9714.1427.43
由表5对比可知,MCL在面积,延时,功耗方面的数据表现均好于Synopsys中已经商用的乘法器IP。MCL与文献[4]相比面积减少了12.0%,速度提高了20.5%,功耗仅增加4.3%,PDP降低了17.0%。MCL与文献[12]相比速度提高63.2%,PDP降低了52.6%,面积仅增加1.5%。MCL结构在面积、电路延时以及功耗方面的表现比较均衡,适用于对乘法器单元的3个指标有同样高要求的DSP处理单元。MSL采用增加流水线寄存器的方式,提高了乘法器的运行速度,所以性能最好,但同时带来的是面积和功耗的增加。MSL结构在性能方面表现比较突出,适用于超高速微处理器的乘法计算单元中。
6 结论
本文主要目的是设计出一种高速并且面积小的、可以执行16位有符号数乘法的定点乘法器单元。新型乘法器对Radix-4编解码模块进行改进,改进后的编解码器电路并行度高、级数少。同时优化压缩模块的符号扩展位和压缩器单元,并提前计算部分数据位,降低了压缩模块电路的复杂度,减少了多位求和电路的位宽。综合结果表明,MCL结构相比已有的乘法器面积减少了12.0%,电路延时也降低了20.5%,可以满足高性能定点DSP对乘法器在面积和速度上的要求;MSL结构增加流水线寄存器来获得更快的运行速度,但代价是额外的面积和功耗。在未来工作中,可将标准单元库扩展,并使用扩展单元对关键路径进行优化,进一步提高乘法器的速度。
[1] SIMONYAN K, ZISSERMAN A. Very deep convolutional networks for large-scale image recognition[EB/OL]. (2015-04-10)[2024-01-12]. http:∥arxiv.org/abs/1409.1556.
[2] VAMSI H S R, REDDY K S, BABU C, et al. Design of reversible logic based 32-bit MAC unit using Radix-16 Booth encoded Wallace tree multiplier[C]∥2018 International Conference on Computer Communication and Informatics. Piscataway: IEEE, 2018: 1-6.
[3] RAMAKRISHNA A, BALAJI N, SRIHARI P. An efficient and enhanced memory based FFT processor using Radix 16 Booth with carry skip adder[C]∥2016 International Conference on Signal Processing, Communication, Power and Embedded System. Piscataway: IEEE, 2016: 1608-1612.
[4] 姚若河, 徐新才. 基于冗余符号数的定点乘法器的设计[J]. 华南理工大学学报(自然科学版), 2014, 42(3): 27-34.YAO R H, XU X C. Design of a fixed-point multiplier based on redundant signed digit[J]. Journal of South China University of Technology (Natural Science Edition), 2014, 42(3): 27-34.
[5] SCHEUNEMANN J C, SIGALES M S, FONSECA M B, et al. Optimizing encoder and decoder blocks for a power-efficient Radix-4 modified Booth multiplier[C]∥2021 34th SBC/SBMicro/IEEE/ACM Symposium on Integrated Circuits and Systems Design. Piscataway: IEEE, 2021: 1-6.
[6] JAIN R, PAHWA K, PANDEY N. Booth-encoded Karatsuba: a novel hardware-efficient multiplier[J]. Advances in Electrical and Electronic Engineering, 2021, 19(3): 272-281.
[7] MONI D J, SOPHIA P E. Design of low power and high speed configurable Booth multiplier[C]∥2011 3rd International Conference on Electronics Computer Technology. Piscataway: IEEE, 2011: 338-342.
[8] 曾宪恺. 高性能并行乘法器半定制设计方法研究[D]. 杭州: 浙江大学, 2012.ZENG X K. Research on semi-custom design method of high-performance parallel multiplier[D]. Hangzhou: Zhejiang University, 2012.
[9] PATIL P A, KULKARNI C. Multiply accumulate unit using Radix-4 Booth encoding[C]∥2018 Second International Conference on Intelligent Computing and Control Systems. Piscataway: IEEE, 2018: 1076-1080.
[10] RAVULA M R, POTHARAJU A, VIDYADHAR R P. Designing carry look ahead adder to enrich performance using one bit hybrid full adder[C]∥2022 International Conference on Electronics and Renewable Systems. Piscataway: IEEE, 2022: 86-89.
[11] RAM G C, SUBBARAO M V, VARMA D R, et al. Delay enhancement of Wallace tree multiplier with binary to excess-1 converter[C]∥2023 5th International Conference on Smart Systems and Inventive Technology. Piscataway: IEEE, 2023: 113-117.
[12] RAJU A, SA S K. Design and performance analysis of multipliers using Kogge Stone adder[C]∥2017 3rd International Conference on Applied and Theoretical Computing and Communication Technology. Piscataway:IEEE, 2017: 94-99.