流水的浮點(diǎn)倒數(shù)近似值運(yùn)算部件的設(shè)計(jì)與實(shí)現(xiàn)*

何 軍，王 麗

(上海高性能集成電路設(shè)計(jì)中心， 上海 201204)

浮點(diǎn)運(yùn)算部件是微處理器的重要運(yùn)算部件，與處理器的性能直接相關(guān)。常見的浮點(diǎn)運(yùn)算包括浮點(diǎn)加、減、乘、乘加等。這些浮點(diǎn)運(yùn)算在傳統(tǒng)的科學(xué)計(jì)算和工程計(jì)算應(yīng)用領(lǐng)域中應(yīng)用十分廣泛。相對(duì)于這些常見的浮點(diǎn)運(yùn)算，浮點(diǎn)倒數(shù)運(yùn)算并不很常用，但是在數(shù)字信號(hào)處理、多媒體、計(jì)算機(jī)圖形計(jì)算等應(yīng)用領(lǐng)域，以及部分科學(xué)計(jì)算應(yīng)用領(lǐng)域，卻比較常用，也是一種重要的運(yùn)算[1]。此外，利用浮點(diǎn)倒數(shù)運(yùn)算，還可以實(shí)現(xiàn)浮點(diǎn)除法運(yùn)算。

常用的實(shí)現(xiàn)浮點(diǎn)倒數(shù)運(yùn)算的算法與浮點(diǎn)除法類似，有基于減法運(yùn)算的數(shù)字迭代算法[2]、SRT算法[3-4]，也有基于乘法運(yùn)算的Newton-Raphson算法和Goldschmidt算法[5-6]。基于這些算法，如果要實(shí)現(xiàn)浮點(diǎn)單精度或雙精度浮點(diǎn)倒數(shù)運(yùn)算，為了減少硬件開銷，一般都是采用非流水的硬件迭代方法實(shí)現(xiàn)。其中基于減法的迭代算法是線性收斂的，每次可以迭代出1(基數(shù)為2)、2(基數(shù)為4)、3(基數(shù)為8)位結(jié)果，硬件開銷小?；诔朔ǖ牡惴ㄊ嵌问諗康模看蔚蠼Y(jié)果的精度翻倍，硬件開銷大。

但在有的應(yīng)用中，其實(shí)并不需要非流水的全精度的浮點(diǎn)倒數(shù)運(yùn)算，而是能流水的部分精度(比如6～10位有效尾數(shù))的浮點(diǎn)倒數(shù)近似值運(yùn)算。再利用流水的快速浮點(diǎn)乘法運(yùn)算，軟件實(shí)現(xiàn)Newton-Raphson算法和Goldschmidt算法，就可以更高效地流水地實(shí)現(xiàn)任意精度的浮點(diǎn)除法運(yùn)算等其他運(yùn)算。這種方法尤其適用于低精度浮點(diǎn)運(yùn)算應(yīng)用。以單精度浮點(diǎn)(24位尾數(shù)，含隱含位)除法運(yùn)算為例，目前硬件非流水實(shí)現(xiàn)，需要17拍。假設(shè)利用流水的浮點(diǎn)倒數(shù)近似值運(yùn)算，得到8位精度尾數(shù)需要6拍，再加上一次乘法運(yùn)算(6拍流水執(zhí)行)，如果低精度應(yīng)用只需要8位精度即可，則一次除法只需要12拍，且可流水執(zhí)行。假設(shè)有n次這樣的除法運(yùn)算，使用非流水硬件實(shí)現(xiàn)，需要17n拍，利用流水的浮點(diǎn)倒數(shù)近似值運(yùn)算加乘法運(yùn)算實(shí)現(xiàn)，只需要12+n-1拍。當(dāng)n越大時(shí)，流水硬件實(shí)現(xiàn)延遲更短。

因此，綜合考慮運(yùn)算延遲和硬件開銷，采用基數(shù)為4的SRT算法[7-9](簡稱“SRT-4算法”)設(shè)計(jì)并實(shí)現(xiàn)了一種浮點(diǎn)倒數(shù)近似值運(yùn)算部件(簡稱“FREC部件”)，6級(jí)流水線結(jié)構(gòu)，運(yùn)算結(jié)果精度至少為8位有效尾數(shù)。為了硬件支持浮點(diǎn)非規(guī)格化浮點(diǎn)數(shù)[10-11]，經(jīng)過進(jìn)一步改進(jìn)，增加源操作數(shù)預(yù)規(guī)格化和結(jié)果后規(guī)格化功能，可以實(shí)現(xiàn)對(duì)浮點(diǎn)非規(guī)格化浮點(diǎn)數(shù)的硬件處理，有利于進(jìn)一步提高浮點(diǎn)倒數(shù)近似值運(yùn)算的性能[12]。

1 設(shè)計(jì)與實(shí)現(xiàn)

1.1 SRT-4算法

基本的SRT算法迭代過程采用數(shù)學(xué)公式描述如下(其中，X為被除數(shù)，D為除數(shù)，R為算法的基數(shù))：

RP0=X

Pi+1=RPi-qi+1D

(1)

這里Pi是第i次迭代后的部分余數(shù)，在每次迭代中，商值qi+1由商值選擇函數(shù)δ決定：qi+1=δ(RPi，D)，經(jīng)k次迭代后最后的商Q和余數(shù)Pr(Pk為k次迭代后的部分余數(shù))分別為：

(2)

具體實(shí)現(xiàn)時(shí)，SRT算法步驟如下：

1)將部分余數(shù)的初始值設(shè)為被除數(shù)X，在第i步，通過將除數(shù)D與當(dāng)前部分余數(shù)比較，選擇下一位商數(shù)qi+1(由商值選擇函數(shù)δ決定)；

2)按照遞推式(1)計(jì)算出下一個(gè)部分余數(shù)Pi+1；

3)按照前兩步，經(jīng)k次迭代后，將所得的商數(shù)加權(quán)求和就得到最終的商Q，見式(2)。

一般基數(shù)R=2n，每次迭代可以得到的n位數(shù)商數(shù)。需要迭代的次數(shù)k與需要得到的結(jié)果精度有關(guān)。當(dāng)R=4時(shí)，每次迭代可以得到2位商數(shù)；對(duì)于單精度浮點(diǎn)數(shù)，k=12，對(duì)于雙精度浮點(diǎn)數(shù)，k=27。

商值選擇函數(shù)δ是SRT算法的關(guān)鍵部分，一般采用查詢表的方式實(shí)現(xiàn)，即根據(jù)部分余數(shù)和除數(shù)的高若干位查表得到商。對(duì)于SRT-4算法，商數(shù)集合為{-2,-1,0,+1,+2}，可以采用表1所示的查詢表[13]，利用部分余數(shù)的高7位和除數(shù)的高4位(由于規(guī)格化的除數(shù)整數(shù)部分默認(rèn)為1，因此這里的高4位實(shí)際是尾數(shù)的高4位)查表，即可得到商數(shù)。

表1 SRT-4商值查詢表[13]Tab.1 The SRT-4 quotient look-up table[13]

表1(續(xù))

為了減少延遲，部分余數(shù)一般采用保留進(jìn)位(carry save)的冗余形式保存在兩個(gè)寄存器Carry和Sum中，避免迭代過程中的進(jìn)位加法運(yùn)算。所以在查表前，需要一個(gè)普通的7位進(jìn)位傳遞加法器(Carry Propagate Adder, CPA)，得到實(shí)際的部分余數(shù)，然后再查表，得到商數(shù)，如圖1所示。

圖1 SRT-4商值選擇函數(shù)的實(shí)現(xiàn)Fig.1 Implement of SRT-4 quotient selection function

圖2 SRT-4算法迭代部分原理圖Fig.2 Schematic diagram of iterative part of SRT-4 algorithm

對(duì)于一次SRT-4迭代來說，其實(shí)現(xiàn)原理如圖2所示。查表得到的商數(shù)q采用3位編碼表示。根據(jù)商數(shù)q，選擇得到多倍除數(shù)，并利用進(jìn)位保留加法器(CSA3B2)得到更新后的部分余數(shù)Carry和Sum；同時(shí)并行得到最新的商。這里商也采用了冗余形式保存在兩個(gè)寄存器Q和Qm中，兩者始終相差1，即Qm=Q-1。利用飛速轉(zhuǎn)換(on-the-fly)技術(shù)[14]，每得到商數(shù)q，就對(duì)當(dāng)前的寄存器Q和Qm值進(jìn)行更新，得到新的商。其轉(zhuǎn)換表參見表 2，由SRT4_QQM模塊實(shí)現(xiàn)。

表2 SRT-4飛速轉(zhuǎn)換Tab.2 The SRT-4 on-the-fly conversion

注：1)對(duì)于浮點(diǎn)倒數(shù)近似值運(yùn)算，只需要保留10位商即可。

2){Q[7∶0],2′b00}是按位拼接運(yùn)算，2′b00表示2位二進(jìn)制數(shù)，下同。

1.2 FREC部件結(jié)構(gòu)

FREC部件采用了SRT-4算法，為了得到至少8位有效尾數(shù)精度，考慮到首次商的最高位可能為0，因此需要經(jīng)過5次迭代，得到10位有效尾數(shù)。FREC部件結(jié)構(gòu)如圖3所示。采用全流水實(shí)現(xiàn)，執(zhí)行延遲為6拍，前5拍(ST0～ST4)分別進(jìn)行5次SRT-4迭代(流水進(jìn)行)，最后一拍(ST5)進(jìn)行結(jié)果輸出處理。與其他浮點(diǎn)運(yùn)算一樣，實(shí)際包括兩條數(shù)據(jù)通路，分別進(jìn)行輸入異常數(shù)據(jù)和正常數(shù)據(jù)的處理，最后兩條通路數(shù)據(jù)二選一輸出(輸入異常優(yōu)先)。其中F_REC_EXCEP模塊進(jìn)行輸入異常數(shù)據(jù)處理，主要進(jìn)行無效操作(INV)、除數(shù)為零(DBZ)、非規(guī)格化浮點(diǎn)數(shù)(DNO)三種輸入異常檢測(cè)和處理。F_REC_EXP模塊主要進(jìn)行階碼計(jì)算，并檢測(cè)是否發(fā)生上、下溢出異常。

第一次迭代時(shí)，商值寄存器Q、Qm初始化為0，部分余數(shù)寄存器Carry初始化為0，部分余數(shù)寄存器Sum初始化為浮點(diǎn)數(shù)1.0(即0×3ff0_0000_0000_0000)規(guī)格化的尾數(shù)Sum_norm，除數(shù)寄存器Divisor初始化為規(guī)格化的除數(shù)尾數(shù)Divisor_norm，這里：

1)Sum_norm={3′b000,1′b1,52′b0,1′b0}，即浮點(diǎn)數(shù)1.0的尾數(shù)；

2)Divisor_norm={2′b00,1′b1,Divisor[51:0],2′b00}。

結(jié)果輸出處理主要完成如下功能：

1)利用普通加法器計(jì)算出實(shí)際的余數(shù)，根據(jù)余數(shù)判斷是否發(fā)生非精確結(jié)果異常，并根據(jù)余數(shù)的符號(hào)決定是否需要恢復(fù)余數(shù)(再加上除數(shù)即可)，并選擇Q、Qm之一為最終的商。

2)根據(jù)商的最高位是否為0，決定是否需要將商進(jìn)行再規(guī)格化(左移1位)，同時(shí)將結(jié)果的階碼減1，得到正常數(shù)據(jù)通路的結(jié)果。

3)再跟輸入異常處理通路的結(jié)果二選一輸出(輸入異常結(jié)果優(yōu)先)，作為最終的結(jié)果。

由于是求浮點(diǎn)倒數(shù)的近似值，為了簡化硬件設(shè)計(jì)，僅支持向零舍入(即截?cái)嗌崛?模式。

1.3 硬件支持非規(guī)格化浮點(diǎn)數(shù)的改進(jìn)

根據(jù)IEEE-754標(biāo)準(zhǔn)[15]，規(guī)格化浮點(diǎn)數(shù)X=(s,e,f)形式化表示如下：

X=(-1)s×2e-bias×(1.f)

這里，0

圖3 FREC部件結(jié)構(gòu)Fig.3 Implementation of FREC unit

非規(guī)格化浮點(diǎn)數(shù)X=(s,e,f)形式化表示如下：

X=(-1)s×21-bias×(0.f)

這里，e=0，f≠0。兩者可統(tǒng)一表示為：

X=(-1)s×2e+～x0-bias×(x0+0.f)

這里x0為尾數(shù)部分隱含整數(shù)位，對(duì)于規(guī)格化浮點(diǎn)數(shù)，其取值為1；對(duì)于非規(guī)格化浮點(diǎn)數(shù)，其取值為0。～x0表示x0取反。

一般浮點(diǎn)硬件僅支持規(guī)格化浮點(diǎn)數(shù)的運(yùn)算，如果需要支持對(duì)非規(guī)格化浮點(diǎn)數(shù)的運(yùn)算，需要進(jìn)行特殊處理[10-11]：

1)對(duì)輸入的非規(guī)格化浮點(diǎn)數(shù)要進(jìn)行預(yù)規(guī)格化(pre-normalization)處理，檢測(cè)尾數(shù)頭1的位置，然后將尾數(shù)左移，直到最高位為1，同時(shí)減少階碼；

2)當(dāng)運(yùn)算結(jié)果為非規(guī)格化浮點(diǎn)數(shù)時(shí)，需要進(jìn)行后規(guī)格化(post-normalization)處理，常規(guī)的浮點(diǎn)運(yùn)算需要對(duì)結(jié)果的尾數(shù)進(jìn)行規(guī)格化左移，直到最高位是1為止。但是，如果發(fā)現(xiàn)此時(shí)的階碼出現(xiàn)了下溢(即小于最小階碼emin)還需要再右移尾數(shù)，并增加階碼，直到階碼等于emin。

1.3.1 源操作數(shù)預(yù)規(guī)格化

對(duì)非規(guī)格化浮點(diǎn)數(shù)的尾數(shù)(包括隱含的整數(shù)部分)進(jìn)行頭零檢測(cè)(Leading Zero Detection，LZD)，假定頭零個(gè)數(shù)為m(規(guī)格化數(shù)m=0，非規(guī)格化數(shù)m>0)，將尾數(shù)左移m位，保證尾數(shù)最高位為1。非規(guī)格化浮點(diǎn)操作數(shù)階碼為0，而實(shí)際的階碼是1，調(diào)整后的階碼為(1-m)。對(duì)于規(guī)格化浮點(diǎn)數(shù)，不需要進(jìn)行預(yù)規(guī)格化，直接進(jìn)行運(yùn)算即可(參見圖 4)。

圖4 源操作數(shù)預(yù)規(guī)格化Fig.4 Source operand pre-normalization

1.3.2 結(jié)果后規(guī)格化

經(jīng)過預(yù)規(guī)格化，非規(guī)格化浮點(diǎn)數(shù)的運(yùn)算結(jié)果的尾數(shù)與規(guī)格化浮點(diǎn)數(shù)一樣，頭0的個(gè)數(shù)最多為1，只需要規(guī)格化左移1位，同時(shí)將結(jié)果的階碼減1，即可得到最終的尾數(shù)fr和階碼er。這里er可能小于等于emin，即結(jié)果發(fā)生了下溢，可能是非規(guī)格化浮點(diǎn)數(shù)。

為了得到非規(guī)格化浮點(diǎn)數(shù)結(jié)果，需要對(duì)結(jié)果進(jìn)行后規(guī)格化，即將結(jié)果的尾數(shù)右移，同時(shí)增加結(jié)果的階碼，直到階碼等于emin。不妨設(shè)假定n=emin-er(er≤emin)，p為浮點(diǎn)尾數(shù)有效位寬(對(duì)于單精度浮點(diǎn)數(shù)p=23，對(duì)于雙精度浮點(diǎn)數(shù)p=52，對(duì)于這里倒數(shù)近似值運(yùn)算來說，實(shí)際p=9)，反規(guī)格化右移位數(shù)y與結(jié)果尾數(shù)的精度p有關(guān)：

1)若n<(p+1)，則y=n(當(dāng)n為0時(shí)無須右移)；

2)若n≥(p+1)，則y=p+1(此時(shí)如果再繼續(xù)右移，實(shí)際上結(jié)果的尾數(shù)已經(jīng)為0，不必再右移了)。

當(dāng)右移位數(shù)超出精度p+1，導(dǎo)致移位后有效尾數(shù)為0，此時(shí)階碼也應(yīng)為0，即最終結(jié)果為0。當(dāng)結(jié)果為非規(guī)格化浮點(diǎn)數(shù)時(shí)，也屬于發(fā)生下溢，會(huì)報(bào)告下溢異常。結(jié)果后規(guī)格化功能的實(shí)現(xiàn)參見圖5。

圖5 結(jié)果后規(guī)格化Fig.5 Result post-normalization

為了硬件支持非規(guī)格化浮點(diǎn)數(shù)處理，在FREC部件正常運(yùn)算通路開始之前對(duì)源操作數(shù)進(jìn)行預(yù)規(guī)格化(需要增加1拍)，在結(jié)果輸出處理模塊之前，增加結(jié)果后規(guī)格化(也需要增加1拍)，最終FREC部件新增2級(jí)流水線，執(zhí)行延遲變?yōu)?拍。

此外，對(duì)輸入異常數(shù)據(jù)處理模塊F_REC_EXCEP也進(jìn)行了適當(dāng)修改，不再把非規(guī)格化浮點(diǎn)數(shù)直接當(dāng)同符號(hào)的0進(jìn)行處理。

2 正確性驗(yàn)證與邏輯綜合

浮點(diǎn)倒數(shù)近似值運(yùn)算的正確性驗(yàn)證，是以已經(jīng)驗(yàn)證正確的浮點(diǎn)除法為參考模型，將被除數(shù)固定為浮點(diǎn)數(shù)1.0，除數(shù)與倒數(shù)運(yùn)算的源操作數(shù)相同，然后截取除法結(jié)果的高8位有效尾數(shù)進(jìn)行驗(yàn)證。源操作數(shù)采用浮點(diǎn)典型特殊值和隨機(jī)值相結(jié)合的方法，進(jìn)行大量模擬驗(yàn)證。此外，針對(duì)算法實(shí)現(xiàn)撰寫了功能點(diǎn)，功能覆蓋率可達(dá)到100%。還進(jìn)行了代碼覆蓋率分析，也可達(dá)到接近100%(部分底層公共子模塊存在覆蓋不到的情況，也進(jìn)行了確認(rèn))。結(jié)果表明，浮點(diǎn)倒數(shù)近似值運(yùn)算部件的功能是正確的，結(jié)果的精度也符合預(yù)期。

利用Synopsys的Design Compiler工具，基于16/14 nm工藝條件，對(duì)FREC部件的Verilog設(shè)計(jì)代碼進(jìn)行了邏輯綜合，包括硬件支持非規(guī)格化浮點(diǎn)數(shù)的改進(jìn)版(FREC2)。邏輯綜合的約束條件相同，時(shí)鐘頻率均為1.6 GHz，兩個(gè)版本均能滿足頻率設(shè)計(jì)目標(biāo)，但是改進(jìn)版有一定的面積和功耗開銷，綜合結(jié)果參見表3。

表3 邏輯綜合結(jié)果Tab.3 Logic synthesis result

增加的面積主要為：源操作數(shù)預(yù)規(guī)格化中頭零檢測(cè)和左移移位器，結(jié)果后規(guī)格化中的右移移位器。增加的面積開銷在合理范圍內(nèi)，主要是對(duì)時(shí)序沒有影響，可以滿足頻率設(shè)計(jì)目標(biāo)。

3 結(jié)論

基于SRT-4算法，本文設(shè)計(jì)并實(shí)現(xiàn)了一種流水的FREC部件，6級(jí)流水線，支持浮點(diǎn)倒數(shù)流水運(yùn)算，結(jié)果精度至少8位有效尾數(shù)?；谠摬考?，利用流水的快速浮點(diǎn)乘法運(yùn)算，軟件基于Newton-Raphson算法和Goldschmidt算法，可以更高效地流水實(shí)現(xiàn)任意精度的浮點(diǎn)除法運(yùn)算等其他運(yùn)算。這種方法尤其適用于低精度浮點(diǎn)運(yùn)算應(yīng)用。

本文還設(shè)計(jì)并實(shí)現(xiàn)了改進(jìn)版的FREC部件，增加源操作數(shù)預(yù)規(guī)格化和結(jié)果后規(guī)格化功能模塊，可以實(shí)現(xiàn)對(duì)浮點(diǎn)非規(guī)格化浮點(diǎn)數(shù)的硬件處理，有利于進(jìn)一步提高浮點(diǎn)倒數(shù)近似值運(yùn)算的性能。改進(jìn)版的FREC部件采用8級(jí)流水線結(jié)構(gòu)，由于支持流水操作，增加了2級(jí)流水線對(duì)運(yùn)算性能的影響很小。經(jīng)過邏輯綜合評(píng)估，改進(jìn)版的FREC部件硬件開銷是面積增加19.23%。增加的面積開銷在合理范圍內(nèi)，且對(duì)時(shí)序沒有明顯影響，可以滿足預(yù)期的1.6 GHz頻率設(shè)計(jì)目標(biāo)。