基于時間約束的高層次綜合調(diào)度方法

劉乙力 白利瓊 鞠瑜華 向明艷

（成都華微電子科技有限公司 四川省成都市 610000）

隨著半導(dǎo)體技術(shù)的不斷發(fā)展，超大規(guī)模集成電路變得越來越復(fù)雜，設(shè)計者在進行電路設(shè)計時常常只能給出系統(tǒng)的算法級行為描述，而在進行邏輯綜合之前需將算法級的行為描述轉(zhuǎn)化為寄存器傳輸級的結(jié)構(gòu)描述，這個轉(zhuǎn)換過程稱為高層次綜合。高層次綜合可在一定的約束條件下搜索設(shè)計空間，通過對調(diào)度或分配算法的比較和選用從而找到一個最佳方案或滿意方案，最終實現(xiàn)對資源或運行時間的優(yōu)化。高層次綜合工具的使用大大地減小了設(shè)計人員的工作量，縮短設(shè)計周期，提高設(shè)計質(zhì)量。

1 調(diào)度算法的介紹

操作的調(diào)度是指在滿足約束的條件下，將操作賦給控制步，從而使給定的目標函數(shù)最小。約束通常為時間約束或資源約束，目標函數(shù)主要考慮控制步總數(shù)、時延或面積。作為高層次綜合中的一個重要步驟，調(diào)度算法很大程度上決定了高層次綜合工具的執(zhí)行速度、響應(yīng)延遲性和硬件資源費用。傳統(tǒng)的調(diào)度算法主要包括ASAP(As soon as possible)、ALAP(As late as possible)調(diào)度算法、列表調(diào)度（LS，List Scheduling algorithm）算法、力引導(dǎo)調(diào)度 (FDS，F(xiàn)orce-Directed Schedulingalgorithm)算法。ASAP 和ALAP 算法簡單快速，常用于求各操作的可調(diào)度區(qū)間。列表調(diào)度算法可以進行資源約束下的操作調(diào)度，因算法復(fù)雜性低且可在短時間內(nèi)找到次優(yōu)解的優(yōu)點而被廣泛應(yīng)用[1]，但無法進行時間約束下的調(diào)度。力引導(dǎo)算法是一種基于時間約束尋找最小資源調(diào)度的構(gòu)造算法，它精確性好，能找到最佳調(diào)度結(jié)果，但是計算復(fù)雜，時間復(fù)雜度最壞情況下為O(n3)[2]。

考慮到高層次綜合過程中的調(diào)度是一個NP 完全問題，啟發(fā)式的算法也常常應(yīng)用于高層次綜合調(diào)度過程中，如遺傳算法(Genetic Algorithm)、模擬退火算(Simulated annealing Algorithm)等。文[3]提出了一種基于遺傳算法的調(diào)度和分配協(xié)同實現(xiàn)的策略；在文[4]中，D Chen 介紹了一種基于FPGA 的增強型模擬退火調(diào)度算法。對于計算量大的對象而言，啟發(fā)式算法能夠較快地找到一個近似解，但啟發(fā)式算法中的參數(shù)對算法的效果起著至關(guān)重要的的作用，而參數(shù)的選取常常取決于經(jīng)驗。

本文提出了一種新穎的基于時間約束的高層次綜合調(diào)度方法，該方法在滿足時間約束的條件下可使得各操作均勻地分布在控制步中，從而提高資源的利用率，減小面積。該調(diào)度方法首先建立中間矩陣記錄各操作的時間幀分布情況，再引入控制步擁擠度函數(shù)C(j)用以表征在當前狀態(tài)下控制步j(luò) 中可能存在的最大操作數(shù)之和，最后構(gòu)造時間幀分布表用于指導(dǎo)下一步選取的待調(diào)度操作。在整個調(diào)度過程中，各控制步的擁擠度會逐漸減小直至各控制步擁擠度之和等于所有操作數(shù)之和。實驗證明該方法有效。

圖1：HAL 的數(shù)據(jù)流圖

圖2：ASAP 和ALAP 調(diào)度結(jié)果

2 基于時間約束的調(diào)度方法

以HAL 基準測試電路為例對該方法進行說明。HAL 的數(shù)據(jù)流圖如圖1所示，其中操作類型主要有乘法器、加法器、減法器和比較器，本應(yīng)分為四組分別進行調(diào)度。為了便于說明可簡化問題，將數(shù)據(jù)流圖中的操作類型分為兩組，一組為所有的乘法操作，另一組為除乘法操作后的剩余操作。

對于數(shù)據(jù)流圖中的任意操作opi(i=1,2,…,n)，n 為操作總數(shù)，定義opi的時間幀用以表示操作opi的可調(diào)度范圍，可通過ASAP 和ALAP 調(diào)度算法得到。ASAP 調(diào)度算法可求得操作opi所能調(diào)度到的最早控制步，用表示；ALAP 算法可得到操作opi所能調(diào)度到的最晚控制步，用表示。即為操作opi的可調(diào)度范圍，又稱時間幀。對于opi∈{op1,…,opn}，有則稱opi為關(guān)鍵路徑上的操作。對于關(guān)鍵路徑上的操作，無需進行調(diào)度。關(guān)鍵路徑的長度決定了調(diào)度時的控制步數(shù)，由此可確定時間約束。

采用ASAP 和ALAP 算法對上述HAL 數(shù)據(jù)流圖進行調(diào)度后可得到圖2所示的調(diào)度結(jié)果。

表1：初始時間幀分布表

表2：一次調(diào)度后的時間幀分布表

表3：調(diào)度完成后時間幀分布表

定義中間矩陣(aij)n×m，記錄各操作的時間幀范圍，用于表征操作在控制步的可調(diào)度情況，其中n 為操作數(shù)，m 為控制步數(shù)。令

其中，csj表示第j 個控制步，j=1,2,…m。一個控制步是一個時鐘單位，對應(yīng)若干時鐘周期。

擁擠度函數(shù)C(j)表示當前情況下在控制步csj中可能存在的最大操作數(shù)之和，可表示為

在較壞的調(diào)度結(jié)果中，操作會聚集在部分控制步，不利于不同控制步的操作對資源的復(fù)用，進而導(dǎo)致資源的浪費，面積和造價的增加。因此，需要在調(diào)度的過程中不斷地降低擁擠度函數(shù)C(j)，使得各控制步的C(j)均勻分布，盡可能保證資源利用最大化。

對于操作opi，定義表示在操作opi的時間幀范圍內(nèi)，擁擠度最大控制步與擁擠度最小的控制步的擁擠度之差，可稱為操作opi的擁擠度差值。

根據(jù)矩陣(aij)n×m和擁擠度函數(shù)C(j)可得到時間幀分布表。該時間幀分布表分為兩部分，一部分為操作與控制步的關(guān)系，可根據(jù)中間矩陣的行和列來確定，中間矩陣的行即為時間幀分布表的行，中間矩陣的列即為時間幀分布表的列，HAL 初始時間幀分布表中操作與控制步的關(guān)系如迭代完成后，所需資源總數(shù)可通過max Ctype(j)得到。

表1（a）所示。考慮更為直觀地表示，可隱去中間矩陣中0 的分布情況。另一部分為各控制步擁擠度分布情況，利用擁擠度函數(shù)分別對每行同類型操作求和得到該種類型的擁擠度，由此可得到不同操作類型在控制步中的擁擠度，HAL 初始時間幀分布表中各控制步擁擠度分布情況如迭代完成后，所需資源總數(shù)可通過max Ctype(j)得到。

表1（b）所示。

本文中調(diào)度方法的步驟如下：

步驟1：通過ASAP，ALAP 調(diào)度算法得到各操作的時間幀；

步驟2：引入中間矩陣并計算各控制步的初始擁擠度，同時計算擁擠度差值；

步驟3：根據(jù)中間矩陣和初始擁擠度分布得到初始時間幀分布圖；

步驟4：若還有未被調(diào)度的操作（各控制步擁擠度之和不等于操作數(shù)），則

（1）選取擁擠度最大的控制步，并尋找該控制步內(nèi)擁擠度差值最大的操作，將其設(shè)為當前操作；

（2）將當前操作調(diào)度到其時間幀內(nèi)擁擠度最小的控制步；

（3）更新當前操作所有前驅(qū)和后繼的時間幀范圍；

（4）更新各控制步的擁擠度，轉(zhuǎn)到步驟4。

迭代完成后，所需資源總數(shù)可通過max Ctype(j)得到。

由數(shù)據(jù)流圖可知，HAL 的操作數(shù)為11，關(guān)鍵路徑長度為4，因此n=11，m=4。假設(shè)所有操作的運行均可在一個控制步內(nèi)完成，首先選擇擁擠度最大的控制步cs1、cs2、cs3，由于cs3 中存在擁擠度差值最大的操作，選取cs3 為當前控制步，cs3 中擁擠度差值最大的操作op10 為當前操作，將op10 調(diào)度到當前操作類型擁擠度最小的控制步cs1。更新op10 的后繼op11 的時間幀時，由于op10 的調(diào)度對op11 不產(chǎn)生影響，不需要對op11 的時間幀作出修改。更新各控制步擁擠度，可得到時間幀分布表如表2所示。

圖3：FDS 與本文方法的調(diào)度結(jié)果對比

在表2中，按上述方法選取cs2 為當前控制步，op8 為當前操作。將op8 調(diào)度至cs3，由于op9 為其后繼操作，更新op9 的時間幀長度后，op9 將被隱式調(diào)度至cs4。按同樣方式對剩下待調(diào)度操作進行迭代處理直至C(j)=n，經(jīng)過5 次調(diào)度，可得到表3所示的結(jié)果。通過max Ctype(j)可知，最終需要2 個乘法器，2 個除乘法器之外其他的操作對應(yīng)的資源。

上述方法的復(fù)雜度分析如下：

（1）一次迭代至少實現(xiàn)一個操作的調(diào)度，最多迭代n 次；

（2）每次迭代需在c 個控制步中選出擁擠度最大的控制步，再通過擁擠度差值確定當前控制步和當前操作；

（3）需將當前操作調(diào)度至其時間幀內(nèi)擁擠度最小的控制步，時間幀最大為c。

考慮上述3 個方面的影響，可得到最壞情況下本文算法的復(fù)雜度為O(c2n2)，c 可忽略不計，相對傳統(tǒng)的力引導(dǎo)調(diào)度算法而言，時間復(fù)雜度降低了n。

3 實驗結(jié)果

從DSP 基準測試套件和媒體測試電路中選取15 個典型的基準電路作為基準測試電路。通過比較力引導(dǎo)算法和本文算法的總資源消耗數(shù)與運行時間，可得到圖3所示的調(diào)度結(jié)果，其中第1 列和第2 列為基準電路的編號和名稱，第3、4 列為節(jié)點數(shù)和關(guān)鍵路徑長度，第5、6 列為FDS 與本文方法的總資源消耗數(shù)比和運行時間比，可以看出，盡管本文調(diào)度方法相對力引導(dǎo)調(diào)度算法資源消耗平均增大了2.7%，但是從運行時間來看，本文算法能夠明顯提升速度，平均可提高3.23 倍，最大可提高5.32 倍。

3 結(jié)論

本文實現(xiàn)了一種基于時間約束的高層次綜合調(diào)度算法，時間約束由輸入數(shù)據(jù)流圖的關(guān)鍵路徑?jīng)Q定，調(diào)度過程按照時間幀分布表確定待調(diào)度操作，在不斷地迭代過程中使得C(j)越來越小的同時趨于均勻分布。通過對15 組典型的基準測試電路的調(diào)度，將本文方法與傳統(tǒng)的力引導(dǎo)算法進行對比，可得到在損失平均2.7%的資源的情況下使得速度提高3.23 倍。