一種基于蟻群算法的民構(gòu)多核周期多幀任務(wù)調(diào)度算法研究.pdf

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

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

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

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