异构环境下基干松弛标记法的任务调度

提出了一种基于松弛标记法的任务调度算法（Relaxation labeling based task scheduling,RLBTS）,将任务映射到异构资源（处理器计算能力和链路的通信能力不同）上．松弛标记法善于处理大量的约束条件,其核心思想是结点的标签分配通常受该结点的邻居结点某些属性的影响．依据邻居约束关系,可以逐渐排除不相关因素,迅速缩小搜索空间．该算法统筹兼顾了任务执行的计算需求和通信需求问题,实验结果表明对于通信和计算需求都很高的任务和通信密集型任务,RLBTS不失为一种有效的调度算法．

Relaxation Labeling Based Task Scheduling in Heterogeneous Environments

On the base of relaxation labeling, an algorithm of task scheduling in heterogeneous computing environments is presented. This new method maps data-processing tasks onto heterogeneous resources (i.e., processors and links of various capacities), and takes both computing requirement and communication needs into account. Relaxation labeling can handle a broad range of constraints and its key idea is that the label of a node is typically influenced by the features of the node's neighborhood in the graph. According to neighborhood restrictions, it can gradually get rid of uncorrelated factors and rapidly shrink the searching space. Experimental results show that it performs very well for applications that have high computing and communication requirements or communication-intensive requirements.