基于动态关键任务的多处理器任务分配算法  

An Algorithm of Allocating Tasks to Multiprocessors Based on Dynamic Critical Task

作　　者：兰舟[1] 孙世新[1] 

机构地区：[1]电子科技大学计算机科学与工程学院,成都610054

出　　处：《计算机学报》2007年第3期454-462,共9页Chinese Journal of Computers

摘　　要：多处理器调度问题是影响系统性能的关键问题,基于任务复制的调度算法是解决多处理器调度问题较为有效的方法.文中分析了几个典型的基于任务复制算法,提出了基于动态关键任务(DCT)的多处理器任务分配算法.DCT算法以克服贪心算法不足为要点,调度过程中动态计算任务时间参数,准确确定处理器的关键任务,以关键任务为核心优化调度,逐步改善调度结果,最终取得最优的调度结果.分析和实验证明,DCT算法优于现有其它同类算法.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.

关 键 词：调度长度 任务复制 多处理器系统 任务分配 并行计算 同构系统 

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