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

对基于总线的机群系统,本文提出了一种基于任务复制的调度Fork-Join任务图的新算法。该算法通过任务集划分计算调度长度,并在不增加调度长度的同时将任务尽可能调度在已用处理器上,节省处理器数。新算法的时间复杂度高于现有算法,但其调度性能最优。

A New Algorithm for Scheduling Fork-Join Task Graphs

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.