面向高層次綜合的自定義指令自動(dòng)識(shí)別方法

肖成龍，林 軍，王珊珊，王 寧

(遼寧工程技術(shù)大學(xué) 軟件學(xué)院，遼寧 葫蘆島 125105)(*通信作者電子郵箱2437017377@qq.com)

0 引言

隨著半導(dǎo)體技術(shù)的飛速發(fā)展以及集成電路的復(fù)雜度不斷增加，在低層次的寄存器傳輸級(jí)(Register-Transfer Level, RTL)下手寫代碼、維護(hù)和仿真較困難并且極易出錯(cuò)。高層次綜合(High Level Synthesis, HLS)是一個(gè)將高抽象層次的行為描述轉(zhuǎn)換為低層次的寄存器傳輸級(jí)描述的自動(dòng)化或半自動(dòng)化編譯過程，它接收基于C或C++語言的行為描述、含硬件組件詳細(xì)信息的資源庫(kù)以及特殊的約束條件作為輸入，經(jīng)過前端編譯、資源分配、調(diào)度、綁定以及代碼轉(zhuǎn)換等過程，自動(dòng)生成寄存器傳輸級(jí)的代碼。高層次綜合(HLS)可以有效解決寄存器傳輸級(jí)所遇到的問題，且具有設(shè)計(jì)周期短、產(chǎn)品質(zhì)量高等優(yōu)點(diǎn)[1-2]。

近年來，研究者致力于高層次綜合的性能和能耗方面的研究。自定義功能單元(自定義指令的硬件實(shí)現(xiàn))是權(quán)衡可擴(kuò)展處理器靈活性和效率的重要組件[3-4]，在可擴(kuò)展處理器中使用自定義指令能夠有效提高運(yùn)算速度、減少面積和代碼量[5-6]。將自定義指令應(yīng)用到高層次綜合中，可以有效解決高層次綜合能耗問題[7-8]。然而，現(xiàn)有研究多數(shù)是在高層次綜合的過程中進(jìn)行[7-13]，需要修改高層次綜合的核心算法，實(shí)現(xiàn)起來相對(duì)困難。

針對(duì)以上問題，本文提出了一種面向高層次綜合的自定義指令自動(dòng)識(shí)別方法，主要貢獻(xiàn)包括：

1)方法在高層次綜合過程之前識(shí)別自定義指令，可適用于大部分的高層次綜合工具，克服了現(xiàn)有研究在高層次綜合過程中識(shí)別自定義指令的缺點(diǎn)。

2)針對(duì)子圖枚舉，結(jié)合搜索樹設(shè)計(jì)了一種基于節(jié)點(diǎn)刪除技術(shù)的深度優(yōu)先(Depth-First based on Node Deletion technique, DFND)搜索算法，可靈活修改圖大小、連通性等約束條件。

3)針對(duì)子圖選擇，提出了基于最少子圖數(shù)目的選擇(Minimum number of matches based subgraph Selection, MS)算法、基于關(guān)鍵路徑的子圖選擇(Critical paths based subgraph Selection, CS)算法以及基于出現(xiàn)頻率的模式選擇(frequency of occurrence based Pattern Selection, PS)算法。在測(cè)試基準(zhǔn)程序上進(jìn)行實(shí)驗(yàn)并對(duì)3種算法進(jìn)行比較，驗(yàn)證了3種算法的有效性。

1 相關(guān)研究

面向高層次綜合的自定義指令自動(dòng)識(shí)別方法涉及兩個(gè)關(guān)鍵問題：子圖枚舉問題和子圖選擇問題。本章分別對(duì)這兩個(gè)問題進(jìn)行分析。

1.1 子圖枚舉問題

由于寄存器的讀寫端口數(shù)目有限，近期的研究專注于在I/O端口約束的條件下枚舉子圖。Chen等[14]證明子圖枚舉是具有多項(xiàng)式時(shí)間復(fù)雜度的問題；Bonzini等[15]提出一種多項(xiàng)式時(shí)間的子圖枚舉算法；Arnold等[16]用動(dòng)態(tài)規(guī)劃的方法枚舉出所有子圖，然而當(dāng)圖的規(guī)模變大，這些枚舉方法效率較低。自定義指令執(zhí)行過程中需要保持原子性，因而在硬件功能單元中實(shí)現(xiàn)的自定義指令應(yīng)該滿足凸性[17]，Giaquinta等[18]提出枚舉出最大凸子圖的算法；Wang等[19]提出枚舉出所有凸子圖的方法；Atasu等[20]提出一種在凸性和I/O端口約束下的二元決策樹的精確算法。在此基礎(chǔ)上，Pozzi等[21]通過添加一項(xiàng)基于永久輸入數(shù)目的修剪標(biāo)準(zhǔn)，使算法得到進(jìn)一步改進(jìn)。Yu等[22-23]通過合并向上和向下的錐體型子圖構(gòu)建連通子圖，然而，該算法可能使得同一個(gè)子圖被多次枚舉。Xiao等[24-25]所提出的子圖枚舉算法利用數(shù)據(jù)流圖的拓?fù)涮匦詠頊p少部分搜索空間，從而減少了算法的執(zhí)行時(shí)間。Xiao等[26]提出了一種靈活的算法，該算法可以枚舉出連通子圖或所有子圖。Xiao等[27]將自定義指令識(shí)別應(yīng)用到高層次綜合之中，提出多約束條件組合的枚舉算法。

在可擴(kuò)展處理器的設(shè)計(jì)中，由于處理器和自定義功能單元之間存在數(shù)據(jù)通信成本，I/O端口數(shù)目是重要的約束。然而，在高層次綜合的技術(shù)背景下，I/O端口的數(shù)目不再被限制[7]。Cong等[8]提出一種子圖枚舉算法，該算法能夠枚舉出所有滿足用戶定義的編輯距離和頻率限制的子圖，但是在枚舉階段應(yīng)用用戶定義的編輯距離和頻率限制約束使一些具有較好提升性能的子圖在早期被丟棄，該算法還必須使用額外的重復(fù)檢查來排除冗余子圖。Balister等[28]以自頂向下的方式枚舉所有連通凸子圖(connected convex subgraphs, cc-subgraphs)，算法至少產(chǎn)生了2·cc(G)-n個(gè)遞歸調(diào)用來枚舉所有的連通凸子圖。其中：cc(G)表示枚舉cc-subgraphs的數(shù)目，n是圖G的節(jié)點(diǎn)數(shù)。在這些遞歸調(diào)用中，只有葉節(jié)點(diǎn)負(fù)責(zé)生成連通凸子圖。

此前國(guó)內(nèi)外的研究主要是在特定約束條件下枚舉子圖。然而當(dāng)用戶增加或刪除約束條件時(shí)，算法將不再適用。本文提出一種更為有效的枚舉算法(DFND算法)，DFND算法只需cc(G)次調(diào)用就可以枚舉所有的連通凸子圖。當(dāng)約束條件發(fā)生變化時(shí)，此算法以自底而上的方式靈活地枚舉出滿足圖大小約束的連通凸子圖。

1.2 子圖選擇問題

枚舉出的候選子圖被選擇的原因多數(shù)是由于其在應(yīng)用代碼中被頻繁利用，或者與其他組件相比具有較高的性能，又或者可以顯著減少面積，因此，提出良好的子圖選擇方法對(duì)于應(yīng)用程序性能提升或面積減少至關(guān)重要。針對(duì)子圖選擇問題，許多研究者提出了不同的方法。

Clark等[29]提出一種精確算法，旨在用最少數(shù)目的自定義指令覆蓋每個(gè)節(jié)點(diǎn)，該算法將子圖選擇問題轉(zhuǎn)換為單邊覆蓋問題。Martin等[30]嘗試通過使用約束編程來解決子圖選擇問題，該文獻(xiàn)對(duì)自定義指令的選擇通過兩種相應(yīng)的調(diào)度策略實(shí)現(xiàn)：時(shí)間約束調(diào)度或資源約束調(diào)度。Yu等[22-23]提出一種基于整數(shù)線性規(guī)劃(Integer Linear Programming, ILP)的自定義指令選擇的最優(yōu)方法。

由于子圖選擇問題的計(jì)算復(fù)雜度較高，當(dāng)應(yīng)用程序?qū)?yīng)的數(shù)據(jù)流圖較大時(shí)，精確算法可能無法給出最優(yōu)解。而探索式方法能夠高效地解決該問題。Kastner等[31]通過沿著最頻繁出現(xiàn)的邊生成子圖來選擇具有高出現(xiàn)頻率的子圖；Guo等[32]提出基于沖突圖的模式選擇算法，此算法用最少數(shù)目的模式來覆蓋圖，該算法在子圖之間不能有重疊的前提下，使用一個(gè)目標(biāo)函數(shù)貪婪地選擇子圖；Bozorgzadeh等[33]提出子圖選擇由調(diào)度決定，使重要的子圖獲得更高的優(yōu)先級(jí)。近年來，一些元啟發(fā)式算法也用來解決子圖選擇問題[34-36]。Cong等[7-8]將實(shí)現(xiàn)的子圖選擇算法應(yīng)用在基于自定義指令的高層次綜合之中。然而，該算法所選擇的自定義指令會(huì)引起延遲增加的問題。為解決時(shí)延問題，Xiao等[26-27]提出基于關(guān)鍵路徑的數(shù)學(xué)模型，提升了高層次綜合效率。本文在無重疊和無循環(huán)約束條件下提出了3種不同子圖選擇方法，重點(diǎn)研究了高層次綜合在性能、面積和代碼量方面的內(nèi)容。

2 相關(guān)定義

數(shù)據(jù)流圖(Data Flow Graph, DFG)是一種有向無環(huán)圖(Directed Acyclic Graph, DAG)。圖G=(V,E)，頂點(diǎn)集V={v1,v2,…,vn}表示基本指令，邊集E={e1,e2,…,en}?V×V表示指令之間數(shù)據(jù)依賴關(guān)系。圖G的子圖S=(Vs,Es)，其中Vs?V，Es?E。

定義1 凸子圖。對(duì)于G的子圖S，?u,v∈Vs，若在G中u與v之間的任何路徑都只經(jīng)過S中的節(jié)點(diǎn)，則稱S是G的凸子圖。

在硬件功能單元中實(shí)現(xiàn)的自定義指令應(yīng)該滿足凸性，否則不能滿足自定義指令執(zhí)行過程中的原子性。在圖1中，子圖{1,2,3}是凸子圖，而子圖{2,3,5}不是凸子圖。

圖1 數(shù)據(jù)流圖示例

定義2 同構(gòu)圖。從圖G到圖S的同構(gòu)是一個(gè)雙射f:V(G)→V(S)，使得uv∈E(G)，記為G?S。如果圖G中的頂點(diǎn)u和v的連線uv屬于圖G邊的集合E(G)，則u和v映射到圖S邊的集合E(S)；反之亦然，則稱圖G和圖S同構(gòu)。有向圖的同構(gòu)是圖中的節(jié)點(diǎn)以及邊的一一對(duì)應(yīng)關(guān)系。

定義3 模式。給定兩個(gè)子圖a和b，如果a與b同構(gòu)，則創(chuàng)建模式P，并且子圖a和b被記錄在模式P中。模式是所有同構(gòu)子圖的圖形化表示。

給定DFGG=(V,E)和子集X，子集X?G，X的后繼或前驅(qū)如下表示。

X的直接前驅(qū)節(jié)點(diǎn)集：

IPred(X)={v|u∈V,v∈X,(u,v)∈E}

X的直接后繼節(jié)點(diǎn)集：

ISucc(X)={v|v∈X,u∈V,(v,u)∈E}

X的所有前驅(qū)節(jié)點(diǎn)集：

X的所有后繼節(jié)點(diǎn)集：

問題1 子圖枚舉。給定一個(gè)DFG,G=(V，E),枚舉滿足以下約束的所有子圖：

1)凸性。S是凸子圖。

2)連通性。S是連通的。

3)最大規(guī)模(可根據(jù)用戶需求設(shè)置)。

子圖滿足凸性可使程序執(zhí)行過程中保持原子性。由于連通子圖內(nèi)部數(shù)據(jù)流可減少多路選擇器的使用，因而枚舉連通子圖。在圖1中，自定義指令{1,3}是一個(gè)連通的子圖，而自定義指令{1,2}是分離子圖。當(dāng)枚舉所有連通凸子圖過于復(fù)雜時(shí)，限制子圖大小很有必要。多數(shù)情況下，考慮到資源重用(面積成本)，具有高出現(xiàn)頻率的小子圖更有可能被選擇。

問題2 子圖/模式選擇。給定一個(gè)DFG，G=(V，E)和一組枚舉的子圖/模式，根據(jù)不同的選擇方法選擇一組最佳子圖集，使G中的每個(gè)節(jié)點(diǎn)被覆蓋，滿足以下約束：

1)無重疊約束。兩個(gè)子圖可能具有共同的節(jié)點(diǎn)。允許重疊有時(shí)可能會(huì)改善程序運(yùn)行時(shí)間，但同時(shí)增加不必要的功耗并難以生成新代碼[37]，因此，本文中不允許選擇的子圖之間有重疊。

2)無循環(huán)約束。如果兩個(gè)子圖相互提供數(shù)據(jù)，則生成一個(gè)循環(huán)。在這種情況下，兩個(gè)自定義指令之間會(huì)發(fā)生死鎖[6]，因此，本文不允許選擇的子圖之間存在循環(huán)。

3 面向高層次綜合的自定義指令自動(dòng)識(shí)別方法

本文所提出的面向高層次綜合的自定義指令自動(dòng)識(shí)別方法在不修改高層次綜合的核心算法前提下，高效地識(shí)別滿足用戶指定的不同約束條件和設(shè)計(jì)目標(biāo)的自定義指令。該方法相對(duì)靈活，改進(jìn)自定義指令自動(dòng)識(shí)別階段的算法就可以提升高層次綜合效率方面的問題，降低了研究問題的難度。本文的方法主要由中間表示生成、子圖枚舉、子圖選擇以及代碼轉(zhuǎn)換組成。方法如圖2所示。圖2中：RTL(Register-Transfer Level)為寄存器傳輸級(jí)；VHDL(Very-High-speed integrated circuit hardware Description Language)為超高速集成電路硬件描述語言。

圖2 面向高層次綜合的自定義指令自動(dòng)識(shí)別方法

3.1 中間表示生成

本文方法的第一步是自動(dòng)生成源代碼的中間表示，該階段的輸入是C或C++源代碼。使用開源編譯器GECOS(Generic Compiler Suite)將源代碼轉(zhuǎn)換為控制數(shù)據(jù)流圖(Control Data Flow Graph, CDFG)，控制數(shù)據(jù)流圖是多個(gè)基本塊之間的數(shù)據(jù)依賴關(guān)系圖。程序代碼對(duì)應(yīng)的數(shù)據(jù)流圖如圖3所示。

圖3 源代碼的中間表示

在生成源代碼的中間表示后，基于控制數(shù)據(jù)流圖內(nèi)的數(shù)據(jù)流圖進(jìn)行自定義的枚舉和選擇。其中，子圖是自定義指令的圖形化表示。

3.2 子圖枚舉

在枚舉階段中，如果生成冗余子圖，將極大地影響子圖枚舉效率。目前識(shí)別子圖的方法存在冗余問題，需進(jìn)行重復(fù)檢查過濾掉重復(fù)的子圖，進(jìn)而額外地增加了程序的運(yùn)行時(shí)間。本文提出了一種可避免產(chǎn)生冗余子圖的子圖枚舉算法——DFND算法，DFND算法通過節(jié)點(diǎn)刪除技術(shù)使所有子圖只能被識(shí)別一次，提升了枚舉效率。

一般情況下，可以通過添加鄰居節(jié)點(diǎn)到預(yù)先識(shí)別的較小子圖來迭代地生成較大的子圖。例如，通過將相鄰節(jié)點(diǎn)添加到k-subgraph來形成(k+1)-subgraph(如果子圖中節(jié)點(diǎn)的數(shù)目為k，則稱為k-subgraph)。然而，大的子圖在枚舉過程中可能被枚舉多次。如圖1所示，子圖{1,2,3}可以通過添加節(jié)點(diǎn)2到{1,3}或者添加節(jié)點(diǎn)1到{2,3}生成，因而子圖{1,2,3}可以被枚舉兩次。

為了避免多次枚舉，DFND算法是以深度優(yōu)先的方式枚舉出所有子圖，并在每次迭代過程中刪除已經(jīng)識(shí)別過的節(jié)點(diǎn)。從圖1的DFG構(gòu)建搜索樹并枚舉所有連通子圖的DFND算法過程如圖4所示，其中，枚舉子圖的最大節(jié)點(diǎn)數(shù)設(shè)為3，R={}代表記錄刪除的節(jié)點(diǎn)，如R={1}代表記錄刪除節(jié)點(diǎn)1。算法首先枚舉出包含節(jié)點(diǎn)1的子圖(子圖{1})；然后，枚舉包含節(jié)點(diǎn)1和3的子圖(子圖{1,3})；緊接著枚舉出包含子圖{1,3}和節(jié)點(diǎn)2的子圖(子圖{1,3,2})。在枚舉包含子圖{1,3}和節(jié)點(diǎn)5的子圖之前，應(yīng)先刪除節(jié)點(diǎn)2。在枚舉出所有的包含節(jié)點(diǎn)1的子圖之后，當(dāng)枚舉包含節(jié)點(diǎn)2，節(jié)點(diǎn)3，節(jié)點(diǎn)4或節(jié)點(diǎn)5的子圖時(shí)，應(yīng)先刪除節(jié)點(diǎn)1。以這種方式可以枚舉出所有滿足條件的子圖，并且避免了任何一個(gè)子圖被枚舉多次。DFND算法的偽代碼如算法1所示。

圖4 DFND算法過程圖

算法1 子圖枚舉算法。

Require:G//圖G

Ensure:CS//CS代表所有枚舉出的子圖集合

1) Procedure SubgraphEnumeration()

2)R=?; //R是記錄的被刪除的節(jié)點(diǎn)

3) for each noden∈Gdo

4)M={n};

5)CS=CS∪M;

6) call DepthFirstEnumeration(M,R);

7)R=R∪n;

8) end for

9) Procedure DepthFirstEumeration(M,R)

10) for each neighbour nodenofMandn?Rdo

11) if SizeCheck(M) && ConversityCheck(M,n) //進(jìn)行圖大小約束和凸性約束檢查 then

12)M′=M∪{n};

13)CS=CS∪M′;

14) call DepthFirstEumeration(M′,R);

15)R=R∪n;

16) end if

17) end for

如算法1所示，對(duì)于枚舉過程中的每個(gè)子圖，都需進(jìn)行圖大小約束檢查和凸性約束檢查(第11)行)。此外，該枚舉算法還可以用來枚舉分離子圖(將算法1中的第10)行替換為M的鄰居節(jié)點(diǎn)和非鄰居節(jié)點(diǎn))。

3.3 子圖選擇

子圖選擇是在枚舉所有滿足約束條件的子圖之后進(jìn)行的。由于精確算法非常耗時(shí)且通常不能在合理的時(shí)間內(nèi)得出結(jié)果，因此需要更高效的啟發(fā)式方法。本文提出了3種不同的啟發(fā)式選擇方法。3種方法考慮的約束條件如下。

1)無重疊。子圖(M)或模式(P)作為候選子圖時(shí)，按照式(1)檢查已經(jīng)選擇的子圖(C)與候選子圖是否有重疊部分：

M∩C=?

(1)

2)無循環(huán)。為了確保所選的子圖與當(dāng)前候選子圖沒有形成循環(huán)，應(yīng)該進(jìn)行無循環(huán)檢查。如果當(dāng)前候選子圖滿足式(2)，則候選子圖與其他所選子圖之間不存在循環(huán)：

Succ(M)∩Pred(M)=?

(2)

其中Succ(M)和Pred(M)代表子圖M的后繼節(jié)點(diǎn)集和前驅(qū)節(jié)點(diǎn)集。如果候選子圖經(jīng)過無重疊檢查和無循環(huán)檢查，則該候選子圖就能被加入到子圖集中。

3.3.1 基于最少子圖數(shù)目的選擇

所選子圖的數(shù)目與代碼量相關(guān)，在子圖選擇過程中，所選子圖數(shù)目越少，經(jīng)代碼轉(zhuǎn)換后生成新代碼量越少。從能耗的角度出發(fā)，在給定的數(shù)據(jù)流圖中選擇最少子圖數(shù)目(MS算法)可以作為子圖選擇的一個(gè)策略。

對(duì)于選擇最少子圖數(shù)目的方法，所選子圖包含的節(jié)點(diǎn)越多，子圖數(shù)目越少。同時(shí)，由于自定義指令的內(nèi)部數(shù)據(jù)流不包含多路選擇器，因此利用所選子圖內(nèi)部邊數(shù)目可以粗略地估計(jì)節(jié)省多路選擇器的數(shù)目。然而，貪婪地選擇包含節(jié)點(diǎn)數(shù)多的子圖，其結(jié)果使一些包含少量節(jié)點(diǎn)卻能夠較好提升性能的子圖被排除。根據(jù)節(jié)點(diǎn)數(shù)目多的子圖與枚舉的所有子圖重疊概率大的特點(diǎn)，引入重疊參數(shù)。選擇較少重疊的子圖限制圖的大小。在最少子圖數(shù)目方法下，該算法根據(jù)式(3)計(jì)算每個(gè)子圖的優(yōu)先級(jí)：

fi=N+E+α*1/O(Mi)

(3)

其中：N表示子圖Mi的節(jié)點(diǎn)數(shù)，E表示子圖Mi的內(nèi)部邊數(shù)目，O(Mi)表示Mi與其他子圖重疊的次數(shù)，α表示重疊權(quán)重的參數(shù)。α小于1時(shí)，重疊對(duì)最少子圖數(shù)目的選擇方法影響過小，導(dǎo)致所選子圖節(jié)點(diǎn)數(shù)過多。為了控制所選子圖節(jié)點(diǎn)的數(shù)目，α的取值為2較為合適。1/O(Mi)表示選擇較少重疊的子圖。

如圖5所示，當(dāng)候選子圖的最大規(guī)模為3，α的值為2時(shí)，且僅考慮連通子圖的情況下,計(jì)算子圖M1和M2的優(yōu)先級(jí)。子圖M1為{1,3,4}，子圖M2為{2,4,5}，圖5枚舉的所有子圖為{{1}，{2}，{3}，{4}，{5}，{1,3}，{1,4}，{2,4}，{4,5}，{1,3,4}，{1,4,2}，{1,4,5}，{2,4,5}}，共13個(gè)子圖，有5個(gè)1-subgraph，4個(gè)2-subgraph和4個(gè)3-subgraph。子圖M1與所有候選子圖重疊的子圖有{{1}，{3}，{4}，{1,3}，{1,4}，{2,4}，{4,5}，{1,3,4}，{1,4,2}，{1,4,5}，{2,4,5}}，O(M1)的值為11。而子圖M2與所有候選子圖重疊的子圖有{{2}，{4}，{5}，{1,4}，{2,4}，{4,5}，{1,3,4}，{1,4,2}，{1,4,5}，{2,4,5}}，O(M2)的值為10。根據(jù)式(3)，fM2=3+2+2*1/10，fM1=3+2+2*1/11，得到fM2>fM1，由于子圖M2與所有候選子圖有較少的重疊，最終選擇子圖M2。

圖5 基于較少重疊的子圖選擇

3.3.2 基于出現(xiàn)頻率的模式選擇

基于出現(xiàn)頻率的模式選擇(PS)算法從提供的一系列模式當(dāng)中選擇一組子集作為自定義指令。模式是一些同構(gòu)子圖的圖形化表示?？紤]到硬件資源重用，選擇較少數(shù)量的模式可使得高層次綜合中使用較少的面積，這樣，出現(xiàn)頻率較高的模式更可能被選擇。通常，較小的模式具有較高的出現(xiàn)頻率；然而，較小的模式可能不會(huì)帶來更好的性能提升或明顯的面積減少。根據(jù)式(4)，本文提出了一個(gè)可在模式大小和頻率之間平衡的優(yōu)先級(jí)函數(shù)：

fi=N*|M|+α*N

(4)

其中：N表示模式的大小，|M|表示模式對(duì)應(yīng)的子圖數(shù)目。參數(shù)α用來控制模式大小所占的權(quán)重。α>1時(shí)，模式較大，而模式出現(xiàn)的頻率較低，不能有效地節(jié)省面積；而α<0.1時(shí)，所選模式較小，影響性能提升的效果。為了控制模式的大小，參數(shù)α取值0.3較為合適。如圖6所示，當(dāng)參數(shù)α的值為0.3時(shí)，模式A(PA)的大小為3，模式B(PB)的大小為1。圖6按照模式A劃分3個(gè)子圖，按模式B劃分9個(gè)子圖。根據(jù)式(4)分別求PA和PB的值，fPA=3×3+0.3×3,fPB=1×9+0.3×1，fPA>fPB。模式A是更好的選擇。

圖6 選擇具有更多節(jié)點(diǎn)的模式

3.3.3 基于關(guān)鍵路徑的子圖選擇

DFG的關(guān)鍵路徑長(zhǎng)度與程序的運(yùn)行時(shí)間有關(guān)?；陉P(guān)鍵路徑的子圖選擇方法(CS算法)能夠在一定程度上節(jié)省時(shí)延開銷。

如圖7所示，假設(shè)乘法需要2個(gè)時(shí)鐘周期，加法需要1個(gè)時(shí)鐘周期，子圖/模式的最大規(guī)模為2。當(dāng)前關(guān)鍵路徑為{4,2,1}，關(guān)鍵路徑的長(zhǎng)度為4個(gè)時(shí)鐘周期。如果選擇子圖M1和M2，進(jìn)一步假定每個(gè)子圖需要2.7個(gè)時(shí)鐘周期。顯而易見，子圖選擇之后，關(guān)鍵路徑的長(zhǎng)度增加到7.4個(gè)時(shí)鐘周期(乘法累加器的時(shí)間延遲要少于乘法器和加法器運(yùn)算的時(shí)間延遲之和)。該選擇方案最終會(huì)造成更多的時(shí)延開銷。

基于關(guān)鍵路徑的子圖選擇方法首先評(píng)估每個(gè)候選子圖，將候選子圖合并成一個(gè)節(jié)點(diǎn)之后，計(jì)算關(guān)鍵路徑長(zhǎng)度。如果關(guān)鍵路徑長(zhǎng)度增加，則放棄選擇該子圖作為候選子圖。為了不增加關(guān)鍵路徑的長(zhǎng)度，使所選子圖的節(jié)點(diǎn)盡量出現(xiàn)在關(guān)鍵路徑上，根據(jù)式(5)按照降序排列候選子圖：

fi=|M∩CP|

(5)

其中：M表示子圖中的節(jié)點(diǎn)集合，CP表示關(guān)鍵路徑上的節(jié)點(diǎn)集合。如圖7所示，子圖{1,2}具有比子圖{1,3}更高的優(yōu)先級(jí)(f{1,2}=2，f{1,3}=1)。對(duì)候選子圖排序后，評(píng)估每個(gè)候選子圖，不選擇增加關(guān)鍵路徑長(zhǎng)度的子圖。子圖{1,2}可減少關(guān)鍵路徑的長(zhǎng)度，則子圖{1,2}將被選擇，而不選擇子圖{1,3}。

圖7 選擇子圖導(dǎo)致關(guān)鍵路徑長(zhǎng)度增加的示例

由于所提出的3種方法都是啟發(fā)式算法，主要區(qū)別在于給定的優(yōu)先級(jí)函數(shù)，可使用通用的偽代碼來描述它們(參見算法2)。

算法2 子圖/模式選擇算法。

Require:CS

//CS代表全部的枚舉子圖

fi

//功能函數(shù)

Ensure:SS

//被選擇的候選子圖集

SortCSin descending order according tofi;

//根據(jù)fi降序排列

whileCS≠? do

M=the highest prioritized candidate inCS;

if Overlapping(M,SS) and Cycle(M,SS)

//進(jìn)行無重疊和無循環(huán)檢查

then

if IncreaseCriticalPath(M) then

SS=SS∪M;

end if

end if

CS=CS-M;

end while

3.4 代碼轉(zhuǎn)換

在選擇一組子圖集作為候選自定義指令之后，需要確定兩個(gè)選擇的子圖集是否可以使用相同的自定義功能單元實(shí)現(xiàn)。此任務(wù)可以看作是一個(gè)圖同構(gòu)問題，本文采用約束編程實(shí)現(xiàn)子圖同構(gòu)算法[38]。

在將功能等效的子圖映射成相同的自定義指令之后，需要在表示自定義指令的代碼之前增加一個(gè)特定的編譯指令。自定義指令用程序語言的方法來表示。這樣，高層次綜合工具就會(huì)像對(duì)其他基本指令一樣，對(duì)自定義指令進(jìn)行調(diào)度和綁定。對(duì)于高層次綜合工具CtoS(C-to-Silicon) Cadence，所有非內(nèi)聯(lián)函數(shù)都被默認(rèn)為自定義指令，即不需要特殊編譯指令。此外，自定義指令運(yùn)算特定技術(shù)的時(shí)間和面積數(shù)據(jù)通過使用RTL綜合工具獲得。自定義指令的代碼格式如圖8所示。

圖8 自定義指令集的代碼

4 結(jié)果和分析

4.1 實(shí)驗(yàn)設(shè)置

本文實(shí)驗(yàn)的環(huán)境為3.5 GHz的i7- 47704處理器。實(shí)驗(yàn)使用具有豐富算數(shù)和邏輯運(yùn)算的測(cè)試基準(zhǔn)程序，測(cè)試基準(zhǔn)程序來源于MediaBench[39]和MiBench[40]，測(cè)試基準(zhǔn)程序?qū)?yīng)的DFG包含數(shù)十個(gè)到數(shù)百個(gè)節(jié)點(diǎn)。實(shí)驗(yàn)測(cè)試基準(zhǔn)程序的特征如表1所示。其中：DFG1用于評(píng)價(jià)子圖枚舉算法的數(shù)據(jù)流圖的大小(節(jié)點(diǎn)數(shù))；DFG2用于評(píng)價(jià)選擇方法的數(shù)據(jù)流圖的大小(節(jié)點(diǎn)數(shù))。測(cè)試基準(zhǔn)程序是由通用編譯平臺(tái)GECOS進(jìn)行前端編譯和模擬，高層次綜合工具CtoS用于評(píng)價(jià)該方法對(duì)高層次綜合性能的提升和面積的減少。其中，使用tutorial.lbr作為技術(shù)庫(kù)，時(shí)鐘頻率設(shè)為50 MHz。本實(shí)驗(yàn)涉及到的測(cè)試基準(zhǔn)程序包括：MP3、點(diǎn)積(Dot Product， DOTPRODUCT)、逆離散余弦變換(Inverse Discrete Cosine Transform， IDCT)、快速傅里葉變換(Fast Fourier Transform， FFT)、速率自適應(yīng)調(diào)整(Automatic Rate Fallback， ARF)算法、無限脈沖響應(yīng)(Infinite Impulse Response, IIR)、MESA(Mesa 3D是開放源代碼的三維計(jì)算機(jī)圖形庫(kù)，本文采用求逆矩陣的測(cè)試基準(zhǔn)程序)。

表1 基準(zhǔn)程序特征

4.2 子圖枚舉效率比較

為了評(píng)價(jià)DFND算法的效率，將DFND算法與Balister等[28]提出的較新的TD(Transitive Digraph)算法以及Chen等[14]提出的經(jīng)典CMS(Chen, Maskell, Sun)算法進(jìn)行了比較，3種算法具有相同的約束條件。比較結(jié)果如表2所示，第一列代表測(cè)試基準(zhǔn)程序；NV(Number node V)和NE(Number Edge)表示DFG中的節(jié)點(diǎn)數(shù)和邊數(shù)；NS(Number Subgraph)表示枚舉出的子圖數(shù)；CT(Calculating Time)表示算法的運(yùn)行時(shí)間，單位為ms。

從表2的結(jié)果可以看出，枚舉所有的連通凸子圖是一個(gè)復(fù)雜的計(jì)算問題。當(dāng)DFG的規(guī)模較大時(shí)，枚舉所有的連通凸子圖是非常耗時(shí)的。例如，對(duì)于包含43個(gè)節(jié)點(diǎn)的基準(zhǔn)程序MP3，DFND算法需要227 s枚舉所有的連通凸子圖。實(shí)驗(yàn)結(jié)果表明，DFND算法優(yōu)于CMS算法和TD算法。與CMS算法相比，TD算法的枚舉效率平均提升了44.5%；對(duì)于基準(zhǔn)程序ARF，TD算法的枚舉效率提升了49.5%。與CMS算法相比，DFND算法的枚舉效率平均提升了83.8%。與TD算法相比，DFND算法的枚舉效率平均提升了70.8%；對(duì)于基準(zhǔn)程序MESA，DFND算法的枚舉效率提升了73.1%。

表2 子圖枚舉算法的比較

4.3 面積減少率和性能提升率比較

為了評(píng)價(jià)本文提出的選擇方法，應(yīng)用程序的源代碼和本方法產(chǎn)生的新代碼分別作為高層次綜合工具CtoS的輸入。然后，使用高層次綜合工具對(duì)兩份代碼分別進(jìn)行高層次綜合處理，表3中列Patterns和Matches分別表示候選模式和候選子圖的數(shù)目。本文提出的基于關(guān)鍵路徑的子圖選擇算法、基于出現(xiàn)頻率的模式選擇算法和基于最少子圖數(shù)的選擇算法分別表示為CS、PS、MS。符號(hào)X_P和X_M分別表示在不同選擇方法下的模式數(shù)和子圖數(shù)(如CS_P表示基于關(guān)鍵路徑選擇方法的模式數(shù)，PS_M表示基于出現(xiàn)頻率的模式選擇方法的子圖數(shù)。此外，實(shí)驗(yàn)中子圖節(jié)點(diǎn)數(shù)不超過6)。

表3 選擇的模式和子圖的數(shù)目

相比傳統(tǒng)的高層次綜合，本文提出的3種不同的子圖選擇方法對(duì)面積減少的結(jié)果如圖9所示。其中，圖9中的平均值表示對(duì)于7個(gè)基準(zhǔn)程序的平均面積減少量。實(shí)驗(yàn)結(jié)果表明，不同的基準(zhǔn)程序面積減少不相同。對(duì)于基準(zhǔn)程序MP3使用CS算法可以減少41.6%的面積，對(duì)于基準(zhǔn)程序DOTPRODUCT只減少5.5%的面積。通過觀察發(fā)現(xiàn)，兩個(gè)基準(zhǔn)程序?qū)?yīng)的DFG形狀有很大差別，基準(zhǔn)程序DOTPRODUCT對(duì)應(yīng)的DFG是一個(gè)樹形圖，而基準(zhǔn)程序MP3對(duì)應(yīng)的DFG是一個(gè)網(wǎng)狀圖。通常，網(wǎng)狀圖具有較高密度的內(nèi)部數(shù)據(jù)流。由于內(nèi)部數(shù)據(jù)流可以粗略地表示多路選擇器的數(shù)目，從具有更多內(nèi)部數(shù)據(jù)流的網(wǎng)狀圖當(dāng)中提取自定義指令可以節(jié)省大量的多路選擇器?？傮w上，PS算法較其他兩種選擇算法能減少更多的面積。

相比傳統(tǒng)的高層次綜合，本文提出的3種不同的子圖選擇方法對(duì)性能提升的結(jié)果如圖10所示。使用不同的選擇方法在性能提升方面有很大的差異：CS算法能較好地提升性能，而其他兩種算法不能提升性能，甚至可能降低性能，這主要是因?yàn)镃S算法評(píng)估了關(guān)鍵路徑長(zhǎng)度。實(shí)驗(yàn)結(jié)果表明，對(duì)于基準(zhǔn)程序DOTPRODUCT使用CS算法的性能提升達(dá)59.4%，然而，對(duì)于基準(zhǔn)程序IDCT的性能提升只有12.2%，因此對(duì)于不同的基準(zhǔn)程序，性能提升的效果差異明顯。

圖9 3種選擇算法減少面積結(jié)果比較

圖10 3種選擇算法提升性能結(jié)果比較

綜上所述，相比傳統(tǒng)的高層次綜合：采用PS算法可平均減少19.1%的面積，最高可減少37.1%的面積；同時(shí)，采用CS算法平均可獲得22.3%的性能提升，最高可達(dá)到59.4%的性能提升。相比Cong等[7-8]把自定義指令應(yīng)用到高層次綜合過程中的方法，本文方法能夠在減少面積和性能提升之間提供更好的權(quán)衡。

4.4 代碼減少率比較

為了評(píng)價(jià)代碼的減少量，使用式(6)計(jì)算代碼減少率：

RSize=((|G|-|G′|)/|G|)*100%

(6)

其中：|G|代表源代碼中的運(yùn)算指令數(shù)目，|G′|代表新代碼運(yùn)算指令的數(shù)目。

使用三種子圖選擇方法減少的代碼量如圖11所示，最少子圖數(shù)目選擇算法顯著地減少了代碼量。最少子圖數(shù)目選擇算法更傾向于選擇較大的子圖，而另外兩種算法考慮到出現(xiàn)頻率或關(guān)鍵路徑傾向于選擇較小的子圖。例如，對(duì)于基準(zhǔn)程序DOTPRODUCT，MS算法可減少81%的代碼量。該算法可平均減少74%的代碼量。通過減少代碼量，高層次綜合工具需要更短的時(shí)間去處理新代碼，進(jìn)而更快地產(chǎn)生電路設(shè)計(jì)方案。

圖11 3種選擇算法減少代碼量結(jié)果比較

5 結(jié)語

本文利用自定義指令在專用硬件中可以提升性能、減少面積和減少代碼量等優(yōu)點(diǎn)，提出了面向高層次綜合的自定義指令的自動(dòng)識(shí)別方法。該設(shè)計(jì)方法克服了現(xiàn)有研究必須在高層次綜合過程中識(shí)別自定義指令的限制。本文的DFND子圖枚舉算法可通過修改約束條件靈活地枚舉出滿足用戶需求的子圖。該算法以一種節(jié)點(diǎn)刪除技術(shù)使得一個(gè)子圖只被識(shí)別一次，顯著地降低了枚舉算法的運(yùn)行時(shí)間。此外，不同的選擇方法使高層次綜合在解決性能和能耗問題上具有一定的應(yīng)用價(jià)值，并且CS算法在面積減少、性能提升和代碼量減少之間提供了很好的折中。

針對(duì)PS算法和MS算法對(duì)部分基準(zhǔn)程序會(huì)帶來負(fù)性能提升的問題。下一步的工作是結(jié)合PS、MS、CS三種算法的優(yōu)點(diǎn)改進(jìn)子圖算法的功能函數(shù)，使子圖選擇算法能夠更好地權(quán)衡性能、面積和代碼量。