多核系統(tǒng)靜態(tài)任務(wù)調(diào)度問題研究
本文關(guān)鍵詞:多核系統(tǒng)靜態(tài)任務(wù)調(diào)度問題研究
更多相關(guān)文章: 調(diào)度算法 拓?fù)湫蛄?/b> 靜態(tài)任務(wù) 多核
【摘要】:由于傳統(tǒng)單核處理器的性能已經(jīng)遇到發(fā)展瓶頸,多核處理器應(yīng)運(yùn)而生并獲得廣泛應(yīng)用。作為多核技術(shù)的一個(gè)重要方面,任務(wù)調(diào)度是備受關(guān)注的一類NPC(Non-deterministic Polynomial Complete)問題。對(duì)于多核處理器的靜態(tài)任務(wù)調(diào)度問題,經(jīng)典列表調(diào)度(Simple List Scheduling, SLS)算法難以獲得滿意的調(diào)度解。本文從經(jīng)典列表調(diào)度算法缺陷——只考慮任務(wù)優(yōu)先級(jí)列表而忽略其它對(duì)應(yīng)于更好調(diào)度結(jié)果的任務(wù)圖拓?fù)湫蛄谐霭l(fā),以拓展任務(wù)圖拓?fù)湫蛄兴阉骺臻g為指導(dǎo),提出了迭代型列表調(diào)度方法,并給出兩種迭代型列表調(diào)度算法實(shí)現(xiàn):ILS-Mb (Iterative List Scheduling with Macroblock)和ILS-RS (Iterative List Scheduling with Random Swapping).其中迭代型列表調(diào)度算法ILS-Mb通過遍歷宏塊拓?fù)湫蛄袛U(kuò)大任務(wù)圖拓?fù)湫蛄兴阉骺臻g,迭代型列表調(diào)度算法ILS-RS則通過對(duì)換兩個(gè)隨機(jī)任務(wù)的優(yōu)先級(jí)以生成新的任務(wù)圖拓?fù)湫蛄。ILS-Mb算法和ILS-RS算法的共同之處在于多次進(jìn)行列表調(diào)度并根據(jù)調(diào)度長度最小化原則篩選最優(yōu)調(diào)度解。本文進(jìn)一步地結(jié)合粒子群算法采用多個(gè)初始最優(yōu)解的基本思路提出組合型列表調(diào)度方法。組合型列表調(diào)度方法以多個(gè)最優(yōu)任務(wù)圖拓?fù)湫蛄凶鳛槌跏冀獗苊鈫蝹(gè)任務(wù)圖拓?fù)湫蛄邢萑刖植孔顑?yōu)解。迭代型列表調(diào)度方法和組合型列表調(diào)度方法的結(jié)合形成迭代-組合型列表調(diào)度方法,以更高的算法時(shí)間復(fù)雜度以期獲取更小的調(diào)度長度。文中通過理論分析證明,對(duì)于任意的一個(gè)任務(wù)圖,兩種迭代型列表調(diào)度方法所得的調(diào)度長度必不大于經(jīng)典列表調(diào)度算法。為證實(shí)本文提出的迭代型列表調(diào)度方法的良好性能,文中采用四種常見類型任務(wù)圖生成大量的任務(wù)圖樣本進(jìn)行兩個(gè)部分的對(duì)比實(shí)驗(yàn)。統(tǒng)計(jì)結(jié)果首先表明:在全互聯(lián)通訊環(huán)境迭代型的列表調(diào)度算法ILS-Mb和ILS-RS能夠有效改善經(jīng)典列表調(diào)度算法的調(diào)度解,尤其在通信代價(jià)比超過1的情況下,調(diào)度性能提升超過14.6%,最大的調(diào)度性能提升達(dá)到102.8%以上:在片上網(wǎng)絡(luò)通訊環(huán)境ILS-Mb算法和ILS-RS算法的相對(duì)性能優(yōu)勢(shì)更加明顯。統(tǒng)計(jì)結(jié)果指出迭代型列表調(diào)度算法的調(diào)度效果優(yōu)于ALS (Advanced List Scheduling)和CPOP (Critical Path on Processor)算法。實(shí)驗(yàn)數(shù)據(jù)還表明ILS-Mb和ILS-RS算法對(duì)調(diào)度解初始值不具有敏感性。
【關(guān)鍵詞】:調(diào)度算法 拓?fù)湫蛄?/strong> 靜態(tài)任務(wù) 多核
【學(xué)位授予單位】:合肥工業(yè)大學(xué)
【學(xué)位級(jí)別】:碩士
【學(xué)位授予年份】:2016
【分類號(hào)】: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 論文的組織結(jié)構(gòu)19-21
- 第二章 任務(wù)調(diào)度問題概述21-31
- 2.1 多核微處理器的體系結(jié)構(gòu)21-23
- 2.2 任務(wù)調(diào)度問題的多核系統(tǒng)模型23-24
- 2.3 任務(wù)調(diào)度問題的應(yīng)用程序模型24-25
- 2.4 任務(wù)調(diào)度問題相關(guān)概念25-27
- 2.5 任務(wù)調(diào)度問題的NPC特性27-28
- 2.6 任務(wù)調(diào)度方案28-30
- 2.6.1 任務(wù)復(fù)制28-29
- 2.6.2 任務(wù)聚簇29
- 2.6.3 列表調(diào)度29-30
- 2.7 本章小結(jié)30-31
- 第三章 迭代型列表調(diào)度算法的設(shè)計(jì)方案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)絡(luò)通訊環(huán)境下的列表調(diào)度37-40
- 3.6 本章小結(jié)40-41
- 第四章 迭代型列表調(diào)度方法的算法實(shí)現(xiàn)41-56
- 4.1 SC算法41-47
- 4.1.1 宏塊41-42
- 4.1.2 宏塊拓?fù)湫蛄?/span>42
- 4.1.3 宏塊劃分42
- 4.1.4 子任務(wù)圖42-43
- 4.1.5 SC算法實(shí)現(xiàn)43-45
- 4.1.6 SC算法性能測(cè)試45-47
- 4.2 ILS-Mb算法47-52
- 4.2.1 宏塊調(diào)度47-48
- 4.2.2 ILS-Mb算法實(shí)現(xiàn)48-52
- 4.3 ILS-RS算法52-55
- 4.4 本章小結(jié)55-56
- 第五章 靜態(tài)任務(wù)調(diào)度算法的性能測(cè)試56-70
- 5.1 性能評(píng)估參數(shù)選取56
- 5.2 樣本任務(wù)圖的生成56-58
- 5.3 對(duì)比試驗(yàn)58-69
- 5.3.1 ILS算法和SLS算法的性能對(duì)比59-67
- 5.3.2 ILS和其它算法的性能對(duì)比67-68
- 5.3.3 ILS算法調(diào)度解初始值的設(shè)定68-69
- 5.4 本章小結(jié)69-70
- 第六章 總結(jié)和展望70-72
- 參考文獻(xiàn)72-75
- 攻讀碩士學(xué)位期間的學(xué)術(shù)活動(dòng)和成果情況75
【相似文獻(xiàn)】
中國期刊全文數(shù)據(jù)庫 前10條
1 孟憲福;基于優(yōu)先級(jí)的任務(wù)調(diào)度與負(fù)載均衡模型研究[J];小型微型計(jì)算機(jī)系統(tǒng);2005年09期
2 廖曉文;廖京盛;;時(shí)間觸發(fā)模式的任務(wù)調(diào)度與分解策略[J];單片機(jī)與嵌入式系統(tǒng)應(yīng)用;2006年07期
3 樊曉香;;任務(wù)調(diào)度問題機(jī)制設(shè)計(jì)[J];計(jì)算機(jī)技術(shù)與發(fā)展;2008年07期
4 黃漾;;分布式環(huán)境下任務(wù)調(diào)度探討[J];電腦知識(shí)與技術(shù);2011年19期
5 陳軍;謝立;孫鐘秀;;分布式任務(wù)調(diào)度研究的新趨向[J];計(jì)算機(jī)研究與發(fā)展;1990年04期
6 陳艇;;基于混沌最優(yōu)博弈的網(wǎng)絡(luò)任務(wù)調(diào)度算法仿真[J];計(jì)算機(jī)仿真;2013年11期
7 李陶深;李明麗;張希翔;;云計(jì)算環(huán)境下任務(wù)調(diào)度技術(shù)的研究進(jìn)展[J];玉林師范學(xué)院學(xué)報(bào);2014年02期
8 劉雄文,陸鑫達(dá);元計(jì)算環(huán)境中任務(wù)調(diào)度的深入分析[J];計(jì)算機(jī)工程與應(yīng)用;2002年17期
9 羅紅,慕德俊,鄧智群,王曉東;網(wǎng)格計(jì)算中任務(wù)調(diào)度研究綜述[J];計(jì)算機(jī)應(yīng)用研究;2005年05期
10 張國海;江平宇;周光輝;;多設(shè)計(jì)任務(wù)調(diào)度的非合作博弈研究[J];西安交通大學(xué)學(xué)報(bào);2007年03期
中國重要會(huì)議論文全文數(shù)據(jù)庫 前10條
1 劉培培;李連;叢海鵬;謝勇;;基于多代理協(xié)商機(jī)制的任務(wù)調(diào)度系統(tǒng)研究[A];2006北京地區(qū)高校研究生學(xué)術(shù)交流會(huì)——通信與信息技術(shù)會(huì)議論文集(下)[C];2006年
2 張磊;馬軍;;描述短時(shí)資源混雜占用型任務(wù)調(diào)度的數(shù)學(xué)模型與算法[A];2005年全國理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會(huì)論文集[C];2005年
3 王軍;巢玉強(qiáng);彭釗軼;;基于任務(wù)調(diào)度的電能量計(jì)量采集系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[A];2006電力系統(tǒng)自動(dòng)化學(xué)術(shù)交流研討大會(huì)論文集[C];2006年
4 張志強(qiáng);王萬玉;王建平;李凡;袁剛;;多站多星任務(wù)調(diào)度優(yōu)化模型研究[A];第二十三屆全國空間探測(cè)學(xué)術(shù)交流會(huì)論文摘要集[C];2010年
5 韓云;于炯;張偉;王命全;;基于負(fù)載均衡的任務(wù)調(diào)度改進(jìn)算法[A];2010年全國開放式分布與并行計(jì)算機(jī)學(xué)術(shù)會(huì)議論文集[C];2010年
6 王全民;王靚;許智宏;;網(wǎng)格環(huán)境中基于蟻群算法的批量任務(wù)調(diào)度的研究[A];2006北京地區(qū)高校研究生學(xué)術(shù)交流會(huì)——通信與信息技術(shù)會(huì)議論文集(上)[C];2006年
7 張曉云;岳繼光;楊麟祥;;零星任務(wù)調(diào)度在多控制任務(wù)系統(tǒng)中的應(yīng)用[A];第16屆中國過程控制學(xué)術(shù)年會(huì)暨第4屆全國故障診斷與安全性學(xué)術(shù)會(huì)議論文集[C];2005年
8 劉宇;劉玉榮;周冰;;基于WCF的環(huán)境減災(zāi)星座運(yùn)控任務(wù)調(diào)度系統(tǒng)[A];第二十五屆全國空間探測(cè)學(xué)術(shù)研討會(huì)摘要集[C];2012年
9 黃文澤;邵峰晶;孫仁誠;;基于雙總線安全結(jié)構(gòu)的操作系統(tǒng)任務(wù)調(diào)度[A];2009全國計(jì)算機(jī)網(wǎng)絡(luò)與通信學(xué)術(shù)會(huì)議論文集[C];2009年
10 楊艦;黃道平;李小亞;;GDCS任務(wù)調(diào)度的SPN模型研究[A];第二十六屆中國控制會(huì)議論文集[C];2007年
中國重要報(bào)紙全文數(shù)據(jù)庫 前1條
1 王波;Linux與服務(wù)器集群技術(shù)[N];中國計(jì)算機(jī)報(bào);2002年
中國博士學(xué)位論文全文數(shù)據(jù)庫 前10條
1 趙凡宇;航天器多目標(biāo)觀測(cè)任務(wù)調(diào)度與規(guī)劃方法研究[D];北京理工大學(xué);2015年
2 孫明明;云計(jì)算平臺(tái)上任務(wù)調(diào)度算法的研究[D];中國科學(xué)技術(shù)大學(xué);2015年
3 郭力爭;云計(jì)算環(huán)境下資源部署與任務(wù)調(diào)度研究[D];東華大學(xué);2015年
4 黃萬偉;基于服務(wù)屬性區(qū)分的可重構(gòu)任務(wù)調(diào)度研究[D];解放軍信息工程大學(xué);2009年
5 瞿進(jìn);可重構(gòu)系統(tǒng)軟硬功能劃分及任務(wù)調(diào)度技術(shù)研究[D];解放軍信息工程大學(xué);2011年
6 周雙娥;實(shí)時(shí)分布容錯(cuò)系統(tǒng)的任務(wù)調(diào)度技術(shù)研究[D];哈爾濱工程大學(xué);2003年
7 柴亞輝;基于FPGA的高性能計(jì)算架構(gòu)硬件任務(wù)與資源模型研究[D];上海大學(xué);2012年
8 金剛;云環(huán)境下任務(wù)調(diào)度關(guān)鍵問題研究[D];吉林大學(xué);2015年
9 耿曉中;基于多核分布式環(huán)境下的任務(wù)調(diào)度關(guān)鍵技術(shù)研究[D];吉林大學(xué);2013年
10 陳錫明;基于NOW的任務(wù)調(diào)度和負(fù)載平衡方法研究[D];電子科技大學(xué);2000年
中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條
1 張巧龍;云計(jì)算環(huán)境下任務(wù)調(diào)度問題的研究[D];江南大學(xué);2015年
2 徐彬;云環(huán)境下基于動(dòng)態(tài)融合遺傳蟻群算法的DAG任務(wù)調(diào)度研究[D];南京信息工程大學(xué);2015年
3 姜志剛;數(shù)據(jù)中心溫度感知任務(wù)調(diào)度技術(shù)研究[D];南京大學(xué);2014年
4 周凱;Hadoop任務(wù)調(diào)度本地化研究[D];華中科技大學(xué);2014年
5 聶如云;云服務(wù)系統(tǒng)任務(wù)調(diào)度負(fù)載均衡的研究[D];首都經(jīng)濟(jì)貿(mào)易大學(xué);2016年
6 張金虎;云計(jì)算環(huán)境下基于服務(wù)成本的任務(wù)調(diào)度研究[D];云南大學(xué);2016年
7 王靖云;面向iVCE云平臺(tái)的數(shù)據(jù)分析任務(wù)調(diào)度系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D];哈爾濱工業(yè)大學(xué);2016年
8 肖健;基于分布式任務(wù)調(diào)度的機(jī)票旗艦店系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D];哈爾濱工業(yè)大學(xué);2016年
9 李夢(mèng)盈;基于動(dòng)態(tài)優(yōu)先級(jí)的云計(jì)算任務(wù)調(diào)度研究[D];南京信息工程大學(xué);2016年
10 范增輝;進(jìn)化算法在軟件工程任務(wù)調(diào)度中的研究與應(yīng)用[D];江南大學(xué);2016年
,本文編號(hào):942175
本文鏈接:http://sikaile.net/kejilunwen/jisuanjikexuelunwen/942175.html