一个调度Fork-Join任务图的新算法  

A New Algorithm for Scheduling Fork-Join Task Graphs

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

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

出　　处：《计算机工程与科学》2007年第4期64-67,共4页Computer Engineering & Science

摘　　要：对基于总线的机群系统,本文提出了一种基于任务复制的调度Fork-Join任务图的新算法。该算法通过任务集划分计算调度长度,并在不增加调度长度的同时将任务尽可能调度在已用处理器上,节省处理器数。新算法的时间复杂度高于现有算法,但其调度性能最优。This paper proposes a new algorithm based on task duplication for scheduling Fork-Join task graphs on busbased clusters. It computes the scheduling length by partitioning the task set, and allocates the tasks to the used processors as far as possible without increasing the scheduling length in order to save the number of processors. The time complexity of the proposed algorithm is higher than the existing algorithm, but its scheduling performance is the most superior.

关 键 词：任务调度 调度长度 Fork-Join DAG 

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