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

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

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

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

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