基于Karatsuba和Vedic算法的快速單精度浮點(diǎn)乘法器

易清明，符清桿，石 敏，駱愛文，陳嘉文

(1.暨南大學(xué)信息科學(xué)技術(shù)學(xué)院 廣州510632；2.泰斗微電子科技有限公司 廣州510663)

單精度浮點(diǎn)數(shù)乘法運(yùn)算的耗時(shí)主要集中在24 bit的尾數(shù)相乘部分。為了提高單精度浮點(diǎn)數(shù)乘法運(yùn)算的速度，研究者提出了各種單精度浮點(diǎn)乘法器的改進(jìn)方法[1-8]。文獻(xiàn)[1]提出了基于Karatsuba算法[9-10]的改進(jìn)設(shè)計(jì)，通過數(shù)學(xué)運(yùn)算的公式變換，用加法器代替乘法器，相比于24 bit尾數(shù)直接相乘的單精度浮點(diǎn)乘法器的設(shè)計(jì)，該設(shè)計(jì)減少了3個(gè)乘法器，只使用了6個(gè)乘法器。但是乘法器的使用限制了單精度浮點(diǎn)乘法器運(yùn)算速度的進(jìn)一步提高。文獻(xiàn)[2]提出了一種基于Vedic算法[3-4]的單精度浮點(diǎn)乘法器設(shè)計(jì)方法，該設(shè)計(jì)沿用了24 bit尾數(shù)直接相乘的設(shè)計(jì)思路，通過使用Vedic算法設(shè)計(jì)3 bit的乘法器，迭代復(fù)用，實(shí)現(xiàn)24 bit的尾數(shù)相乘運(yùn)算，從而避免乘法器的使用，提高單精度浮點(diǎn)乘法器的運(yùn)算速度。但是簡單使用Vedic算法設(shè)計(jì)單精度浮點(diǎn)乘法器，導(dǎo)致Vedic算法設(shè)計(jì)的3 bit乘法器迭代次數(shù)過多，硬件資源增多。文獻(xiàn)[3]沿用了Vedic算法的思想，利用流水線設(shè)計(jì)方法對單精度浮點(diǎn)乘法器結(jié)構(gòu)進(jìn)行優(yōu)化，同時(shí)減少單精度浮點(diǎn)乘法器的組合邏輯延時(shí)，提高單精度浮點(diǎn)乘法器的運(yùn)算速度，但是同樣存在Vedic算法設(shè)計(jì)的3 bit乘法器迭代次數(shù)過多，硬件資源增多的問題；文獻(xiàn)[5]在Vedic算法的基礎(chǔ)上，通過全加器的復(fù)用來簡化單精度浮點(diǎn)乘法器的設(shè)計(jì)結(jié)構(gòu)，提高單精度浮點(diǎn)乘法器的運(yùn)行速度，但是依然無法滿足目前的運(yùn)算需求。

以上文獻(xiàn)提出的改進(jìn)方法對單精度浮點(diǎn)乘法器的運(yùn)算速度均有一定的提高，但是人工智能的興起對浮點(diǎn)數(shù)乘法運(yùn)算的速度提出了更高的要求，數(shù)以百萬計(jì)的浮點(diǎn)數(shù)乘法運(yùn)算造成深度學(xué)習(xí)的訓(xùn)練時(shí)間過長，限制了人工智能的研究與實(shí)用性。為了進(jìn)一步提高單精度浮點(diǎn)乘法器的運(yùn)算速度，本文利用Vedic算法改進(jìn)了Karatsuba算法，并把該算法應(yīng)用于單精度浮點(diǎn)乘法器設(shè)計(jì)。

1 浮點(diǎn)數(shù)乘法原理

本文設(shè)計(jì)的單精度浮點(diǎn)乘法器基于IEEE754標(biāo)準(zhǔn)[11]。單精度浮點(diǎn)數(shù)的表示格式由4字節(jié)組成，分為3個(gè)部分。第1部分為符號位，占1 bit；第二部分為階碼部分，占8 bit；第三部分為尾數(shù)部分，占23 bit。一個(gè)實(shí)數(shù)H的浮點(diǎn)數(shù)表示形式為：

式中，C表示符號位；Z表示尾數(shù)部分，在浮點(diǎn)數(shù)運(yùn)算時(shí)要補(bǔ)上隱藏的‘1’，轉(zhuǎn)換成{1,Z}；E表示階碼，在實(shí)數(shù)轉(zhuǎn)換為浮點(diǎn)數(shù)格式時(shí)要減去相應(yīng)的偏移量。

單精度浮點(diǎn)數(shù)乘法運(yùn)算可以簡單分為4個(gè)步驟。

1)兩個(gè)乘數(shù)的符號位進(jìn)行異或運(yùn)算。根據(jù)異或的結(jié)果決定最后計(jì)算結(jié)果的正負(fù)性。若符號位異或的結(jié)果為1，則浮點(diǎn)數(shù)相乘的結(jié)果是負(fù)數(shù)，若異或的結(jié)果為0，則浮點(diǎn)數(shù)相乘的結(jié)果是正數(shù)。

2)兩個(gè)乘數(shù)的階碼直接相加，其結(jié)果再減去偏移量Bias得到相乘后結(jié)果的階碼，Bias的值為127。

3)尾數(shù)部分補(bǔ)上隱藏的‘1’，執(zhí)行尾數(shù)相乘操作，得到相乘的結(jié)果V。

4)步驟3)相乘結(jié)果V的最高位的值決定標(biāo)準(zhǔn)化結(jié)果尾數(shù)的取值。若最高位為1，則取V[46:24]位作為最后標(biāo)準(zhǔn)化結(jié)果的尾數(shù)；若最高位是0，則取V[45:23]位作為最后標(biāo)準(zhǔn)化結(jié)果的尾數(shù)。聯(lián)合符號位的值、階碼的值和尾數(shù)的值到兩個(gè)浮點(diǎn)數(shù)相乘的結(jié)果。

浮點(diǎn)數(shù)乘法運(yùn)算的流程如圖1所示。Ha、Hb表示32位的浮點(diǎn)數(shù),Za、Zb為23 bit的尾數(shù)。Ha的符號位與Hb的符號位進(jìn)行異或運(yùn)算得到符號位部分運(yùn)算后的結(jié)果；Ha的階碼加上Hb的階碼再減去相應(yīng)的偏移量(Bias)得到階碼部分運(yùn)算后的結(jié)果；尾數(shù)在高位補(bǔ)上隱藏的‘1’，分別得到24 bit的乘數(shù){1,Za}、{1,Zb}。24 bit的乘數(shù)相乘得到48 bit的結(jié)果V，其最高位的值決定浮點(diǎn)數(shù)相乘結(jié)果尾數(shù)的取值。聯(lián)合符號位部分運(yùn)算后的結(jié)果、階碼部分運(yùn)算后的結(jié)果及尾數(shù)部分標(biāo)準(zhǔn)化的結(jié)果得到浮點(diǎn)數(shù)相乘的結(jié)果。由于尾數(shù)部分的標(biāo)準(zhǔn)化需要依據(jù)V最高位的值，所以尾數(shù)相乘的耗時(shí)決定了浮點(diǎn)乘法器的運(yùn)算速度。

圖1 浮點(diǎn)數(shù)乘法運(yùn)算的流程框圖

2 Karatsuba算法

傳統(tǒng)單精度浮點(diǎn)乘法器中的尾數(shù)相乘實(shí)現(xiàn)方法如下所示[1]：

式中，n取值為8；W、X(W={1,Za},X={1,Zb})為24 bit的尾數(shù)；W2、W1、W0分別表示W(wǎng)的高8位、中8位、低8位；X2、X1、X0分別表示X的高8位、中8位、低8位。傳統(tǒng)的單精度浮點(diǎn)乘法器設(shè)計(jì)把尾數(shù)W和X直接相乘，由式(4)可知，得到24 bit尾數(shù)相乘的結(jié)果需要9個(gè)8位×8位的乘法器和8個(gè)加法器。由于乘法運(yùn)算比加法運(yùn)算耗時(shí)長，且電路結(jié)構(gòu)更加復(fù)雜，所以傳統(tǒng)的單精度浮點(diǎn)乘法器效率比較低且運(yùn)算速度慢。Karatsuba算法用加法器來替代乘法器，從而減少乘法器的使用，達(dá)到簡化電路結(jié)構(gòu)，提高運(yùn)算速度的目的。基于Karatsuba算法的24 bit尾數(shù)相乘的實(shí)現(xiàn)方法具體如下所示[1]：

根據(jù)式(5)～(10)可以得到24 bit尾數(shù)相乘的結(jié)果，如下所示：

由式(11)可得，相比于傳統(tǒng)方法實(shí)現(xiàn)的24 bit尾數(shù)相乘，基于Karatsuba算法實(shí)現(xiàn)的24 bit尾數(shù)相乘使用的乘法器數(shù)量更少，由之前的9個(gè)乘法器減少到6個(gè)乘法器，而僅增加了9個(gè)加法器。

3 本文設(shè)計(jì)

針對基于Karatsuba算法設(shè)計(jì)的單精度浮點(diǎn)數(shù)乘法器依然存在乘法器，限制了運(yùn)算速度的提升，本文對原Karatsuba算法進(jìn)行了改進(jìn)，并將該改進(jìn)算法應(yīng)用于單精度浮點(diǎn)乘法器設(shè)計(jì)。具體地，本設(shè)計(jì)在將24 bit乘法分解為8 bit乘法和9 bit乘法的基礎(chǔ)上，再次復(fù)用Karatsuba算法，將8 bit和9 bit的乘法運(yùn)算進(jìn)一步分解，使得原有的24 bit乘法運(yùn)算被分解為3 bit和4 bit的乘法運(yùn)算，從而使用更少的低位寬乘法器來實(shí)現(xiàn)更高比特的乘法運(yùn)算，可以減少乘法器的使用，進(jìn)一步簡化電路結(jié)構(gòu)，達(dá)到提高運(yùn)算速度的目的。另一方面，本設(shè)計(jì)同時(shí)結(jié)合Vedic算法設(shè)計(jì)一種基于加法運(yùn)算的乘法器，替換Karatsuba尾數(shù)乘法架構(gòu)中的3 bit和4 bit的乘法器，從而利用少量低比特加法器實(shí)現(xiàn)乘法運(yùn)算，降低硬件資源消耗和降低關(guān)鍵延時(shí)，提高單精度浮點(diǎn)乘法器運(yùn)算速度。如圖2所示，單精度浮點(diǎn)乘法器由數(shù)據(jù)分割處理模塊、符號位運(yùn)算模塊、階碼運(yùn)算模塊、尾數(shù)運(yùn)算模塊、標(biāo)準(zhǔn)化模塊等5個(gè)模塊組成。

圖2 浮點(diǎn)數(shù)乘法器的整體結(jié)構(gòu)

如圖2所示，本文對24 bit的尾數(shù)運(yùn)算(尾數(shù)部分在最高位隱藏了一個(gè)“1”，在計(jì)算浮點(diǎn)數(shù)乘法時(shí)要補(bǔ)上“1”)進(jìn)行改進(jìn)。本文的設(shè)計(jì)步驟主要分為3個(gè)階段：

1)將24 bit的乘法運(yùn)算通過Karatsuba算法分解為8 bit的乘法器、9 bit的乘法器、加法器和移位寄存器[1]；

2)再次利用Karatsuba算法對8 bit乘法器和9 bit乘法器進(jìn)行分解，分解成3 bit的乘法器和4 bit的乘法器、加法器和移位寄存器；

3)使用Vedic算法設(shè)計(jì)的3 bit Vedic乘法器和4 bit Vedic乘法器來代替階段2)的3 bit乘法器和4 bit乘法器。

以下是各個(gè)階段的具體實(shí)現(xiàn)方法。

階段1)：由式(11)可知，將24 bit的乘法運(yùn)算分解為8 bit和9 bit乘法運(yùn)算；階段2)：對式(5)～(10)中的乘法運(yùn)算進(jìn)行分解，拆分為3 bit和4 bit的乘法運(yùn)算。式(5)～(7)中的乘法運(yùn)算是8 bit的乘法運(yùn)算，式(8)～(10)中的乘法運(yùn)算是9 bit的乘法運(yùn)算。9 bit乘法運(yùn)算的分解方法和24 bit乘法運(yùn)算的分解方法一樣，把輸入進(jìn)行劃分，n的取值變?yōu)?。8 bit乘法運(yùn)算的分解方法為：

圖3 Vedic算法設(shè)計(jì)3 bit乘法器的流程圖

式中，W21、W22、X21、X22分別是W2、X2的高4位和低4位，此時(shí)n的取值為4。階段3)：為了進(jìn)一步提高單精度浮點(diǎn)乘法器的運(yùn)算速度，利用Vedic算法設(shè)計(jì)的3 bit Vedic乘法器和4 bit Vedic乘法器來代替Karatsuba算法分解后的3 bit、4 bit的乘法器。按照Vedic算法的思想使用加法器來搭建乘法器時(shí)使用了流水線設(shè)計(jì)方法。

Vedic算法可通過加法器來實(shí)現(xiàn)乘法運(yùn)算，其具有運(yùn)算簡單，實(shí)現(xiàn)的乘法運(yùn)算速度快、效率高、硬件資源消耗少的特點(diǎn)[12]?；赩edic算法設(shè)計(jì)3 bit Vedic乘法器流程如圖3所示。

如圖3所示，M是二進(jìn)制的(110)2，N是二進(jìn)制的(111)2。M2、M1、M0分別代表M的高1位、中間1位、低1位，N2、N1、N0分別代表N的高1位、中間1位、低1位。運(yùn)算步驟如下：

1)M0與N0相與的結(jié)果out0作為輸出結(jié)果的最低位S[0]；

2)M1與N0相與的結(jié)果再加上M0與N1相與的結(jié)果得到值out1，將out1[0]作為輸出結(jié)果的次低位S[1]；

3)out1[1]作為加數(shù)與M0和N2相與的值、M1和N1相與的值、M2和N0相與的值相加得到結(jié)果out2，將out2[0]作為輸出結(jié)果的S[2]；

4)out2[1:2]作為加數(shù)與M1和N2相與的值、M2和N1相與的值相加得到的結(jié)果out3，將out3[0]作為輸出結(jié)果的S[3]；

5)out3[1:2]作為加數(shù)與M2和N2相與的值相加得到結(jié)果out4，將out4作為輸出結(jié)果的S[5:4]。拼接S[5:4]、S[3]、S[2]、S[1]、S[0]的值得到輸出結(jié)果S。

4 bit Vedic乘法器設(shè)計(jì)流程與3 bit Vedic乘法器設(shè)計(jì)流程類似。如圖4所示，把式(8)中的W2加W1的結(jié)果A分割為高3位A2、中間3位A1、低3位A0，X2加X1的結(jié)果B分割為高3位B2、中間3位B1、低3位B0。按照Karatsuba算法的思想可以通過3 bit的Vedic乘法器(VM表示Vedic multiplier)和4 bit的Vedic乘法器實(shí)現(xiàn)9 bit的乘法運(yùn)算。9 bit乘法器的整體設(shè)計(jì)框如圖4所示。

圖4 9 bit乘法器的硬件設(shè)計(jì)框圖

同理，按照Karatsuba算法的思想通過8 bit乘法器和9 bit乘法器實(shí)現(xiàn)24 bit尾數(shù)相乘運(yùn)算。24 bit乘法器的整體設(shè)計(jì)框如圖5所示。

圖5 24 bit乘法器的硬件設(shè)計(jì)框圖

由圖5可知，得到24 bit尾數(shù)相乘的結(jié)果僅需要21個(gè)4 bit Vedic乘法器和9個(gè)3 bit Vedic乘法器。相比于文獻(xiàn)[3]的64個(gè)3 bit Vedic乘法器，本文設(shè)計(jì)減少了Vedic乘法器的迭代次數(shù)。

4 算法性能仿真與驗(yàn)證

本文設(shè)計(jì)的單精度浮點(diǎn)乘法器在Modelsim平臺上進(jìn)行仿真。隨機(jī)產(chǎn)生3000組32位浮點(diǎn)數(shù)測試數(shù)據(jù)ain和bin，執(zhí)行完乘法運(yùn)算后，在輸出數(shù)據(jù)有效指示信號dout_vld為高電平時(shí)得到輸出結(jié)果dout。

圖6給出了本文設(shè)計(jì)的單精度浮點(diǎn)乘法器的一個(gè)測試案例的仿真結(jié)果。由仿真結(jié)果可知，輸入ain以十六進(jìn)制表示為3f000000(即十進(jìn)制實(shí)數(shù)0.5)，輸入bin以十六進(jìn)制表示為3f400000(即十進(jìn)制實(shí)數(shù)0.75)，輸出結(jié)果dout以十六進(jìn)制表示為3ec00000 (即十進(jìn)制實(shí)數(shù)0.375)。根據(jù)仿真波形可得，單精度浮點(diǎn)乘法器的輸出結(jié)果需要延時(shí)5拍時(shí)鐘，仿真結(jié)果證明了本文所提出的單精度浮點(diǎn)乘法器設(shè)計(jì)方法的正確性。

圖6 浮點(diǎn)數(shù)乘法器的仿真結(jié)果

為了進(jìn)一步證明本文設(shè)計(jì)的有效性，利用Quartus II 64-bit 13.0.1平臺在相同的芯片Cyclone II EP2C5F256C6、Cyclone IV EP4CE6F17C6上綜合。表1給出了本文設(shè)計(jì)的單精度浮點(diǎn)乘法器與文獻(xiàn)[1]算法、文獻(xiàn)[3]算法設(shè)計(jì)的單精度浮點(diǎn)乘法器及Altera公司開發(fā)的浮點(diǎn)數(shù)乘法IP核的性能比較。

表1 5種浮點(diǎn)乘法器的性能參數(shù)對比

在相同的芯片Cyclone II EP2C5F256C6、Cyclone IV EP4CE6F17C6下，文獻(xiàn)[1]設(shè)計(jì)的單精度浮點(diǎn)乘法器最大時(shí)鐘頻率分別為59.11MHz、62.31 MHz。文獻(xiàn)[1]消耗的資源較少，是因?yàn)檠赜昧速Y源消耗少但工作頻率低的乘法器。文獻(xiàn)[3]設(shè)計(jì)的單精度浮點(diǎn)乘法器最大運(yùn)行時(shí)鐘頻率分別為148.28 MHz、159.06 MHz。相比于文獻(xiàn)[1]，文獻(xiàn)[3]設(shè)計(jì)的單精度浮點(diǎn)乘法器的最大運(yùn)行時(shí)鐘頻率提高了2.5倍，但是邏輯單元、寄存器及LUTs使用數(shù)量分別平均增多了約730個(gè)、700個(gè)和690個(gè)。本文二次復(fù)用Karatsuba算法把文獻(xiàn)[1]的9 bit和8 bit乘法運(yùn)算分解為3 bit和4 bit乘法運(yùn)算。本文二次復(fù)用Karatsuba算法實(shí)現(xiàn)的單精度浮點(diǎn)乘法器的最大時(shí)鐘頻率分別增大到73.86 MHz、80.89 MHz。二次復(fù)用Karatsuba算法的實(shí)驗(yàn)結(jié)果證明，文獻(xiàn)[1]設(shè)計(jì)的單精度浮點(diǎn)乘法器的最大時(shí)鐘頻率受限于乘法器。本文融合Karatsuba算法和Vedic算法兩者優(yōu)點(diǎn)設(shè)計(jì)的單精度浮點(diǎn)乘法器輸出結(jié)果需要延時(shí)5拍時(shí)鐘，相比于文獻(xiàn)[1]的8拍時(shí)鐘、文獻(xiàn)[3]的9拍時(shí)鐘，延時(shí)更短，響應(yīng)時(shí)間更快。本文融合Karatsuba算法和Vedic算法優(yōu)點(diǎn)實(shí)現(xiàn)的單精度浮點(diǎn)乘法器的最大時(shí)鐘頻率是相對最優(yōu)的，分別達(dá)到313.58 MHz、331.35 MHz。相比于文獻(xiàn)[1]、文獻(xiàn)[3]、浮點(diǎn)數(shù)乘法IP核，本文融合Karatsuba算法和Vedic算法兩者優(yōu)點(diǎn)設(shè)計(jì)的單精度浮點(diǎn)乘法器的最大時(shí)鐘頻率分別平均提高了5.30倍、2.10倍、1.97倍。本文融合Karatsuba算法和Vedic算法優(yōu)點(diǎn)設(shè)計(jì)的單精度浮點(diǎn)乘法器比文獻(xiàn)[3]的邏輯單元、寄存器及LUTs分別平均降低了22個(gè)、330個(gè)、127個(gè)，比文獻(xiàn)[1]的邏輯單元、寄存器及LUTs分別平均增加了706個(gè)、375個(gè)、559個(gè)，比浮點(diǎn)數(shù)乘法IP核的邏輯單元、寄存器及LUTs分別平均增加了938個(gè)、285個(gè)、778個(gè)，但是在硬件資源可以接受的范圍下獲得了更高的最大時(shí)鐘頻率，降低了輸出延時(shí)，提高了運(yùn)算速度。同時(shí)本文融合Karatsuba算法和Vedic算法優(yōu)點(diǎn)設(shè)計(jì)的單精度浮點(diǎn)乘法器的功耗分別是40.38 mW、75.27 mW。在芯片Cyclone II EP2C5F256C6下，本文設(shè)計(jì)的單精度浮點(diǎn)乘法器相比于文獻(xiàn)[1]、文獻(xiàn)[3]、浮點(diǎn)數(shù)乘法IP核分別降低了0.68 mW、0.35 mW、0.21 mW。在芯片Cyclone IV EP4CE6F17C6下，本文設(shè)計(jì)的單精度浮點(diǎn)乘法器相比于文獻(xiàn)[1]、文獻(xiàn)[3]、浮點(diǎn)數(shù)乘法IP核分別降低了9.03 mW、9.21 mW、3.0 mW。本文所提出的設(shè)計(jì)方法在需要計(jì)算大量數(shù)據(jù)的人工智能領(lǐng)域更具有優(yōu)勢，更能滿足計(jì)算實(shí)時(shí)性的需求，具有一定的實(shí)用價(jià)值。

5 結(jié)束語

本文優(yōu)化了Karatsuba算法并利用該算法設(shè)計(jì)了基于IEEE754標(biāo)準(zhǔn)的單精度浮點(diǎn)乘法器。設(shè)計(jì)充分利用了Karatsuba算法可以減少乘法器數(shù)量的優(yōu)點(diǎn)和Vedic算法可以用簡單的加法器實(shí)現(xiàn)乘法功能而門延遲和面積增加很緩慢的優(yōu)點(diǎn)，通過二次復(fù)用Karatsuba算法來減少乘法器的數(shù)量，降低單精度浮點(diǎn)乘法器復(fù)雜度；再通過Vedic算法設(shè)計(jì)的3 bit、4 bit Vedic乘法器來替換本文設(shè)計(jì)中需要用到的3 bit乘法器和4 bit乘法器，并在Vedic算法設(shè)計(jì)的3 bit乘法器、4 bit的乘法器中運(yùn)用了流水線設(shè)計(jì)方法來優(yōu)化結(jié)構(gòu)，提高設(shè)計(jì)的運(yùn)行時(shí)鐘頻率、運(yùn)算效率及運(yùn)算速度。在相同的平臺和芯片型號下，本文設(shè)計(jì)的單精度浮點(diǎn)乘法器的最大時(shí)鐘頻率相比于文獻(xiàn)[1]、文獻(xiàn)[3]、浮點(diǎn)數(shù)乘法IP核分別平均提高了5.30倍、2.10倍、1.97倍。

本文研究工作得到羊城創(chuàng)新創(chuàng)業(yè)領(lǐng)軍人才支持計(jì)劃的資助(2019019)，在此表示感謝。