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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1：初始時(shí)間幀分布表

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

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

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

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

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

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

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

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

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

表1（b）所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果

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

3 結(jié)論

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