引言

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

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

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

　　對部分積相加，可以采用不同的加法器陣列結(jié)構(gòu)。而不同的陣列結(jié)構(gòu)將直接影響完成一次乘法所需要的時間，因此，加法器陣列結(jié)構(gòu)是決定乘法器性能的重要因素。重復陣列（iterative array，簡稱ia）和wallace樹型結(jié)構(gòu)是最為典型的兩種加法器陣列結(jié)構(gòu)。ia結(jié)構(gòu)規(guī)整，易于版圖實現(xiàn)，但速度最慢且面積大；理論上，wallace樹型結(jié)構(gòu)是進行乘法操作最快的加法器陣列結(jié)構(gòu)，但傳統(tǒng)的wallace樹型結(jié)構(gòu)電路互連復雜，版圖實現(xiàn)困難。為了解決這個問題，人們推出了一些連接關系較為簡單的樹型結(jié)構(gòu)，例如zm樹和os樹。它們都是將ia樹分為幾段，每段稱之為子樹，子樹內(nèi)部連接采用ia結(jié)構(gòu)，而子樹間采用樹型連接，以此來降低連接復雜度，但是這種方法降低了部分積相加的速度。
在對樹型結(jié)構(gòu)進行改進的同時，設計者們也嘗試了對加法陣列中基本加法單元的改進。wallace最早提出的方案中，是以csa（進位保留加法器）作為基本單元構(gòu)建加法陣列的。其基本方法是：通過csa部件，以3∶2的壓縮比對部分積進行逐級壓縮，直到最后只產(chǎn)生兩個輸出為止，再通過進位傳遞加法器對產(chǎn)生的這兩個偽和與局部進位相加得出真正的結(jié)果。此后，dadda提出了一種新的加法單元，稱為“（j，k）計數(shù)器”，它有j個輸入和k個輸出，其中j≦2k。經(jīng)過研究和實踐，人們發(fā)現(xiàn)4-2壓縮器（實際上是5-3計數(shù)器）具有較好的平衡性和對稱性，用其作為基本加法單元構(gòu)成的乘法器在總體性能上具有一定的優(yōu)勢，因此4-2壓縮器也就成為了目前乘法器中較多采用的加法單元。

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

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

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

　　但這種未經(jīng)過優(yōu)化的電路結(jié)構(gòu)很可能造成關鍵路徑不必要的延長。上文已提到，4-2壓縮器實際上是由5個權(quán)1的輸入，產(chǎn)生2個權(quán)2的輸出（cout，c）和1個權(quán)1的輸出（s）。而本文之所以稱其為4-2壓縮器而非5-3計數(shù)器，是基于這樣一個事實：將此單元作橫向排列后，加數(shù)數(shù)目可以實現(xiàn)的壓縮比為4:2。

　　此外，通過平衡路徑，該結(jié)構(gòu)使橫向進位鏈不對關鍵路徑的延遲造成影響，也就是說產(chǎn)生c和s信號所需的時間不決定于cin信號，電路關鍵路徑為3個異或門的延遲。在90nm工藝條件下，采用mentor公司的eldod仿真工具得到的實際電路延遲仿真數(shù)據(jù)如表1