一種具有動態(tài)加速浮點乘法運算功能的變基maeh算法

隨著數(shù)字信號處理器（pd）的發(fā)展，浮點運算器的應(yīng)用越來越廣泛。乘法器是浮點運算電路的關(guān)鍵部件,對其整體性能影響很大。自從20世紀50年代初文獻提出Booth乘法器后,基于改進的Booth算法[2,.3]的乘法器設(shè)計就不斷有人提出。很多設(shè)計采用高基的Booth算法,以求收到較好的加速效果。但高基Booth算法在帶來較少的部分積累加次數(shù)的同時,也由于部分積不能完全直接通過移位生成而給累加器的設(shè)計帶來了很多問題,最直接的一個問題就是一個2輸入的累加器不能在生成部分積的同時完成累加。因此,這些設(shè)計所作的工作都集中在加法電路的優(yōu)化上。許多加法器結(jié)構(gòu)都是應(yīng)乘法器設(shè)計要求而生,如CPA(carry-propagateadder)、CSA(carry-saveadder)和Wallacetree等。在此基礎(chǔ)上對上述加法器結(jié)構(gòu)進行改進,以解決設(shè)計中延遲過大、布局布線時資源利用率低等問題,使乘法器性能達到最優(yōu)。而對于在有限的累加器資源下,如何通過采用合適的算法來使乘法器加速的討論則未見到。任何基的Booth乘法器對乘法運算的加速都是硬性的,均未考慮到數(shù)據(jù)的特點。實際上,在有限的硬件(主要是加法器)資源條件下,通過對乘數(shù)的各位組成結(jié)構(gòu)進行分析,也可減少部分積,收到動態(tài)加速的效果。本文設(shè)計的乘法器是利用乘數(shù)的特點靈活調(diào)整Booth編碼的基數(shù),所有的部分積都通過移位形成,對加法器要求低,關(guān)鍵路徑的延遲大大減小。同時這種變基Booth編碼的思想具有一般性的指導(dǎo)意義,可以用在其他的乘法器中,與具體的設(shè)計特點結(jié)合,得到更優(yōu)的結(jié)果。1浮點乘數(shù)法算例硬件電路進行二進制乘法的運算原理同手算十進制乘法的原理本質(zhì)上是一樣的,都是逐位將乘數(shù)與被乘數(shù)相乘,產(chǎn)生部分積累加起來。可以統(tǒng)一表示為Ρ=n-1∑i=0Y×ai×mi(1)P=∑i=0n?1Y×ai×mi(1)其中,Y表示被乘數(shù);ai等于0或1,表示乘數(shù)的第i位值;n為乘數(shù)的位數(shù),i從0～n-1的每一項Y×ai×mi都稱為部分積;m表示進制數(shù),當(dāng)m為2時,是硬件電路二進制乘法的基本計算原理,m為10時,則是手算十進制乘法的運算原理。計算實現(xiàn)過程可表示為Ρ0≤0Ρi+1≤Ρi+ai×Y?i(2)Ρ≤ΡnP0≤0Pi+1≤Pi+ai×Y?i(2)P≤Pn其中,Pi表示第i次迭代的累加和;“?”表示左移操作,其他參數(shù)的定義同前。需要指出的是,通常對于浮點乘法運算來說,并不需要保留乘積的所有有效數(shù)字,一般只保留與被乘數(shù)相同的位數(shù)的有效數(shù)字。因此,在實現(xiàn)乘法運算時會隨時舍棄低位的運算結(jié)果,其實現(xiàn)過程同理可表示為Ρ0≤0Ρi+1≤Ρi?1+ai×Y(3)Ρ≤ΡnP0≤0Pi+1≤Pi?1+ai×Y(3)P≤Pn從中可以看出,數(shù)字電路實現(xiàn)乘法運算的基本方法就是移位——累加。由此可見,減少迭代次數(shù)對于加快乘法運算的速度具有決定性的意義。有2種途徑:①增強累加器的能力,同時完成多個部分積的累加,這是乘法陣列的根本思想。②減少需要累加的部分積的數(shù)目,典型的代表是Booth重編碼方法,本文討論的內(nèi)容屬于后者。1.1將補數(shù)與被乘數(shù)的編碼生成部分積從(3)式表達的基本實現(xiàn)方法來看,乘數(shù)的每一位都產(chǎn)生部分積,數(shù)目很多。實際上當(dāng)ai為0時,并不需要累加,則累加器需要完成的累加次數(shù),即實際要生成的累加項的數(shù)目與乘數(shù)中值為1的位數(shù)相同。這樣,如果能將乘數(shù)中值為1的位數(shù)減少,就可以減少所需要完成的累加次數(shù)。類似與手算乘法中分配律的使用,但乘數(shù)本身乘法運算復(fù)雜,而它卻近似于某個大的整值數(shù)(如幾百、幾千等)時,可以用這個大的整值數(shù)與被乘數(shù)的積減去其對應(yīng)這個整值數(shù)的補數(shù)與被乘數(shù)的乘積來進行計算。把這種思想引入到二進制乘法中,若乘數(shù)中的1?0時,可以對其補數(shù)生成部分積。對整個乘數(shù)而言,出現(xiàn)這種情況的可能性很少,因此直接對整個乘數(shù)采用這種方法來減少部分積不切實際。一般是對乘數(shù)進行分組,通過分組可以消除整個乘數(shù)一起考慮時給乘數(shù)中0、1數(shù)目對比帶來的統(tǒng)計效果,而使得局部0、1數(shù)目差別較大;而且分組可以使處理變得簡單。將乘數(shù)進行分組,每組生成一個部分積。最基本的是4基Booth算法,每2位一組,8基Booth和16基Booth分別是每3位、每4位生成一個部分積,8基Booth以上稱為高基Booth算法。對于每組生成部分積時,采用編碼的方法,選擇利用補數(shù)或原數(shù)來生成累加項較少的部分積(有時為了整體編碼的簡化,在不影響累加器復(fù)雜度的前提下,也可能選擇累加項較多的部分積生成方法),以被乘數(shù)的倍數(shù)表示。運算乘積可表示為Ρ=[(n-1)/r]∑i=0Di×2r×i(4)P=∑i=0[(n?1)/r]Di×2r×i(4)其中,Di為第i組的部分積;2r為Booth的基值;n為乘數(shù)位寬。根據(jù)前面給出Booth算法減少累加項的原理可知:當(dāng)每組位數(shù)多于2位時,存在原數(shù)和補數(shù)都含有2個(或更多)1的情況,即高基Booth算法的部分積不能完全通過移位直接生成,有時需要加法運算,這給乘法器中的加法器設(shè)計在面積和時序上都帶來較大負擔(dān)。1.2變基法定共享算法傳統(tǒng)高基布斯的問題是:由改進Booth算法在生成部分積時對減少部分積的2種途徑考慮的順序所導(dǎo)致的。改進Booth算法首先考慮將乘數(shù)分組,在分組確定的基礎(chǔ)上考慮如何減少累加項。它只是固定地將每幾位乘數(shù)組合一起,沒有考慮這種組合是否有利于部分積的直接生成。從上述討論可知,分組不單是為了使處理簡化,還有一個更重要的目的是使局部范圍的0、1數(shù)目對比出現(xiàn)較大差別。而固定位數(shù)的分組方式?jīng)]有考慮乘數(shù)中0或1分布的集中度問題,顯然在這方面收效甚微。而從前面描述的補數(shù)的原理可以看出,分組位寬固定的要求并不必要。如果能在首先考慮減少累加項的基礎(chǔ)上進行分組,再將乘數(shù)分割組合時能靈活變動,使乘數(shù)中0或1較集中的一段分為一組,而不是將固定位數(shù)的乘數(shù)組合在一起,就可以在不給累加器帶來時序負擔(dān)的前提下,較好地減少部分積生成數(shù)目。變基Booth算法的核心思想就是打破分組位數(shù)固定的限制,在考慮簡化部分積生成的前提下確定每一組的寬度,根據(jù)乘數(shù)的當(dāng)前特征靈活分組。不同的分組寬度,對應(yīng)Booth算法的不同基值,因此稱為變基Booth算法。確定分組寬度的原則是使生成部分積只需對被乘數(shù)作移位操作,而不需加法器的參與。其分組準則描述如下:準則1分組從最低位開始,順次截取一定位數(shù)的乘數(shù)為一組,記為T=akak-1,…,a0。準則2若將T看成補碼表示的帶符號數(shù),應(yīng)有-2≤T≤1。準則3k≥1,若ak不是整個乘數(shù)的最高位,應(yīng)有ak+1⊕ak=1。準則1是由乘法的運算規(guī)則決定的。值得一提的是,分組也可以從高位開始,需要從高位向低位乘的算法來配合。從高位向低位進行乘法累加的缺點是:增加了硬件資源消耗,而且導(dǎo)致關(guān)鍵路徑長度增加;優(yōu)點是,通過適當(dāng)控制,可以使許多乘數(shù)低位為全零的數(shù)據(jù)運算提前多個周期完成,在某些特定場合可以使用。而本文討論的是通用的浮點乘法計算,因此不在這一方面展開。準則2是保證部分積直接生成的關(guān)鍵,當(dāng)-2≤T≤1時,可保證T中1的數(shù)目不會多于1個。若單獨考察分組數(shù)據(jù),當(dāng)T=±2k時,均滿足原碼中只有一個1的條件,但考慮到相鄰一組產(chǎn)生的進位時,只有T為-2、-1、0和1這4種情況滿足要求。準則3則是由部分積最少的要求決定的,即力求每組的位寬在滿足部分積移位生成要求的同時達到最大。這里需要指出的是,在實際設(shè)計中,為了控制邏輯的實現(xiàn)簡潔,一般要有個位寬上限且位寬上限越大,控制邏輯越復(fù)雜。根據(jù)分組準則可知,乘數(shù)分組時每組的位寬最小為2位,最大的可能值為位寬上限。不同傳統(tǒng)Booth算法,變基Booth的運算乘積可表達為Ρ=m∑i=1Di×2i-1∑j=0ri(5)P=∑i=1mDi×2∑j=0i?1ri(5)其中,Di為第i組的部分積;ri為第i組的位寬,r0=0,顯然有:m∑i=1ri=n?n∑i=1mri=n?n為乘數(shù)位寬。通過剖析變基Booth乘法的運算原理并給出分組準則后,變基Booth乘法器的設(shè)計實現(xiàn)思路就非常清晰了。2編碼值的確定和變形從變基Booth乘法的運算原理公式可以看出,設(shè)計實現(xiàn)的關(guān)鍵有4個部分:當(dāng)前組位寬的確定、部分積的獲得、累加的完成,以及累加和、乘數(shù)的移位。變基Booth乘法器的算法結(jié)構(gòu)圖,如圖1所示。其中,Booth算法基值改變主要是通過分組控制邏輯來實現(xiàn),依據(jù)前面給出的準則,結(jié)合乘數(shù)的特點來確定當(dāng)前組的位寬。為了簡化分組控制邏輯,本設(shè)計中設(shè)定位寬上限為8位。對于尾數(shù)寬度小于64位的乘法器來說,8位的位寬上限是比較合理的。對于部分積生成,由準則2可知,有-3<T<2,加上前一組的進位考慮,只需將每組的最低2位結(jié)合前一組的進位來譯碼就可以了,譯碼復(fù)雜度與4基Booth相當(dāng)。變基Booth譯碼,見表1所列。從表1看出,它同4基Booth的編碼表相同。這是因為分組時所控制的編碼值T的范圍同4基Booth完全一樣,這也是變基Booth可以在不增加累加器復(fù)雜度的同時收到加速乘法效果的根本所在。這樣,所有的部分積分布在-2Y～2Y之間,通過簡單的移位就可以獲得。設(shè)計實現(xiàn)中另一個關(guān)鍵在于累加和與乘數(shù)都需要進行可變位數(shù)的移位(這是由于分組位寬的不固定導(dǎo)致的),因此需要設(shè)計一個可以進行位數(shù)選擇的移位單元,本文通過設(shè)計移位通道解決了這一問題,該移位通道可以實現(xiàn)0～8位右移操作。需要指出的是,為了節(jié)省資源,該移位通道用定制的方法來實現(xiàn),在RTL仿真時使用開關(guān)級語句描述。另外,考慮節(jié)省面積,累加和與乘數(shù)移位復(fù)用移位通道,乘數(shù)移位與累加和移位分別占用時鐘周期的高電平和低電平部分,累加和移位結(jié)果由時鐘上升沿觸發(fā)鎖存,乘數(shù)移位結(jié)果由時鐘下降沿觸發(fā)鎖存。由于用于累加的加法器都是通道設(shè)計,不含鎖存機制,因此需要對當(dāng)前組的控制字進行鎖存。加法器不是本文的設(shè)計重點,實際上本文提出的變基Booth算法的目標就是減輕加法器的負擔(dān),任何通用的2輸入加法器都適用于本設(shè)計,因此在綜合設(shè)計時沒有對這部分做過多優(yōu)化。3不同工藝庫的特性對比基于變基Booth算法的乘法器具有動態(tài)加速的功能,對于不同的操作數(shù),加速效果不同。運用隨機模擬的辦法,從10萬次、100萬次…10億次,對32位尾數(shù)寬度浮點乘法運算的周期數(shù)進行統(tǒng)計,當(dāng)模擬到1000萬次以后,平均周期數(shù)保持為10.832443,這一效果略優(yōu)于傳統(tǒng)8基Booth算法的加速效果。而本設(shè)計在面積和速度上都優(yōu)于8基Booth乘法器。表2所列是本設(shè)計同采用CSA加法電路優(yōu)化過的8基Booth乘法器在基于Tsmc0.25μm工藝庫綜合后的性能比較。在