【摘要】 针对异构环境下任务图为TIG(task interaction graph)的问题,利用松弛标记法善于利用邻居属性处理大量约束的特点,提出一种任务调度算法.算法把任务看作目标对象,处理器单元看作待分配标记,根据对象间所有可能关系,逐渐排除不相关的处理器单元,选择计算和通信综合性能较好的处理器单元.在兼顾任务执行的计算和通信需求的情况下,能够合理分配资源、提高处理速度、缩短整个应用程序的执行时间.实验结果与用穷举法得出的最优结果比较显示,本算法能较理想地解决异构环境下基于任务交互图的调度问题.更多还原

【Abstract】 This paper focuses on the task scheduling problem on the basis of task interaction graph(TIG) under heterogeneous computing environments.An algorithm of task scheduling in heterogeneous computing environments is presented by taking advantage of relaxation labeling,which is good at handling a broad range of constraints according to neighbor nodes’ attributes.The task nodes are considered as objects,and processing cells are regarded as the labels to be allocated to the objects.According to the possible relationships among objects,uncorrelated processing cells are gradually removed,therefore,those with better computing and communication capacity can be chosen.Experimental results show that it can efficiently distribute resource,improve computing speed and reduce the executing time,and the match results are close to the optimal mapping obtained from exhaustive search algorithm.更多还原