摘要
网格环境中的任务调度面临着海量的计算和通信资源环境,所以调度者需要考虑资源的选择问题.传统的资源选择方法一般只考虑计算能力或通信能力的最大化,没有考虑资源的通信模式与应用的匹配问题.本文在Remos研究的基础上,提出了一个完整的基于应用通信模式的网格结点选择算法.算法使用子图同构的辨识方法来判断网格结点的连通关系是否与应用模式相匹配,在满足通信模式约束的前提下,再用贪婪算法来选择计算和通信均较优化的结点.在通用算法的基础上,特别考虑了基于Master-Slave和All-to-All应用模式简化结点选择算法.最后,利用仿真方法,将本文的算法和随机选择法进行了比较,结果表明本文算法选择的网格结点不但满足应用的通信约束,而且性能较优.
Grid computing provides tremendous computation and communication resources for tasks scheduling, meanwhile there raises the problem of Grid resources selection must be considered by scheduler. Traditional resources selection methods only care how to maximize computation and communication capacity of networks resources. However, the communication structure of the resources must match the communication pattern of the application is generally ignored by traditional scheduler. This paper presents an algorithm of communication pattern based node selection for Grid Computing, the algorithm is improved upon Remos project. A subgraph identification algorithm is used to decide the graph composed of the selected Grid nodes is match to the communication pattern of the application. After satisfies the communication pattern constraint, a Greedy Algorithm is used to select the optimization nodes. As special case of the general algorithm, two simplified algorithms based on Master-Slave and All-to-All application pattern respectively is introduced. The presented algorithms have been tested and compared with a random selection method in a simulation environment. The tests results show that the nodes set selected by the presented algorithms are not only satisfy the communication pattern requirement of the application but also have optimization computation and communication capacity.
出处
《小型微型计算机系统》
CSCD
北大核心
2008年第8期1479-1485,共7页
Journal of Chinese Computer Systems
基金
国家自然科学基金项目(60503048)资助
关键词
网格计算
通信模式
结点选择
子图同构
任务调度
grid computing
communication pattern
node selection
subgraph isomorphism
task scheduling
