彭章國(guó)1，張征宇1,2，王學(xué)淵1，賴(lài)瀚軒1，茆驥1

　?。?. 西南科技大學(xué) 信息工程學(xué)院，四川 綿陽(yáng) 621010；2. 中國(guó)空氣動(dòng)力研究與發(fā)展中心，四川 綿陽(yáng) 621000）

       摘要：針對(duì)現(xiàn)有的采用Booth算法與華萊士（Wallace）樹(shù)結(jié)構(gòu)設(shè)計(jì)的浮點(diǎn)乘法器運(yùn)算速度慢、布局布線(xiàn)復(fù)雜等問(wèn)題，設(shè)計(jì)了基于FPGA的流水線(xiàn)精度浮點(diǎn)數(shù)乘法器。該乘法器采用規(guī)則的Vedic算法結(jié)構(gòu)，解決了布局布線(xiàn)復(fù)雜的問(wèn)題；使用超前進(jìn)位加法器（Carry Lookahead Adder，CLA）將部分積并行相加，以減少路徑延遲；并通過(guò)優(yōu)化的4級(jí)流水線(xiàn)結(jié)構(gòu)處理，在Xilinx ISE 14.7軟件開(kāi)發(fā)平臺(tái)上通過(guò)了編譯、綜合及仿真驗(yàn)證。結(jié)果證明，在相同的硬件條件下，本文所設(shè)計(jì)的浮點(diǎn)乘法器與基4-Booth算法浮點(diǎn)乘法器消耗時(shí)鐘數(shù)的比值約為兩者消耗硬件資源比值的1.56倍。

　　關(guān)鍵詞：浮點(diǎn)乘法器;超前進(jìn)位加法器;華萊士樹(shù);流水線(xiàn)結(jié)構(gòu);Vedic算法;Booth算法

　　中圖分類(lèi)號(hào)：TP331.2文獻(xiàn)標(biāo)識(shí)碼：ADOI： 10.19358/j.issn.1674-7720.2017.04.022

　　引用格式：彭章國(guó)，張征宇，王學(xué)淵，等.基于FPGA的流水線(xiàn)單精度浮點(diǎn)數(shù)乘法器設(shè)計(jì)［J］.微型機(jī)與應(yīng)用，2017,36（4）：74-77,83.

0引言

　　*基金項(xiàng)目： 國(guó)家自然科學(xué)基金（51475453）；國(guó)家自然科學(xué)基金（11472297）浮點(diǎn)乘法器（eFloating Point Multiplier，F(xiàn)PM）是數(shù)字信號(hào)處理（eDigital Signal Processing，DSP）、視頻圖像處理以及信號(hào)識(shí)別等應(yīng)用鄰域重要的運(yùn)算單元。尤其是在視頻圖像處理領(lǐng)域，隨著對(duì)高速海量圖像數(shù)據(jù)處理的實(shí)時(shí)性要求逐漸提高，設(shè)計(jì)一種具有更高速率、低功耗、布局規(guī)律、占用面積小和集成度高的浮點(diǎn)乘法器極其重要。

　　陣列乘法器是采用移位與求和的算法而設(shè)計(jì)的一種乘法器［1］。陣列乘法器具有規(guī)則的結(jié)構(gòu)，易于布局布線(xiàn)等特點(diǎn)。隨著乘數(shù)位寬的增加，部分乘積的個(gè)數(shù)也成倍地增加，部分乘積項(xiàng)數(shù)目決定了求和運(yùn)算的次數(shù)，直接影響乘法器的速度。修正的Booth算法對(duì)乘數(shù)重新編碼，可以減少相加的部分乘積的數(shù)量，因?yàn)椴糠址e的存在，部分積相加過(guò)程與陣列乘法器沒(méi)有太大差異。為了實(shí)現(xiàn)速度的提高，Wallace樹(shù)結(jié)構(gòu)可以改變部分積求和方式，將求和級(jí)數(shù)從O（N）減少到O（logN）。因此現(xiàn)有很多乘法器設(shè)計(jì)都采用修正的Booth算法與Wallace樹(shù)結(jié)構(gòu)相結(jié)合的方法。但是Wallace樹(shù)結(jié)構(gòu)缺乏規(guī)整性，布局布線(xiàn)困難；引線(xiàn)的延長(zhǎng)導(dǎo)致寄生電容增加，妨礙了電路速度的進(jìn)一步提高。同時(shí)不規(guī)則的結(jié)構(gòu)會(huì)增加硅板的面積，并且由于路由復(fù)雜而導(dǎo)致中間連接過(guò)程的增多，繼而導(dǎo)致功耗的增大［23］。

　　吠陀乘法器具有其獨(dú)特規(guī)則的結(jié)構(gòu)，隨著乘數(shù)位寬的增加，門(mén)延遲和面積的增加很緩慢，因此乘法器能夠在時(shí)間延遲、面積、功耗上達(dá)到最優(yōu)。文獻(xiàn)［4］設(shè)計(jì)了一種高速的4×4位吠陀乘法器，通過(guò)實(shí)驗(yàn)證明了4×4位吠陀乘法器比同位寬的陣列乘法器、Booth算法乘法器的運(yùn)算速度快；文獻(xiàn)［5］設(shè)計(jì)了單精度的浮點(diǎn)乘法器，其中尾數(shù)計(jì)算部分分別采用了吠陀乘法器和Booth算法乘法器兩種方法，結(jié)果證明吠陀乘法器在時(shí)間延遲和面積上都優(yōu)于Booth算法乘法器；文獻(xiàn)［6］在吠陀乘法器中分別采用行波進(jìn)位加法器（eRipple Carry Adders，RCA）和超前進(jìn)位加法器（eCarry Lookahead Adder，CLA）計(jì)算部分乘積的和，通過(guò)實(shí)驗(yàn)數(shù)據(jù)對(duì)比，采用超前進(jìn)位加法器可以獲得更高的速度和占更少的面積。然而對(duì)于海量的圖像數(shù)據(jù)進(jìn)行浮點(diǎn)數(shù)乘法運(yùn)算時(shí)，每一組數(shù)據(jù)從運(yùn)算開(kāi)始到結(jié)束期間會(huì)產(chǎn)生時(shí)間延遲，可以在乘法器中加入流水線(xiàn)結(jié)構(gòu)來(lái)減少延遲時(shí)間，為此本文設(shè)計(jì)了一種基于吠陀數(shù)學(xué)的流水線(xiàn)浮點(diǎn)乘法器。

1總體設(shè)計(jì)

　　本文所設(shè)計(jì)的單精度浮點(diǎn)數(shù)乘法器主要包含以下幾個(gè)部分：24位吠陀乘法器、一個(gè)8位無(wú)符號(hào)加法器、一個(gè)9位無(wú)符號(hào)減法器、一個(gè)符號(hào)位計(jì)算單元和一個(gè)標(biāo)準(zhǔn)化單元。其結(jié)構(gòu)框圖如圖1所示。

　　1.1符號(hào)位與階碼計(jì)算

　　IEEE 754標(biāo)準(zhǔn)［7］為二進(jìn)制浮點(diǎn)運(yùn)算提供了一個(gè)精確的浮點(diǎn)數(shù)格式計(jì)算規(guī)范操作及異常處理。這一標(biāo)準(zhǔn)定義了32位單精度浮點(diǎn)數(shù)和64位雙精度浮點(diǎn)數(shù)兩種類(lèi)型。它們都分別由符號(hào)位、尾數(shù)、階碼組成，表1給出了單精度浮點(diǎn)數(shù)格式，由式（1）表示為：

　　式中S 代表符號(hào)位；Exp表示階碼；Bias為固定值，其值為127；M為尾數(shù)。

　?。?）符號(hào)位計(jì)算：兩個(gè)數(shù)相乘的結(jié)果的符號(hào)位由這兩個(gè)乘數(shù)的符號(hào)位相異或（）得到，如式（2）所示。

　　S=S1S2（2）

　　式中S1、S2為兩個(gè)單精度度浮點(diǎn)數(shù)的符號(hào)位，S 為兩者之間的異或結(jié)果。

　?。?）階碼計(jì)算：該加法器模塊主要將兩個(gè)乘數(shù)的階碼相加，其結(jié)果再減去偏差值而得到相乘后結(jié)果的階碼，如式（3）所示。

　　PExp=AExp+BExp-Bias（3）

　　式中AExp、BExp為兩個(gè)單精度浮點(diǎn)數(shù)的階碼；Bias為固定值，其值為127。

　　1.224位吠陀乘法器的邏輯電路設(shè)計(jì)

　　吠陀乘法器是基于吠陀數(shù)學(xué)而設(shè)計(jì)的。吠陀數(shù)學(xué)是Sri Bharati Krishna Tirthaji（巴拉蒂·克里希納·第勒塔季）在研究印度古代吠陀經(jīng)文的基礎(chǔ)上重構(gòu)的數(shù)學(xué)計(jì)算體系，其中包括了算術(shù)、代數(shù)、幾何、三角函數(shù)和微積分等學(xué)科的處理方法。本文設(shè)計(jì)的24位吠陀乘法器是基于Urdhva Tiryakbhyam 圖22×2吠陀乘法器Sutra（字面意思是垂直和橫向）而設(shè)計(jì)的，2位吠陀乘法器的結(jié)構(gòu)框圖如圖2所示，它由4個(gè)與門(mén)和2個(gè)半加器組成，它是24位吠陀乘法器的基本組成單元。

　　根據(jù)2位吠陀乘法器的結(jié)構(gòu)，一個(gè)4位吠陀乘法器可以分解為4個(gè)2位吠陀乘法器和3個(gè)4位加法器，如圖3所示。

　　同理，一個(gè)8位吠陀乘法器可以由4個(gè)4位吠陀乘法器和3個(gè)8位加法器組成，因此，n位的吠陀乘法器能夠使用4個(gè)n/2位吠陀乘法器和3個(gè)n位的加法器實(shí)現(xiàn)。綜上，n位的吠陀乘法器被分解成n/2個(gè)n/2位的乘法器，然后這些較小位寬的乘法器（n/2位）再次分為更小位寬的乘法器（n/4位），直到被乘數(shù)位寬為2位，從而簡(jiǎn)化整個(gè)增殖過(guò)程。

　　由吠陀乘法器的結(jié)構(gòu)可知，乘法器中會(huì)用到進(jìn)位加法器將各部分積并行相加，隨著加法器的引入，必然會(huì)產(chǎn)生路徑時(shí)間延遲，從而降低乘法器的運(yùn)算速度。本文使用CLA先行求得多位加法各位間的進(jìn)位值，它由進(jìn)位位產(chǎn)生進(jìn)位，各進(jìn)位彼此獨(dú)立，不依賴(lài)于進(jìn)位傳播，從而減少等待進(jìn)位所需要的時(shí)間延遲。其推導(dǎo)過(guò)程如下：

　　設(shè)二進(jìn)制加法器的第i位為 Ai 和 Bi ，輸出為Si，進(jìn)位輸入為 Ci，進(jìn)位輸出為 Ci+1，則有：

　　Si=Ai+Bi+Ci（4）

　　Ci+1=Ai&Bi+Ci&(Ai+Bi)（5）

　　令：Gi=Ai&Bi，Pi=Ai+Bi ，則有：

　　Ci+1=Gi+Ci&Pi（6）

　　只要 Gi=1 ，就會(huì)產(chǎn)生向 Ci+1 位的進(jìn)位，稱(chēng) Gi 為進(jìn)位產(chǎn)生函數(shù)。同樣，只要Pi=1，就會(huì)把 Ci 傳遞到 Ci+1 位；其中 Pi 為進(jìn)位傳遞函數(shù)。隨著位數(shù)的增加式（5）會(huì)加長(zhǎng)，但總保持三個(gè)邏輯級(jí)的深度，因此形成進(jìn)位的延遲是與位數(shù)無(wú)關(guān)的常數(shù)。

　　24位吠陀乘法器結(jié)構(gòu)圖如圖4所示，其中包括1個(gè)16位吠陀乘法器、2個(gè)16×8位吠陀乘法器、1個(gè)8位吠陀乘法器、3個(gè)CLA。

　　1.3流水線(xiàn)結(jié)構(gòu)設(shè)計(jì)

　　為了提高FPM對(duì)批量數(shù)據(jù)的運(yùn)算速度，根據(jù)乘法器內(nèi)部獨(dú)特的結(jié)構(gòu)，乘法器中采用了4級(jí)流水線(xiàn)進(jìn)行處理，如圖5所示。通過(guò)對(duì)24位吠陀乘法器的結(jié)構(gòu)進(jìn)行分析可知，該乘法器主要由4個(gè)不同位寬的吠陀乘法器級(jí)聯(lián)而成，因此從最基本的2位吠陀乘法器單元出發(fā)，在每一個(gè)乘法器單元中加入了移位寄存器，形成流水線(xiàn)結(jié)構(gòu)。

2實(shí)驗(yàn)結(jié)果與分析

　　整個(gè)FPM設(shè)計(jì)使用Verilog HDL語(yǔ)言描述，然后在Xilinx ISE14.7集成軟件環(huán)境下進(jìn)行了編譯、綜合及功能仿真，最后在XiLinx公司的Virtex6（xc6vlx240t-1ff1156 ）硬件實(shí)驗(yàn)平臺(tái)上進(jìn)行了驗(yàn)證。FPM中尾數(shù)乘積部分是其最重要的部分，因此設(shè)計(jì)了采用Vedic、基2-Booth、基4-Booth三種算法的24位無(wú)符號(hào)整數(shù)乘法器，并對(duì)三種算法的乘法器消耗的硬件資源進(jìn)行了對(duì)比，如表2所示。

　　由表2可知，由于乘法器中每一級(jí)都包含了3個(gè)CLA，Vedic算法乘法器消耗的LUTs數(shù)目是三種算法乘法器中最多的，而在其他方面的資源消耗是最少的?；?-Booth算法乘法器相對(duì)于基2Booth算法乘法器消耗了更多的資源。

　　形如圖6~圖8所示。其中基2-Booth算法完成一次計(jì)算需要52個(gè)時(shí)鐘周期，基4-Booth算法需要15個(gè)時(shí)鐘周期，而Vedic算法乘法器由組合邏輯電路設(shè)計(jì)而成，不需要消耗時(shí)鐘周期。　　

　　表3列出了基2Booth、基4-Booth兩種算法設(shè)計(jì)的FPM與本文設(shè)計(jì)的基于吠陀數(shù)學(xué)的流水線(xiàn)FPM在消耗FPGA資源數(shù)目上的對(duì)比。

　　由表3所知，三種方法的FPM在資源、時(shí)鐘周期消耗上與無(wú)符號(hào)整數(shù)乘法器所得結(jié)論基本一致。其中基2Booth算法FPM完成一次計(jì)算需要52個(gè)時(shí)鐘周期，基4-Booth算法需要24個(gè)時(shí)鐘周期，Vedic算法的浮點(diǎn)乘法器需要9個(gè)時(shí)鐘周期。綜上，Vedic算法FPM在運(yùn)算速度上更快，這是因?yàn)榉屯映朔ㄆ鞯牟糠址e并行相加的結(jié)果，采用高速的超前進(jìn)位加法器，使得運(yùn)算速度進(jìn)一步提升。三種算法的浮點(diǎn)數(shù)乘法器的仿真波形如圖9~圖11所示。

　　通過(guò)計(jì)算基4-Booth FPM與本文設(shè)計(jì)的FPM消耗資源、時(shí)鐘周期數(shù)目的比值發(fā)現(xiàn)，本文設(shè)計(jì)的FPM與基4-Booth算法FPM消耗時(shí)鐘數(shù)的比值約為兩者消耗FPGA資源比值的1.56倍。

3結(jié)論

　　本文設(shè)計(jì)了一種基于吠陀數(shù)學(xué)的流水線(xiàn)FPM。乘法器采用Vedic算法，并在其結(jié)構(gòu)中采用超前進(jìn)位保留加法器將產(chǎn)生的部分積結(jié)果并行相加，從而減少了電路延遲，4級(jí)流水線(xiàn)結(jié)構(gòu)也使得乘法器運(yùn)算速度進(jìn)一步得到了提高。相比于華萊士樹(shù)算法相結(jié)合設(shè)計(jì)的乘法器，吠陀乘法器具有較規(guī)則的結(jié)構(gòu)，容易布局布線(xiàn)。雖然本文設(shè)計(jì)的浮點(diǎn)乘法器消耗了更多的資源，但是在速度上獲得了提高。

　　參考文獻(xiàn)

　?。?］ 胡正偉，仲順安． 一種多功能陣列乘法器的設(shè)計(jì)方法［J］. 計(jì)算機(jī)工程， 2007, 33(22): 2325.

　?。?］ 夏煒， 肖鵬． 一種高效雙精度浮點(diǎn)乘法器［J］. 計(jì)算機(jī)測(cè)量與控制，2013, 21(4): 10171020.

　?。?］ 李飛雄, 蔣林．一種結(jié)構(gòu)新穎的流水線(xiàn) Booth 乘法器設(shè)計(jì)［J］. 電子科技， 2013, 26(8):4648.

　?。?］ KARTHIK S, UDAYABHAUN P. FPGA implementation of high speed vedic multipliers［C］.International Journal of Engineering Research and Technology. ESRSA Publications, 2012, 1(10).