基于改進的Booth編碼和Wallace樹的乘法器優(yōu)化設計

石　敏　王　耿　易清明

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

?

基于改進的Booth編碼和Wallace樹的乘法器優(yōu)化設計

石敏王耿易清明

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

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

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

0引言

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

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

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

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

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

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

2改進的Booth編碼算法

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

2.1部分積的生成

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

表1　基4的Booth編碼

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

(1)

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

(2)

通過以上表達式可以得到16個32位部分積的高31位，部分積的最低位可由以下式子得到：

PP0=Y0·(X2i⊕X2i-1)

(3)

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

2.2改進的部分積陣列

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

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

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

圖2　部分積的排列方式

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

圖3　部分積求補加1位的生成電路

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

假設所有部分積都為負，即部分積的符號擴展位全為1，把這些擴展位按照圖2所示的對齊方式進行相加，得到總和為一個32位的二進制數(shù)：10101010101010101010101010101011。此32位數(shù)位于部分積陣列的最后一行，作為第17個部分積[9]。此時文獻[9]對每個部分積的符號擴展位S的操作是將部分積最高位取反作為S的值，S的值取決于部分積的值，只有得到了部分積才能求得S，這樣會增加部分積陣列生成的延時。

本文提出一種新的方法來求得部分積的符號擴展位S，其電路圖如圖4所示。

圖4　部分積符號擴展位的生成電路

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

3改進的Wallace樹壓縮結(jié)構(gòu)

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

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

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

Sum=A⊕B⊕C⊕D⊕Cin

(4)

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

(5)

Cout=AB+AC+BC

(6)

由兩個3-2壓縮器組成的4-2壓縮器在關(guān)鍵路徑上需要4個XOR門的延時，而且輸入的信號不是同時參與運算，累加過程容易產(chǎn)生問題?；趯鹘y(tǒng)的4-2壓縮器邏輯表達式的研究，可以對其電路進行化簡，得到以下簡化的邏輯表達式：

(7)

(8)

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

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

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

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

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

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

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

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

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

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

4實驗結(jié)果及性能分析

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

圖7　功能仿真圖

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

表3　乘法器性能比較

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

5結(jié)語

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

參考文獻

[1] 趙忠民.64位高性能嵌入式CPU中乘法器單元的設計與實現(xiàn)[D].同濟大學,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)化的高速并行乘法器實現(xiàn)[J].微電子學與計算機,2011,28(1):61-63,68.

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

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

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

[7] 朱鑫標,施隆照.一種高壓縮Wallace樹的快速乘法器設計[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] 曾憲愷,鄭丹丹,嚴曉浪,等.基于標準單元庫擴展的快速乘法器設計[J].計算機應用研究,2012,29(5):1778-1780,1814.

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

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

[12] 王仁平,何明華,魏榕山,等.32×32高性能乘法器的全定制設計[J].福州大學學報:自然科學版,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ù)研究中心項目(2012gczx A003)。石敏，副教授，主研領域：圖像處理，SoC設計。王耿，碩士生。易清明，教授。

中圖分類號TP332

文獻標識碼A

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