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

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

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

1 引言

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

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

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

2 SRT算法及基數選擇

SRT算法基于以下關系式：

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

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

商數字選擇函數定義如下：

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除法商數字選擇圖

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

3 總體結構設計

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

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

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

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

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

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

4 優化設計策略

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

在傳統SRT－8除法迭代計算實現中，如圖3所示，每一次SRT－8迭代涉及的運算有：

（1）部分余數Pj經過移位器左移三位生成8＊Pj；

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

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

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

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

Figure 3 Traditional implementation of SRT－8 division’s iteration圖3 傳統SRT－8除法迭代實現

4.1 商選擇函數

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

Figure 4 Selective function of digital quotients圖4 商數字選擇函數

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

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

其中，Ak（i）為整數。

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

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

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

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

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

4.3 SIMD結構設計

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

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

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

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

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

4.4 商數字存儲

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

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

Table 2 Storage of digital quotients表2 商數字存儲

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

5 驗證與性能評估

5.1 驗證流程與結果

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

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

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

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

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

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

5.2 性能分析與評估

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

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

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

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

6 結束語

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

［1］ Oberman S F，Flynn 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］ 劉華平.高性能浮點除法及基本函數功能部件的研究［D］.北京：中國科學院計算技術研究所，2003.

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