一種基于SRT－8算法的SIMD浮點除法器的設計與實現(xiàn)＊

鄧子椰，陳書明，彭元喜，雷元武

（國防科學技術大學計算機學院，湖南長沙410073）

1 引言

浮點除法運算是基本操作之一。在早期的計算機中，除了除法本身的復雜性外，除法的不頻繁使用導致了人們對除法效率的忽略。隨著VLSI技術的發(fā)展，針對各個應用領域的處理器相繼出現(xiàn)，特別是DSP、MMP等專用處理器，這些處理器的應用需求使得除法應用越來越廣泛；而通用處理器中也大部分實現(xiàn)了浮點除法，如AMD－K7、Intel Core i7和Intel Itanium［1］等等。同時，各種應用的處理器對計算速度、芯片面積以及功耗大小的要求也對除法的實現(xiàn)提出了挑戰(zhàn)，因此設計并實現(xiàn)高速低開銷的浮點除法器是十分重要的。

除法算法可以分為三類：查表法、函數(shù)迭代和數(shù)字迭代。查表法使用簡單，當精確度要求不高時可以直接用其得到結果，但對于IEEE－754標準的單精度浮點除法，很難使用查表法直接實現(xiàn)精確的浮點除法。函數(shù)迭代算法包括Newton－Raphson和Goldschmidt算法，這類算法具有收斂速度快的特點，通常與查表法相結合使用來降低迭代次數(shù)。函數(shù)迭代算法每次迭代都涉及到多次乘法操作，所以需要較大的乘法器，面積較大。例如AMD處理器［2］、NVIDIA GPUs［3］、Intel Itanium CPUs［4］及FT－matrix。數(shù)字迭代方法是基本函數(shù)實現(xiàn)中最廣泛的一類算法。它以簡單的加減法和移位操作為基礎，每次迭代獲得固定位數(shù)的商。在目前的處理器中，使用最多的數(shù)字循環(huán)算法是SRT（Sweeney、Robertson以及Tocher）［5］，使用SRT－4算法的處理器有Intel Pentium CPUs［6］、ARM處理器［7］和IBM FPUs［8］；Intel Core2處理器實現(xiàn)SRT－16除法［6］。

本文基于SRT－8除法算法，設計了一種輸入輸出皆符合IEEE－754浮點標準的SIMD（Single Instruction Multiple Data）浮點除法器，支持一個雙精度或兩個并行單精度浮點除法。在深入研究SRT除法算法基礎上，通過優(yōu)化SRT－8迭代除法結構，提出商選擇和余數(shù)加法的并行處理，并采用商數(shù)字存儲技術來降低迭代除法的計算延時，提高頻率。另外，SIMD結構采用復用策略減少硬件資源開銷，節(jié)省面積。

2 SRT算法及基數(shù)選擇

SRT算法基于以下關系式：

其中，Pj＋1是第j次循環(huán)之后的部分余數(shù)；P0為最初的除數(shù)；r是SRT算法的基；d表示被除數(shù)；qj＋1表示第j次循環(huán)得到的商。

SRT算法的關鍵是基數(shù)的大小，它決定了每次循環(huán)可以得到的商的位數(shù)，每次迭代得到的位數(shù)越多則需要迭代的次數(shù)就越少，除法運算所需的周期就越少，從而可提高算法性能。但是，增大基數(shù)會增加設計的硬件復雜度，同時也會增加除法部件的延遲和面積。Oberman S F［1］指出查找商選擇函數(shù)表所需要的時間延遲與基數(shù)成線性增長，而所需要的面積與基數(shù)成二次方增長。文獻［9］通過實驗結果表明，基4優(yōu)化結構比傳統(tǒng)結構減少的時間最短；基8優(yōu)化結構選擇表的查找電路和函數(shù)選擇表輸入值的計算電路相對比較平衡，減少的時間延遲最大；基16實現(xiàn)選擇表輸入值的計算電路過于復雜，減少的時間延遲介于前兩者之間。

商數(shù)字選擇函數(shù)定義如下：

qj＋1＝k∈＋1，…，0，…，a－1，a｝，收斂條件d（k－ρ）≤rPj≤d（k＋ρ），在PD圖中r Pj表示為P，d表示為D，則：

我們取r＝8，a＝5為例，如圖1所示。

Figure 1 Selection of SRT－8 digital quotients圖1 SRT－8除法商數(shù)字選擇圖

從圖1可以看出，相鄰的兩個選擇區(qū)間存在著重疊區(qū)域（圖中陰影部分），重疊區(qū)域的大小由冗余因子ρ和除數(shù)d決定。在重疊區(qū)域［Lk，Uk－1）內，部分商qj＋1可以選取為k或者k－1。所以，在迭代計算中無需知道每次r＊Pj的精確值，且無需進行精確模式下d（k－ρ）≤r＊Pj＜d（k＋ρ）的比較操作。所以，重疊區(qū)間的存在簡化了商數(shù)字選擇函數(shù)的復雜性，只需知道部分余數(shù)r＊Pj的前幾位和除數(shù)d的前幾位就可以選擇出商數(shù)字qj＋1，從而提高其運算效率。并且，重疊區(qū)間越大，比較操作中所需要的精度越小，因此，冗余度越高，商選擇函數(shù)的邏輯復雜度越低。

3 總體結構設計

本文設計的SIMD浮點除法器總體結構如圖2所示。

SIMD浮點除法器支持一個IEEE－754標準雙精度浮點除法或兩個并行單精度浮點除法，主要包括三個執(zhí)行站：

E1站：數(shù)據(jù)輸入及預處理。在E1級接收以IEEE－754標準表示的被除數(shù)與除數(shù)，并解析這兩個輸入操作數(shù)，以分離出尾數(shù)與指數(shù)；運算前調整模塊整合了尾數(shù)調整與指數(shù)調整的功能，其主要作用是將操作數(shù)調整為SRT－8運算單元所要求的格式與精度。

E2站：SRT－8迭代除法計算。在E2級設計控制與計數(shù)模塊，主要負責雙、單精度的除法迭代計數(shù)（分別迭代18次和9次）以及異常處理與匯報。該模塊實現(xiàn)了一個簡單的狀態(tài)機，是運算單元的直接管理中心。SRT－8運算單元是運算核心所在，其性能決定了整個設計的運算速度，所以本文對該模塊進行了充分的優(yōu)化。

E3站：規(guī)格化。在E3級后規(guī)格化模塊將尾數(shù)除結果與指數(shù)減結果按IEEE－754浮點標準執(zhí)行規(guī)格化操作，另外還包括例外數(shù)據(jù)判斷。

所設計的SIMD主體結構是在經(jīng)典低延遲64位雙精度浮點除法基礎上進行改進，充分利用硬件復用，包括商數(shù)字選擇邏輯、余數(shù)產(chǎn)生57位并列加法器、尾數(shù)舍入規(guī)格化等復用邏輯，相比經(jīng)典低延遲結構，面積增加較小，能實現(xiàn)雙精度浮點除法和兩個并行的單精度浮點除法。

4 優(yōu)化設計策略

兩個浮點數(shù)據(jù)相除，被除數(shù)與除數(shù)的符號位進行異或運算得到結果的符號位；被除數(shù)的指數(shù)減去除數(shù)的指數(shù)得到中間指數(shù)結果PreEXP；被除數(shù)與除數(shù)的尾數(shù)部分進行定點除運算，定點除法使用SRT－8除法算法。

在傳統(tǒng)SRT－8除法迭代計算實現(xiàn)中，如圖3所示，每一次SRT－8迭代涉及的運算有：

（1）部分余數(shù)Pj經(jīng)過移位器左移三位生成8＊Pj；

（2）然后以8＊Pj和d為輸入，經(jīng)商選擇邏輯查表得到該次循環(huán)的商qj＋1；

（3）通過qj＋1選擇乘積值F＝－qj＋1＊d；

（4）最后通過加法器運算得到下一次循環(huán)的部分余數(shù)Pj＋1。

Figure 2 Overall structure of SIMD floating－point division圖2 SIMD浮點除法器總體結構

Figure 3 Traditional implementation of SRT－8 division’s iteration圖3 傳統(tǒng)SRT－8除法迭代實現(xiàn)

4.1 商選擇函數(shù)

依據(jù)上述SRT－8算法分析，商選擇函數(shù)部件位于算法設計的關鍵路徑上，該部分實現(xiàn)會影響到整個設計的時間延遲。在SRT－8算法中采用了冗余的商數(shù)字集，只需要知道部分余數(shù)值范圍就可以決定本次商的結果。所以，只需要部分余數(shù)的前幾位數(shù)值就可以得到本次循環(huán)的結果（如圖4）。采用這種方法可以在降低時間延遲的同時，減少商選擇函數(shù)硬件實現(xiàn)的復雜度。

Figure 4 Selective function of digital quotients圖4 商數(shù)字選擇函數(shù)

首先將除數(shù)d∈［1，2）劃分成長度為2－δ的小區(qū)間［di，di＋1），且d1＝1/2，di＋1＝di＋2－δ。這樣，區(qū)間就用除數(shù)的前δ位小數(shù)和一位整數(shù)“1”來表示。在小區(qū)間［di，di＋1）里，qj＋1＝k，如果mk（i）≤r Pj＜mk＋1（i），選擇常數(shù)mk定義如下：

設選擇常數(shù)mk的最小長度為2－C，則：

其中，Ak（i）為整數(shù)。

最壞情況下，k＝a，d＝1，可推導出：

得出δ的下界后，通過表1可以得出δ＋C的最小值。

Table 1 Boundaries of r＊Pj表1 r＊Pj的界限（/7）

取δ＝4，此時C＝3，δ＋C取最小值7。

4.2 SRT－8迭代單元設計

從圖3可以得出，關鍵路徑主要在于商數(shù)字選擇函數(shù)查找表的延遲和57位全加器的延遲，如果這兩個邏輯能夠并行執(zhí)行，延遲將會得到大大改觀。因此，我們對以上方式進行改進，如圖5虛線框所示。首先由五個加法器計算所有可能的部分余數(shù)（其中3d和5d分別分解為（d＋2d）和（d＋4d），并且通過進位節(jié)省加法器CSA3－2來加速運算），與此同時，以8＊Pj和d為輸入，經(jīng)商選擇邏輯查表得到該次循環(huán)的商qj＋1；然后再通過qj＋1選擇余數(shù)Pj＋1。

Figure 5 Parallel iteration of SRT－8（1）圖5 SRT－8并行迭代（改進1）

通過改進1，關鍵路徑中的商數(shù)字選擇延時被虛線框內的加法器掩蓋。

SRT－8迭代改進2如圖6所示，對于3d和5d，事先用加法器把結果計算出來并儲存，這樣迭代延遲（虛線框內）將會減少一級CSA3－2壓縮的時間，從而提高系統(tǒng)頻率。

Figure 6 Parallel iteration of SRT－8（2）圖6 3d和5d預先計算SRT－8并行迭代（改進2）

4.3 SIMD結構設計

SIMD數(shù)據(jù)通路結構主要由三個部分組成：數(shù)據(jù)準備（Data Prepare）、迭代計算模塊和數(shù)據(jù)儲存（Data Save），如圖7所示。

Figure 7 Structure of SIMD division’s iteration圖7 SIMD除法迭代結構

數(shù)據(jù)準備模塊主要負責余數(shù)和除數(shù)加減前的數(shù)據(jù)準備。當為雙精度除法時，若余數(shù)符號位為0，則余數(shù)減去F，余數(shù)末位設為1（因為通過左移，余數(shù)末端三位全為0），除數(shù)求反；若余數(shù)符號位為1，則余數(shù)加上F。當為SIMD雙單精度除法時，若高28位余數(shù)2符號位為0，則余數(shù)2減去F2，余數(shù)2末位設為1，28位除數(shù)2求反，否則余數(shù)2和除數(shù)2均不變；若低28位余數(shù)1符號位為0，則余數(shù)1減去F1，余數(shù)1末位設為1，28位除數(shù)1求反，否則余數(shù)1和除數(shù)1均不變。在計算SIMD雙單精度除法時，余數(shù)和除數(shù)的中間位設為0。

迭代計算模塊復用商數(shù)字選擇部件1，求雙精度尾數(shù)除法每次迭代商數(shù)字和單精度1尾數(shù)除法每次迭代商數(shù)字，增加商數(shù)字選擇部件1，求單精度2尾數(shù)除法每次迭代商數(shù)字；復用57位并列加法器1/2/3/4/5，求雙精度尾數(shù)除法每次迭代后的余數(shù)和兩個并列單精度1、單精度2尾數(shù)除法每次迭代后的余數(shù)。

數(shù)據(jù)儲存模塊是每次迭代后余數(shù)和商結果的數(shù)據(jù)保存。余數(shù)的存儲包括通過商qj＋1來選擇余數(shù)Pj＋1以及余數(shù)通過移位器左移三位，以便于下次迭代運算；商的存儲主要運用了商數(shù)字轉換技術（詳細見4.4節(jié)）。

4.4 商數(shù)字存儲

由于在迭代中計算結果是用冗余數(shù)表示，需要將其轉換為非冗余二進制形式。最直接的辦法是將冗余數(shù)分為正數(shù)位和負數(shù)位兩部分，再將其相加可得非冗余的二進制數(shù)。但是，這樣做增加了控制的復雜度和迭代時間。

在SRT算法中應用商數(shù)字的存儲技術，在每次迭代中將商數(shù)字分別存入兩個單獨的寄存器Q與QM。其中，q表示第j次迭代產(chǎn)生的以二進制補碼形式表示的商值。每次迭代的結尾，商數(shù)字選擇函數(shù)產(chǎn)生q后，寄存器Q與QM被刷新，如表2所示。

Table 2 Storage of digital quotients表2 商數(shù)字存儲

可見，其中不存在算術操作，且無進位/借位的傳遞問題。在除法運算的最后一步迭代完成后，二進制補碼形式表示的商值即保存在Q寄存器中。

5 驗證與性能評估

5.1 驗證流程與結果

從下列角度對SIMD浮點除法部件進行全面驗證，如圖8所示。

（1）功能驗證完備性。主要測試RTL代碼的功能正確性，驗證了IEEE－754標準中的各種浮點數(shù)異常和溢出處理。異常的處理主要是除數(shù)為0、Den，無窮大除以無窮大和無效數(shù)；溢出的處理是指數(shù)上溢與指數(shù)下溢。

Figure 8 Flow chart of verification圖8 驗證流圖

（2）數(shù)據(jù)驗證完備性。采用隨機數(shù)驗證方法對雙精度除法和兩個并行單精度除法均測試了300萬組隨機數(shù)據(jù)，并將執(zhí)行結果與對應的C黃金模型模擬作比較，結果表明實現(xiàn)SIMD浮點除法器的功能正確。

（3）系統(tǒng)驗證完備性。在模擬環(huán)境下搭建好DSP內核平臺，在此基礎上對RTL代碼進行了系統(tǒng)級仿真，聯(lián)合其它部件在DSP內核下測試一些典型算法大程序的運行結果，與模擬器仿真硬件執(zhí)行作比較，驗證結果顯示正確，符合設計要求。

本文對所設計的浮點除法部件進行了代碼覆蓋率分析。為了得到代碼覆蓋率，需要對源代碼進行分解，分解的過程就是在源代碼的關鍵位增加斷點，記錄該位置是否存在特殊結構，然后用驗證平臺來對這些分解的代碼進行模擬，得到覆蓋率信息。經(jīng)過對未覆蓋到的代碼進行審查和增加測試激勵，使代碼覆蓋率達到100%。

5.2 性能分析與評估

基于40 nm標準單元庫在“Typical”典型常溫常壓（1 V，25°C）綜合條件下對SIMD浮點除法器實現(xiàn)進行綜合，邏輯優(yōu)化后的綜合結果如表3所示。選取時序約束時鐘周期400 ps，其中設置第一站（E1）的輸入延時為100 ps，以用于數(shù)據(jù)讀取，第三站（E3）增加了50 ps的輸出延遲，用于數(shù)據(jù)寫回，兩個模塊在關鍵路徑延遲設計上相對于E2站要短一些，使得各站之間延遲均勻。除法器綜合運行頻率可達2.5 GHz，綜合cell面積為18 601.968 1μm2。

Table 3 Synthesized results of the division表3 除法器綜合結果

綜合優(yōu)化結果與圖3經(jīng)典的SRT－8結構、文獻［9］采用由SRT－4和SRT－2重疊組成的結構（不復用結構，實現(xiàn)雙精度浮點除法和雙單精度浮點除法）在相同工藝、相同綜合條件下的綜合結果比較如表4所示。面積為經(jīng)典SRT－8結構的91.79%、文獻［9］結構的69.57%；關鍵路徑為經(jīng)典SRT－8結構的76.19%、文獻［9］結構的98.03%。性能提升來自以下技術：商選擇和余數(shù)加法的并行處理技術降低了計算延時；商數(shù)字存儲技術有效降低了存儲商延遲。采用商選擇和余數(shù)加法的并行處理技術，雖然增加了四個并行的57位全加器，但是商數(shù)字存儲技術，卻減少了一個57位和兩個30位全加器。SIMD結構采用復用策略，如圖7所示，復用商數(shù)字選擇部件1，復用57位并列加法器1/2/3/4/5，有效地減少了硬件開銷。

Table 4 Comparison of divisions’synthesized results表4 除法器綜合結果比較

6 結束語

本文設計實現(xiàn)了一個支持雙精度和兩個單精度的SIMD浮點除法部件。本設計改進了SRT－8迭代結構，并運用商數(shù)字存儲技術，加速了除法運算速度。采用了SIMD結構，能夠并行計算兩個單精度浮點除法。復用了硬件資源，減少了資源開銷，節(jié)省了整體的面積。本文從子系統(tǒng)級驗證完整、功能驗證完全和數(shù)據(jù)驗證完備的角度出發(fā)，對運算單元進行了功能驗證，在驗證過程中進行了代碼覆蓋率分析，使代碼覆蓋率達到100%。綜合結果表明，40 nm工藝庫下，綜合cell面積為18 601.968 1μm2，綜合運行頻率可達2.5 GHz。相對傳統(tǒng)SRT－8結構，面積減少8.21%，同時關鍵路徑僅為傳統(tǒng)SRT－8結構的76.19%。相對文獻［9］的結構，性能提高1.97%，同時硬件面積僅為文獻［9］結構的69.57%。

［1］ Oberman S F，F(xiàn)lynn M.Design issues in division and other floating－point operations［J］.IEEE Transactions on Computers，1997，46（2）：154－161.

［2］ Oberman S F.Floating－point division and square root algorithms and implementation in the AMD－K7 microprocessor［C］∥Proc of the 14th Symposium on Computer Arithmetic，1999：106－115.

［3］ NVIDIA.Fermi：NVIDIA’s next generation CUDA compute architecture［EB/OL］.［2009－10－10］.http：∥www.nvidia.com/content/PDF/fermi＿white＿papers/NVIDIA＿Fermi＿Compute＿Architecture＿Whitepaper.pdf.

［4］ Sharangpani H，Arora H.Itanium processor micro－architecture［J］.IEEE Micro，2000，20（5）：24－43.

［5］ Wang Xian，Ni Xiao－qiang，Xing Zuo－cheng.The analysis and research of floating－point division［C］∥Proc of the Computer Project and Craftwork，2008：282－283.（in Chinese）

［6］ Baliga H，Cooray N，Gamsaragan E，et al.Improvements in the Intel Core2 Penryn processor family architecture and microarchitecture［J］.Intel Technology Journal，2008，12（3）：179－192.

［7］ Burgess N，Hinds C N.Design of the ARM VFP11 divide and square root synthesisable macrocell［C］∥Proc of the 18th IEEE Symposim on Computer Arithmetic，2007：87－96.

［8］ Gerwig G，Wetter H，Schwarz E M，et al.High performance floating－point unit with 116 bit wide divider［C］∥Proc of the 16th Symposim on Computer Arithmetic，2003：87－94.

［9］ Liu Hua－ping.Research on high－performance arithmetic for floating－point division and the elementary functions［D］.Beijing：Institute of Computing Technology，Chinese Academy of Science，2003.（in Chinese）

［10］ Liu W，Nannarelli A.Power efficient division square root unit［J］.IEEE Transactions on Computers，2012，61（8）：1059－1070.

［11］ Harris D L，Oberman S F，Horowirtz M A.SRT division architectures and implementations［C］∥Proc of the 13th IEEE Symposium，1997：18－25.

［12］ Fandrianto J.Algorithm for high－speed shared radix－4 division and radix－4 square－root［C］∥Proc of the 8th IEEE Symposium on Computer Arithmetic，1987：73－79.

［13］ Wang Wen－guang.Design and implementation of double precision 64－bits floating－point division［D］.Changsha：Central South University，2007.（in Chinese）

附中文參考文獻：

［5］ 王縣，倪曉強，邢座程.浮點除法算法的分析與研究［C］∥計算機工程與工藝，2008：282－283.

［9］ 劉華平.高性能浮點除法及基本函數(shù)功能部件的研究［D］.北京：中國科學院計算技術研究所，2003.

［13］ 王文廣.雙精度64位浮點除法運算單元的設計與實現(xiàn)［D］.長沙：中南大學，2007.