康 磊，徐英卓

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

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

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

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

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

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

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

2 浮點(diǎn)乘法運(yùn)算過(guò)程

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

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

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

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

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

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

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

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

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

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

圖1 浮點(diǎn)乘法運(yùn)算流程Fig．1 Flowchart for floating-point multiplication

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

因此有

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

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

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

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

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

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

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

4 FPGA實(shí)現(xiàn)

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

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

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

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

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

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

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

［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．