异构环境下Out-Tree任务图的调度算法  

Scheduling Algorithm for Out-Tree Task Graph in Heterogeneous Environment

作　　者：旷文[1] 张建军[1] 刘永凯[1] 

机构地区：[1]海军工程大学理学院应用数学系,武汉430033

出　　处：《计算机工程》2013年第10期63-67,共5页Computer Engineering

基　　金：国家自然科学基金资助项目"不确定冲突环境中的超对策认知信息学习融合与超对策分析"(70471031);海军工程大学自然科学基金资助项目"现代模糊信息优化处理技术及其应用研究"(HGDJJ05005)

摘　　要：Out-Tree任务图是任务调度问题中的基本结构,现有的多数算法在调度该任务图时凸显出处理器浪费的问题,从而导致算法调度效果欠佳。针对该问题,结合任务复制的调度策略,提出一种基于平均值的启发式算法。该算法在不增加算法调度长度的情况下,尽可能将任务调度至已有的处理器中执行,注重平衡处理器的负载,达到减少使用处理器的目的。实验结果表明,与TDS算法相比,该算法使用的处理器个数较少,且效率较高。Out-Tree task graph is one of basic structurs in task scheduling, and the problem of wasting processors is revealed when many previous algorithms work on it, which results in poor schedule efficiency. This paper proposes a new heuristic algorithm with task duplication based on mean value, which tries to get the shortest schedule length and takes load balances into account to economize the used processors. Experimental results show that the proposed scheduling algorithm can produce better schedule which has less number of used processors and higher efficiency.

关 键 词：Out—Tree任务图 异构计算系统 任务复制 调度长度 标准效率 平均值 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]