基于Karatsuba和Vedic算法的快速單精度浮點乘法器

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

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

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

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

1 浮點數乘法原理

本文設計的單精度浮點乘法器基于IEEE754標準[11]。單精度浮點數的表示格式由4字節組成，分為3個部分。第1部分為符號位，占1 bit；第二部分為階碼部分，占8 bit；第三部分為尾數部分，占23 bit。一個實數H的浮點數表示形式為：

式中，C表示符號位；Z表示尾數部分，在浮點數運算時要補上隱藏的‘1’，轉換成{1,Z}；E表示階碼，在實數轉換為浮點數格式時要減去相應的偏移量。

單精度浮點數乘法運算可以簡單分為4個步驟。

1)兩個乘數的符號位進行異或運算。根據異或的結果決定最后計算結果的正負性。若符號位異或的結果為1，則浮點數相乘的結果是負數，若異或的結果為0，則浮點數相乘的結果是正數。

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

3)尾數部分補上隱藏的‘1’，執行尾數相乘操作，得到相乘的結果V。

4)步驟3)相乘結果V的最高位的值決定標準化結果尾數的取值。若最高位為1，則取V[46:24]位作為最后標準化結果的尾數；若最高位是0，則取V[45:23]位作為最后標準化結果的尾數。聯合符號位的值、階碼的值和尾數的值到兩個浮點數相乘的結果。

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

圖1 浮點數乘法運算的流程框圖

2 Karatsuba算法

傳統單精度浮點乘法器中的尾數相乘實現方法如下所示[1]：

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

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

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

3 本文設計

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

圖2 浮點數乘法器的整體結構

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

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

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

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

以下是各個階段的具體實現方法。

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

圖3 Vedic算法設計3 bit乘法器的流程圖

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

Vedic算法可通過加法器來實現乘法運算，其具有運算簡單，實現的乘法運算速度快、效率高、硬件資源消耗少的特點[12]?；赩edic算法設計3 bit Vedic乘法器流程如圖3所示。

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

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

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

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

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

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

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

圖4 9 bit乘法器的硬件設計框圖

同理，按照Karatsuba算法的思想通過8 bit乘法器和9 bit乘法器實現24 bit尾數相乘運算。24 bit乘法器的整體設計框如圖5所示。

圖5 24 bit乘法器的硬件設計框圖

由圖5可知，得到24 bit尾數相乘的結果僅需要21個4 bit Vedic乘法器和9個3 bit Vedic乘法器。相比于文獻[3]的64個3 bit Vedic乘法器，本文設計減少了Vedic乘法器的迭代次數。

4 算法性能仿真與驗證

本文設計的單精度浮點乘法器在Modelsim平臺上進行仿真。隨機產生3000組32位浮點數測試數據ain和bin，執行完乘法運算后，在輸出數據有效指示信號dout_vld為高電平時得到輸出結果dout。

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

圖6 浮點數乘法器的仿真結果

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

表1 5種浮點乘法器的性能參數對比

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

5 結束語

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

本文研究工作得到羊城創新創業領軍人才支持計劃的資助(2019019)，在此表示感謝。