An Algorithm of Allocating Tasks to Multiprocessors Based on Dynamic Critical Task
Sun Shi · Chinese Journal of Computers · 2007
One of main obstacles in achieving high performance is the scheduling for multiprocessors.Scheduling algorithm based on task duplication is a better way to solve this problem.The authors discuss several recently reported duplication-based scheduling algorithms and propose a novel algorithm.The proposed algorithm,which is called the algorithm of allocating tasks to multiprocessors based on Dynamic Critical Task(DCT),is different from the previously proposed algorithms in a number of ways.Besides a directed acyclic graph(DAG),the gantt graph also is introduced into the scheduling process.Based on the gantt graph DCT algorithm a set of time parameters is put forward to accurately describe the task positions and states.After dynamically computing the task time parameters,DCT algorithm determines the critical tasks of a processor and then optimizes this processor schedule length through duplicating the critical father tasks of the critical tasks to this processor.Once the schedule length is shorter,DCT algorithm determines the critical tasks again for the next scheduling such that DCT algorithm can tackle the drawbacks of the greedy algorithms(e.g.OSA,PPA and CPFD algorithm).DCT algorithm also employs several strategies to reduce the number of processors.The analytical and experimental results show DCT algorithm has advantages over the previously proposed algorithms in terms of the schedule length and the number of processors.