云計(jì)算環(huán)境下基于復(fù)雜DAG圖的任務(wù)調(diào)度策略研究.pdf

1、云計(jì)算是一種新興的資源使用和交付模式，它以一種有趣的形式呈現(xiàn)并且推動(dòng)科學(xué)的發(fā)展和商業(yè)應(yīng)用。類似于水電，云計(jì)算通過按需消費(fèi)向用戶提供一種即時(shí)、靈活和可擴(kuò)展的服務(wù)。云計(jì)算旨在允許以完全虛擬化的方法訪問大量的計(jì)算能力。通過整合資源并提供一個(gè)單一的系統(tǒng)視圖，目的在于提供一個(gè)實(shí)用的計(jì)算。云計(jì)算表示一種一個(gè)計(jì)算基礎(chǔ)設(shè)施可以作為一個(gè)“云”的模式，企業(yè)或者個(gè)人均可以從世界的任何地方訪問這些及應(yīng)用。
　　如何有效快速地將用戶提交的應(yīng)用任務(wù)分配到各個(gè)

2、處理器上執(zhí)行，以獲得最短的響應(yīng)時(shí)間和最有效的執(zhí)行結(jié)果，這一難題使得云計(jì)算中的任務(wù)調(diào)度問題成為學(xué)術(shù)界的熱點(diǎn)問題。許多經(jīng)典與新興的算法被應(yīng)用到云計(jì)算的調(diào)度中，為適應(yīng)云計(jì)算的異構(gòu)性、動(dòng)態(tài)性和可擴(kuò)展性均作出了一定的調(diào)整和改進(jìn)?，F(xiàn)今學(xué)術(shù)界遇到的云計(jì)算調(diào)度的問題越來越多，也越來越復(fù)雜。許多科學(xué)應(yīng)用，如生物信息學(xué)、化學(xué)、天文學(xué)等，這些應(yīng)用中包含大量的任務(wù)，任務(wù)間存在復(fù)雜的先后約束關(guān)系，這些應(yīng)用需要大量的計(jì)算和通信開銷，在云計(jì)算系統(tǒng)中處理時(shí)已不能使用簡

3、單的圖來表示。
　　本文主要研究云計(jì)算中的任務(wù)調(diào)度，使用遺傳算法來輔助完成云計(jì)算下的任務(wù)調(diào)度。本文中主要針對(duì)復(fù)雜的任務(wù)使用復(fù)雜的DAG圖來進(jìn)行表示，并將任務(wù)調(diào)度到云計(jì)算平臺(tái)上的處理器上進(jìn)行處理。
　　本文的主要內(nèi)容和創(chuàng)新點(diǎn)如下:
　　1、提出了一種自適應(yīng)工作流調(diào)度算法IAHA(Improved Adaptive heuristic algorithm)。該算法主要對(duì)HSGA算法進(jìn)行改進(jìn)，首先將用戶提交的任務(wù)轉(zhuǎn)為DAG圖

4、后，對(duì)DAG圖中的任務(wù)節(jié)點(diǎn)進(jìn)行計(jì)算排序，考慮復(fù)雜DAG圖中的拓?fù)浣Y(jié)構(gòu)和優(yōu)先級(jí)約束，對(duì)每個(gè)染色體進(jìn)行預(yù)先優(yōu)化，以減少迭代次數(shù)更快獲得最優(yōu)解，再根據(jù)種群的情況自適應(yīng)改變交叉和變異率來控制和引導(dǎo)算法獲得最優(yōu)解。
　　2、提出了帶任務(wù)重復(fù)的工作流調(diào)度算法D-IAHA(Improved Adaptive heuristicalgorithm with duplication)。該算法利用處理器上出現(xiàn)的空閑時(shí)間隙來重復(fù)出度最多或者完成時(shí)間最晚

5、的父任務(wù)來達(dá)到減少處理器間任務(wù)通信時(shí)間的目的，從而使子任務(wù)的開始時(shí)間提前，整個(gè)調(diào)度的調(diào)度時(shí)間縮短。與此同時(shí)考慮了冗余任務(wù)的刪除，在調(diào)度后檢查是否存在冗余的重復(fù)任務(wù)，若存在則刪除，這樣不至于增加處理器的計(jì)算負(fù)載。
　　3、提出了一種帶任務(wù)重復(fù)的任務(wù)劃分策略算法D-ITPS(Improved task partitioningStrategy with duplication)，該算法首先將DAG圖中的一些滿足歸并條件的任務(wù)進(jìn)行歸并，