一種改進(jìn)的Wallace樹型乘法器的設(shè)計(jì)

摘要：對(duì)Booth算法產(chǎn)生的部分積重新合理分組，采用CSA和4-2壓縮器的混合電路結(jié)構(gòu)，對(duì)傳統(tǒng)的Wallace樹型乘法器進(jìn)行改進(jìn)，提出一種高速的樹型乘法器。該結(jié)構(gòu)與傳統(tǒng)Wallace樹型乘法器相比，具有更小的延時(shí)，更規(guī)整的布局和更規(guī)則的布線，使其易于VLSI實(shí)現(xiàn)。
關(guān)鍵詞：Booth算法；Wallace樹；CSA；4-2壓縮器；樹型乘法器

引言
    在微處理器芯片中，乘法器是進(jìn)行數(shù)字信號(hào)處理的核心，同時(shí)也是微處理器中進(jìn)行數(shù)據(jù)處理的關(guān)鍵部件。乘法器完成一次操作的周期基本上決定了微處理器的主頻。乘法器的速度和面積優(yōu)化對(duì)于整個(gè)CPU的性能來說是非常重要的。為了加快乘法器的執(zhí)行速度，減少乘法器的面積，有必要對(duì)乘法器的算法、結(jié)構(gòu)及電路的具體實(shí)現(xiàn)做深入的研究。

基４Booth算法與乘法器的一般結(jié)構(gòu)

    乘法器工作的基本原理是首先生成部分積，再將這些部分積相加得到乘積。在目前的乘法器設(shè)計(jì)中，基４Booth算法是部分積生成過程中普遍采用的算法。對(duì)于N位有符號(hào)數(shù)乘法A×B來說，常規(guī)的乘法運(yùn)算會(huì)產(chǎn)生N個(gè)部分積。如果對(duì)乘數(shù)B進(jìn)行基４Booth編碼，每次需考慮3位：相鄰高位、本位和相鄰低位，編碼后產(chǎn)生部分積的個(gè)數(shù)可以減少到[(N+1)/2]   （[X]取值為不大于X的整數(shù)），確定運(yùn)算量0、±1A、±2A。對(duì)于2A的實(shí)現(xiàn)，只需要將A左移一位。因此，對(duì)于符號(hào)數(shù)乘法而言，基4 Booth算法既方便又快捷。而對(duì)于無符號(hào)數(shù)來說，只需對(duì)其高位作0擴(kuò)展，而其他處理方法相同。雖然擴(kuò)展后可能導(dǎo)致部分積的個(gè)數(shù)比有符號(hào)數(shù)乘法多1，但是這種算法很好地保證了硬件上的一致性，有利于實(shí)現(xiàn)。對(duì)于32位乘法來說，結(jié)合指令集的設(shè)計(jì)，通常情況下需要相加的部分積不超過18個(gè)。

    對(duì)部分積相加，可以采用不同的加法器陣列結(jié)構(gòu)。而不同的陣列結(jié)構(gòu)將直接影響完成一次乘法所需要的時(shí)間，因此，加法器陣列結(jié)構(gòu)是決定乘法器性能的重要因素。重復(fù)陣列（Iterative Array，簡稱IA）和Wallace樹型結(jié)構(gòu)是最為典型的兩種加法器陣列結(jié)構(gòu)。IA結(jié)構(gòu)規(guī)整，易于版圖實(shí)現(xiàn)，但速度最慢且面積大；理論上，Wallace樹型結(jié)構(gòu)是進(jìn)行乘法操作最快的加法器陣列結(jié)構(gòu)，但傳統(tǒng)的Wallace樹型結(jié)構(gòu)電路互連復(fù)雜，版圖實(shí)現(xiàn)困難。為了解決這個(gè)問題，人們推出了一些連接關(guān)系較為簡單的樹型結(jié)構(gòu)，例如ZM樹和OS樹。它們都是將IA樹分為幾段，每段稱之為子樹，子樹內(nèi)部連接采用IA結(jié)構(gòu)，而子樹間采用樹型連接，以此來降低連接復(fù)雜度，但是這種方法降低了部分積相加的速度。

    在對(duì)樹型結(jié)構(gòu)進(jìn)行改進(jìn)的同時(shí)，設(shè)計(jì)者們也嘗試了對(duì)加法陣列中基本加法單元的改進(jìn)。Wallace最早提出的方案中，是以CSA（進(jìn)位保留加法器）作為基本單元構(gòu)建加法陣列的。其基本方法是：通過CSA部件，以3∶2的壓縮比對(duì)部分積進(jìn)行逐級(jí)壓縮，直到最后只產(chǎn)生兩個(gè)輸出為止，再通過進(jìn)位傳遞加法器對(duì)產(chǎn)生的這兩個(gè)偽和與局部進(jìn)位相加得出真正的結(jié)果。此后，Dadda提出了一種新的加法單元，稱為“（j，k）計(jì)數(shù)器”，它有j個(gè)輸入和k個(gè)輸出，其中j≦2k。經(jīng)過研究和實(shí)踐，人們發(fā)現(xiàn)4-2壓縮器（實(shí)際上是5-3計(jì)數(shù)器）具有較好的平衡性和對(duì)稱性，用其作為基本加法單元構(gòu)成的乘法器在總體性能上具有一定的優(yōu)勢，因此4-2壓縮器也就成為了目前乘法器中較多采用的加法單元。

    圖1中列舉了乘法器中幾種加法器陣列的結(jié)構(gòu)，它們都采用4-2壓縮器作為基本加法單元來完成對(duì)18個(gè)部分積的加和。圖中每個(gè)矩形代表一組4-2壓縮器，帶箭頭的線段表示部分積與中間結(jié)果。
   
（a）IA陣列        （b）Wallace樹
   
（c）一階OS樹      （d）參考文獻(xiàn)[5]中的樹型結(jié)構(gòu)

圖1 對(duì)18個(gè)部分積相加所采用的加法陣列結(jié)構(gòu)

    如前所述，圖1（a）中的IA陣列，結(jié)構(gòu)最為規(guī)整，但很明顯，其延時(shí)級(jí)數(shù)大大多于其他結(jié)構(gòu)。（b）是Wallace樹結(jié)構(gòu)，由于采用4-2壓縮器作為唯一的加法單元，而18不能被4整除，因此在對(duì)18個(gè)部分積的求和過程中，必然要對(duì)其中的兩個(gè)部分積做額外處理。Wallace樹采取的方法是：先將16個(gè)部分積通過三級(jí)4-2壓縮器后產(chǎn)生兩個(gè)結(jié)果，然后與剩下的兩個(gè)部分積一起再進(jìn)行一級(jí)4-2壓縮。（c）中的一階OS樹結(jié)構(gòu)也采用了類似的方法，只是在處理的先后順序上有所改變。這兩種結(jié)構(gòu)，都破壞了樹的對(duì)稱性，造成路徑的不等長，因此浪費(fèi)了硬件資源，且增加了布局布線的復(fù)雜度。（d）是參考文獻(xiàn)[5]中提出的一種經(jīng)過改進(jìn)的樹型結(jié)構(gòu)，其求和過程是：將18個(gè)部分積分為3組，先對(duì)每組中的6個(gè)部分積求和，各產(chǎn)生兩個(gè)中間結(jié)果，再把這6個(gè)中間結(jié)果相加。由于對(duì)每組中的6個(gè)部分積求和，可以采用相同結(jié)構(gòu)的兩組4-2壓縮器，這樣就很好地降低了布局布線的復(fù)雜度。其缺點(diǎn)在于：用4-2壓縮器對(duì)6個(gè)中間結(jié)果進(jìn)行相加的過程中，仍不能避免路徑不平衡的問題，因此，還是使關(guān)鍵路徑的延時(shí)有不必要的增加。

CSA和4-2壓縮器的電路結(jié)構(gòu)和時(shí)延分析

    既然CSA和4-2壓縮器是加法陣列中主要采用的基本單元，那么，就有必要對(duì)CSA和4-2壓縮器在電路特性方面做一下分析比較。如圖2所示，CSA的電路邏輯實(shí)際上就是一位全加器，其關(guān)鍵路徑上需要經(jīng)過兩級(jí)異或門邏輯的延時(shí)。對(duì)于4-2壓縮器，可以把它看作是兩個(gè)CSA按照?qǐng)D3形式相連而構(gòu)成。

     
圖2 CSA電路結(jié)構(gòu)   

 

 圖3 由兩個(gè)CSA連接而成的4-2壓縮器電路結(jié)構(gòu)

    通過圖3所示的連接方式能夠很容易地實(shí)現(xiàn)4-2壓縮器。但這種未經(jīng)過優(yōu)化的電路結(jié)構(gòu)很可能造成關(guān)鍵路徑不必要的延長。上文已提到，4-2壓縮器實(shí)際上是由5個(gè)權(quán)1的輸入，產(chǎn)生2個(gè)權(quán)2的輸出（Cout，C）和1個(gè)權(quán)1的輸出（S）。而本文之所以稱其為4-2壓縮器而非5-3計(jì)數(shù)器，是基于這樣一個(gè)事實(shí)：將此單元作橫向排列后，加數(shù)數(shù)目可以實(shí)現(xiàn)的壓縮比為4:2。基于真值表，可以設(shè)計(jì)出較為理想的4-2電路結(jié)構(gòu)，如圖4所示，其中采用了基于2選1多路選擇器的異或門電路結(jié)構(gòu)代替?zhèn)鹘y(tǒng)的異或門。

圖4 基于多路選擇器的4-2壓縮器電路結(jié)構(gòu)

    此外，通過平衡路徑，該結(jié)構(gòu)使橫向進(jìn)位鏈不對(duì)關(guān)鍵路徑的延遲造成影響，也就是說產(chǎn)生C和S信號(hào)所需的時(shí)間不決定于Cin信號(hào)，電路關(guān)鍵路徑為3個(gè)異或門的延遲。在90nm工藝條件下，采用Mentor公司的eldoD仿真工具得到的實(shí)際電路延遲仿真數(shù)據(jù)如表1所示。由此可見，一級(jí)4-2壓縮器的最大延時(shí)約為一級(jí)CSA最大延遲的1.5倍，但完成了兩級(jí)CSA所做的相加工作。

表1 4-2壓縮器和CSA時(shí)延仿真數(shù)據(jù)

     信號(hào)
延時(shí) P1 P2 P3 P4       信號(hào)
延時(shí) A B C
S  （ps） 187.76 201.30 194.99 192.77  Sum（ps） 134.46 138.11 94.492
C  （ps） 185.79 183.98 187.5 195.14  Carry（ps） 118.97 111.98 100.73
（a）4-2壓縮器時(shí)延仿真數(shù)據(jù)      （b）CSA時(shí)延仿真數(shù)據(jù)

改進(jìn)的Wallace樹型乘法器結(jié)構(gòu)及性能比較

    對(duì)于32位乘法來說，符號(hào)數(shù)相乘時(shí)，基4 Booth編碼形成16個(gè)編碼項(xiàng)，并由此產(chǎn)生16個(gè)部分積；無符號(hào)數(shù)相乘時(shí)，編碼項(xiàng)與部分積各多出一個(gè)。此外，在目前CPU指令集的設(shè)計(jì)中，乘加/減（C±A×B）指令已被廣泛采用。所以，在一次乘法運(yùn)算中，加法陣列中需要相加的部分積最多達(dá)到18個(gè)。而部分積個(gè)數(shù)對(duì)陣列結(jié)構(gòu)的設(shè)計(jì)有著重大的影響，進(jìn)而也就影響了布局布線的復(fù)雜度以及陣列的延遲級(jí)數(shù)。這一點(diǎn)在上文對(duì)圖1中各個(gè)陣列結(jié)構(gòu)的分析中，可以得到很好的證明。

    為了解決圖1中各結(jié)構(gòu)在對(duì)部分積求和過程中存在的樹型結(jié)構(gòu)對(duì)稱性不好、規(guī)整性差、布局布線復(fù)雜度高，以及關(guān)鍵路徑延時(shí)不必要增加等問題，本文基于傳統(tǒng)的Wallace樹型結(jié)構(gòu)，對(duì)其做出了改進(jìn)，提出如圖5所示的樹型陣列結(jié)構(gòu)。
 

圖5  CSA與4-2壓縮器相結(jié)合的樹型陣列結(jié)構(gòu)

    此結(jié)構(gòu)中，采用CSA和4-2壓縮器共同作為基本加法單元，對(duì)18個(gè)部分積進(jìn)行壓縮。其具體過程為：先采用CSA對(duì)18個(gè)部分積做第一次壓縮，產(chǎn)生12個(gè)中間結(jié)果，再采用4-2壓縮器進(jìn)行第二次壓縮，然后再分別采用CSA和4-2壓縮器對(duì)第二次壓縮產(chǎn)生的6個(gè)中間結(jié)果和隨后產(chǎn)生的4個(gè)中間結(jié)果做壓縮，得到最終的兩個(gè)偽和，送入進(jìn)位傳播加法器得到最終結(jié)果。該結(jié)構(gòu)通過在第一次和第三次壓縮中采用CSA，使得最初的18個(gè)部分積和用4-2壓縮器進(jìn)行第二次壓縮產(chǎn)生的6個(gè)中間結(jié)果能夠同時(shí)得到處理，使各條路徑在時(shí)延上達(dá)到平衡，相比于只采用4-2壓縮器作為基本加法單元的陣列，這就節(jié)省了不必要的等待時(shí)間。與此同時(shí)，用兩級(jí)CSA取代兩級(jí)4-2壓縮器，也使得關(guān)鍵路徑的延時(shí)有了明顯的縮短，對(duì)高速集成電路設(shè)計(jì)有著很高的實(shí)用價(jià)值。

    此外，由圖5可以看出，此結(jié)構(gòu)具有較好的對(duì)稱性和規(guī)整性，宏模塊數(shù)量少，有利于布局布線。同時(shí)，對(duì)于目前指令集設(shè)計(jì)中常用的乘法指令，該結(jié)構(gòu)對(duì)硬件的利用率也是相當(dāng)高的。概括地說，該結(jié)構(gòu)保持了傳統(tǒng)Wallace樹型結(jié)構(gòu)求和速度快的優(yōu)點(diǎn)，又較好地改進(jìn)了原來那種由單一加法單元構(gòu)成的陣列的不足。
 
    為了比較該結(jié)構(gòu)與圖1所示各結(jié)構(gòu)陣列的面積，本文在90nm工藝下采用全定制設(shè)計(jì)方法，利用Cadence的版圖工具Virtuoso對(duì)各種情況進(jìn)行了比較。另外，采用經(jīng)過4-2壓縮器級(jí)數(shù)度量關(guān)鍵路徑的時(shí)延，不考慮互連延時(shí)，再通過AT2標(biāo)準(zhǔn)做了進(jìn)一步的比較，結(jié)果如表2所示。(其中由表1數(shù)據(jù)可得，1級(jí)CSA延時(shí)≈0.7級(jí)4-2壓縮器延時(shí)。

表2 各種結(jié)構(gòu)的比較

陣列結(jié)構(gòu) 面積A（μm2） 延時(shí)T（4-2級(jí)數(shù)） AT2 用Wallace樹歸一化
IA陣列 0.0362 8 2.3168 3.3
Wallace樹 0.0437 4 0.6992 1
一階OS樹 0.0402 4 0.6432 0.92
參考文獻(xiàn)[5]結(jié)構(gòu) 0.0414 4 0.6624 0.95
本文提出結(jié)構(gòu) 0.0418 3.4 0.4832 0.69

結(jié)語
    采用CSA與4-2壓縮器相結(jié)合的電路，在對(duì)部分積的求和過程中對(duì)硬件達(dá)到了最為高效的利用。同時(shí)，這種結(jié)構(gòu)既發(fā)揮了CSA版圖面積小的優(yōu)點(diǎn)，又體現(xiàn)了4-2壓縮器壓縮比高、速度快的長處，因此，與其他結(jié)構(gòu)相比，本文提出的改進(jìn)結(jié)構(gòu)在面積和速度上都達(dá)到了相對(duì)理想的效果。雖然其在布局布線上有一定的復(fù)雜度，但與傳統(tǒng)的Wallace樹相比，已取得了頗為可觀的改進(jìn)。目前，該結(jié)構(gòu)乘法器的版圖設(shè)計(jì)工作已基本完成，并被用于正在進(jìn)行的64位高性能嵌入式CPU設(shè)計(jì)的項(xiàng)目中，預(yù)計(jì)于2007年3月進(jìn)行流片。

參考文獻(xiàn)
1 Bwick G. Fast multiplication：algorithms and implementation[D]. Stanford University, 1994
2 Poornaiah, D. Algorithm for designing efficient VLSI concurrent add-multiply and add-multiply-add cells for DSP applications[J]. Electronic Letters, 2000, 36(5)：399-400
3 Jessani R M, Putrino M. Comparison of Single- and Dual-Pass Multiply-Add Fused Floating - Point Units[J]. IEEE Trans Comput, 1998, 47（9）：927-937
4 Sousa L, Chaves R.. A universal architecture for designing ef