TSA-OT: An Algorithm Scheduling An Out-Tree DAG
Zhen Liu · Chinese Journal of Computers · 2001
As to schedule tasks to processors, an algorithm with the shortest scheduling length is always emphasized, and using as less processors as possible is always ignored in this algorithm. This paper purposes an algorithm, called TSA -OT, based on task duplication to schedule an Out Tree task graph which represents a number of divide and conquer algorithms. TSA -OT algorithm assigns the task nodes of the critical paths to processors at first, and allocates the rest nodes to the used processors as possible without changing the scheduling length. And all the communication of an Out Tree graph is zeroized in this algorithm. By the comparison among TDS, CPFD, DCP and TSA -OT algorithms, it shows that TSA -OT algorithm has the shortest scheduling length, and takes less or equal number of processors.