一種基于蟻群算法的民構多核周期多幀任務調度算法研究.pdf

1、異構多核處理器以其高效率、低成本等優(yōu)勢被廣泛應用于嵌入式系統(tǒng)、多媒體應用等諸多領域。高效合理地將任務分配至固定數目的處理單元使任務完成總成本最小，是異構多核系統(tǒng)上任務調度的關鍵問題。由于異構多核系統(tǒng)處理單元異構性的不斷增強，以及任務復雜度的持續(xù)增加，使得異構多核系統(tǒng)上任務調度算法研究面臨更嚴峻的挑戰(zhàn)。
　　當前在異構多核任務調度研究中對經典周期任務的研究通常采用任務的單一最大處理時間，較少考慮任務模型的多幀性。這就造成了在分析任務

2、可調度性時，使一部分本可調度的任務被錯誤地判定為不可調度。本文針對現有模型對周期任務描述不完全、已有周期多幀任務調度算法存在策略時間復雜度高等問題，參照經典周期任務，并結合任務多幀特性，在構建具有累積單調性質的異構多核多幀周期任務模型的基礎上，設計了一種蟻群算法與遺傳算法相融合的任務調度算法，以提高多幀周期任務在異構多核系統(tǒng)中的實時性和準確性。主要工作如下：
　　針對傳統(tǒng)任務模型因沒考慮任務多幀特性而造成誤判的問題，研究并建立了具

3、有累積單調性質的異構多核多幀周期任務模型。該模型具有能分配更多任務的優(yōu)勢，也集中體現了計算平臺的異構性及任務的多幀性；從處理器利用率及任務響應時間兩方面闡述論證了多幀任務調度的可行性。
　　結合異構多核多幀周期任務模型設計了基于蟻群算法的異構多核多幀任務調度算法--ACGO(Ant Colony Genetic Optimization)調度算法。該算法在傳統(tǒng)蟻群算法的基礎上做了如下改進：引入了遺傳算法中的復制、交叉、變異等遺傳因

4、子，以提高算法的收斂速度和全局搜索能力；同時改進了信息素的更新方式，以提高蟻群算法的自適應性，使得算法在執(zhí)行過程中能根據收斂和進展情況，動態(tài)地調整信息殘留程度，從而提高算法的收斂速度或全局搜索能力；此外引入了一種確定性搜索方法，來加快啟發(fā)式搜索的收斂速度。
　　為驗證本文算法的性能，設計實現了一個模擬系統(tǒng)，并在該系統(tǒng)上仿真實現了本文算法及相關算法，將本文算法從可行性和運行時間兩方面進行了對比評估。實驗結果表明，考慮了多幀特性的異構