衛(wèi)祥慶，秦水介

（1.貴州省光電子技術及應用重點實驗室，貴陽 550025；2.貴州大學大數據與信息工程學院，貴陽 550025）

1 引言

眾所周知處理器的最重要操作在于完成運算，整數除法也是衡量處理器性能的重要方面。除法的應用場景遠低于加減乘操作，因此大多數設計者都不會優(yōu)先做除法上的改良。整數除法的應用比例大概占總體運算的百分之三，目前也不是主流的研究方向。然而，近年來有研究表明：一旦數據通路有阻塞時發(fā)生，會增加每指令周期數CPI，處理器的整體性能也隨之會大幅降低，嚴重時降幅可超過40%[1]。此類情況下，對處理機芯片除法運算的研究體現出其重要性。優(yōu)秀的除法算法能夠明顯提升系統性能，降低功耗與成本。

2 除法算法研究現狀

國內目前對除法算法的研究仍然不是很多，更多是加法、減法、乘法上的研究。除法研究大多是對SRT算法的進一步改進。有提出以更高基除法來縮小時鐘周期，也有提出并行計算查找表與查找表輸入，有提出飛速轉換部件來提高浮點除法運算[2]。同濟大學的劉冀[3]做過以SRT2為基礎、并行做SRT4的模擬，發(fā)現比原來的性能提升20%，面積只增加5%，結構更加簡潔。在國外，印度學者在《Computer Science》中提出并行除法解決方案，將部件拆開多個部分，各個部分同時并行來減少時延。

當前學界通常將除法分為五種:數位迭代（Digit Recurrence）；函數循環(huán)（Functional Iteration）；高基算法（FLigh-Radix）；可變延時法（Variable Latency）[4]；查表法（Table）。起初除法主要多使用數位迭代，雖然會使得硬件面積變大，但結構簡單。上世紀90年代末以來，為實現更高性能計算機，開始采用SRT的方法。典型CPU用于除法運算的使用情況如表1所示。

表1 典型CPU的除法運用

3 常規(guī)算法

3.1 保留余數法

保留余數法的實質是用加減法來實現除法，屬于數位迭代法。第一步操作從商的最高有效位開始，用被除數中對除數進行一次試探性的減法[5]。在保留余數的過程中，使用的是加法。在循環(huán)中的操作是加法還是減法，則取決于上一輪的部分余數Rj的符號與被除數的符號是否一致。若一致，減去除數，否則加上除數，其符號位不再產生進位（舍棄），所得結果為本輪部分余數R，再對商位做判斷[6]。在此處再把余數左移一位，進行減操作。如果試探減法成功，那么商位為“1”，循壞操作直至結束。

3.2 Goldsmidit算法

此類算法是目前算法中公認性能最優(yōu)秀的，其核心思想可由下式表述：

其中，函數迭代被除數為D，除數為d，Q=D/d，Di是分子，di為分母，Fi為迭代因子[7]。

通過數學方法將除法操作轉為乘法，最后迭代直到分子的值接近商值Q，分母接近1。

這一算法的缺點也顯而易見，就是需要另外設計乘法器，此舉會影響乘法指令的周期，并且對所得到的結果還要另外進行處理。

3.3 SRT算法

算法名稱SRT來自于三位提出者Sweeney、Robertson和Tocher的名字首字母。此算法結構簡單，采用數值循環(huán)的基本思想。其基本概念為：進行一次求商運算可以得到固定位數的商位數值，通過循環(huán)運算同時得到準商和余數值[8]。常見的SRT算法有SRT4與SRT16。目前大多數的SRT都是通過查詢Radix基表的方法獲得結果，除此以外整個過程由加減法和移位操作完成，運算過程可表述為：

其中，Rj為部分余數迭代循環(huán)j次的值，d為除數，D為被除數，q為商位。

對不同基時鐘計算周期，可表述為：n=log2r，其中n代表了運算過程中得到的商數的位數，r為定下的基數[9]。以此，基2的算法在每次迭代會得到1位商數位，基4得2位，基16得4位，基64得6位，從而完成多次循環(huán)迭代運算。

4 優(yōu)化設計

對除法運算進行優(yōu)化的主要方法為：利用基本的SRT-4算法做除法運算來實現對SRT-64除法運算的模擬。

4.1 算法優(yōu)化

極大基法是目前SRT算法中為了減少時鐘周期、提高運算頻率而提出的一種方法。每次迭代的位數取決于所使用的基數r，即r=2b（b為每次迭代均獲得結果的位數）。當基為64時，每次迭代得到6位，最理想情況為64/6，即11個周期內就可以完成。然而此處的商選過程十分復雜，根據研究，查找表的面積與r成2的指數冪增長，即使是以最小的冗余來看，也會產生超大的面積，得不償失。

對除法使用基數為4的數位遞歸SRT算法（每次迭代的結果為2位），每個循環(huán)重復多次，模擬基64的SRT算法，來縮短運算周期，除法每個周期3次迭代，即6位/周期，等效于基數64位數的遞歸除法。與極大基64方法相比，硬件結構與面積大幅減少，運算的時鐘周期也得以縮短。

為實現優(yōu)化，所設計的結構為在一個周期內需要同時完成三次基4迭代，通過基數差分的方法，增加基4的迭代次數。雖然相比基4 SRT會增加硬件的面積，但與基SRT16相比硬件結構并未有太大的變化。基4 SRT部分余數運算為Rj+1=4Rj-qj+1d，此過程進行三次。對于中間三次迭代中多組數據的相加使用CSA加法器來提高運行速度，結構如圖1所示，它將中間步驟的Rj分成Sj與Cj。

圖1 使用CSA加法器處理中間數據

該結構為三輸入二輸出，內部沒有進位，相當于沒有絲毫時間上的冗余。整個CSA的延遲與一位全加器相同，并不受數據位寬的影響，適合于對多組相加數據做中間值管理。另外使用多組CSA器件，還能達到壓縮數據的作用。

除法中商數位值的選擇是最占硬件面積的，所以設計合適的共用商數選擇查找表邏輯也很關鍵。在具體實現時，q可取值為q∈(-3,-2,-1,0,1,2,3)d，稱為最大冗余度；也可取q∈(2,-1,0,1,2)d，稱為最小冗余度[10]。使用最小冗余度可避免運算過程中碰到(3d,-3d)的情況，其中2d和-2d可以通過對d和-d移位產生。

4.2 結構設計

所設計64位整數除法器的結構原理如圖2所示。所有設計均為使用Verilog語言來實現。

圖2 64位整數除法器總體結構

64位整數除法運算通過如下三個步驟實現：

第一步：對于輸入的操作數進行符號位擴展以及負數的求補，以此可使之兼容無符號數的運算。對于32位的操作數，需將高的32位符號位變成31位的數。規(guī)格化的操作后再進行完除數與被除數的判定。在運算開始后可以不用考慮符號位，且數據高位對齊，以此節(jié)省運算時間，減少商選函數的硬件邏輯冗余度[11]。

第二步：商值循環(huán)迭代，在一個周期里迭代得到2位商值，之后再進行兩次迭代，累計得到6位商值，如此進行直至迭代次數值或者Rj為零。由于部分余數的計算在全商值范圍內進行，在一個周期須進行三次迭代，此時需要拆基：基4需要兩個CSA加法器用來做進位保留，還要增加另外兩個保留加法器CSA進行下一次迭代，每一次皆需如此，因此有2×2×3，一共需要12個CSA。

根據加法器計算的部分余數結果，得到下一次迭代的部分余數，同時在過程中根據最小冗余度得到6位商數值。本次迭代部分余數值作為下次迭代部分余數，除數累計移6位，再進入下一次迭代。部分余數rem的計算在整個路徑上不可避免要增加整體部件的時間延遲。如果部分余數的計算選擇冗余的方法，即使用Carry save adder（CSA），將減少rem的時間延遲。

第三步：中間的數據處理選擇進位保留加法器CSA，直到最后產生一組進位保留格式的結果，Rj應當為0時，迭代操作還未結束，把商值左移，以補足被除數與除數的倍數關系。符號位是0為正，無需改動；符號位是1為負，結果以補碼形式寫出。

中間的邏輯步驟會有加、減、求補、移位操作。在此專門設計一個64位的加法器，以便在需要時調用完成加減與移位。加法器結構設計如圖3所示。加法器設計以32位為單位，使用2位進位選擇結構，得到64位的中間值S。

圖3 加法器總體結構

4.3 功能驗證

驗證工具語言采用SystemVerilog，基于UVM驗證方法學搭建功能驗證模塊，原理如圖4所示。驗證數據來自于定點數據、邊界性數據與隨機數據，使用這些數據對驅動產生激勵。Driver是用來驅動設計和對比的模塊。計分板Scoreboard是用來記錄與反饋數據比較功能是否完成。

圖4 基于SystemVerilog設計的功能驗證模塊

在圖4所示的功能驗證環(huán)境中，選取三組數據進行實驗，驗證所設計結構的功能，并對比本設計與基16算法除法器對相同數據的不同表現。實驗結果如圖5所示。圖中為運算后的功能驗證波形，div_r16[63:0]為基16 SRT算法結果，div_r4_64[63:0]為本設計運算結果。第一組定點數據ffff_fffff_ffff_ffff(-1)自身相除商值得1；第二組邊界性數據8000_0000_0000_0000(-263)除負1，商值發(fā)生溢出；第三組隨機數據10除以6商為1。由波形圖可見，改進設計的除法器實現了預期功能。

圖5 改進除法器與基16除法器實驗對比結果

5 綜合分析

綜合結果是使用DC綜合工具在SMIC180工藝庫的標準溫度、電壓下得到的結果。綜合面積結果如表2所示。

表2 除法器綜合面積結果

基于傳統的SRT16實現64位有符號整數除法時，商數值Q的位數位4=log216。不考慮其他因素的理想情況下，有64/4=16，即16個周期內可完成。兩種除法器的性能對比如表3所示。

表3 除法器性能對比

Div_16原本的設計是傳統的SRT-16算法，考慮到在商數位選時查找表會極大占據硬件面積，所以在面積上r4_64是占優(yōu)勢的。在功耗對比上，雖然原設計功耗更低，由于SRT算法會大量增加芯片內部晶體管的數量，所以整體功耗也大幅增加。在總體面積幾乎不變的同時，優(yōu)化設計在頻率上提升20%，時鐘周期縮短30%。

此處頻率的提升是顯著的，數據通路產生slack的值全為正數，意味這本設計的時序未有冗余。在最大路徑和最小路徑中slack值為0.003與0.07。

時鐘周期也是衡量除法器性能的關鍵指標。CPI是執(zhí)行一條指令所需要的時間周期。執(zhí)行一條指令所需要的時鐘周期數也等于總的周期數除以總指令數。一般除法的周期數在6～60之間，僅考慮數字迭代循環(huán)步驟時，基16的設計最小時鐘周期為16，而模擬基64則只需要11個時鐘周期。

從綜合的結果可以證明，模擬基64算法出色地實現了一款除法器應有的功能。在硬件面積、功耗與性能之達到了一種優(yōu)化的新平衡。

6 結束語

相比與原有的基16除法器，模擬基64的新設計可以在面積幾乎不變的同時在頻率上獲得20%的優(yōu)化，時鐘周期縮短30%。當增大SRT的基數值，將會使得除法運算的循壞迭代時間變短，硬件復雜與面積也會增加，而在硬件上增加了數據處理量，提高了運算處理能力。與目前高性能處理器里采用的簡單快捷的SRT16算法相比，該種方法最主要的是提高了實時性，在面積結構相似的設計下，部件將運算執(zhí)行的周期數大幅減少，多時鐘周期的除法指令因此能夠得以更快執(zhí)行。