石　敏　王　耿　易清明

(暨南大學(xué)信息科學(xué)技術(shù)學(xué)院　廣東 廣州 510632)

?

基于改進(jìn)的Booth編碼和Wallace樹(shù)的乘法器優(yōu)化設(shè)計(jì)

石敏王耿易清明

(暨南大學(xué)信息科學(xué)技術(shù)學(xué)院廣東 廣州 510632)

摘要針對(duì)當(dāng)前乘法器設(shè)計(jì)難于兼顧路徑延時(shí)和版圖面積的問(wèn)題，設(shè)計(jì)一種新型的32位有符號(hào)數(shù)乘法器結(jié)構(gòu)。其特點(diǎn)是：采用改進(jìn)的Booth編碼，生成排列規(guī)則的部分積陣列，所產(chǎn)生的電路相比于傳統(tǒng)的方法減小了延時(shí)與面積；采用由改進(jìn)的4-2壓縮器和3-2壓縮器相結(jié)合的新型Wallace樹(shù)壓縮結(jié)構(gòu)，將17個(gè)部分積壓縮為2個(gè)部分積只需經(jīng)過(guò)10級(jí)異或門(mén)延時(shí)，有效地提高了乘法運(yùn)算的速度。設(shè)計(jì)使用FPGA開(kāi)發(fā)板進(jìn)行測(cè)試，并采用基于SMIC 0.18 μm的標(biāo)準(zhǔn)單元工藝進(jìn)行綜合，綜合結(jié)果顯示芯片面積為0.1127 mm2，關(guān)鍵路徑延時(shí)為3.4 ns。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的乘法器既減少了關(guān)鍵路徑延時(shí)，又縮小了版圖面積。

關(guān)鍵詞乘法器Booth編碼部分積陣列Wallace樹(shù)

0引言

乘法器是進(jìn)行數(shù)字信號(hào)處理的核心，同時(shí)也是微處理器中進(jìn)行數(shù)據(jù)處理的關(guān)鍵部件。其運(yùn)行速度基本決定了微處理器的速度，故乘法器速度和面積的優(yōu)化對(duì)于整個(gè)CPU的性能來(lái)說(shuō)是非常重要的。乘法器的設(shè)計(jì)過(guò)程中，最關(guān)鍵的就是部分積的產(chǎn)生和部分積的壓縮，與其相關(guān)的技術(shù)為Booth編碼和Wallace樹(shù)型結(jié)構(gòu)[1]。

目前，許多研究針對(duì)Booth編碼和部分積的壓縮提出了改進(jìn)措施[2-6]。例如，文獻(xiàn)[3]通過(guò)采用選擇器結(jié)構(gòu)來(lái)替換傳統(tǒng)的與或門(mén)，提高了部分積電路的性能；文獻(xiàn)[4]為了減少信號(hào)翻轉(zhuǎn)率，重新設(shè)計(jì)了Booth編碼電路，降低了功耗；文獻(xiàn)[5]通過(guò)簡(jiǎn)化部分積產(chǎn)生電路，減小了版圖面積。以上分別就電路結(jié)構(gòu)對(duì)部分積生成電路進(jìn)行了改進(jìn)，改進(jìn)后的電路優(yōu)化了版圖面積，但是也增加了不必要的門(mén)延時(shí)。文獻(xiàn)[6]將部分積分拆重組，改進(jìn)后的重組模塊有利于部分積的快速壓縮，但也因此增加了版圖面積。乘法器的設(shè)計(jì)一直以來(lái)都是在面積和速度中去權(quán)衡，往往很難兩者兼顧。本文為了設(shè)計(jì)面積速度優(yōu)化的乘法器，針對(duì)傳統(tǒng)的Booth算法進(jìn)行了改進(jìn)，通過(guò)調(diào)整擴(kuò)展位的位置，設(shè)計(jì)出排列規(guī)則的部分積陣列結(jié)構(gòu)，并提出了新型的Wallace樹(shù)型結(jié)構(gòu)，既優(yōu)化了版圖面積又縮短了關(guān)鍵路徑延時(shí)。

1乘法器結(jié)構(gòu)

該乘法器用作兩個(gè)32位符號(hào)數(shù)的乘法運(yùn)算，主要包括三部分：部分積產(chǎn)生模塊、部分積壓縮模塊、最后兩組部分積的快速求和模塊。乘法器的結(jié)構(gòu)如圖1所示。

圖1　乘法器的整體結(jié)構(gòu)

為了得到有利于進(jìn)行樹(shù)型結(jié)構(gòu)壓縮的部分積陣列，本文對(duì)Booth編碼進(jìn)行改進(jìn)，兩個(gè)32位的二進(jìn)制數(shù)送入部分積產(chǎn)生模塊中，會(huì)產(chǎn)生一個(gè)由17個(gè)部分積組成的排列緊湊規(guī)則的陣列。對(duì)此部分積陣列進(jìn)行快速壓縮的是新型的Wallace樹(shù)結(jié)構(gòu)，該結(jié)構(gòu)根據(jù)部分積的數(shù)量，將優(yōu)化的4-2壓縮器[7]和3-2壓縮器重新排列，組成的壓縮結(jié)構(gòu)資源消耗少而且關(guān)鍵延時(shí)小。

2改進(jìn)的Booth編碼算法

本文設(shè)計(jì)的Booth編碼電路相較于傳統(tǒng)的方法會(huì)多產(chǎn)生一個(gè)部分積，雖然增加了部分積的個(gè)數(shù)，但卻簡(jiǎn)化了每個(gè)部分積的符號(hào)擴(kuò)展位。最終生成的部分積陣列主要由兩部分組成：一部分是32位的部分積PP；另外一部分是部分積的擴(kuò)展補(bǔ)充位：符號(hào)擴(kuò)展位S，求補(bǔ)時(shí)需要的加1位C。其排列方式使部分積陣列更加緊湊規(guī)則。

2.1部分積的生成

基4的Booth編碼算法對(duì)乘數(shù)重新編碼，并且產(chǎn)生四個(gè)相應(yīng)的控制信號(hào)，如表1所示。對(duì)于32位的乘數(shù)，在最低位補(bǔ)一個(gè)0后變?yōu)?3位數(shù)，按照每三位作為一組，每?jī)山M重疊一位的方式進(jìn)行分組，將乘數(shù)分成了16組。對(duì)每組按表1的方式重新編碼，表中X表示乘數(shù)，Y表示被乘數(shù)，NEG、Z、B1、B2表示控制信號(hào)[8]。

表1　基4的Booth編碼

表1中+1與+2分別表示被乘數(shù)的1倍和2倍，-1與-2分別表示減去1倍的被乘數(shù)和2倍的被乘數(shù)，即被乘數(shù)1倍求反加1和被乘數(shù)2倍求反加1。根據(jù)真值表得到各控制信號(hào)的表達(dá)式為：

(1)

根據(jù)以上控制信號(hào)可以通過(guò)譯碼電路得到部分積PPj，參照文獻(xiàn)[2]提出的部分積產(chǎn)生電路，可以得到其表達(dá)式為：

(2)

通過(guò)以上表達(dá)式可以得到16個(gè)32位部分積的高31位，部分積的最低位可由以下式子得到：

PP0=Y0·(X2i⊕X2i-1)

(3)

本文將32位的部分積分成兩個(gè)部分，一部分是高31位，另一部分是最低位第0位。相比于部分積都由同一個(gè)Booth編碼電路得到的方法，將部分積的最低位通過(guò)單獨(dú)、更簡(jiǎn)單的電路得到的方法更節(jié)省資源。

2.2改進(jìn)的部分積陣列

生成的部分積為了便于樹(shù)型結(jié)構(gòu)的壓縮，往往會(huì)排成陣列的形式，越是占用面積少的部分積陣列，越能節(jié)省資源的消耗，同時(shí)排列規(guī)則的部分積也有利于下一步的快速壓縮。而部分積的排列往往會(huì)受其他擴(kuò)充位的影響，例如符號(hào)位和求補(bǔ)時(shí)的取反加1位。

在Booth編碼中對(duì)被乘數(shù)的-2×Y和-1×Y的操作，是采取對(duì)被乘數(shù)的所有位數(shù)取反加1這種方法。其中的加1操作如果在被乘數(shù)取反之后立即執(zhí)行，就會(huì)增加部分積生成的延時(shí)，從而影響整個(gè)乘法的運(yùn)算速度。對(duì)于這個(gè)加1操作，文獻(xiàn)[6]采取的方法是把這個(gè)加1位保留至與本部分積最低位對(duì)齊的下一行部分積中去，相當(dāng)于給下一行的部分積同時(shí)增加了低兩位。這種方法可以減小部分積生成過(guò)程中的延遲，但是并未使部分積的排列最緊湊、最節(jié)省資源。

為了避免這一缺陷，本文將部分積求補(bǔ)時(shí)的加1位C置于緊挨下一行部分積的第0位處，形成該部分積新的最低位，按此方法排列的部分積如圖2所示。

圖2　部分積的排列方式

相比于文獻(xiàn)[6]，這樣做的好處是減少了每個(gè)部分積的位數(shù)，從而縮小了部分積陣列的面積。移位后的求反加1位C不再僅僅與乘數(shù)有關(guān)，還和被乘數(shù)Y的最低位有關(guān)，其取值由圖3的電路得到。

圖3　部分積求補(bǔ)加1位的生成電路

由于基于Booth編碼的乘法器處理的是有符號(hào)數(shù)的乘法運(yùn)算，因此部分積中的數(shù)據(jù)均為補(bǔ)碼形式。在部分積的加法運(yùn)算中，擴(kuò)展的符號(hào)位要消耗相當(dāng)大的硬件資源，以圖2中的第一行部分積為例，這個(gè)32位的部分積需要從[31∶0]擴(kuò)展到[63∶0]，[63∶32]全部為該部分積原來(lái)的最高位PP[31]。如果再把所有的這些符號(hào)擴(kuò)展位相加，將會(huì)消耗大量資源，所以有必要對(duì)部分積的符號(hào)擴(kuò)展位進(jìn)行處理。

假設(shè)所有部分積都為負(fù)，即部分積的符號(hào)擴(kuò)展位全為1，把這些擴(kuò)展位按照?qǐng)D2所示的對(duì)齊方式進(jìn)行相加，得到總和為一個(gè)32位的二進(jìn)制數(shù)：10101010101010101010101010101011。此32位數(shù)位于部分積陣列的最后一行，作為第17個(gè)部分積[9]。此時(shí)文獻(xiàn)[9]對(duì)每個(gè)部分積的符號(hào)擴(kuò)展位S的操作是將部分積最高位取反作為S的值，S的值取決于部分積的值，只有得到了部分積才能求得S，這樣會(huì)增加部分積陣列生成的延時(shí)。

本文提出一種新的方法來(lái)求得部分積的符號(hào)擴(kuò)展位S，其電路圖如圖4所示。

圖4　部分積符號(hào)擴(kuò)展位的生成電路

采用此方法的符號(hào)擴(kuò)展位S的值只依賴(lài)于被乘數(shù)的最高位和乘數(shù)，能與部分積同時(shí)求得，節(jié)省了部分積陣列生成的時(shí)間，能夠盡快進(jìn)入乘法運(yùn)算的下一個(gè)步驟——部分積的壓縮。

3改進(jìn)的Wallace樹(shù)壓縮結(jié)構(gòu)

Wallace樹(shù)型壓縮結(jié)構(gòu)的核心是壓縮器，常見(jiàn)的有3-2壓縮器，即進(jìn)位保留加法器CSA(Carry Save Adder)，和壓縮比為二比一的4-2壓縮器[10]。若僅采用CSA模塊作為壓縮結(jié)構(gòu)的基本單元，則會(huì)增加壓縮電路的路徑延時(shí)；若僅采用4-2壓縮器作為壓縮結(jié)構(gòu)的基本單元，則會(huì)增加資源的消耗。為了兼顧兩種壓縮器的優(yōu)點(diǎn)，本文采用CSA與4-2壓縮器相混合的樹(shù)型壓縮結(jié)構(gòu)。

3.1壓縮器的分析與優(yōu)化

CSA即帶進(jìn)位的一位全加器，其關(guān)鍵路徑上有2個(gè)XOR門(mén)的延時(shí)。通常4-2壓縮器由兩個(gè)3-2壓縮器實(shí)現(xiàn)[11]，其邏輯表達(dá)式為：

Sum=A⊕B⊕C⊕D⊕Cin

(4)

Carry=(A⊕B⊕C)D+(A⊕B⊕C)Cin+DCin

(5)

Cout=AB+AC+BC

(6)

由兩個(gè)3-2壓縮器組成的4-2壓縮器在關(guān)鍵路徑上需要4個(gè)XOR門(mén)的延時(shí)，而且輸入的信號(hào)不是同時(shí)參與運(yùn)算，累加過(guò)程容易產(chǎn)生問(wèn)題?；趯?duì)傳統(tǒng)的4-2壓縮器邏輯表達(dá)式的研究，可以對(duì)其電路進(jìn)行化簡(jiǎn)，得到以下簡(jiǎn)化的邏輯表達(dá)式：

(7)

(8)

優(yōu)化后的4-2壓縮器如圖5所示，通過(guò)此4-2壓縮器得到Sum的關(guān)鍵路徑延時(shí)為3個(gè)XOR門(mén)延時(shí)，比傳統(tǒng)4-2壓縮器少了1個(gè)XOR門(mén)的延時(shí)[12]。

圖5　優(yōu)化后的4-2壓縮器邏輯電路圖

3.2樹(shù)型結(jié)構(gòu)的分析比較

由于該乘法器中總共有17個(gè)部分積，如果完全采用3-2壓縮器對(duì)部分積進(jìn)行相加，則需要通過(guò)6級(jí)CSA才能將17個(gè)部分積壓縮成兩個(gè)部分積；如果完全采用4-2壓縮器對(duì)部分積進(jìn)行相加，則需要通過(guò)4級(jí)4-2壓縮器壓縮得到兩個(gè)部分積。最后將壓縮得到的兩個(gè)部分積通過(guò)超前進(jìn)位加法器進(jìn)行相加，就可以得到最終的結(jié)果。

文獻(xiàn)[3,5]采用的是基于CSA和4-2壓縮器相混合的Wallace樹(shù)結(jié)構(gòu)。第一級(jí)采用6個(gè)CSA壓縮得到8個(gè)部分積，第二級(jí)采用3個(gè)4-2壓縮器將8個(gè)部分積壓縮成6個(gè)，第三級(jí)采用2個(gè)CSA將6個(gè)部分積壓縮成4個(gè)，第四級(jí)采用1個(gè)4-2壓縮器壓縮4個(gè)部分積至最終的2個(gè)。此結(jié)構(gòu)將17個(gè)部分積壓縮成2個(gè)部分積經(jīng)過(guò)了2級(jí)CSA延時(shí)和2級(jí)4-2壓縮器的延時(shí)，相比于單獨(dú)使用3-2壓縮器或4-2壓縮器構(gòu)成的Wallace樹(shù)結(jié)構(gòu)，節(jié)約了兩級(jí)異或門(mén)的延遲。

為了進(jìn)一步節(jié)省資源的消耗，本文設(shè)計(jì)出新的Wallace樹(shù)結(jié)構(gòu)如圖6所示，P0～P16為經(jīng)過(guò)改進(jìn)的Booth編碼電路產(chǎn)生的17個(gè)部分積。

圖6　本文提出的Wallace樹(shù)壓縮結(jié)構(gòu)

此結(jié)構(gòu)與文獻(xiàn)[3,5]的樹(shù)結(jié)構(gòu)在壓縮部分積時(shí)具有相同的延遲。但是相比于后者，本文提出的Wallace樹(shù)結(jié)構(gòu)比后者多一個(gè)CSA模塊，少一個(gè)4-2壓縮器模塊。由于全加器的結(jié)構(gòu)比4-2壓縮器簡(jiǎn)單的多，需要的邏輯資源少于4-2壓縮器，所以總體上本文的樹(shù)結(jié)構(gòu)更節(jié)省資源。綜合比較這四種不同的Wallace樹(shù)結(jié)構(gòu)，其需要消耗的壓縮單元數(shù)量及關(guān)鍵延時(shí)如表2所示。

表2　四種樹(shù)型結(jié)構(gòu)的比較

雖然表2中四種樹(shù)結(jié)構(gòu)采用的是相同的CSA單元和4-2壓縮單元，但其關(guān)鍵延時(shí)和消耗資源情況各不相同。通過(guò)表2列出的數(shù)據(jù)可以清楚地看到，本文提出的Wallace樹(shù)結(jié)構(gòu)關(guān)鍵延時(shí)和消耗的壓縮單元都是最少的。

4實(shí)驗(yàn)結(jié)果及性能分析

本文設(shè)計(jì)的乘法器采用Verilog HDL語(yǔ)言進(jìn)行描述，并通過(guò)Modelsim軟件進(jìn)行功能仿真。通過(guò)編寫(xiě)測(cè)試激勵(lì)文件，使用隨機(jī)數(shù)函數(shù)產(chǎn)生32位符號(hào)數(shù)的測(cè)試數(shù)據(jù)，其取值范圍為-2 147 483 648～2 147 483 647。將測(cè)試數(shù)據(jù)a和b輸入到本文設(shè)計(jì)的乘法器和Altera的乘法器IP核中，對(duì)比兩組乘法運(yùn)算的結(jié)果，若不一致則輸出錯(cuò)誤信號(hào)error為1。對(duì)300萬(wàn)組測(cè)試數(shù)據(jù)的仿真結(jié)果顯示兩者得到的乘積完全一致，圖7為部分仿真的對(duì)比結(jié)果，每個(gè)時(shí)鐘上升沿產(chǎn)生前一組數(shù)據(jù)的乘積。

圖7　功能仿真圖

設(shè)計(jì)采用Altera公司的EP4CE30F23C7為目標(biāo)芯片，綜合結(jié)果顯示使用了2426個(gè)邏輯單元，相較于傳統(tǒng)乘法器減少了邏輯單元的消耗。采用基于SMIC的0.18 μm標(biāo)準(zhǔn)庫(kù)，使用Synopsys的Design Compiler進(jìn)行綜合，將綜合結(jié)果與其他的設(shè)計(jì)方法進(jìn)行比較，結(jié)果如表3所示。

表3　乘法器性能比較

從表3中可以看出，本文設(shè)計(jì)的乘法器相較于文獻(xiàn)[7,11]，速度分別提高了19%和5%，面積分別縮小了30%和16%，關(guān)鍵路徑延時(shí)和面積都得到了極大的優(yōu)化和提升。

5結(jié)語(yǔ)

本文通過(guò)對(duì)傳統(tǒng)Booth編碼和Wallace樹(shù)型結(jié)構(gòu)的深入研究，設(shè)計(jì)了一種32位有符號(hào)數(shù)的乘法器。對(duì)各級(jí)電路結(jié)構(gòu)進(jìn)行了優(yōu)化改進(jìn)，提出了改進(jìn)的Booth編碼算法，得到排列規(guī)則版圖整齊的部分積陣列，減少了部分積產(chǎn)生的延時(shí)，并且用一種新穎的Wallace樹(shù)壓縮結(jié)構(gòu)節(jié)省了資源的消耗。最后通過(guò)實(shí)驗(yàn)表明了本設(shè)計(jì)的優(yōu)越性，相比于其他文獻(xiàn)中的方法，總體上減少了乘法器的延時(shí)與面積，使乘法器的性能得到了優(yōu)化。

參考文獻(xiàn)

[1] 趙忠民.64位高性能嵌入式CPU中乘法器單元的設(shè)計(jì)與實(shí)現(xiàn)[D].同濟(jì)大學(xué),2007.

[2] Yeh Wenchang,Jen Cheinwei.High-speed Booth encoded parallel multiplier design[J].Computers,IEEE Transactions on,2000,49(7):692-701.

[3] 李康,林鈺凱,馬佩軍,等.基于部分積優(yōu)化的高速并行乘法器實(shí)現(xiàn)[J].微電子學(xué)與計(jì)算機(jī),2011,28(1):61-63,68.

[4] 何軍,朱英.一種64位Booth乘法器的設(shè)計(jì)與優(yōu)化[J].計(jì)算機(jī)工程,2012,38(16):253-254.

[5] 翟召岳,韓志剛.基于Booth算法的32位流水線(xiàn)型乘法器設(shè)計(jì)[J].微電子學(xué)與計(jì)算機(jī),2014,31(3):146-149.

[6] 陳海民,李崢,謝鐵頓.基于Radix-4Booth編碼的乘法器優(yōu)化設(shè)計(jì)[J]. 計(jì)算機(jī)工程,2012,38(1):233-235.

[7] 朱鑫標(biāo),施隆照.一種高壓縮Wallace樹(shù)的快速乘法器設(shè)計(jì)[J].微電子學(xué)與計(jì)算機(jī),2013,30(2):46-49.

[8] Muralidharan R,Chang Chiphong.Radix-4 and radix-8 Booth encoded multi-modulus multipliers[J].Circuits and Systems I: Regular Papers,IEEE Transactions on,2013,60(11):2940-2952.

[9] 曾憲愷,鄭丹丹,嚴(yán)曉浪,等.基于標(biāo)準(zhǔn)單元庫(kù)擴(kuò)展的快速乘法器設(shè)計(jì)[J].計(jì)算機(jī)應(yīng)用研究,2012,29(5):1778-1780,1814.

[10] 管幸福,余寧梅,路偉.一種wallace樹(shù)壓縮器硬件結(jié)構(gòu)的實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(23):76-78,83.

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

[12] 王仁平,何明華,魏榕山,等.32×32高性能乘法器的全定制設(shè)計(jì)[J].福州大學(xué)學(xué)報(bào):自然科學(xué)版,2012,40(5):602-608.

AN OPTIMISED DESIGN OF MULTIPLIER BASED ON IMPROVED BOOTH ENCODING AND WALLACE TREE

Shi MinWang GengYi Qingming

(SchoolofInformationScienceandTechnology,JinanUniversity,Guangzhou510632,Guangdong,China)

AbstractAccording to the problem that multiplier can’t take into account both the path delay and layout area, we proposed a novel structure of 32 bit signed multiplier. Its characteristics are: the multiplier uses the improved Booth encoding to generate a partial product array ranging regularly, and the circuit it brought forth reduces the delay and area compared with traditional method; it employs the improved novel Wallace tree compressing structure which is the combination of 4-2 compressor and 3-2 compressor, and to compress 17 partial products into 2 ones only needs 10 XOR-delays, thus speeds up multiplication computation considerably. The whole design was verified on FPGA, and synthesised with SMIC 0.18 μm-based standard unit process. Synthesis results showed that the chip area was 0.1127 mm2, and the key path delay was 3.4 ns. Experimental results also showed that the improved multiplier reduced both the key path delay and the layout area.

KeywordsMultiplierBooth encodingPartial product arrayWallace tree

收稿日期：2014-11-28。廣東省工程技術(shù)研究中心項(xiàng)目(2012gczx A003)。石敏，副教授，主研領(lǐng)域：圖像處理，SoC設(shè)計(jì)。王耿，碩士生。易清明，教授。

中圖分類(lèi)號(hào)TP332

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.05.004