王珊珊 劉萬軍 肖成龍

(遼寧工程技術(shù)大學軟件學院 遼寧葫蘆島 125105) (celine.shanshan.wang@gmail.com)

可擴展處理器(專用指令集處理器)越來越多的被用到現(xiàn)代的電子設(shè)備中.例如Tensilica Xtensa[1]，Argonaut RISC Core (ARC)[2]，STMicroe-lectronic ST200[3]，NIOS Ⅱ[4]等.可擴展處理器通過使用自定義功能單元(custom function unit, CFU)可以在靈活性和效率之間做出很好的折中.在CFU上執(zhí)行的自定義指令封裝了一組基本指令，并通過基本指令之間的并行化和鏈化來提高性能.通過對相同領(lǐng)域的不同應用程序使用相同的自定義指令集，可以使其具有一定的靈活性[5].此外，通過使用預驗證的和預優(yōu)化的基準處理器，可以減少設(shè)計復雜性和縮短產(chǎn)品上市時間[6].

為了滿足成本約束，可擴展處理器經(jīng)常在信號處理和圖像處理等領(lǐng)域中使用.例如文獻[7]提出了一種用于加速加密算法的自定義指令集的定制方法；文獻[8]提出了一種專用于汽車應用領(lǐng)域傳感器信號調(diào)理的可擴展處理器設(shè)計.可擴展處理器設(shè)計中涉及的最關(guān)鍵的問題之一是自定義指令識別問題.

近年來，自定義指令的自動識別成為嵌入式領(lǐng)域的研究熱點之一.從程序的數(shù)據(jù)流圖中人工識別一組最佳的自定義指令耗時且容易出錯.因此，有必要構(gòu)建完全自動化的自定義指令識別的編譯流程.本文提出了一個用于識別最大自定義指令的最大凸自定義指令編譯流程如圖1所示.在設(shè)計流程中，應用程序源代碼作為前端編譯器generic compiler suite (GECOS)的輸入[9].GECOS生成應用程序?qū)目刂茢?shù)據(jù)流圖(control data-flow graph, CDFG).CDFG是表示多個基本塊之間的數(shù)據(jù)相關(guān)性的圖.基于CDFG內(nèi)的數(shù)據(jù)流圖(data-flow graph, DFG)，枚舉出所有最大凸子圖(最大凸自定義指令的圖形化表示).然后，從所有枚舉出的最大凸子圖集合當中選擇一組最佳的最大凸子圖作為最終的自定義指令.每個選定的子圖將聚合成1個虛擬節(jié)點.如果DFG仍然有未覆蓋的有效節(jié)點，則繼續(xù)執(zhí)行1次迭代(包括枚舉和選擇).此過程持續(xù)到DFG中所有的有效節(jié)點均被覆蓋.最后，將原始源代碼轉(zhuǎn)換為包含所識別的自定義指令的新源代碼.

Fig. 1 Maximal convex custom instruction compilation flow圖1 最大凸自定義指令編譯流程

考慮到計算復雜性，之前的大多數(shù)研究僅枚舉滿足基準處理器的可用寄存器讀寫端口數(shù)目限制的自定義指令.此外，可以實現(xiàn)為硬件功能單元的自定義指令應該是凸的，否則不能原子地執(zhí)行自定義指令.然而，通過使用內(nèi)部狀態(tài)寄存器，影子寄存器或Pozzi和Ienne[10]提出的技術(shù)，在大多數(shù)現(xiàn)有的可擴展處理器(諸如Tensilica Xtensa)中允許使用具有比寄存器讀寫端口更多的輸入和輸出操作數(shù)的自定義指令.此外，最近的一些研究表明枚舉和選擇最大自定義指令可以帶來更多的性能提升[6,11].本文專注于最大凸自定義指令的自動識別.

本文的主要貢獻有2個方面:

1) 提出了一種用于最大凸子圖枚舉的新算法.所提出的算法結(jié)合了自下而上的枚舉方法和自上而下的枚舉方法的優(yōu)點.相比于文獻[6,12]提出的算法，可實現(xiàn)數(shù)量級的加速.

2) 提出并實現(xiàn)了最大凸自定義指令迭代識別流程.在每次迭代中，采用高效的精確算法來選擇最佳自定義指令集.與文獻[6]中的方法相比，利用精確選擇算法，在大多數(shù)情況下可以找到用于最大化提升性能的最佳自定義指令集.

1 相關(guān)工作

本節(jié)對自定義指令自動識別過程中涉及到的2個關(guān)鍵問題：自定義指令枚舉和自定義指令選擇，分別進行分析.

1) 自定義指令枚舉.自定義指令枚舉問題是從應用程序?qū)臄?shù)據(jù)流圖中枚舉出所有滿足一定設(shè)計約束或用戶約束的凸子圖作為候選自定義指令.由于寄存器的讀寫端口的數(shù)目(IO)有限，例如 NIOS Ⅱ中的輸入輸出端口數(shù)一般為21，近期的一些研究主要是關(guān)注于枚舉滿足IO限制的子圖.文獻[13]首次證明了滿足約束條件的子圖(自定義指令的圖形化表示)數(shù)目是多項式次的；Bonzini等人[14]提出了具有多項式時間的子圖枚舉算法；文獻[15]使用約束編程解決子圖枚舉問題.然而，當應用程序?qū)臄?shù)據(jù)流圖變大時，這些方法效率不高；文獻[16]的作者首先提出了一種基于凸約束和IO約束下的二元決策樹的枚舉算法；Pozzi等人[17]通過添加基于永久輸入數(shù)量的修剪標準進一步改進了該算法；文獻[18]中提出的算法使用預過濾方法，在保留文獻[16]中算法所有優(yōu)點的同時，可以進一步修剪大量搜索空間；文獻[19]在此前的研究基礎(chǔ)上，提出了基于并行計算的子圖枚舉算法，實驗結(jié)果表明相對于串行算法，并行算法可達到近似線性的加速比；Yu和Mitra[20]通過枚舉向上的錐體型子圖和向下的錐體型子圖構(gòu)建連通子圖，然而，在這個算法中，同一子圖可能被枚舉多次.

此前的研究表明:放松輸入約束和輸出約束可以帶來更好的性能提升[11,21].例如文獻[21]的實驗顯示IO數(shù)目為21的約束下，識別自定義指令可以將DES加密算法的執(zhí)行時間計數(shù)減少到67%，而完全放松IO約束的情況下算法的執(zhí)行時間減少到56%.因此，在沒有IO約束的條件下識別自定義指令近年來已經(jīng)受到越來越多的關(guān)注.通過使用內(nèi)部狀態(tài)寄存器和影子寄存器，自定義指令枚舉問題可以被轉(zhuǎn)換為最大凸子圖(maximal convex subgraph, MCS)枚舉問題.Pothineni 等人[22]首次提出了MCS枚舉算法,該算法基于不兼容性圖枚舉MCSs,然而，該算法僅生成連通MCS.文獻[11]將等價節(jié)點分組并構(gòu)建集群圖，MCS枚舉問題被轉(zhuǎn)換為最大團枚舉問題.Atasu 等人[6]首次證明了MCS數(shù)目上限是2|VI|，其中|VI|是DFG中的無效節(jié)點集合.文獻[12] 按照自頂向下的方式通過對DFG進行分割來枚舉MCS.然而，此方法不能保證所枚舉的子圖是唯一的和最大的.

上述研究都是以自底向上方式或自頂向下的方式來枚舉MCS.自底向上方式可以通過聚合等價節(jié)點來減小DFG的大??；自頂向下的方式可以通過將DFG分解成更小的圖來減小DFG的大小.為了結(jié)合自底向上方式和自頂向下方式的優(yōu)點，本文提出了先自底向上聚合后自頂向下分割的方法來高效地枚舉MCS(夾心方法).本文還給出并證明了在給定DFG中MCS的數(shù)量上限.

2) 自定義指令選擇.在自定義指令枚舉步驟之后，自定義指令選擇步驟確定哪些枚舉的子圖應當作為最終的自定義指令，并在硬件中實現(xiàn).一般來說，在自定義指令選擇期間應該考慮的因素包括運行時性能(時鐘周期計數(shù))、面積成本、功耗和代碼量[23].一些先前的研究旨在選擇定制指令以在滿足給定面積約束的同時實現(xiàn)最佳性能提升[6,24-25].一些其他工作嘗試選擇考慮功耗約束的自定義指令[26].這些研究通常在上述因素之間進行權(quán)衡.在本文中，自定義指令選擇步驟關(guān)注于性能提升的最大化.沒有其他因素的限制，可以實現(xiàn)最佳的性能提升.文獻[6]使用一個價值函數(shù)貪婪地選擇自定義指令.然而，實驗顯示候選子圖的數(shù)量通常很少，而且很多候選子圖之間存在覆蓋關(guān)系.通過非覆蓋約束條件，可以大量地修剪搜索空間.因此，采用精確算法可以保證性能提升的最大化.

2 相關(guān)定義

數(shù)據(jù)流圖是一種有向無環(huán)圖.它是一個圖G=(V,E)，其中頂點集v={v1,v2,…,vn}表示基本指令，邊集E={e1,e2,…,em}∈V×V表示指令之間數(shù)據(jù)依賴關(guān)系.

定義1. 無效節(jié)點.由于體系結(jié)構(gòu)的限制，內(nèi)存操作和分支操作等基本指令不能包含在自定義指令中，代表這些基本指令的節(jié)點被視為無效節(jié)點.

子集VI?V表示G中的無效節(jié)點.子集V-VI表示G中的有效節(jié)點.枚舉的最大凸子圖是僅包含有效節(jié)點的圖.

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

可以實現(xiàn)為硬件功能單元的自定義指令應該是凸的，否則不能原子地執(zhí)行自定義指令.數(shù)據(jù)流圖中的凸子圖如圖2陰影部分所示.子圖{n1,n2,n3}是一個凸子圖，而子圖{n1,n2,n4}是一個非凸子圖.

Fig. 2 A data flow graph with a convex subgraph圖2 數(shù)據(jù)流圖中的凸子圖

定義3. 最大凸子圖.G中凸子圖S，其不包含無效節(jié)點，且不能通過添加VVI中的任一節(jié)點形成更大的凸子圖，則稱S為最大凸子圖.

Fig. 3 An example using the iterative design flow圖3 迭代設(shè)計流程示例

MCS識別包括2個基本步驟： MCS枚舉和MCS選擇.MCS枚舉問題是找到給定DFG中的所有MCS；MCS選擇問題是從枚舉的MCS中選擇最佳的非重疊的MCS子集.2個候選MCS可能有共同的節(jié)點.允許自定義指令間存在節(jié)點重疊，有時可以提升性能，但它也不必要地增加功耗并且使得代碼轉(zhuǎn)換變得非常困難.類似于文獻[6]中提出的方法，本文不允許任何MCS之間存在節(jié)點重疊.迭代設(shè)計流程示例如圖3所示.在第1次迭代步驟中枚舉出了2個MCS即MCS1和MCS2.由于這2個MCS具有共同的節(jié)點5，根據(jù)非重疊的規(guī)則，只能選擇MCS1或MCS2.

給定DFGG=(V,E)和節(jié)點u，G中的節(jié)點與u的關(guān)系可以定義：

1) 節(jié)點u的直接前驅(qū)節(jié)點集.IPred(G,u)={v|v∈V,(v,u)∈E}.

2) 節(jié)點u的直接后續(xù)節(jié)點集.ISucc(G,u)={v|v∈V,(u,v)∈E}.

3) 節(jié)點u的所有前驅(qū)節(jié)點集.Pred(G,u)={v∪Pred(G,v)|v∈IPred(G,u)}.

4) 節(jié)點u的所有后繼節(jié)點集.Succ(G,u)={v∪Succ(G,v)|v∈ISucc(G,u)}.

5) 節(jié)點u的分離節(jié)點集.Disc(G,u)=G-Pred(G,u)-Succ(G,u)-u.

無效節(jié)點集可以進一步分為2組.

定義4. 邊界無效節(jié)點.無效節(jié)點u是G的邊界無效節(jié)點，當且僅當Pred(G,u)∩{VVI}=?或Succ(G,u)∩{VVI}=?.

定義5. 內(nèi)部無效節(jié)點.無效節(jié)點u是G的內(nèi)部無效節(jié)點,當且僅當Pred(G,u)∩{VVI}≠? 和Succ(G,u)∩{VVI}≠?.

3 最大凸自定義指令迭代識別算法

圖3給出了從給定應用程序的數(shù)據(jù)流圖中識別MCS的過程示例.數(shù)據(jù)流圖由12個節(jié)點組成，包括11個有效節(jié)點和1個無效節(jié)點(節(jié)點I).MCS識別流程以迭代方式進行.在第1次迭代中，在MCS枚舉步驟枚舉出2個MCS即MCS1和MCS2.然后，根據(jù)非重疊規(guī)則，MCS選擇步驟僅選擇其中一個MCS(例如MCS1)作為自定義指令.MCS1內(nèi)的節(jié)點聚合到虛擬節(jié)點中，聚合之后生成的DFG作為第2次迭代的輸入.在第2次迭代中，選擇MCS3作為自定義指令.到目前為止，原始DFG中的所有有效節(jié)點都被覆蓋了.最后，源程序被轉(zhuǎn)換為包含了所識別的自定義指令的新代碼.

Fig. 4 Summary of our approach to maximal convex subgraph enumeration圖4 最大凸子圖枚舉方法示例

最大凸自定義指令的迭代識別流程的偽代碼如算法1所示.算法1接受DFG作為輸入，并產(chǎn)生一組選定的最大凸子圖作為輸出.在每次迭代中，算法1首先調(diào)用最大凸子圖枚舉算法(行③)；然后，根據(jù)候選子圖的性能增益來選擇非重疊的MCS作為自定義指令(行④～⑤).迭代結(jié)束的條件為原始DFG中所有有效節(jié)點均被自定義指令覆蓋.

算法1. 最大凸自定義指令迭代識別.

輸入：數(shù)據(jù)流圖G(V,E)；

輸出：最佳最大凸自定義指令集.

①IterativeIdentification(GraphG)；

② whileG包含有效節(jié)點do

③MCS=MCSEnumeration(G);

④ 按照性能增益對MCS中的最大凸子圖排序;

⑤ 選擇最佳的非重疊最大凸子圖子集;

⑥ 在圖G中將選擇的每個最大凸子圖聚合成單個節(jié)點;

⑦ end while

4 最大凸自定義指令枚舉算法

本節(jié)提出了一種結(jié)合自下而上方法和自頂向下方法的夾心枚舉算法.該算法首先刪除邊界無效節(jié)點；然后，通過自下而上的方式聚合節(jié)點；最后，采用自上而下的分割方法將DFG分割成更小的圖，最終生成所有最大凸子圖.最大凸子圖枚舉方法示例如圖4所示:

4.1 預處理

根據(jù)定義，邊界無效節(jié)點在VVI沒有前導，或者在VVI中沒有后繼.因此，可以將邊界無效節(jié)點DFG中移除而不會影響最大凸子圖枚舉的結(jié)果.例如在圖4中，從DFG中移除邊界無效節(jié)點I4和I5不會影響最大凸子圖的枚舉結(jié)果.在實際的應用程序?qū)臄?shù)據(jù)流圖中存在著大量無效節(jié)點.移除所有邊界無效節(jié)點的預處理可以最大地減少DFG中的無效節(jié)點數(shù)目，進而減少自頂向下分割步驟中涉及的遞歸次數(shù).

4.2 自下而上聚合

1) 有效節(jié)點聚合.如果2個有效節(jié)點u和v滿足Pred(G,u)∩VI=Pred(G,v)∩VI和Succ(G,u)∩VI=Succ(G,v)∩VI，則將節(jié)點u和節(jié)點v聚合成1個節(jié)點.通過有效節(jié)點聚合在保證最大凸子圖的枚舉結(jié)果不受影響的同時，可以大大減少DFG中的有效節(jié)點數(shù)目，從而減少枚舉算法的運行時間.

2) 內(nèi)部無效節(jié)點聚合.由于在預處理步驟中刪除了所有邊界無效節(jié)點，可以通過聚合內(nèi)部無效節(jié)點進一步減小DFG中的無效節(jié)點數(shù)目和減少自頂向下分割過程中涉及的遞歸次數(shù).G中的2個內(nèi)部無效節(jié)點u和v，如果這2個節(jié)點滿足以下3個條件之一，則u和v可以聚集到1個節(jié)點中，而不影響最大凸子圖枚舉的結(jié)果:

①Pred(G,u)∩{VVI}=Pred(G,v)∩{VVI};

②Succ(G,u)∩{VVI}=Succ(G,v)∩{VVI};

③Pred(G,u)?Pred(G,v)且Succ(G,u)?Succ(G,v).

內(nèi)部無效節(jié)點聚合的示例如圖4所示.內(nèi)部無效節(jié)點I2和節(jié)點I3滿足條件:

Succ(G,I2)∩{VVI}=Succ(G,I3)∩{VVI}，

I2和I3可以聚合成1個無效節(jié)點I6.本文的內(nèi)部無效節(jié)點的聚合方法和文獻[6]的主要區(qū)別是：本文不僅聚集在VVI中具有相同后繼集合或相同前驅(qū)集合的內(nèi)部無效節(jié)點(條件①,②)，而且滿足第3個條件的2個節(jié)點也可以聚合成1個節(jié)點.而文獻[6]中的方法只能聚合滿足條件①,②之一的內(nèi)部無效節(jié)點.圖5中，使用本文提出的內(nèi)部無效節(jié)點聚合方法，無效節(jié)點I1和無效節(jié)點I2滿足Pred(G,I2)?Pred(G,I1)且Succ(G,I2)?Succ(G,I1)，2個節(jié)點可以聚集成1個節(jié)點I.但是，文獻[6]提出的聚合方法無法集合這2個節(jié)點.

Fig. 5 Invalid nodes clustering圖5 無效節(jié)點聚合

4.3 自頂向下分割

(1)

例如圖4中，在預處理和自底向上聚合之后生成了一個由5個有效節(jié)點和2個無效節(jié)點(I1和I6)組成的圖.首先選擇無效節(jié)點I1作為分割點，根據(jù)式(1)導出2個新的子圖G1和G2;然后，選擇無效節(jié)點I6作為分割點，G1進一步分成2個子圖(G11和G12).由于G11和G12中沒有無效節(jié)點，因此G11和G12即為MCS.

Fig. 6 Selection of invalid nodes for division operations圖6 無效節(jié)點的選擇對分割操作的影響

然而，選擇哪個無效節(jié)點作為分割點對算法運行效率起關(guān)鍵作用.無效節(jié)點的選擇對分割操作的影響如圖6所示.在圖6(a)中，首先選擇無效節(jié)點I2進行分割，最終得到4個子圖，其中子圖{1}并非最大凸子圖.在這種情況下，需要檢查子圖是否為最大凸子圖，這樣會額外增加算法的運行時間.然而，如果首先選擇無效節(jié)點I1進行分割，則所有生成的凸子圖都是最大凸子圖,如圖6(b)所示.這樣不需要額外地檢查來判斷生成的子圖是否為最大凸子圖.觀察發(fā)現(xiàn)，這是因為無效節(jié)點I1具有私有前驅(qū)和私有后繼，而無效節(jié)點I2不具有私有后繼.(無效節(jié)點的直接前驅(qū)或直接后繼稱為u的私有前驅(qū)或u的私有后繼，當且僅當它是有效節(jié)點，并且不是任何其他無效節(jié)點的前驅(qū)或后繼).

定理1. 給定1個無效的節(jié)點u，u至少有1個私有前驅(qū)或至少1個私有后繼，那么在Disc(Gcur,u)中沒有MCS.

證明. 假設(shè)在Disc(Gcur,u)中有1個MCS為m.如果u有1個私有前驅(qū)v，那么v不是任何其他無效節(jié)點的前驅(qū).此外，v不能是Disc(Gcur,u)中任何無效節(jié)點的后繼.因此，v可以添加到m以形成更大的最大凸子圖.這與假設(shè)m是最大凸子圖矛盾.

證畢.

算法2. 最大凸子圖枚舉算法.

輸入：數(shù)據(jù)流圖G(V,E)、無效節(jié)點集VI；

輸出：最大凸子圖集.

①MCSEnumeration(GraphG);

②CHECK=False;

③ 預處理: 移除邊界無效節(jié)點;

④ 聚合: 有效節(jié)點聚合及無效節(jié)點聚合;

⑥ ifCHECK=True then

⑦ 進行最大化檢查和冗余檢查;

⑧ end if

⑨Divide(GraphG,InvalidNodeSetVI)；

⑩ ifG=?

基于本文的分割算法，可以得到給定DFG中的MCS數(shù)量的上限由定理2確定.

證畢.

本文提出自下而上的聚合方法產(chǎn)生的無效節(jié)點的數(shù)目通常小于通過在文獻[6]中提出的聚合方法.因此，MCS數(shù)量的上限比文獻[6]中給出的上限更小.

5 自定義指令選擇

在自定義指令枚舉步驟之后，現(xiàn)在的任務(wù)是從所有枚舉出的最大凸子圖當中選擇最佳的子集作為最終的自定義指令.由于本文的目標是最大化提升性能，所以使用性能增益評估每個候選最大凸自定義指令.每個自定義指令S的性能增益P(S)可定義為該自定義指令S的硬件實現(xiàn)相比于用軟件實現(xiàn)的性能提升(以時鐘數(shù)表示)，即：

(2)

在文獻[6]中，作者提出了一個價值函數(shù)來判定候選自定義指令的優(yōu)先等級，以便在每次迭代中貪婪地選擇等級高的MCS作為最終的自定義指令.然而，實驗中發(fā)現(xiàn)枚舉出的候選MCS的數(shù)量通常非常小.此外，通過應用非重疊規(guī)則，可以大大減少搜索空間.因此，采用精確算法來選擇自定義指令可以保證最大化提升性能.

首先根據(jù)MCS之間的重疊關(guān)系，構(gòu)建出兼容圖.此兼容圖為無向圖，其中每個節(jié)點對應于由枚舉步驟生成的MCS.如果2個MCS——MCSi和MCSj——不存在共同的節(jié)點，則在MCSi和MCSj對應的2個節(jié)點之間建立1條邊.每個節(jié)點分配有相應MCS的性能增益.因此，自定義指令選擇問題被轉(zhuǎn)換為典型的帶權(quán)最大團問題.帶權(quán)最大團問題的最大團對應于自定義指令選擇問題的最佳子集.一個具有5個節(jié)點的兼容圖的示例如圖7所示.每個節(jié)點被賦予權(quán)重(或性能增益).此示例的最大團是{MCS1,MCS2,MCS5}.

Fig. 7 An example of building compatibility graph圖7 兼容圖構(gòu)建示例

在構(gòu)建兼容圖之后，使用分支定界的方式尋找最大團.在該算法中，所有候選MCS根據(jù)性能增益以降序排序.算法在分支定界搜索之前首先用貪婪算法生成一個解決方案.一方面，貪婪解決方案提供了一個很好的下限，可以在分支定界過程中快速修剪搜索空間；另一方面，獲得的貪婪解決方案可以保證如果算法運行太長時間，則至少獲得不劣于貪婪的解決方案.在搜索過程中，如果當前解決方案比目前為止的最佳解決方案好，則更新下限.

6 實驗與結(jié)果分析

本實驗的環(huán)境為 i3-3240 3.4 GHz處理器、4 GB主存儲器、操作系統(tǒng)為Windows 8.測試基準集來源于MediaBench[27]和MiBench[28]，這些基準是由通用編譯平臺GECOS[8]進行前端編譯和模擬的.實驗中使用的數(shù)據(jù)流圖特征如表1所示:

Table 1 Characteristics of the Data Flow Graphs of

列|V|、列|VI|和列|V-VI|分別表示數(shù)據(jù)流圖中節(jié)點的數(shù)目、無效節(jié)點的數(shù)目和有效節(jié)點的數(shù)數(shù)目.實驗主要分為2個部分：自定義指令枚舉算法運行時間的比較和自定義指令對性能提升的比較.

6.1 預處理和聚合結(jié)果比較

在實驗中，首先本文提出的自下而上聚合方法與在文獻[6]中提出的聚合方法進行比較.為了詳細比較聚合方法的效果，本實驗分別評估有效節(jié)點和無效節(jié)點聚合之后的數(shù)量變化.2種聚合方法的結(jié)果見如表2所示.

由于本文中的預處理和有效節(jié)點聚合與文獻[6]中的方法相同，通過預處理和有效節(jié)點聚合，2個方法獲得的結(jié)果是相同的(列Preprocessing和列Valid Nodes Clustering).從表2可以看出，在預處理和有效節(jié)點聚合之后，無效節(jié)點的數(shù)量和有效節(jié)點的數(shù)量極大地減少.還可以觀察到，本文提出的無效節(jié)點聚合方法優(yōu)于文獻[6]中的無效節(jié)點聚合方法.對于測試基準程序Blowfish，JPEG，DES3，本文的聚合方法將無效節(jié)點的數(shù)量分別減少到49,8,16，而文獻[6]中的方法只能將無效節(jié)點的數(shù)量減少到53,10,19.

Table 2 Preprocessing and Clustering Results表2 預處理和聚合結(jié)果比較

6.2 最大凸自定義指令枚舉算法運行時間比較

為了評估所提出的枚舉算法的運行時間，將本文提出的最大凸子圖枚舉算法(表示為MS)與文獻[12]中的自頂向下枚舉算法(表示為TD)和文獻[6]中的自底向上算法(表示為ILP)進行了比較.為了比較的公平性，所有相關(guān)的算法在相同的開發(fā)環(huán)境中實現(xiàn)，并且使用相同的數(shù)據(jù)結(jié)構(gòu)表示MCS.

Table 3 Comparison of MCS Enumeration Algorithms表3 MCS枚舉算法運行時間比較

實驗結(jié)果表明：本文提出的算法MS顯著快于算法TD和算法ILP.可以觀察到：對于包含少于100個無效節(jié)點的測試基準程序，相比于自頂向下的算法TD，本文的算法可以達到5.6～47.3倍的加速.對于具有超過100個無效節(jié)點的測試基準程序，算法MS相對于算法TD的加速更加顯著，為15.9～111倍.對于測試基準程序MPEG2，算法MS需要102 s產(chǎn)生超過1 600萬個MCS，而算法TD無法在10 h內(nèi)產(chǎn)生結(jié)果.由于算法TD無法在合理的實間內(nèi)產(chǎn)生所有的結(jié)果，在算法TD中添加了一個計時器(時間設(shè)為102 s).當計時器設(shè)定的時間結(jié)束時，算法TD停止枚舉.實驗中觀察到算法TD枚舉的子圖數(shù)量約為1 400萬.在這些枚舉的子圖中，存在大量的子圖是冗余的或非最大的.此外，從算法MS枚舉的MCS中選擇定制指令之后，對測試基準程序的性能提升是2.85倍.而從算法TD枚舉的子圖中選擇自定義指令所達到的性能提升只有2.4倍.

相比于算法TD，算法MS的運行時間的減少主要有3個原因：

1) 通過預處理和無效節(jié)點聚合之后可以去除相當多數(shù)量的無效節(jié)點，使得二叉查找樹的搜索空間大量減少.例如對于測試基準程序Blowfish和GSM，在預處理和無效節(jié)點聚合之后，無效節(jié)點的數(shù)量分別減少為49和0.

2) 有效節(jié)點聚合可以減小DFG的大小，這有助于減少諸如式(1)中的計算時間.例如對于測試基準程序JPEG，通過有效節(jié)點聚合之后，有效節(jié)點的數(shù)量從187減少到26.

3) 選擇具有私有前驅(qū)和私有后繼的無效節(jié)點可以避免產(chǎn)生冗余或非最大凸子圖.如圖6(a)所示，根據(jù)算法TD中提出的無效節(jié)點選擇策略，其首先選擇無效節(jié)點I2來分割圖.在這種情況下，枚舉出非最大子圖{1}，導致額外的搜索空間.此外，需要執(zhí)行最大化檢查以過濾掉非最大子圖，這也極大地增加了算法的運行時間.相反，本文提出的枚舉算法選擇無效節(jié)點I1來分割圖.所有枚舉出的子圖都是唯一的最大凸子圖.

實驗結(jié)果顯示，對于測試基準程序SHA，GSM和ADPCM，算法MS運行時間和算法ILP的運行時間相當.分析發(fā)現(xiàn)測試基準程序SHA，GSM和ADPCM中的無效節(jié)點均為邊界無效節(jié)點，經(jīng)過預處理(算法MS和算法ILP的預處理相同)，無效節(jié)點的數(shù)目為零，因此預處理之后的圖為唯一的MCS.所以算法MS運行時間和算法ILP的運行時間一樣.然而，對于測試基準程序DES3，JPEG，EPIC，算法MS相對于算法ILP的加速比分別為15.6倍，16.4倍,31.2倍.

相比于算法ILP，算法MS的運行時間的減少主要有2個原因：

1) 算法ILP不能保證枚舉的凸子圖是最大的，并且可能多次生成相同的子圖.在這種情況下，需要額外的最大性檢查和冗余校驗來獲得MCS，而最大化檢查和冗余校驗非常耗時.算法MS總是優(yōu)先選擇具有私有前驅(qū)和私有后繼的無效節(jié)點進行分割，這樣可以避免生成冗余MCS.只有當沒有具有私有前驅(qū)和私有后繼的無效節(jié)點作為分割點時，才需要執(zhí)行冗余檢查和最大化檢查.

6.3 性能提升

本節(jié)將所提出的自定義指令選擇方法所實現(xiàn)的性能提升與文獻[6]中提出的啟發(fā)式選擇方法實現(xiàn)的性能提升進行比較.

在實驗中，比照文獻[29-30]，假定基準處理器是單發(fā)射流水線結(jié)構(gòu)的處理器.乘法指令的軟件時延為2個周期，其余指令的軟件時延均為1個周期.自定義功能單元中實現(xiàn)的基本指令的硬件延遲信息如表4所示：

Table4HardwareTimingoftheOperationsImplementedintheCustomFunctionUnits

表4 自定義功能單元中指令的硬件延遲信息

假定包含多個節(jié)點的自定義指令在自定義功能單元上執(zhí)行，而應用程序中未被包含進自定義指令的基本指令在基準處理器上執(zhí)行.給出了使用自定義指令應用程序總時延的計算：

(3)

其中,HW(i)表示自定義指令i的硬件延遲;T(S)表示傳輸自定義指令的輸入和輸出操作數(shù)所需的額外時延.式(3)等號右邊的第1項表示所選自定義指令累積硬件時延的總和(SC表示所選自定義指令的集合，C(S)表示是位于所選自定義指令S的關(guān)鍵路徑上的節(jié)點)；式(3)等號右邊第2項表示未包含進自定義指令的基本指令的累積軟件時延(PI表示未包含的基本指令的集合).

通過使用最大凸自定義指令實現(xiàn)性能提升的計算：

(4)

其中，式(4)等號右邊是原始應用程序的源代碼中所有基本指令的累積軟件時延(n表示原始代碼中基本指令的數(shù)量).

精確選擇算法和啟發(fā)式選擇算法[6]所獲得的性能提升的對比，如圖8所示.在實驗中，假設(shè)核心寄存器有2個輸入端口和1個輸出端口.使用式(4)計算相應的性能提升，可以觀察到本文提出的方法優(yōu)于文獻[6]中提出的方法.例如對于測試基準程序DES3，本文方法實現(xiàn)的性能提升是5.8倍，而使用文獻[6]中的方法實現(xiàn)的性能提升是5.2倍.對于測試基準程序SHA，GSM，ADPCM，MPEG2，2種方式達到相同的性能提升.這是因為對于測試基準程序SHA，GSM，ADPCM，只枚舉出了一個候選MCS(見表3).因此，精確算法和啟發(fā)式算法的選擇結(jié)果是相同的.對于測試基準程序MPEG2，由于候選MCS的數(shù)量太大，精確算法提供與文獻[6]中的算法相同的結(jié)果.

Fig. 8 Performance improvement of two algorithm[6]圖8 2種算法[6]對性能提升的比較

7 總 結(jié)

本文提出了一種用于求解最大凸子圖枚舉問題的高效算法.該算法以夾心方式生成所有最大凸子圖.夾心方式通過組合自下而上枚舉方法和自頂向下方法，充分利用2種方法的優(yōu)勢.與最新算法相比，提出的方法可以實現(xiàn)數(shù)量級的加速，同時保證生成相同的所有最大凸子圖集.此外，本文提出了使用精確選擇算法的迭代識別流程，選擇能夠最大化提升性能的自定義指令集.與此前的啟發(fā)式選擇算法相比，所提出的精確選擇算法可以實現(xiàn)對應用程序的更好的性能提升.

本文專注于選擇最大凸自定義指令以最大化提升性能.由于低功耗已成為嵌入式領(lǐng)域研究的熱點，因此在執(zhí)行自定義指令識別時考慮功耗約束是很有必要的,這也是將來研究工作的重點之一.