采用Karatsuba 算法在FPGA 上實現(xiàn)雙精度浮點乘法

康 磊，徐英卓

(西安石油大學(xué)計算機(jī)學(xué)院，陜西西安710065)

浮點運算廣泛應(yīng)用于諸多領(lǐng)域，特別是在科學(xué)計算、數(shù)值分析和信號處理等方面，如數(shù)字濾波器、FFT、圖像處理等。在所有的浮點算術(shù)運算中，乘法是其核心算法之一，如何構(gòu)建高效的浮點乘法器一直是人們關(guān)注的焦點。隨著FPGA技術(shù)的發(fā)展，由于FPGA器件本身的優(yōu)勢——速度、邏輯資源、豐富的IP核等，使得采用FAPG實現(xiàn)通用高性能的運算器成為可能。按照IEEE754中定義的雙精度浮點數(shù)的尾數(shù)有53 bit，采用FGAP實現(xiàn)53 bit×53 bit的硬件乘法器需要占用大量的硬件資源［1-2］。本文詳細(xì)說明了采用Karatsuba算法在FPGA上實現(xiàn)了雙精度浮點乘法器的過程。

1 雙精度浮點數(shù)格式

IEEE754是使用最廣泛的浮點數(shù)運算標(biāo)準(zhǔn)，常用的浮點數(shù)有單精確度(32 bit)和雙精確度(64 bit)2 種［3］。

單精度浮點數(shù)的格式:

雙精度浮點數(shù)的格式:

浮點運算器的運算包含加、減、乘、除、平方和開方等。通常情況下，在運算之前需要將浮點數(shù)分解為符號位、階碼和尾數(shù)，然后進(jìn)行運算，各部分運算結(jié)束后，還要經(jīng)過舍入和規(guī)格化，最后再將符號、階碼和指數(shù)重構(gòu)得到結(jié)果。本文只討論雙精度浮點數(shù)的乘法運算。浮點乘法器雖然是一個簡單的算術(shù)單元，但由于它需要一個53 bit位的乘法器，因此在使用FPGA實現(xiàn)時需要考慮硬件資源的消耗和時間。

2 浮點乘法運算過程

浮點乘法運算規(guī)則的通式為:X×Y=(－1)SX+SY×(MX×MY)×2EX+EY。式中X和Y為2個輸入的浮點數(shù)，其中SX和SY是符號位，MX和MY是尾數(shù)，EX和EY是階碼。雙精度浮點乘法運算流程如圖1所示，其操作步驟如下:

(1)輸入的操作數(shù)先是被分成1 bit符號位、11 bit階碼和53 bit尾數(shù)(包括隱藏位);

(2)判斷2個操作數(shù)中是否存在0，若是則轉(zhuǎn)向(9);

(3)2個運算數(shù)的符號位進(jìn)行異或運算，結(jié)果就是乘法運算結(jié)果的符號位結(jié)果;

(4)將階碼相加，然后減去1 023，得到乘法運算的階碼結(jié)果;

(5)尾數(shù)相乘，得到106位的結(jié)果;

(6)對運算的結(jié)果進(jìn)行規(guī)格化處理，即對尾數(shù)的106位結(jié)果左移至最高位是1為止，然后取第106位到54位;

(7)對尾數(shù)的53到1位按照舍入原則進(jìn)行舍入操作，通常采用的默認(rèn)模式是最近舍入(Round to Nearest);

(8)對階碼結(jié)果進(jìn)行判溢處理，設(shè)置階碼和尾數(shù)的最后結(jié)果;

(9)將符號位、階碼和尾數(shù)的結(jié)果重新拼接成64 bit的運算結(jié)果。

圖1 浮點乘法運算流程Fig．1 Flowchart for floating-point multiplication

3 用Karatsuba算法實現(xiàn)尾數(shù)乘法運算

因此有

其中:r2=P1Q1;r1=P1Q0+P0Q1;r0=P0Q0。

從式(1)可以看出，實現(xiàn)P×Q可以將乘法器的位數(shù)由n位降低為m位(m=n/2)，乘法器的尾數(shù)降低了一半，但是需要做4次乘法操作。

Karatsuba乘法算法［4］是將式(1)中的r1做如下變換:

變換后的式(2)中r1的2次乘法運算變成了1次，但需要增加加法的次數(shù)，而加法的運算時間要比乘法小得多。

Karatsuba算法還可以進(jìn)一步擴(kuò)展，將2個乘數(shù)分解成更多的項數(shù)。若將2個乘數(shù)表示分解為3項，P和Q可寫為

其中:r2=P2Q2;r1=P1Q1;r0=P0Q0;s2=P2Q1+P1Q2;s1=P2Q0+P0Q2;s0=P1Q0+P0Q1。

式(3)使得乘法器的位數(shù)更少，但是需要9次乘法運算，若采用式(2)的方法對式(3)中的s2～s0進(jìn)行如下變換:可以將乘法運算減少為6次。

4 FPGA實現(xiàn)

本文采用Altera公司的EP2C70896C6芯片實現(xiàn)浮點乘法器，由于該芯片內(nèi)部乘法器單元是18 bit×18 bit的。因此，將雙精度浮點數(shù)的53 bit(含隱含的整數(shù)位1 bit)尾數(shù)進(jìn)行如下分解(即式(3)中m=18，b=2):

從式(3)和式(4)可以看出，實現(xiàn)r0～r2需要18 bit的無符號乘法器，s0～s2需要19 bit的無符號乘法器。由于EP2C70896C6芯片內(nèi)部的乘法器是18 bit的，因此，實現(xiàn)19 bit的乘法需要2個18 bit的乘法器，為了節(jié)省資源需要對其運算過程再次進(jìn)行改進(jìn)。19 bit乘法器的改進(jìn)算法如圖2所示。

圖2 19 bit乘法器改進(jìn)算法Fig．2 Improved algorithm of 19bit multiplier

圖2 所示計算過程中的中間結(jié)果P0可以使用1個dsp_18(18 bit×18 bit的乘法單元)來實現(xiàn)，而P1～P3可以只用邏輯資源來實現(xiàn)。這樣計算53 bit的尾數(shù)乘法只需要6個dsp_18就可以實現(xiàn)了，而且也可以有效減少電路時延。

圖2方法實現(xiàn)的19 bit×19 bit的Verilog HDL模塊如下:

module mul_19b(a，b，out);

input［18:0］a，b;

output［37:0］out;

wire［37:0］out_P0，out_P1，out_P2，out_P3;

wire［35:0］out_Pt0;

lpm_mult0 mul_18x18(．dataa(a［17:0］)，．datab(b［17:0］)，．result(out_Pt0));

assign out_P0={2'b0，out_Pt0};

assign out_P1=a［18］? {2'b0，b［17:0］，18'b0}:38'b0;

assign out_P2=b［18］? {2'b0，a［17:0］，18'b0}:38'b0;

assign out_P3={1'b0，a［18］＆b［18］，36'b0};

assign out=out_P0+out_P1+out_P2+out_P3;

endmodule

5 結(jié)果

Karatsuba算法實現(xiàn)的尾數(shù)乘法運算的時序仿真如圖3所示，圖中p、q是輸入的53 bit尾數(shù)，out和out2分別是Karatsuba算法和IP核乘法運算結(jié)果，可以看出兩者結(jié)果相同。

圖3 Karatsuba和IP核乘法結(jié)果比較Fig．3 Comparison of Karatsuba and IP nuclear multiplication results

采用QuatusII提供的IP核實現(xiàn)尾數(shù)乘法需要9個18 bit的乘法器及252個LUT，而采用Karatsuba算法(式(3))實現(xiàn)尾數(shù)乘法，只需要6個18 bit的乘法器，此外，還需要6個18 bit的加法器、3個36 bit的加法器和3個38 bit的減法器，若按照通常情況下一個N位加法器需要N個LUT來實現(xiàn)的話，那么該電路還需要6*18+3*36+3*38=330個LUT。如果將一個18 bit的乘法器用LUT實現(xiàn)需要437個LUT，因此，減少3個乘法器可以減少4*437=1 748個LUT?？梢钥闯霾捎肒aratsuba算法可以明顯節(jié)省FPGA的資源，經(jīng)仿真測試Karatsuba算法的乘法器相比于IP核的乘法器會增加大約11 ns的延時，如果采用流水線運算可以提高運算速度。

［1］ Jang J，Choi S，Prasanna V K K．Area and time efficient implementations of matrix multiplication on FPGAs［C］．2002 IEEE International Conference on Field Programmable Technology．Seoul，South Korea:IEEE，2002．

［2］ Akkas A，Schuhe M．A Quadruple precision and dual double precision floating-point multiplier［C］．Proc of Euromicro Symp Digital System Design(DSD＇03)，2003．

［3］ IEEE，IEEE standard floating-point arithmetic．IEEE Std 754-2008［S］．The Insitute of Electrical and Electronic Engineers，2008．

［4］ Karatsuba A．，Ofman Y．Multiplication of many-digital numbers by automatic computers［J］．Doklady Akad Nauk SSSR，1962，145(2):293-294．