數(shù)據(jù)網(wǎng)格資源調(diào)度

《數(shù)據(jù)網(wǎng)格資源調(diào)度》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、數(shù)據(jù)網(wǎng)格資源調(diào)度---基于改進的并行遺傳算法李輝徐煒民教授上海市上海大學計算機學院200072E-Mail:lanyinghavy@163.com摘要數(shù)據(jù)網(wǎng)格目的是能夠共享異地分布的物理資源，如數(shù)據(jù)資源等。數(shù)據(jù)量過大、資源分布不集中、計算同步等問題的存在，導致對網(wǎng)格調(diào)度算法探索精益求精。本文中，我們針對網(wǎng)格任務的瞬變性、隨機性，以新的建模方式構建基于遺傳算法的網(wǎng)格調(diào)度算法，并對遺傳算法本身進行了改進，針對數(shù)據(jù)網(wǎng)格任務數(shù)量龐大的特點，將程序并行化，探索出適合數(shù)據(jù)網(wǎng)格調(diào)度的進化算法---改進的并行遺傳調(diào)度算法(IMGA)。最后同傳統(tǒng)的Max-Min

2、和GA調(diào)度算法進行了比較,實驗表明該算法對大規(guī)模的數(shù)據(jù)網(wǎng)格任務調(diào)度具有很好的性能。關鍵詞網(wǎng)格，數(shù)據(jù)網(wǎng)格，調(diào)度，遺傳算法，MPI[1]ASchedulingArithmeticBaseonImprovedParallelGAAbstractOnepurposeofDataGridistosharephysicallydistributedresources,suchasdataresourses.Datasetsmassive,resourcesdistributedandcomputingsynchronized,makeuskeepimpro

3、vingschedulingarithmeticinDataGridInthispaper,wehaveimprovedtheGAandexploredParallelDataGridSchedulingGA(IMGA)withanewmodelingmethodsoastosuittheinstantaneouschange,randomicityandhugenessofthetasks。Atlastwehavecomparedtotwoofthetraditionalarithmetics---Max-MinandGA,andtheexp

4、erimentresultsindicatethatthearithmeticwedesignedhashigherperformanceforcosmicallyDataGridtaskscheduling.KeywordsGrid;DataGrid;Scheduling;GeneticArithmetic;MPI[1]1引言網(wǎng)格計算即包含實際的網(wǎng)絡服務，又包括在網(wǎng)格中相互連接的大量的計算設備[2]。早期網(wǎng)格主要集中在對高性能計算的研究，然而現(xiàn)在，許多領域的科學和工程計算，如高能物理、航空航天、地震工程、天體物理、生物信息學等[3]，還需要協(xié)

5、同、共享大量地域分布松散、資源異構的數(shù)據(jù)集，并且滿足整體實時性。例如CMS[4]物理學家們訪問他們的試驗結果，這些由原子對撞產(chǎn)生的TB乃至PB的數(shù)據(jù)被分成不同的層次，分配到網(wǎng)格中的超級計算機。如何調(diào)度這些數(shù)據(jù)資源才能提高運算效率和可靠性呢？這就需要一種優(yōu)良的調(diào)度算法。廣義的講，調(diào)度問題考慮的是隨著時間變化，如何調(diào)度有限的資源并在執(zhí)行任務的同時滿足特定約束[5]。類似這種問題都是NP難的問題，因此引起了用遺傳算法處理這些問題的興趣?！　￡P于調(diào)度算法的研究很多:RBuyya和Abraham等人提出了一種基于應用經(jīng)濟模型的優(yōu)化調(diào)度模型[6],其目的是

6、在資源的擁有者和使用者之間建立一種“交易”,以盡可能低的費用滿足資源使用者進行計算任務的最低要求，并介紹了模擬退火等進化算法在網(wǎng)格資源調(diào)度中的應用[7]；ZhihongXu等人介紹了蟻群算法[8]的應用。但是他們都是一次分配完畢便對任務進行固定的調(diào)度，沒能順應網(wǎng)格任務變化的特性。在常用的網(wǎng)格調(diào)度算法中:有FIFO(如PBS和LSF采用的均是此種算法)、Min-Min或Max-Min[9]、A*和GA等算法,TracyD.kraun等人已經(jīng)做了詳細的研究[10]，結果表明,GA算法在不同ETC(預測執(zhí)行時間)矩陣下的性能是最好的,Min-Min(

7、Max-Min)和A*次之。SeonhoKim和JonB.Weissman[11]等人也對遺傳算法和其他算法(如Baseline、IDLT、CDLT、TDP等)作過比較，同樣表明遺傳算法的預測執(zhí)行時間最短，而且效果最好。遺傳算法是基于自然選擇和基因遺傳學原理的搜索算法。它將“適者生存”這一基本的達爾文進化理論引入串結構，并且在串之間進行有組織但又隨機的信息交換。隨著算法的進行優(yōu)良的品質(zhì)便會被逐漸保留并加以組合直到產(chǎn)生出優(yōu)化的個體[12]。另外它的優(yōu)點是“魯棒性”強，而且搜索空間上不存在限制性假設。本文介紹了一種基于遺傳算法的調(diào)度策略,采用十進制

8、編碼方式，在滿足任務之間邏輯關系的條件下,盡可能地縮短任務的完成時間,提高資源的使用效率。本文首先對網(wǎng)格調(diào)度的相關工作談起，分析了網(wǎng)格調(diào)度器在數(shù)據(jù)網(wǎng)格