32位乘法器性能比較

     對基於陣列乘法器、修正布斯演算法(MBA)乘法器、華萊士(WT)乘法器和MBA-WT混合乘法器的四種架構的32位乘法器性能進行了比較，在選擇乘法器時,應根據實際應用,從面積、速度、功耗等角度權衡考慮。

    乘法是數字信號處理中重要的基本運算。在圖像、語音、加密等數字信號處理領域,乘法器扮演著重要的角色,並在很大程度上左右著系統性能。隨著實時信號處理的提出和集成電路工藝水平的進步,人們開始致力於高速乘法器設計。
   
     最初,陣列乘法採用移位與求和演算法,部分乘積項(Partial Product, PP)數目決定了求和運算的次數,直接影響乘法器的速度。修正布斯演算法(Modified Booth Algorithm, MBA)對乘數重新編碼,以壓縮PP。華萊士樹(Wallace Tree, WT)結構改變求和方式,將求和級數從O(N)降為O(logN),提高了運算速度,但是WT存在結構不規整,布線困難的缺點。用4:2壓縮器(4: 2 compressor)代替全加器(FA)可以解決這一問題。將MBA演算法和WT結構的優點相結合,形成了MBA-WT乘法器。
   
    以下1～4節將分別介紹陣列乘法器、MBA乘法器、WT乘法器、MBA?WT乘法器。最後對四種乘法器的性能進行比較,並總結全文。 
      
1 陣列乘法器    
     陣列乘法器基於移位與求和演算法。被乘數與乘數中的某一位相乘,產生一組PP,將該組PP移位,使LSB與乘數對應位對齊;求出全部PP,並相應移位;對所有PP求和,得到乘積。因此,加法陣列結構非常重要。CRA (Carry Ripple Adder)存在進位問題,運算速度慢。CSA  (Carry Save Adder)將本級進位傳至下級,求和速度快,且速度與字長無關。陣列乘法器中,CSA把PP陣列縮減至Sum和Carry兩項,再用高速加法器求和得積。陣列乘法器結構規範,利於布局布線。
   
    因為乘數和被乘數可正、可負,所以一般用二進位補碼錶示,以簡化加、減運算。補碼運算需要符號擴展,符號擴展寬度與加法器結構有關。對於CRA,加數和被加數符號擴展至本級和的最高位;對於CSA,擴展至兩數最高位對齊。符號擴展增加了符號位扇出,使電容負載不平衡,影響電路整體速度;需要冗餘的加法器,擴大了版圖面積。符號擴展問題可用以下演算法解決［1］。假設P1=A、P2=B,求A+B: ① 將A符號位擴展一位,對擴展位取反;② 將B符號位取反;③ 在B符號位左邊添1;④ 求和。
   
    假設兩個6位部分積A、B相加,需擴展一位符號位,如圖1(a)所示;採用新演算法后,計算式如圖1(b)所示;相應6×6乘法器電路如圖1(c)所示。
 

2 MBA乘法器    
    求和是乘法運算中最耗時步驟。縮減PP數目是提高乘法運算速度的方法之一。陣列乘法中PP數目與乘數位數相等。MBA演算法通過對乘數重新編碼,壓縮PP數目,以提高運算速度。壓縮率取決於編碼方法,如果採用三位編碼,可壓縮一半PP。考慮到編碼電路的引入,乘法器速度的提高是有限的。基於MBA的乘法器架構如圖2所示。
 
    MBA演算法描述如下:假設A為被乘數、B為乘數,均採用二進位補碼錶示:
 
    按式(3),對乘數B重新編碼,編碼后B可用式(4)表示。
 
    (n為偶數;若n為奇數,則B符號擴展一位)
     
    如式(5)所示,A×B運算所需加?法次數減少了一半。注意,求和時,Ki+1A相對於KiA需左移兩位。

3 WT乘法器    
    樹型結構可以減少求和級數,是提高乘法運算速度的另一方法。1961年,Wallace提出的WT結構是其中最著名的一種。它對於16位以上的乘法運算尤其適用。
   
    WT 結構,將全部PP按列分組,每列對應一組加法器,各列同時相加,前列進位傳至后列,生成新PP陣列;同法,化簡新陣列,直至只剩兩行PP;最後用高速加法器求和得積。WT結構優點在於只需做O(logN)次加法,因而運算速度快。6×6 WT乘法器如圖3所示。在WT結構基礎上,通過對PP劃分的優化,可以進一步減少求和級數［2］。
 
    注意到FA不同輸入端到同一輸出端的路徑延時不同,不同埠在時序上應區別對待。例如,兩個FA的兩種級聯方式:最長路徑+最長路徑、最長路徑+最短路徑。後者關鍵路徑小於前者,有利於提高速度。在利用FA構建WT時,可以採用一種演算法［3］使WT的最長路徑最短。缺乏規整性,布線困難,是 WT結構最大的不足。引線的延長導致寄生電容增加,妨礙了電路速度的進一步提高。針對這一問題,Weinberger提出了基於4∶2縮減器的乘法器架構,其最大優點在於電路簡單,連線規則。4∶2縮減器可由FA構成,見圖4(a);也可進行邏輯優化,見圖4(b)。
 
   
4 MBA-WT混合乘法器    
    高速乘法器可同時採用MBA演算法和WT結構,如圖5所示。首先,MBA演算法把乘法運算N×M的PP壓縮1／2;然後,WT結構將PP按列分組,并行約減,直至PP陣列只剩餘兩行;最後由高速加法器求和得積。 
 
    因為WT結構中所有PP同時相加,所以符號位要擴展至M+N位。這將花費大量硬體資源,並且嚴重影響運算速度。符號擴展問題可由以下方法解決［4］。假設部分積均為負數,可以預求所有擴展符號位之和
 
    如果某一部分積為正數,再進行修正:將部分積的符號位s由0變成1就可以抵消預測的影響。此方法較好的解決了符號擴展問題,提高了運算速度,並且硬體開銷很小。 
    
5 性能比較及總結    
    A. J. Al-Kbalili和N. Zaman利用FPGA,分別綜合了基於以上四種架構的32×32乘法器,並比較了乘法器在面積、延時和功耗方面的性能參數,如表1所示［5］。
 
    陣列乘法器面積小、功耗小,運算速度慢;WT乘法器和MBA-WT乘法器運算速度快,但功耗較大,WT乘法器面積最大,MBA-WT乘法器面積略大於陣列乘法器;MBA乘法器各項參數介於前三種乘法器之間。不同乘法器架構在性能上都存在優點和缺點。選擇乘法器時,必須根據應用場合的要求,在面積、延時和功耗等方面綜合考慮。
    
參考文獻
    [1] Salomon O, Green J M, and Klar H, General Algorithms for a Simplified Addition of 2’s Complement Numbers. IEEE JSSC, July 1995;30(7):839-844   
    [2] Robinson M E, Swartzlander E. A Reduction Scheme to Optimize the Wallace Multiplier In:Proc ICCD'98, 1998;122-127   
    [3] Oklobdzija V G. A Method for Speed Optimized Partial Product Reduction and Generation of Fast Parallel Multipliers Using an Algorithmic Approach. IEEE Trans Comp, Match 1996;45(3):294-305   
    [4] Ardekani J F. M×N Booth Encoded Multiplier Generator Using OptimizedWallace Trees . IEEE Trans VLSI systems, Jun 1993;1(2):120-125   
    [5] Al?Khalili A J. 32?bit Constant(k) Coefficient Multiplier In:Proc EE Tech, 2001