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

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

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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 云中子;解析新時代下的高性能計算[N];中國信息化周報;2015年

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

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

8 ;IBM TotalStorage DS4800[N];中國電子報;2005年

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文編號：2608063