王珊珊 劉萬軍 肖成龍

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

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

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

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

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

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

本文的主要貢獻(xiàn)有2個(gè)方面:

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

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

1 相關(guān)工作

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

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

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

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

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

2 相關(guān)定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

無效節(jié)點(diǎn)集可以進(jìn)一步分為2組.

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

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

3 最大凸自定義指令迭代識(shí)別算法

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

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

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

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

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

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

①IterativeIdentification(GraphG)；

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

③MCS=MCSEnumeration(G);

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

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

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

⑦ end while

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

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

4.1 預(yù)處理

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

4.2 自下而上聚合

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

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

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

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

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

4.3 自頂向下分割

(1)

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

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

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

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

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

證畢.

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

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

輸出：最大凸子圖集.

①M(fèi)CSEnumeration(GraphG);

②CHECK=False;

③ 預(yù)處理: 移除邊界無效節(jié)點(diǎn);

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

⑥ ifCHECK=True then

⑦ 進(jìn)行最大化檢查和冗余檢查;

⑧ end if

⑨Divide(GraphG,InvalidNodeSetVI)；

⑩ ifG=?

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

證畢.

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

5 自定義指令選擇

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

(2)

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

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

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

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

6 實(shí)驗(yàn)與結(jié)果分析

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

Table 1 Characteristics of the Data Flow Graphs of

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

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

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

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

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

6.2 最大凸自定義指令枚舉算法運(yùn)行時(shí)間比較

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

Table 3 Comparison of MCS Enumeration Algorithms表3 MCS枚舉算法運(yùn)行時(shí)間比較

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

相比于算法TD，算法MS的運(yùn)行時(shí)間的減少主要有3個(gè)原因：

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

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

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

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

相比于算法ILP，算法MS的運(yùn)行時(shí)間的減少主要有2個(gè)原因：

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

6.3 性能提升

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

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

Table4HardwareTimingoftheOperationsImplementedintheCustomFunctionUnits

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

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

(3)

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

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

(4)

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

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

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

7 總 結(jié)

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

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