關(guān)沫， 佟彤

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

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

　　關(guān)鍵詞：蟻群優(yōu)化算法,；多核系統(tǒng)；實(shí)時(shí),；任務(wù)調(diào)度

　　0引言

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

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

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

　　在多核系統(tǒng)中，一個(gè)程序被劃分成更小的段,，命名為任務(wù)分布在處理器上,。通過同時(shí)運(yùn)行任務(wù)來減少程序的整體執(zhí)行時(shí)間。一個(gè)程序的任務(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é)合最早完成時(shí)間(makespan)［3］、最少完成時(shí)間和負(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］,、禁忌搜索算法,、鄰域搜索算法、蟻群算法等,。它們擅長(zhǎng)找到全局最優(yōu)解,，但也普遍存在算法收斂時(shí)間較長(zhǎng)的缺點(diǎn),，在具體應(yīng)用過程中很難按基礎(chǔ)算法使用。為了改進(jìn)人工智能算法,，研究者們采用混合調(diào)度策略或者設(shè)置相關(guān)約束條件來不斷加快算法的收斂速度,。其中蟻群算法［6］是一種有效的隨機(jī)模擬進(jìn)化算法，它模擬蟻群覓食過程中發(fā)現(xiàn)最優(yōu)路徑的過程,，可用于解決組合優(yōu)化問題,。

2基本蟻群算法

　　蟻群算法是一種人工螞蟻合作來找到一個(gè)給定的問題的優(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ò)路由等,。實(shí)驗(yàn)證明該算法能較為出色地解決復(fù)雜優(yōu)化問題,特別是離散性優(yōu)化問題,，是一種比較卓越的優(yōu)化算法。

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

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

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

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

　?。?）生成蟻群；

　?。?）設(shè)置初始化信息,；

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

　　（4）記錄信息素變量,；

　?。?）信息素變量的更新。

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

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

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

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

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

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

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

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

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

4實(shí)驗(yàn)結(jié)果及分析

　　在 Microsoft Visual C++ 60 上使用 C語(yǔ)言實(shí)現(xiàn)了本文提出的優(yōu)化的蟻群算法,。用有向無環(huán)圖（DAG）對(duì)任務(wù)進(jìn)行建模。圖2表示了一個(gè)程序的任務(wù)圖,。

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

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

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

5結(jié)論

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

　　優(yōu)化算法在平均任務(wù)調(diào)度長(zhǎng)度和最優(yōu)解的任務(wù)調(diào)度長(zhǎng)度上的表現(xiàn)均優(yōu)于相比較的算法。

參考文獻(xiàn)

　?。?］ 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.

　?。?］ 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.

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

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

　?。?］ 周會(huì)嬌．異構(gòu)多核系統(tǒng)多媒體流計(jì)算實(shí)時(shí)任務(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.

　?。?］ 朱君,蔡延光,湯雅連,，等.改進(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.

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