帶有飽和處理功能的并行乘加單元設(shè)計(jì)

本文介紹了一種48bit+24bit×24bit帶飽和處理的MAC單元設(shè)計(jì)。在乘法器的設(shè)計(jì)中，采用改進(jìn)的booth 算法來減少部分積的數(shù)目，用由壓縮單元組成的Wallace tree將產(chǎn)生的部分積相加，并將被加數(shù)作為乘法器的一個(gè)部分積參與到Wallace tree陣列中來完成乘加運(yùn)算，同時(shí)增加了飽和檢測和飽和值運(yùn)算邏輯來實(shí)現(xiàn)飽和處理。
關(guān)鍵詞：booth算法； Wallace tree ；飽和處理；飽和檢測

圖1? 飽和MAC結(jié)構(gòu)框圖

圖2? 優(yōu)化后的飽和MAC結(jié)構(gòu)框圖

引言
在一些數(shù)字信號處理應(yīng)用，如數(shù)字濾波、語音編碼、圖形處理等領(lǐng)域中，要大量反復(fù)地進(jìn)行飽和處理操作。所謂飽和處理操作，是指當(dāng)兩個(gè)n位操作數(shù)相運(yùn)算時(shí)，如果結(jié)果發(fā)生溢出，則取其飽和值。對于用補(bǔ)碼表示的n位二進(jìn)制數(shù)，正的飽和值為011…11，負(fù)的飽和值為100…00。飽和處理操作一般要用到兩個(gè)周期，在第一個(gè)周期中處理算術(shù)運(yùn)算操作，在第二個(gè)周期中處理飽和操作。更加復(fù)雜的操作，例如MAC操作，一般是在分別完成乘法和加法運(yùn)算之后再進(jìn)行飽和處理，這通常需要更多的周期。而并行飽和運(yùn)算操作則是在一個(gè)周期之內(nèi)取得串行操作的結(jié)果，這需要更多的硬件電路來實(shí)現(xiàn)。
本文設(shè)計(jì)了一種MAC單元，實(shí)現(xiàn)

=>的運(yùn)算操作，并帶有飽和處理功能。

圖3? 24×24高速乘加器的結(jié)構(gòu)框圖

圖4 并行乘加器中最大的Wallace tree 結(jié)構(gòu)

圖5 最終加法器的實(shí)現(xiàn)

飽和乘加單元基本結(jié)構(gòu)
為了實(shí)現(xiàn)

=>的飽和運(yùn)算，在一般情況下，計(jì)算P時(shí)，可以將X 、Y經(jīng)乘法器相乘，然后將積與A相加，如果發(fā)生溢出，則將所得的和修正為飽和值。這實(shí)際上就是將乘法器與加法器簡單串聯(lián)，然后進(jìn)行飽和值修正，如圖1所示。但是以這種結(jié)構(gòu)實(shí)現(xiàn)的MAC單元，由于乘法器中的最終加法器和加法器只是簡單的串聯(lián)在一起，在關(guān)鍵路徑上就有兩級串聯(lián)的加法器，面積、延時(shí)都比較大。
為了提高M(jìn)AC單元的性能，本文對上面提到的結(jié)構(gòu)進(jìn)行了優(yōu)化， 優(yōu)化后的結(jié)構(gòu)如圖2所示。 將MAC單元的被加數(shù)作為乘法器的一個(gè)部分積，參與到部分積加法陣列中，這樣就可以省去完成乘法計(jì)算后再進(jìn)行加法計(jì)算的操作，縮短關(guān)鍵路徑上的延時(shí)。

高速并行乘加單元結(jié)構(gòu)
本文選用修正booth算法和Wallace tree結(jié)構(gòu)實(shí)現(xiàn)24×24高速并行乘法器。圖3是24×24高速乘加器的結(jié)構(gòu)框圖，主要由booth編碼、部分積陣列、Wallace tree以及最終加法器構(gòu)成。
booth編碼
被乘數(shù)、乘數(shù)分別為n位補(bǔ)碼表示的有符號數(shù)，在MBA(修正booth算法)中：
部分積的數(shù)目＝，不失一般性，在這里只討論n為偶數(shù)的情況。
設(shè)： X=-an-12n-1+2i；
?????? Y=-bn-12n-1+2i；
根據(jù)MBA，對乘數(shù)進(jìn)行以下變換：
Y=-bn-12n-1+2i
?? =
在這里a-1=0；
令其中i=0,1,2,…(n/2-1)；則
；
；
由上式可以看到加法計(jì)算量減少了一半，同時(shí)可以看出Ki+1X相對于KiX需要左移兩位。
在MBA中，乘數(shù)被劃分成2位的塊，對于第j個(gè)塊，塊中的2位(b2j+1,b2j)和前一個(gè)塊中的高位b2j-1重新進(jìn)行編碼，編碼真值表為：
符號擴(kuò)展及部分積產(chǎn)生
在部分積生成過程中，符號位的擴(kuò)展隨部分積一起產(chǎn)生，我們將所有的擴(kuò)展符號位相加：

由于和是48位的，故將上式中第一項(xiàng)舍掉，得：
；
對于部分積的產(chǎn)生，如果乘數(shù)經(jīng)booth重編碼后Ki為負(fù)，則需將部分積取反后加1，如表1所示。因此，在設(shè)計(jì)中可將每一個(gè)部分積的最后一位與ni相加，booth編碼值為負(fù)時(shí)ni=1；編碼值為正時(shí)ni=0。
部分積及被加數(shù)相加
Wallace tree是通過提高電路的并行度來提高電路速度的一種實(shí)現(xiàn)結(jié)構(gòu)，它將所有的部分積在同一時(shí)刻相互獨(dú)立地并行加到電路中，從而提高運(yùn)算速度。在Wallace tree結(jié)構(gòu)里面，我們用壓縮單元將乘法操作過程中產(chǎn)生的部分積以及被加數(shù)相加。在本設(shè)計(jì)中，我們把被加數(shù)作為一個(gè)部分積，加到Wallace tree陣列中，這樣就可以省去完成乘法運(yùn)算后再進(jìn)行加法運(yùn)算的操作延遲，提高M(jìn)AC單元速度。
最大的樹由3個(gè)3-2壓縮單元和4個(gè)4-2壓縮單元組成，樹的高度只有3級，這比只用全加器實(shí)現(xiàn)時(shí)的高度要小得多，延時(shí)也小得多。對于其他較小的樹，可以通過減少壓縮單元的數(shù)目來實(shí)現(xiàn)。圖4為本MAC單元中最大的Wallace tree 結(jié)構(gòu)(其中a22為被加數(shù)的相應(yīng)位)。
最終加法器
在Wallace tree陣列中，Wallace tree的每一列都產(chǎn)生一個(gè)初步的進(jìn)位項(xiàng)和一個(gè)初步的加法結(jié)果，最后必須使用一個(gè)快速加法器將所有的進(jìn)位項(xiàng)和加法結(jié)果加起來。為了獲得較高性能，一般采用先行進(jìn)位加法器(CLA)，它可以同時(shí)產(chǎn)生所有的進(jìn)位項(xiàng)，因而可以獲得極高的速度，在最壞情況下的延遲正比于n。但是隨著位數(shù)的增加，進(jìn)位項(xiàng)變得越來越復(fù)雜，相應(yīng)地消耗的面積越來越大，同時(shí)速度也無法得到保證。研究表明，CLA的最佳位數(shù)是4位，這時(shí)可以在速度與面積之間取得最優(yōu)的折衷。在本設(shè)計(jì)中，加數(shù)共有48位，因此將它分成12塊，每塊4位，塊與塊之間通過塊間進(jìn)位串聯(lián)，每一塊的進(jìn)位只影響本塊中的位，不影響更高塊的位。圖5為最終加法器的實(shí)現(xiàn)。

飽和檢測和飽和值的產(chǎn)生
在本設(shè)計(jì)中，通過下式來檢測結(jié)果是否發(fā)生溢出：

其中(Xn-1)為XY的符號。在發(fā)生溢出的情況下，通過48位2選1的MUX將飽和修正值輸出。修正的飽和值可以由下面的公式計(jì)算：
V=
(a2n-1為被加數(shù)的符號位)

結(jié)語
考察整個(gè)MAC單元的實(shí)現(xiàn)，優(yōu)化后的設(shè)計(jì)將被加數(shù)作為部分積的一部分加入到Wallace tree陣列中，從而在關(guān)鍵路徑上減少了一級串聯(lián)的先行進(jìn)位加法器；采用特殊的飽和檢測邏輯，可以不用再等待和的產(chǎn)生，使得飽和檢測操作可以和乘加操作并行進(jìn)行，將飽和檢測邏輯的延時(shí)排除在關(guān)鍵路徑延時(shí)之外。與優(yōu)化以前的設(shè)計(jì)實(shí)現(xiàn)相比，MAC單元的速度有了很大提高。優(yōu)化以后的設(shè)計(jì)實(shí)現(xiàn)，其面積和時(shí)延都集中消耗在部分積產(chǎn)生、Wallace tree陣列、最終加法器和2選1的MUX這四部分上。
表2是優(yōu)化前后的面積和時(shí)延的比較，從表中可以看出不論是在速度還是在面積方面，優(yōu)化后比優(yōu)化前都有了很大的改進(jìn)。

參考文獻(xiàn)
1 Michael J.Schulte, Pablo I. Balzola, Ahmet Akkas,and Robert W.Brocato. Inter Multiplication with Overflow Detection or Saturation. IEEE TRANSACTIONS ON COMPUTERS,VOL 49,NO.7,JULY 2000
2 Fayez Elguibaly. ast Parallel Multiplier-Accumulator Using the Modified Booth algorithm. IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS-II: ANALOG AND DIGITAL SIGNAL PROCESSIONG, VOL.47,NO.9, SEPTEMBER 2000