發(fā)布時(shí)間：2020-03-30 21:04

【摘要】：在計(jì)算密集型批處理任務(wù)中,有一種任務(wù)運(yùn)行時(shí)間很長(zhǎng)、且要占用大量CPU和內(nèi)存資源,例如基因測(cè)序任務(wù)。對(duì)于該種類型的任務(wù)調(diào)度策略來(lái)講,任務(wù)完成時(shí)間是衡量調(diào)度策略好壞的一個(gè)重要指標(biāo)。在任務(wù)大小和數(shù)量一定時(shí),任務(wù)完成時(shí)間越小,系統(tǒng)服務(wù)質(zhì)量越高。設(shè)計(jì)了一種面向計(jì)算密集型批處理任務(wù)的調(diào)度系統(tǒng)。該系統(tǒng)采用一種混合改進(jìn)遺傳模擬退火算法(Improved Genetic Simulated Annealing,IGSA)來(lái)進(jìn)行任務(wù)調(diào)度。該算法綜合了遺傳算法(Genetic Algorithm,GA)多點(diǎn)尋優(yōu)和模擬退火算法(Simulated Annealing,SA)局部搜索能力強(qiáng)的優(yōu)勢(shì),其基本思想是對(duì)遺傳算法的初始化方法、選擇算子、交叉算子、交叉概率、變異概率和算法的終止條件做出一定的改進(jìn),其中初始化方法采用在多個(gè)隨機(jī)解中選出一部分最優(yōu)秀解作為部分初始解的方法,選擇算子采用最優(yōu)個(gè)體直接保留到下一代的方法,交叉算子采用一種雙精英保留策略,交叉概率和變異概率采用自適應(yīng)概率的方法,算法終止條件采用種群最優(yōu)解連續(xù)幾代都沒有發(fā)生改變則終止算法的方法。然后將改進(jìn)遺傳算法(Improved Genetic Algorithm,IGA)產(chǎn)生的多個(gè)解作為模擬退火算法的輸入,同時(shí)對(duì)多個(gè)解進(jìn)行模擬退火并將結(jié)果中最優(yōu)秀的解作為算法的最終解。實(shí)驗(yàn)結(jié)果表明,相比于RoundRobin(RR)算法、改進(jìn)的遺傳算法、模擬退火算法的任務(wù)調(diào)度,混合改進(jìn)遺傳模擬退火算法更能縮短任務(wù)的完成時(shí)間,同時(shí)更能保障系統(tǒng)的負(fù)載均衡性。
【圖文】：

圖 2-6 Min-Min 算法示例2.2.3 啟發(fā)式調(diào)度算法分布式計(jì)算系統(tǒng)中任務(wù)調(diào)度是一個(gè)多對(duì)多的組合優(yōu)化問題，也是一個(gè) NP-Hard問題。群智能算法相比傳統(tǒng)算法而言在組合優(yōu)化問題上表現(xiàn)出了明顯的優(yōu)勢(shì)，，它們往往通過(guò)模擬自然界動(dòng)物群體的一些習(xí)性來(lái)表達(dá)生物的智慧。例如，遺傳算法用一個(gè)個(gè)體表示一個(gè)任務(wù)調(diào)度方案，通過(guò)種群不斷的選擇、交叉、變異而得到最優(yōu)的調(diào)度方案[34]。粒子群算法通過(guò)模擬鳥類覓食的行為使多個(gè)解之間相互交換信息從而找到最優(yōu)解[34]。蟻群算法通過(guò)模擬螞蟻尋找食物的過(guò)程中通過(guò)信息素與其它伙伴相互交流的過(guò)程而找到最佳調(diào)度方案[34]。

圖 2-7 Max-Min 算法示例2.3 本章小結(jié)數(shù)據(jù)一致性的保證、系統(tǒng)故障的處理、資源的有效利用、集群擴(kuò)展性的保障、調(diào)度策略的靈活配置等一系列問題都是調(diào)度系統(tǒng)設(shè)計(jì)的難點(diǎn)，而不同的集群調(diào)度架構(gòu)在這些問題的處理上各有千秋。調(diào)度系統(tǒng)中任務(wù)調(diào)度策略對(duì)系統(tǒng)的性能至關(guān)重要，本章在介紹了主流的集群調(diào)度架構(gòu)后，闡述了獨(dú)立任務(wù)的調(diào)度模型以及常用調(diào)度算法。
【學(xué)位授予單位】：華中科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2019
【分類號(hào)】：TP18

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 車明康;;性能比8096強(qiáng)一倍的80C 196 16位單片機(jī)[J];微電子學(xué)與計(jì)算機(jī);1988年12期

2 楊志豪;趙太銀;姚興苗;李磊;;一種適應(yīng)數(shù)據(jù)與計(jì)算密集型任務(wù)的私有云系統(tǒng)實(shí)現(xiàn)研究[J];計(jì)算機(jī)應(yīng)用研究;2011年02期

3 趙吉志;;5600系列處理器淺析[J];科技浪潮;2010年04期

4 ;成品油零售求變 安騰2在計(jì)算密集型應(yīng)用方案[J];信息系統(tǒng)工程;2004年03期

5 ;AlphaServer DS20強(qiáng)化64位計(jì)算[J];每周電腦報(bào);1999年06期

6 江先陽(yáng);劉新春;張佩珩;孫凝暉;徐志偉;;計(jì)算密集型體系集成DDR SDRAM控制器設(shè)計(jì)[J];計(jì)算機(jī)工程與科學(xué);2006年03期

7 史紅周,李錦濤,郭俊波,黃晁,葉劍;圖形終端應(yīng)用協(xié)議中計(jì)算密集型操作的分布技術(shù)[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2005年04期

8 朱敏;劉雷波;尹首一;楊晨;王文杰;魏少軍;;H.264計(jì)算密集型任務(wù)在可重構(gòu)處理器上的映射[J];電路與系統(tǒng)學(xué)報(bào);2013年02期

9 王尚萬(wàn)家;;教你打造終極游戲機(jī)[J];當(dāng)代職校生;2004年11期

10 殷開爽;駱麗;;基于SOPC的MPEG-4視頻播放器[J];單片機(jī)與嵌入式系統(tǒng)應(yīng)用;2006年05期

相關(guān)會(huì)議論文 前4條

1 張盛;張明華;劉雅杰;;云平臺(tái)SaaS模式下位場(chǎng)數(shù)據(jù)處理軟件設(shè)計(jì)與實(shí)現(xiàn)[A];2017中國(guó)地球科學(xué)聯(lián)合學(xué)術(shù)年會(huì)論文集（四十二）——專題81：應(yīng)用地球物理學(xué)前沿、專題82：工程結(jié)構(gòu)性態(tài)化設(shè)計(jì)與地震韌性、專題83：地球重力場(chǎng)及其地學(xué)應(yīng)用[C];2017年

2 唐思宇;朱振宇;許冬燕;;面向多終端協(xié)同的多域融合邊緣控制系統(tǒng)[A];物聯(lián)網(wǎng)與無(wú)線通信-2018年全國(guó)物聯(lián)網(wǎng)技術(shù)與應(yīng)用大會(huì)論文集[C];2018年

3 劉濱;石峰;;基三分層互連網(wǎng)絡(luò)中負(fù)載平衡的研究與仿真[A];中國(guó)系統(tǒng)仿真學(xué)會(huì)第五次全國(guó)會(huì)員代表大會(huì)暨2006年全國(guó)學(xué)術(shù)年會(huì)論文集[C];2006年

4 宋賢鑫;張一帆;秦曉琦;馮志勇;;車聯(lián)網(wǎng)中基于邊緣計(jì)算的感知決策技術(shù)[A];第十四屆中國(guó)智能交通年會(huì)論文集（2）[C];2019年

相關(guān)重要報(bào)紙文章 前10條

1 賽迪評(píng)測(cè)計(jì)算機(jī)整機(jī)實(shí)驗(yàn)室;圖形/計(jì)算密集型應(yīng)用用戶的選擇[N];中國(guó)計(jì)算機(jī)報(bào);2003年

2 ;計(jì)算場(chǎng)為PC帶來(lái)力量[N];網(wǎng)絡(luò)世界;2001年

3 ;IBM啟動(dòng)高性能計(jì)算計(jì)劃[N];計(jì)算機(jī)世界;2007年

4 本報(bào)記者 逄丹;高性能計(jì)算和云計(jì)算是否可以調(diào)和？[N];通信產(chǎn)業(yè)報(bào);2011年

5 云中子;解析新時(shí)代下的高性能計(jì)算[N];中國(guó)信息化周報(bào);2015年

6 計(jì)算機(jī)世界評(píng)測(cè)實(shí)驗(yàn)室 于澤;小身材 大內(nèi)涵[N];計(jì)算機(jī)世界;2012年

7 安琳 賽迪智庫(kù)軟件與信息服務(wù)業(yè)研究所;移動(dòng)云計(jì)算發(fā)展亟須突破四大瓶頸[N];通信產(chǎn)業(yè)報(bào);2014年

8 ;IBM TotalStorage DS4800[N];中國(guó)電子報(bào);2005年

9 ;Linux更快 更強(qiáng) 更企業(yè)[N];網(wǎng)絡(luò)世界;2004年

10 劉洪宇;IDF2009預(yù)示快速創(chuàng)新與整合風(fēng)向[N];中國(guó)計(jì)算機(jī)報(bào);2009年

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

1 管茂林;面向計(jì)算密集型嵌入式應(yīng)用的VLIW編譯優(yōu)化技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2012年

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

1 何昕迪;移動(dòng)微云中的任務(wù)分配框架及算法的研究[D];上海交通大學(xué);2017年

2 胡江峰;面向計(jì)算密集型批處理的任務(wù)調(diào)度策略[D];華中科技大學(xué);2019年

3 劉銳;基于移動(dòng)邊緣計(jì)算的任務(wù)卸載策略研究[D];東華大學(xué);2019年

4 左超;移動(dòng)邊緣計(jì)算中的端到端任務(wù)分配算法[D];廣東工業(yè)大學(xué);2019年

5 劉國(guó)強(qiáng);基于移動(dòng)邊緣計(jì)算的任務(wù)卸載策略研究[D];哈爾濱工業(yè)大學(xué);2018年

6 肖騫;移動(dòng)邊緣計(jì)算網(wǎng)絡(luò)聯(lián)合計(jì)算遷移決策與資源分配算法研究[D];重慶大學(xué);2018年

7 盛沖沖;計(jì)算密集型應(yīng)用在新型眾核處理機(jī)環(huán)境下的實(shí)現(xiàn)及性能[D];復(fù)旦大學(xué);2014年

8 郭俊武;移動(dòng)云環(huán)境下的計(jì)算密集型任務(wù)遷移技術(shù)[D];哈爾濱工業(yè)大學(xué);2015年

9 高哲;基于能耗的云遷移方法研究[D];西安理工大學(xué);2016年

10 王福友;計(jì)算密集型應(yīng)用下嵌入式雙機(jī)容錯(cuò)系統(tǒng)研究與實(shí)現(xiàn)[D];西南交通大學(xué);2014年

本文編號(hào)：2608063