支持媒體處理的子字絕對值單元設(shè)計與實現(xiàn)*

開耀文，高德遠，張 萌

(西北工業(yè)大學計算機學院，西安710129)

1 前言

當前，為了滿足多媒體應用的需要，很多通用處理器提供了針對多媒體應用的擴展指令。如Intel的MMX，AMD 的3DNow!，以及 Motorola的 AltiVec等。

多媒體應用具有兩個基本特點:數(shù)據(jù)并行度高和數(shù)據(jù)精度要求低［1］。子字并行技術(shù)是一種單指令流多數(shù)據(jù)流技術(shù)，它的原理是一條指令中的數(shù)據(jù)可以拆分成多個子字并行執(zhí)行。例如AltiVec指令集中，參與計算的操作數(shù)位數(shù)為128位，這些操作數(shù)可以選擇4個32位字的，或者8個16位半字，或者16個8位字節(jié)進行運算。子字并行運算的特點正好與多媒體應用的特點相符合，是一種有效提高多媒體應用性能的手段。

在圖像處理中，兩個數(shù)的絕對值運算|A-B|得到了廣泛應用，例如視頻中的運動估計和預測算法中就采用了大量的這種絕對值運算。在沒有實現(xiàn)絕對值單元的通用處理器中，實現(xiàn)一個無符號絕對值運算需要進行A-B和B-A運算，并將結(jié)果相或，實現(xiàn)一個有符號絕對值運算則需要更復雜的步驟。而采用了絕對值單元的處理器只需要一條指令就能實現(xiàn)通用處理器中需要多條指令實現(xiàn)的絕對值運算。絕對值單元在減少計算指令數(shù)的同時減少了訪存次數(shù)，因為絕對值運算只需要一次取出操作數(shù)做運算，而不用像通用處理器那樣需要多次取數(shù)。絕對值運算是建立在普通減法運算基礎(chǔ)上的，通過擴展原有加法器實現(xiàn)絕對值單元可以使普通的加法器與絕對值單元共享一個計算單元，這樣實現(xiàn)絕對值單元的代價是較小的。

2 并行前綴加法器原理

2.1 加法器原理

考慮加法器的進位傳播公式［2］:

單個進位生成和not kill信號給出如下:

公式(1)和(2)的信號可以概括地描述為:在多位組所包括的位z...x范圍內(nèi)，可分成高位組和低位組兩個子組，進位生成信號是由兩方面決定的:高位子組z….y生成進位信號或者低位子組y-1...x生成進位，而低位子組的生成進位信號不被“殺死”。如果高位子組和低位子組的都不“殺死”進位，那么這個組也不“殺死”進位。

公式3說明第i位的進位信號即是第i-1位到第0位的組進位生成信號。根據(jù)求和公式Si=Pi8 ci可得到A與B的和，其中Pi為單個位的進位傳播信號，Pi=Ai8Bi;Si為和的第i位。

因此，加法可以縮減為三步來進行［3］:

(1)使用公式4和5按位計算進位生成和not kill信號;

(3)結(jié)合公式3和求和公式計算求和信號。

顯然，進位生成邏輯是整個計算的關(guān)鍵。加法器運算的優(yōu)化核心就是減小進位信號的生成時間。由此引出了各種優(yōu)秀的加法器設(shè)計，如超前進位加法器，條件加法器，旁路進位加法器和并行前綴加法器。其中，相對于其它加法器結(jié)構(gòu)，并行前綴加法器對于位寬較大的加法運算(N＞16)可以較好的控制延時增長，通過構(gòu)造多級結(jié)構(gòu)可以取得以logN增長的延時［3］。通過構(gòu)造并行前綴樹，快速的計算出各個位的進位信號，從而快速計算出加法結(jié)果。

2.2 并行前綴樹原理

1.并行前綴計算公式如下［4］:

式中，“·”算符為前綴計算算符。前綴計算算符具有兩個重要的計算性質(zhì):結(jié)合律及冪等律，即滿足以下公式:

結(jié)合律使得整個計算式可以并行計算，冪等律允許各并行計算子項交疊執(zhí)行，從而給并行前綴加法器的構(gòu)造帶來很大的靈活性［5］。不同的并行前綴加法器正是對并行子項的不同區(qū)間運用了結(jié)合律和冪等率而得到的。圖1給出了ladner-Fischer［6］的并行前綴樹示意圖，圖中黑點采用公式1和2，灰點采用公式1。ladner-Fischer樹的構(gòu)造較為簡單，各個計算子項沒有重疊，計算層數(shù)達到最優(yōu)。

圖1 32位ladner-Fischer加法器并行前綴樹示意圖

3 絕對值運算的研究與設(shè)計

通常，計算絕對值的方法是將兩個數(shù)大小進行比較，再根據(jù)比較的結(jié)果，用大值減去小值，或者直接計算兩個數(shù)的減法，再對結(jié)果取正值。硬件實現(xiàn)中［7］，這種計算方法需要兩步運算。顯然，兩步運算增加了關(guān)鍵路徑的長度，從而對整個運算的時序產(chǎn)生影響。為了消除這樣的兩步運算，可以通過另外一種方法解決［8］。這種方法的思想基于條件加法器，即同時計算A-B和B-A，通過計算結(jié)果的符號位選擇結(jié)果為正數(shù)的計算通路。

然而，這種方法在減小關(guān)鍵路徑的同時，大大增加了計算單元的面積，因為它引入了兩條計算通路。

3.1 絕對值運算的分析

通過觀察發(fā)現(xiàn)，無論用何種方法，絕對值運算中，兩個數(shù)的減法運算是必須的過程。同其它運算一樣，絕對值運算的操作數(shù)也分有符號數(shù)和無符號數(shù)，以下分別通過有符號操作數(shù)和無符號操作數(shù)來分析絕對值運算。

3.1.1 有符號絕對值運算

對于有符號數(shù)，補碼的加減法運算是最常見的運算方法，因為有符號數(shù)補碼減法可以轉(zhuǎn)化為有符號數(shù)補碼加法的運算，所以這里討論的都是基于補碼的運算法則，并且參與運算的兩個數(shù)都為有符號數(shù)。約定A為A的所有位取反。A-B=A+(B+1)，B=-(B+1)，在加法運算前將B的所有位取反得到的結(jié)果為A-B-1。如果這個值是正數(shù)，加法器的結(jié)果加1就是絕對值的計算結(jié)果。反之，如果加法器的結(jié)果是負數(shù)，將加法器結(jié)果的所有位取反得到的結(jié)果為-(A-B-1+1)=B-A，也為絕對值的結(jié)果。所以，絕對值運算可以實現(xiàn)為在加法器中加入兩個控制信號:和加一信號inc和取反信號inv，并且其中一個操作數(shù)在送入加法器中時全部取反。顯然，inc=inv。如果加法器結(jié)果的符號位為負，則將加法器結(jié)果的全部位取反即可。如果加法器結(jié)果的符號位為正，則還要對加法器的結(jié)果加1。

3.1.2 無符號絕對值運算

兩個有n個數(shù)字的二進制無符號絕對值|M-N|可按以下步驟進行:

(1)將被減數(shù)M與減數(shù)N的補碼相加，即:

(2)當M＞=N，M-N的值即為絕對值的大小。觀察發(fā)現(xiàn)，如果M＞=N時，結(jié)果將產(chǎn)生進位2n，舍去這個進位，得到的就是M-N。

(3)當M＜N，那么N-M的值即為絕對值的大小，對于這種情況，將被減數(shù)M與減數(shù)N的反碼相加，即:

由于N＞M，結(jié)果和不會產(chǎn)生進位，且為N-M的反碼，將結(jié)果取反即可得到N-M的值。通過以上分析可知，無符號絕對值運算與有符號絕對值運算具有共同的性質(zhì)，總結(jié)如下:

·兩操作數(shù)之一需要求反送入加法樹中，即進行減法運算;

·對加法樹出來的結(jié)果位處理方式相同，取反或者結(jié)果加1。

顯然，取反運算相對于結(jié)果加1運算的延時小很多。所以，結(jié)果加1處于關(guān)鍵路徑上。最壞情況下，加1運算的進位傳播延時經(jīng)過加法器結(jié)果的每一位，這對于整個計算單元時序的影響是很大的。定義需要對加法器結(jié)果的和進行加1的運算為和加一運算。為了消除對加法器結(jié)果的加一運算，需要研究和加一運算的性質(zhì)。

3.2 和加一運算

考慮和加一運算的重要性，定義和加一運算的進位信號為CA，則第i位的進位信號為CAi。CAi信號與原本的c(i)信號是有聯(lián)系的:如果c(i)=1，顯然 CAi=1;如果 c(i)=0，而且 i-1…..0組不“殺死“進位，即=1，則 CAi=1，所以 CAi=。由以上描述可得:

將式3代入得到:

其中，inc為和加一運算控制信號。所以和加一運算的求和公式為SAi=CAi8Pi，其中SAi為A與B和加一運算結(jié)果的第i位。

輸出邏輯如圖3所示。

4 子字并行絕對值單元的設(shè)計

通過分析加法器的結(jié)構(gòu)可知，要想實現(xiàn)子字并行運算，最重要的是要控制低位子字的進位對高位子字產(chǎn)生影響。例如，在AltiVec指令集中，基于字節(jié)運算的指令要消除在7+8*i(0≤i≤15)位上產(chǎn)生的進位。所以，需要一個控制邏輯來控制低位進位需不需要傳播到高位，對于32位字，對最短子字長度為8的加法器單元，通過給出的控制信號，可以同時計算4個字節(jié)，或2個半字，或一個字的加法。如表1所示。

表1 控制信號

在一般的子字并行加法器設(shè)計中，控制邏輯只要控制了進位的傳播就能實現(xiàn)子字并行加法。當需要進行子字加法時，屏蔽相鄰位的進位;反之，允許進位?；诖嗽?，提出了進位控制機制:進位截斷機制［1］。該方法的思想是，在并行前綴加法器的并行前綴樹結(jié)構(gòu)中，當需要進行子字并行運算時，控制低位的進位對高位的影響，即在子字的邊界處設(shè)置控制信號，消除進位的傳播。

參照這種思想，對于子字并行絕對值的運算也可以通過設(shè)置控制位截斷進位的方式來實現(xiàn)。通過比較分析，子字并行絕對值單元在絕對值單元上做如下改進:

(1)采用與子字并行加法器相似的進位截斷機制，根據(jù)控制信號的有無決定是否將低位的進位信號傳遞到高位。

(2)根據(jù)絕對值運算的特點，需要獲得最小子字(8位)進位和符號位。以決定對結(jié)果進行取反還是加一操作。

通過以上分析可知，子字并行絕對值單元的結(jié)構(gòu)框圖如圖4所示。

圖4 32位子字并行絕對值單元

輸出邏輯如圖3，由于要實現(xiàn)子字并行，所以相應的inc和inv如下:

輸出邏輯0:inv0_7=(inv8＆～S0＆～S1)|(inv16＆S0＆ ～S1)|(inv32＆S0＆S1);

輸出邏輯1:inv8_15=(inv16＆～S0＆～S1)|(inv16＆S0＆ ～S1);

輸出邏輯2:inv16_23=(inv24＆～S0＆～S1)|(inv32＆S0＆ ～S1)|(inv32＆S0＆S1);

輸出邏輯3:inv24_31=(inv32＆～S0＆～S1)|(inv32＆S0＆S1)

其中 invx=sign?sx-1:coutx(x 為8，16，32)

5 實現(xiàn)與性能分析

5.1 實現(xiàn)

采用verilog語言實現(xiàn)了以上討論的32位子字并行絕對值單元的可綜合設(shè)計，同時實現(xiàn)了前面所討論的其它可實現(xiàn)絕對值單元的方法，并使之并行化。文獻［7］中沒有經(jīng)過優(yōu)化的絕對值單元為方案1，文獻［8］中采用條件加法器思想的絕對值單元為方案2，經(jīng)過優(yōu)化的絕對值單元為方案3。使用Modelsim對3種方案的設(shè)計進行仿真，仿真數(shù)據(jù)的輸入采用隨機數(shù)，運算模塊的輸出結(jié)果同相對應的行為級的輸出結(jié)果比較，結(jié)果全部正確。為了比較3種方法的面積與延時，采用synopsys Design Complier［9］工具進行邏輯綜合，為了體現(xiàn)公平性，所有絕對值單元中的加法器結(jié)構(gòu)都是用ladner-Fischer前綴加法器，不采用 synopsys DesignWare［10］中的基本加法單元。在TSMC 0.13um工藝下對這三種方案的子字并行絕對值進行了實現(xiàn)并測試了它們的性能，時序/面積報告如表2所示:

表2 子字并行絕對值單元時序/面積報告

三種方案的絕對值單元的時序/面積報告如表3所示。

表3 絕對值單元時序/面積報告

5.2 性能分析

通過時序/面積報告可以看出，沒有實現(xiàn)子字并行的絕對值單元中，方案1的面積與方案3的面積相當，但方案3的時序明顯好于方案1。方案2的時序與方案3相當，但方案3的面積比方案2小很多。從前面分析可知，方案2采用了兩個加法器同時計算A-B和B-A，所以面積大了很多，而方案1是采用時間換取面積的方式，通過加法器計算結(jié)果來進行下一步運算，所以它的延時較大。方案3綜合了前兩種方案的優(yōu)點，所以它的延時與面積都與前兩種方案的最好形式相當。通過對和加一運算的分析，使得在加法器的運算過程中可以同時進行A+B和A+B+1運算，所以采用方案3方法實現(xiàn)的絕對值單元在減小面積的同時，也減小了整個運算單元的延遲。

子字并行絕對值單元是在絕對值單元的基礎(chǔ)上增加了一些控制低位進位的邏輯，所以延時和面積較絕對值單元要大一些，但增加的不是很明顯。相比較其它方案，方案1中，子字并行絕對值單元的面積比絕對值單元大了很多。這是因為方案1中的絕對值單元是在加法器結(jié)果出來后，通過判斷加法器的進位或符號位來決定對結(jié)果取反還是加一。因為每一個加法器模塊后面都有一個實現(xiàn)加一運算的加法器，為了實現(xiàn)子字運算，每個相應的8位，16位和32位子字都需要這樣的加一運算，所以導致方案1的面積大大增加。

6 結(jié)束語

子字并行運算作為加速多媒體運算的有效方式，在各種媒體處理(比如音頻和視頻)需要的大量運算中得到了充分利用。該文分析了基于前綴加法器的子字并行絕對值單元的實現(xiàn)方法，并重點介紹了優(yōu)化絕對值單元中的和加一運算，結(jié)合前綴加法器的特性，使得加法器可以同時進行A+B和A+B+1運算。分別實現(xiàn)了各種絕對值單元和子字并行單元并進行了比較。結(jié)果顯示:優(yōu)化的子字并行絕對值單元在面積上克服了條件絕對值單元的不足，同時又保持了條件絕對值單元犧牲面積所帶來的時序優(yōu)勢，在整體性能上優(yōu)于前文提出的絕對值單元。

［1］ 馬勝，黃立波，王志英，等.子字并行加法器的研究與實現(xiàn)［J］.計算機工程與應用，2009，45(36):54-58.

［2］ N Burgess.The flagged prefix adder and its application in integer arithmetic［J］.VLSI Signal Process，2002，31(3):263-271.

［3］ Neil H.E.Weste，David Harris.CMOS超大規(guī)模集成電路設(shè)計［M］.汪東，等譯.北京:中國電力出版社，2006.

［4］ Weinberger A，Smith J L A.A logic for high-speed addition［J］.National Bureau of Standards Circular，1958，591:3-12.

［5］ Beaumont-Smith A，Um C C.Parallel prefix adder design［C］.Pro-ceedings of 15th IEEE Symposium on Computer Arithmetic，2001:218-225.

［6］ Ladner R E，F(xiàn)ischer M J.Parallel prefix computation［J］.ACM，1980，27(4):831-838.

［7］ Carlson，D.A，Castelino，R.W，Mueller，R.O.Multimedia extensions for a 550-MHz RISC microprocessor［J］.IEEE Journal of Solid-State Circuits，1997，32(11):1618-1624.

［8］ S.C.Knowles.Arithmetic processor design for the T9000 Transputer［C］.Proc.SPIE，1991:230-243.

［9］ Synopsys Inc.Design compiler user guide［M］.Mountain View:Synopsys，2007.

［10］ Synopsys Inc.DesignWare building block IP user guide［M］.Mountain View:Synopsys，2007.