元计算环境下的支持依赖任务的 O GS 算法研究.pdf

1
2 2
e algo rithm assign s a fixed p riority fo r each task. It, then, filters ou t all independen t
task s acco rding to the sam e p riority. F inally, it m ap s these independen t task s to all m ach ines
availab le u sing som e heu ristics by fo rerunners fo r comparison. In O GS A lgo rithm , expect m a
ch ine ready time is u sed, the comp letion times of all p redecesso rs are also con sidered as heu ristic
info rm ation. So, idle times in m ach ines can be decreased, and the M akespan then be imp roved.
By test, it is demon strated that the perfo rm ance of O GS exceeds GS algo rithm s.
Keywords　 m app ing and schedu ling, heu ristics, dependen t task, m etasystem , heterogeneou s
system
构均一系统上调度的例子. 关于依赖任务在异构系
1　引　言 统上调度的典型算法是分代算法 (Generation A lgo
rithm s, GS) [2, 3 ]. 论文基于 GS 算法的基本思路, 提
在广域异构的元计算系统[1 ] 上开发优化的任务 出了基于优先数过滤的、支持依赖任务的、优化的分
调度算法是N P HA RD 的, 因此必须提出一些启发 代调度算法O GS (Op timal GS). 与 GS 算法不同的
式调度算法来获得最优或近优解. 现有的启发式调 是: O GS 不只考虑机器就