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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

若e為一個(gè)浮點(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á)式的計(jì)算精度、計(jì)算時(shí)間和資源消耗。

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

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

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

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

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

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

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

6）由于非支配列表中的表達(dá)式是在相應(yīng)的鄰域內(nèi)是非支配的，因此需要再次對(duì)非支配列表中的等價(jià)表達(dá)式進(jìn)行探索，若該列表中存在可支配的表達(dá)式，則將其刪除，保留的等價(jià)表達(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è)計(jì)空間探索方法的有效性，將提出的空間探索方法與現(xiàn)有的針對(duì)浮點(diǎn)表達(dá)式空間探索的方法從計(jì)算精度、計(jì)算時(shí)間和資源消耗等方面進(jìn)行對(duì)比分析。為了便于比較，選擇表達(dá)式結(jié)構(gòu)由簡(jiǎn)單到復(fù)雜的多個(gè)浮點(diǎn)表達(dá)式作為測(cè)試表達(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，采用就近舍入方法。

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

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

實(shí)驗(yàn)選擇3 個(gè)主流的浮點(diǎn)表達(dá)式設(shè)計(jì)空間探索方法進(jìn)行對(duì)比分析，包括快速選擇空間探索（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ù)位寬自動(dòng)調(diào)節(jié)的設(shè)計(jì)空間探索（Exploring Area-efficient with Optimized Exponent/mantissa Widths，EAOEW）方法［5］。

3.1 計(jì)算精度對(duì)比分析

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

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

3.2 計(jì)算時(shí)間對(duì)比分析

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

圖4 四種方法的計(jì)算時(shí)間對(duì)比Fig.4 Calculation time comparison of four methods

3.3 資源消耗對(duì)比分析

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

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

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

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

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

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

4 結(jié)語(yǔ)

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