焦永

摘要：單精度浮點倒數(shù)開方運算在GPU設(shè)計中經(jīng)常會用到。實現(xiàn)這種運算一般有兩種方法，迭代法和查表法。迭代法要根據(jù)精度要求確定迭代次數(shù)，只需要很小的存儲器保存迭代初值，但需要的運算器數(shù)量較多。查表法根據(jù)輸入的數(shù)據(jù)直接從ROM中查表得到結(jié)果，需要占用的存儲資源比較多。該文提出了一種間接查表法實現(xiàn)的浮點倒數(shù)開方運算實現(xiàn)方法，將迭代法和直接查表法的優(yōu)點結(jié)合起來。經(jīng)過理論推導(dǎo)和硬件仿真驗證，該算法能夠滿足單精度浮點數(shù)的運算精度。

關(guān)鍵詞：單精度浮點；倒數(shù)開方；查表

中圖分類號：TP312 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2013）09-2242-04

單精度浮點倒數(shù)開方運算在GPU設(shè)計中經(jīng)常會用到。在硬件設(shè)計中一般有兩種實現(xiàn)方法，一種是采用迭代法，比較著名的是牛頓-辛普森迭代法；另一種方法是查表法。兩種方法各有優(yōu)缺點：迭代法需要的存儲資源比較小，但是要達(dá)到單精度浮點數(shù)的精度要求，需要進(jìn)行多級迭代，所耗費的運算資源比較大；而查表法不需要運算資源，但是需要占用的存儲器資源數(shù)量會比較大。所以結(jié)合這兩種實現(xiàn)方法的優(yōu)缺點，該文實現(xiàn)了一種間接查表法，利用泰勒級數(shù)展開，取出適當(dāng)?shù)奈粩?shù)位數(shù)進(jìn)行查表，然后再進(jìn)行運算得出滿足精度要求的結(jié)果，在存儲資源和運算資源方面進(jìn)行了平衡。

1 IEEE 754單精度浮點數(shù)據(jù)格式

IEEE754標(biāo)準(zhǔn)定義了單精度32位和雙精度64位浮點數(shù)的格式。32位IEEE754單精度標(biāo)準(zhǔn)值中，第一位是符號位，其后8位用來存放指數(shù)，最后23位用來存放小數(shù)尾數(shù)，如表1所示。

表 1 單精度32位浮點數(shù)格式

在IEEE754單精度浮點標(biāo)準(zhǔn)中，明確包含了符號位，第32位用作符號位。尾數(shù)進(jìn)行了歸一化，以產(chǎn)生一個1.f格式的數(shù)，f是小數(shù)部分，占用分配的23位。因為規(guī)格化的數(shù)最左一位總是1，所以不需要存儲該位，在該格式中它是隱式的。這樣一個n位的尾數(shù)實際上存放了一個n+1位數(shù)。為使尾數(shù)規(guī)格化，指數(shù)被適當(dāng)增減，來跟蹤規(guī)格化所需的左右移位數(shù)以及小數(shù)點。

2 單精度浮點倒數(shù)開方算法

設(shè)x為單精度浮點數(shù)，計算[1x]的算法有迭代法、直接查表法和間接查表法。先不考慮指數(shù)的計算，只考慮尾數(shù)的倒數(shù)開方。（指數(shù)的計算在間接查表法中一并介紹）

2.1 迭代法

牛頓迭代法的迭代公式：

迭代法的收斂速度定義為：

則稱序列[xn]p階收斂，如果序列[xn]是由迭代公式[xn+1=Φxn]產(chǎn)生的，且p階收斂，則稱這種迭代過程是P階收斂的。

當(dāng)定義域為[1，4）時，上式可轉(zhuǎn)化為對尾數(shù)的整數(shù)運算。

注：定義域為[1，4）的說明：對于任一個浮點數(shù)而言，其尾數(shù)都在[1，2）內(nèi)，但由于開方時需要將階數(shù)除以2，因此尾數(shù)的范圍需要放大為2倍或縮小一半。實驗表明，放大至[1，4）效果更好。

為了加快收斂速度，按照如下方法確定迭代的初值：由于這里計算倒數(shù)時定義域為[1，4），因此把x軸上的區(qū)間[1，4）分成N段，每一段取中點的倒數(shù)開方值作為落在此段的x的迭代初值。當(dāng)分為32份時，則浮點數(shù)的尾數(shù)部分的前4位即可作為分段的序號。

試驗表明，分成32段的情況下，迭代n步得到結(jié)果的情況如下：

2.2 直接查表法

直接查表法比較簡單，根據(jù)浮點數(shù)的尾數(shù)，構(gòu)造ROM表，若直接根據(jù)輸入數(shù)據(jù)查ROM得到結(jié)果，總共需要223×32（bit）的存儲空間（即32MB），這在硬件實現(xiàn)時是基本不可能的。

2.3 間接查表法

將上述兩種方法的優(yōu)點結(jié)合起來，我們就會很自然的得到一種間接查表法。關(guān)鍵問題是ROM表如何設(shè)計。

2.3.1 指數(shù)的計算。

由浮點數(shù)格式可知：

因此，在保證24位精度的前提下，應(yīng)把浮點數(shù)x的尾數(shù)的定義域[1，2]等分為[212=4096]份。

步驟1：把x規(guī)格化到[1，2）的范圍內(nèi)，保持該數(shù)的后23位尾數(shù)，前面用0x3f8替代，即：nval = 0x3f800000 | （nval & 0x7fffff）；

步驟2：計算n值。n就是[an]中剛好小于x的n值，也就是尾數(shù)的前12位。于是：n = （nval & 0x7fffff） >> 11；

步驟3：計算h值、確定[An]、計算[an]-h。注意到當(dāng)x落在第一個小區(qū)間[1.0+14096，1.0+24096]時，即n==0時，[an]=0x3f800000，[2an-h]時會出現(xiàn)尾數(shù)溢出的情況。所以這時使用公式（4）進(jìn)行計算，其余情況使用公式（3）計算。

結(jié)論：計算2[an]-h時，注意到[an]和h的精度剛好是尾數(shù)中的前12位和后11位，因此這兩個數(shù)的差值不需要按浮點數(shù)相減，只需要把它們按照32位整數(shù)值相減就可以了。

步驟4：計算[An]（2[an]-h）。使用浮點數(shù)乘法計算以上兩數(shù)之積，得到的結(jié)果的后23位就是所要求的1/x的尾數(shù)。

得到尾數(shù)之后，再把x的符號位和1/x指數(shù)位合并到一起就得到了最后的1/x。

3 硬件實現(xiàn)

根據(jù)前面對算法的描述，將該算法的硬件實現(xiàn)結(jié)構(gòu)如圖2所示。

根據(jù)硬件實現(xiàn)結(jié)構(gòu)，計算浮點倒數(shù)的模塊需要的邏輯資源為：1個24位加法、1個24位乘法、1個4096×32（bit）=16KB的ROM。

將該算法用Verilog語言描述，生成一些隨機(jī)測試激勵在NC_Verilog環(huán)境下進(jìn)行仿真，仿真波形如圖3所示，其中輸入數(shù)據(jù)、運行結(jié)果、實際結(jié)果和誤差見表2所示。

由仿真結(jié)果可以看出，在硬件實現(xiàn)的計算結(jié)果與真實結(jié)果相比，誤差都不會超過±1×2-24，能夠滿足單精度浮點數(shù)的精度要求。

4 結(jié)束語

為了實現(xiàn)一種運算邏輯與存儲資源的平衡，該文提出了一種浮點倒數(shù)的間接查表算法。通過理論證明，該算法能夠保證單精度浮點數(shù)的運算精度。將該算法用硬件實現(xiàn)，通過仿真進(jìn)一步驗證了算法的正確性。

參考文獻(xiàn)：

[1] Nobuhiro Ide.2.44-GFLOPS 300-MHz Floating-Point Vector-Processing Unit for High-Performance 3-D Graphics Computing [J].IEEE JOURNAL OF SOLID-STATE CIRCUITS （JSSC），2000，35（7）：1025-1033.

[2] Kim D H.A SoC with 1.3 Gtexels/s 3-D Graphics Full Pipeline for Consumer Applications[J].IEEE JOURNAL OF SOLID-STATE CIRCUITS，2006，41：71-78.

[3] E.Lindholm，et at.A User-Programmable Vertex Engine [C].ACM SIGGRAPH，2001：12-17.

[4] Ercegovac M D，Lang T.Digital Arithmetic[M].Morgan Kaufmann Publishers，2004：182-237.