本文選題：分布式并行計算　切入點：任務(wù)調(diào)度　出處：《東北大學(xué)》2014年碩士論文

【摘要】：分布式并行計算可以提供相對廉價且強(qiáng)大的處理能力,在研究和應(yīng)用領(lǐng)域都得到了廣泛的關(guān)注。負(fù)載平衡是影響分布式并行計算性能的重要因素之一,負(fù)載平衡策略的效率直接關(guān)系到分布式并行系統(tǒng)的執(zhí)行效果。負(fù)載平衡作為提高分布式并行計算性能的關(guān)鍵技術(shù),是一個NP問題,因此分布式并行系統(tǒng)只能通過優(yōu)化得到近似解而不能獲得最優(yōu)的負(fù)載平衡。分布式并行系統(tǒng)具有的特點也進(jìn)一步增加了負(fù)載平衡難度：首先,分布式并行計算系統(tǒng)中節(jié)點的異構(gòu)性和任務(wù)的異構(gòu)性增加了負(fù)載平衡策略的難度；其次,網(wǎng)絡(luò)的異構(gòu)性也對負(fù)載平衡策略提出了挑戰(zhàn)；再次,分布式并行系統(tǒng)的不斷擴(kuò)展要求負(fù)載平衡策略具有良好的可擴(kuò)展性；最后,負(fù)載平衡策略需要適應(yīng)分布式并行系統(tǒng)的動態(tài)性。這使得,目前對負(fù)載平衡的研究在任務(wù)調(diào)度模型、算法復(fù)雜程度、信息獲取、數(shù)據(jù)傳輸代價、調(diào)整策略等方面存在一些問題。針對上述問題,本文在現(xiàn)有研究的基礎(chǔ)上設(shè)計了任務(wù)調(diào)度模型,并基于此模型提出一種簡單高效的負(fù)載平衡算法。(1)針對分布式并行環(huán)境的特點設(shè)計了任務(wù)調(diào)度模型。首先,抽象出包含處理數(shù)據(jù)的任務(wù)和純計算任務(wù)的任務(wù)模型。其次,抽象出接近實際的系統(tǒng)結(jié)構(gòu)；基于歷史值的影響設(shè)計了考慮工作節(jié)點計算能力動態(tài)性和異構(gòu)性的處理機(jī)模型；提出標(biāo)準(zhǔn)網(wǎng)絡(luò)距離的概念,更好地處理網(wǎng)絡(luò)的動態(tài)變化和計算通信開銷,并基于此設(shè)計了包含局域網(wǎng)和廣域網(wǎng)的通信模型。最后,根據(jù)設(shè)計的模型給出任務(wù)組織形式、遷移方式以及本文負(fù)載平衡算法要解決的問題。(2)基于設(shè)計的任務(wù)調(diào)度模型提出一種高效的負(fù)載平衡算法。算法將負(fù)載平衡分為Assignment和Redistribution兩個過程,針對兩個過程分別提出了簡單且準(zhǔn)確性較高的任務(wù)調(diào)度算法(SHAS:Simple and High Accuracy Scheduling Algorithm)和基于性能收益因子的動態(tài)負(fù)載調(diào)整算法(DLAPGF:Dynamic Load Adjustment Algorithm based on Performance Gains Factor)。SHAS結(jié)合了按需和周期性的信息收集方式,并采用捎帶信息的方式進(jìn)一步提高信息的準(zhǔn)確性,在此基礎(chǔ)上充分考慮通信開銷和數(shù)據(jù)傳輸代價,提出任務(wù)最終完成時間較準(zhǔn)確的計算方式,最后在提出的任務(wù)調(diào)度原則的指導(dǎo)下采用Min-Min算法對新任務(wù)進(jìn)行調(diào)度。DLAPGF通過分析得出負(fù)載平衡目標(biāo),然后基于標(biāo)準(zhǔn)網(wǎng)絡(luò)距離確定伙伴節(jié)點,并采用改進(jìn)的交互信息反饋方式獲取伙伴節(jié)點的信息,最后根據(jù)工作節(jié)點的最終完成時間提出性能收益因子的概念,并在此概念的基礎(chǔ)上采用任務(wù)交換和任務(wù)遷移操作實現(xiàn)動態(tài)調(diào)整策略,降低了數(shù)據(jù)傳輸代價。同時SHAS和DLAPGF在一定程度對系統(tǒng)的動態(tài)性進(jìn)行了處理。(3)基于系統(tǒng)完成時間、系統(tǒng)平衡性、數(shù)據(jù)傳輸代價和消息開銷四個性能指標(biāo),分別對SHAS和DLAPGF的實驗結(jié)果進(jìn)行對比和分析,表明了提出算法的有效性。同時,驗證了參數(shù)和系統(tǒng)動態(tài)性對算法效率的影響。
[Abstract]:Distributed parallel computing can provide relatively cheap and powerful processing power , and has gained wide attention in research and application fields . Load balancing is one of the most important factors affecting distributed parallel computing performance . Load balancing is a key technique that affects distributed parallel computing performance . The load balancing act as a key technology to improve the distributed parallel computing performance . The load balancing act as a key technology to improve distributed parallel computing performance . The load balancing act as a key technology to improve the distributed parallel computing performance . The distributed parallel system can only be optimized to get the optimal load balance . The distributed parallel system has the characteristics of increasing the load balancing difficulty . First , the heterogeneity of the nodes in the distributed parallel computing system and the heterogeneity of the tasks increase the difficulty of the load balancing strategy .
Secondly , the heterogeneity of the network also presents a challenge to the load balancing strategy .
Thirdly , the expansion of the distributed parallel system requires that the load balancing strategy has good scalability .
Finally , the load balancing strategy needs to adapt to the dynamic of the distributed parallel system . This makes the research on load balancing have some problems in task scheduling model , algorithm complexity , information acquisition , data transmission cost , adjustment strategy , etc . Aiming at the above problems , this paper designs a task scheduling model based on the existing research .
Based on the historical value , a processor model considering the dynamic and heterogeneous computing ability of the working nodes is designed .
In this paper , the concept of standard network distance is put forward to better deal with the dynamic change of network and calculate the communication cost . Finally , according to the design model , a kind of efficient load balancing algorithm is proposed . SHAS combines the information collecting mode with the demand and periodicity , and further improves the accuracy of the information by using the way of backing up the information . In the end , the method of calculating the performance benefit factor is proposed by using the Min - Min algorithm . At the same time , the dynamic performance of the system is determined by using the improved interactive information feedback method .

【學(xué)位授予單位】：東北大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TP338;TP301.6

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 楊穎;楊磊;樂嘉錦;;基于范圍分割數(shù)據(jù)的負(fù)載平衡算法的研究[J];計算機(jī)應(yīng)用研究;2006年04期

2 胡益紅;蔣加伏;趙嘉;;一種基于生態(tài)捕食模型的網(wǎng)絡(luò)負(fù)載平衡算法[J];計算機(jī)工程與應(yīng)用;2010年19期

3 王廣召，，馬立勇;一個基于局部服務(wù)策略的最優(yōu)靜態(tài)負(fù)載平衡算法[J];哈爾濱電工學(xué)院學(xué)報;1994年03期

4 魏振華,洪炳熔,喬永強(qiáng),蔡則蘇,彭俊杰;基于偏差信息的星載計算機(jī)系統(tǒng)負(fù)載平衡算法的研究[J];宇航學(xué)報;2002年06期

5 董肖;;兩種負(fù)載平衡算法的設(shè)計與比較[J];電腦與信息技術(shù);2007年06期

6 王鵬;董渭清;王甜;;基于反饋的片上多處理器系統(tǒng)層次負(fù)載平衡算法[J];西安交通大學(xué)學(xué)報;2008年02期

7 謝紅薇;謝顯宇;;基于內(nèi)容的網(wǎng)絡(luò)集群負(fù)載平衡算法模型[J];計算機(jī)應(yīng)用與軟件;2010年01期

8 劉曉尼;祝永志;傅瑩;;一種基于異構(gòu)系統(tǒng)的動態(tài)負(fù)載平衡算法[J];計算機(jī)與信息技術(shù);2010年10期

9 蔣江,張民選,廖湘科;一種基于多種資源的負(fù)載平衡算法的設(shè)計與模擬[J];計算機(jī)工程與科學(xué);2002年06期

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

中國重要報紙全文數(shù)據(jù)庫 前1條

1 本報記者 曉嵐;Radware：鎖定負(fù)載均衡[N];計算機(jī)世界;2002年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前1條

1 劉旭;基于圖剖分和圖排序的負(fù)載平衡算法研究[D];中國工程物理研究院;2008年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 曲全民;一種高效的負(fù)載平衡算法研究與設(shè)計[D];東北大學(xué);2014年

2 胡茂偉;一種基于分級的負(fù)載平衡算法[D];暨南大學(xué);2002年

3 黃珊;面向集群的負(fù)載平衡算法的研究與實現(xiàn)[D];南京農(nóng)業(yè)大學(xué);2009年

4 余玉連;基于Cayley圖互連網(wǎng)絡(luò)的負(fù)載平衡算法研究[D];華南理工大學(xué);2010年

5 郭冰;異構(gòu)Web Server集群負(fù)載平衡算法的研究[D];河北工業(yè)大學(xué);2003年

6 郭建根;HP2P網(wǎng)絡(luò)負(fù)載平衡算法的設(shè)計與仿真[D];西安電子科技大學(xué);2014年

7 姚沖;并行系統(tǒng)互連網(wǎng)絡(luò)負(fù)載平衡算法的設(shè)計與實現(xiàn)[D];大連理工大學(xué);2009年

8 鄭錦;實時分布式系統(tǒng)的容錯設(shè)計與負(fù)載平衡算法的研究[D];遼寧工程技術(shù)大學(xué);2004年

9 胡陳麗;GECISM中基于P2P的多機(jī)配置模型及負(fù)載平衡算法研究[D];河北大學(xué);2006年

10 何毅權(quán);基于sort first并行渲染系統(tǒng)的動態(tài)負(fù)載平衡研究[D];電子科技大學(xué);2011年

本文編號：1707255