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

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

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

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