本文關(guān)鍵詞：基于任務(wù)分裂的多核平臺實(shí)時(shí)任務(wù)調(diào)度研究，由筆耕文化傳播整理發(fā)布。

【摘要】：近年來,隨著多核平臺在市場上的激增,研究熱點(diǎn)逐漸轉(zhuǎn)移到執(zhí)行復(fù)雜、計(jì)算密集型的任務(wù)上,而多核處理器的復(fù)雜性往往會(huì)使任務(wù)行為不統(tǒng)一、不可預(yù)測,變化性極大。由于許多任務(wù)間可能存在約束性依賴關(guān)系,任務(wù)分配變得不協(xié)調(diào),導(dǎo)致互相等待而錯(cuò)過期限超時(shí)。因此,基于獨(dú)立任務(wù)的傳統(tǒng)實(shí)時(shí)任務(wù)調(diào)度理論面臨著巨大的挑戰(zhàn),考慮到依賴任務(wù)集合的調(diào)度算法越來越成為研究的新方向。 本文在分析和研究國內(nèi)外現(xiàn)有多核平臺實(shí)時(shí)任務(wù)調(diào)度算法的基礎(chǔ)上,在分區(qū)調(diào)度和全局調(diào)度之間找到了折中點(diǎn),提出了一種基于任務(wù)拆分的多核平臺實(shí)時(shí)任務(wù)調(diào)度的策略TDTD/TS (Tree Dependent Task Dispatching/Task Splitting)并且設(shè)計(jì)和實(shí)施了該策略的算法。該策略構(gòu)建于多核平臺上的混合實(shí)時(shí)任務(wù)(依賴和非依賴任務(wù))之上,鑒于實(shí)時(shí)應(yīng)用中嚴(yán)格時(shí)間保證的共性需求,綜合考慮任務(wù)的動(dòng)態(tài)性和依賴性對系統(tǒng)性能的影響。采用層次調(diào)度的方式設(shè)計(jì)本方案,具體方法分為兩個(gè)階段：TDTD (TreeDependent Task Dispatching,多叉樹依賴任務(wù)分配)和TDTS (Tree Dependent Task Split,多叉樹依賴任務(wù)分裂)。TDTD將依賴任務(wù)轉(zhuǎn)換成一系列的連續(xù)作業(yè),通過多叉樹任務(wù)模型獲取相互關(guān)聯(lián)的子任務(wù)路徑,以及相應(yīng)的最后期限,對任務(wù)分配,建立任務(wù)表；TDTS算法中,本地調(diào)度程序會(huì)根據(jù)任務(wù)表來分配給任務(wù)處理器內(nèi)核使用權(quán),空閑等待狀態(tài)的依賴任務(wù)進(jìn)行分裂,所有被阻止的子任務(wù)搶占CPU立即執(zhí)行保證期限。與已有算法相比,本算法具有明顯優(yōu)勢,任務(wù)集合對處理器利用率邊界可達(dá)到69.31%。 通過仿真軟件gem5和實(shí)驗(yàn)機(jī)上進(jìn)行性能測試,并與已有算法進(jìn)行對比,對協(xié)議進(jìn)行可調(diào)度性和實(shí)時(shí)性QOS性能分析,在時(shí)間比率、調(diào)度下界比SLR (Schedule Length Ratio)和加速比Speedup方面表現(xiàn)優(yōu)異,結(jié)果證明TDTD/TS提供了更高的效率和擴(kuò)展性,具有相對的優(yōu)越性。
【關(guān)鍵詞】：實(shí)時(shí)調(diào)度 多核平臺 任務(wù)依賴 任務(wù)分裂
【學(xué)位授予單位】：大連理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TP332
【目錄】：

• 摘要4-5
• Abstract5-8
• 1 緒論8-13
• 1.1 研究背景與意義8
• 1.2 國內(nèi)外研究現(xiàn)狀8-11
• 1.3 論文主要工作11-12
• 1.4 論文組織結(jié)構(gòu)12-13
• 2 多核實(shí)時(shí)任務(wù)調(diào)度綜述13-21
• 2.1 多核處理器13-15
• 2.1.1 多核處理器分類13-14
• 2.1.2 多核處理器特點(diǎn)14-15
• 2.2 實(shí)時(shí)調(diào)度技術(shù)15-17
• 2.2.1 實(shí)時(shí)任務(wù)分類15-17
• 2.2.2 實(shí)時(shí)任務(wù)調(diào)度算法17
• 2.3 多核調(diào)度策略17-20
• 2.3.1 多核調(diào)度算法分類17-19
• 2.3.2 多核調(diào)度算法評估19-20
• 2.4 小結(jié)20-21
• 3 基于任務(wù)分裂的多核平臺實(shí)時(shí)任務(wù)調(diào)度策略21-35
• 3.1 策略概述21-24
• 3.1.1 應(yīng)用場景21-22
• 3.1.2 實(shí)現(xiàn)目標(biāo)22-23
• 3.1.3 總體設(shè)計(jì)23-24
• 3.2 符號定義與建模分析24-27
• 3.2.1 系統(tǒng)模型24-25
• 3.2.2 任務(wù)DAG與多叉樹25-26
• 3.2.3 依賴任務(wù)模型26-27
• 3.3 基于多叉樹的任務(wù)分配算法27-31
• 3.4 運(yùn)行時(shí)依賴任務(wù)分裂調(diào)度算法31-34
• 3.5 小結(jié)34-35
• 4 算法性能分析35-41
• 4.1 可調(diào)度性分析35-40
• 4.2 復(fù)雜度分析40
• 4.3 小結(jié)40-41
• 5 仿真實(shí)驗(yàn)與性能測試41-55
• 5.1 仿真工具與數(shù)據(jù)集41-44
• 5.1.1 gem5多核仿真器41-42
• 5.1.2 SPLASH-2 Benchmark42-44
• 5.2 實(shí)驗(yàn)與測試過程44-54
• 5.2.1 參數(shù)與指標(biāo)44-46
• 5.2.2 仿真實(shí)驗(yàn)46-51
• 5.2.3 案例測試51-54
• 5.3 結(jié)果討論54
• 5.4 小結(jié)54-55
• 結(jié)論55-56
• 參考文獻(xiàn)56-59
• 攻讀碩士學(xué)位期間發(fā)表學(xué)術(shù)論文情況59-60
• 致謝60-61

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前2條

1 陳芳園;張冬松;王志英;;異構(gòu)多核處理器體系結(jié)構(gòu)設(shè)計(jì)研究[J];計(jì)算機(jī)工程與科學(xué);2011年12期

2 王建紅;晏立;;多處理器EPDFPfair算法的可調(diào)度性判定[J];計(jì)算機(jī)工程與應(yīng)用;2013年01期

中國博士學(xué)位論文全文數(shù)據(jù)庫 前2條

1 楊志邦;一類異構(gòu)多處理器片上系統(tǒng)任務(wù)調(diào)度算法研究與應(yīng)用[D];湖南大學(xué);2012年

2 耿曉中;基于多核分布式環(huán)境下的任務(wù)調(diào)度關(guān)鍵技術(shù)研究[D];吉林大學(xué);2013年

  本文關(guān)鍵詞：基于任務(wù)分裂的多核平臺實(shí)時(shí)任務(wù)調(diào)度研究，由筆耕文化傳播整理發(fā)布。

，

本文編號：392119