一種面向通信開銷的網格工作流調度算法

朱曉虹

（福建對外經濟貿易職業技術學院　信息技術系，福建　福州　350012）

一種面向通信開銷的網格工作流調度算法

朱曉虹

（福建對外經濟貿易職業技術學院信息技術系，福建福州350012）

摘要：采用任務—資源分配圖定義了網格任務調度模型，運用動態規劃的方法提出了面向通信開銷的工作流任務調度算法。采用擴展的拓撲排序算法對具有依賴關系的工作流任務進行劃分，根據劃分的任務子集得到相應的調度階段，在每一階段選擇滿足約束條件和以計算開銷、通信開銷以及任務執行成功率為最優目標函數的資源節點進行任務分配，從而使工作流任務調度目標函數最優。應用GridSim工具包實現了該調度算法，并與Min-Min算法進行對比分析。仿真結果表明，基于動態規劃的網格工作流調度算法具有良好的適應性，且能較好地處理不同網絡環境下任務間存在大量數據傳輸的網格調度問題。

關鍵詞：網格計算；工作流；動態規劃；通信開銷

0　引言

移動互聯網的發展使得地理位置上分散的計算資源可以協同工作，從而組成一個計算網格，實現資源共享［1-2］。由多個相互之間存在數據依賴或時序關系的網格任務組成的網格作業稱為網格工作流作業。對于通信密集型的應用，在網格調度時僅僅考慮計算能力是不夠的，還需要考慮通信需求。在海量數據的網格計算應用中，服務站點需要處理的數據量較為龐大，此時計算開銷對于服務站點來說是影響性能的關鍵因素，為了保證網格計算性能，必須對分布的數據資源進行合理的調度管理［3］?！?br>