關(guān) 沫， 佟 彤

(沈陽工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 沈陽 110870)

多核系統(tǒng)的實時任務(wù)調(diào)度算法研究

關(guān) 沫， 佟 彤

(沈陽工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 沈陽 110870)

為更好地解決多核系統(tǒng)實時任務(wù)調(diào)度問題，針對基本蟻群算法求解最短路徑過程中容易陷入局部最優(yōu)的情況，對基本蟻群算法進(jìn)行了改進(jìn)。改進(jìn)算法根據(jù)系統(tǒng)的實際情況對概率選擇公式做出調(diào)整，同時根據(jù)相應(yīng)策略對信息素進(jìn)行調(diào)整，有效地縮小了信息素之間的差距，有利于跳出局部最優(yōu)狀態(tài)。實驗結(jié)果表明，該算法與基本蟻群算法相比在收斂速度和計算最優(yōu)解方面都有了提高。

蟻群優(yōu)化算法；多核系統(tǒng)；實時；任務(wù)調(diào)度

0 引言

隨著程序的時間復(fù)雜性的增加和硬件成本的減少，多核系統(tǒng)的利用已經(jīng)越來越多。同時，實時系統(tǒng)領(lǐng)域的實時控制要求也在日益增加，因而提高系統(tǒng)的實時性能至關(guān)重要。在這些系統(tǒng)中，程序被劃分成一些任務(wù)映射到一些處理器上，以減少程序的完成時間。在這些架構(gòu)中最重要的挑戰(zhàn)之一是如何視處理器的數(shù)量和處理能力來安排任務(wù)，在滿足所有任務(wù)的時限要求的前提下，給予外部請求及時的響應(yīng)，使程序的整體執(zhí)行時間可以盡量最小化。

目前，已出現(xiàn)很多研究著作對異構(gòu)多核系統(tǒng)下的實時任務(wù)調(diào)度提出了一些性能較好的算法及其改進(jìn)算法。然而，即使在簡化了一些問題的假設(shè)后，多核系統(tǒng)的任務(wù)調(diào)度也是NP(Non-deterministic Polynomial)難題[1]。傳統(tǒng)窮舉法計算復(fù)雜度大，耗時長[2]，所以至今為止還沒有一種被確定為最優(yōu)的調(diào)度算法。正因如此，很多學(xué)者仍在孜孜不倦地追求更優(yōu)解，也為后來的研究者提供了極大的可改進(jìn)和可拓展空間。

1 多核任務(wù)調(diào)度

在多核系統(tǒng)中，一個程序被劃分成更小的段，命名為任務(wù)分布在處理器上。通過同時運行任務(wù)來減少程序的整體執(zhí)行時間。一個程序的任務(wù)之間是有依賴關(guān)系的。一些任務(wù)需要其他任務(wù)所產(chǎn)生的數(shù)據(jù)。因此，任務(wù)之間有約束關(guān)系，并且內(nèi)核之間需要數(shù)據(jù)通信。在本文中，假定是異構(gòu)體系結(jié)構(gòu)和完全連接的處理器。

早期的異構(gòu)多核系統(tǒng)大部分是通過啟發(fā)式算法解決任務(wù)調(diào)度問題的，一般是結(jié)合最早完成時間(makespan)[3]、最少完成時間和負(fù)載均衡等指標(biāo)，通過使用貪婪算法的思想去求解任務(wù)分配的次優(yōu)解。這種算法雖然收斂速度很快，可是由于所供參考的任務(wù)范圍較小，因此比較容易陷入局部最優(yōu)解[4]。在異構(gòu)多核系統(tǒng)的任務(wù)調(diào)度問題中，啟發(fā)式算法的局限性導(dǎo)致了人工智能算法的引入，這類算法的主要思想是憑借設(shè)定啟發(fā)信息去合理引導(dǎo)搜索過程向最優(yōu)解逐漸收斂，主要有遺傳算法[5]、禁忌搜索算法、鄰域搜索算法、蟻群算法等。它們擅長找到全局最優(yōu)解，但也普遍存在算法收斂時間較長的缺點，在具體應(yīng)用過程中很難按基礎(chǔ)算法使用。為了改進(jìn)人工智能算法，研究者們采用混合調(diào)度策略或者設(shè)置相關(guān)約束條件來不斷加快算法的收斂速度。其中蟻群算法[6]是一種有效的隨機(jī)模擬進(jìn)化算法，它模擬蟻群覓食過程中發(fā)現(xiàn)最優(yōu)路徑的過程，可用于解決組合優(yōu)化問題。

2 基本蟻群算法

蟻群算法是一種人工螞蟻合作來找到一個給定的問題的優(yōu)化解決方案的并行算法。蟻群算法[7]最早是由DORIGO M等人提出的，靈感來源于大自然中螞蟻尋找食物的群體行為。作為一種解決旅行商問題[8](TSP)的機(jī)率型模擬進(jìn)化算法，它已經(jīng)成功地應(yīng)用于許多復(fù)雜的離散性優(yōu)化問題，如二次分配問題(QAP)、車間調(diào)度[9](JSP)、車輛路徑、圖著色、排序、網(wǎng)絡(luò)路由等。實驗證明該算法能較為出色地解決復(fù)雜優(yōu)化問題,特別是離散性優(yōu)化問題，是一種比較卓越的優(yōu)化算法。

下面具體闡述蟻群搜索路徑的原理[10]。如果有一個障礙物，螞蟻要繞過它有兩側(cè)兩條路徑，其中一邊的路徑比另一邊長。首先，螞蟻通過隨機(jī)運動來繞過障礙。然后，較長一側(cè)的信息素蒸發(fā)更快，螞蟻逐漸收斂到短的路徑上。因此，它們總是能找到從食物到蟻穴的最短路徑。由上述螞蟻搜索路徑的原理可知，路徑上信息量越大，這條路徑被選中的概率就越大，直到最后，螞蟻完全選中這條路徑，這種現(xiàn)象所體現(xiàn)出的是信息的正反饋機(jī)制。

蟻群算法模擬這種覓食行為。在開始時，所有任務(wù)的狀態(tài)都是可以訪問的，螞蟻被設(shè)置為一個初始狀態(tài)。它根據(jù)相鄰狀態(tài)信息素的值使用概率公式選擇下一個任務(wù)，并在此路徑上留下信息素，為下一只螞蟻提供可參考信息。使用同樣的方法為任務(wù)選擇處理核。螞蟻重復(fù)此操作，直到它遍歷過所有的任務(wù)。此時，更新任務(wù)選擇和處理器選擇路徑上的信息素變量。通過這種機(jī)制螞蟻收斂得到最優(yōu)解。

3 蟻群優(yōu)化算法

為了提高多核系統(tǒng)的調(diào)度效率，針對蟻群算法的缺點，從兩方面進(jìn)行改進(jìn)：一是在選擇任務(wù)和為任務(wù)選擇處理核的概率選擇公式的設(shè)計上；二是信息素變量的更新。首先，n是給定的任務(wù)圖的任務(wù)數(shù)，處理器的個數(shù)為m。τ(i,j)是指有向邊i、j上的信息素變量，η(i,j)是指任務(wù)i后會選擇任務(wù)j的期望程度。最初所有元素有相同的較小值。然后執(zhí)行迭代的蟻群算法：

(1)生成蟻群；

(2)設(shè)置初始化信息；

(3)每只螞蟻循環(huán)(直到完成調(diào)度任務(wù))——根據(jù)信息素變量選擇下一個就緒任務(wù)，為該任務(wù)選擇處理器；

(4)記錄信息素變量；

(5)信息素變量的更新。

改進(jìn)蟻群算法的流程圖如圖1所示。

圖1 蟻群優(yōu)化算法流程圖

在第一階段，只是創(chuàng)建一個長度為n的列表。在第二階段，每只螞蟻從準(zhǔn)備列表中選擇一個任務(wù)，并為該任務(wù)選擇一個處理核，直到完成任務(wù)調(diào)度。在每次迭代中，N只螞蟻就會得到N組可行解。選擇一組任務(wù)調(diào)度長度最短的解作為一次迭代的最優(yōu)解。對于螞蟻k，通過使用概率選擇式(1)和式(2)為任務(wù)i選擇下一個任務(wù)j。

(1)

(2)

公式的設(shè)計考慮如下幾個因素：(1)Dj，任務(wù)j的截止期；(2)Mj，任務(wù)j的估計運算量；(3)ei,j，任務(wù)i和j之間的估計通信量。

在為任務(wù)選擇處理器時，根據(jù)概率選擇式(1)和式(3)進(jìn)行選擇。

(3)

考慮以下幾個因素：(1)sp，處理核p的處理速率;(2)rj,p，任務(wù)j在處理核p上準(zhǔn)備就緒的時間;(3)tp,處理核p的最早可用時間。

然后生成一個隨機(jī)數(shù)，選擇與所生成的數(shù)相對應(yīng)的作為下一個任務(wù)。顯然，有較大信息素值的任務(wù)有更大的機(jī)會被選擇。選定的任務(wù)被添加到禁忌表中，

從允許被選擇的列表中刪除，被選擇任務(wù)的子任務(wù)現(xiàn)在可以執(zhí)行，增加到準(zhǔn)備列表中。這些操作是重復(fù)的，直到完成所有任務(wù)的調(diào)度，換句話說，完成了螞蟻的列表。

在第三階段中，根據(jù)k組可行解的情況，對路徑上的信息素變量進(jìn)行更新，調(diào)整策略如式(4)、式(5)和式(6)所示。

τ(i,j)=(1-ρ)τ(i,j)+Δτ(i,j)

(4)

(5)

(6)

Lk表示第k只螞蟻求得的任務(wù)調(diào)度長度，Q在基本蟻群算法中是常數(shù)，但通過實驗發(fā)現(xiàn)，有時會導(dǎo)致搜索停滯，對Q作出兩點改變來解決：一是限定信息素變量的最大值和最小值，二是根據(jù)迭代次數(shù)對Q值進(jìn)行調(diào)整。

最后階段，選擇所有迭代結(jié)束后得到的調(diào)度時間最短的解作為最優(yōu)的解決方案。

4 實驗結(jié)果及分析

在MicrosoftVisualC++ 6.0 上使用C語言實現(xiàn)了本文提出的優(yōu)化的蟻群算法。用有向無環(huán)圖(DAG)對任務(wù)進(jìn)行建模。圖2表示了一個程序的任務(wù)圖。

圖2 程序的任務(wù)圖

在圖2中，節(jié)點是任務(wù)，邊是指定任務(wù)之間的優(yōu)先約束。邊(i，j)表明，任務(wù)i必須在任務(wù)j開始前完成。每個節(jié)點的權(quán)重是任務(wù)的必要的執(zhí)行時間，邊(i，j)的權(quán)重是任務(wù)i向任務(wù)j傳輸數(shù)據(jù)所需的時間作為通信成本。如果兩個任務(wù)在同一個處理器上執(zhí)行，它們之間的通信成本將是零。在程序編譯階段產(chǎn)生任務(wù)執(zhí)行時間、通信成本和任務(wù)之間的優(yōu)先級約束。

在實驗中設(shè)置參數(shù)如下：螞蟻個數(shù)為10，最大迭代次數(shù)為100，α為2，β為2，ρ為0.7，該算法成功完成了異構(gòu)多核系統(tǒng)中的實時任務(wù)調(diào)度，求出的最優(yōu)解不僅是可行解，而且任務(wù)調(diào)度長度較短，充分證明了本文混合算法的可行性。

同時改進(jìn)蟻群算法與基本蟻群算法進(jìn)行比較，分析結(jié)果如圖3、圖4所示。從圖3可知，改進(jìn)蟻群算法的平均任務(wù)調(diào)度長度明顯優(yōu)于基本蟻群算法；圖4將不同算法得到的最優(yōu)解進(jìn)行對比，可知改進(jìn)蟻群算法得到的最優(yōu)解的任務(wù)調(diào)度長度更短并且較穩(wěn)定，明顯優(yōu)于基本蟻群算法得到的最優(yōu)解。

圖3 不同算法的平均任務(wù)調(diào)度長度比較

5 結(jié)論

針對多核系統(tǒng)的實時性，本文算法考慮了任務(wù)的到達(dá)時間、就緒時間和截止期，再結(jié)合多核系統(tǒng)的復(fù)雜環(huán)境，考慮了各內(nèi)核不同的運行速率和內(nèi)核間不同的通信帶寬。將所提出的方法與其他調(diào)度方法進(jìn)行了實驗對比，本文提出的蟻群優(yōu)化算法在平均任務(wù)調(diào)度長度和最優(yōu)解的任務(wù)調(diào)度長度上的表現(xiàn)均優(yōu)于相比較的算法。

圖4 不同算法的最優(yōu)解調(diào)度長度比較

[1] CHRETIENNE P, COFFMAN E G, LENSTRA J K, et al. Scheduling theory and its application[J]. Journal of the Operational Research soeiety, 1995,48(7):764-765.

[2] Liu Yi, Zhang Xin, Li He,et al. Allocating tasks in multi-core processor based par-allel system[C]. Proceedings of the IFIP International Conference on Network and Parallel Computing Workshops, Washington DC, 2007: 748-753.

[3] Zhu Jie, Li Xiaoping. An effective meta-heuristic for no-wait job shops to minimize makespan[C]. IEEE Transactions on Automation Science and Engineering, 2012,1(9): 189-198.

[4] 劉進(jìn)，劉春，陳家佳．基于改進(jìn)蟻群算法的多處理器任務(wù)調(diào)度仿真[J]．計算機(jī)仿真，2014, 31( 6)：334-337．

[5] 王嘉平．多核系統(tǒng)中實時任務(wù)調(diào)度算法的研究[D]．南京：南京郵電大學(xué)，2012.

[6] 周會嬌．異構(gòu)多核系統(tǒng)多媒體流計算實時任務(wù)調(diào)度策略研究[D]．武漢：華中科技大學(xué)，2013.

[7] DORIGO M， BIRATTARI M， STUTZLE T. Ant colony optimization [J]. IEEE Computational Intelligence Magazine， 2006, 1(4)：28-39.

[8] 朱君,蔡延光,湯雅連，等.改進(jìn)混合蟻群算法求解關(guān)聯(lián)旅行商問題[J].微型機(jī)與應(yīng)用, 2014, 33(9):80-84, 88.

[9] 張麗萍.改進(jìn)的蟻群算法求解置換流水車間調(diào)度問題[J].微型機(jī)與應(yīng)用,2014,33(12):66-68,72.

[10] 段海濱. 蟻群算法原理及其應(yīng)用[M]. 北京： 科學(xué)出版社, 2005.

Research on real-time task scheduling algorithm of multi-core system

Guan Mo, Tong Tong

(School of Information Science and Engineering, Shenyang University of Techenology, Shenyang 110870, China)

Ant colony system algorithm can solve the real-time task scheduling problem, but it is easily trapped in local optimization problem. In order to solve the problem, the basic ant colony algorithm is improved. According to the actual situation of the system, improved algorithm makes the adjustment to the probability selection formula, and adjusts the pheromone with corresponding strategy. Effectively reducing the gap between the pheromone, it is advantageous to jump out of the local optimal state. Experimental results show that the proposed algorithm is improved compared with the basic ant colony algorithm in terms of convergence rate and computational optimization.

ant colony optimization; multi-core systems; real-time; task scheduling

TP332

A

1674-7720(2016)02-0017-03

關(guān)沫，佟彤. 多核系統(tǒng)的實時任務(wù)調(diào)度算法研究[J] .微型機(jī)與應(yīng)用，2016,35(2)：17-19.

2015-09-22)

關(guān)沫(1976-)，女，博士，副教授，主要研究方向：嵌入式軟件與實時系統(tǒng)，計算機(jī)視覺。

佟彤(1990-)，女，碩士研究生，主要研究方向：嵌入式軟件與實時系統(tǒng)。