任務(wù)調(diào)度問題是計算機(jī)科學(xué)研究的基本課題,多核系統(tǒng)的出現(xiàn)為任務(wù)調(diào)度問題帶來了新的變化。多核系統(tǒng)的任務(wù)調(diào)度問題首先考慮能否在保證任務(wù)得以完成情況下,尋求分配方案使得處理器繁忙程度平均,這也稱為任務(wù)的分配問題。該問題在異構(gòu)多核系統(tǒng)中更為復(fù)雜。在異構(gòu)系統(tǒng)的任務(wù)分配問題中需要綜合考慮處理器的異構(gòu)特性,使得各處理器各盡所能,任務(wù)各取所需。 當(dāng)前在異構(gòu)多核任務(wù)分配的研究中對經(jīng)典的周期任務(wù)研究較為深入,但這些研究并沒有關(guān)注具有多幀性質(zhì)的任務(wù),導(dǎo)致在分析中使用任務(wù)的單一最大處理時間,悲觀的誤判某些可以分配的任務(wù)集不能分配。 本文從經(jīng)典的周期任務(wù)入手,在研究當(dāng)前異構(gòu)多核任務(wù)分配的流行算法基礎(chǔ)上,將多幀性質(zhì)應(yīng)用于異構(gòu)多核系統(tǒng),建立新的任務(wù)模型:異構(gòu)多核多幀任務(wù)模型。該模型具有更全面的描述能力,集中體現(xiàn)了計算系統(tǒng)的異構(gòu)性和任務(wù)的多幀性。利用非線性規(guī)劃的描述方法證明新模型的優(yōu)勢,并借助遺傳算法進(jìn)行驗證。 首先對于具有AM(累積單調(diào))性質(zhì)的異構(gòu)多核多幀任務(wù),從理論上分析新模型的優(yōu)勢,即能分配更多任務(wù),其后設(shè)計遺傳算法進(jìn)行解決。為驗證理論結(jié)果和算法性能,同時針對異構(gòu)多核研究沒有統(tǒng)一平臺的問題,本文設(shè)計了一個易于擴(kuò)展的異構(gòu)多核任務(wù)分配評估系統(tǒng),實現(xiàn)文中使用的兩種方法:遺傳算法和Matlab兩步法。本文基于該系統(tǒng)進(jìn)行AM異構(gòu)多核多幀任務(wù)的模擬實驗。 在此基礎(chǔ)上,對一般異構(gòu)多核實時任務(wù)進(jìn)行了討論,使得模型具有更廣泛的應(yīng)用范圍。給出了一般異構(gòu)多核任務(wù)的相似理論分析和遺傳算法設(shè)計,通過模擬實驗證實模型的可用性,以及更全面的體現(xiàn)任務(wù)。 理論分析和實驗結(jié)果表明,考慮了多幀特性的異構(gòu)多核任務(wù)模型較悲觀的使用最大處理時間的任務(wù)分配方法可以成功分配更多任務(wù),更全面的表現(xiàn)任務(wù)性質(zhì)。遺傳算法的設(shè)計簡單實用,在較短的時間內(nèi)即能獲得很好的結(jié)果,移植性好,具有一定的應(yīng)用價值。
【學(xué)位單位】：湖南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位年份】：2009
【中圖分類】：TP332
【部分圖文】：

圖 4.1 HTES 主界面對兩個模塊分別進(jìn)行介紹。算法算法需要具備的功能包括：單個任務(wù)集的可分配性測試。S 隨機(jī)產(chǎn)生任務(wù)集，對該任務(wù)集的可分配性以及分配結(jié)果進(jìn)行個任務(wù)集的分配成功率計算。隨機(jī)產(chǎn)生的多個任務(wù)集中可分配的比例；不同幀差別下的單個任務(wù)集可分配性。定的一個任務(wù)集，改變其幀差別的大小，考察可分配性的變化個任務(wù)集的分配成功率對比。定的多個任務(wù)集，改變其幀差別大小，考察可分配比例的變化 HTES 在遺傳算法（簡稱 GA）下設(shè)計四個子功能：隨機(jī)產(chǎn)生

有 124 組任務(wù)不能分配�？紤]多幀，使用 FRM 進(jìn)行分配，幀差別范圍[5,10],[10,50]和[50,100]分別可以分配這 124 組任務(wù)中的 103，110 和 112 個。由此得到三組 RPSP 的變化情況，結(jié)果如圖 4.7 所示：圖 4.7 m=2 相對分配成功率圖 4.7 橫坐標(biāo)為任務(wù)個數(shù)，表示在兩個處理器的異構(gòu)系統(tǒng)中需要分配的任務(wù)數(shù)目，縱坐標(biāo)為相對分配成功率 RPSP。三組曲線分別表示任務(wù)幀差別產(chǎn)生范圍在[5,10],[10,50]和[50,100]的情況。由圖 4.7 可知，對比不考慮多幀，三組曲線均可多分配至少 60%的任務(wù)集，說明了新模型在提出幀差別后帶來的分配成功率提高，驗證了理論分析的正確性。同時在圖 4.7 中，三組曲線[50,100]最高，基本維持在 90%左右

c） d）圖 4.8 m=4,6,8,10 相對分配成功率以上五組實驗都表現(xiàn)出高的幀差別范圍曲線較高，說明了理論分析的正確性。4.4.3 算法時間和結(jié)果為分析算法性能，分別使用 HTES 中的 GA 模塊和 M-TS 模塊分配一組相同的異構(gòu)多核任務(wù)（如圖 4.9），系統(tǒng)規(guī)模為 10 個異構(gòu)處理器，25 個任務(wù)，利用率范圍在[0.00295, 0.495]，對本文算法和文獻(xiàn) [13]進(jìn)行比較。

【引證文獻(xiàn)】

相關(guān)博士學(xué)位論文 前1條

1 劉彥;異構(gòu)多核片上系統(tǒng)的任務(wù)調(diào)度及應(yīng)用研究[D];湖南大學(xué);2009年

相關(guān)碩士學(xué)位論文 前1條

1 李靜;基于多核的任務(wù)調(diào)度策略研究[D];哈爾濱工程大學(xué);2011年

本文編號：2816761