通信感知的DAG工作流費用優(yōu)化模型及算法.pdf

1、在云環(huán)境中對服務(wù)進行付費使用已經(jīng)成為一種趨勢，且資源調(diào)度問題一直是云環(huán)境中的核心問題。由于云搭建在異構(gòu)環(huán)境中，通信開銷在云環(huán)境中無法忽略，但現(xiàn)有DAG工作流費用優(yōu)化模型大都未考慮任務(wù)間的通信開銷，難以在實際云環(huán)境中應(yīng)用。為此，提出通信感知的工作流費用優(yōu)化模型CA-DAG，并在分層算法的基礎(chǔ)上，提出針對CA-DAG模型的調(diào)度算法CACO和改進的基于串歸約算法1-CACO。
　　CA-DAG模型是在原有的費用優(yōu)化模型中引入通信開銷，從

2、而使得其能夠在真實的云環(huán)境中應(yīng)用。CACO調(diào)度算法使用前向一致規(guī)則FC求解工作流的最小完工時間，解決最小關(guān)鍵路徑法在本模型中的不適問題;根據(jù)逆向分層策略將任務(wù)分層，使費用優(yōu)化問題從全局轉(zhuǎn)化到局部;采用動態(tài)規(guī)劃方法收集任務(wù)在選擇服務(wù)時產(chǎn)生的零散“時間碎片”，增加任務(wù)的費用優(yōu)化空間，改善費用優(yōu)化效果。
　　在CACO算法的基礎(chǔ)上進一步提出改進算法I-CACO，該算法基于串歸約思想，將DAG工作流中具有串行特征的任務(wù)，歸約到同一時間窗口

3、內(nèi)，實現(xiàn)組內(nèi)任務(wù)的整體費用最優(yōu)。I-CACO算法在任務(wù)調(diào)度之前首先確定DAG工作流中的串歸約組，并使用CACO的分層規(guī)則，在調(diào)度過程中若遇到屬于串歸約組的任務(wù)，就在組內(nèi)采用動態(tài)規(guī)劃的方法進行組內(nèi)費用優(yōu)化。
　　在仿真環(huán)境中實現(xiàn)了CACO和I-CACO，并且實現(xiàn)了原有算法DTL，DBL和TCDBL。對這些算法的費用優(yōu)化效果進行了評估，進行對比實驗，證明了在考慮通信開銷的前提下，CACO的費用優(yōu)化效果比DTL，DBL，TCDBL分別提