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

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

1 引言

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

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

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

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

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

3 常規(guī)算法

3.1 保留余數(shù)法

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

3.2 Goldsmidit算法

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

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

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

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

3.3 SRT算法

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

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

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

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

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

4.1 算法優(yōu)化

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.3 功能驗(yàn)證

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

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

在圖4所示的功能驗(yàn)證環(huán)境中，選取三組數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，驗(yàn)證所設(shè)計(jì)結(jié)構(gòu)的功能，并對(duì)比本設(shè)計(jì)與基16算法除法器對(duì)相同數(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è)計(jì)運(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。由波形圖可見(jiàn)，改進(jìn)設(shè)計(jì)的除法器實(shí)現(xiàn)了預(yù)期功能。

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

5 綜合分析

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

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

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

表3 除法器性能對(duì)比

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

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

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

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

6 結(jié)束語(yǔ)

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