本文關鍵詞：多核系統(tǒng)靜態(tài)任務調(diào)度問題研究

  更多相關文章： 調(diào)度算法 拓撲序列 靜態(tài)任務 多核

【摘要】：由于傳統(tǒng)單核處理器的性能已經(jīng)遇到發(fā)展瓶頸,多核處理器應運而生并獲得廣泛應用。作為多核技術的一個重要方面,任務調(diào)度是備受關注的一類NPC(Non-deterministic Polynomial Complete)問題。對于多核處理器的靜態(tài)任務調(diào)度問題,經(jīng)典列表調(diào)度(Simple List Scheduling, SLS)算法難以獲得滿意的調(diào)度解。本文從經(jīng)典列表調(diào)度算法缺陷——只考慮任務優(yōu)先級列表而忽略其它對應于更好調(diào)度結果的任務圖拓撲序列出發(fā),以拓展任務圖拓撲序列搜索空間為指導,提出了迭代型列表調(diào)度方法,并給出兩種迭代型列表調(diào)度算法實現(xiàn)：ILS-Mb (Iterative List Scheduling with Macroblock)和ILS-RS (Iterative List Scheduling with Random Swapping).其中迭代型列表調(diào)度算法ILS-Mb通過遍歷宏塊拓撲序列擴大任務圖拓撲序列搜索空間,迭代型列表調(diào)度算法ILS-RS則通過對換兩個隨機任務的優(yōu)先級以生成新的任務圖拓撲序列。ILS-Mb算法和ILS-RS算法的共同之處在于多次進行列表調(diào)度并根據(jù)調(diào)度長度最小化原則篩選最優(yōu)調(diào)度解。本文進一步地結合粒子群算法采用多個初始最優(yōu)解的基本思路提出組合型列表調(diào)度方法。組合型列表調(diào)度方法以多個最優(yōu)任務圖拓撲序列作為初始解避免單個任務圖拓撲序列陷入局部最優(yōu)解。迭代型列表調(diào)度方法和組合型列表調(diào)度方法的結合形成迭代-組合型列表調(diào)度方法,以更高的算法時間復雜度以期獲取更小的調(diào)度長度。文中通過理論分析證明,對于任意的一個任務圖,兩種迭代型列表調(diào)度方法所得的調(diào)度長度必不大于經(jīng)典列表調(diào)度算法。為證實本文提出的迭代型列表調(diào)度方法的良好性能,文中采用四種常見類型任務圖生成大量的任務圖樣本進行兩個部分的對比實驗。統(tǒng)計結果首先表明：在全互聯(lián)通訊環(huán)境迭代型的列表調(diào)度算法ILS-Mb和ILS-RS能夠有效改善經(jīng)典列表調(diào)度算法的調(diào)度解,尤其在通信代價比超過1的情況下,調(diào)度性能提升超過14.6%,最大的調(diào)度性能提升達到102.8%以上：在片上網(wǎng)絡通訊環(huán)境ILS-Mb算法和ILS-RS算法的相對性能優(yōu)勢更加明顯。統(tǒng)計結果指出迭代型列表調(diào)度算法的調(diào)度效果優(yōu)于ALS (Advanced List Scheduling)和CPOP (Critical Path on Processor)算法。實驗數(shù)據(jù)還表明ILS-Mb和ILS-RS算法對調(diào)度解初始值不具有敏感性。
【關鍵詞】：調(diào)度算法 拓撲序列 靜態(tài)任務 多核
【學位授予單位】：合肥工業(yè)大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：TP332
【目錄】：

• 致謝7-8
• 摘要8-9
• ABSTRACT9-16
• 第一章 緒論16-21
• 1.1 課題的背景與意義16-17
• 1.2 國內(nèi)外研究現(xiàn)狀17-19
• 1.2.1 國外研究現(xiàn)狀17-18
• 1.2.2 國內(nèi)研究現(xiàn)狀18-19
• 1.3 論文的主要工作19
• 1.4 論文的組織結構19-21
• 第二章 任務調(diào)度問題概述21-31
• 2.1 多核微處理器的體系結構21-23
• 2.2 任務調(diào)度問題的多核系統(tǒng)模型23-24
• 2.3 任務調(diào)度問題的應用程序模型24-25
• 2.4 任務調(diào)度問題相關概念25-27
• 2.5 任務調(diào)度問題的NPC特性27-28
• 2.6 任務調(diào)度方案28-30
• 2.6.1 任務復制28-29
• 2.6.2 任務聚簇29
• 2.6.3 列表調(diào)度29-30
• 2.7 本章小結30-31
• 第三章 迭代型列表調(diào)度算法的設計方案31-41
• 3.1 經(jīng)典列表調(diào)度算法及其缺陷31-34
• 3.2 迭代型列表調(diào)度方法34-35
• 3.3 組合型列表調(diào)度方法35-36
• 3.4 迭代—組合型列表調(diào)度方法36-37
• 3.5 片上網(wǎng)絡通訊環(huán)境下的列表調(diào)度37-40
• 3.6 本章小結40-41
• 第四章 迭代型列表調(diào)度方法的算法實現(xiàn)41-56
• 4.1 SC算法41-47
• 4.1.1 宏塊41-42
• 4.1.2 宏塊拓撲序列42
• 4.1.3 宏塊劃分42
• 4.1.4 子任務圖42-43
• 4.1.5 SC算法實現(xiàn)43-45
• 4.1.6 SC算法性能測試45-47
• 4.2 ILS-Mb算法47-52
• 4.2.1 宏塊調(diào)度47-48
• 4.2.2 ILS-Mb算法實現(xiàn)48-52
• 4.3 ILS-RS算法52-55
• 4.4 本章小結55-56
• 第五章 靜態(tài)任務調(diào)度算法的性能測試56-70
• 5.1 性能評估參數(shù)選取56
• 5.2 樣本任務圖的生成56-58
• 5.3 對比試驗58-69
• 5.3.1 ILS算法和SLS算法的性能對比59-67
• 5.3.2 ILS和其它算法的性能對比67-68
• 5.3.3 ILS算法調(diào)度解初始值的設定68-69
• 5.4 本章小結69-70
• 第六章 總結和展望70-72
• 參考文獻72-75
• 攻讀碩士學位期間的學術活動和成果情況75

【相似文獻】

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

1 孟憲福;基于優(yōu)先級的任務調(diào)度與負載均衡模型研究[J];小型微型計算機系統(tǒng);2005年09期

2 廖曉文;廖京盛;;時間觸發(fā)模式的任務調(diào)度與分解策略[J];單片機與嵌入式系統(tǒng)應用;2006年07期

3 樊曉香;;任務調(diào)度問題機制設計[J];計算機技術與發(fā)展;2008年07期

4 黃漾;;分布式環(huán)境下任務調(diào)度探討[J];電腦知識與技術;2011年19期

5 陳軍;謝立;孫鐘秀;;分布式任務調(diào)度研究的新趨向[J];計算機研究與發(fā)展;1990年04期

6 陳艇;;基于混沌最優(yōu)博弈的網(wǎng)絡任務調(diào)度算法仿真[J];計算機仿真;2013年11期

7 李陶深;李明麗;張希翔;;云計算環(huán)境下任務調(diào)度技術的研究進展[J];玉林師范學院學報;2014年02期

8 劉雄文,陸鑫達;元計算環(huán)境中任務調(diào)度的深入分析[J];計算機工程與應用;2002年17期

9 羅紅,慕德俊,鄧智群,王曉東;網(wǎng)格計算中任務調(diào)度研究綜述[J];計算機應用研究;2005年05期

10 張國海;江平宇;周光輝;;多設計任務調(diào)度的非合作博弈研究[J];西安交通大學學報;2007年03期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 劉培培;李連;叢海鵬;謝勇;;基于多代理協(xié)商機制的任務調(diào)度系統(tǒng)研究[A];2006北京地區(qū)高校研究生學術交流會——通信與信息技術會議論文集（下）[C];2006年

2 張磊;馬軍;;描述短時資源混雜占用型任務調(diào)度的數(shù)學模型與算法[A];2005年全國理論計算機科學學術年會論文集[C];2005年

3 王軍;巢玉強;彭釗軼;;基于任務調(diào)度的電能量計量采集系統(tǒng)的設計與實現(xiàn)[A];2006電力系統(tǒng)自動化學術交流研討大會論文集[C];2006年

4 張志強;王萬玉;王建平;李凡;袁剛;;多站多星任務調(diào)度優(yōu)化模型研究[A];第二十三屆全國空間探測學術交流會論文摘要集[C];2010年

5 韓云;于炯;張偉;王命全;;基于負載均衡的任務調(diào)度改進算法[A];2010年全國開放式分布與并行計算機學術會議論文集[C];2010年

6 王全民;王靚;許智宏;;網(wǎng)格環(huán)境中基于蟻群算法的批量任務調(diào)度的研究[A];2006北京地區(qū)高校研究生學術交流會——通信與信息技術會議論文集（上）[C];2006年

7 張曉云;岳繼光;楊麟祥;;零星任務調(diào)度在多控制任務系統(tǒng)中的應用[A];第16屆中國過程控制學術年會暨第4屆全國故障診斷與安全性學術會議論文集[C];2005年

8 劉宇;劉玉榮;周冰;;基于WCF的環(huán)境減災星座運控任務調(diào)度系統(tǒng)[A];第二十五屆全國空間探測學術研討會摘要集[C];2012年

9 黃文澤;邵峰晶;孫仁誠;;基于雙總線安全結構的操作系統(tǒng)任務調(diào)度[A];2009全國計算機網(wǎng)絡與通信學術會議論文集[C];2009年

10 楊艦;黃道平;李小亞;;GDCS任務調(diào)度的SPN模型研究[A];第二十六屆中國控制會議論文集[C];2007年

中國重要報紙全文數(shù)據(jù)庫 前1條

1 王波;Linux與服務器集群技術[N];中國計算機報;2002年

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

1 趙凡宇;航天器多目標觀測任務調(diào)度與規(guī)劃方法研究[D];北京理工大學;2015年

2 孫明明;云計算平臺上任務調(diào)度算法的研究[D];中國科學技術大學;2015年

3 郭力爭;云計算環(huán)境下資源部署與任務調(diào)度研究[D];東華大學;2015年

4 黃萬偉;基于服務屬性區(qū)分的可重構任務調(diào)度研究[D];解放軍信息工程大學;2009年

5 瞿進;可重構系統(tǒng)軟硬功能劃分及任務調(diào)度技術研究[D];解放軍信息工程大學;2011年

6 周雙娥;實時分布容錯系統(tǒng)的任務調(diào)度技術研究[D];哈爾濱工程大學;2003年

7 柴亞輝;基于FPGA的高性能計算架構硬件任務與資源模型研究[D];上海大學;2012年

8 金剛;云環(huán)境下任務調(diào)度關鍵問題研究[D];吉林大學;2015年

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

10 陳錫明;基于NOW的任務調(diào)度和負載平衡方法研究[D];電子科技大學;2000年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 張巧龍;云計算環(huán)境下任務調(diào)度問題的研究[D];江南大學;2015年

2 徐彬;云環(huán)境下基于動態(tài)融合遺傳蟻群算法的DAG任務調(diào)度研究[D];南京信息工程大學;2015年

3 姜志剛;數(shù)據(jù)中心溫度感知任務調(diào)度技術研究[D];南京大學;2014年

4 周凱;Hadoop任務調(diào)度本地化研究[D];華中科技大學;2014年

5 聶如云;云服務系統(tǒng)任務調(diào)度負載均衡的研究[D];首都經(jīng)濟貿(mào)易大學;2016年

6 張金虎;云計算環(huán)境下基于服務成本的任務調(diào)度研究[D];云南大學;2016年

7 王靖云;面向iVCE云平臺的數(shù)據(jù)分析任務調(diào)度系統(tǒng)的設計與實現(xiàn)[D];哈爾濱工業(yè)大學;2016年

8 肖健;基于分布式任務調(diào)度的機票旗艦店系統(tǒng)的設計與實現(xiàn)[D];哈爾濱工業(yè)大學;2016年

9 李夢盈;基于動態(tài)優(yōu)先級的云計算任務調(diào)度研究[D];南京信息工程大學;2016年

10 范增輝;進化算法在軟件工程任務調(diào)度中的研究與應用[D];江南大學;2016年

，

本文編號：942175