關(guān)沫， 佟彤

沈陽工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 沈陽 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)算法。然而，即使在簡化了一些問題的假設(shè)后，多核系統(tǒng)的任務(wù)調(diào)度也是NP（Nondeterministic Polynomial）難題［1］。傳統(tǒng)窮舉法計(jì)算復(fù)雜度大，耗時(shí)長［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］、禁忌搜索算法、鄰域搜索算法、蟻群算法等。它們擅長找到全局最優(yōu)解，但也普遍存在算法收斂時(shí)間較長的缺點(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è)兩條路徑，其中一邊的路徑比另一邊長。首先，螞蟻通過隨機(jī)運(yùn)動(dò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ù)選擇處理器；

　?。?）記錄信息素變量；

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

　　圖1蟻群優(yōu)化算法流程圖在第一階段，只是創(chuàng)建一個(gè)長度為n的列表。在第二階段，每只螞蟻從準(zhǔn)備列表中選擇一個(gè)任務(wù)，并為該任務(wù)選擇一個(gè)處理核，直到完成任務(wù)調(diào)度。在每次迭代中，N只螞蟻就會(huì)得到N組可行解。選擇一組任務(wù)調(diào)度長度最短的解作為一次迭代的最優(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)度長度，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語言實(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)度長度較短，充分證明了本文混合算法的可行性。

　　同時(shí)改進(jìn)蟻群算法與基本蟻群算法進(jìn)行比較，分析結(jié)果如圖3、圖4所示。從圖3可知，改進(jìn)蟻群算法的平均任務(wù)調(diào)度長度明顯優(yōu)于基本蟻群算法；圖4將不同算法得到的最優(yōu)解進(jìn)行對(duì)比，可知改進(jìn)蟻群算法得到的最優(yōu)解的任務(wù)調(diào)度長度更短并且較穩(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)度長度和最優(yōu)解的任務(wù)調(diào)度長度上的表現(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.

　　［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.

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

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

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

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