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

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

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

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

4、后，對DAG圖中的任務(wù)節(jié)點(diǎn)進(jìn)行計算排序，考慮復(fù)雜DAG圖中的拓?fù)浣Y(jié)構(gòu)和優(yōu)先級約束，對每個染色體進(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)的空閑時間隙來重復(fù)出度最多或者完成時間最晚

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