本文選題：云計(jì)算 + 任務(wù)調(diào)度�。� 參考：《電子科技大學(xué)》2014年碩士論文

【摘要】：在云計(jì)算環(huán)境下,隨著計(jì)算機(jī)集群中的動態(tài)節(jié)點(diǎn)變化、節(jié)點(diǎn)中資源的動態(tài)變化以及大規(guī)模的任務(wù)需求接踵而來,我們將面臨著如何提高任務(wù)調(diào)度系統(tǒng)的資源利用率、如何達(dá)到負(fù)載均衡以及如何提升系統(tǒng)的整體性能和效率等問題。在云計(jì)算研究領(lǐng)域中,任務(wù)調(diào)度問題一直是一個(gè)比較典型的NP-Hard問題。盡管國內(nèi)外許許多多的研究學(xué)者致力于研究這個(gè)問題,但是仍然沒有提出一個(gè)很好的解決方案。其中,提高系統(tǒng)的負(fù)載均衡率是提高系統(tǒng)整體性能的一個(gè)有效方法,至今也有很多研究者研究出許多相關(guān)成果,但是以求達(dá)到更好,負(fù)載均衡算法尚存在不足,需要繼續(xù)改進(jìn)。本論文的重點(diǎn)是研究并改進(jìn)一個(gè)動態(tài)負(fù)載均衡(Dynamic Load Balancing,即DLB)算法Work-stealing,使得任務(wù)能夠高效并行執(zhí)行,使得各臺機(jī)器的負(fù)載均衡,提高任務(wù)調(diào)度系統(tǒng)的并行資源利用率和整體性能。其基本思想是:由于一個(gè)任務(wù)調(diào)度系統(tǒng)中各個(gè)計(jì)算節(jié)點(diǎn)的處理能力不同,處理任務(wù)的快慢也會有差別,輕載節(jié)點(diǎn)可以按照某種策略被選為Thief,然后去重負(fù)載的節(jié)點(diǎn)上竊取任務(wù)執(zhí)行,與重載節(jié)點(diǎn)分擔(dān)任務(wù),縮短系統(tǒng)的時(shí)間跨度Make Span,提高系統(tǒng)的整體效率。在論文的研究過程中,首先對任務(wù)調(diào)度和負(fù)載均衡算法的相關(guān)理論進(jìn)行調(diào)研,對Work-stealing算法的相關(guān)成果進(jìn)行研究,并對本文提出的三種竊取任務(wù)數(shù)量方面的改進(jìn)策略(加法級數(shù)、乘法級數(shù)、二分法)和兩種竊取任務(wù)時(shí)機(jī)(空閑時(shí)竊取和預(yù)取策略)進(jìn)行分析對比,最后針對Work-stealing算法的這兩個(gè)方面綜合改進(jìn)。本文中還設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)原型任務(wù)調(diào)度系統(tǒng),主要包含了中心任務(wù)調(diào)度服務(wù)器和執(zhí)行器Worker兩類組件,可以實(shí)現(xiàn)任務(wù)分發(fā)、任務(wù)竊取等相關(guān)操作。在系統(tǒng)模型中,使用改進(jìn)的動態(tài)負(fù)載均衡算法Work-stealing實(shí)現(xiàn)對系統(tǒng)中的任務(wù)進(jìn)行動態(tài)分發(fā)和遷移,盡量消除和減少集群系統(tǒng)中各個(gè)計(jì)算節(jié)點(diǎn)負(fù)載不均勻的現(xiàn)象。最后,論文使用實(shí)驗(yàn)?zāi)M的方式把改進(jìn)的Work-stealing算法與比較經(jīng)典的負(fù)載均衡算法以及原有的Work-stealing算法進(jìn)行對比,來驗(yàn)證改進(jìn)算法的性能和負(fù)載均衡率。實(shí)驗(yàn)過程中,使用了任務(wù)的最終完成時(shí)間Make Span、吞吐率、資源綜合利用率和負(fù)載均衡度等技術(shù)指標(biāo)。實(shí)驗(yàn)數(shù)據(jù)表明,改進(jìn)的Work-stealing算法與其他算法相比,整體性能都有所提高,尤其是在Make Span和吞吐率方面,與原有的Work-stealing算法相比,提高了11.7%。
[Abstract]:In the cloud computing environment, with the change of dynamic nodes in the cluster, the dynamic changes of resources in the nodes and the large-scale task requirements, we will be faced with how to improve the resource utilization of task scheduling system. How to achieve load balance and how to improve the overall performance and efficiency of the system. In the field of cloud computing, task scheduling is a typical NP-Hard problem. Although many researchers at home and abroad have devoted themselves to this problem, they have not put forward a good solution. Increasing the load balancing rate of the system is an effective method to improve the overall performance of the system. Up to now, many researchers have studied a lot of related results, but in order to achieve better, load balancing algorithm is still inadequate, need to continue to improve. The emphasis of this paper is to study and improve a dynamic load balancing (DLB) algorithm, Work-Stealing. which makes the tasks execute in parallel efficiently, makes each machine load balance, and improves the utilization ratio of parallel resources and the overall performance of the task scheduling system. The basic idea is: due to the different processing capacity of each computing node in a task scheduling system, the speed of processing tasks will also be different. The light load node can be selected as the third node according to a certain strategy, then steal the task execution on the heavy load node, share the task with the heavy load node, shorten the time span of the system make Span, and improve the overall efficiency of the system. In the research process of this paper, firstly, the related theories of task scheduling and load balancing algorithm are investigated, and the related results of Work-Stealing algorithm are studied, and three improved strategies (additive series) proposed in this paper for stealing the number of tasks are proposed. The multiplicative series, dichotomy) and two kinds of stealing task timing (free time theft and prefetching strategy) are analyzed and compared. Finally, the two aspects of Work-Stealing algorithm are comprehensively improved. In this paper, a prototype task scheduling system is designed and implemented, which mainly includes two kinds of components: the central task scheduling server and the executor worker, which can realize the task distribution, task theft and other related operations. In the system model, the improved dynamic load balancing algorithm, Work-Stealing, is used to dynamically distribute and migrate the tasks in the system, so as to eliminate and reduce the uneven load of each computing node in the cluster system. Finally, the improved Work-Stealing algorithm is compared with the classical load balancing algorithm and the original Work-Stealing algorithm in order to verify the performance and load balancing rate of the improved algorithm. In the process of the experiment, the final completion time of the task, such as make Span, throughput, comprehensive utilization of resources and load balance, is used. Experimental data show that compared with other algorithms, the overall performance of the improved Work-Stealing algorithm is improved, especially in the area of make span and throughput, compared with the original Work-Stealing algorithm, the performance of the improved Work-Stealing algorithm is improved by 11.7%.
【學(xué)位授予單位】：電子科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TP301.6;TP393.07

【參考文獻(xiàn)】

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

1 蔣江,張民選,廖湘科;基于多種資源的負(fù)載平衡算法的研究[J];電子學(xué)報(bào);2002年08期

，

本文編號：2053738