网格优化有向超图任务调度算法

Grid Optimized Directed Hypergraph Task Scheduling Algorithm

任务调度是网格计算的一个重要部分.分析网格环境下任务调度的特点以及传统DAG图的优缺点,吸取有向超图的优点,将有向超图理论融合网格环境特征,建立了网格环境下的优化有向超图模型,并在此基础上通过网格优化有向超图的水平构形、标号及带宽计算实现任务对网格资源的映射与调度,提出网格优化有向超图任务调度算法GODHTS.模拟实验结果证明了该模型及其算法的有效性和优越性.

Task scheduling is an important part in Grid computing. In the paper, characters of task scheduling in Grid and advantages and shortcomings of traditional DAG are analysed, and a optimized directed hypergraph model is built by drawing advantages of directed hypergraph and combining hypergraph theory with characters of Grid environment. Based on the model, mapping and scheduling from tasks to Grid resources are realized by making use of level structure, tab and bandwidth computing of Grid optimized directed hypergraph, and a Grid optimized directed hypergraph task scheduling algorithm, GODHTS, is proposed. Simulation results show that validity and superiority of the proposed model and algorithm are obvious.