基于整數(shù)線性規(guī)劃的VLIW DSP指令分簇調(diào)度

摘要：在分簇VLIW DSP上，指令分簇是一項對程序性能有重要影響的編譯優(yōu)化，但現(xiàn)有的指令分簇算法只能處理順序的程序區(qū)域，且難以獲得最佳的分簇方案。針對這些問題，提出一種基于整數(shù)線性規(guī)劃的統(tǒng)一指令分簇與指令調(diào)度的方法。該方法使用0-1決策變量表示函數(shù)中指令的分簇、指令的局部調(diào)度以及簇間傳輸指令的全局調(diào)度，并將指令之間的依賴關(guān)系和對處理器資源的競爭關(guān)系構(gòu)造為線性約束，最終得到一個以最小化函數(shù)的估計執(zhí)行時間為目標的整數(shù)線性規(guī)劃模型。實驗結(jié)果表明，求解該模型得到的分簇調(diào)度方案對程序性能的優(yōu)化顯著強于現(xiàn)有算法，并且求解模型所耗費的時間是可接受的。

關(guān)鍵詞：數(shù)字信號處理器； 超長指令字； 指令分簇； 指令調(diào)度； 整數(shù)線性規(guī)劃

中圖分類號：TP314文獻標志碼：A

文章編號：1001-3695（2022）10-030-3078-06

doi：10.19734/j.issn.1001-3695.2022.03.0120

Integer linear programming based instruction cluster assignment schedule of VLIW DSP

Zhou Penga，b， Liu Chunganga，b， Zheng Qilonga，b

（a.School of Computer Science amp; Technology， b.Key Laboratory of High Performance Computing of Anhui Province， University of Science amp; Technology of China， Hefei 230026， China）

Abstract：Cluster assignment is a compiler optimization that plays an important role in performance of programs. However， the existing algorithms only work on straight-line program area， and is difficult to be optimal. Aiming at these problems， this paper proposed a unified cluster assignment and instruction scheduling method based on integer linear programming. This method used 0-1 decision variables to represent cluster assignment， local instruction scheduling and global scheduling of inter-cluster transfer instructions， and formulated dependency and processor resources competition between instructions into linear constraints， eventually got an integer linear programming model whose objective was to minimize the estimated execution time of the function. Experimental results show that the cluster assignment and scheduling scheme from solving the model significantly outperforms the existing algorithms on accelerating programs， and the time required to solve the model is acceptable.

Key words：digital signal processor（DSP）; very long instruction word（VLIW）; cluster assignment; instruction scheduling; integer linear programming

0引言

許多數(shù)字信號處理器（DSP）采用超長指令字（VLIW）架構(gòu)來提高指令級并行（instruction level parallelism，ILP）。VLIW架構(gòu)DSP一般發(fā)射寬度較大，需要大量的運算設(shè)備和寄存器文件。讓所有運算設(shè)備與所有寄存器直接連通會使處理器的設(shè)計復(fù)雜度較高，且功耗較大［1］。解決這個問題的一個方法是將運算設(shè)備和寄存器分為多個簇，每簇中運算設(shè)備與寄存器數(shù)目相同，簇內(nèi)的運算設(shè)備能直接訪問內(nèi)部寄存器文件，不同簇之間通過總線連通，跨簇訪問數(shù)據(jù)需要將其他簇的數(shù)據(jù)復(fù)制到本地簇內(nèi)。這樣的分簇架構(gòu)中，簇內(nèi)的數(shù)據(jù)訪問延遲低、功耗低，而不同簇之間的數(shù)據(jù)訪問延遲高、功耗高。

在分簇架構(gòu)的處理器上，需要確定指令使用哪一個簇的運算資源，這一操作稱為分簇（cluster assignment）。在一些早期的處理器上，分簇由硬件自動完成［2］。在現(xiàn)代的分簇VLIW DSP上，分簇由編譯器完成，如由中國電子科技第38研究所研發(fā)的HXDSP。分簇的目的是讓程序充分利用不同簇上的運算資源，同時避免過多的簇間通信，從而提高程序的指令級并行度，這使得分簇與指令調(diào)度這項編譯優(yōu)化緊密相關(guān)。在早期的工作中，分簇是一項獨立的優(yōu)化［3～6］，分簇完成后再進行指令調(diào)度，更近的一些工作則同時進行指令的分簇與調(diào)度［7～10］。

當前的各種分簇方法在基本塊或者trace［11］這樣的無分支的程序區(qū)域上進行分簇，不同的方法之間的主要區(qū)別在于采用了不同的啟發(fā)因子確定指令被分派的簇。這些方法欠缺對全局數(shù)據(jù)流的處理，忽視了不同基本塊中的指令之間的簇間通信開銷，盡管在trace中分簇考慮了多個基本，但在很多程序中不同分支的跳轉(zhuǎn)情況難以估計，不容易構(gòu)造trace。另一問題是基于啟發(fā)式?jīng)Q策的方法并不能保證得到最優(yōu)的分簇方案，啟發(fā)式方法的優(yōu)點在于算法執(zhí)行速度快，但在DSP的應(yīng)用領(lǐng)域中，耗費更多的編譯時間以實現(xiàn)更好的分簇方案，獲得更高的執(zhí)行性能往往是可以接受的。

組合優(yōu)化是一類尋找問題最優(yōu)解的方法，其中整數(shù)線性規(guī)劃是一種形式簡單但被廣泛使用的方法，在編譯優(yōu)化領(lǐng)域中也有不少應(yīng)用，如指令調(diào)度［12，13］、超字并行［14］。考慮到當前的分簇算法不能保證最優(yōu)的現(xiàn)狀，使用整數(shù)線性規(guī)劃進行分簇，進一步提高指令分簇的質(zhì)量是比較好的選擇。本文的主要貢獻是提出了一種VLIW DSP上的指令分簇與調(diào)度的整數(shù)線性規(guī)劃建模方法，將整個函數(shù)中每條指令的分簇、每個基本塊的指令調(diào)度以及分簇導(dǎo)致的簇間傳輸指令的插入位置和調(diào)度表示為一個整數(shù)線性規(guī)劃模型。相比于現(xiàn)有的分簇方法，本文方法以函數(shù)為單位進行分簇，解決了全局數(shù)據(jù)流之間的簇間傳輸指令的插入問題，并且求解得到的分簇調(diào)度方案是（在估計的代價模型下）最優(yōu)的，此方法可以直接實現(xiàn)在其他程序區(qū)域上，如只考慮循環(huán)內(nèi)部的代碼、基本塊或者trace等，當實現(xiàn)在無分支的程序區(qū)域上時，執(zhí)行時間可以準確地評估，得到的分簇調(diào)度方案便是真正上最優(yōu)的。

1相關(guān)工作

最早的指令分簇方法由Ellis［3］在Bulldog編譯器中實現(xiàn)，稱為BUG（bottom up greedy）算法，此方法基于一項稱為完成時刻（completion cycle）的啟發(fā)因子進行分簇。指令關(guān)于某個簇的完成時刻定義為：將指令分派到該簇執(zhí)行完成后，并將數(shù)據(jù)傳輸?shù)搅饕蕾嚭罄^所在的候選簇的最晚時刻。BUG算法從每個無后繼的指令節(jié)點開始，逆向深度優(yōu)先遍歷數(shù)據(jù)流圖，每次選擇使指令完成時刻最小的簇作為當前指令的候選簇，依次對所有依賴前驅(qū)分簇，所有前驅(qū)分簇完畢后再將當前指令分派到某一個完成時刻最小的簇。

BUG算法貪心地分簇并不能保證將所有位于關(guān)鍵路徑上的指令分派到同一個簇，而且基于最小化完成時間的分簇可能導(dǎo)致首次深度優(yōu)先遍歷數(shù)據(jù)流圖時將一部分有數(shù)據(jù)流依賴的指令分散到不同簇。Lowney等人［4］在實現(xiàn)BUG算法時進行了一些改進，將數(shù)據(jù)流圖分為多個部件，每個部件內(nèi)部并行度較低、數(shù)據(jù)共享度高，在BUG算法中計算完成時刻時，若兩個相關(guān)部件（一個的數(shù)據(jù)被另一個使用）存在于不同的簇中，則在完成時刻上施加一個較大的懲罰值，從而實現(xiàn)若干相關(guān)的部件分派到同一個簇，避免簇間通信代價過大。Desoli［5］采用一個多階段的迭代算法實現(xiàn)分簇，首先采用類似BUG的算法得到初步的分簇，但分簇的依據(jù)是最小化簇間通信量，然后迭代地進行列表調(diào)度［15］，根據(jù)執(zhí)行時鐘周期數(shù)、寄存器壓力、簇間通信量調(diào)整分簇，直到穩(wěn)定。列表調(diào)度是最為廣泛使用的指令調(diào)度框架，它根據(jù)一些啟發(fā)因子如指令在數(shù)據(jù)依賴圖中的高度、后繼的數(shù)目等對數(shù)據(jù)依賴圖進行帶優(yōu)先級的拓撲排序，按照此拓撲順序依次盡可能早地發(fā)射每一條指令。Lapinskii等人［6］按照最遲調(diào)度時刻、松弛度（最遲調(diào)度時刻與最早調(diào)度時刻之差）、數(shù)據(jù)流后繼數(shù)目這三個因素對指令排序，按照這個順序訪問每條指令，將指令分派到使計算設(shè)備使用代價、總線使用代價、簇間通信代價的帶權(quán)和最小的簇。在完成初步分簇后，此方法迭代地對不同簇的邊緣指令（與其他簇存在通信的指令）進行“擾動”，嘗試將其分派到其他簇看能否得到更優(yōu)的結(jié)果以進一步提高分簇效果。Ozer等人［7］首次提出了統(tǒng)一指令分簇與調(diào)度的方法，稱為UAS（unified assignment and sche-duling）。UAS在列表調(diào)度的框架下進行，根據(jù)指令的數(shù)據(jù)流依賴前驅(qū)指令的完成時間（UAS稱為completion-weighted predecessor（CWP），在BUG稱為開始時刻（start cycle），當前指令開始時刻等于依賴前驅(qū)完成時刻的最大值）決定當前待調(diào)度指令的被分派的簇，并盡可能早地發(fā)射當前指令和其所需的簇間傳輸指令。Kailas等人［8］提出的CARS代碼生成框架基于列表調(diào)度實現(xiàn)了統(tǒng)一的指令分簇和調(diào)度以及寄存器分配的算法，在CARS中指令分簇依然采用了開始時刻作為分簇的啟發(fā)因子。Zhang等人［9］提出了一個精心構(gòu)造的啟發(fā)因子，稱為lmax-succesor-tree-consistent deadline，定義為對指令及其所有后繼的任意一種可行的分簇調(diào)度方案（每條指令的發(fā)射時刻都不超過給定的上界）中該指令最晚的執(zhí)行完成時間。這個方法在列表調(diào)度框架下選擇此啟發(fā)因子最小的就緒指令，將其分派到能盡早發(fā)射的簇上，并確定發(fā)射時刻。Porpodas等人［10］提出的LUCAS算法綜合了開始時刻與完成時刻作為啟發(fā)因子，在列表調(diào)度框架下，當面臨擁塞（就緒指令數(shù)目gt;發(fā)射寬度×簇間通信延遲）或高松弛度（松弛度gt;發(fā)射寬度×2（簇間通信延遲-1），松弛度為指令最遲調(diào)度時刻減去最早調(diào)度時刻）時選擇使開始時刻最小的分簇，否則選擇使指令完成時刻最小的分簇。王玉林等人［16］則使用模擬退火算法進行分簇與調(diào)度，將調(diào)度后的時鐘周期作為反饋迭代地提高分簇質(zhì)量。一些工作將分簇與循環(huán)的模調(diào)度一同實現(xiàn)，在對循環(huán)軟件流水化時考慮指令的分簇［17，18］，這些方法能有效地提升程序的性能，但循環(huán)軟件流水要求循環(huán)內(nèi)無分支，或者分支情況比較簡單，能使用if-conversion［19］轉(zhuǎn)換為謂詞指令再實現(xiàn)軟件流水［20］，限制較大。

本文方法實現(xiàn)在編譯器令選擇之后、寄存器分配之前，以整個函數(shù)為輸入，函數(shù)表示為控制流圖，每個基本塊表示為數(shù)據(jù)依賴圖。

整數(shù)線性規(guī)劃是指變量取值為整數(shù)的線性規(guī)劃，定義為給定一系列整數(shù)變量x=（x1，x2，…，xn）T，稱為決策變量，在滿足一系列不等式Ax≥b以及x1，x2，…，xn≥0的條件下，使線性函數(shù)cTx最小，其中A是一個實數(shù)矩陣，c是一個實數(shù)向量。決策變量取值僅為0或1的整數(shù)線性規(guī)劃稱為零一規(guī)劃，是一種常見的建模方式。

本文中指令分簇與調(diào)度都使用零一規(guī)劃來建模，主要決策變量以及相關(guān)符號如表1所示。約束規(guī)則可以粗略地分為指令出現(xiàn)次數(shù)約束、資源約束和依賴約束三類，優(yōu)化目標為每個基本塊執(zhí)行時間的帶權(quán)和，權(quán)值為基本塊的估計執(zhí)行次數(shù)，基本塊執(zhí)行時間使用最后一條指令的發(fā)射時刻表示。

2簇間傳輸指令

考慮任意變量v，它可能因為定義它的指令被分派到不同簇而出現(xiàn)在不同簇，使用v的指令也可能被分派到其他不同的簇，所以需要簇間傳輸指令來傳遞v。傳輸變量v所有可能的簇間傳輸指令x（v，m1，m2）共有M（M－1）種，這些簇間傳輸指令可能被調(diào)度到定義與使用v之間的任意一條路徑上的任意基本塊中。為了表示這些調(diào)度結(jié)果，對于每種簇間傳輸指令x（v，m1，m2），在這些路徑中的每個基本B中決策變量τB，x（v，m1，m2），t都有定義。例如，對于圖1的控制流圖，定義使用變量v的路徑包括A→E，A→E→F，B→C→E，B→C→E→F，B→D→F五條路徑，因此在A、B、C、D、E、F上關(guān)于傳遞v的簇間傳輸指令的決策變量τ都應(yīng)當有定義，否則無法表達所有可能的簇間傳輸指令插入方案，圖2～4顯示了幾種分簇與簇間傳輸指令插入方案（圖中簇間傳輸指令形如Xv=Yv，表示將v從簇Y傳遞到X），可見簇間傳輸指令可以出現(xiàn)在圖中每個基本塊中。

但簇間傳輸指令只出現(xiàn)在輸入函數(shù)中已有的基本塊中，并不一定是最優(yōu)方案。考慮如圖5所示的控制流圖，當I1和I4被分派到不同簇時，若將簇間傳輸指令插入在A中則會導(dǎo)致在程序執(zhí)行路徑為A→C的情況下會執(zhí)行一條多余的指令，如圖6所示。若插入在D中，當程序執(zhí)行路徑為B→D時，則執(zhí)行該簇間傳輸會導(dǎo)致數(shù)據(jù)錯誤，如圖7所示。這種情況的解決方案是將簇間傳輸指令插入在路徑A→D之間新構(gòu)建的基本塊中，如圖8所示，確保僅在程序執(zhí)行該路徑時簇間傳輸指令才會被執(zhí)行。盡管這樣可能引入新的跳轉(zhuǎn)指令，導(dǎo)致較長延遲，但若存在較多的簇間傳輸指令插入，重復(fù)執(zhí)行無用指令浪費的時鐘周期可能更大。

重復(fù)執(zhí)行與額外的跳轉(zhuǎn)開銷之間的權(quán)衡會在整數(shù)線性規(guī)劃求解中得到最佳的選擇，但必須保證解空間中存在這樣的方案。因此，對于任意控制流圖的邊，若其起點有多條出邊，終點有多條入邊，則需要在該邊上構(gòu)建一個新的基本塊，若該邊是直接下落邊（即前后兩個基本塊地址連續(xù)），那么新插入的基本塊為空基本塊，否則其中應(yīng)當存在一條跳轉(zhuǎn)指令，跳轉(zhuǎn)目標是該邊的后繼，這條跳轉(zhuǎn)指令是否出現(xiàn)在最終的目標代碼中依賴于新的基本塊中是否有簇間傳輸指令；而若起點只有一條出邊或終點只有一條入邊，那么簇間傳輸指令可以插入在起點塊或終點塊中，插入在新構(gòu)建的塊上只會帶來更大的開銷。

3約束

3.1指令出現(xiàn)次數(shù)約束

最基本的，待分簇的指令必須且只能被分派到一個簇中，對于任意待分簇指令i，有如下約束規(guī)則：

∑Mm=1ρi，m=1（1）

在此約束的保障下，根據(jù)零一變量的特性，指令i被分派到的簇編號可以記為

cluster（i）：=∑Mm=1m×ρi，m（2）

同理，函數(shù)中原有的基本塊B中的任意i必須且只能被調(diào)度到某一個時鐘周期：

∑T（B）t=1τB，i，t=1（3）

基本塊B中指令i被調(diào)度的時鐘周期可以記為

cycle（B，i）：=∑T（B）t=1t×τB，i，t（4）

簇間傳輸指令被調(diào)度的情況依賴于對應(yīng)變量的定義與使用的指令的分簇情況，可以總結(jié)為以下四條規(guī)則：

a）對于任意變量v，當任意兩條讀寫變量v的指令i、j被分派到任意不同的兩個簇m1、m2時，簇間傳輸指令x（v，m1，m2）必須在它們之間的每條路徑P中的某個基本塊內(nèi)被調(diào)度。容易驗證，此約束可以表示為

∑B∈P∑T（B）t=1τB，x（v，m1，m2），t≥ρi，m1+ρi，m2－1（5）

這條約束使簇間傳輸指令總是從定義變量的指令所在的簇讀取數(shù)據(jù)，排除了簇間傳輸指令“接力”傳遞的情況。盡管“接力”方案也是合法方案，但在大多分簇VLIW DSP上，“接力”方案不可能是唯一的最優(yōu)方案。從數(shù)據(jù)流依賴情況來看，簇間傳輸指令從其他簇間傳輸指令的結(jié)果中讀取數(shù)據(jù)的最早發(fā)射時刻總是晚于直接從定義變量的指令所在的簇讀取數(shù)據(jù)。從資源占用方面來看，只有簇間傳輸指令占用簇間傳輸總線這一機器資源且簇間傳輸指令只占用該資源，因此，無論簇間傳輸指令從哪個簇讀取資源，其資源占用情況都對非簇間指令不構(gòu)成競爭關(guān)系，不會在資源方面影響調(diào)度；另一方面，由于總線的特性，只有從同一個簇讀取同一數(shù)據(jù)的簇間傳輸指令可能在同一個周期發(fā)射，所有簇間傳輸指令全都從定義變量的指令所在的簇讀取數(shù)據(jù)能得到的結(jié)果總是優(yōu)于或等于多個簇間傳輸指令接力的情況。所以，此約束并不會限制降低分簇質(zhì)量。

b）對于任意變量v，定義它的指令為i，在控制流圖中，任意一條從i到使用v的指令的路徑P上，對于任意簇m，僅當指令i沒有被分派到簇m時，將數(shù)據(jù)傳輸?shù)絤的簇間傳輸指令才允許出現(xiàn)，且最多在某個基本塊中某個時刻出現(xiàn)一次。此約束為

ρi，m+∑B∈P∑T（B）t=1∑1≤m1≤MτB，x（v，m1，m），t≤1（6）

這一項約束既限制了同一個變量的相同簇間傳輸指令最多出現(xiàn)一次，還排除了同一條執(zhí)行路徑上存在多個向某個簇中的變量寫入數(shù)據(jù)的不合法方案，如圖7所示的情況。

c）在定義、使用變量v的任意一條路徑上的每個基本塊B中，只有當使用v的指令j被分派到簇m時才允許簇間向m傳輸數(shù)據(jù)的傳輸指令x（v，_，m）在該基本塊中出現(xiàn)：

∑T（B）t=1τB，x（v，_m），t≤ρj，m（7）

d）同理，在定義、使用變量v的任意一條路徑上的每個基本塊B中，只有當定義v的指令i被分派到簇m時，才允許簇間從m傳輸數(shù)據(jù)的傳輸指令x（v，m，_）在該基本塊中出現(xiàn)：

∑T（B）t=1τB，x（v，m，_），t≤ρi，m（8）

簇間傳輸指令x是否出現(xiàn)在基本塊B可以記為

occur（B，x）：=∑T（B）t=1τB，x，t（9）

在任意一個新插入的基本塊B中，只可能存在簇間傳輸指令和一條跳轉(zhuǎn)指令j，當存在其他簇間傳輸指令被調(diào)度，跳轉(zhuǎn)指令j必須在B中被調(diào)度，此約束可以表示為

T（B）∑T（B）t=1τB，j，t≥∑x∈X（B）occur（B，x）（10）

反之，若B中不存在簇間傳輸指令，則B可以整個刪去，這一條規(guī)則無須表達成約束，因為多一條跳轉(zhuǎn)指令不可能是最優(yōu)解，會在求解過程中被排除掉。

同一周期發(fā)射的指令數(shù)目不能超過VLIW長度，對于基本塊B中的調(diào)度，在任意時刻t有

∑T（B）t=1τB，j，t≤NηB，t（11）

上式除了約束同一時鐘周期發(fā)射的指令條數(shù)，也確保若時刻t存在指令發(fā)射，變量ηB，t為1。但這并不夠，為了正確統(tǒng)計基本塊B中指令調(diào)度結(jié)果中最后一條指令的發(fā)射時刻，必須確保流水線停頓的周期t對應(yīng)的變量ηB，t也為1，還需要增加如下約束：

2≤t≤T（B）：ηB，t－1≥ηB，t（12）

此約束也使得指令總是被調(diào)度到最早的連續(xù)若干個時鐘周期。

3.2依賴約束

基本塊中指令之間的依賴關(guān)系包括流依賴、反依賴和輸出依賴三種數(shù)據(jù)依賴；另一項依賴關(guān)系是基本塊中其他所有指令不能在跳轉(zhuǎn)指令（若存在）之后執(zhí)行，簡單起見，這一項依賴在本文中簡稱為控制依賴，值得一提的是，廣泛使用的術(shù)語“控制依賴”有另外的意義［21］。

依賴約束是指存在數(shù)據(jù)依賴或控制依賴的兩條指令在被調(diào)度后，兩者所發(fā)射的時刻之差應(yīng)該大于等于依賴延遲。

基本塊B中，指令i、j之間的依賴若與簇內(nèi)寄存器無關(guān)，或是控制依賴時，依賴約束可以統(tǒng)一表示為

cycle（B，i）－cycle（B，j）≥L（13）

其中：L表示依賴延遲，在VLIW DSP中，一般控制依賴、反依賴延遲為0，輸出依賴為1，流依賴與流水線長度有關(guān)。

當反依賴或輸出依賴由簇內(nèi)寄存器傳遞時，若依賴的前驅(qū)或后繼被分派到不同的簇時，則依賴自然地被消除，依賴的前后兩條指令可以任意調(diào)度，否則就需要滿足延遲約束。兩種情況統(tǒng)一的約束規(guī)則可以用大M法表示如下：

cycle（j）－cycle（i）+2T（B）（1－δi，j）≥L（14）

其中：δi，j表示指令i、j是否被分派到同一個簇，它的語義還需要添加如下約束來得到保證：

ai，j+δi，j+bi，j=1

cluster（i）－cluster（j）≥－Mai，j+bi，j

cluster（i）－cluster（j）≤Mbi，j－ai，j（15）

上式中還引入了兩個輔助的零一變量ai，j、bi，j分別表示i、j之間簇的編號關(guān)系是小于或大于。

流依賴涉及簇間傳輸指令，考慮指令i、j分別定義、使用變量v，對于任意簇m1、m2，僅當x（v，m1，m2）被調(diào)度到i所在的基本塊B的某個時刻且i被分派到簇m1，才有x（v，m1，m2）流依賴于i，即

cycle（B，x（v，m1，m2））－cycle（B，i）+

2T（B）（2－occur（B，x（v，m1，m2））－ρi，m1）≥Lflow（16）

同理，僅當x（v，m1，m2）被調(diào)度到j(luò)所在的基本塊且j被分派到簇m2，j才流依賴于x（v，m1，m2），有

cycle（B，j）－cycle（B，x（v，m1，m2））+

2T（B）（2－occur（B，x（v，m1，m2））－ρi，m2）≥Lflow（17）

當i、j在同一個基本塊時，若它們被分派到同一個簇，它們存在流依賴，因此需要添加同式（13）一樣的約束，只是將不等式中的延遲換成流依賴的延遲，若它們被分派到不同的簇，則它們之間必然存在簇間傳輸指令，約束式（16）（17）確保了它們的延遲關(guān)系能得到滿足。

3.3資源約束

合法的指令調(diào)度還必須滿足：對于機器中的任意資源，譬如ALU、立即數(shù)通道等，在任意時刻執(zhí)行的指令使用的每一類資源不能超過機器限制。指令i在流水線第k階段使用的資源r的數(shù)目記為RES（i，k，r），大多數(shù)情況下資源沖突只會發(fā)生在少數(shù)流水線階段，不同的指令在占用資源的階段也可能不同，RES（i，k，r）只在這些會沖突的階段上有定義。

分簇DSP的資源可以被劃分為兩類：a）全局資源，由整個DSP共用的，指令使用該資源的情況與指令所在的簇無關(guān)；b）簇內(nèi)資源，只能由簇內(nèi)的指令使用，且每個簇擁有相同數(shù)目。值得注意的是，簇間數(shù)據(jù)總線也是簇內(nèi)資源，表示為每個簇中的若干個讀寫端口。

考慮基本塊B的調(diào)度，對于全局資源r，在任意時刻t執(zhí)行的所有指令使用資源r的總和不超過機器限制，有

∑i∈B∑k≤tτB，i，t－k×RES（i，k，r）≤M（r）（18）

簇內(nèi)資源中，簇間讀寫端口需要單獨考慮。當r是簇間總線的讀端口時，對于任意簇m，僅有從m讀取數(shù)據(jù)的簇間傳輸指令會占用。設(shè)可能在B中被調(diào)度的這些簇間傳輸指令為X（B，m，_），簇間傳輸指令使用總線的約束如下：

∑i∈X（B，m，_）∑k≤tτB，x，t－k×RES（x，k，r）≤M（r）（19）

類似地，當資源r是簇間總線的寫端口，對于任意簇m，設(shè)可能在B中被調(diào)度的、目標是m的簇間傳輸指令為X（B，_，m），約束為

∑i∈X（B，_，m）∑k≤tτB，x，t－k×RES（x，k，r）≤M（r）（20）

對于簇內(nèi)的其他資源，資源使用情況則與待分簇指令自身分派的簇有關(guān)，資源約束為

∑i∈X（B，_，m）∑k≤t（ρi，m∧τB，x，t－k）×RES（x，k，r）≤M（r）（21）

其中：∧表示零一變量的邏輯合取，通過引入額外的一個零一變量并添加約束2（α∧β）≥α+β，（α∧β）≤α，（α∧β）≤β得到線性表達。

4優(yōu)化目標

分簇調(diào)度的目標是使函數(shù)執(zhí)行時間最短，但程序的執(zhí)行時間是不可判定問題，只能近似。基本塊在前文約束的保證下，基本塊B的最后一條指令的發(fā)射時刻為∑T（B）t=1ηB，t。

設(shè)輸入的函數(shù)為F，優(yōu)化目標為∑B∈FW（B）∑T（B）t=1ηB，t。在沒有其他信息的情況下，估計基本塊B的執(zhí)行次數(shù)W（B）基于一個直觀的原則：處于循環(huán)中的基本塊，循環(huán)層次越靠內(nèi)，執(zhí)行次數(shù)越大，遠遠大于循環(huán)外的塊，除了循環(huán)的回邊外，假設(shè)跳轉(zhuǎn)指令的分支概率相同。設(shè)分簇調(diào)度的函數(shù)的控制流圖是可規(guī)約的，本文采取如下方法估計基本塊的執(zhí)行次數(shù)：

a）忽略控制流圖中的回邊，若在新插入的塊在回邊上也一同忽略該塊，將控制流圖的入口塊未執(zhí)行次數(shù)設(shè)為W0=1，廣度優(yōu)先遍歷控制流圖，基本塊的出邊平分基本塊的次數(shù)，基本塊的執(zhí)行次數(shù)等于入邊次數(shù)之和。

b）識別流圖中的自然循環(huán)，合并具有相同首節(jié)點的循環(huán)。設(shè)基本塊（或邊）被包含在循環(huán)中的次數(shù)為k，那么該塊（或邊）的次數(shù)估計為100kW0，循環(huán)的回邊平分回邊的起點的權(quán)值，回邊上插入的基本塊的執(zhí)行次數(shù)等于該邊的執(zhí)行次數(shù)。

5其他細節(jié)

5.1處理函數(shù)調(diào)用指令

出于簡化表達的目的，上文中線性整數(shù)規(guī)劃建模忽略了函數(shù)調(diào)用指令這一特殊情況。函數(shù)調(diào)用指令實際執(zhí)行時間依賴于被調(diào)用的函數(shù)，無法判斷，并且當函數(shù)返回時，返回值寄存器中的數(shù)據(jù)已準備好，即使下一條指令要使用函數(shù)的返回數(shù)據(jù)也不需要再等待流依賴延遲，前文中的依賴約束不能準確地表達這種情況。將函數(shù)指令看做基本塊邊界能繞過這一問題，但會稍微錯失一點并行機會，另一個方法是讓函數(shù)調(diào)用指令的發(fā)射占用多個時鐘周期，等于最大延遲L，這樣當函數(shù)調(diào)用指令執(zhí)行完后所有依賴它的指令都已滿足延遲，能直接發(fā)射，不用改變前文的建模方式。盡管這樣做會使優(yōu)化目標中對最后一條指令發(fā)射時刻的計算不精確，但是并不影響最終目的，即對程序執(zhí)行時間的近似。在這種方法下，函數(shù)調(diào)用指令發(fā)射占用的第2～L時鐘周期不應(yīng)該有其他指令占用，設(shè)基本塊B中的函數(shù)調(diào)用指令為c，這項約束為

1≤t≤T（B）－L：

∑t+L－1u=t∑i∈B∧i≠cτB，i，u≤（1－τB，c，t）T（B）N（22）

5.2優(yōu)化求解速度

由于DSP的各簇都是同構(gòu)的，所以存在許多對稱的分簇方案，破除這些對稱往往能加快整數(shù)線性規(guī)劃求解，思路為盡量將指令分派到簇編號較小的簇，可以通過添加如下約束不等式來實現(xiàn)目標：

2≤m≤M：∑i∈Fρi，m－1≥∑i∈Fρi，m（23）

基本塊B中每條指令實際能發(fā)射的時刻范圍一般遠遠小于1～T（B）約束每條指令的發(fā)射周期范圍能夠大幅降低整數(shù)線性規(guī)劃求解時的搜索空間。將程序依賴圖看做一個AOE網(wǎng)，容易求出每條指令i的最早發(fā)射時間與最晚發(fā)射時間。如果不考慮機器資源，顯然指令只能在最早發(fā)射時間與最晚發(fā)射時間之間被發(fā)射，但由于分簇可能插入簇間傳輸指令以及DSP的發(fā)射數(shù)限制，實際上指令合法的發(fā)射時刻可能會大于該最晚發(fā)射時間，可以使用如下方法保守地估計指令發(fā)射時刻的區(qū)間。

a）對于任意基本塊，遍歷不含簇間傳輸指令的程序依賴圖，計算最早發(fā)射時刻：

et（i）=0if pred（i）=

maxj∈pred（i）（et（j）+lati，j）otherwise

其中：pred（i）表示指令i的在圖中的所有直接間接前驅(qū)；lati，j表示指令i、j之間的延遲。

b）遍歷包含簇間傳輸指令的依賴圖，使用步驟a）中的公式以及結(jié)果計算每條簇間傳輸指令的最早發(fā)射時刻。

c）計算指令發(fā)射時刻的下界：

lb（i）=maxet（i），|pred（i）|N

d）遍歷不含簇間傳輸指令的程序依賴圖，設(shè)當前處理的基本塊為B，計算指令的最晚發(fā)射時刻：

lt（i）=T（B）if succ（i）=

minj∈succ（i）（lt（j）－lati，j）otherwise

其中：succ（i）表示指令i所有直接間接后繼。此處的最晚發(fā)射時刻lt與AOE網(wǎng)絡(luò)中的定義并不一樣，實際上是反方向計算的最早發(fā)射時刻。

e）遍歷包含簇間傳輸指令的依賴圖，使用步驟d）中的公式以及結(jié)果計算每條簇間傳輸指令的最晚發(fā)射時間。

f）計算指令發(fā)射時刻的上界為

ub（i）=minlt（i），T（B）－|succ（i）|N」

對于任意基本塊B，限制非簇間傳輸指令發(fā)射在估計的區(qū)間內(nèi)的約束為

lb（i）≤cycle（B，i）≤ub（i）（24）

簇間傳輸指令x的發(fā)射時刻上界約束與其他指令的相同，但由于簇間傳輸指令x不一定被調(diào)度，cycle（B，x）可能為0，所以其發(fā)射時刻上界約束為

lb（i）≤cycle（B，x）+T（B）（1－occur（B，x））（25）

6實驗評估

本文選用HXDSP1042作為算法的驗證平臺，HXDSP1042一款典型的分簇VLIW DSP由中國電子科技集團第38研究所研發(fā)，支持16發(fā)射，有4個簇、13級流水線，各簇之間通過總線通信，已經(jīng)被大量運用在雷達信號處理上。整數(shù)線性規(guī)劃求解是另一個復(fù)雜的話題，超出本文討論的范圍，這里使用求解器Gurobi［22］來實現(xiàn)本文算法。測試程序選擇的是DSPStone［23］，編譯時開啟O2優(yōu)化，僅替換指令分簇與指令調(diào)度優(yōu)化，并實現(xiàn)了幾種統(tǒng)一分簇與調(diào)度的方法作為參考，這些算法對測試程序中每個基本塊分別進行，而本文方法實現(xiàn)在整個函數(shù)上，測試程序在HXDSP1042的仿真器上執(zhí)行，結(jié)果顯示了本文方法相比效果最好的近似算法LUCAS在不同的測試程序上有20%～35%的性能提升。圖9顯示了幾種方法在DSPStone中幾項測試程序中的歸一化執(zhí)行時間，使用UAS算法的結(jié)果作為基準1。其中UAS-CC表示使用完成時間作為為啟發(fā)因子的UAS算法，LSTC 表示文獻［9］算法，ILP表示本文方法。

盡管整數(shù)線性規(guī)劃是NP問題，但對于一般程序中的函數(shù)，使用分支定界法往往能較快地求解出最優(yōu)解。本文從在GSL［24］、FANN［25］、Zlib、DSPStone中隨機選擇了共4 000個函數(shù)，在一臺Intel Core i5-8300H的筆記本電腦上測試了本文算法，結(jié)果顯示，其中約81%的函數(shù)能在0.5 s內(nèi)得到結(jié)果，如表2所示。

7結(jié)束語

本文使用整數(shù)線性規(guī)劃方法實現(xiàn)了分簇VLIW DSP上的指令分簇與指令調(diào)度，并在HXDSP1042進行了實驗，結(jié)果表明本文方法能有效提高程序的性能，且算法的運行時間是可以接受的，盡管與近似算法還有一定差距，但已經(jīng)具備了相當?shù)膶嵱眯浴Ｒ粋€不足之處在于對函數(shù)執(zhí)行時間的估計過于粗糙，這個問題可以通過利用編譯器高層的信息，或采用深度方法預(yù)測［26］分支概率得到改善。另一個問題是本文方法的時間開銷還有優(yōu)化空間，其原因在于使用了一個大的整數(shù)線性規(guī)劃模型來表示所有指令的分簇與調(diào)度，求解時間開銷比較大，但實際上往往存在許多指令的分簇和調(diào)度與另外許多指令無關(guān)。因此下一步的研究將探索如何將函數(shù)分割為多個部分，對每個部分分別建模求解并保證整體結(jié)果最優(yōu)，從而進一步提高求解速度。

參考文獻：

[1]Mattson P， Dally W J， Rixner S， et al. Communication scheduling［J］.ACM SIGPLAN Notices，2000，35（11）：82-92.

［2]Kessler R. The Alpha 21264 microprocessor［J］.IEEE Micro，1999，19（2）：24-36.

［3]Ellis J R. Bulldog： a compiler for VLSI architectures［M］.Cambridge，MA：MIT Press，1986.

［4]Lowney P G， Freudenberger S M， Karzes T J， et al. The multiflow trace scheduling compiler［J］.Journal of Supercomputing，1993，7（5）：51-142.

［5]Desoli G. Instruction assignment for clustered VLIW DSP compilers： a new approach［EB/OL］.（1998-02）.https：//www.hpl.hp.com/techreports/98/HPL-98-13.pdf.

［6]Lapinskii V S， Jacome M F， De Veciana G A. Cluster assignment for high-performance embedded VLIW processors［J］.ACM Trans on Design Automation of Electronic Systems，2002，7（3）：430-454.

［7]Ozer E， Banerjia S， Conte T M. Unified assign and schedule： a new approach to scheduling for clustered register file microarchitectures［C］//Proc of the 31st Annual ACM/IEEE International Symposium on Microarchitecture.Washington DC：IEEE Computer Society，1998：308-315.

［8]Kailas K， Ebcioglu K， Agrawala A. CARS： a new code generation framework for clustered ILP processors［C］//Proc of the 7th International Symposium on High-Performance Computer Architecture.Washington DC：IEEE Computer Society，2001：133-143.

［9]Zhang Xuemeng， Wu Hui， Xue Jingling. An efficient heuristic for instruction scheduling on clustered VLIW processors［C］//Proc of the 14th International Conference on Compilers， Architectures and Synthesis for Embedded Systems.Washington DC：IEEE Computer Society，2011：35-44.

［10]Porpodas V， Cintra M. LUCAS： latency-adaptive unified cluster assignment and instruction scheduling［J］.ACM SIGPLAN Notices， 2013，48（5）：45-54.

［11]Fisher J A. Trace scheduling： a technique for global microcode compaction［J］.IEEE Trans on Computers，1981，30（7）：478-490.

［12]Wilken K， Liu J， Heffernan M. Optimal instruction scheduling using integer programming［J］.ACM SIGPLAN Notices，2000，35（5）：121-133.

［13]Kstner D， Winkel S. ILP-based instruction scheduling for IA-64［J］.ACM SIGPLAN Notices，2001，36（8）：145-154.

［14]Mendis C， Amarasinghe S. goSLP： globally optimized superword level parallelism framework［J］.Proceedings of the ACM on Programming Languages，2018，2（OOPSLA）：article No.110.

［15]Fisher J A. The optimization of horizontal microcode within and beyond basic blocks： an application of processor scheduling with resources［D］.New York：New York University，1979.

［16]王玉林，鄭啟龍.魂芯分簇VLIWDSP上指令調(diào)度的優(yōu)化［J］.微型機與應(yīng)用，2017，36（11）：23-26，30.（Wang Yulin， Zheng Qilong. Instruction scheduling optimization for clustered VLIW HXDSP［J］.Microcomputer amp; Its Applications，2017，36（11）：23-26，30.）

［17]Zalamea J， Llosa J， Ayguadé E， et al. Modulo scheduling with integrated register spilling for clustered VLIW architectures［C］//Proc of the 34th ACM/IEEE International Symposium on Microarchitecture.Washington DC：IEEE Computer Society，2001：160-169.

［18]Aleta A， Codina J M， Sánchez J， et al. AGAMOS： a graph-based approach to modulo scheduling for clustered microarchitectures［J］.IEEE Trans on Computers，2009，58（6）：770-783.

［19]Mahlke S A， Lin D C， Chen W Y， et al. Effective compiler support for predicated execution using the hyperblock［J］.ACM SIGMICRO Newsletter，1992，23（1-2）：45-54.

［20]Llosa J， González A， Ayguadé E， et al. Swing module scheduling： a lifetime-sensitive approach［C］//Proc of the 22nd Conference on Parallel Architectures and Compilation Technique.Piscataway，NJ：IEEE Press，1996：80-86.

［21]Ferrante J， Ottenstein K J， Warren J D. The program dependence graph and its use in optimization［J］.ACM Trans on Programming Languages and Systems，1987，9（3）：319-349.

［22]Gurobi Optimization. Gurobi optimizer reference manual［EB/OL］.［2022-05-07］.https：//www.gurobi.com/documentation/9.5/matlab_html/index.html.

［23]Institute for Communication Technologies and Embedded Systems.DSPStone［EB/OL］.［2022-05-07］.https：//www.ice.rwth-aachen.de/research/tools-projects/closed-projects/dspstone.

［24]Gough B. GNU scientific library reference manual［M］.3rd ed.［S.l.］：Network Theory Ltd.，2009.

［25]Nissen S. Implementation of a fast artificial neural network library（FANN）［EB/OL］.（2003-10-31）.http：//attic-distfiles.pld-linux.org/distfiles/distfiles/by-md5/8/1/8117a677afc79dfaa31de39ca84d 82da/fann_doc_complete_1.0.pdf.

［26]Bieber D， Sutton C， Larochelle H， et al. Learning to execute programs with instruction pointer attention graph neural networks［C］//Proc of the 34th International Conference on Neural Information Processing Systems.Red Hook，NY：Curran Associates，Inc.，2020：8626-8637.

收稿日期：2022-03-03；

修回日期：2022-05-18

基金項目：國家核高基重大專項資助項目（2012ZX01034-001-001）

作者簡介：周鵬（1994-），男，四川廣安人，碩士研究生，主要研究方向為編譯優(yōu)化（pzzp@mail.ustc.edu.cn）；劉純綱（1994-），男，安徽安慶人，碩士研究生，主要研究方向為編譯優(yōu)化；鄭啟龍（1969-），安徽合肥人，副教授，碩士，主要研究方向為深度學(xué)習(xí)平臺與應(yīng)用.