LSA_IT:一种In-Tree任务图的分层调度算法  

LSA_IT:Layered Scheduling Algorithm for In-Tree Task Graph

作　　者：张艳[1] 李延红[1] 

机构地区：[1]深圳大学信息工程学院,广东深圳518060

出　　处：《计算机工程与应用》2006年第31期23-24,63,共3页Computer Engineering and Applications

摘　　要：In-Tree任务图可用来求解归并排序、求和等分治问题的并行。针对该类任务图,提出了一种分层调度算法——LSA_IT。它对任务图逐层调度。调度中,根据优先级,保证任务的最优前驱被优先调度,并在不影响调度长度的同时,将任务尽可能地调度到其已调度兄弟所在处理器上。实验表明,与TDS、DCP、MCP算法相比,LSA_IT的调度性能最优。The In-Tree task graph can be used to solve the parallel of divide-and-conquer problems,such as merging sorting and summing etc.Specially aiming at this kind of task graph,this paper proposes a layered algorithm,called LSA_IT.It schedules the task graph by level.During the scheduling,according to the priority,it guarantees the most superior predecessor of task is firstly scheduled,and allocates the nodes to the processors of its scheduled sibling as possible without changing the scheduling length.The experiment shows,by comparing with TDS,DCP,MCP,LSA_IT has the best scheduling performance.

关 键 词：任务调度 有向无环图 调度长度 In—Tree 

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