基于SRT4的整數(shù)除法器設(shè)計與優(yōu)化*

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

（1.貴州省光電子技術(shù)及應(yīng)用重點(diǎn)實(shí)驗(yàn)室，貴陽 550025；2.貴州大學(xué)大數(shù)據(jù)與信息工程學(xué)院，貴陽 550025）

1 引言

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

2 除法算法研究現(xiàn)狀

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

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

表1 典型CPU的除法運(yùn)用

3 常規(guī)算法

3.1 保留余數(shù)法

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

3.2 Goldsmidit算法

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

其中，函數(shù)迭代被除數(shù)為D，除數(shù)為d，Q=D/d，Di是分子，di為分母，F(xiàn)i為迭代因子[7]。

通過數(shù)學(xué)方法將除法操作轉(zhuǎn)為乘法，最后迭代直到分子的值接近商值Q，分母接近1。

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

3.3 SRT算法

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

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

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

4 優(yōu)化設(shè)計

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

4.1 算法優(yōu)化

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

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

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

圖1 使用CSA加法器處理中間數(shù)據(jù)

該結(jié)構(gòu)為三輸入二輸出，內(nèi)部沒有進(jìn)位，相當(dāng)于沒有絲毫?xí)r間上的冗余。整個CSA的延遲與一位全加器相同，并不受數(shù)據(jù)位寬的影響，適合于對多組相加數(shù)據(jù)做中間值管理。另外使用多組CSA器件，還能達(dá)到壓縮數(shù)據(jù)的作用。

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

4.2 結(jié)構(gòu)設(shè)計

所設(shè)計64位整數(shù)除法器的結(jié)構(gòu)原理如圖2所示。所有設(shè)計均為使用Verilog語言來實(shí)現(xiàn)。

圖2 64位整數(shù)除法器總體結(jié)構(gòu)

64位整數(shù)除法運(yùn)算通過如下三個步驟實(shí)現(xiàn)：

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

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

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

第三步：中間的數(shù)據(jù)處理選擇進(jìn)位保留加法器CSA，直到最后產(chǎn)生一組進(jìn)位保留格式的結(jié)果，Rj應(yīng)當(dāng)為0時，迭代操作還未結(jié)束，把商值左移，以補(bǔ)足被除數(shù)與除數(shù)的倍數(shù)關(guān)系。符號位是0為正，無需改動；符號位是1為負(fù)，結(jié)果以補(bǔ)碼形式寫出。

中間的邏輯步驟會有加、減、求補(bǔ)、移位操作。在此專門設(shè)計一個64位的加法器，以便在需要時調(diào)用完成加減與移位。加法器結(jié)構(gòu)設(shè)計如圖3所示。加法器設(shè)計以32位為單位，使用2位進(jìn)位選擇結(jié)構(gòu)，得到64位的中間值S。

圖3 加法器總體結(jié)構(gòu)

4.3 功能驗(yàn)證

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

圖4 基于SystemVerilog設(shè)計的功能驗(yàn)證模塊

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

圖5 改進(jìn)除法器與基16除法器實(shí)驗(yàn)對比結(jié)果

5 綜合分析

綜合結(jié)果是使用DC綜合工具在SMIC180工藝庫的標(biāo)準(zhǔn)溫度、電壓下得到的結(jié)果。綜合面積結(jié)果如表2所示。

表2 除法器綜合面積結(jié)果

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

表3 除法器性能對比

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

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

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

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

6 結(jié)束語

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