云計算下計算能力調(diào)度算法的研究與改進(jìn)
發(fā)布時間：2019-04-27 00:58
【摘要】：近年來,云計算作為一種新的高性能計算模式成為廣大研究學(xué)者的研究熱點(diǎn),各大公司也紛紛推出自己的云平臺,如加利福尼亞大學(xué)研究的Eucalyptus, Apache基金會的Hadoop平臺、以及10gen的MongoDB等。其中Hadoop平臺是開源的,現(xiàn)在已被廣泛使用,它具有分布性、效率高、成本低、可靠性強(qiáng)等優(yōu)點(diǎn),而其中它的一項(xiàng)重要技術(shù)作業(yè)調(diào)度是影響到平臺整體性能與資源利用率的一個關(guān)鍵。作業(yè)調(diào)度技術(shù)是要將進(jìn)入系統(tǒng)的作業(yè)進(jìn)行合理的分配與處理,它的目標(biāo)既要使整個系統(tǒng)能夠有序的運(yùn)行,又要充分有效的利用資源,還要使用戶滿意度盡可能高。但是隨著用戶需求的不斷增多和作業(yè)種類、作業(yè)規(guī)模的不斷增大,目前的調(diào)度算法越來越難滿足用戶的需求,因此研究一種新的作業(yè)調(diào)度算法,既能滿足上述要求,又能結(jié)合實(shí)際應(yīng)用具有重大的意義。 目前應(yīng)用廣泛的作業(yè)調(diào)度算法有先進(jìn)先出(FIFO)算法,這種算法簡單明了,成本低,只適合滿足單作業(yè)或少量作業(yè)的需求；公平調(diào)度算法(Fair Scheduling algorithm),它支持多用戶公平地享用資源,能夠滿足大量作業(yè)進(jìn)入系統(tǒng),但這樣極易造成資源的浪費(fèi)；計算能力調(diào)度算法(Capacity Scheduling algorithm),它吸取了公平算法的不足,根據(jù)作業(yè)的性能分配資源,但這種分配策略過于簡單,容易陷入局部最優(yōu)；國內(nèi)一些學(xué)者分別從系統(tǒng)資源、系統(tǒng)配置、作業(yè)等方面下手深入地研究,試圖提出一些改進(jìn)算法。 本文針對系統(tǒng)的配置,從作業(yè)的總運(yùn)行時間、平均運(yùn)行時間與等待時間著手,利用模擬退火算法在組合優(yōu)化問題上能夠避免局部最優(yōu)的優(yōu)勢,結(jié)合計算能力調(diào)度算法,提出了一種基于模擬退火的計算能力調(diào)度算法,構(gòu)建了模擬退火調(diào)度算法的數(shù)學(xué)模型,選擇計算能力調(diào)度算法的默認(rèn)搜索策略作為初始解,提出一個新的目標(biāo)函數(shù),計算出作業(yè)的解空間,并選擇對數(shù)函數(shù)作為退火策略。該目標(biāo)函數(shù)綜合考慮了作業(yè)的總運(yùn)行時間和作業(yè)等待時間,旨在提高作業(yè)運(yùn)行效率的同時減少作業(yè)的等待時間。為了提高學(xué)習(xí)速度對模擬退火作業(yè)調(diào)度算法進(jìn)行了改進(jìn),在算法中加入了記憶功能,可以大大減少迭代次數(shù),提高搜索速度和算法的收斂速度。 本文在最后詳細(xì)描述了如何在Hadoop平臺下實(shí)現(xiàn)該算法,其中包括平臺的內(nèi)部配置已經(jīng)四種調(diào)度算法的配置。將改進(jìn)的算法與前三種算法分別放入平臺中運(yùn)行,得出了作業(yè)的總運(yùn)行時間與等待時間。最后對實(shí)驗(yàn)結(jié)果進(jìn)行比較與分析,證明了改進(jìn)算法的有效性。
[Abstract]:In recent years, cloud computing as a new high-performance computing model has become the research focus of many researchers, and many companies have launched their own cloud platforms, such as the Hadoop platform of the Eucalyptus, Apache Foundation, which is researched by the University of California. And 10gen's MongoDB and so on. Hadoop platform is open source, it has been widely used, it has the advantages of distribution, high efficiency, low cost, strong reliability and so on. And one of its important technology job scheduling is a key to the overall performance of the platform and resource utilization. Job scheduling technology is to allocate and deal with the jobs entered into the system reasonably. Its goal is not only to make the whole system run in an orderly manner, but also to make full and effective use of resources, and also to make the user satisfaction as high as possible. However, with the increasing demands of users, the types of jobs and the scale of jobs, the current scheduling algorithms are more and more difficult to meet the needs of users. Therefore, a new job scheduling algorithm is studied, which can not only meet the above requirements, but also can meet the requirements mentioned above. It is of great significance to combine practical application. At present, the most widely used job scheduling algorithms are first-in-first-out (FIFO) algorithm, which is simple and simple, low cost, and is only suitable for single job or a small number of jobs. Fair scheduling algorithm (Fair Scheduling algorithm), which supports multi-users to enjoy resources fairly, can satisfy a large number of jobs into the system, but it is easy to waste resources. Computing ability scheduling algorithm (Capacity Scheduling algorithm),) absorbs the deficiency of fair algorithm and allocates resources according to job performance, but this allocation strategy is too simple and easy to fall into local optimization. Some domestic scholars studied the system resource, system configuration, homework and so on, and tried to put forward some improved algorithms. Aiming at the configuration of the system, this paper starts with the total run time of the job, the average run time and the waiting time, utilizes the simulated annealing algorithm to avoid the local optimal advantage on the combinatorial optimization problem, and combines the computing ability scheduling algorithm. A computational capability scheduling algorithm based on simulated annealing is proposed. The mathematical model of simulated annealing scheduling algorithm is constructed. The default search strategy of computational capability scheduling algorithm is selected as the initial solution, and a new objective function is proposed. The solution space of the operation is calculated and the logarithmic function is chosen as the annealing strategy. The objective function takes into account the total running time and the waiting time of the job, in order to improve the running efficiency of the job and reduce the waiting time of the job at the same time. In order to improve the learning speed, the simulated annealing scheduling algorithm is improved. The memory function is added to the algorithm, which can greatly reduce the number of iterations, improve the search speed and the convergence speed of the algorithm. In the end, this paper describes in detail how to implement the algorithm under the Hadoop platform, including the configuration of four scheduling algorithms for the internal configuration of the platform. The improved algorithm and the first three algorithms are put into the platform respectively, and the total running time and waiting time of the job are obtained. Finally, the experimental results are compared and analyzed, and the effectiveness of the improved algorithm is proved.
【學(xué)位授予單位】：太原理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2012
【分類號】：TP338
本文編號：2466547
[Abstract]:In recent years, cloud computing as a new high-performance computing model has become the research focus of many researchers, and many companies have launched their own cloud platforms, such as the Hadoop platform of the Eucalyptus, Apache Foundation, which is researched by the University of California. And 10gen's MongoDB and so on. Hadoop platform is open source, it has been widely used, it has the advantages of distribution, high efficiency, low cost, strong reliability and so on. And one of its important technology job scheduling is a key to the overall performance of the platform and resource utilization. Job scheduling technology is to allocate and deal with the jobs entered into the system reasonably. Its goal is not only to make the whole system run in an orderly manner, but also to make full and effective use of resources, and also to make the user satisfaction as high as possible. However, with the increasing demands of users, the types of jobs and the scale of jobs, the current scheduling algorithms are more and more difficult to meet the needs of users. Therefore, a new job scheduling algorithm is studied, which can not only meet the above requirements, but also can meet the requirements mentioned above. It is of great significance to combine practical application. At present, the most widely used job scheduling algorithms are first-in-first-out (FIFO) algorithm, which is simple and simple, low cost, and is only suitable for single job or a small number of jobs. Fair scheduling algorithm (Fair Scheduling algorithm), which supports multi-users to enjoy resources fairly, can satisfy a large number of jobs into the system, but it is easy to waste resources. Computing ability scheduling algorithm (Capacity Scheduling algorithm),) absorbs the deficiency of fair algorithm and allocates resources according to job performance, but this allocation strategy is too simple and easy to fall into local optimization. Some domestic scholars studied the system resource, system configuration, homework and so on, and tried to put forward some improved algorithms. Aiming at the configuration of the system, this paper starts with the total run time of the job, the average run time and the waiting time, utilizes the simulated annealing algorithm to avoid the local optimal advantage on the combinatorial optimization problem, and combines the computing ability scheduling algorithm. A computational capability scheduling algorithm based on simulated annealing is proposed. The mathematical model of simulated annealing scheduling algorithm is constructed. The default search strategy of computational capability scheduling algorithm is selected as the initial solution, and a new objective function is proposed. The solution space of the operation is calculated and the logarithmic function is chosen as the annealing strategy. The objective function takes into account the total running time and the waiting time of the job, in order to improve the running efficiency of the job and reduce the waiting time of the job at the same time. In order to improve the learning speed, the simulated annealing scheduling algorithm is improved. The memory function is added to the algorithm, which can greatly reduce the number of iterations, improve the search speed and the convergence speed of the algorithm. In the end, this paper describes in detail how to implement the algorithm under the Hadoop platform, including the configuration of four scheduling algorithms for the internal configuration of the platform. The improved algorithm and the first three algorithms are put into the platform respectively, and the total running time and waiting time of the job are obtained. Finally, the experimental results are compared and analyzed, and the effectiveness of the improved algorithm is proved.
【學(xué)位授予單位】：太原理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2012
【分類號】：TP338
【參考文獻(xiàn)】
相關(guān)期刊論文 前10條
1 鄭小花;陳淑燕;武林芝;;模擬退火算法在公交調(diào)度中的應(yīng)用[J];信息化研究;2009年09期
2 冀俊忠;胡仁兵;張鴻勛;劉椿年;;一種混合的貝葉斯網(wǎng)結(jié)構(gòu)學(xué)習(xí)算法[J];計算機(jī)研究與發(fā)展;2009年09期
3 李成華;張新訪;金海;向文;;MapReduce:新型的分布式并行計算編程模型[J];計算機(jī)工程與科學(xué);2011年03期
4 李建鋒;彭艦;;云計算環(huán)境下基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法[J];計算機(jī)應(yīng)用;2011年01期
5 冼進(jìn);余桂城;;基于云計算的作業(yè)調(diào)度算法研究[J];計算機(jī)與數(shù)字工程;2011年07期
6 王凱;吳泉源;楊樹強(qiáng);;一種多用戶MapReduce集群的作業(yè)調(diào)度算法的設(shè)計與實(shí)現(xiàn)[J];計算機(jī)與現(xiàn)代化;2010年10期
7 郭暢;朱金佗;;礦難的多種形式及防治策略[J];科技致富向?qū)?2011年17期
8 陳康;鄭緯民;;云計算:系統(tǒng)實(shí)例與研究現(xiàn)狀[J];軟件學(xué)報;2009年05期
9 陳華根,吳健生,王家林,陳冰;模擬退火算法機(jī)理研究[J];同濟(jì)大學(xué)學(xué)報(自然科學(xué)版);2004年06期
10 孫廣中;肖鋒;熊曦;;MapReduce模型的調(diào)度及容錯機(jī)制研究[J];微電子學(xué)與計算機(jī);2007年09期
相關(guān)碩士學(xué)位論文 前5條
1 孫軍歡;專用系統(tǒng)人機(jī)界面技術(shù)研究[D];哈爾濱工程大學(xué);2009年
2 鄧自立;云計算中的網(wǎng)絡(luò)拓?fù)湓O(shè)計和Hadoop平臺研究[D];中國科學(xué)技術(shù)大學(xué);2009年
3 王芳;基于GPU加速的細(xì)粒度并行模擬退火算法[D];大連理工大學(xué);2009年
4 劉海平;基于主從備份的云計算容錯調(diào)度算法研究[D];浙江工商大學(xué);2010年
5 余楚禮;基于Hadoop的并行關(guān)聯(lián)規(guī)則算法研究[D];天津理工大學(xué);2011年
，本文編號：2466547
本文鏈接：http://sikaile.net/kejilunwen/jisuanjikexuelunwen/2466547.html
最近更新
教材專著
