基于啟發(fā)式搜索的浮點(diǎn)表達(dá)式設(shè)計空間探索方法

李 釗，董霄霄，黃程程，任崇廣

（山東理工大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，山東淄博 255000）

0 引言

隨著信號處理和圖像處理等在現(xiàn)場可編程門陣列（Field Programmable Gate Array，F(xiàn)PGA）上的廣泛應(yīng)用，浮點(diǎn)計算在FPGA 上的應(yīng)用變得越來越流行［1-4］。浮點(diǎn)數(shù)可以增加數(shù)據(jù)的表示范圍，但是浮點(diǎn)計算的誤差也會導(dǎo)致最終結(jié)果不準(zhǔn)確。根據(jù)IEEE 754 標(biāo)準(zhǔn)，通過加、減或乘兩個浮點(diǎn)數(shù)產(chǎn)生的計算結(jié)果都應(yīng)四舍五入為IEEE 754 浮點(diǎn)數(shù)格式，這種舍入是浮點(diǎn)計算不準(zhǔn)確的原因。當(dāng)浮點(diǎn)數(shù)格式固定的前提下，浮點(diǎn)計算的誤差主要取決于浮點(diǎn)表達(dá)式的形式。例如：表達(dá)式(x+y)2可表示為(x+y)×(x+y)和x×(x+y)+y×(x+y)等不同的形式，當(dāng)x的取值范圍為[0，0.000 02]，y的取值范圍為[20，21]時，兩個表達(dá)式的表示范圍分別為[-5.53×10-5，5.53×10-5]和[-5.05×10-5，5.05×10-5]，從而產(chǎn)生不同的誤差［5］。

浮點(diǎn)計算在FPGA 平臺上實(shí)現(xiàn)時，若浮點(diǎn)數(shù)格式固定，資源消耗主要取決于浮點(diǎn)表達(dá)式的形式。例如：表達(dá)式(x+y)×(x+y)需要一個乘法器和兩個加法器，而表達(dá)式x(x+y)+y(x+y)需要兩個乘法器和三個加法器，表達(dá)式(x+y)×(x+y)消耗更少的資源。因此通過優(yōu)化浮點(diǎn)表達(dá)式的結(jié)構(gòu)，可實(shí)現(xiàn)資源消耗的優(yōu)化。

浮點(diǎn)計算還需考慮計算時間，計算時間主要依賴于浮點(diǎn)運(yùn)算器的流水線深度以及浮點(diǎn)表達(dá)式的形式。當(dāng)浮點(diǎn)運(yùn)算器確定的前提下，可以通過改變浮點(diǎn)表達(dá)式的形式來改變計算時間。例如：若采用相同的浮點(diǎn)運(yùn)算器，表達(dá)式(x+y)×(x+y)可設(shè)計兩級流水線結(jié)構(gòu)完成計算，而表達(dá)式x(x+y)+y(x+y)需要設(shè)計三級流水線結(jié)構(gòu)完成計算，表達(dá)式(x+y)×(x+y)具有更短的計算時間。

一個浮點(diǎn)表達(dá)式經(jīng)過因式分解和提取公因數(shù)等方法進(jìn)行變形后可生成大量等價的浮點(diǎn)表達(dá)式，例如：x2+xz+z(x+y+z)+y(2x+y+z)可產(chǎn)生698 個等價表達(dá)式，每個表達(dá)式具有不同的計算精度，而且資源消耗和計算時間也不同?？刹捎酶↑c(diǎn)運(yùn)算器的結(jié)構(gòu)優(yōu)化、指數(shù)和尾數(shù)位寬調(diào)節(jié)和等價表達(dá)式的設(shè)計空間探索等方法，實(shí)現(xiàn)浮點(diǎn)計算在FPGA 上的優(yōu)化。

文獻(xiàn)［6］中采用半單元偏置格式設(shè)計浮點(diǎn)加法器和乘法器，以降低浮點(diǎn)運(yùn)算器的資源消耗并提高計算速度。文獻(xiàn)［7］中提出了一種新的位對重編碼算法，該算法可有效減少浮點(diǎn)乘法運(yùn)算中部分積行數(shù)，并減少與多路復(fù)用器、移位器和加法器相關(guān)聯(lián)的部分積的數(shù)量，與全精度乘法器相比可節(jié)省49%的面積和44.2%的功耗。文獻(xiàn)［8］中采用Newton-Raphson 迭代方法設(shè)計了一種32 位流水線浮點(diǎn)除法器，該除法器支持IEEE 754 標(biāo)準(zhǔn)中指定的所有類型的數(shù)據(jù)，該方案與現(xiàn)有方法相比需要多消耗30%的功耗，但所提出的流水線方法顯著降低了計算時間。文獻(xiàn)［5］中提出OptiFEX 優(yōu)化框架，可根據(jù)數(shù)據(jù)輸入范圍和最大允許誤差等參數(shù)，調(diào)節(jié)浮點(diǎn)運(yùn)算器指數(shù)和尾數(shù)的位寬，從而減少資源消耗，提高計算效率。

對浮點(diǎn)運(yùn)算器進(jìn)行優(yōu)化，可減少運(yùn)算器的資源消耗，并有效提高計算效率，但是浮點(diǎn)計算多為多個浮點(diǎn)數(shù)的混合運(yùn)算，浮點(diǎn)表達(dá)式的結(jié)構(gòu)也是制約浮點(diǎn)計算優(yōu)化的關(guān)鍵。

文獻(xiàn)［9］中設(shè)置一組關(guān)于資源消耗、計算時間和精度的約束條件，并從等價表達(dá)式集合中選擇滿足約束的等價表達(dá)式，從而完成設(shè)計空間的探索。利用該方法選擇的表達(dá)式雖然滿足約束條件，但仍可能是可支配的，因此選擇的表達(dá)式不一定是最優(yōu)表達(dá)式。文獻(xiàn)［10］中通過迭代分解的方法對初始浮點(diǎn)表達(dá)式進(jìn)行變形，在迭代過程中采用Pareto 算法刪除非最優(yōu)的表達(dá)式，從而減少等價表達(dá)式的數(shù)量，然后從剩余表達(dá)式中選擇資源消耗和計算時間最優(yōu)的浮點(diǎn)表達(dá)式。該方法在探索過程中對可支配等價表達(dá)式及其后繼表達(dá)式進(jìn)行了刪減，其探索過程不能覆蓋整個搜索空間，因此其選擇的非支配表達(dá)式的資源消耗、計算時間和精度等性能可能不是最優(yōu)的。

針對上述問題，本文提出一種新的浮點(diǎn)表達(dá)式設(shè)計空間探索的方法，該方法不僅對非支配表達(dá)式的鄰域進(jìn)行空間探索，同時對可支配列表中的表達(dá)式進(jìn)行再次評估，選擇該列表中非支配表達(dá)式，并對其鄰域進(jìn)行探索，最后再次對非支配列表中的等價表達(dá)式進(jìn)行探索，得到最優(yōu)的浮點(diǎn)表達(dá)式。該方法可對給定的浮點(diǎn)表達(dá)式及其等價表達(dá)式進(jìn)行探索，探索過程基本覆蓋整個搜索空間，根據(jù)優(yōu)化目標(biāo)和約束條件選擇最優(yōu)的等價表達(dá)式，因此不會引入浮點(diǎn)數(shù)處理的錯誤；同時該方法有效提高了非支配列表中非支配表達(dá)式的多樣性和隨機(jī)性，提高了最優(yōu)表達(dá)式的性能指標(biāo)。

1 產(chǎn)生等價表達(dá)式的方法

浮點(diǎn)表達(dá)式在等價變換過程中，以不同的等價表達(dá)式為起點(diǎn)，可能會重復(fù)出現(xiàn)同一個表達(dá)式，如圖1 中，表達(dá)式x(x+y)+y(x+y)重復(fù)出現(xiàn)兩次。若多次對同一個表達(dá)式進(jìn)行性能評估會影響空間探索的效率。

圖1 浮點(diǎn)表達(dá)式變換示例Fig.1 Example for floating-point expression transformation

本文參考文獻(xiàn)［5］中的方法實(shí)現(xiàn)了等價表達(dá)式的變換。首先對初始表達(dá)式進(jìn)行因式分解，直到表達(dá)式不能進(jìn)一步分解，然后對分解后的表達(dá)式進(jìn)行迭代提取公因式，直到?jīng)]有新的等價表達(dá)式產(chǎn)生。例如對(x+y)2的變換過程如圖2 所示，采用該方法可有效避免在等價變換過程中重復(fù)出現(xiàn)同一表達(dá)式。

圖2 （x+y）2的等價變換過程Fig.2 Equivalent transformation process of（x+y）2

2 設(shè)計空間探索方法

設(shè)計空間探索是一個多目標(biāo)優(yōu)化過程，可實(shí)現(xiàn)多目標(biāo)的折中［11-13］。為了提高設(shè)計空間探索的效率，需要根據(jù)優(yōu)化目標(biāo)，設(shè)計目標(biāo)函數(shù)以及相關(guān)約束，并在設(shè)計空間探索過程中對每個設(shè)計個體的性能進(jìn)行評估，判斷是否滿足目標(biāo)函數(shù)。另外需要設(shè)計搜索算法，利用該算法選擇下一步要評估的個體，將設(shè)計空間引導(dǎo)到符合優(yōu)化目標(biāo)的區(qū)域。

2.1 優(yōu)化目標(biāo)函數(shù)

浮點(diǎn)表達(dá)式在設(shè)計空間探索過程中，會產(chǎn)生多個等價的表達(dá)式，表達(dá)式的精度、計算時間以及資源消耗等都會有所不同。設(shè)計空間探索的目的是依據(jù)優(yōu)化目標(biāo)，將設(shè)計空間引導(dǎo)到符合優(yōu)化目標(biāo)的區(qū)域。浮點(diǎn)表達(dá)式設(shè)計空間探索的優(yōu)化目標(biāo)函數(shù)如式（1）：

其中：P為浮點(diǎn)表達(dá)式的計算精度，可由式（2）計算得到，為表達(dá)式以更高指數(shù)和尾數(shù)長度表示的計算結(jié)果Fr(xr1，xr2，…，xrn)與當(dāng)前參與空間探索的表達(dá)式的計算結(jié)果Ff(xf1，xf2，…，xfn)之差的絕對值，其值越小表示計算精度越高，例如當(dāng)前參與計算的為IEEE754 標(biāo)準(zhǔn)的32 位浮點(diǎn)數(shù)，則采用IEEE754標(biāo)準(zhǔn)的64位浮點(diǎn)數(shù)作為參考數(shù)據(jù)。D為浮點(diǎn)表達(dá)式在FPGA 上實(shí)現(xiàn)后從輸入浮點(diǎn)數(shù)據(jù)到輸出計算結(jié)果的時間，由關(guān)鍵路徑上各處理單元的計算時間之和計算得到，如式（3）所示，m為關(guān)鍵路徑上處理單元的數(shù)量。R為FPGA 上實(shí)現(xiàn)浮點(diǎn)計算的資源消耗，由各個處理單元的資源消耗之和計算得到，如式（4）所示，t為浮點(diǎn)運(yùn)算所需處理單元的數(shù)量。為了更好地實(shí)現(xiàn)多目標(biāo)優(yōu)化，對優(yōu)化目標(biāo)函數(shù)設(shè)置了多個約束條件，參考表達(dá)式的參數(shù)xri和參與計算表達(dá)式的參數(shù)xfi的取值必須在其允許的取值范圍內(nèi)，關(guān)鍵路徑的計算時間Dkp應(yīng)該大于等于任意處理單元的完成時間Dend(k)，任意處理單元的完成時間Dend(k)可由該處理單元的計算時間與該處理單元的前任處理單元的計算時間之和得到，如式（5）所示，其中d為前任處理單元的數(shù)量。最后浮點(diǎn)運(yùn)算的資源消耗應(yīng)小于等于FPGA平臺總的資源Rtotal。

2.2 啟發(fā)式搜索方法

浮點(diǎn)表達(dá)式在設(shè)計空間探索中會產(chǎn)生多個等價表達(dá)式，等價表達(dá)式之間的計算精度、資源消耗和計算時間等都有所不同［14-15］。每次迭代過程中采用啟發(fā)式搜索方法對產(chǎn)生的浮點(diǎn)表達(dá)式進(jìn)行評估，提取非支配的浮點(diǎn)表達(dá)式作為局部最優(yōu)的表達(dá)式，并以非支配表達(dá)式為起點(diǎn)進(jìn)行新一輪的迭代。

2.2.1 非支配浮點(diǎn)表達(dá)式的定義

若e為一個浮點(diǎn)表達(dá)式，N為浮點(diǎn)表達(dá)式的集合，且e∈N，若e滿足式（6），則浮點(diǎn)表達(dá)式e為集合N中的非支配浮點(diǎn)表達(dá)式。

其中：?x∈N；Precision、Delay和Resource分別為表達(dá)式的計算精度、計算時間和資源消耗。

2.2.2 非支配浮點(diǎn)表達(dá)式的選擇

現(xiàn)有的方法在進(jìn)行空間探索時，為了提高探索效率，直接刪除可支配表達(dá)式的后繼等價表達(dá)式，不對其進(jìn)行評估，而后繼表達(dá)式中可能存在非支配解。為此，本文提出一種新的非支配浮點(diǎn)表達(dá)式的選擇方法，可覆蓋整個探索空間，算法流程如圖3所示。

1）首先將給定的需要探索的表達(dá)式進(jìn)行因式分解，將分解后的表達(dá)式作為初始表達(dá)式。

2）然后對該表達(dá)式提取公因式進(jìn)行等價變形，即得到初始表達(dá)式的鄰域，并計算鄰域中等價表達(dá)式的計算精度、計算時間和資源消耗等性能指標(biāo)，得到非支配的等價表達(dá)式和可支配的等價表達(dá)式，并將可支配的表達(dá)式添加到可支配列表中，同時保存非支配表達(dá)式到非支配列表中。

3）以新的非支配表達(dá)式為起點(diǎn)，通過提取公因式得到相應(yīng)的鄰域，并探索鄰域，最終得到該起點(diǎn)鄰域中的非支配的等價表達(dá)式和可支配的等價表達(dá)式，并分別添加到可支配列表和非支配列表中。

4）再次以新的非支配表達(dá)式為起點(diǎn)，按照步驟3）進(jìn)行探索，直到達(dá)到規(guī)定的迭代次數(shù)或者無新的等價表達(dá)式產(chǎn)生。

5）上述過程未對可支配表達(dá)式的鄰域進(jìn)行探索，該步驟首先對可支配列表中的表達(dá)式進(jìn)行探索，提取該集合中的非支配表達(dá)式，并對其鄰域進(jìn)行探索，將鄰域中的非支配表達(dá)式保存到非支配列表中，可提高非支配列表中多項(xiàng)式的隨機(jī)性和多樣性。

6）由于非支配列表中的表達(dá)式是在相應(yīng)的鄰域內(nèi)是非支配的，因此需要再次對非支配列表中的等價表達(dá)式進(jìn)行探索，若該列表中存在可支配的表達(dá)式，則將其刪除，保留的等價表達(dá)式即為最終的最優(yōu)浮點(diǎn)表達(dá)式。

圖3 浮點(diǎn)表達(dá)式空間探索算法流程Fig.3 Flowchart of floating-point expression space exploration

3 實(shí)驗(yàn)驗(yàn)證

為了驗(yàn)證本文提出的基于啟發(fā)搜索的浮點(diǎn)表達(dá)式設(shè)計空間探索方法的有效性，將提出的空間探索方法與現(xiàn)有的針對浮點(diǎn)表達(dá)式空間探索的方法從計算精度、計算時間和資源消耗等方面進(jìn)行對比分析。為了便于比較，選擇表達(dá)式結(jié)構(gòu)由簡單到復(fù)雜的多個浮點(diǎn)表達(dá)式作為測試表達(dá)式，表達(dá)式中各參數(shù)的精度設(shè)定為：x∈[0.01，0.15]，y∈[0.32，0.43]，z∈[1.11，1.35]，指數(shù)的寬度設(shè)為5，尾數(shù)的寬度設(shè)為10，采用就近舍入方法。

為了更好地對計算精度進(jìn)行評估，分別在設(shè)定的精度范圍內(nèi)，均勻地取10 個浮點(diǎn)數(shù)據(jù)，首先分別按照IEEE754 標(biāo)準(zhǔn)格式對表達(dá)式進(jìn)行計算，將該計算結(jié)果的均值作為參考的準(zhǔn)確結(jié)果，然后按照實(shí)驗(yàn)要求格式，對表達(dá)式進(jìn)行計算，并計算實(shí)際結(jié)果的平均值，兩個平均值之差的絕對值即為計算精度。在設(shè)計空間探索過程中，利用FloPoCo［16］來提取加法器和乘法器的資源消耗和計算時間。FloPoCo 是一個用于生成算術(shù)數(shù)據(jù)通路的開源C++框架，其輸出是一個可綜合的VHDL代碼。

為了對各種設(shè)計空間探索方法的計算時間和資源消耗進(jìn)行定性和直觀比較，分別從各種方法產(chǎn)生的非支配表達(dá)式集合中隨機(jī)選擇5個表達(dá)式在FPGA 平臺上進(jìn)行仿真實(shí)驗(yàn)驗(yàn)證。FPGA 平臺選用Kintex7 系列的XC7K325T，綜合工具為Vivado2017.4，參考時鐘頻率為120 MHz。

實(shí)驗(yàn)選擇3 個主流的浮點(diǎn)表達(dá)式設(shè)計空間探索方法進(jìn)行對比分析，包括快速選擇空間探索（Fast Selection Design Space Exploration，F(xiàn)SDSE）方法［10］、基于迭代分解的空間探索（Design Space Exploration using Iterative Factorization，DSEIF）方法［9］和調(diào)節(jié)浮點(diǎn)運(yùn)算器指數(shù)和尾數(shù)位寬自動調(diào)節(jié)的設(shè)計空間探索（Exploring Area-efficient with Optimized Exponent/mantissa Widths，EAOEW）方法［5］。

3.1 計算精度對比分析

表1 為不同的設(shè)計空間探索方法對不同表達(dá)式進(jìn)行探索后，選擇的非支配表達(dá)式計算產(chǎn)生的計算精度對比。由表1可知，本文提出的浮點(diǎn)表達(dá)式設(shè)計空間探索方法的計算精度與DSEIF 方法相當(dāng)，但是要優(yōu)于FSDSE 和EAOEW 方法。例如針對浮點(diǎn)表達(dá)式(x+y+z)2，本文提出的方法的計算精度等于DSEIF 方法的計算精度，與EAOEW 方法相比本文提出方法的計算精度提高了9%，與FSDSE 方法相比提高了4%。主要原因在于DSEIF 方法是對整個搜索空間進(jìn)行探索，分別對每個等價多項(xiàng)式進(jìn)行計算精度等性能進(jìn)行評估，并從中選擇非支配表達(dá)式，其缺點(diǎn)是空間探索效率低。FSDSE 為快速選擇空間探索方法，在探索過程中對可支配等價表達(dá)式及其后繼表達(dá)式進(jìn)行了刪減，其探索過程不能覆蓋整個搜索空間，而可支配表達(dá)式的后繼節(jié)點(diǎn)中可能存在計算精度更高的表達(dá)式，因此其選擇的非支配表達(dá)式的計算精度會降低。EAOEW方法在空間探索過程中，只對資源消耗進(jìn)行評估，所以其計算精度最低。本文提出的方法采用啟發(fā)式搜索，在避免對可支配表達(dá)式進(jìn)行探索的同時，盡可能地覆蓋整個搜索空間，提高了最終選擇非支配表達(dá)式的多樣性和隨機(jī)性，從而保證了計算精度的準(zhǔn)確性。

表1 四種方法的計算精度對比Tab.1 Calculation accuracy comparison of four methods

3.2 計算時間對比分析

圖4 為針對每個測試表達(dá)式隨機(jī)選擇的5 個最優(yōu)等價表達(dá)式計算時間的平均值。計算時間為將經(jīng)過設(shè)計空間探索后得到的最優(yōu)表達(dá)式在FPGA 平臺上運(yùn)行所需要的時間。從圖4 中可知，本文提出的空間探索方法得到的非支配表達(dá)式的計算時間與DSEIF 方法相當(dāng)，要優(yōu)于FSDSE 和EAOEW 方法，例如針對表達(dá)式x(x+2z)+y(y+2x)+z(z+2y)，與FSDSE方法相比本文提出方法的計算時間減少了5%，與EAOEW 方法相比減少了12%，本文方法可選擇計算時間更優(yōu)的等價表達(dá)式。主要原因在于本文方法不僅對非支配表達(dá)式的鄰域進(jìn)行探索，同時選擇可支配列表中的非支配表達(dá)式，并對其鄰域進(jìn)行探索；還對最終產(chǎn)生的非支配列表再次進(jìn)行探索，最終得到最優(yōu)的等價表達(dá)式，從而提高了選擇計算時間最優(yōu)的表達(dá)式的概率。

圖4 四種方法的計算時間對比Fig.4 Calculation time comparison of four methods

3.3 資源消耗對比分析

圖5 為針對每個測試表達(dá)式隨機(jī)選擇的5 個等價表達(dá)式資源消耗的平均值。從圖5 中可知，與計算時間不同，EAOEW 方法具有最優(yōu)的資源消耗，本文提出的空間探索方法得到的非支配表達(dá)式的資源消耗與DSEIF 方法相當(dāng)，要優(yōu)于FSDSE 方法，例如針對表達(dá)式y(tǒng)(x+y)2，與FSDSE 方法相比，本文提出方法的資源消耗減少了5%。主要原因是：在設(shè)計空間探索過程中，EAOEW 只針對資源消耗一個性能進(jìn)行評估，選擇的等價表達(dá)式是資源消耗最優(yōu)的；而本文方法是針對計算精度、計算時間與資源消耗三個性能進(jìn)行綜合評估的，為三個性能的折中優(yōu)化。

圖5 四種方法的資源消耗對比Fig.5 Resource consumption comparison of four methods

3.4 設(shè)計空間探索時間對比分析

因?yàn)楸疚姆椒ㄅcDSEIF 方法在計算精度、計算時間與資源消耗等方面性能相當(dāng)，為進(jìn)一步對比兩種設(shè)計空間探索方法，用設(shè)計空間探索的時間對二者進(jìn)行對比分析。設(shè)計空間探索時間是指在PC平臺上，利用浮點(diǎn)表達(dá)式設(shè)計空間探索方法對等價的浮點(diǎn)表達(dá)式及其鄰域進(jìn)行探索，直到得到最優(yōu)表達(dá)式所需要的時間，可體現(xiàn)設(shè)計空間探索方法的效率。

圖6 為兩種設(shè)計空間探索方法對不同表達(dá)式進(jìn)行探索的時間對比。本文提出方法的設(shè)計空間探索時間要優(yōu)于DSEIF方法，尤其當(dāng)浮點(diǎn)表達(dá)式結(jié)構(gòu)復(fù)雜時，其時間優(yōu)勢越明顯，例如對表達(dá)式x(x+2z)+y(y+2x)+z(z+2y)，本文提出方法的空間探索時間比DSEIF 方法縮短了89 s。主要原因是：DSEIF 方法需要對整個設(shè)計空間進(jìn)行探索，探索效率低；而本文方法在保證對非支配表達(dá)式的鄰域進(jìn)行探索的前提下，對可支配列表中的表達(dá)式進(jìn)行選擇性的探索，在保證覆蓋整個搜索空間的同時，有效提高了設(shè)計空間探索的效率。

圖6 設(shè)計空間探索時間對比Fig.6 Design space exploration time comparison

4 結(jié)語

本文對浮點(diǎn)表達(dá)式設(shè)計空間探索的問題進(jìn)行研究，針對已有的方法空間探索效率低下和計算性能差等問題，提出一種基于啟發(fā)搜索的浮點(diǎn)表達(dá)式設(shè)計空間探索方法，并與現(xiàn)有的具有代表性的浮點(diǎn)表達(dá)式設(shè)計空間探索方法對典型的浮點(diǎn)表達(dá)式進(jìn)行實(shí)驗(yàn)對比，實(shí)驗(yàn)結(jié)果表明本文提出的浮點(diǎn)表達(dá)式設(shè)計空間探索方法，在有效提高空間探索效率的前提下，得到的等價表達(dá)式具有更高的計算精度、更低的計算時間和資源消耗。